Bài giảng Hệ quản trị cơ sở dữ liệu

CHƯƠNG 10: PHỤ THUỘC HÀM (Functional Dependencies)

Phụ thuộc hàm (FD)

• Định nghĩa: Cho một lược đồ quan hệ gồm n

thuộc tính: Q(A1, A2,…, An)

– X, Y là hai tập con của Q+={A1, A2,…, An}.

– r là một quan hệ trên Q.

– t1, t2 là hai bộ bất kỳ của r.

ộ ụ ữ ệ

ượ ư ị ộ Ph thu c hàm gi a hai thu c tính X và Y ký hi u là X Y đ c đ nh nghĩa nh sau:

(t1.X = t2.X (cid:0)

X Y (cid:0)

t1.Y = t2.Y)

ụ ộ ị (Ta nói X xác đ nh Y hay Y ph thu c hàm vào X)

Phụ thuộc hàm (FD)

• Ví dụ: cho lược đồ quan hệ: Q(A, B, C, D, E)

A

B

C

D

E

I. AB  C

1

2

3

4

5

II.

B  D (T)

III.

DE  A (T)

1

4

3

4

5

1

2

4

1

Phụ thuộc hàm (FD)

• Phụ thuộc hàm hiễn nhiên:

Nếu X (cid:0)

Y thì X Y.

– Với r là quan hệ bất kỳ, F là tập phụ thuộc hàm thỏa

trên r, ta luôn có

F (cid:0) {các phụ thuộc hàm hiển nhiên}

Phụ thuộc hàm (FD)

• Thuật toán Satifies: Cho quan hệ r và X, Y là hai tập con của Q+, Thuật toán SATIFIES sẽ trả về trị true nếu X  Y ngược lại là false

• SATIFIES(r,X,Y)

– Sắp các bộ của quan hệ r theo X để các giá trị giống

– Nếu tập các bộ cùng giá trị trên X cho các giá trị trên Y

nhau trên X nhóm lại với nhau

giống nhau thì trả về true ngược lại là False

Phụ thuộc hàm (FD)

• Ví dụ: SATIFIES(phanCong,MAYBAY,GIOKH)

Phụ thuộc hàm (FD)

• Cách tìm tất cả tập con của Q+:

– Số tập con có thể có của Q+ = {A ,A ,...,A } là 2n – Số phụ thuộc hàm có thể có: 2nx2n

(cid:0)

ụ

Ví d : Q+=(A, B, C, D)

ABC

ABD

ố ậ

• S t p con: 24=16

ố

• S PTH:

ABC

=24x24=256

Hệ luật dẫn Armstrong

• Phụ thuộc hàm được suy diễn logic từ F

– Phụ thuộc hàm X (cid:0) quan hệ r bất kỳ thỏa mãn tất cả các phụ thuộc hàm của F thì cũng thỏa phụ thuộc hàm X (cid:0)

Y được suy diễn logic từ F nếu một

• Bao đóng của F (F+)

– Bao đóng của F ký hiệu F+ là tập tất cả các phụ thuộc

Y. Ký hiệu F|= X (cid:0) Y.

hàm được suy diễn logic từ F.

Hệ luật dẫn Armstrong

• Các tính chất của tập F+

– Tính phản xạ: F (cid:0)

– Tính đơn điệu: Nếu F (cid:0)

F+

– Tính lũy đẳng: (F+)+ = F+.

– Gọi G là tập tất cả các phụ thuộc hàm có thể có của r,

G thì F+ (cid:0) G+

‑ phần phụ của F ký hiệu F = G - F+

Hệ luật dẫn Armstrong

• Hệ luật dẫn Amstrong:

– Cho X,Y,Z,W là tập con của Q+ – r là quan hệ bất kỳ của Q. – Ba luật của tiên đề Amstrong: 1. Luật phản xạ (reflexive rule):

(cid:0)

ế

N u Y

Y

X thì X (cid:0) 2. Luật tăng trưởng(augmentation rule):

(cid:0) ế N u Z Q và X (cid:0) Y thì XZ (cid:0) YZ

(cid:0)

5. Luật bắc cầu (Transivity Rule) Y và Y (cid:0) Z

Z thì X (cid:0) ế N u X

Hệ luật dẫn Armstrong

– Ba hệ quả của tiên đề Amstrong:

(cid:0)

