Thuật Toán Tìm Phủ Tối Thiểu - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Trang chủ >
Giáo án - Bài giảng >
Cao đẳng - Đại học >

Thuật toán tìm phủ tối thiểu

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.37 MB, 89 trang )

Thuật toán tìm phủ tối thiểuBước 1: Tách vế phải mỗi phụ thuộc hàm trong F saocho vế phải của mỗi phụ thuộc hàm chỉ chứa mộtthuộc tính (điều này luôn thực hiện được do bổ đềtrên)Bước 2. Tìm tập phụ thuộc hàm đầy đủ bằng cáchloại bỏ các thuộc tính dư thừa ở vế trái của từngphụ thuộc hàm.Chú ý:Việc tìm tất cả các tập X' ⊆ X theo thuật toán trênhoàn toàn thay thế được việc tìm X' cách tìm cáctập con của X.Bước 3. Loại bỏ các phụ thuộc hàm dư thừa trong F.Ví dụCho lược đồ quan hệ Q và tập phụ thuộc F như sau: Q(ABCD)F={ AB→CD; B→C; C→D} Hãy tìm phủ tối thiểu của F.Giải:Bước 1: Tách các phụ thuộc hàm có vp chưa đơnF1={ AB→C; AB→D; B→C; C→D}Bước 2: Loại bỏ các phụ thuộc hàm có VT dư thừaXét 1: A+ =A không chứa CB+ = BCD ⊃ C. Vậy (1) dư thừa TT AXét 2: A+ =A không chứa DB+ = BCD ⊃ D. Vậy (2) dư thừa TT AVậy sau khi loại bỏ thuộc tính dư thừa ta thu được tập phụ thuộc hàmF2={ B→C; B→D; B→C; C→D} ={ B→D; B→C; C→D}Bước 3: Loại bỏ phuộc hàm dư thừaXét 1: B+ =BCD ⊃ Dsuy ra (1) thừaXét 2: B+ -{1}- {2} =B không chứa CXét 3: C+ -{1}- {3} =C không chứa DQ(ABCD) F={ B→C; C→D }BÀI ICho lược đồ quan hệ R(U, F), U={ABCDEFGHIJ},F1={AB->CI, BD->EF, C->HI, AD->GH,A->I, H->J}b.Tìm tập F tối thiểu?AB có phải là khóa của R không?c.Tìm tất cả các khóa của R?a.BÀI IICho lược đồ quan hệ R(U, F), U={ABCDE} và tập phụ thuộchàmF={AB->DE, D->EB, BD->C, B->D}a.Tìm bao đóng của AB?b.Tìm tất cả các khóa của R?BÀI IIICho lược đồ quan hệ R(U, F), U={ABCDE} và tập phụ thuộchàmF={AB->CD, A->B, C->E, E->DC}a.Tìm bao đóng của AB?b.Tìm tất cả các khóa của R?Chương 4. Lý thuyết thiết kếCSDL5.1. CÁC VẤN ĐỀ GẶO PHẢI KHI TỔ CHỨC CSDL5.2. PHỤ THUỘC HÀM5.3 BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM VÀBAO ĐÓNG CỦA TẬP THUỘC TÍNH5.4. KHOÁ CỦA LƯỢC ĐỒ QUAN HỆ - MỘT SỐTHUẬT TOÁN TÌM KHOÁ5.5. PHỦ TỐI THIỂU (minimal cover)5.6.DẠNG CHUẨN CỦA LƯỢC ĐỒ QUAN HỆ5.7 PHÉP TÁCH KẾT NỐI BẢO TOÀNMột số khái niệm liên quan đến dạngchuẩnThuộc tính khoá/không khoáA là một thuộc tính khoá nếu A có tham gia vào bất kỳmột khoá nào của quan hệ, ngược lại A gọi là thuộc tínhkhông khoá.Ví dụ:Cho lược đồ quan hệ Q(ABC) và tập phụ thuộc hàmF={ A→ B; A → C; B → A}Có hai khóa là A và B. khi đó thuộc tính khoá là A, B;thuộc tính không khóa là: CThuộc tính phụ thuộc đầy đủ-phụthuộc hàm đầy đủA là một thuộc tính phụ thuộc đầy đủ vào tập thuộc tính Xnếu X →A là một phụ thuộc hàm đầy đủ (tức là không tồntại X' ⊂ X sao cho X' → A ∈ F+)Ví dụ: Cho lược đồ quan hệ Q(ABC) và tập phụ thuộc hàmF={ A → B; A→ C; AB → C} PTH A →B; A → C là các phụ thuộc hàm đầy đủ. PTH AB → C không là phụ thuộc hàm đầy đủ vì cóA → C.Chú ý rằng, một phụ thuộc hàm mà vế trái chỉ có một thuộctính là phụ thuộc hàm đầy đủ.

Xem Thêm