Cơ sở dữ liệu - Chương VII: Phụ thuộc hàm

CHƯƠNG VII: 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/4/16 07:04 2 8/4/16 07:04 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 và 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: 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, MaHang, TongGiaTri) -  SoHD -> MaHang -  SoHD -> TongGiaTri !  Ví dụ: CHITIET_HOADON (SoHD, MaHang, SoLuong, DonGia, ThanhTien) -  SoHD , MaHang -> SoLuong -  SoHD , MaHang -> DonGia -  SoHD , MaHang -> ThanhTien 8/4/16 07:04 4 8/4/16 07:04 9 !  Biểu diễn phụ thuộc hàm: -  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/4/16 07:04 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ồmcác nguyên tắc biến đổi của PTH !  Định nghĩa: -  F là tập pth trên quan hệ R(U) và A→B là một pth với A, B⊂U. -  Nói rằng, pth A→B được suy diễn logic từ F nếu với mỗi quan hệ r xác định trên R thỏa các phụ thuộc hàm trong F thì cũng thỏa phụ thuộc hàm A→B. 8/4/16 07:04 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ó AB → C, C → EG thì AB → EG 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/4/16 07:04 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)) 8/4/16 07:04 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 Thực hiện: 1.  F ! A (gt) 2.  FB ! AB (tăng cường) 3.  AB ! C (gt) 4.  ABC ! C (tc) 5.  ABC ! E (gt) 6.  ABC ! EC (hợp 4 và 5) 7.  AB ! E (tách 6) 8.  FB ! E (bắc cầu 2 và 7) 8/4/16 07:04 19 !  Ví dụ: -  Hãy dùng hệ tiên đề Armstrong để chứng minh: -  Nếu X → Y và U → V thì XU → YV !  Chứng Minh: 1.  Từ X → Y (gt) 2.  Có XU → YU (tăng trưởng U vào (1) ) 3.  Từ U → V (gt) 4.  Có YU → YV (tăng trưởng Y vào (3) ) 5.  Có XU → YV (bắc cầu (2) và (4) ) 8/4/16 07:04 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+ } !  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 !  Nhận xét: -  X ⊆ X+ -  X→Y ∈ F+ " Y ⊆ X+ => Có nghĩa là: X →Y được suy diễn từ hệ tiên đề Amstrong khi và chỉ khi Y ⊆ X+ 2. Thuật toán tìm bao đóng của tập thuộc tính ! Closure of a set attributes ! Cho X ⊂ U là tập thuộc tính => Tìm X+ ! Thuật toán CLOSURE - Input: Tập thuộc tính X và tập phụ thuộc hàm F - Output: Tìm bao đóng X+ của F - Thực hiện: Lần lượt tính các chuỗi X0, X1, X2, và Xi 8/4/16 07:04 21 Thuật toán !  Bước 0: Đặt G = F và Gán X0 = X (i=0) !  Bước i (i = 1): Chọn một phụ thuộc hàm A → B ∈ G -  Nếu A ⊆ Xi #  Nếu B ⊄ Xi 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 4: Tồn tại chỉ số i sao cho: Xi = Xi+1 = Xi+2 = X+ 8/4/16 07:04 22 8/4/16 07:04 23 !  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/4/16 07:04 24 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) !  Cho LĐQH p = (U,F) với U = ABCDE, !  F = { A → C, BC → D, D → E, E → A }. !  Tính: -  (AB)+ -  (BD)+ - (D)+ 8/4/16 07:04 25 3. Bài toán thành viên !  Là bài toán để 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: -  Bước 1: Tính X+ -  Bước 2: 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 8/4/16 07:04 26 !  Ví dụ: Cho U = (ABCDE) 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 !  Ví dụ: Cho U = (ABEGHI) và pth F = {AB ! E, AG! I, BE!I, E ! G, GI ! H} -  Chứng minh rằng: AB ! GH 8/4/16 07:04 28 ! Chú ý: -  có thể áp dụng hệ tiên đề Amstrong để kiểm tra một pth có là thành viên của F hay không bằng cách áp dụng lần lượt các luật để suy ra pth cần chứng minh 8/4/16 07:04 29 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 (hay G phủ F). !  Kí hiệu: F ≡ G 8/4/16 07:04 30 !  Thuật toán kiểm tra sự tương đương của 2 tập PTH -  Kiểm tra G phủ F: ∀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 -  Kiểm tra F phủ G: ∀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 8/4/16 07:04 31 ! Ví dụ: Xét hai tập phụ thuộc hàm F = { A → C, AC → D, E→ AD, E → H } và E = { A → CD, E → AH } CMR: F và E là tương đương với nhau 8/4/16 07:04 32 !  Ví dụ: Cho lược đồ U = ABCDE và hai tập PTH: !  F = {A → BC, A → D, CD →E} và G = {A → BCE, A→ ABD, CD →E} !  Hỏi: -  F có tương đương với G không V. Phụ thuộc hàm dư thừa ! Cho F = {Lj → Rj | Lj, Rj  Ω} là tập các phụ thuộc hàm thoả trên lược đồ quan hệ s = . ! Phụ thuộc 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} 8/4/16 07:04 33 *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/4/16 07:04 34 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/4/16 07:04 35 ví dụ ! Cho lược đồ quan hệ : -  H= ; -  U = ABCD; -  F = {CD ! B, A!C, B!ACD} ! Kiểm tra CD ! B có dư thừa hay không? 8/4/16 07:04 36 VI. Thuộc tính dư thừa !  Cho tập các phụ thuộc hàm 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/4/16 07:04 38 Thuật toán loại bỏ thuộc tính dư thừa !  Xét phụ thuộc có dạng A1A2 A3...An  B  G (kiểm tra các PTH có vế trái có nhiều thuộc tính) !  Giả sử Ai là thuộc tính dự thừa, Loại bỏ tạm thời thuộc tính Ai trong A1 A2...AnB # Tính (A1 A2 ... Ai-1 Ai+1 ... An)+ # Kiểm tra B có là tập con của (A1 A2 ... Ai-1 Ai+1 ... An)+
 Nếu là tập con thì Ai là thuộc tính dư thừa.
 Ngược lại Ai không dư thừa 8/4/16 07:04 39 Ví dụ ! Cho PTH F = { A → BC, B → C, AB → D} Loại bỏ các thuộc tính dư thừa của tập PTH trên 8/4/16 07:04 40 Ví dụ !  Cho lược đồ quan hệ: α= -  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 8/4/16 07:04 41 8/4/16 07:04 44 VIII. Khóa của quan hệ 1.  Định nghĩa: - Cho R(A1, , An) là lược đồ quan hệ, gồm # Tập các thuộc tính U = { A1, A2, ... , An} # Tập các pth F= { f1, f2, ... ,fn} xác định trên R. - Tập K ⊆ U là siêu khóa nếu K+ = U hay K → U - 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 8/4/16 07:04 45 !  Nhận xét -  Một LĐQH có thể có một hoặc nhiều siêu khóa và khóa -  Số thuộc tính trong các khóa có thể khác nhau -  Hai khóa phân biệt không thể bao nhau 8/4/16 07:04 48 2. Thuật toán tìm 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 !  Ý tưởng: Bắt đầu từ tập U vì U+ = U. Bớt dần các thuộc tính của U để nhận được tập bé nhất mà bao đóng của nó vẫn bằng U. !  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/4/16 07:04 49 Ví dụ: ! cho R = { A,B,C,D,E,G,H,I } và ! F= { AC → B, BI → ACD, ABC → D, H → I , ACE → BCG, CG → AE } ! Tìm khóa của lược đồ trên? ! Nhận xét: Thuật toán trên chỉ tìm được một khoá trong sơ đồ quan hệ. Nếu cần tìm nhiều khoá, ta thay đổi trật tự loại bỏ các phần tử của tập K. 8/4/16 07:04 50 8/4/16 07:04 57 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. *Kiểm tra lược đồ có một khóa duy nhất !  Bước 1: Tính M theo công thức !  Bước 2: Tính bao đóng của M !  Bước 3: Dựa vào kết quả có kết quả như sau: -  Nếu M+ = U thì kết luận lược đồ có duy nhất một khóa -  Ngược lại: Lược đồ không có duy nhất một khóa 8/4/16 07:04 58 M =U − (R− L) L→R∈F ∪ * Thuật toán tìm tất cả các khóa !  Bước 1: -  Tạo tập nguồn TN -  Tập trung gian 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ìm tất cả tập con Xi của tập trung gian. !  Bước 4: 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 5: tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu " xác định các siêu khóa tối thiểu 8/4/16 07:04 59 8/4/16 07:04 61 Ví dụ ! Cho lược đồ quan hệ Q={ C, S, Z } tập phụ thuộc hàm F = {CS → Z; Z → C} tìm tất cả các khóa của lược đồ quan hệ trên. 8/4/16 07:04 62 !  Ví dụ: Cho LĐQH Q(ABCDEG) và F = {AE→C,CG→A, BD →G, GA→E}. Xác định tất cả các khóa của Q !  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 !  Ví dụ: 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 khóa của Q 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/4/16 08:35 63 8/4/16 07:04 64 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ế 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ó thuộc tính ở vế trái dư thừa - không có phụ thuộc hàm F dư thừa 8/4/16 07:04 69 *Thuật toán tìm phủ 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 Ví dụ 1 Bài 1: Cho lược đồ quan hệ: α= U = {A,B,C,D,E,G,H} F = { BH→CA, H→BG, GH→AD, DH→CG } Hãy rút gọn tập phụ thuộc hàm F? 8/4/16 07:04 70 Ví dụ 2: Cho lược đồ quan hệ: α = U = { A, B,C,D,E,G} F = { AB→C, D→EG, C→A, BE→C, BC→D, CG→BD, ACD→B } Rút gọn tập phụ thuộc hàm 8/4/16 07:04 71 8/4/16 07:04 77 ! Ví dụ: -  Cho F = { A →C, BD →E, B →D, B →E, C →AD } -  Tìm phủ tối thiểu của F ! Ví dụ: -  Cho G = { AB→ C, A → B, B → A, AB → F; A→ CD; B → E} -  Tìm phủ tối thiểu của G.