1. Luật hợp (Union Rule) Z thì X (cid:0) Y và X (cid:0)

ế N u X YZ

2. Luật bắc cầu giả (Pseudotransivity Rule)

(cid:0) ế N u X Y và WY (cid:0) Z thì XW (cid:0) Z

3. Luật phân rã (Decomposition Rule)

N u ế X  YZ thì X  Y and X  Z

Bao đóng của tập thuộc tính X (closures of attribute sets)

• Định nghĩa: ồ - Q là l - r là m t quan h trên Q, - F là t p các ph thu c hàm trong Q. ậ - X, Ai là các t p con c a Q+

ượ ộ ậ ệ c đ quan h . ệ ụ

ố ớ ệ

ị ủ ậ c đ nh nghĩa: ộ X+=(cid:0) Ai

ễ ừ ượ ộ c suy di n t ờ ệ F nh h

ề ộ ủ Bao đóng c a t p thu c tính X đ i v i F ký hi u là X+ ượ đ v i Xớ (cid:0) Ai là ph thu c hàm đ ụ tiên đ Armstrong

Bao đóng của tập thuộc tính X (closures of attribute sets)

• Thuật toán tìm bao đóng:

– Tính liên tiếp tập các tập thuộc tính X0,X1,X2,... theo

– Bước 1: X0 = X – Bước 2: lần lượt xét các phụ thuộc hàm của F

Xi thì Xi+1 = Xi (cid:0) Z

phương pháp sau:

ộ

(cid:0) Z có Y (cid:0) • N u Yế ụ ạ • Lo i ph thu c hàm Y

Z kh i F ỏ

– Bước 3: Nếu ở bước 2 không tính được Xi+1 thì Xi

(cid:0)

chính là bao đóng của X – Ngược lại lặp lại bước 2

Bao đóng của tập thuộc tính X (closures of attribute sets)

Ví dụ 1: Cho lược đồ quan hệ Q(A,B,C,D,E,G,H) và tập phụ thuộc hàm

C; AC(cid:0) D}. Tìm bao đóng

{D}

{C,E} {H}

