Tập phụ thuộc hàm tương đương

Hai tập phụ thuộc hàm F và G là tương đương nếu:

• Tất cả các phụ thuộc hàm trong F có thể được suy ra từ G, và
• Tất cả các phụ thuộc hàm trong G có thể suy ra từ F.

Vì thế, F và G là tương đương nếu F+ = G+

Nếu F và G là tương đương thì ta nói F phủ G hay G phủ F.

Thuật toán kiểm tra sự tương đương của 2 tập PTH

• F phủ G: “X ® YÎG, tính X⁺ từ F, sau đó kiểm tra xem YÎX⁺
• G phủ F: “X ® YÎF, tính X⁺ từ G, sau đó kiểm tra xem YÎX⁺

Ví dụ : Xét hai tập phụ thuộc hàm

F = {A →C, AC → D, E→AD, E →H }

G = { A →CD,  E → AH }

Ta chứng minh  F phủ G:

Tìm bao đóng của các vế trái của các phụ thuộc hàm trong G theo F. Áp dụng thuật toán tìm bao đóng của tập thuộc tính, ta có:

{A}⁺ = { A, C, D };

{E}⁺ = {E, A, D, H, C}

ta thấy các bao đóng này chứa các vế phải tương ứng. Từ đó suy ra F phủ G.

Ta chứng minh G phủ F:

Tìm bao đóng của các vế trái của các phụ thuộc hàm trong F theo G. Ta có:

{A}⁺ ={A,C,D},

{AC}+ = { A,C,D},

{E}+ = {E,A,H,C,D}, ta thấy các bao đóng này chứa các vế phải tương ứng. Từ đó suy ra E phủ F.

Tóm lại E tương đương với F.