Chương 4: PTH - Cô Nguyễn Thị Thu Hiếu
Gửi bởi: Nguyễn Thị Thu Hiếu 10 tháng 9 2020 lúc 10:04:58 | Được cập nhật: 9 giờ trước (14:25:23) Kiểu file: PDF | Lượt xem: 379 | Lượt Download: 2 | File size: 0.7211 Mb
Nội dung tài liệu
Tải xuống
Link tài liệu:
Các tài liệu liên quan
Có thể bạn quan tâm
Thông tin tài liệu
Môn học
Cơ sở dữ liệu
GV: Nguyễn Thị Thu Hiếu
LOGO
Chương 4:
Ràng buộc toàn vẹn &
Phụ thuộc hàm
Chương 4:
Ràng buộc toàn vẹn & Phụ thuộc hàm
1. Ràng buộc toàn vẹn
2. Phụ thuộc hàm
2. Phụ thuộc hàm (PTH)
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.
2.8.
Định nghĩa và biểu diễn PTH
Suy diễn logic các PTH
Bao đóng của tập PTH
Hệ luật dẫn Armstrong
Bao đóng của tập thuộc tính
Phủ và phủ tương đương
Phủ tối thiểu
Thuật toán xác định khóa của lược đồ quan hệ
2. Phụ thuộc hàm (PTH)
2.1. Định nghĩa và biểu diễn PTH
2.2. Suy diễn logic các PTH
2.3. Bao đóng của tập PTH
2.4. Hệ luật dẫn Armstrong
2.5. Bao đóng của tập thuộc tính
2.6. Phủ và phủ tương đương
2.7. Phủ tối thiểu
2.8. Thuật toán xác định khóa của lược đồ quan hệ
2.1. Định nghĩa và biểu diễn PTH
Định nghĩa:
Phụ thuộc hàm - Functional Dependencies
Là sự biểu diễn RBTV dưới hình thức toán học
Bảo đảm thông tin không bị tổn thất khi phân rã
hoặc kết nối giữa các quan hệ.
2.1. Định nghĩa và biểu diễn PTH (tt)
Sử dụng PTH để:
Kiểm tra các quan hệ để xem chúng có thỏa
mãn tập các PTH đã cho không.
• Nếu quan hệ r đúng trên tập PTH F, ta nói r thỏa F.
Xác định các ràng buộc trên tập các quan hệ
được cho phép.
Chú ý:
Một thể hiện (quan hệ) của lược đồ quan hệ có
thể thỏa mãn 1 PTH cho dù PTH đó không đảm
bảo tính hợp lệ của tất cả các quan hệ.
2.1. Định nghĩa và biểu diễn PTH (tt)
Biểu diễn PTH:
Cho R(U) là một lược đồ quan hệ với
U = {A1, A2,..., An} là tập thuộc tính.
PTH giữa hai tập thuộc tính X, Y ⊆ U
• Ký hiệu: X → Y ( đọc là X xác định hàm Y hoặc Y
phụ thuộc hàm vào X )
• ∀r ∈ R, ∀ t1, t2 ∈ r nếu t1[X] = t2[X] thì t1[Y] = t2[Y].
2.1. Định nghĩa và biểu diễn PTH (tt)
Các PTH xuất phát từ các ràng buộc trong thế giới
thực.
Phụ thuộc hàm cơ bản nhất là những phụ thuộc hàm
khẳng định rằng một khoá xác định được tất cả các
thuộc tính của lược đồ quan hệ.
VD1:
Quan hệ HOCVIEN (MaHV, Ho, Ten, NgaySinh,
GioiTinh, NoiSinh, MaLop)
• Có các PTH sau:
MaHV → Ho, MaHV → Ten, MaHV → NgaySinh,
MaHV → GioiTinh, NoiSinh, MaLop.
• Không có PTH:
Ho, Ten → NgaySinh, NoiSinh.
2.1. Định nghĩa và biểu diễn PTH (tt)
VD2:
Quan hệ KETQUATHI(MaHV, MaMH, LanThi,NgayThi,Diem)
• Có các PTH sau:
MaHV, MaMH, LanThi → NgayThi
MaHV, MaMH, LanThi → Diem
• Không có PTH sau:
MaHV → Diem
PTH X → Y là tầm thường (trivial) Y = X
VD: Ho → Ho, Ten → Ten, NgaySinh → NgaySinh…
Một số phụ thuộc hàm khác:
VD: MaHV, Ho, Ten → NgaySinh, NoiSinh
2.1. Định nghĩa và biểu diễn PTH (tt)
Chú ý:
Vì thực thể được nhận dạng bằng giá trị của các
thuộc tính khóa nên nếu một thực thể có
• Các thuộc tính A1, A2,..., An
• X là tập các thuộc tính khóa của tập thực thể
• Y là mọi tập con thuộc tính
Thì ta có thể khẳng định: X → Y
Quan hệ r biểu diễn mối liên hệ n-1 từ tập thực
thể E1 đến tập thực thể E2
• X là khóa của E1; Y là khóa của E2
Thì ta có thể khẳng định: X → Y
2.2. Suy diễn logic các PTH
Cho lược đồ quan hệ R với tập thuộc tính U và
tập các PTH F.
X → Y là 1 PTH; X,Y ⊆ U.
Ta nói rằng X → Y được suy diễn logic từ F (hay F
khẳng định logic X → Y):
∀r ∈R, nếu r thỏa tất cả các PTH trong F thì r cũng
thỏa X → Y
Ký hiệu là: F X → Y.
VD:
Nếu F chứa A → B và B → C thì A → C được khẳng
định logic từ F.
Ký hiệu: {A → B, B → C} A → C
2.3. Bao đóng của tập PTH
Với F là tập các PTH, khi đó
Bao đóng (Closure) của F là tập các PTH
được suy diễn lôgic từ F.
Ký hiệu: F+ = {X → Y | F X → Y}
Nếu F = F+ thì ta nói F là họ đầy đủ (full
family) của các PTH.
Bao đóng của tập PTH được dùng để xác
định khóa dự tuyển của quan hệ, nhưng
chi phí tính toán lớn.
2.4. Hệ luật dẫn Armstrong
Để có thể xác định khoá của một lược đồ quan hệ
Để hiểu được các phép suy diễn logic cho các phụ
thuộc hàm, cần tính được F+ từ F
Để khẳng định được X → Y có thuộc F hay không
nếu biết phụ thuộc hàm X → Y và tập phụ thuộc
hàm F.
Đòi hỏi phải có những qui tắc suy diễn cho biết
làm sao có thể suy ra một hay nhiều phụ thuộc
hàm từ các phụ thuộc hàm khác.
Tập các qui tắc này được Armstrong đưa ra năm
1974 và được gọi là hệ luật dẫn Armstrong.
2.4. Hệ luật dẫn Armstrong (tt)
Cho R là lược đồ quan hệ
với U= {A1,..,An} là tập các thuộc tính của nó
và X, Y, Z, W ⊆ U.
Hệ luật dẫn Armstrong:
Phản xạ: Y ⊆ X ⇒ X → Y.
Tăng trưởng: X → Y ⇒ XZ → YZ, với XZ = X∪Z.
Bắc cầu: X → Y, Y → Z ⇒ X → Z.
Các luật bổ sung (chứng minh dựa vào Hệ luật dẫn Armstrong)
Phân rã: X → YZ ⇒ X → Y, X → Z.
Hợp: X → Y, X → Z ⇒ X → YZ.
Giả bắc cầu: X → Y, WY → Z ⇒ WX → Z.
2.4. Hệ luật dẫn Armstrong (tt)
Chứng minh các luật suy dẫn bổ sung:
Phân rã: X → YZ ⇒ X → Y, X → Z
Vì Z YZ nên YZZ (theo luật phản xạ).
Dùng luật bắc cầu cho XYZ và YZZ có XZ.
Tương tự có X → Y
Hợp: X → Y, X → Z ⇒ X → YZ
Từ XY dùng luật tăng trưởng, thêm X có XXY
Từ XZ dùng luật tăng trưởng thêm Y có XYYZ
và cuối cùng dùng luật bắc cầu suy ra vì XXy và XYXZ nên
XYZ.
Giả bắc cầu: X → Y, WY → Z ⇒ WX → Z
Từ XY, dùng luật tăng trưởng, thêm W có WX WY. Dùng luật
bắc cầu cho WX WY và WYZ suy ra WXZ.
Một hệ quả quan trọng của luật tách và luật hợp là nếu X Y
suy ra XAi với mọi AiY
2.4. Hệ luật dẫn Armstrong (tt)
VD: Cho F = {AB → C, C → A }.
CMR: BC → ABC
Ta có:
(1) C → A (giả thiết)
(2) BC → AB (tăng trưởng 1)
(3) AB → C (giả thiết)
(4) AB → ABC (tăng trưởng 3)
(5) BC → ABC (bắc cầu 2 & 4)
2.5. Bao đóng của tập thuộc tính
Làm thế nào để biết một PTH X → Y được
suy diễn từ tập PTH F cho trước?
2.5. Bao đóng của tập thuộc tính
Định nghĩa:
F là tập PTH trên tập thuộc tính U và X ⊆ U
Bao đóng của tập thuộc tính X đối với tập các
PTH F (ký hiệu: X+) là tập tất cả các thuộc tính
A có thể suy dẫn từ X nhờ tập bao đóng của F
(F+)
X+ = {A ∈ U | X → A ∈ F+}
Nhận xét:
X ⊆ X+.
X → Y ∈ F+ ⇔ Y ⊆ X+.
Nếu K là khóa của R thì K+ = U.
2.5. Bao đóng của tập thuộc tính (tt)
Sử dụng X+ để:
Kiểm tra siêu khóa:
• Để kiểm tra K là siêu khóa, tính K+, kiểm tra K+ có
chứa mọi thuộc tính của R?
Kiểm tra các PTH:
• Để kiểm tra phụ thuộc hàm X → Y có thuộc F+
không thì kiểm tra Y ⊆ X+
Tính bao đóng của tập PTH F:
• Với mỗi r ⊆ R, tìm r+
• Với mỗi S ⊆ r+, đưa ra PTH r → S
2.5. Bao đóng của tập thuộc tính (tt)
Thuật toán tính bao đóng của tập các thuộc
tính
Input: U, F và X ⊆ U
Output: X+
Thuật toán:
B1: X0 = X;
B2: Nếu tồn tại Y → Z ∈ F với Y ⊆ Xi, Z Xi thì
Xi+1 = Xi ∪ Z;
Tiếp tục B2
Ngược lại B3
B3: output X+ = Xi
2.5. Bao đóng của tập thuộc tính (tt)
VD: Cho R(U) với U=ABCDEG
F = {AB → C, C → A, BC → D, ACD → B,
D → EG, BE → C, CG → BD, CE → AG}
Tính X+, với:
X=D
X = BD
2.5. Bao đóng của tập thuộc tính (tt)
Xi
Tập PTH
D → EG
X0 = D
Xi+1
DEG
X1= DEG
Vậy D+ = DEG
Xi
Tập PTH
Xi+1
X0= BD
D → EG
BDEG
X1= BDEG
BE → C
BCDEG
X2= BCDEG
C→A
X3= ABCDEG
Vậy BD+ = ABCDEG
ABCDEG
2.6. Phủ và phủ tương đương
Cho F và G là hai tập PTH trên tập thuộc
tính U, ta nói rằng tập PTH F tương đương
với tập phụ thuộc hàm G (ký hiệu: F G)
nếu và chỉ nếu F+ = G+
Nếu F+ = G+ thì ta nói rằng F là phủ
của G và ngược lại G là phủ của F.
2.6. Phủ và phủ tương đương (tt)
Thuật toán xác định F và G có tương
đương không?
B1: Với mỗi PTH X → Y của F ta xác định
xem X → Y có được suy diễn logic từ G
không
B2: Với mỗi PTH X → Y của G ta xác định
xem X → Y có được suy diễn logic từ F
không
Nếu cả 2 bước trên đều đúng thì F G
2.6. Phủ và phủ tương đương (tt)
VD: Cho lược đồ quan hệ R(ABCDE),
2 PTH: F={A → BC, A → D, CD → E}
và G={A → BCE, A → ABD, CD → E}
a. F có tương đương với G không?
b. F có tương đương với G’={A → BCDE} không?
Giải:
a. Ta có AG+ = ABCDE trong G+ có A → BC và A
→ D F ⊆ G+ F+ ⊆ G+ (1)
Lại có AF+ = ABCDE trong F+ có A → BCE và A
→ ABD F+ G F+ G+ (2)
Từ (1) và (2) F+ = G+ F G
b. Do (CD)+ = CD G’+ không chứa PTH CD → E
F không tương đương G’
2.7. Phủ tối thiểu
2.7. Phủ tối thiểu (tt)
Tìm phủ tối thiểu của F:
B1: Tách các PTH có vế phải nhiều hơn 1 thuộc
tính thành PTH có vế phải chỉ có 1 thuộc tính độc
nhất
B2: Loại bỏ thuộc tính dư thừa ở vế trái
X → A, Y ⊆ X, Y dư thừa A (X-{Y})F+
Nếu XY → Z và X → Z thì Y dư thừa ở vế trái của PTH
XY → Z. Vậy còn PTH X → Z
Nếu XY → Z và X → Y thì Y dư thừa ở vế trái của PTH
XY → Z. Vậy còn PTH X → Z, X → Y
B3: Loại bỏ các PTH dư thừa
Áp dụng Hệ luật dẫn Armstrong
X → A dư thừa A (X)+F-{XA}
F X → Y Y ⊆ X+
2.7. Phủ tối thiểu (tt)
VD: Cho R(U), U={A,B,C}
F = {A → BC, B → C, A → B, AB → C}
Tìm phủ tối thiểu F’ của F
Tách các PTH có vế phải nhiều hơn 1 thuộc tính.
F trở thành: {A → B, A → C, B → C, AB → C}
Loại bỏ thuộc tính dư thừa ở vế trái
Có AB → C mà A → C nên B dư thừa ở vế trái của PTH AB → C.
Còn A → C.
Tập F mới là {A → B, A → C, B → C}
Loại bỏ các PTH dư thừa
Có A → B và B → C, theo luật bắc cầu của Hệ luật dẫn
Armstrong A → C
Như vậy PTH A → C trong tập F mới ở B2 là dư thừa
Tập F mới {A → B, B → C}
Vậy F’ = {A → B, B → C}
2.8. Thuật toán xác định khóa
của lược đồ quan hệ
2.8. Thuật toán xác định khóa
của lược đồ quan hệ (tt)
Input: R(U), F
Output: Tập K là khóa của R
Thuật toán:
B1: Đặt K = U = {A1, …, An}
i = 1;
B2: Loại bỏ thuộc tính khỏi K
• Nếu U = (K – {Ai})F+ thì K = K - {Ai}.
• i = i + 1;
• Nếu i > n thì sang B3. Ngược lại, tiếp tục B2.
B3: output K
Chú ý: Khi thay đổi thứ tự loại bỏ các thuộc tính
trong K, ta có thể tìm được các khóa khác
2.8. Thuật toán xác định khóa
của lược đồ quan hệ (tt)
VD 2.8.1: Cho R(U), U = {A, B, C, D, E, F, G}
F = {B → A, D → C, D → BE, DF → G}
Tìm khóa của R.
Giải:
B1:
K = ABCDEFG.
B2:
Loại bỏ A: (BCDEFG)F+ = ABCDEFG ⇒ K = BCDEFG.
Loại bỏ B: (CDEFG)F+ = ABCDEFG ⇒ K = CDEFG.
Loại bỏ C: (DEFG)F+ = ABCDEFG ⇒ K = DEFG.
Loại bỏ D: (EFG)F+ = EFG.
Loại bỏ E: (DFG)F+ = ABCDEFG ⇒ K = DFG.
Loại bỏ F: (DG)F+ = ABCDEG.
Loại bỏ G: (DF)F+ = ABCDEFG ⇒ K = DF.
B3:
Khóa là K = DF.
2.8. Thuật toán xác định khóa
của lược đồ quan hệ (tt)
VD 2.8.2: Cho R(U), U = {C, S, Z}
F = {CS → Z, Z → C}
Tìm khóa của R
B1: K = CSZ.
B2:
Loại bỏ C: (SZ)F+ = CSZ ⇒ K = SZ.
• Loại bỏ S: (Z)F+ = CZ.
• Loại bỏ Z: (S)F+ = S.
K1 = SZ
Loại bỏ S: (CZ)F+ = CZ.
• Loại bỏ C: (Z)F+ = CZ.
• Loại bỏ Z: (C)F+ = C.
Loại bỏ Z: (CS)F+ = CSZ ⇒ K = CS.
• Loại bỏ C: (S)F+ = S.
• Loại bỏ S: (C)F+ = C.
K2 = CS
B3: LĐQH R có 2 khóa là K1 = SZ và K2 = CS.
2.8. Thuật toán xác định khóa
của lược đồ quan hệ (tt)
Thuật toán cơ bản tìm tất cả các khóa:
B1: Xác định tất cả các tập con khác rỗng của U. Kết
quả tìm được giả sử là các tập thuộc tính X1, X2,…
…,X2n-1
B2: Tìm bao đóng của Xi
B3: Siêu khóa là các Xi có bao đóng đúng bằng U.
Giả sử ta đã tìm được các siêu khóa là S = {S1, S2,…
…,Sm}
B4: Xây dựng tập chứa tất cả các khóa của R từ tập
S bằng cách xét mọi Si, Sj con của S (i j),
nếu Si ⊆ Sj thì ta loại Sj.
Kết quả còn lại của S chính là tập tất cả các khóa cần
tìm.
2.8. Thuật toán xác định khóa
của lược đồ quan hệ (tt)
VD 2.8.2: Cho R(U), U = {C, S, Z}
F = {CS → Z, Z → C}
Tìm khóa của R
Xi
Xi+
C
C
S
S
Z
CZ
CS
CSZ
CZ
CZ
SZ
CSZ
Siêu khóa
Khóa
CS
CS
CSZ
SZ
SZ
CSZ
CSZ
Vậy LĐQH R có 2 khóa là K1 = SZ và K2 = CS
2.8. Thuật toán xác định khóa
của lược đồ quan hệ (tt)
Một số khái niệm:
Tập thuộc tính nguồn (TN): chứa tất cả các thuộc tính
xuất hiện ở vế trái và không xuất hiện ở vế phải của các
PTH; đồng thời chứa các thuộc tính không xuất hiện ở
cả vế trái lẫn vế phải của các PTH.
Tập thuộc tính đích (TD): chứa tất cả các thuộc tính
xuất hiện ở vế phải và không xuất hiện ở vế trái của các
PTH
Tập thuộc tính trung gian (TG): chứa các thuộc tính xuất
hiện ở cả vế trái lẫn vế phải của các PTH.
Hệ quả:
Nếu K là khóa của R thì TN ⊆ K và TD K =
2.8. Thuật toán xác định khóa
của lược đồ quan hệ (tt)
Thuật toán cải tiến bản tìm tất cả các khóa:
B1: Tạo tập thuộc tính nguồn TN, tập thuộc tính trung
gian TG
B2: Nếu TG = thì LĐQH R chỉ có một khóa K = TN
Ngược lại, thực hiện B3
B3: Tìm tất cả các tập con Xi của tập thuộc tính trung
gian TG
B4: Tìm các siêu khóa Si
Nếu (TN Xi)+ = U thì Si = TN Xi
B5: Tìm khóa bằng cách loại bỏ các siêu khóa không
tối thiểu
Si, Sj S (i j), nếu Si ⊆ Sj thì ta loại Sj khỏi tập siêu
khóa S. Kết quả còn lại của S chính là tập tất cả các
khóa cần tìm.
2.8. Thuật toán xác định khóa
của lược đồ quan hệ (tt)
VD 2.8.2: Cho R(U), U = {C, S, Z}
F = {CS → Z, Z → C}
Tìm khóa của R
Giải:
TN = {S}; TG = {C,Z}
Gọi Xi là các tập con của tập TG
Xi
TN Xi
(TN Xi) +
Siêu
khóa
Khóa
S
S
C
CS
CSZ
CS
CS
Z
SZ
CSZ
SZ
SZ
CZ
CSZ
CSZ
CSZ
Vậy LĐQH R có 2 khóa là K1 = SZ và K2 = CS
LOGO