Giáo trình cơ sở dữ liệu - Chương 3

Ch ng 3. Đ I S QUAN Hươ Ạ Ố Ệ GV: Đ ng Qu c Vi tặ ố ệ dqviet@cit.ctu.edu.vn 3. 2 Đ i s quan hạ ố ệ (Relational Algebra) n Đ i s quan h là m t b ạ ố ệ ộ ộ α = (M, P ), trong đó F M : t p các quan h cho tr cậ ệ ướ F P : t p các phép toán c b n sau.ậ ơ ả n Các phép toán c b n:ơ ả 1. Phép ch n ọ σ 2. Phép chi u ế pi 3. Phép h p ợ ∪ 4. Phép giao ∩ 5. Phép tích Descart x 6. Phép tr - hay \ ừ 7. Phép chia : hay / 8. Phép θ-k t n i ế ố 9. Phép k t n i t nhiên *ế ố ự 10.Phép k t n i m r ngế ố ở ộ Các phép toán này có: n u vào: 1 ho c nhi u Đầ ặ ề quan hệ n u ra: m t quan h m i Đầ ộ ệ ớ g i là quan h k t qu .ọ ệ ế ả A θ B 3. 3 Bi u th c quan hể ứ ệ n Đ nh nghĩa: là m t bi u th c g m các quan h ị ộ ể ứ ồ ệ trong 1 CSDL và các phép toán quan h .ệ n Ví d :ụ piMAÎHAÌNG, TÃNHG (σ ÂVT=”caïi” (HAÌNG)) n Đ u tiên c a các phép toán trong 1 bi u ộ ư ủ ể th c quan h :ứ ệ FPhép toán m t ngôiộ FTùy theo HQTCSDL c th , có th có nh ng qui ụ ể ể ữ đ nh riêngị 3. 4 Ví d - CSDL Đào T oụ ạ n Trong ch ng này, các ví d s d ng các quan h ươ ụ ử ụ ệ sau: F SV(MASV, HOTEN_SV, NAMS_SV, DCHI_SV, TENLOP) F MON(MAMH, TENMON, SO_TC, LOAI_MON) F GV( MAGV, HOTEN_GV, NAMS_GV, HOCVI) F HOC(MASV, MAMH, STT_HK, NKHOA, LANTHI, K_QUA) F DAY(MAGV, MAMH, STT_HK, NKHOA) n Xác đ nh khóa chính, khóa ngo i cho t ng quan hị ạ ừ ệ n V s đ cho th y s thông th ng gi a các quan hẽ ơ ồ ấ ự ươ ữ ệ 3. 5 Phép ch nọ (Select Operation) n M c đíchụ : Xây d ng m t t p con g m các b c a quan h đã ự ộ ậ ồ ộ ủ ệ cho, th a bi u th c logic cho tr c.ỏ ể ứ ướ n Đ nh nghĩaị : Cho quan h R trên t p thu c tính U, ký hi u R(U).ệ ậ ộ ệ Cho bi u th c logic E phát bi u trên U g m có:ể ứ ể ồ F Các thu c tính ho c các h ngộ ặ ằ F Các phép toán so sánh s h c: ố ọ , ≥ , =, ≠ F Các phép toán logic: ∧, ∨, ¬ Phép ch n quan h R theo đi u ki n E, ký hi u R(E) hay ọ ệ ề ệ ệ σE(R) P = R(E)=σE(R) = {t | t ∈ R and t(E)} Trong đó: t(E): nghĩa là b t th a bi u th c đi u ki n Eộ ỏ ể ứ ề ệ n Ví d : Li t kê danh sách sinh viên l p DI0056A1ụ ệ ớ σTenlop = “DI0056A1” (SV) L c b ng ọ ả theo chi u ề ngang 3. 6 Phép ch n – Ví Dọ ụ MAMH TENMON SO_TC TH409 C S D Li uơ ở ữ ệ 3 TH364 Trí Tu Nhân T oệ ạ 5 TH490 C u Trúc D Li u & GTấ ữ ệ 3 TH324 Gi i Thu tả ậ 4 σSo_TC = 3 (MON) MON MAMH TENMON SO_TC TH409 C S D Li uơ ở ữ ệ 3 TH490 C u Trúc D Li u & GTấ ữ ệ 3 B ng K t ả ế qu :ả Tìm thông tin chi ti t c a các sinh viên thu c l p ế ủ ộ ớ DI0056A1 và sinh vào n m 1980ă Tìm thông tin v k t qu h c môn TH409 và TH490 ề ế ả ọ c a sinh viên.ủ 3. 7 Phép chi uế (Project Operation) n M c đíchụ : Cho k t qu là m t quan h g m các b ế ả ộ ệ ồ ộ c a quan h đã cho trong đó lo i b đi m t s thu c ủ ệ ạ ỏ ộ ố ộ tính không đ c li t kê.ượ ệ n Đ nh nghĩaị : Cho quan h R(U)=(Aệ 1, A2, …, An), Ai ∈U và t p thu c tính X ậ ộ ⊂ U Phép chi u quan h R trên X là t p h p: ế ệ ậ ợ P =R[X] = ∏X (R) = {t[X] | t ∈ R} n Vì quan h là t p h p => Nh ng dòng trùng nhau b ệ ậ ợ ữ ị xóa kh i quan h k t quỏ ệ ế ả n Ví dụ: Li t kê mã s sv, h tên và tên l p.ệ ố ọ ớ ∏ mssv, hoten_sv, tenlop (SV) L c b ng ọ ả theo chi u ề d cọ 3. 8 Phép chi u – Ví dế ụ MAMH TENMON SO_TC TH409 C S D Li uơ ở ữ ệ 3 TH490 C u Trúc D Li u & GTấ ữ ệ 3 TH364 Trí Tu Nhân T oệ ạ 5 TH324 Gi i Thu tả ậ 4 ∏ MAMH, So_TC (MON) MON B ng K t qu :ả ế ả MAMH SO_TC TH409 3 TH490 3 TH364 5 TH324 4 Li t kê danh sách g m mã s sinh viên và i m thi l n ệ ồ ố để ầ 1 c a môn TH409 trong h c k v a r i.ủ ọ ỳ ừ ồ Cho bi t i m c a t ng môn h c ã tích l y c c a ế để ủ ừ ọ đ ũ đượ ủ sinh viên. 3. 9 Phép h pợ (Union Operation) n Hai quan h t ng thích: ệ ươ n u chúng có cùng t p ế ậ thu c tính, hay l c đ quan hộ ượ ồ ệ n Đ nh nghĩaị : H p c a 2 quan h t ng thích R(U) và ợ ủ ệ ươ S(U) là m t quan h P g m các b thu c ít nh t m t ộ ệ ồ ộ ộ ấ ộ trong hai quan h đã cho.ệ P = R ∪ S = R + S = {t | t ∈ R ho cặ t ∈ S} n Ví d : ụ Li t kê danh sách g m h tên c a sinh viên và ệ ồ ọ ủ h tên c a giáo viên.ọ ủ pihoten_sv (SV) ∪ pihoten_gv (GV) R ∪ S R S 3. 10 Phép trừ (Set Difference Operation) n Đ nh nghĩaị : hi u c a 2 quan h t ng thích R(U) và ệ ủ ệ ươ S(U) là m t quan h P g m các b có trong R nh ng ộ ệ ồ ộ ư không có trong S. P = R \ S = R – S = {t | t ∈ R và t ∉ S} n Ví d : ụ Tìm mã các môn h c có d y h c kỳ 2 năm ọ ạ ở ọ h c 04-05 nh ng không có d y h c kỳ 2 năm h cọ ư ạ ở ọ ọ 05-06. pimamh σSTT_KH = 2 ∧ NKHOA = ’04-05’(DAY) – pimamh σSTT_KH = 2 ∧ NKHOA = ’05-06’(DAY) RR \ S S 3. 11 Phép giao (Set-Intersection Operation) n Đ nh nghĩaị : Giao c a 2 quan h t ng thích R(U) và ủ ệ ươ S(U) là m t quan h P g m các b thu c c hai quan h ộ ệ ồ ộ ộ ả ệ đã cho. R ∩ S ={ t | t ∈ R và t ∈ S } n Có th bi u di n phép giao qua phép tr :ể ễ ễ ừ R ∩ S = R - (R - S) n Ví d : ụ Tìm mã s c a các giáo viên có d y môn có mã ố ủ ạ s TH409 và môn có mã s TH490.ố ố pimagv σMAMH = ‘TH409’ (DAY) ∩ pimagv σMAMH = ‘TH490’(DAY) R R ∩ S S 3. 12 Ví d phép H p, Giao, Trụ ợ ừ MAMH STT_HK TH409 2 TH490 1 TH334 1 TH333 2 MAMH STT_HK TH409 2 TH490 1 TH336 2 A: Nh ng môn d y NK 04-05ữ ạ ở B: Nh ng môn d y NK 05-06ữ ạ ở A ∪ B MAMH STT_HK TH409 2 TH490 1 TH334 1 TH333 2 TH336 2 MAMH STT_HK TH409 2 TH490 1 A ∩ B MAMH STT_HK TH334 1 TH333 2 A \ B ? A ∪ B ? A ∩ B ? A \ B 3. 13 Phép chia (Division Operation) n Đ nh nghĩaị : Cho 2 quan h R(U) có n ngôi và S(V) có m ệ ngôi, V ⊂ U và S ≠ φ. Đ t X = U – V.ặ Phép chia quan h R cho S cho k t qu là m t quan h ệ ế ả ộ ệ g m các b t có (n-m) thu c tính, sao cho v i m i b v ồ ộ ộ ớ ọ ộ trong S, thì là m t b thu c Rộ ộ ộ R : S = R/S = { t | t ∈ R(U-V) ∧ (∀ v ∈ S) ( ∈ R ) } n Ví dụ: Tìm mã s c a các sinh viên có h c t t c các ố ủ ọ ấ ả môn. pimasv, mamh(HOC) / pimamh(MON) R S R / S 3. 14 n Ví d :ụ R: Giáo viên d y môn:ạ S: Các môn h c ọ quan tâm Phép chia - ví dụ (Division Operation) R / S: Các giáo viên có d y t t c các môn ạ ấ ả quan tâm MAGV MAMH 1231 TH409 1231 TH364 1232 TH334 1232 TH409 1231 TH334 1244 TH490 1232 TH124 MAMH TH409 TH334 TH364 MAGV 1231 3. 15 Tích Đ -các ề (Cartesian-Product Operation) n Đ nh nghĩaị : Cho 2 quan h R(U) n ngôi, có a ệ b và S(V) m ngôi, có b b , và U ộ ộ ∩ V = ∅ Tích Descart c a R và S là t p g m (a.b) b , ủ ậ ồ ộ m i b có (n+m) thu c tính.ỗ ộ ộ R x S = { | u ∈ R ∧ v ∈ S } n N u U ế ∩ V ≠ ∅, v y thì ph i đ i tên các thu c ậ ả ổ ộ tính trùng nhau. 3. 16 R x S: DS sinh viên lên để i mđểR: DS L pớ S: DS Môn h c trong h c k nàyọ ọ ỳ Tích -các – ví d Đề ụ (Cartesian-Product Operation) n Ví dụ: MASV 1033010 1033011 1033012 MAMH TH409 TH490 TH324 TH334 MASV MAMH 1033010 TH409 1033011 TH409 1033012 TH409 1033010 TH490 1033011 TH490 1033012 TH490 1033010 TH324 1033011 TH324 1033012 TH324 1033010 TH334 1033011 TH334 1033012 TH334 3. 17 Phép k t n i θế ố (Inner join, join) n Đ nh nghĩa: ị Cho 2 quan h R(U) và S(V)ệ θ là m t trong các phép toán s h c: ộ ố ọ , ≥ , =, ≠ Phép k t n i gi a quan h R đ i v i thu c tính A ế ố ữ ệ ố ớ ộ ∈U và quan h S đ i v i thu c tính B ệ ố ớ ộ ∈V, đ c ký hi u R S ượ ệ R S= {| u∈U ∧ v ∈V ∧u[A] θ v[B] } n Phép k t n i ch th c hi n đ c khi θ th c hi n đ c ế ố ỉ ự ệ ượ ự ệ ượ gi a A và B.ữ n N u không d a trên phép so sánh θ thì R S là phép ế ự tích Descartes, n u θ là phép so sánh “=“ thì g i là phép ế ọ k t n i b ng.ế ố ằ A θ B A θ B A θ B 3. 18 Phép k t n i θ – ế ố Ví dụ Ví d : Tìm thông tin v sinh viên l n tu i h n ụ ề ớ ổ ơ m t giáo viên nào đó.ộ MASV HOTEN_SV NAMS_S V 1033010 Nguy n Minh ễ Thi nệ 1989 1033014 Tr n Minh Sangầ 1988 1032967 Lê Công Vũ 1987 MAGV HOTEN_GV NAMS_GV 1250 Lê Phú Thọ 1980 1255 Nguy n Khuy nễ ế 1988 1256 Đào Anh Vũ 1989 MASV HOTEN_SV NAMS_SV MAGV HOTEN_GV NAMS_GV 1033014 Tr n Minh Sangầ 1988 1256 Đào Anh Vũ 1989 1032967 Lê Công Vũ 1987 1255 Nguy n ễ Khuy nế 1988 1032967 Lê Công Vũ 1987 1256 Đào Anh Vũ 1989 SV GV SV.NAMS_SV < GV.NAMS_GV SV GV 3. 19 Phép k t n i t nhiênế ố ự (Natural-Join Operation) n N u k t n i θ d a trên phép so sánh “=“ t i ế ế ố ự ạ các thu c ộ tính cùng tên c a 2 quan h R và S và m t trong hai ủ ệ ộ thu c tính đó b lo i b qua phép chi u thì g i là phép ộ ị ạ ỏ ế ọ k t n i t nhiên, ký hi u *.ế ố ự ệ n Ví dụ: Tìm tên các môn h c có d y trong h c kỳ 2 05-ọ ạ ọ 06. MAMH TH409 TH364 TH324 A: pimamh σSTT_KH = 2 ∧ NKHOA = ’05-06’(DAY) MAMH TENMON TH409 C S D Li uơ ở ữ ệ TH490 C u Trúc D Li u & ấ ữ ệ GT TH364 Trí Tu Nhân T oệ ạ TH324 Gi i Thu tả ậ MAMH TENMON TH409 C S D Li uơ ở ữ ệ TH364 Trí Tu Nhân T oệ ạ TH324 Gi i Thu tả ậ B: pimamh, TenMon (MON) A * B Nh ng dòng không có ữ ở c 2 b ng s không có ả ả ẽ m t b ng KQặ ở ả 3. 20 Phép k t n i m r ngế ố ở ộ (Outer join) n Đ nhị nghĩa: Phép toán này cho phép làm vi cệ v iớ thông tin bị thi uế , t cứ là v nẫ th cự hi nệ phép k tế n iố tự nhiên trên các trị tr ngố c aủ thu cộ tính dùng để k tế n iố . n Có 3 lo iạ k tế n iố mở r ngộ : trái, ph iả và hai bên n Cho 2 quan h R và S:ệ F Trái: R S = P ∪ ( R * S ) 4 P={| u ∈ R, u không t ng ng v i b nào c a S, v ươ ứ ớ ộ ủ ∈S, các giá tr c a các thu c tính trong v đ u là null }ị ủ ộ ề F Ph iả : R S = Q ∪ ( R * S ) 4 Q={| v ∈ s, v không t ng ng v i b nào c a R, u ươ ứ ớ ộ ủ ∈ R, các giá tr c a các thu c tính trong u đ u là null }ị ủ ộ ề F Hai bên: R S = P ∪ Q ∪ ( R * S ) 4 P và Q đ c đ nh nghĩa nh trên.ượ ị ư 3. 21 Phép k t n i m r ng – ví dế ố ở ộ ụ (Outer join) MAGV MAMH 1231 TH409 1232 TH409 1232 TH334 1255 TH490 1957 TH333 MAGV HOTEN_GV 1250 Lê Phú Thọ 1255 Nguy n Khuy nễ ế 1256 Đào Anh Vũ 1231 Tr n Ngân Bìnhầ 1232 Phan Ph ng Lanươ MAGV HOTEN_GV MAGV MAMH 1250 Lê Phú Thọ NULL NULL 1255 Nguy n Khuy nễ ế 1255 TH490 1256 Đào Anh Vũ NULL NULL 1231 Tr n Ngân Bìnhầ 1231 TH409 1232 Phan Ph ng Lanươ 1232 TH409 1232 Phan Ph ng Lanươ 1232 TH334 MAGV MAMH MAGV HOTEN_GV 1231 TH409 1231 Tr n Ngân Bìnhầ 1232 TH409 1232 Phan Ph ng Lanươ 1232 TH334 1232 Phan Ph ng Lanươ 1255 TH490 1255 Nguy n Khuy nễ ế 1957 TH333 NULL NULL R: DS GV c a Khoaủ S: Phân công d y trong HK nàyạ R S R S R S ? 3. 22 Phép đ i tênổ (Rename Operation) n Cho phép chúng ta đ t tên, và nh đó ta có th tham ặ ờ ể chi u đ n k t qu c a các bi u th c đ i s quan h .ế ế ế ả ủ ể ứ ạ ố ệ n Cho phép chúng ta tham chi u đ n m t quan h ế ế ộ ệ nhi u l n, dùng trong các phép k t n i.ề ầ ế ố n Ví d : ụ ρ x (E) S tr v k t qu c a bi u th c E v i tên Xẽ ả ề ế ả ủ ể ứ ớ n N u k t qu c a bi u th c quan h E có n ngôi, thì:ế ế ả ủ ể ứ ệ ρx (A1, A2, …, An) (E) S tr v k t qu c a E v i tên ẽ ả ề ế ả ủ ớ X, và v i các thu c ớ ộ tính đ c đ t tên là ượ ặ A1, A2, …., An. 3. 23 Phép gán (Assignment Operation) n Phép gán (←) cung c p m t ph ng ti n thu n l i ấ ộ ươ ệ ậ ợ đ bi u di n các truy v n ph c t p.ể ễ ễ ấ ứ ạ n Example: Có th vi t R(U) ể ế ÷ S(V) nh sau ư temp1 ← ∏U-V (R) temp2 ← ∏U-V ((temp1 x S) – ∏U-V,V (R)) result = temp1 – temp2 FK t qu c a bi u th c bên ph i d u ế ả ủ ể ứ ả ấ ← s đ c gán ẽ ượ cho bi n bi u th c bên trái d u ế ể ứ ấ ←. FCó th s d ng bi n các bi u th c theo sau.ể ử ụ ế ở ể ứ 3. 24 Các hàm k t t pế ậ (Aggregate Functions) Các hàm k t t pế ậ nh n vào m t t p các ậ ộ ậ giá tr và tr v k t qu là m t giá ị ả ề ế ả ộ tr .ị 1. avg: giá tr trung bìnhị 2.min: giá tr minị 3.max: giá tr maxị 4. sum: t ngổ 5. count: đ m nh ng giá trế ữ ị 3. 25 Các hàm k t t p – Ví d ế ậ ụ (Aggregate Functions) sum SO_TC (MON) max SO_TC (MON) n Trong tr ngườ h pợ ta mu nố lo iạ bỏ các giá trị trùng nhau, thì ph iả thêm từ khoá distinct vào sau tên hàm và d uấ g chạ ngang (-) Ví dụ : Count-distinct SO_TC (MON) = 3 MAMH TENMON SO_TC TH409 C S D Li uơ ở ữ ệ 3 TH490 C u Trúc D Li u & GTấ ữ ệ 3 TH364 Trí Tu Nhân T oệ ạ 5 TH324 Gi i Thu tả ậ 4 MON Sum-SO_TC 15 Max-SO_TC 5 count SO_TC (MON) Count-SO_TC 4 min SO_TC (MON) Min-SO_TC 3 avg SO_TC (MON) Avg-SO_TC 3.75 3. 26 n Ta có th áp d ng hàm k t t p trên nhi u ể ụ ế ậ ề nhóm khác nhau, m i nhóm bao g m m t t p ỗ ồ ộ ậ các b . Hàm k t t p trên nhóm có d ng: ộ ế ậ ạ G1, G2, …, Gn g F1 A1, F2 A2,…, Fm Am (E) n Trong đó: FE là bi u th c quan h b t kỳ ể ứ ệ ấ FG1, G2, …, Gn là các thu c tính mà vi c chia ộ ệ nhóm d a trên các giá tr c a chúng.ự ị ủ FM i Fỗ i là m t hàm k t t p.ộ ế ậ FM i Aỗ i là m t thu c tínhộ ộ Các hàm k t t p ế ậ (cont.) (Aggregate Functions) 3. 27 Các hàm k t t p ế ậ (cont.) (Aggregate Functions) MASV MAMH K_QUA 1033010 TH409 8 1033010 TH490 5 1033010 TH324 7 1033011 TH409 9 1033011 TH324 8 1033011 TH490 7 1033012 TH490 4 1033012 TH409 6 1033012 TH324 6 MASV Min-KQ Avg_KQ 1033010 5 6.67 1033011 7 8 1033012 4 5.34 Bi u th c:ể ứ MASV g min K_QUA, avg K_QUA (HOC) s cho k t qu nh sau:ẽ ế ả ư HOC 3. 28 Tính ch t đ i s quan hấ ạ ố ệ Tính Ch tấ Phép Toán Công Th cứ Giao Hoán H p, Giao, K t N iợ ế ố R * S = S * R R + S = S+ R R . S = S . R K t H pế ợ H p, Giao, K t N iợ ế ố (R * S) * P = R * (P * S) (R + S) + P = R + (P + S) (R . S) . P = R . (P . S) Lũy Đ ng b c IIẳ ậ Ch n, Chi u (phép ọ ế toán m t ngôi)ộ R(E) (E) = R(E) R[X] [X] = R[X] Lũy Đ ng b c Iẳ ậ H p, Giao, K t N iợ ế ố R + R = R R . R = R R * R = R Thác các phép ch nọ N u Eế 1 => E2 Thì R(E1)(E2) = R(E2)(E1) = R(E1) 3. 29 Tính ch t đ i s quan h (Cont.)ấ ạ ố ệ Tính Ch tấ Công Th cứ Thác các phép chi uế N u X ế ⊆ Y ⊆ U Thì R[Y][X] = R[X] Phép Ch n Theo H i, ọ ộ Tuy nể a) R(E1 ∧ E2) = R(E1) . R (E2) b) R(E1 ∨ E2) = R(E1) + R (E2) c) N u Eế 1 => E2 Thì R(E1 ∨ E2) = R(E2) d) R(T) = R v i T là bi u th c h ng đúngớ ể ứ ằ e) R(F) = φ v i F là bi u th c h ng saiớ ể ứ ằ Thác phép Ch n-K t n iọ ế ố (R*S) (ER ∧ ES) = R(ER) * S(ES) Thác phép Chi u-Ch nế ọ E là bi u th c đi u ki n trên U, Eể ứ ề ệ X trên X ⊆ U: R(E ∧ EX) [X] = R (E) (EX)[X] = R(E) [X] (EX) Phép Giao qua phép trừ R . S = R − ( R − S ) Phép chia qua các phép toán khác R ÷ S = R[X] − (R[X] * S − R) [X] 3. 30 T i u Hóa Bi u Th c Quan Hố Ư ể ứ ệ n M c đích:ụ Chuy n bi u th c quan h v d ng ể ể ứ ệ ề ạ t ng đ ng nh ng có chi phí th c hi n th p h n ươ ươ ư ự ệ ấ ơ (th i gian, không gian l u tr )ờ ư ữ n Nguyên t c:ắ Tìm cách chuy n các phép toán đ ể ể th c hi n s m nh t đ n m c có th các phép toán có ự ệ ớ ấ ế ứ ể tính ch t làm h p quan h (phép ch n, chi u).ấ ẹ ệ ọ ế n Đ th c hi n đ c đi u này, ta dùng ể ự ệ ượ ề cây th c hi n ự ệ đ minh h a cho quá trình th c hi n m t bi u th c.ể ọ ự ệ ộ ể ứ n Ví d : ụ Có bi u th c quan h :ể ứ ệ (SINHVIEN*SV_DT*DETAI) (MADT>3 ∧ MASV > MADT ∧ KETQUA>HOCLUC)[TENDT, KETQUA] 3. 31 T i u Cây Th c Hi n BTQHố Ư ự ệ [TENDT, KETQUA] (MADT > 3 ∧ KQ > HL ∧ MASV > MADT) * * SV SV_DT DETAI [TENDT, KETQUA] (MADT > 3) * * SV SV_DT DETAI (KQ>HL) [MADT,TENDT,KQ] [MASV,HL] (MASV> MADT) [MASV, MADT,KQ]