Bài giảng Lý thuyết cơ sở dữ liệu - Chương 4: Phụ thuộc hàm - Trịnh Thị Xuân

CHƯƠNG IV: PHỤ THUỘC HÀM I. Giới thiệu ¡ Functional Dependency ¡Phụ thuộc hàm là khái niệm được xây dựng để mô tả các ràng buộc logic trong CSDL - là công cụ để biểu diễn các ràng buộc logic giữa các thuộc tính của quan hệ 8/9/21 8:06 AM 2 8/9/21 8:06 AM 3 *Định nghĩa PTH ¡Cho quan hệ R(U), trong đó U = {A1, A2,An} là tập thuộc tính. Cho X,Y là tập thuộc tính con thuộc U ¡Nói rằng X xác định hàm Y hay Y phụ thuộc hàm vào X, ký hiệu X®Y, nếu với mọi quan hệ (bộ) r xác định trên R(U) và với hai bộ t1 và t2 bất kỳ mà t1[X] = t2[X] thì t1[Y] = t2[Y] ¡Cách đọc khác: X xác định duy nhất Y (hay X kéo theo Y) -X gọi là vế trái của PTH, Y là vế phải acủa PTH ¡Ký hiệu: F:= { f : Lj → Rj | Lj, Rj ⊆ Ω } là tập các phụ thuộc hàm trên các thuộc tính Ω ¡ Ví dụ: HOADON (soHD, NgayLap, TongGiaTri) CHITIET_HOADON (SoHD, MaHang, SoLuong, DonGia, ThanhTien) - SoHD® NgayLap - SoHD® TongGiaTri - SoHD, MaHang® SoLuong - SoHD, MaHang® DonGia - SoHD, MaHang® ThanhTien 8/9/21 8:06 AM 4 8/9/21 8:06 AM 9 ¡ Biểu diễn phụ thuộc hàm: - Liệt kê các thuộc tính, dùng đường nối mũi tên từ các thuộc tính vế trái đến các thuộc tính vế phải của tất cả các phụ thuộc hàm ¡ Ví dụ: MƯỢN( Sốthẻ, Mãsốsách, Tênngườimượn, Tênsách, Ngàymượn ) - Với các phụ thuộc hàm: FD1: Sốthẻ ® Tênngườimượn FD2: Mãsốsách ® Tênsách FD3: Sốthẻ, Mãsốsách ® Ngàymượn ¡ Có sơ đồ phụ thuộc hàm như sau: Sốthẻ Mã số sách Tên người mượn Tên sách Ngàymượn FD3 FD1 FD2 8/9/21 8:06 AM 13 II. Hệ tiên đề Amstrong ¡Năm 1974, Amstrong đưa ra hệ luật dẫn hay các tính chất của phụ thuộc hàm, gọi là hệ tiên đề Amstrong ¡Hệ tiên đề Amstrong gồm các nguyên tắc biến đổi của PTH 8/9/21 8:06 AM 14 * Hệ tiên đề Amstrong: ¡ Cho X, Y, Z, W Í U. Ký hiệu: XY = XÈY. Ta có các luật sau : 1. Luật phản xạ: Nếu Y Í X thì X® Y VD: MaNV, HoTen, NgaySinh® HoTen, NgaySinh 2. Luật bổ sung - gia tăng: Nếu X®Y thì XZ®YZ VD: Nếu MaNV® HoTen thì MaNV, NgaySinh® HoTen, NgaySinh 3. Luật bắc cầu: Nếu X®Y và Y®Z thì X® Z VD: Nếu có MaNV, Hoten® MaP và MaP® TenPhong,DiaChi thì MaNV, Hoten® TenPhong, DiaChi 4. Luật tựa bắc cầu: Nếu X®Y và WY®Z thì XW®Z VD: MaNV® HoTen và HoTen, NgaySinh® HSL thì MaNV, NgaySinh® HSL 5. Luật hợp: Nếu X®Y và X®Z thì X®YZ VD: MaSV® HoTen, MaSV® NgaySinh thì MaSV® HoTen, NgaySinh 6. Luật tách: Nếu X®Y và Z Í Y thì X®Z VD: MaSV® HoTen, NgaySinh thì MaSV® HoTen, MaSV® NgaySinh 8/9/21 8:06 AM 17 ¡ Ví dụ: Cho R = {ABC} và tập F = { AB®C, C®A }. Áp dụng hệ tiên đề Amstrong CMR: BC®ABC Thực hiện: 1. Từ C® A 2. Có: BC® AB (luật tăng cường thêm B) 3. Từ AB® C 4. Có: AB® ABC (luật tăng cường thêm AB) 5. Có BC® ABC (bắc cầu từ (2) và (4)) Vậy tồn tại BC®ABC 8/9/21 8:06 AM 18 ¡ Ví dụ: Cho R = { A, B, C, E, F } và F= { ABà C, Cà B , ABCà E, Fà A }. Áp dụng hệ tiên đề Amstrong. CMR: FBà E 8/9/21 8:06 AM 20 III. Bao đóng - Closure 1. Các khái niệm cơ bản ¡ Gọi F là tập các pth trên tập thuộc tính U, X Í U ¡ Bao đóng của tập thuộc tính X: là tất cả các thuộc tính A mà phụ thuộc hàm X ® A có thể được suy diễn logic từ F nhờ hệ tiên đề Amstrong. Kí hiệu: X+ X+ = { AÎU | X ® A Î F+ } ó Là tập tất cả các thuộc tính A mà được suy ra từ X ¡ Bao đóng của phụ thuộc hàm: là tập tất cả các PTH được suy diễn logic từ tập pth F - F+ := {X→Y | X,Y ⊆U và X→Y được suy dẫn logic từ F} - Nếu F+ = F thì F là họ đầy đủ của các pth 2. Thuật toán tìm bao đóng của tập thuộc tính ¡Closure of a set attributes ¡Các bước: - Bước 0: Đặt G = F và Gán X0 = X (i=0) - Bước i (i =1): Chọn phụ thuộc hàm A®B Î G Ÿ Nếu A Í Xi-1 * Nếu B Ë Xi-1 khi đó Xi = Xi-1 È B với i = 2, 3, * G = G – { A® B } Ÿ Lặp lại bước i Ÿ Thuật toán dừng kiểm tra nếu G = ᴓ - Bước n: Tập Xi cuối cùng là kết quả Xi = Xi+1 = Xi+2 = X+ 8/9/21 8:06 AM 21 8/9/21 8:06 AM 22 ¡ Ví dụ: U = (ABCDEGH) và tập pth F = {Aà D, ABà DE, CEàG, EàH } - Tính bao đóng X+ với X = (AB) 8/9/21 8:06 AM 23 Ví dụ: ¡Ví dụ: Cho R = { A, B, C, D, E} Và F = {AàC, BàC,CàD,DEàC,CEàA } - Tính bao đóng X+ với X = (AE) 8/9/21 8:06 AM 24 Ví dụ: ¡ Cho Q+ = ABCDEG ¡ F = {AB->C; D->EG; C->A; BE->C; BC->D; CG->BD; ACD->B; CE->AG } Cho X = BD. Tính (BD)+ 8/9/21 8:06 AM 25 Ví dụ: ¡ Cho Q+ = ABCDEG F = {AB->C; D->EG; C->A; BE->C; BC->D; CG->BD; ACD->B; CE->AG } Cho X = AD Tính bao đóng (AD)+ 8/9/21 8:06 AM 26 3. Bài toán thành viên ¡ Dùng để xác định một phụ thuộc hàm bất kỳ nào đó có là thành viên của tập phụ thuộc hàm F đã cho hay không ó phụ thuộc hàm được suy dẫn từ F ¡ Thuật toán kiểm tra X®Y là thành viên của F: - Cách 1: Áp dụng các quy tắc biến đổi của Hệ tiên đề Amstrong - Cách 2: Tính X+. So sánh X+ với Y nếu YÍX+ thì khẳng định X®Y là thành viên của tập phụ thuộc hàm F, ngược lại không phải là thành viên 8/9/21 8:06 AM 27 ¡ Ví dụ: Cho U = (ABCDEI) và F = { AB® E, BE® I, E® C, CI® D } - Chứng minh: AB® CD ¡ Ví dụ: Cho R = { A, B, C, D, E, G, H } và F= { ABà C, Bà D, CDàE, CEà GH, Gà A} - Chứng minh rằng: ABà G 8/9/21 8:06 AM 30 IV. Tập phụ thuộc hàm tương đương ¡ Hai tập pth F và G được gọi là tương đương nếu: - mọi pth của F đều có thể suy được từ G - mọi pth của G đều có thể suy được từ F có nghĩa là F+ = G+ ¡ Khi đó ta nói F phủ G (và G phủ F). ¡ Kí hiệu: F º G 8/9/21 8:06 AM 31 Thuật toán ¡ Kiểm tra mọi PTH của F suy từ G: "X ® YÎF, tính X+ từ G, sau đó kiểm tra xem YÎ X+ ó Tính bao đóng của tất cả vế trái của F dựa trên tập PTH của G và kết luận dựa vào vế phải ¡ Kiểm tra mọi PTH của G suy từ F: "X ® YÎG, tính X+ từ F, sau đó kiểm tra xem YÎ X+ ó Tính bao đóng của tất cả vế trái của G dựa trên tập PTH của F và kết luận dựa vào vế phải 8/9/21 8:06 AM 32 ¡Ví dụ: Xét hai tập phụ thuộc hàm F = { A® C, AC® D, E® AD, E® H } và G = { A® CD, E® AH } CMR: F và G là tương đương với nhau V. Phụ thuộc hàm dư thừa ¡Cho tập PTH F trên tập thuộc tính Ω ¡Phụ thuộc hàm X→Y ∈ F là phụ thuộc dư thừa, khi và chỉ khi X→Y được suy dẫn logic từ G := F – {X →Y} - Phụ thuộc hàm X →Y được gọi là dư thừa nếu nó được suy ra từ các PTH khác của tập F 8/9/21 8:06 AM 34 Thuật toán xác định tập phụ thuộc không dư thừa ¡ Cho Tập thuộc tính U và tập pth F ¡ Kiểm tra pth X→ Y có dư thừa không? ¡Bước 1: Tính G = F – { X → Y } ¡Bước 2: Tìm X+ dựa trên tập pth G ¡Bước 3: Kiểm tra - Nếu Y Î X+ thì khẳng định pth X → Y là dư thừa - Nếu Y Ï X+ thì khẳng định pth X → Y là không dư thừa 8/9/21 8:06 AM 35 Ví dụ: ¡Cho tập phụ thuộc hàm F = { X → YW, XW → Z, Z →Y, XY → Z}. ¡Kiểm tra: XY → Z là phụ thuộc dư thừa của tập F ? 8/9/21 8:06 AM 36 ví dụ ¡Cho lược đồ quan hệ : - U = ABCD; - F = {CDà B, AàC, BàACD} ¡Kiểm tra CDàB có dư thừa hay không? 8/9/21 8:06 AM 37 Yêu cầu trình bày báo cáo ¡ Các nhóm lần lượt báo cáo theo thứ tự (Mang máy tính) => nhóm nào muộn bị trừ điểm tương ứng ¡ Làm slide báo cáo theo mẫu yêu cầu của Khoa ¡ Nội dung báo cáo: - Phát biểu bài toán - Xây dựng mô hình thực thể - Xây dựng mô hình CSDL quan hệ ¡ Hoàn thiện song song trong file Google doc - Trước: 12h – Thứ 2 – 18/2/2019 8/9/21 8:06 AM 38 8/9/21 8:06 AM 40 VI. Khóa của quan hệ 1. Định nghĩa: -Cho R(A1, , An) là lược đồ quan hệ, gồm ŸTập U = { A1, A2, ... , An } ŸTập F= { f1, f2, ... ,fm } -Tập K Í U là siêu khóa nếu K+ = U hay K ® U ŸTập K được gọi là siêu khoá nếu tập K suy ra tất cả các thuộc tính của lược đồ -K Í U là khoá của R nếu thoả mãn hai điều kiện sau: ŸK là siêu khóa ŸKhông tồn tại K' Ì K mà K' ® U ó K là siêu khóa nhỏ nhất -Khoá là tập thuộc tính nhỏ nhất để xác định tất cả các thuộc tính của lược đồ 8/9/21 8:06 AM 44 2. Thuật toán tìm một khóa ¡ Input: - Tập thuộc tính U = {A1, A2, , An} - Tập PTH F ¡ Output: Khóa của quan hệ R ¡ Các bước: - Bước 1: Gán K = U - Bước 2: Loại khỏi K lần lượt từng thuộc tính A mà (K\A)+ = U - Bước 3: Lặp lại bước 2 đến khi không loại khỏi thêm thuộc tính từ K được nữa 8/9/21 8:06 AM 47 Ví dụ: ¡ Cho LĐQH với R = {ABCDEF} và tập PTH F = {AB®C, C®D, AD®E, F®A} ¡ Tìm một khóa của lược đồ quan hệ 8/9/21 8:06 AM 53 3. Thuật toán tìm tất cả các khóa ¡ Tập thuộc tính nguồn (TN) - các thuộc tính chỉ xuất hiện ở vế trái, không xuất hiện ở vế phải của pth và - các thuộc tính không xuất hiện ở vế trái lẫn vế phải của pth. ¡ Tập thuộc tính đích (TĐ) - các thuộc tính chỉ xuất hiện ở vế phải không xuất hiện ở vế trái của pth. ¡ Tập thuộc tính trung gian (TG) - Các thuộc tính ở vế trái lẫn vế phải của pth. * Thuật toán tìm tất cả các khóa ¡ Bước 1: Tính tập TN và tập TG ¡ Bước 2: - Nếu TG = 0(rỗng) thì K = TN => kết thúc tìm khóa - Ngược lại qua bước 3. ¡ Bước 3: Tính TN+ - Nếu TN+ = U, kết luận chỉ có một khóa duy nhất là TN. - Ngược lại qua bước 4 ¡ Bước 4: tìm tất cả tập con Xi của tập trung gian (TG). TG={A,B} => X1={}; X2={A}; X3={B}; X4={AB} ¡ Bước 5: tìm siêu khóa Si theo nguyên tắc nếu (TN U Xi)+ = Q+ thì Si = TN U {Xi} ¡ Bước 6: tìm Khóa bằng cách loại bỏ các siêu khóa không tối thiểu (loại bỏ các siêu khoá chứa/bao phủ các siêu khoá khác) ó xác định các siêu khóa tối thiểu là khoá của lược đồ 8/9/21 8:06 AM 55 Ví dụ ¡Ví dụ: Cho LĐQH Q(ABCDEG) và F = {EC→B, AB→C, EB→D, BG→A, AE→G}. Xác định tất cả các khóa của Q 8/9/21 8:06 AM 59 Ví dụ ¡Cho tập thuộc tính ABCD và PTH F = { A® BC, B® C, AB® D} Xác định tất cả các khóa của lược đồ 8/9/21 8:06 AM 60 Ví dụ ¡ Bài 1: Cho lđqh Q(ABCDEG) và F = { AE ® C; CG ® A; BD ® G, GA ® E } - Xác định tất cả các khoá của Q. ¡ Bài 2: Cho lđqh Q(ABCDEG) và F = { EC ® B; AB ® C; EB ® D, BG ® A; AE ® G } Xác định tất cả các khoá của Q. ¡ Bài 3: Cho lđqh Q(ABCDEG) và F = {AB ® C; D ® EG; C ® A; BE ® C; BC ® D; CG ® BD; ACD ® B; CE ® AG } - Xác định tất cả các khoá của Q. 8/9/21 8:06 AM 61 VII. Thuộc tính dư thừa ¡ Cho F = {Lj → Rj: Lj, Rj ⊆ Ω}. ¡ Định nghĩa: üCho phụ thuộc hàm thuộc F có dạng A1A2→ B (vế trái của phụ thuộc hàm gồm nhiều thuộc tính) üNói rằng thuộc tính A1 dư thừa vế trái khi và chỉ khi G+ := F – {A1A2→ B} ∪ {A2→ B} ≅ F+. § Nói cách khác thuộc tính A1 trong vế trái của phụ thuộc A1A2→ B là dư thừa, nếu thay A1A2→ B bằng A2→ B thì bao đóng F+ không thay đổi. 8/9/21 8:06 AM 62 Thuật toán loại bỏ thuộc tính dư thừa ¡ Xét phụ thuộc có dạng A1A2→ B ∈ G (kiểm tra các PTH có vế trái có nhiều thuộc tính) ¡ Giả sử A1 là thuộc tính dự thừa, Loại bỏ tạm thời thuộc tính A1 trong A1A2→ B ŸTính: (A2)+ dựa trên F ŸKiểm tra: *Nếu B ⊆(A2)+ thì A1 là thuộc tính dư thừa. *Ngược lại, A1 không dư thừa 8/9/21 8:06 AM 63 Ví dụ ¡ Cho lược đồ quan hệ: a= - U = {A,B,C,D,E,G,H} - F ={AàD, ABàDE, CEàG, Eà H} ¡ Y/c: Loại bỏ thuộc tính dư thừa ở VT của các PTH 8/9/21 8:06 AM 65 ¡Ví dụ: Cho F = { AB® CD, B® C, C® D } - Kiểm tra xem F có chứa PTH có vế trái dư thừa hay không? 8/9/21 8:06 AM 67 8/9/21 8:06 AM 68 VII. Tập PTH tối thiểu ¡Định nghĩa: tập pth F được gọi là tập phụ thuộc hàm tối thiểu nếu: -Không có thuộc tính ở vế trái dư thừa -Không có thuộc tính ở vế phải dư thừa ŸMọi vế phải của các pth trong F chỉ có 1 thuộc tính -Không có phụ thuộc hàm F dư thừa 8/9/21 8:06 AM 73 *Thuật toán tìm PTH tối thiểu -Bước 1: Loại khỏi F các PTH có thuộc tính vế trái dư thừa -Bước 2: Đưa tất cả các PTH trong F về dạng PTH vế phải chỉ có 1 thuộc tính -Bước 3: Loại khỏi F các PTH dư thừa 8/9/21 8:06 AM 76 Ví dụ: ¡ Cho tập thuộc tính R = {P,C,H,A,R,T} và tập phụ thuộc hàm F như sau: - F = { P → CHART, CH → PART, C → T, A→ R } - Tìm tập PTH tối thiểu 8/9/21 8:06 AM 81 ¡Ví dụ: - Cho tập U={A,B,C,D,E} và F = { A ®C, BD ®E, B ®D, B ®E, C ®AD } - Tìm tập PTH tối thiểu của F KIỂM TRA – 6/3/2021 ¡Cho lược đồ quan hệ R= với U = (ABCDEGH) và tập phụ thuộc hàm F ¡ F = {Aà D, ABà DE, CEàG, EàH}. - Tìm tất cả các khóa của lược đồ - Loại bỏ thuộc tính VT dư thừa (nếu có). ¡ Yêu cầu: ¡ Làm ra file word và nộp bài lên hệ thống LMS (trước 11H15) ¡ Trong file gồm: họ tên đầy đủ ¡ Yêu cầu đặt tên file: CSDL-ST7-MSV-Họ tên.docx 8/9/21 8:06 AM 83