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 - 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!
Nội dung trích xuất từ tài liệu:
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 U8. 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 , ĐHQGHNN. 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 / 25Ví d ph thu c hàm 1Lư c đ quan hMUONSACH(Sothe, MaSach, Nguoimuon, Tensach, Ngaymuon) có cácph 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 / 25Ví d ph thu c hàm 2Lư c đ quan h CONGDAN(SoCMND, Hoten, Ngaysinh, Gioitinh) có cácph 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 / 25Ph 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 / 25Các qui t c suy di n đ i v i các ph thu c hàmArmstrong1 đư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 ngti 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 / 25Ch 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 / 25Ch ng minh QT3QT3: {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 / 25Ch ng minh QT4QT4: {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 / 25Ch ng minh QT5QT5: {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 / 25Ch ng minh QT6QT6: {X → Y , WY → Z } |= WX → Z Gi s ta có: X →Y (17) và ...