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ÀM

Một số định nghĩa
Cho 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 đương
Thuậ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  G
Phủ 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ừa
Phủ 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.1
Phủ 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BC
Xét BD : {ABC, ABD} không thể |= BD
Xé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ểu
Bướ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 F
Bướ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ếu
KF+ = Q+
Định nghĩa : K là 1 khóa của Q nếu
KF+ = 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 LDQH
Input : Lược đồ quan hệ Q, tập PTH F
Output : K là 1 khóa của Q
Bướ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 Q
Khóa của lược đồ quan hệ (p.2)
Tính chất của khóa
Ký 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 – TD
Tí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 minh
Chứ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  V
Dự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óa
Bước 1 : Tạo tập TN, TG
Bướ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 Si
Bướ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)