Cộng đồng chia sẻ tri thức Doc24.vn

Chương 4: PTH - Cô Nguyễn Thị Thu Hiếu

580e7c866c3b0a90dc18c5d3f307fbe9
Gửi bởi: Nguyễn Thị Thu Hiếu vào ngày 2020-09-10 03:04:58 || Kiểu file: PDF Lượt xem: 133 | Lượt Download: 0 | File size: 0.7211 Mb

Nội dung tài liệu Xem trước tài liệu

Link tài liệu:
Tải xuống

Các tài liệu liên quan

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 YZZ (theo luật phản xạ).
Dùng luật bắc cầu cho XYZ và YZZ có XZ.
Tương tự có X → Y
 Hợp: X → Y, X → Z ⇒ X → YZ
Từ XY dùng luật tăng trưởng, thêm X có XXY
Từ XZ dùng luật tăng trưởng thêm Y có XYYZ
và cuối cùng dùng luật bắc cầu suy ra vì XXy và XYXZ nên
XYZ.
 Giả bắc cầu: X → Y, WY → Z ⇒ WX → Z
Từ XY, 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à WYZ suy ra WXZ.
 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 XAi với mọi AiY

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-{XA}
 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