Thiết kế cơ sở dữ liệu quan hệ - Phần IV Phụ thuộc hàm

THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ (Relational Database Designing)Phần IV – PHỤ THUỘC HÀM(Functional Dependency)Phụ thuộc hàm – Khái niệmPhụ thuộc hàm là công cụ để biểu diễn hình thức các RBTV phụ thuộc.Các lý thuyết về Phụ thuộc hàm ứng dụng nhiều trong bài toán Chuẩn Hóa CSDL.Ký hiệu :	X  Y : Y phụ thuộc hàm vào X hay X xác định Y.	với X, Y là các tập thuộc tính (trong 1 lược đồ quan hệ). Khái niệm về Phụ thuộc hàmPhụ thuộc hàm – Định nghĩaCho Q(A1,A2,,An); X, Y là 2 tập con của Q+; q là 1 quan hệ trên Q; t1, t2 là 2 bộ bất kỳ của q. Ta có X xác định Y , ký hiệu X  Y , nghĩa là	(t1.X=t2.X => t1.Y=t2.Y)	Nếu 2 bộ bất kỳ trong q giống nhau trên X thì phải giống nhau trên Y.X  Y là PTH của Q, khi X  Y đúng với mọi q là quan hệ trên QHệ quả : Q, X  Q+ , X   Định nghĩa về Phụ thuộc hàmPhụ thuộc hàm hiển nhiên (Trivial Dependencies)Nếu X  Y thì XY luôn đúngTrong trường hợp này (X  Y), XY được gọi là Phụ thuộc hàm hiển nhiên. Ví dụ : XXKhi chuẩn hóa CSDL, ta thường không quan tâm đến các PTH hiển nhiên.Phụ thuộc hàm hiển nhiênThuật toán kiểm tra PTH : SatifiesInput : 	_ Quan hệ q, 	_ Tập thuộc tính X, YOutput :	_ True nếu XY, ngược lại, FalseThuật toán kiểm tra Phụ thuộc hàm (p.1)Thuật toán kiểm tra PTH (t.t)Bước 1 :	Sắp lại các bộ trong q sao cho các bộ giống nhau trên X nằm kề nhau.Bước 2 :	Kiểm tra nếu tất cả các bộ giống nhau trên X cũng giống nhau trên Y thì trả về True, ngược lại, trả về False.Thuật toán kiểm tra Phụ thuộc hàm (p.2)Hệ luật dẫn Amstrong(Amstrong inference rule) - Một số định nghĩaKý hiệu F là tập các phụ thuộc hàm của lược đồ quan hệ Q, F = {f1,f2,,fn}, quy ước ta không quan tâm đến các phụ thuộc hàm hiển nhiên.Định nghĩa : Phụ thuộc hàm được suy diễn logic từ F.Phụ thuộc hàm d = XY được suy diễn logic từ F nếu với mọi q trên Q thỏa F thì cũng thỏa d, ký hiệu F |= XY , hay F|=d.Định nghĩa : Bao đóng của F(Closure), ký hiệu F+, là tập tất cả các phụ thuộc hàm được suy diễn logic từ FHệ luật dẫn Amstrong (p.1)Các tính chất của Bao đóng F+Tính phản xạVới mọi F+, ta luôn có F  F+Tính đơn điệuNếu F  G thì F+  G+Tính lũy đẳngVới mọi F, ta luôn có (F+)+ = F+Định nghĩa : Phủ của F, ký hiệu F- = G - F+, với G là tập tất cả các phụ thuộc hàm có thể có của QHệ luật dẫn Amstrong (p.2)Hệ luật dẫn AmstrongCho X,Y,Z,W là các tập con của Q+; q là 1 quan hệ bất kỳ trên Q.Luật phản xạ (Reflexive rule) : 	X  XLuật thêm vào (Augmentation rule) : X  Y => XZ  YLuật hợp (Union rule) : X  Y, X  Z => X  YZLuật phân rã (Decomposition rule) : X  YZ => X  Y, X  ZLuật bắt cầu (Transitive rule) : X  Y, Y  Z => X  ZLuật giả bắt cầu (Pseudo transitive rule) : 	X  Y, YZ  W => XZ  WHệ luật dẫn Amstrong (p.3)Bao đóng của tập thuộc tínhCho lược đồ quan hệ Q(A1,A2,,An) với quan hệ q; F là tập phụ thuộc hàm trên Q, X là 1 tập con của Q+.Định nghĩa : Bao đóng của X trên F, ký hiệu XF+, là tập các thuộc tính Ai :XF+= Ai với XAi được suy diễn từ F nhờ hệ luật dẫn Amstrong.Khi không có nhầm lẫn về F, ta viết X+ thay vì XF+Hệ luật dẫn Amstrong (p.4)Các tính chất của Bao đóngHệ quả : Bao đóng của Q chính là Q+ : QF+ = Q+Tính phản xạ :	X  X+Tính đơn điệu : 	X  Y => X+  Y+Tính lũy đẳng :	(X+)+ = X+(XY)+  X+Y+(X+Y)+ = (XY+)+ = (X+Y+)+X  Y  Y+  X+X  X+, 	X+  XX+ = Y+  X  Y và Y  XHệ luật dẫn Amstrong (p.5)Thuật toán tìm Bao đóngInput : lược đồ quan hệ Q, tập phụ thuộc hàm F, tập thuộc tính X.Output : X+Bước 1 :	i = 0, Xi = XBước 2 :	Duyệt tập F, Nếu Fk = YZ có Y  Xi thì 	Xi+1 = Xi  Z và F = F \ FkBước 3 : 	Nếu Xi+1  Xi : 	i = i+1, trở lại bước 2	 Nếu Xi+1 = Xi : kết thúcHệ luật dẫn Amstrong (p.6)Thuật toán tìm Bao đóng – Ví dụCho : Q(ABCDEGH), F = {	f1:	B		A	f2:	DA		CE	f3:	D		H	f4:	GH		C	f5:	AC		D 	}X = {AC}	, tìm X+ ?Hệ luật dẫn Amstrong (p.7)Tìm Bao đóng - Ví dụ (t.t)Hệ luật dẫn Amstrong (p.8)BướcCác giá trị của i,Xi, F1i = 0; X0 = X = {AC}2Xi+1=X1={ACD}; F = F \ f5= {f1,f2,f3,f4}3X1  X0 => i = i+1 = 1, quay lại bước 24 Xi+1=X2={ACDH}; F = F \ f3= {f1,f2,f4}5X2  X1 => i = i+1 = 2, quay lại bước 26Xi+1=X3={ACDHE}; F = F \ f2= {f1,f4}7X3  X2 => i = i+1 = 3, quay lại bước 28Không có fk nào.9X4 = X3 => Kết thúc giải thuật. X+={ACDHE}Thuật toán Kiểm tra F|=dCho d = XY, kiểm tra F|=d ?	Bước 1 : Tính X+=XF+	Bước 2 : Y  X+ F|=dHệ luật dẫn Amstrong (p.9)Tính chất của các PTH  F+Xét d = XY  F+ , => F |= d hay F+ |= dF |= d, => Y  XF+ (1)Gọi TN là tập các thuộc tính có xuất hiện ở vế trái của ít nhất 1 PTH trong FTừ thuật toán tìm bao đóng của tập thuộc tính, ta có kết luận rằng : Nếu X  TN => XF+ = X (2)Hệ luật dẫn Amstrong (p.10)Thuật toán tìm F+Input : Lược đồ Q, tập PTH FOutput : Tập PTH F+Bước 1 : F+ = , Tìm tất cả các tập con của TNBước 2 : Ứng với mỗi tập con X của TN: 	2.1	Tính XF+	2.2	Tìm tất cả các tập con Y của XF+ và Y  X	2.3	F+ = F+ + XYHệ luật dẫn Amstrong (p.11)