F={B(cid:0) A; DA(cid:0) CE; D(cid:0) H; GH(cid:0) ủ c a X = {AC} trên F § X(0) = {A,C} , {A,C}(cid:0) § X(1) = {A,C,D}, {A, D}(cid:0) § X(2) = {A,C,D,E}, {D}(cid:0) § X(3) = {A,C,D,E,H} § X+= X(3) Cho X = {B, D} >X+?

Bao đóng của tập thuộc tính X (closures of attribute sets)

• Ví du 2: cho lược đồ quan hệ: Q(A,B,C,D,E,G)

F = { f1: A → C;

f2: A → EG;

f3: B → D;

– Tìm bao đóng của X+ và Y+ của

f4: G → E}

– Kết quả : X+ = {ABCDEG} , Y+ = {CGDE}

X = {A,B}; Y = {C,G,D}

Sử dụng bao đóng của tập thuộc tính

• Kiểm tra siêu khóa (Testing for superkey)

– Để kiểm tra X có phải là siêu khóa: tính X+, nếu X+ chứa tất cả các thuộc tính của R thì X là siêu khóa.

– X là khóa dự tuyển (candidate key) nếu không tập con nào trong số các tập con của nó là khóa. • Kiểm tra một phụ thuộc hàm XY có được

suy dẫn từ F.

Sử dụng bao đóng của tập thuộc tính

• Kiểm tra 2 tập phụ thuộc hàm tương đương

ụ

ộ

(cid:0)

F+=G+ – Với mỗi phụ thuộc hàm Y(cid:0) Z trong F ậ • Tính Y+ trên t p ph thu c hàm G ế • N u Z

Y+ thì Y(cid:0) Z trong G+ và ng

ượ ạ i c l

Phụ thuộc hàm dư thừa

• Tập các phụ thuộc hàm có thể là dư thừa vì

chúng có thể suy diễn từ các FDs khác. – Ví dụ: A(cid:0) C là dư thừa đối với F: (A(cid:0) B, B(cid:0) C, A(cid:0)

• Một phần của phụ thuộc hàm cũng có thể dư

thừa. – Ví dụ: F=(A(cid:0)

B, B(cid:0) C, A(cid:0) C,D)

có thể được viết lại:

F=(A(cid:0) B, B(cid:0) C, A(cid:0) D)

Bao đóng của tập phụ thuộc hàm

• Bao đóng của F ký hiệu F+ là tập tất cả các phụ

thuộc hàm được suy diễn logic từ F.

• Thuật toán tìm bao đóng F+

– Bước 1: Tìm tất cả tập con của Q+ – Bước 2: Tìm tất cả các phụ thuộc hàm có thể có của Q. – Bước 3: Tìm bao đóng của tất cả tập con của Q. – Bước 4: Dựa vào bao đóng của tất cả các tập con đã

tìm để xác định phụ thuộc hàm nào thuộc F+

Bao đóng của tập phụ thuộc hàm

• Ví dụ: Q(A,B,C) F = {AB (cid:0)

C,C (cid:0)

B} F+ ?

– B1: tìm tất cả tập con của các thuộc tính Q+

(cid:0) A B C

(cid:0) {A} {B} {C}

ậ

ả

ộ

– B2: Tìm bao đóng của tất c các t p con thu c tính

{A,B} {A,C}

{B,C}

• A+ = A • B+ = B • C+ = BC • AC+ = ABC • AB+ = ABC • BC+ = BC

{A,B,C}

Bao đóng của tập phụ thuộc hàm

• Tìm tất cả các phụ thuộc hàm có thể có:

A(cid:0) B A(cid:0) BC B(cid:0) C

AB(cid:0) C(cid:0) F

C(cid:0) A C(cid:0) BC(cid:0) F+ AC(cid:0) BC(cid:0) F+ BC(cid:0) AC

A(cid:0) AB A(cid:0) ABC B(cid:0) AC AB(cid:0) AC(cid:0) F+ C(cid:0) B(cid:0) F C(cid:0) ABC AC(cid:0) ABC(cid:0) F+BC(cid:0) ABC

A(cid:0) C B(cid:0) A B(cid:0) BC AB(cid:0) BC(cid:0) F+ C(cid:0) AB AC(cid:0) B(cid:0) F+

BC(cid:0) A

A(cid:0) AC B(cid:0) AB B(cid:0) ABC

C(cid:0) AC

BC(cid:0) AB

AB(cid:0) ABC(cid:0) F +

AC(cid:0) AB(cid:0) F +

• Kết quả:

F+={AB(cid:0) C, AB(cid:0) AC,AB(cid:0) BC, AB(cid:0) ABC,C(cid:0) B,C(cid:0) BC,AC(cid:0) B, AC(cid:0) AB,AC(cid:0) BC, AC(cid:0) ABC}

Bao đóng của tập phụ thuộc hàm

• Thuật toán tìm F+ cải tiến:

– Bước 1: Tìm tất cả tập con của Q+

– Bước 2: Tìm bao đóng của tất cả tập con của Q+

– Bước 3: Dựa vào bao đóng của các tập con đã tìm để

suy ra các phụ thuộc hàm thuộc F+

Bao đóng của tập phụ thuộc hàm

• Ví dụ:

– A+ = A chỉ gồm các phụ thuộc hàm hiển nhiên

– {AB}+ = ABC cho các phụ thuộc hàm không hiển nhiên sau: AB(cid:0) C, AB (cid:0) – Tìm tất cả các tập con của {ABC} rồi bỏ các tập con của

BC, AB (cid:0) AC, AB (cid:0) ABC

ủ

ậ

• Các t p con c a {ABC} là:

(cid:0)

,{A},{B},{AB},{C},{AC},{BC},{ABC}

ỏ

ậ

• B các t p con c a {AB} là:

(cid:0)

{AB}

ủ ,{A},{B},{AB},{C},{AC},{BC},{ABC}

– Các tập còn lại chính là vế phải của phụ thuộc hàm có

vế trái là AB

Bao đóng của tập phụ thuộc hàm

• 1/ Cho quan hệ sau:

ụ

ỏ

ộ

– r( A B C D E) – a1 b1 c1 d1 e1 – a1 b2 c2 d2 d1 – a2 b1 c3 d3 e1 – a2 b1 c4 d3 e1 – a3 b2 c5 d1 e1 Ph thu c hàm nào sau đây th a r: A(cid:0) D; AB(cid:0) D; C(cid:0) BDE; E(cid:0) A; A(cid:0) E

Bao đóng của tập phụ thuộc hàm

1. Cho Q+={ABC}.

– a) Tìm tất các các tập con của Q – b) Tìm tất cả các phụ thuộc hàm có thể có của Q

