Chương 5: Phụ thuộc hàm và một số ứng dụng

Phụ thuộc hàm (functional dependancy) là một công cụ dùng để biểudiễn một cách hình thức các ràng buộc toàn vẹn.
Nội dung trích xuất từ tài liệu:
Chương 5: Phụ thuộc hàm và một số ứng dụng MônCƠSỞDỮLIỆUChương5:Phụthuộchàm vàmộtsốứngdụngNộidung 1. PHỤ THUỘC HÀM Định Nghĩa Phụ Thuộc Hàm  Một số tính chất của phụ thuộc hàm - hệ luật dẫn  armstrong 2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM F & CỦA TẬP THUỘC TÍNH X Bao đóng của tập phụ thuộc hàm F  Bao đóng của tập thuộc tính X  3. THUẬT TOÁN TÌM BAO ĐÓNG F+ VÀ X+, BÀI TOÁN THÀNH VIÊN Bài toán thành viên  Thuật toán tìm bao đóng của một tập thuộc tính (X)  2Nộidung(tt) 4. PHỦ TỐI THIỂU CỦA MỘT TẬP PHỤ THUỘC HÀM Tập Phụ Thuộc Hàm Tối Thiểu  Tập Phụ Thuộc Hàm Tương Đương  Thuật Toán Tìm Phủ Tối Thiểu Của Một Tập Phụ Thuộc Hàm  5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ - MỘT SỐ THUẬT TOÁN TÌM KHÓA Định Nghĩa  Thuật toán tìm một khóa của một lược đồ quan hệ Q  Thuật Toán Tìm Tất Cả Các Khóa Của Một Lược Đồ Quan Hệ  6. DẠNG CHUẨN CỦA LƯỢC ĐỒ QUAN HỆ Dạng chuẩn 1, 2, 3  Dạng chuẩn Boyce Codd  31.PHỤTHUỘCHÀM Phụ thuộc hàm (functional dependancy) là một công cụ dùng để biểu diễn một cách hình thức các ràng buộc toàn vẹn.Định Nghĩa Phụ Thuộc Hàm Cho lược đồ quan hệ Q với {A1,A2,…,An} là tập các thuộc tính. X, Y là hai tập con khác rỗng của Q. Ta nói X xác định Y (hay Y phụ thuộc hàm vào X) nếu với r là một quan hệ trên Q và nếu hai bộ t1,t2 bất kỳ thuộc r mà t1.X = t2.X ==> t1.Y = t2.Y. Khi đó ta ký hiệu là X → Y Phụ thuộc hàm X → X được gọi là phụ thuộc hàm hiển nhiên. người ta thường dùng F để chỉ tập các phụ thuộc hàm định nghĩa trên Q. Vì Q hữu hạn nên F cũng hữu hạn, ta có thể đánh số các phụ thuộc hàm của F là f1, f2, .., fm. Quy ước rằng chỉ cần mô tả các phụ thuộc hàm không hiển nhiên trong tập F (các phụ thuộc hàm hiển nhiên được ngầm hiểu là đã có trong F}. 41.PHỤTHUỘCHÀM(tt)Một số tính chất của phụ thuộc hàm - hệ luật dẫn armstrong Để có thể xác định được các phụ thuộc hàm khác từ tập phụ thuộc hàm đã có, ta dùng hệ tiên đề Armstrong (1974), gồm các luật sau:với X,Y,Z,W ⊆ Q+ X →X Luật phản xạ:1. X → Y ==> XZ → YZ Luật thêm vào:2. X → Y, Y → Z ==> X → Z Luật bắc cầu:3. Luật bắc cầu giả: Cho X → Y, WY → Z ==> XW → Z4. Cho X → Y, X → Z ==> X YZ Luật hợp:5. Cho X → Y, Z → Y ==> X → Z Luật phân rã:6.(các hệ tiên đề 1,2,3 được gọi chung là Hệ luật dẫn Armstrong) 52.BAOĐÓNGBao đóng của tập phụ thuộc hàm F Bao đóng của tập phụ thuộc hàm F (thường ký hiệu là F+) là tập hợp tất cả các phụ thuộc hàm có thể suy ra từ F dựa trên các tiên đề Armstrong.Ví dụ: Cho r là quan hệ trên lược đồ quan hệ Q(A,B,C,D) và tập F được cho như sau:F = {A → B; B → C; A → D ; B → D}khi đó F+= { A → B; B → C; A → D ; B → D;A → BD; A → BCD; A → C; A → CD; A → BC; B → CD;….}Rõ ràng F ⊆ F+ Các tính chất của tập F+ Tính phản xạ: Với mọi tập phụ thuộc hàm F+ ta luôn luôn có F ⊆ F+ x Tính đơn điệu: Nếu F ⊆ G thì F+ ⊆ G+ x Tính lũy đẳng: Với mọi tập phụ thuộc hàm F ta luôn luôn có F++ = F+. 6 x2.BAOĐÓNG(tt)Bao đóng của tập thuộc tính X Cho r là quan hệ trên lược đồ quan hệ Q. giả sử F là tập các phụ thuộc hàm trong Q, X ⊆ Q+.Bao đóng của tập thuộc tính X đối với F ký hiệu là X+ (hoặc X+F) là tập tất cả các thuộc tính A của Q được suy ra từ X dựa vào hệ tiên đề Armstrong và các phụ thuộc hàm trong F.X+ = {A : A ∈ Q và X → A ∈ F+} 72.BAOĐÓNG(tt)Bao đóng của tập thuộc tính X – Ví dụQ(A,B,C,D,E,G);F={A → C; A → EG; B → D; G → E};X={A,B};Y={C,G,D}Thì X+ = {A,B,C,D,E,G}; Y+ = {C,G,D,E}Tương tự như tập bao đóng của tập PTH F+, tập bao đóng X+ cũng chứa các phần tử của X+, tức là X ⊆ X +. 82.BAOĐÓNG(tt)Bao đóng của tập thuộc tính X – Ví dụNếu X,Y là các tập con của tập thuộc tính Q thì ta có các tính chất sau đây: X ⊆ X+ phản xạ: x Tính Nếu X ⊆ Y thì X+ ⊆ Y+ x Tính đơn điệu: x Tính lũy đẳng: X++ = X+ x (XY)+ ⊇ X+Y+ x (X+Y)+ = (XY+)+ = (X+Y+)+ x X → Y∈ F+ ⇔ Y ⊆ X+ x X → Y ⇔ Y+ ⊆ X+ x X → X+ và X+ → X x X+ = Y+ ⇔ X → Y và Y → X 93.TTTÌMBAOĐÓNGF+VÀX+Bài toán thành viên Trên đây ta nhận thấy rằng X+ được định nghĩa thông qua F+. Một vấn đề quan trọng khi nghiên cứu lý thuyết CSDL là: Cho trước tập các PTH F và một phụ thuộc hàm f, có hay không một khẳng định f ∈ F+ ? bài toán này được gọi là bài toán thành viên. Để trả lời câu hỏi này (bài toán thành viên) không đơn giản, vì mặc dù F là rất nhỏ nhưng F+ thì có thể rất lớn. Tuy nhiên để giải bài toán thành viên, chúng ta có thể dùng tính chất 6 của tập bao đóng X+. đó là tính chất X → Y ∈ F+ ⇔ Y ⊆ X . Do vậy chỉ cần tính X+ và so sánh với tập Y, ta có ngay câu trả lời X → Y ∈ F+ hay không ? Do đó, việc tính X+ được giải quyết đơn giản hơn rất nhiều. 103.TTTÌMBAOĐÓNGF+VÀX+(tt)Thuật toán tìm bao đóng của một tập thuộc tính (X)(độ phức tạp O(N2), với N là số thuộc tính của Q) Q, F, X ⊆ Q+Dữ Liệu VàoDữ Liệu Ra X+ Bước 1: Đặt X+ = X Bước 2: Temp = X+ ∀ f U →V ∈ F Neáu U ⊆ X+ thì X+ = X+ ∪ V Bước 3: Nếu X+=Temp thì X+ chính là kết quả cần tìm và kết thúc thuật toán. Ngược lại trở lại bước 2. ...