hệ cơ sở dữ liệu chuẩn hóa

Các qui tắc phụ thuộc hàm  Các tính chất của phụ thuộc hàm - Tính phản xạ: Nếu B ⊆ A khi đó A → B - Tính gia tăng: Nếu A → B và C ⊆ Ω khi đó AC → BC - Tính bắc cầu: Nếu A → B và B → C khi đó A → C - Quy tắc hợp: Nếu A → B và A → C khi đó A → BC - Quy tắc tách: Nếu A → B và C ⊆ B khi đó A → C Các qui tắc phụ thuộc hàm Ví dụ: Cho lược đồ R=ABC và F={AB→C, C→A} Hãy chứng minh rằng BC→ABC 1. C→A (theo giả thiết) 2. BC→AB (luật 1 thêm B) 3. AB→C (giả thiết) 4. AB→ABC (luật 3 thêm AB) 5. BC→ABC (luật bắc cầu từ 2 đến 4) Các qui tắc phụ thuộc hàm Ví dụ: Cho {AB → E, AG → I, BE → I, E → G, GI → H} Chứng minh AB → GH 1. AB → E; E → G ⇒ AB → G 2. AB → G ⇒ AB → AG mà AG → I ⇒ AB → I AB → G, AB → I ⇒ AB → GI, mà GI → H ⇒ AB → H Từ (1) và (2): AB ⇒ GH Suy diễn lô-gíc  Định nghĩa: Giả sử F là tập các phụ thuộc hàm trên lược đồ quan hệ R, X và Y là các tập con thuộc tính của R Ta nói rằng F suy diễn lôgic phụ thuộc hàm X→Y hay phụ thuộc hàm X→Y được suy diễn lôgic từ F Ký hiệu F |= X→Y nếu mọi quan hệ r thoả các phụ thuộc hàm trong F cũng thoả phụ thuộc hàm X→Y Ví dụ: {A→B, B→C} |= A→C Bao đóng của tập phụ thuộc hàm  Định nghĩa: Bao đóng của tập phụ thuộc hàm F, ký hiệu là F+, là tập hợp tất cả các phụ thuộc hàm suy diễn lôgic từ F: F+ = {X→Y  F |= X→Y}  Ví dụ: Cho F = {A → B, B → C, A → D, B → D }. Tìm F+? - Từ A → B, B → C, suy ra A → C ∈ F+ - Vì B → C và B →D, suy ra B→ DC ∈ F+ - Vì A → B và A → C ∈ F+, suy ra A→ BC ∈ F+ - Vì A → B và A → D, suy ra A →BD ∈ F+ - Vì A → B và B → D, suy ra A → D ∈ F+ Bao đóng của tập phụ thuộc hàm  Ví dụ: Cho F = {A → B, C → X, BX → Z}. Khi đó AC → Z ∈ F+ ? - Vì A → B ⇒ AX → BX - Từ AX → BX , kết hợp BX →Z, suy ra AX → Z - Từ C → X ⇒ AC → AX - Áp dụng tính chất bắc cầu, AC → AX và AX → Z suy ra AC → Z ∈ F+