2. Cho F = {AB(cid:0) C, B(cid:0) D, C(cid:0) E, CE(cid:0) GH, G(cid:0) A}

(không liệt kê phụ thuộc hàm hiển nhiên)

– a) Hãy chứng tỏ phụ thuộc hàm AB(cid:0) E,AB (cid:0) suy diễn từ F nhờ luật dẫn Armstrong

– b) Tìm bao đóng của AB(với bài toán không nói gì về

G được

lược đồ quan hệ Q ta ngầm hiểu Q+ là tập thuộc tính có trong F nghĩa là Q+={ABCEGH})

Bao đóng của tập phụ thuộc hàm

1. Cho F = {A(cid:0) D,AB (cid:0)

DE,CE (cid:0)

G,E (cid:0)

H}. Hãy

tìm bao đóng của AB.

2. Cho F={AB (cid:0)

E, AG (cid:0)

I, BE (cid:0)

I, E (cid:0)

G, GI (cid:0)

GH được suy diễn

H}. – Hãy chứng tỏ phụ thuộc hàm AB (cid:0) từ F nhờ luật dẫn Armstrong

– Tìm bao đóng của {AB}

3. Cho F={A (cid:0)

D, AB (cid:0)

E, BI (cid:0)

E, C (cid:0)

I, E (cid:0)

C}

tìm bao đóng của {AE}+

Phụ thuộc hàm tương đương

• Định Nghĩa: Hai tập phụ thuộc hàm F và G là

tương đương (Equivalent) nếu F+ = G+ – ký hiệu F = G.

• Thuật toán xác định F và G có tương đương

không – Bước 1: Với mỗi phụ thuộc hàm X(cid:0) Y của F ta xác định xem X(cid:0) Y có là thành viên của G không – Bước 2: Với mỗi phụ thuộc hàm X(cid:0) Y của G ta xác định xem X(cid:0) Y có là thành viên của F không – Nếu cả hai bước trên đều đúng thì F (cid:0) G

Phụ thuộc hàm tương đương

• Ví dụ: Cho lược đồ quan hệ Q(ABCE) hai tập phụ

thuộc hàm:

– F={A(cid:0) BC,A(cid:0) D,C(cid:0) E}

– G = {A(cid:0) BCE,A(cid:0) ABD,C(cid:0) E}

ươ ươ ớ a) F có t ng đ ng v i G không?

ươ ươ ớ b) F có t ng đ ng v i G’={A (cid:0) BCE} không?

Phụ thuộc hàm tương đương

a) Tính A+ dựa trên tập G

• A+=ABCE (cid:0) (cid:0)

trong G+ có A(cid:0) BC và A(cid:0) D F (cid:0)

G+ (1).

G+ (cid:0)

F+ (cid:0)

Tính A+ dựa trên tập F

• A+=ABCE (cid:0) (cid:0)

G+ (2)

G (cid:0)

trong F+ có A(cid:0) BCE và A(cid:0) ABD F+ (cid:0) F+ = G+ (cid:0)

F+ (cid:0) G.

• (1) và(2) (cid:0)

F (cid:0) G’+ không chứa phụ thuộc hàm C(cid:0) E (cid:0)

b) Do = C (cid:0)

F không tương đương với G’

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

• Phụ thuộc hàm có vế trái dư thừa:

– F là tập các phụ thuộc hàm trên lược đồ quan

Y có vế trái dư thừa nếu có

F-{Z (cid:0)

Y}(cid:0)

{(Z-A) (cid:0)

Y}

F-{AB(cid:0) C}(cid:0)

hệ Q. – Z(cid:0) Y(cid:0) F. – Phụ thuộc hàm Z (cid:0) một A(cid:0) Z sao cho: F (cid:0) Ví d 1ụ : Q(A,B,C), F={AB(cid:0) C; B(cid:0) C} {(AB-A)(cid:0) C}={B(cid:0) C} F (cid:0) ụ

ộ

ầ

ủ

C: là ph thu c hàm không đ y đ

ụ

ầ

ủ

AB (cid:0) B (cid:0)

ộ C :là ph thu c hàm đ y đ

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

D}. Phụ thuộc hàm AB (cid:0)

D có vế trái dư

