Bài giảng Cơ sở dữ liệu: Chương 5 - Trịnh Xuân

Chia sẻ: 5A4F5AFSDG 5A4F5AFSDG | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

102
lượt xem 5
download

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

Chương 5: Phụ thuộc hàm. 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. Trong chương này chúng ta sẽ tìm hiểu một số nội dung chính sau: Hệ tiên đề Amstrong, bao đóng - closure, tập phụ thuộc hàm tương đương, phụ thuộc hàm dư thừa. Mời các bạn 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 5 - Trịnh Xuân

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