Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 8: Phụ thuộc hàm

Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 8 trang bị cho người học những hiểu biết về phụ thuộc hàm. Thông qua chương này người học sẽ nắm bắt được: Định nghĩa phụ thuộc hàm, bao đóng của tập thuộc tính X, sử dụng 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 Hệ quản trị cơ sở dữ liệu - Chương 8: Phụ thuộc hàmCHƯƠNG 10: PHỤ THUỘC HÀM (Functional Dependencies) Phụ thuộc hàm (FD)• Định nghĩa: Cho một lược đồ quan hệ gồm n thuộc tính: Q(A1, A2,…, An) – X, Y là hai tập con của Q+={A1, A2,…, An}. – r là một quan hệ trên Q. – t1, t2 là hai bộ bất kỳ của r. PhụthuộchàmgiữahaithuộctínhXvàYkýhiệulàX Yđượcđịnhnghĩanhưsau: XY (t1.X=t2.X t1.Y=t2.Y) (TanóiXxácđịnhYhayYphụthuộchàmvàoX) Phụ thuộc hàm (FD)• Ví dụ: cho lược đồ quan hệ: Q(A, B, C, D, E) A B C D E I. ABC 1 2 3 4 5 II. BD(T) 1 4 3 4 5 III. DEA(T) 1 2 4 4 1 Phụ thuộc hàm (FD)• Phụ thuộc hàm hiễn nhiên: Nếu X Y thì X Y. – Với r là quan hệ bất kỳ, F là tập phụ thuộc hàm thỏa trên r, ta luôn có F {các phụ thuộc hàm hiển nhiên} Phụ thuộc hàm (FD)• Thuật toán Satifies: Cho quan hệ r và X, Y là hai tập con của Q+, Thuật toán SATIFIES sẽ trả về trị true nếu X  Y ngược lại là false• SATIFIES(r,X,Y) – Sắp các bộ của quan hệ r theo X để các giá trị giống nhau trên X nhóm lại với nhau – Nếu tập các bộ cùng giá trị trên X cho các giá trị trên Y giống nhau thì trả về true ngược lại là False Phụ thuộc hàm (FD)• Ví dụ: SATIFIES(phanCong,MAYBAY,GIOKH) Phụ thuộc hàm (FD)• Cách tìm tất cả tập con của Q+: – Số tập con có thể có của Q+ = {A ,A ,...,A } là 2n – Số phụ thuộc hàm có thể có: 2nx2n A B C D A B C D AB AC AD BC BD Vídụ:Q+=(A,B,C,D) ABC ABD • Sốtậpcon:24=16 C AC • SốPTH: BC =24x24=256 ABC Hệ luật dẫn Armstrong• Phụ thuộc hàm được suy diễn logic từ F – Phụ thuộc hàm X Y được suy diễn logic từ F nếu một quan hệ r bất kỳ thỏa mãn tất cả các phụ thuộc hàm của F thì cũng thỏa phụ thuộc hàm X Y. Ký hiệu F|= X Y.• Bao đóng của F (F+) – Bao đóng của F ký hiệu F+ là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. Hệ luật dẫn Armstrong• Các tính chất của tập F+ – Tính phản xạ: F F+ – Tính đơn điệu: Nếu F G thì F+ G+ – Tính lũy đẳng: (F+)+ = F+. – Gọi G là tập tất cả các phụ thuộc hàm có thể có của r, phần phụ của F ký hiệu F‑ = G - F+ Hệ luật dẫn Armstrong• Hệ luật dẫn Amstrong: – Cho X,Y,Z,W là tập con của Q+ – r là quan hệ bất kỳ của Q. – Ba luật của tiên đề Amstrong: 1. Luật phản xạ (reflexive rule): NếuY XthìX Y 2. Luật tăng trưởng(augmentation rule): NếuZ QvàX YthìXZ YZ 5. Luật bắc cầu (Transivity Rule) NếuX YvàY ZthìX Z Hệ luật dẫn Armstrong– Ba hệ quả của tiên đề Amstrong:1. Luật hợp (Union Rule) NếuX YvàX ZthìX YZ2. Luật bắc cầu giả (Pseudotransivity Rule) NếuX YvàWY ZthìXW Z3. Luật phân rã (Decomposition Rule) NếuX YZthìX YandX Z Bao đóng của tập thuộc tính X (closures of attribute sets)• Định nghĩa: − Qlàlượcđồquanhệ. − rlàmộtquanhệtrênQ, − FlàtậpcácphụthuộchàmtrongQ. − X,AilàcáctậpconcủaQ+ BaođóngcủatậpthuộctínhXđốivớiFkýhiệulàX+ đượcđịnhnghĩa:X+= Ai vớiX AilàphụthuộchàmđượcsuydiễntừFnhờhệ tiênđềArmstrong Bao đóng của tập thuộc tính X (closures of attribute sets)• Thuật toán tìm bao đóng: – Tính liên tiếp tập các tập thuộc tính X0,X1,X2,... theo phương pháp sau: – Bước 1: X0 = X – Bước 2: lần lượt xét các phụ thuộc hàm của F • NếuY ZcóY XithìXi+1=Xi Z • LoạiphụthuộchàmY ZkhỏiF – Bước 3: Nếu ở bước 2 không tính được Xi+1 thì Xi chính là bao đóng của X – Ngược lại lặp lại bước 2 Bao đóng của tập thuộc tính X (closures of attribute sets)Ví dụ 1: Cho lược đồ quan hệ Q(A,B,C,D,E,G,H)và tập phụ thuộc hàm F={B A;DA CE;D H;GH C;AC D}.Tìmbaođóng củaX={AC}trênF § X(0)={A,C},{A,C} {D} § X(1)={A,C,D},{A,D} {C,E} § X(2)={A,C,D,E},{D} {H} ...