Ví dụ 2: cho tập phụ thuộc hàm F = {A (cid:0) BC , B (cid:0) C, AB (cid:0) thừa B vì:

F (cid:0)

F – {AB (cid:0)

D} (cid:0) {A (cid:0)

= {A (cid:0)

BC, B (cid:0)

C, A (cid:0)

• F là tập phụ thuộc hàm có vế trái không dư thừa nếu F không chứa phụ thuộc hàm có vế trái dư thừa.

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

• Thuật toán loại các phụ thuộc hàm có vế trái

của X, nếu X’ (cid:0) Y (cid:0) F+ thì thay X

dư thừa: – Xét lần lượt các phụ thuộc hàm X (cid:0) Y trong F – Với mọi tập con X’≠ (cid:0) (cid:0) Y bằng X’ (cid:0) Y .

D},

Ví dụ 3: F = {A (cid:0) BC , B (cid:0) phụ thuộc hàm AB (cid:0) A (cid:0) D(cid:0) F+

(cid:0) C, AB (cid:0) D có A+=ABCD(cid:0) D bằng A (cid:0) D

(cid:0) Trong F ta thay AB (cid:0) F = {A (cid:0) BC,B (cid:0) C, A (cid:0) D}

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

• Phụ thuộc hàm dư thừa:

– F là tập phụ thuộc hàm không dư thừa nếu không tồn tại F’(cid:0) F. Ngược lại F là tập phụ thuộc hàm dư thừa. Ví d : ụ Cho F = {A (cid:0)

F sao cho F’(cid:0)

D, AB (cid:0) BC, B (cid:0) D}

(cid:0) ư ừ thì F d th a vì F F’= {A(cid:0) BC, B(cid:0) D}

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

• Tập phụ thuộc hàm tối thiểu (minimal cover)

– F được gọi là một tập phụ thuộc hàm tối thiểu (hay phủ

tối thiểu) nếu F thỏa đồng thời ba điều kiện sau: ư ừ ộ ế ế

§ F là t p ph thu c hàm có v trái không d th a ộ ả § F là t p ph thu c hàm có v ph i m t thu c tính. ư ừ § F là t p ph thu c hàm không d th a

ụ ụ ụ ậ ậ ậ ộ ộ ộ

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

• Thuật toán tìm phủ tối thiểu của một tập phụ

thuộc hàm – Bước 1: Loại bỏ các phụ thuộc hàm có vế trái dư

– Bước 2: Tách các phụ thuộc hàm có vế phải nhiều hơn một thuộc tính thành các phụ thuộc hàm có vế phải một thuộc tính.

– Bước 3: Loại bỏ các phụ thuộc hàm dư thừa.

thừa.

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

• Ví dụ 1: Cho lược đồ quan hệ Q(A,B,C,D) và D}. Tìm

C, C (cid:0)

CD là phụ thuộc hàm có vế trái

tập phụ thuộc F ={AB (cid:0) CD, B (cid:0) phủ tối thiểu của F. – Bước 1: AB (cid:0) dư thừa? • Xét B (cid:0)

CD(cid:0) F+ ? B (cid:0) Tính B+ =BCD (cid:0) CD (cid:0) F+

(cid:0) ư ừ ế

ậ • V y AB F={B (cid:0) A (cid:0) CD là ph thu c hàm có v trái d th a CD; B (cid:0) D} ụ ộ C; C (cid:0)

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

– Bước 2: tách các phụ thuộc hàm có vế phải nhiều hơn 1 thuộc tính thành các phụ thuộc hàm có vế phải 1 thuộc tính

– Bước 3:

F={B(cid:0) D; B (cid:0) C; C (cid:0) D}=F1tt

ư ừ ụ ộ C là ph thu c hàm d th a?

Trong F1tt, B (cid:0) C (cid:0) B (cid:0) G+ ?

(cid:0) C}={B (cid:0) D;C (cid:0) D}

ớ v i G = F1tt {B BG+=BD (cid:0) C (cid:0) G+

(cid:0) ư ừ B (cid:0) trong F1tt B (cid:0) C không d th a.

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

D là phụ thuộc hàm dư

Trong F1tt,B (cid:0) thừa? B (cid:0) D (cid:0)

G+ ?

(cid:0)

C; C (cid:0)

D}

D}={B (cid:0) D (cid:0) G+

(cid:0)

ớ v i G = F1tt {B B (cid:0) BG+=BC D(cid:0) trong F1tt, B (cid:0)

ư ừ D d th a.

– Kết quả của bước 3 cho phủ tối thiểu: C;C (cid:0)

D}=Ftt

F={B (cid:0)

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

• Ví dụ 6: Cho lược đồ quan hệ Q(A,B,C,D) và tập

A;

D;

B;

phụ thuộc F như sau: F = {A (cid:0) C; C (cid:0) CB (cid:0) AD (cid:0) CD (cid:0) AB (cid:0)

D}

• Hãy tìm phủ tối thiểu của F

Phủ tối thiểu của tập phụ thuộc hàm (minimal cover)

• kết quả:

C;

A;

B;

Ftt = {A (cid:0) C (cid:0) C,D (cid:0) A,B (cid:0)

D}

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

• Định Nghĩa: Cho lược đồ quan hệ Q(A1,A2,

…,An)

ủ

ậ

ộ • Q+ là t p thu c tính c a Q.

ậ

ụ

ộ

ậ

• F là t p ph thu c hàm trên Q. ủ • K là t p con c a Q+ K là một khóa của Q nếu:

• K+ = Q+

(cid:0)

ồ ạ

• Không t n t

i K'

K sao cho K’+= Q+

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

– Tập thuộc tính S được gọi là siêu khóa nếu S (cid:0) K

– Thuộc tính A được gọi là thuộc tính khóa nếu A(cid:0) K với K là khóa bất kỳ của Q. Ngược lại A được gọi là thuộc tính không khóa.

– Một lược đồ quan hệ có thể có nhiều khóa và tập thuộc tính không khóa cũng có thể bằng rỗng.

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

• Thuật toán tìm một khóa của một lược đồ quan

ế

ố

ủ ứ ự

ể

ổ

ồ ạ ỏ

ầ ử ủ

hệ Q – Bước 1: gán K = Q+ – Bước 2: A là một thuộc tính của K, đặt K’ = K - A. Nếu K’+= Q+ thì gán K = K' thực hiện lại bước 2 ế • N u mu n tìm các khóa khác (n u có) c a ệ ượ l c đ quan h , ta có th thay đ i th t c a K. lo i b các ph n t

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

• Ví dụ: cho lược đồ quan hệ Q và tập phụ thuộc

B, BC (cid:0) DE} tìm khóa K

hàm F như sau: ‒ Q(A,B,C,D,E) ‒ F={AB(cid:0) C, AC (cid:0) B1: K=Q+ (cid:0)

K=ABCDE

B2:(K\A)+ (cid:0) (BCDE)+=BCDE ≠ Q+ (cid:0) K=ABCDE

B3:(K\B)+ (cid:0) (ACDE)+= ABCDE = Q+ (cid:0) K=ACDE

B4: (K\C)+ (cid:0) (ADE)+ = ADE ≠ Q+ (cid:0) K=ACDE

B5: (K\D)+ (cid:0) (ACE)+ = ACEBD=Q+ (cid:0) K=ACE

B6: (K\E)+ (cid:0) (AC)+ = ACBDE =Q+ (cid:0) K=AC

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

• Ví dụ: cho lược đồ quan hệQ(ABCDEGHI) và tập

thuộc tính F={AC(cid:0)

B;

AC;

D;

BCG;

BI (cid:0) ABC (cid:0) H (cid:0) I; ACE (cid:0) CG (cid:0)

AE}

– Tìm K – Đáp án: K=CGH

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

• Thuật toán tìm tất cả khóa của lược đồ quan

hệ: – Bước 1: Xác định tất cả các tập con khác rỗng

của Q+={X1, X2, …,X2n-1 }

– Bước 2: Tìm bao đóng của các Xi – Bước 3: Siêu khóa là các Xi có Xi+= Q+

s ta đã có các siêu khóa là S = {S1,S2,

ả ử • Gi …,Sm}

– Bước 4: xét mọi Si, Sj con của S (i ≠ j), nếu Si (cid:0) Sj thì loại Sj (i,j=1..n), 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.

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

• Ví dụ: Tìm tất cả các khóa của lược đồ quan hệ

và tập phụ thuộc hàm như sau:

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

• Thuật toán (cải tiến) tìm tất cả khóa của một

lược đồ quan hệ – Bước1: tạo tập thuộc tính nguồn TN, tập thuộc

tính trung gian TG

– Bước2:

(cid:0)

ế

ượ

ồ

ộ

ỉ

ệ c đ quan h ch có m t

ướ

thì l ế i Qua b

ượ ạ c l

• N u TG = khóa K = TN k t thúc c 3 • Ng – Bước3: tìm tất cả các tập con Xi của tập trung

gian TG

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

– Bước 4: tìm các siêu khóa Si bằng cách (cid:0) Xi

• if (TN (cid:0) • Si = TN (cid:0) Xi

– Bước 5: tìm khóa bằng cách loại bỏ các siêu

Xi)+ = Q+ then

khóa không tối thiểu

Si, Sj (cid:0) S

ạ

• (cid:0) • if Si (cid:0) Sj then Lo i Sj ra kh i T p siêu khóa S i chính là t p khóa c n tìm. • S còn l

ỏ ậ ầ ạ ậ

KHÓA CỦA LƯỢC ĐỒ QUAN HỆ (Key)

Ví dụ: cho lược đồ quan hệ Q(CSZ) và tập phụ thuộc hàm F={CS (cid:0) Z; Z (cid:0) C}. Áp dụng thuật toán cải tiến:

– TN = {S}; TG = {C,Z} – Gọi Xi là các tập con của tập TG:

Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 8: Phụ thuộc hàm

CHƯƠNG 10: PHỤ THUỘC HÀM (Functional Dependencies)

Phụ thuộc hàm (FD)

thuộc tính: Q(A1, A2,…, An)

(t1.X = t2.X (cid:0)

X Y (cid:0)

Phụ thuộc hàm (FD)

A

B

C

D

E

1

2

3

4

5

B  D (T)

DE  A (T)

1

4

3

4

5

1

2

4

4

1

Phụ thuộc hàm (FD)

Nếu X (cid:0)

Y thì X Y.

Phụ thuộc hàm (FD)

Phụ thuộc hàm (FD)

Phụ thuộc hàm (FD)

ụ

Ví d : Q+=(A, B, C, D)

ố ậ

ố

=24x24=256

Hệ luật dẫn Armstrong

Hệ luật dẫn Armstrong

Hệ luật dẫn Armstrong

– Cho X,Y,Z,W là tập con của Q+ – r là quan hệ bất kỳ của Q. – Ba luật của tiên đề Amstrong: 1. Luật phản xạ (reflexive rule):

ế

N u Y

Y

X thì X (cid:0) 2. Luật tăng trưởng(augmentation rule):

5. Luật bắc cầu (Transivity Rule) Y và Y (cid:0) Z

Hệ luật dẫn Armstrong

1. Luật hợp (Union Rule) Z thì X (cid:0) Y và X (cid:0)

2. Luật bắc cầu giả (Pseudotransivity Rule)

3. Luật phân rã (Decomposition Rule)

Bao đóng của tập thuộc tính X (closures of attribute sets)

Bao đóng của tập thuộc tính X (closures of attribute sets)

Bao đóng của tập thuộc tính X (closures of attribute sets)

Ví dụ 1: Cho lược đồ quan hệ Q(A,B,C,D,E,G,H) và tập phụ thuộc hàm

{D}

{C,E} {H}

Bao đóng của tập thuộc tính X (closures of attribute sets)

Sử dụng bao đóng của tập thuộc tính

suy dẫn từ F.

Sử dụng bao đóng của tập thuộc tính

ụ

ộ

F+=G+ – Với mỗi phụ thuộc hàm Y(cid:0) Z trong F ậ • Tính Y+ trên t p ph thu c hàm G ế • N u Z

Y+ thì Y(cid:0) Z trong G+ và ng

ượ ạ i c l

Phụ thuộc hàm dư thừa

chúng có thể suy diễn từ các FDs khác. – Ví dụ: A(cid:0) C là dư thừa đối với F: (A(cid:0) B, B(cid:0) C, A(cid:0)

thừa. – Ví dụ: F=(A(cid:0)

Bao đóng của tập phụ thuộc hàm

thuộc hàm được suy diễn logic từ F.

Bao đóng của tập phụ thuộc hàm

C,C (cid:0)

B} F+ ?

Bao đóng của tập phụ thuộc hàm

A(cid:0) B A(cid:0) BC B(cid:0) C

AB(cid:0) C(cid:0) F

C(cid:0) A C(cid:0) BC(cid:0) F+ AC(cid:0) BC(cid:0) F+ BC(cid:0) AC