[DATABASE] Phủ tối thiểu của tập phụ thuộc hàm

Cách thực hiện:

• B1. Phân rã PTH sao cho VP chỉ còn 01 thuộc tính
• B2. Loại các thuộc tính dư thừa ở VT (không xét PTH mà VT có 01 thuộc tính)
• Bỏ thuộc tính ở VT khi và chỉ khi bao đóng của các thuộc tính còn lại chứa thuộc tính ở VP

• B3. Loại bỏ các PTH dư thừa (không xét PTH mà thuộc tính ở VP chỉ xuất hiện một lần)
• B3.1: Tìm bao đóng của VT
• B3.2: Nếu bao đóng của VT chứa thuộc tính ở VP thì nó là PTH dư thừa, ngược lại nó không là PTH dư thừa

------------

Ví dụ: Cho lược đồ quan hệ Q=(A, B, C, D) và PTH F={AB → CD, B → C, C → D} 

Tìm phủ tối thiểu? 

B1. Phân rã PTH sao cho vế phải chỉ còn một thuộc tính

F={AB → C, AB → D, B → C, C → D} 

B2. Bỏ các thuộc tính dư thừa ở vế trái

• B → C, C → D : không xét vì vế trái chỉ có một thuộc tính
• Xét AB → C
• A⁺_{F-{AB → C}}  = A, không chứa C nên B không thừa
• B⁺_{F-{AB → C}} = BCD, chứa C nên A thừa
• Loại thuộc tính A khỏi VT, ta được: B → C

• Xét AB → D
• A⁺_{F-{AB → D}} = A, không chứa D nên B không thừa 
• B⁺_{F-{AB → D}} = BCD, chứa D nên A thừa
• Loại thuộc tính A khỏi VT, ta được: B → D

Sau B2, thu được PTH F={B → C, B → D, C → D} 

B3. Loại các PTH dư thừa (không xét các PTH có thuộc tính ở VP chỉ xuất hiện một lần)

• B → C: thuộc tính C chỉ xuất hiện một lần ở mọi VP của PTH nên không xét
• Xét B → D : Tính B⁺_{F-{B → D}} = BCD, chứa C nên AB → C thừa => Loại AB → C khỏi F
• Xét C → D: Tính C⁺_{F-{C → D}} = C, không chứa D nên  C → D không thừa

Kết luận: Phủ tối thiểu là {B → C, C → D}

------------

Slide bài giảng: