CHƯƠNG 10: PHỤ THUỘC HÀM
(Functional Dependencies)
Phụ thuộc hàm (FD)
•Định nghĩa: Cho một lược đồ quan hệ gồm n
thuộc tính: Q(A1, A2,…, An)
–X, Y là hai tập con của Q+={A1, A2,…, An}.
–r là một quan hệ trên Q.
–t1, t2 là hai bộ bất kỳ của r.
Ph thu c hàm gi a hai thu c tính X và Y ký hi u là X ụ ộ ữ ộ ệ
Y đc đnh nghĩa nh sau:ượ ị ư
X Y (t1.X = t2.X t1.Y = t2.Y)
(Ta nói X xác đnh Y hay Y ph thu c hàm vào X)ị ụ ộ
Phụ thuộc hàm (FD)
•Ví dụ: cho lược đồ quan hệ: Q(A, B, C, D, E)
A B C D E
1 2 3 4 5
1 4 3 4 5
1 2 4 4 1
I. AB C
II. B D (T)
III. DE A (T)
Phụ thuộc hàm (FD)
•Phụ thuộc hàm hiễn nhiên:
Nếu X Y thì X Y.
–Với r là quan hệ bất kỳ, F là tập phụ thuộc hàm thỏa
trên r, ta luôn có
F {các phụ thuộc hàm hiển nhiên}
Phụ thuộc hàm (FD)
•Thuật toán Satifies: Cho quan hệ r và X, Y là
hai tập con của Q+, Thuật toán SATIFIES sẽ trả
về trị true nếu X Y ngược lại là false
•SATIFIES(r,X,Y)
–Sắp các bộ của quan hệ r theo X để các giá trị giống
nhau trên X nhóm lại với nhau
–Nếu tập các bộ cùng giá trị trên X cho các giá trị trên Y
giống nhau thì trả về true ngược lại là False