Bài giảng Cơ sở dữ liệu - Chương 8.2: Phụ thuộc hàm - Các khái niệm, qui tắc suy diễn và thuật toán

Chia sẻ: Cố Dạ Bạch | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

10
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cơ sở dữ liệu - Chương 8.2: Phụ thuộc hàm - Các khái niệm, qui tắc suy diễn và thuật toán. Chương này cung cấp cho sinh viên những nội dung gồm: định nghĩa phụ thuộc hàm; phụ thuộc hàm suy diễn được; các qui tắc suy diễn đối với các phụ thuộc hàm; bao đóng của tập thuộc tính; tìm bao đóng của tập thuộc tính;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu - Chương 8.2: Phụ thuộc hàm - Các khái niệm, qui tắc suy diễn và thuật toán

BÀI GI NG CƠ S D LI U 8. Ph thu c hàm: các khái ni m, qui t c suy di n và thu t toán Nguy n H i Châu Khoa Công ngh Thông tin Trư ng Đ i h c Công ngh , ĐHQGHN N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 1 / 25
Đ nh nghĩa ph thu c hàm Gi s X và Y là hai t p thu c tính c a lư c đ quan h R M t ph thu c hàm t X vào Y là m t ràng bu c trên các b c a m i tr ng thái h p l r (R) sao cho v i hai b b t kỳ t1 , t2 ∈ r (R), n u t1 [X ] = t2 [X ] thì t1 [Y ] = t2 [Y ] Ph thu c hàm t X vào Y đư c ký hi u là X → Y v i X là v trái và Y là v ph i c a ph thu c hàm Các cách di n đ t khác: Y ph thu c hàm vào X ho c X xác đ nh hàm Y M t ph thu c hàm là m t tính ch t c a lư c đ quan h R và không ph i là tính ch t c a tr ng thái quan h r (R) M t ph thu c hàm không th đư c phát hi n m t cách t đ ng t các tr ng thái r (R) mà ph i xác đ nh t ng nghĩa c a lư c đ quan h R N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 2 / 25
Ví d ph thu c hàm 1 Lư c đ quan h MUONSACH(Sothe, MaSach, Nguoimuon, Tensach, Ngaymuon) có các ph thu c hàm: Sothe → Nguoimuon Masach → Tensach Sothe, Masach → Ngaymuon N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 3 / 25
Ví d ph thu c hàm 2 Lư c đ quan h CONGDAN(SoCMND, Hoten, Ngaysinh, Gioitinh) có các ph thu c hàm: SoCMND → Hoten SoCMND → Ngaysinh SoCMND → Gioitinh N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 4 / 25
Ph thu c hàm suy di n đư c Gi s F là m t t p ph thu c hàm trên lư c đ quan h R M t ph thu c hàm X → Y đư c g i là suy di n đư c t F n u X → Y đúng trong m i tr ng thái h p l r (R). Đi u này có nghĩa là khi r (R) th a mãn các ph thu c hàm trong F, r (R) cũng th a mãn X →Y X → Y suy di n đư c t F đư c ký hi u là F |= X → Y Bao đóng c a t p ph thu c hàm F, ký hi u là F + , đư c đ nh nghĩa như sau: F + = F ∪ {X → Y , F |= X → Y } (1) N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 5 / 25
Các qui t c suy di n đ i v i các ph thu c hàm Armstrong1 đưa ra 6 qui t c suy di n đ i v i ph thu c hàm (1974): QT1. (ph n x ): N u X ⊇ Y thì X → Y QT2. (tăng): {X → Y } |= XZ → YZ 2 QT3. (b c c u): {X → Y , Y → Z } |= X → Z QT4. (chi u): {X → YZ } |= X → Y và X → Z QT5. (h p): {X → Y , X → Z } |= X → YZ QT6. (t a b c c u): {X → Y , WY → Z } |= WX → Z 1 William Ward Armstrong là nhà toán h c và khoa h c máy tính ngư i Canada. Ông nh n b ng ti n sĩ năm 1966 t i trư ng Đ i h c British Columbia (University of British Columbia). 2 Đ cho ti n, {X , Y } đư c vi t t t là XY N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 6 / 25
Ch ng minh QT1, QT2 QT1: N u X ⊇ Y thì X → Y Gi s X ⊇ Y và t1 , t2 là hai b b t kỳ trong r (R) th a mãn t1 [X ] = t2 [X ]. Khi đó, do X ⊇ Y nên t1 [Y ] = t2 [Y ]. V y X → Y . QT2: {X → Y } |= XZ → YZ Gi s X → Y nhưng XZ → YZ . Khi đó theo đ nh nghĩa ph thu c hàm, t n t i hai b t1 , t2 ∈ r (R) sao cho: t1 [X ] = t2 [X ], (2) t1 [Y ] = t2 [Y ], (3) t1 [XZ ] = t2 [XZ ] (4) nhưng t1 [YZ ] = t2 [YZ ] (5) T (2) và (4) ta có: t1 [Z ] = t2 [Z ] (6) T (3) và (6) suy ra t1 [YZ ] = t2 [YZ ] =⇒ mâu thu n v i (5). N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 7 / 25
Ch ng minh QT3 QT3: {X → Y , Y → Z } |= X → Z Gi s ta có X →Y (7) và Y →Z (8) Khi đó, v i hai b t1 , t2 ∈ r (R) b t kỳ sao cho t1 [X ] = t2 [X ], t (7) chúng ta suy ra: t1 [Y ] = t2 [Y ] (9) T (8) và (9) ta có: t1 [Z ] = t2 [Z ] (10) T t1 [X ] = t2 [X ] và (10) chúng ta có X → Z N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 8 / 25
Ch ng minh QT4 QT4: {X → YZ } |= X → Y và X → Z Ta có X → YZ (11) Do YZ ⊇ Y nên theo QT1: YZ → Y (12) Áp d ng QT3 cho (11) và (12): X → Y . Tương t , ta có: X → Z . N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 9 / 25
Ch ng minh QT5 QT5: {X → Y , X → Z } |= X → YZ Gi s ta có X →Y (13) và X →Z (14) Áp d ng QT2 cho (13): XX → YX (15) Áp d ng QT2 cho (14): YX → YZ (16) Áp d ng QT3 cho (15), (16) và do XX = X : X → YZ . N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 10 / 25
Ch ng minh QT6 QT6: {X → Y , WY → Z } |= WX → Z Gi s ta có: X →Y (17) và WY → Z (18) Áp d ng QT2 cho (17): WX → WY (19) Áp d ng QT3 cho (19): WX → Z . N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 11 / 25
Các qui t c suy di n đ i v i ph thu c hàm Amstrong đã ch ng minh r ng các quy t c suy di n QT1, QT2 và QT3 là đúng và đ y đ : Đúng: cho trư c m t t p ph thu c hàm F trên m t lư c đ quan h R, b t kỳ m t ph thu c hàm nào suy di n đư c b ng cách áp d ng các quy t c t t QT1 đ n QT3 cũng đúng trong m i tr ng thái quan h r (R) tho mãn các ph thu c hàm trong F Đ y đ : vi c s d ng các quy t c t QT1 đ n QT3 l p l i nhi u l n đ suy di n các ph thu c hàm cho đ n khi không còn suy di n đư c n a s cho k t qu là m t t p h p đ y đ các ph thu c hàm có th đư c suy di n t F Các qui t c QT1, QT2 và QT3 đư c g i là các qui t c suy di n Armstrong N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 12 / 25
Bao đóng c a t p thu c tính Gi s F là m t t p ph thu c hàm trên lư c đ quan h R và X là m t t p thu c tính c a R Bao đóng c a t p thu c tính X dư i F, ký hi u là X + đư c đ nh nghĩa như sau: X + = {A, A là thu c tính c a R, F |= X → A} (20) Khi c n ch rõ t p ph thu c hàm, chúng ta ký hi u bao đóng c a X + dư i F là XF N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 13 / 25
Tìm bao đóng c a t p thu c tính Thu t toán 1: Tìm bao đóng X + c a X dư i F Vào: Lư c đ quan h R, t p ph thu c hàm F và t p thu c tính X Ra: T p thu c tính X + là bao đóng c a X 1 X+ = X; 2 repeat 3 OldX + = X + ; 4 for m i ph thu c hàm Y → Z trong F do 5 if X + ⊃ Y then 6 X+ = X+ ∪ Z; 7 end 8 end 9 until OldX + = X + ; N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 14 / 25
Ví d bao đóng c a t p thu c tính Lư c đ quan h R(MaNV , Hoten, MaDA, TenDA, Diadiem, Sogio) có t p ph thu c hàm: F = {MaNV → Hoten, MaDA → {TenDA, Diadiem}, {MaNV , MaDA} → Sogio} MaNV + = {MaNV , Hoten}, MaDA+ = {MaDA, TenDA, Diadiem} {MaNV , MaDA}+ = {MaNV , Hoten, MaDA, TenDA, Diadiem, Sogio} N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 15 / 25
Bao đóng c a t p thu c tính và khóa Gi s ta có lư c đ quan h R(A1 , A2 , ..., An ) N u X + = {A1 , A2 , ..., An } thì X xác đ nh hàm các thu c tính còn l i, đi u này tương đương v i X là siêu khóa Có th ki m tra m t t p thu c tính X có là khóa hay không b ng cách: 1 Ki m tra X là siêu khóa hay không: X + = {A1 , A2 , ..., An }? 2 N u có, ki m tra X có là siêu khóa t i thi u hay không: Có t n t i t p thu c tính S X sao cho S + = {A1 , A2 , ..., An }? N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 16 / 25
Ví d bao đóng và khóa Lư c đ quan h R(MaNV , Hoten, MaDA, TenDA, Diadiem, Sogio) {MaNV , MaDA}+ = {MaNV , Hoten, MaDA, TenDA, Diadiem, Sogio}, MaNV + = {MaNV , Hoten}, MaDA+ = {MaDA, TenDA, Diadiem} {MaNV , MaDA} là siêu khóa t i thi u =⇒ {MaNV , MaDA} là khóa N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 17 / 25
Tìm khóa c a lư c đ quan h Thu t toán 2: Tìm m t khóa c a lư c đ quan h Vào: Lư c đ quan h R(A1 , A2 , ..., An ) và t p ph thu c hàm F Ra: M t khóa c a lư c đ quan h R 1 K = {A1 , A2 , ..., An }; 2 for m i thu c tính A c a K do 3 Xác đ nh (K − A)+ ; F // Th c hi n thu t toán 1 4 if (K − A)+ = {A1 , A2 , ..., An } then F 5 K = K − {A} 6 end 7 end Th i gian th c hi n bư c 3 ph thu c s lư ng ph thu c hàm trong F (xem vòng for bư c 4–8, thu t toán 1) =⇒ có th lo i b các ph thu c hàm "dư th a" trong F? N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 18 / 25
S tương đương c a các t p ph thu c hàm M t t p ph thu c hàm E đư c ph b i m t t p ph thu c hàm F hay F ph E n u E ⊂ F + . Đi u này có nghĩa là: ∀X → Y ∈ E, F |= X → Y Hai t p ph thu c hàm E và F đư c g i là tương đương n u E+ = F+ Đ ki m tra F ph E (E ⊂ F + ), v i m i X → Y là ph thu c hàm trong E: Tính X + dư i F ∀X → Y ∈ E N u X + ⊃ Y đúng v i t t c các ph thu c hàm X → Y trong E thì F ph E N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 19 / 25
Ví d hai t p ph thu c hàm tương đương Lư c đ quan h R(A, C , D, E , H); ký hi u {A, E }+ là bao đóng c a t p thu c tính E {A, E } dư i t p ph thu c hàm E: F = {A → C , AC → D, E → AD, E → H} E = {A → CD, E → AH} {A}+ = {A, C , D} ⊃ {C } E {A}+ = {A, C , D} ⊃ {C , D} F {A, C }+ = {A, C , D} ⊃ {D} E {E }+ = {E , A, H, C , D} ⊃ F {A, H} {E }+ = {E , A, H, C , D}: E {E }+ ⊃ {A, D} và {E }+ ⊃ {H} E E =⇒ E tương đương v i F N. H. Châu (VNU-UET) Cơ s d li u: Ph thu c hàm https://bit.ly/3dIZGAm 20 / 25