Thiết kế cơ sở dữ liệu quan hệ - Phần V Phủ của tập phụ thuộc hàm

THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ (Relational Database Designing)Phần V – PHỦ CỦA TẬP PHỤ THUỘC HÀMMột số định nghĩaCho F, G là 2 tập phụ thuộc hàm,	F và G gọi là tương đương nếu và chỉ nếu 	F+=G+	Ký hiệu : F  G	F gọi là phủ G nếu và chỉ nếu	F+  G+2 tập Phụ thuộc hàm tương đươngThuật toán kiểm tra F  G Bước 1 : 	Tính F+, G+Bước 2 : 	Nếu F+ = G+, => F  G	Thuật toán kiểm tra F  GPhủ tối thiểu (minimal cover) –Tập Phụ thuộc hàm không đầy đủCho lược đồ Q, tập PTH F, ZY  F.ZY gọi là có vế trái dư thừa hay Y phụ thuộc không đầy đủ vào Z hay ZY là phụ thuộc hàm không đầy đủ nếu và chỉ nếu :	A  Z: 	F  (F \ {ZY})  {(Z-A)Y}Ngược lại, ZY gọi là phụ thuộc hàm đầy đủ hay không có vế trái dư thừa.F được gọi (tắt) là có vế trái không dư thừa, nếu F không chứa PTH có vế trái dư thừa.Phủ tối thiểu của 1 tập phụ thuộc hàm (p.1)Phụ thuộc hàm không đầy đủ - Ví dụCho Q(ABC), F={ABC, BC}	Xét ABC :	F’ = F – {ABC} = {BC}	(AB-A)C = {BC}	=> F’ = 	(F – {ABC})  {(AB-A)C} = 	{BC}	Tính (F’)+ , ta có (F’)+ = {ABC,BC}	Tính F+ = F = {ABC, BC}	=> F+ = (F’)+	=> ABC là phụ thuộc hàm có vế trái dư thừaPhủ tối thiểu của 1 tập phụ thuộc hàm (p.2)Thuật toán loại khỏi F các PTH không đầy đủBước 1 : Tính F+Bước 2 : Duyệt tập F, với mọi d = XY F :	Bước 2.1 : Duyệt các tập con X’ của X :	Nếu X’Y  F+ : thay X = X’, lặp lại 2.1Phủ tối thiểu của 1 tập phụ thuộc hàm (p.3)Tập phụ thuộc hàm có vế phải 1 thuộc tínhĐịnh nghĩa : F được gọi là tập phụ thuộc hàm có vế phải 1 thuộc tính nếu và chỉ nếu mọi phụ thuộc hàm trong F đều có vế phải chỉ 1 thuộc tính.Ví dụ : F = {ABC,BC,ABD}, ta tách các phụ thuộc hàm trong F để F thỏa tiêu chuẩn là tập phụ thuộc hàm có vế phải 1 thuộc tính :	F = {AB, AC, BC, ABD}Phủ tối thiểu của 1 tập phụ thuộc hàm (p.4)Tập phụ thuộc hàm không dư thừaĐịnh nghĩa : F được gọi là tập phụ thuộc hàm không dư thừa 	Không  F’  F, F’ F	Ngược lại, F được gọi là tập phụ thuộc hàm dư thừa.Ví dụ : F = {ABC, BD, ABD}	F dư thừa vì F  F’ = {ABC, BD}Phủ tối thiểu của 1 tập phụ thuộc hàm (p.5)Thuật toán loại khỏi F các PTH dư thừa	Duyệt từng PTH XY thuộc F :	Nếu (F-{XY}) |= XY thì F = F-{XY}Ví dụ : F = {ABC, BD, ABD}Xét ABC : {BD, ABD} không thể |= ABCXét BD : {ABC, ABD} không thể |= BDXét ABD : {ABC,BD} |= ABD vì :	ABC => AB, do BD => AD => ABD	Vậy ABD là dư thừa trong F, => F = {ABC,BD}Phủ tối thiểu của 1 tập phụ thuộc hàm (p.6)Tập PTH tối thiểuĐịnh nghĩa : F được gọi là một tập PTH tối thiểu (hay F là 1 phủ tối thiểu) nếu và chỉ nếu F thỏa 3 điều kiện sau :F là tập PTH có vế trái không dư thừa.F là tập PTH có vế phải 1 thuộc tính.F là tập PTH không dư thừa.Phủ tối thiểu của 1 tập phụ thuộc hàm (p.7)Thuật toán tìm Phủ tối thiểuBước 1 :	Loại khỏi F các PTH có vế trái dư thừa.Bước 2 :	Tách các PTH có vế phải nhiều hơn 1 thuộc tính thành các PTH có vế phải 1 thuộc tính.Bước 3 :	Loại khỏi F các PTH dư thừa.Luôn tìm được ít nhất 1 PTH tối thiểu của 1 tập PTH bất kỳ.Có thể tìm được nhiều PTH tối thiểu của 1 tập PTH bất kỳ.Phủ tối thiểu của 1 tập phụ thuộc hàm (p.8)Thuật toán tìm PTT – Ví dụInput : Q(ABCD), F = {ABCD, BC, CD}Output : Fm = PTT của FBước 1 :	ABCD là PTH không đầy đủ, vì A là dư thừa trong vế trái: BC, CD => BCD.	=> F = {BCD, BC, CD}Bước 2 :	F = {BC, BD, BC, CD}Bước 3 :	F = {BC, CD}Phủ tối thiểu của 1 tập phụ thuộc hàm (p.9)Khóa(Key) của lược đồ quan hệCho Q(A1,A2,,An), tập PTH F, K là 1 tập con của Q+Định nghĩa : K là 1 siêu khóa của Q nếuKF+ = Q+Định nghĩa : K là 1 khóa của Q nếuKF+ = Q+Không tồn tại K’  K , K’F+ = Q+Khóa của lược đồ quan hệ (p.1)Thuật toán tìm khóa của LDQHInput :	Lược đồ quan hệ Q, tập PTH FOutput : 	K là 1 khóa của QBước 1 : 	gán K = Q+Bước 2 :	Duyệt các thuộc tính A trong K,	_ Tính K’+ với K’ = K-A	_ Nếu K’+ = Q+, gán K = K’ Khóa K tìm được có thể không là khóa duy nhất của QKhóa của lược đồ quan hệ (p.2)Tính chất của khóaKý hiệu : Tập nguồn (TN) : chứa tất cả các thuộc tính chỉ xuất hiện ở vế trái của các PTH trong F.Tập đích (TD) : chứa tất cả các thuộc tính chỉ xuất hiện ở vế phải của các PTH trong F.Tập trung gian (TG) = Q+ - TN – TDTính chất : Nếu K là 1 khóa của Q, thì 	TN  K và TD  K = Khóa của lược đồ quan hệ (p.3)Tính chất của khóa – Chứng minhChứng minh TN  K :Giả sử TN không  K, => tồn tại 1 PTH XYF và X không  K và không tồn tại 1 PTH ZV F sao cho X  VDựa trên thuật toán tìm bao đóng của tập thuộc tính K => X không xuất hiện trong Ki nào => XK+F => trái với giả thiết (K là khóa, nên XK+F)Khóa của lược đồ quan hệ (p.4)Tính chất của khóa – Chứng minh (t.t)Chứng minh TD  K =  :Giả sử TD  K   => A: A  TD  A  K A  TD => tồn tại 1 PTH XAF (1) AK => K+=(K-A)+A ; X K+X(K-A)+A ;AX vì XA không là PTH hiển nhiên (xem slide 4 chương 4) => X(K-A)+ => K-AX (2)(1) và (2) => K-AA => (K-A)+ = [(K-A)A]+=K+ => vô lý vì K là khóa.Khóa của lược đồ quan hệ (p.5)Thuật toán tìm tất cả các khóaBước 1 : Tạo tập TN, TGBước 2 : Nếu TG= => Q chỉ có 1 khóa K = TN, kết thúc thuật toán.Bước 3 : Tìm tất cả tập con Xi của TG, đặt Si=TNXi , tính Si+. Gọi L là tập tất cả các SiBước 4 : Duyệt tập Si, nếu Si+Q+ thì bỏ Si khỏi L.Bước 5 : Với mọi Sk,Sl  L, nếu Sk Sl thì bỏ Sk khỏi L. Tập L còn lại chính là tập tất cả các khóa của Q.Khóa của lược đồ quan hệ (p.6)