Phụ thuộc hàm: Bài giảng Hệ cơ sở dữ liệu

ươ

ng 9

Ụ Ộ

Ph thu c hàm (Functional Dependency)

ầ

Tr n Thi Kim Chi

Nội dung

ượ ồ

ậ

ả

ệ

c đ quan h

Trần Thi Kim Chi

n D th a d li u ư ừ ữ ệ n Ph thu c hàm ộ ụ n H tiên đ Amstrong ề ệ n Bao đóng c a t p ph thu c hàm ụ ủ ậ ộ n Bao đóng c a t p thu c tính ộ ủ ậ n Gi i thu t Tìm khóa cho l

Dư thừa dữ liệu - (Data redundancy)

n M c đích c a thi

ụ ế ế ộ

t k CSDL là gom các thu c tính thành ể ư ừ ữ ệ ủ ệ ả các quan h sao cho gi m thi u d th a d li u

ả ủ ư ừ ữ ệ

ậ

n H u qu c a d th a d li u: ậ ¨ Lãng phí không gian đĩa ¨ Các b t th ườ ậ ấ ng khi c p nh t n Ba lo i b t th ườ ạ ấ ng: ¨ B t th ấ ¨ B t th ấ ¨ B t th ấ

Trần Thi Kim Chi

ườ ườ ườ ng khi thêm vào ỏ ng khi xóa b ử ổ ng khi s a đ i

Ví dụ MaSv HoTen MaMH

TenMH

SoTC

Điem

1111 1111 5556 5556 9876

Mai Mai Long Long Son

CSDL KTMT CSDL KTMT CSDL

Cơ Sở Dữ Liệu Kiến Trúc Máy Tính Cơ Sở Dữ Liệu Kiến Trúc Máy Tính Cơ Sở Dữ Liệu

4 4 4 4 4

9 8 8 8 7

 MaSv + MaMH

n Khóa chính c a b ng KETQUA? ủ ả n Các b t th ng:

ị

ấ ư ừ ữ ệ (Redundancy): Thông tin cá nhân b trùng

ườ ¨ D th a d li u

l p ặ

ứ

ế

ả

ấ

¨ Không nhất quán (Inconsistency): N u đ i b n ghi th nh t ấ ổ ả ữ ệ  b n ghi 2 tên Mai thành Nga  Không nh t quán d li u ẫ v n tên Mai

ế

ổ

ể ạ

ườ

¨ Dị thường khi thêm bộ (Insertion anomalies): N u b sung  không th t o

thêm ng ả b n ghi m i đ

ớ Trần Thi Kim Chi

ả

i m i tên là Hùng nh ng ch a thi ớ ượ  vì khóa chính là MaSv + MaMH ế ¨ Dị thường khi xoá bộ (Deletion anomalies): N u xóa b n

ề

ghi cu i ố  thì thông tin v môn CSDL cũng m t ấ

Phụ thuộc hàm (Functional Dependency)

ả ố ộ m i liên h gi a các thu c tính

n Ph thu c hàm mô t ộ n D a vào ph thu c hàm đ thi

ể ộ ạ ỏ ụ ệ ữ ế ế ạ t k l i CSDL, lo i b các

n Có th bi u di n RBTV b ng ph thu c hàm. n

ụ ằ ộ

ủ ế ả ộ ụ ự ư ừ ữ ệ d th a d li u ể ể ễ ụ ụ ng d ng c a ph thu c hàm là gi i quy t các bài toán

Ứ v :ề

ủ ố

Trần Thi Kim Chi

ể i thi u. ơ ở ữ ệ Tìm khóa. Tìm ph t ẩ Chu n hoá c s d li u.

Phụ thuộc hàm (Functional Dependency)

n Cho l

ượ ệ ấ ỳ ệ ồ c đ quan h R(U), r là 1 quan h b t k trên R, X

ậ ộ và Y là 2 t p thu c tính con.

ị ụ ượ  Y trên l

n Đ nh nghĩa: Ph thu c hàm (FD) f: X ế ớ

ị ệ

ộ ỉ ế ị ị

(cid:0)

t1[Y]= t2[Y] ọ t1, t2 (cid:0) ế ệ

Trần Thi Kim Chi

ế ệ ả ọ ồ c đ ệ ỗ quan h R n u và ch n u m i giá tr X trong r có quan h ấ ể chính xác v i 1 giá tr Y trong r. Nghĩa là b t k khi nào 2 ị ộ ủ b c a r có cùng giá tr X thì cũng có cùng giá tr Y. r(R): t1[X] = t2[X] (cid:0)  X là v trái, ký hi u left(f) hay còn g i là determinant  Y là v ph i, ký hi u right(f) hay còn g i là dependent

Phụ thuộc hàm (Functional Dependency -FD)

ữ ộ c a các thu c tính,

n Ph thu c hàm là 1 ộ c xem là 1

ụ ượ ể ữ ộ ủ ặ đ c đi m ng nghĩa ràng bu c ộ gi a các thu c tính. đ

n Ví d : M t nhân viên ch có 1 m c l

ụ ộ ỉ ươ ư ề ng nh ng nhi u

ứ ươ ể nhân viên có th có cùng 1 m c l ́ ư ng

Emp_ID  Salary

Salary  Emp_ID

n Ph thu c hàm đ ộ

ệ ắ ụ

Trần Thi Kim Chi

ụ ượ c xác đ nh d a vào quy t c nghi p v ượ ồ ượ ị c xác đ nh trên l ự ị ệ c đ quan h đ

Phụ thuộc hàm (Functional Dependency -FD)

̀ ́ ự ̉

n T quy tă c bao toa n th c thê ộ t c các thu c tính Y c a l

ủ ượ ế ồ ụ ẽ ộ ̉  n u X là 1 candidate key ả c đ R s ph i ph thu c

ượ ồ c đ PROFESSOR có ProfId là primary key ̀ ư ấ ả thì t hàm vào X n Ví d : trong l ụ

nên:

ProfId  Name, Qualification

n Có 1 s FD trong l ố

Trần Thi Kim Chi

ượ ồ ẽ ư ừ ữ ệ c đ s gây ra d th a d li u.

Phụ thuộc hàm (Functional Dependency -FD)

Ví dụ FD và dư thừa dữ liệu

ớ c đ PERSON(SSN, Name, Address,Hobby) v i quy

ượ ồ ườ ể

ườ ề ả ộ ở i có nhi u s thích thay

n Xét l ề ở ắ t c là 1 ng i có th có nhi u s thích (hobby) ¨ SSN,Hobby  SSN, Name, Address,Hobby n B t th ườ ấ ổ ị đ i đ a ch

Trần Thi Kim Chi

ng x y ra khi m t ng ỉ

ụ ệ

Phụ thuộc hàm (Functional Dependency -FD) n Ví d : Cho quan h phancong sau :

Tùng

9/8

10:15a

Tùng

116

10/8

1:25p

Minh

281

8/8

5:50a

Minh

301

12/8

6:35p

Minh

13/8

10:15a

Nghia

11/8

10:15a

Nghia

116

12/8

1:25p

Trần Thi Kim Chi

Phancong (Phicong, maybay, ngaykh, giokh)

Phụ thuộc hàm (Functional Dependency -FD)

ễ ả

di n t

n Quan h Phancong ệ

NKH

GKH

ờ

ở ả

Tùng

9/8 10:15a

ệ

ề

Tùng

116 10/8

1:25p

phi công nào lái máy bay nào và máy bay kh i hành vào ệ th i gian nào. Quan h trên ph i tuân theo ộ các đi u ki n ràng bu c sau : Ø M i máy bay có m t gi

ộ ờ

Minh

281

8/8

5:50a

Minh

301 12/8

6:35p

ấ

Minh

83 13/8 10:15a

Nghia

83 11/8 10:15a

Nghia

116 12/8

1:25p

ế ế ở

ở

ỗ ở kh i hành duy nh t. Ø N u bi ế ế t phi công, bi t ờ t kh i hành thì bi ngày gi ượ c máy bay do phi công đ lái. Ø N u bi ế ế ế t t máy bay, bi ế ờ kh i hành thì bi ngày gi t Trần Thi Kim Chi ế phi công lái chuy n máy bay y.ấ

Phụ thuộc hàm (Functional Dependency -FD) ụ ề

ụ

ộ

ượ

ộ c phát bi u l

NKH

GKH

Tùng

9/8 10:15a

ị

n Các ràng bu c này là các ví d v ph thu c hàm ể ạ ư và đ i nh sau : Ø MAYBAY xác đ nh GIOKH. ị Ø {PHICONG, NGAYKH, GIOKH} xác đ nh

MAYBAY.

Tùng

116 10/8

1:25p

ị

Ø {MAYBAY, NGAYKH} xác đ nh PHICONG

hay

Minh

281

8/8

5:50a

ộ

ụ

Minh

301 12/8

6:35p

ụ

Ø GIOKH ph thu c hàm vào MAYBAY. Ø MABAY ph thu c hàm vào {PHICONG,

Minh

83 13/8 10:15a

ụ

ộ NGAYKH, GIOKH} . Ø PHICONG ph thu c hàm vào {MAYBAY, ộ

ệ

Nghia

83 11/8 10:15a

Và đ

NGAYKH}. c ký hi u nh sau :

GIOKH

Nghia

116 12/8

1:25p

MAYBAY

ượ ư Ø {MAYBAY} (cid:0) Ø {PHICONG, NGAYKH, GIOKH) (cid:0) Ø {MAYBAY, NGAYKH} (cid:0)

PHICONG

Trần Thi Kim Chi

Phụ thuộc hàm (Functional Dependency -FD) Ví dụ

n V i quan h này, cho bi

ệ ớ ế ộ ụ t có các ph thu c hàm

A B C

sau không? 1. A (cid:0) B Không vì t1 [A] = t4 [A], but t1 [B] (cid:0) t4 1 5 3

2 6 4

3 7 4

1 4 3

Trần Thi Kim Chi

[B]. 3. A (cid:0) Có vì t1 [A] = t4 [A], and t1 [C] = t4 [C]. 5. AB (cid:0) C Có vì ti [AB] (cid:0) tj [AB] for i (cid:0) j .

Phụ thuộc hàm (Functional Dependency -FD)

A a1 a1 a2 a3 a2 a4

B b 1 b 1 b 1 b 2 b 1 b 1

C c 1 c 2 c 2 c 3 c 3 c 1

D d 1 d 1 d 3 d 4 d 3 d 5

E e 1 e 2 e 2 e 3 e 4 e 1

F f 1 f 3 f 3 f 2 f 4 f 1

n Các phụ thuộc hàm của quan hệ R là:

B D

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

E,F

n Các bộ của quan hệ r(R) có vi phạm các FD này không?

Trần Thi Kim Chi

Giải thuật kiểm tra phụ thuộc hàm

n Thu t toán Satifies :

ậ ệ Cho quan h r và X, Y là hai t p ị True ẽ ả ề

ậ ủ con c a Q+. Thu t toán Satifies s tr v giá tr n uế X (cid:0) Y ng i là

n Bài toán: cho quan h r và 1 ph thu c hàm f:X

ộ ậ ượ ạ c l ệ  Y. Ki m ể

False ụ tra xem r th a mãn f hay không?

ỏ n Function Satisfies(r,f:X Y) ứ ự ắ ủ ộ

¨ S p th t ¨ If m i t p các b có cùng giá tr X thì có cùng giá tr Y ỗ ậ

các b trong r theo các thu c tính c a X ị ộ ộ ị

n Satisfies = true

¨ Else

n Satisfies = false

Trần Thi Kim Chi

then

Thuật toán Satifies

Tùng

9/8

10:15a

Minh

13/8

10:15a

Nghia

11/8

10:15a

Nghia

116

12/8

1:25p

Tùng

116

10/8

1:25p

ế

ả

MAYBAY (cid:0) GIOKH Cho k t qu là True

Minh

281

8/8

5:50a

Nghia

281

5:50a

Minh

281

13/8

5:50a

Minh

301

12/8

6:35p

Trần Thi Kim Chi

Phancong (Phicong, maybay, ngaykh, giokh)

Thuật toán Satifies

SATIFIES (Phicong, maybay, ngaykh, giokh)

Tùng

83 9/8

10:15a

Minh

83 13/8

10:15a

Nghia

83 11/8

10:15a

MAYBAY (cid:0) GIOKH ả ế cho k t qu là False

Nghia

116 12/8

1:25p

Tùng

116 10/8

1:25p

Minh

281 8/8

5:50a

Nghia

281

98 5:50a

Minh

281 13/8

1:50a

Minh

301 12/8

6:35p

Trần Thi Kim Chi

Bài tập 1: Cách nhận biết một phụ thuộc hàm thỏa trên 1 thể hịên của quan hệ Q ? Thuật toán Satifies

ộ ụ ỏ

Ph thu c hàm nào sau đây th a r (A, B, C, D, E )? A (cid:0) D , AB(cid:0) D , AB (cid:0) B, AB E

a1 b1 c1 d1 e1 a1 b1 c2 d1 d1 a2 b1 c3 d3 e1 a2 b1 c4 d3 e1 a3 b2 c5 d1 e1

Trần Thi Kim Chi

Bài tập 2: Tìm phụ thuộc hàm thỏa trên 1 thể hịên của quan hệ R ? Thuật toán Satifies

A

B

C

D

E

F

A a1 a1 a2 a3 a2 a4

B b 1 b 1 b 1 b 2 b 1 b 1

C c 1 c 2 c 2 c 3 c 3 c 1

D d 1 d 1 d 3 d 4 d 3 d 5

E e 1 e 2 e 2 e 3 e 4 e 1

F f 1 f 3 f 3 f 2 f 4 f 1

n Các ph thu c hàm c a quan h R là:

ụ ủ ệ ộ

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

B D

E,F

n Các b c a quan h r(R) có vi ph m các FD này không?

ộ ủ ạ ệ Trần Thi Kim Chi

ậ

Thu t toán Satifies

Phụ thuộc hàm nào sau đây thỏa r’ A (cid:0) D , AB(cid:0) D

Phụ thuộc hàm nào sau đây thỏa q BC(cid:0) E , DE(cid:0) C , A (cid:0)

BCDE

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

a1 b1 c1 d1 e1 a2 b2 c2 d2 e2 a3 b1 c1 d1 e1 a4 b2 c2 d2 e2 a5 b1 c1 d3 e1

Trần Thi Kim Chi

ậ

Thu t toán Satifies

Phụ thuộc hàm nào sau đây thỏa q BC(cid:0) E , DE(cid:0) C , A (cid:0)

BCDE

a1 b1 c1 d1 e1 a2 b2 c2 d2 e2 a3 b1 c1 d1 e1 a4 b2 c2 d2 e2 a5 b1 c1 d3 e1

Trần Thi Kim Chi

ụ

ụ ộ

Tìm tất cả các phụ thuộc hàm Ví d : Q+= {C, T, H, R} Có bao nhiêu tâp con? Có 2n = 24 =16 ể Có bao nhiêu ph thu c hàm có th có ?có 2n x 2n = 24 x 24 =256

˘ (cid:0)

C

T

H

R

(cid:0) T, (cid:0)

(cid:0) C; (cid:0)

(cid:0)

C

(cid:0) CT,… CT, C (cid:0) H,… CT, T (cid:0) H,…

(cid:0) (cid:0) (cid:0)

; (cid:0) ; C (cid:0) ; T (cid:0)

T; C (cid:0) C; T (cid:0)

T CT

H CH

R CR

TH

TR

CTH

CTR

HR

CHR

THR

THR,

CTHR

C (cid:0) T (cid:0) …. (cid:0) , CTHR (cid:0) CTHR (cid:0) CT, CTHR (cid:0) CTHR (cid:0) CTHR (cid:0) CH, CTHR (cid:0) CTHR (cid:0) CTHR (cid:0) CTHR (cid:0) CTHR (cid:0) CTHR (cid:0)

C, H, TH, CTH, CTHR (cid:0) R, CR, CTHR (cid:0) TR, CTR, CTHR (cid:0) HR, CHR, CTHR (cid:0) CTHR 22

Trần Thi Kim Chi

Tập phụ thuộc hàm

n G i F là 1 t p ph thu c hàm trên R n u m i ph thu c

ọ ụ ế ộ ọ ộ

ậ ề ộ ụ hàm trong F đ u là ph thu c hàm trên R

ụ ộ ộ ầ ng (trivial FD) hay ph thu c hàm

(cid:0) ụ n Ph thu c hàm t m th ế

X Name

n S t p con có th có c a R = {A1,A2,...,An} là ủ n ẽ ạ

ườ ụ  Y n u Y ể hi n nhiên X ¨ Ví d : ụ Name, Address (cid:0) ố ậ ể 2n.

ớ ố

ậ ỉ ủ ậ ầ ử ố c là 1 ch nh h p l p ch p 2 c a 2n ph n t  S FD có th có ố i ể . S FD t

Trần Thi Kim Chi

ể Ứ ng v i 2 t p con s t o thành 1 FD ợ ặ ượ đ 22n. đa có th có (2n)2=

Tập phụ thuộc hàm

n FD đ

ể ượ ể ả ộ

ả ả ầ ậ

ệ c dùng đ th hi n các ràng bu c b o toàn (integrity constraint), vì v y DBMS c n ph i qu n lý các FD.

n V i 1 t p S ch a toàn b các FD c a 1 l

ộ ớ ậ ứ ủ ồ

(cid:0) ề ậ ọ

ầ ủ ủ ừ ỉ c đ , có cách S sao cho m i FD c a S đ u ng m các FD c a T. Khi đó, DBMS ch qu n lý các FD c a

Trần Thi Kim Chi

ẽ ượ ự ộ ả ộ ượ ủ ả c qu n lý m t cách t nào tìm ra 1 t p T suy t T, các FD trong S s đ đ ng.

Hệ tiên đề Amstrong

ọ

ậ

ừ t

PHỤ THUỘC HÀM ĐƯỢC SUY DIỄN LOGIC TỪ F n Ph thu c hàm X ộ

ễ c ượ suy di n lu n lý

ộ

ế ỏ

F n u m i quan Y

ượ

ễ

Y đ ụ ụ ọ ệ ỏ h th a mãn m i ph thu c hàm trong F thì cũng th a mãn X ¨ Ký hi u F X ệ ⊨ Y ¨ F bao hàm (implies) XY ¨ XY đ ắ

ệ ừ ế

c suy di n theo quan h t n Quy t c suy di n (inference rule): ễ ệ

ố

ụ ộ

ệ ỏ ố n u 1 quan h th a mãn 1 s ụ ỏ ộ ph thu c hàm nào đó thì quan h này cũng th a mãn 1 s ph thu c hàm khác

PHICONG

Ví dụ : Phân công (Phicong, Maybay, NgayKH, GioKH) (1) : {MAYBAY} (cid:0) GIOKH (2) : {MABAY,NGAYKH } (cid:0) (3) {MABAY,NGAYKH} (cid:0)

PHICONG , GIOKH

Trần Thi Kim Chi

ễ ừ

ụ

ộ (là ph thu c hàm suy di n t

(1) và (2) )

(cid:0)

Hệ tiên đề Amstrong

n Cho quan h Q(Q+) . X,Y,Z,W là các t p thu c tính c a Q+.

ủ ệ ộ

ồ ề ệ

ả X(cid:0) Y ậ (cid:0) X (cid:0)

XZ (cid:0) YZ

ắ ầ (cid:0) Y và Y(cid:0) Z (cid:0) X (cid:0) Z

ợ

ế (cid:0) Y và X(cid:0) Z (cid:0) (cid:0) YZ (cid:0) X (cid:0) YZ X (cid:0) Y, X (cid:0) Z

ắ ầ ả ậ H tiên đ Amstrong g m các lu t sau ¨ F1. Ph n x (reflexivity): Y ạ ¨ F2. Gia tăngthêm vào(augmentation): X(cid:0) Y (cid:0) ¨ F3. B c c u (transitivity): X ¨ F4. H p (additivity): X ¨ F5. Chi u (projectivity): X ¨ F6. B c c u gi (pseudotransitivity): X (cid:0) Y và YZ(cid:0) W (cid:0)

Trần Thi Kim Chi

XZ (cid:0) W

ụ

Hệ tiên đề Amstrong Ví d : cho q (ABCDE)

ả

ậ

ạ

Lu t ph n x

ậ

Lu t thêm vào

B (cid:0) A (cid:0)

DE DEB

DEB

ậ ắ ầ Lu t b c c u

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

DE C

ả

ậ ắ ầ Lu t b c c u gi

AB (cid:0)

ậ ộ Lu t h i

A (cid:0)

DEB

DE B

ậ

Lu t phân rã

A (cid:0)

A (cid:0) DE (cid:0) A (cid:0) DEB (cid:0) A (cid:0) A (cid:0) A (cid:0) DE Trần Thi Kim Chi

D , A (cid:0) 27

Hệ tiên đề Amstrong

ỏ

(cid:0)

thi C, C(cid:0) A th a trên Q ỏ ằ ABC th a trên Q ? ế t)

ạ

thi t)

Trần Thi Kim Chi

ả (gi ậ (lu t thêm (1) thêm B) ả ậ (lu t ph n x ) ậ ộ (lu t h i (2),(3)) ế ả (gi ậ ậ ắ ầ ừ Ví du: cho AB (cid:0) ứ Ch ng minh r ng BC 1. C(cid:0) A 2. BC (cid:0) A 3. BC (cid:0) B 4. BC (cid:0) AB 5. AB (cid:0) C 6. AB (cid:0) ABC (lu t thêm (5) thêm AB) 7. BC (cid:0) ABC (lu t b c c u t (4) và (6))

Hệ tiên đề Amstrong

Ví dụ

ể ứ

n Dùng h tiên đ Amstrong đ ch ng minh ế N u X

(cid:0) ề ệ YZ và Z (cid:0) W, thì X (cid:0) YZW

n Ch ng minh: ứ ¨ T Z ừ (cid:0) YZW

(cid:0) ậ W  YZZ (cid:0) YZW (lu t gia tăng) hay YZ

¨ T Xừ  YZ và YZ  YZW  X (cid:0)

Trần Thi Kim Chi

ậ ắ ầ YZW (lu t b c c u)

Bao đóng của tập thuộc tính

ộ ủ ậ ộ ậ ụ

n Bao đóng c a t p thu c tính X d a trên m t t p ph thu c ộ hàm F (closure of X under F) là 1 t p thu c tính Y sao cho: ¨ (cid:0) XY(cid:0) ¨ (cid:0) XZ(cid:0)

ự ậ ộ

+ FX

F+ F+: Z (cid:0) Y

Trần Thi Kim Chi

ặ Ho c = {A|X A (cid:0) F+}

Bao đóng của tập thuộc tính

n Ví d : Cho quan h Q(A,B,C,D,E,G) và ệ

¨ F={A  C; A  EG; B  D; G  E}; ¨ X={A,B}; ¨ Y={C,G,D}

n Thì X+ = {A,B,C,D,E,G};

n Y+ = {C,G,D,E}

ụ

n T

ươ ủ ậ ng t

Trần Thi Kim Chi

(cid:0) ầ ử ủ ứ ự ư ậ ứ X+ cũng ch a các ph n t nh t p bao đóng c a t p PTH F+, t p bao đóng c a X+, t c là X ậ X+.

Giải thuật tìm bao đóng của tập thuộc tính trên tập phụ thuộc hàm

ậ ậ ộ

Thu t toán tìm bao đóng X ươ tính X0,X1,X2,... theo ph ế ậ +: Tính liên ti p t p các t p thu c ng pháp sau:

B ướ : c 1 X0 = X

ủ ộ B ướ : c 2

(cid:0) Z

(cid:0) Z có Y (cid:0) ộ ụ ầ ượ l n l N u Yế ạ Lo i ph thu c hàm Y ụ t xét các ph thu c hàm c a F Xi thì Xi+1 = Xi (cid:0) Z kh i Fỏ

ướ ượ c 3 c 2 không tính đ c Xi+1 thì Xi

ế ở ướ : N u B b chính là bao đóng c a Xủ

Ng c 2

ượ ạ ặ ạ ướ i l p l i b c l Trần Thi Kim Chi

Giải thuật tìm bao đóng của tập thuộc tính trên tập phụ thuộc hàm Ví dụ 1: Cho lược đồ quan hệ Q(ABCDE) và tập phụ thuộc hàm F F = {

f1: A (cid:0) C D E }

f2: B (cid:0) f3: C f4: D (cid:0)

Tìm bao đóng của tập X = {A} dựa trên F

(cid:0)

iả : c ướ 1:X0 = A ướ

B = AB , lo i f1ạ

ọ

C = ABC , l ai f2

D = ABCD , lo i f3ạ

E = ABCDE , lo i f4ạ

ướ

Gi B c 2: B xét f1 vì A (cid:0) xét f2 vì B (cid:0) xét f3 vì C (cid:0) xét f4 vì D (cid:0) B

c 3 :

X0  X1 = A (cid:0) X1  X2 = AB (cid:0) X2  X3 = ABC (cid:0) X3  X4 = ABCD (cid:0) X+ = X4 = {ABCDE} là bao đóng c a Xủ Trần Thi Kim Chi

ượ ồ

ụ

ộ

ệ

ậ

Giải thuật tìm bao đóng của tập thuộc tính trên tập phụ thuộc hàm Ví d 2:ụ (sgk ) Cho l F = {

c đ quan h Q(ABCDEGH) và t p ph thu c hàm F f1: B (cid:0)

f2: DA (cid:0) f3: D f4: GH(cid:0) f5: AC (cid:0)

CE H C D }

(cid:0)

ự

ủ ậ

X0  X1 = AC (cid:0)

Tìm bao đóng c a t p X = {AC} d a trên F. Gi B B

D = ACD, lo i f5ạ CE = ACDE, lo i f2ạ

H = ACDEH

X1  X2 = ACD (cid:0) X2  X3 = ACDE (cid:0) ỏ

ế

ậ

iả : c ướ 1:X0 = AC c ướ 2: xét f5 vì AC (cid:0) xét f2 vì AD (cid:0) xét f3 vì D (cid:0) Xét f1, f4 :không th a vì có v trái không n m trong X3 V y X3 không thay đ i

ằ ổ  X+=X3={ACDEH} là bao đóng c a Xủ Trần Thi Kim Chi

Giải thuật tìm bao đóng của tập thuộc tính trên tập phụ thuộc hàm Ví d tìm bao đóng c a X

ủ ụ

n Cho R(A,B,C,D,E,F) và t p F={f1:D

ậ B, f2: AC, f3:

n Tìm A+F:

¨ A+F ={A} ¨ Duy t F l n 1: T f2 ầ ệ

ADE, f4:CF}

ừ  A+F = {AC}; T f4 ừ  A+F =

{ACF}

¨ Duy t F l n 2: A+F không thay đ i ổ

ệ

§ Tìm {AD}+F ???

Trần Thi Kim Chi

ầ  A+F = {ACF}

Giải thuật tìm bao đóng của tập thuộc tính trên tập phụ thuộc hàm Ví d tìm bao đóng c a X

n Ví dụ: Cho tập phụ thuộc hàm:

¨ F = { SSN→ENAME, PNUMBER→{PNAME, PLOCATION},

{SSN, PNUMBER} → HOURS}

n Suy ra:

¨ {SSN}+ = {SSN, ENAME} ¨ {PNUMBER}+ = {PNUMBER, PNAME, PLOCATION} ¨ {SSN, PNUMBER}+ = {SSN, PNUMBER, ENAME, PNAME,

PLOCATION, HOURS}

n Như vậy, tập thuộc tính {SSN, PNUMBER} là khoá của

ụ ủ

Trần Thi Kim Chi

quan hệ.

(cid:0) (cid:0) (cid:0) Y, t p Fậ

Kiểm tra thành viên trong F+ n B đ 1: ề

ể ờ f nh vào (cid:0) F+. Đ xác đ nh F ị

ể ổ ề Cho ph thu c hàm f: X ụ ộ ế ỉ ế ệ h tiên đ Armstrong n u và ch n u Y  Y (cid:0) X⊨ Y, c n ki m tra X ầ F+

ả ủ ổ ề Bài toán thành viên

ệ ậ ượ c. Bài

(cid:0)

n H qu c a b đ : ệ ¨ Cho F và f: X (cid:0) ặ tóan đ t ra là f

ớ ộ Y m t pth m i nh n di n đ F+ ?

¨ Theo b đ 1 : tr l ổ ề

ươ ươ ứ i bài toán này t ng đ ng ch ng

minh Y (cid:0)

Trần Thi Kim Chi

ả ờ F+ ¨ Nghĩa là không c n tìm F+ đ tr l ầ ể ả ờ f (cid:0) i F+

ậ

ả

Kiểm tra thành viên trong F+ n Gi

ộ

Y và t p Fậ

i thu t: ậ ấ

¨ Nh p: ph thu c hàm X ụ ¨ Xu t: true n u F X

ế ⊨ Y, ng

ượ ạ c l

i là false

Function Member(X,Y,F)

Begin

if Y (cid:0)

Closure(X,F) then Member = true

else Member = false;

End

ị ủ (cid:0) Y có là thành viên c a F+ hay

ậ Thu t toán xác đ nh f:X không?

Trần Thi Kim Chi

(cid:0) (cid:0) ị B c 1 B c 2 ướ : tính X+ ế ướ : n u Y ẳ X+ thì kh ng đ nh X Y (cid:0) F+

C, BC (cid:0)

D, D (cid:0)

EG,

BE (cid:0)

C}, AB (cid:0)

ả

ậ i thu t

ủ

Cách 2: Theo gi • AB+ ={ABCDEG} • AB  EG là thành viên c a F+

ế ế

t) t)

{ABCDEG}

vì EG (cid:0)

Kiểm tra thành viên trong F+ Ví dụ n Cho R = {A, B, C, D, E, G} và F = {AB (cid:0) ằ EG có n m trong F+? ề Cách 1: Theo tiên đ Astrong ả C (Gi thi ả thi D (Gi ả ắ ầ D (B c c u gi ) ế ả t) thi EG (Gi ắ ầ EG (B c c u)

¨ AB (cid:0) ¨ BC (cid:0) ¨ AB(cid:0) ¨ D (cid:0) ¨ AB (cid:0)

B, A (cid:0)

C, CG (cid:0)

H, CG (cid:0)

n Cho R = (A, B, C, G, H, I) và F = {A (cid:0) ủ

ộ ố

H}. Tìm m t s thành viên c a F+

Trần Thi Kim Chi

I, B (cid:0) ¨ A (cid:0) ¨ AG (cid:0) ¨ CG (cid:0)

H I HI

Kiểm tra thành viên trong F+

n Cho R = (A, B, C, G, H, I), F= {A (cid:0)

B, A (cid:0)

C, CG (cid:0)

H, CG (cid:0)

I, B

Ví dụ

(cid:0)

H} ộ ố

ủ

M t s thành viên c a F+ n A (cid:0)

ậ ắ ầ

B và B (cid:0)

ề H (theo đ ) suy ra A

H (lu t b c c u)

¨ t n AG (cid:0)

C (theo đ )ề

ưở

ng thêm G)

ậ ắ ầ

ậ CG (lu t tăng tr I (theo đ )ề I (lu t b c c u)

(cid:0)

ậ ợ

ể

n CG (cid:0) ¨ t

H và CG (cid:0)

I “lu t h p” có th có

đ nh nghĩa pth, hay

(cid:0)

ể

Trần Thi Kim Chi

H đ suy ra 40

H A ừ (cid:0) I ¨ A (cid:0) ¨ AG (cid:0) ¨ CG (cid:0) ¨ AG (cid:0) HI ừ CG ừ ị n t n thêm CG (cid:0) CGI (cid:0)

CGI, thêm CG (cid:0) I đ suy ra CG ậ ắ ầ ử ụ HI, và sau đó s d ng lu t b c c u

(cid:0)

Kiểm tra thành viên trong F+ Ví dụ kiểm tra phụ thuộc hàm

n Cho F={DB, AC, ADE, CB}. Ki m tra F có bao

ể

n Cách 1

hàm AB??

Tìm A+F?  A+F = {ACB} Do B (cid:0)

n Cách 2: Dùng h tiên đ Astrong ệ

Trần Thi Kim Chi

A+F nên F bao hàm AB ề

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

ộ ụ

ỏ ộ ấ

ề ủ ậ ứ ậ ậ ụ ộ ể ụ ể ạ

ệ

ễ ừ

ợ

c suy di n t

ượ ồ

ệ

ậ

c đ quan h Q(A,B,C,D) và t p

ượ

n Bao đóng (closure) c a t p ph thu c hàm F là 1 t p ph ụ ệ thu c hàm nh nh t ch a F sao cho không th áp d ng h tiên đ Amstrong trên t p này đ t o ra 1 ph thu c hàm khác không có trong t p h p này ¨ Ký hi u F+ ¨ F+ là 1 t p h p các FD đ ậ ượ n Ví d : ụ Cho r l quan h trên l c cho nh sau:

F đ

ư F = {A  B; B  C; A  D ; B  D}

khi đó F+= { A  B; B  C; A  D ; B  D; A BD; A  BCD; A C; A CD; A BC; B  CD;….}

Rõ ràng F (cid:0)

F+

Trần Thi Kim Chi

ậ ợ

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

n Ví d cho F={ ụ  F+=

AB C, CB} trên r(ABC)

{AA, ABA, ACA, ABCA,

Trần Thi Kim Chi

BB, ABB, BCB, ABCB, CC, ACC, BCC, ABCC, ABAB, ABCAB, ACAC, ABCAC, BCBC, ABCBC, ABCABC, ABC, ABAC, ABBC, ABABC, CB,CBC, ACB, ACAB }

Các tính chất của bao đóng của tập phụ thuộc hàm

ớ ọ ậ ộ 1. Tính ph n x :

F+

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

ế ệ n u F ớ ọ ậ ụ G+ ộ v i m i t p ph thu c hàm F ta luôn có ụ ả ạ v i m i t p ph thu c hàm F+ ta luôn có F (cid:0) ơ 2. Tính đ n đi u: 3. Tính lũy đ ng:ẳ

ệ

ụ

ộ

ừ

ễ

ệ

ậ

ộ ộ

ệ

ả

(F+)+ = F+. ề H tiên đ Amstrong n H tiên đ Amstrong là ề suy di n t ộ Amstrong cũng là m t ph thu c hàm trên r

ượ

ế

ễ

đúng đ nắ (sound)  các ph thu c hàm ề ụ F (t p ph thu c hàm trên r) theo h tiên đ ụ toàn v nẹ (completeness)  b o đ m n H tiên đ Amstrong là ề ỉ ế F+ n u và ch n u f là 1 FD đ c suy di n

ệ ằ r ng f

Trần Thi Kim Chi

(cid:0)

Thuật toán tìm F+

ậ

Thu t toán tìm F+

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

ấ ả ụ ủ ể ộ ướ : Tìm t t c các ph thu c hàm có th có c a Q.

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

n B c 1 n B c 2 n B c 3 n B c 4

ậ ể t c các t p con đã tìm đ

Trần Thi Kim Chi

ự ụ ị ướ : D a vào bao đóng c a t ủ ấ ả ộ ộ xác đ nh ph thu c hàm nào thu c F+

ộ

ậ

ủ ấ ả ậ

t c t p

B3: Bao đóng c a t con

(cid:0)

ấ ả A {A}

Q(A,B,C) F = {AB (cid:0) C,C (cid:0) B} F+ ? ủ ậ B1: T t c các t p con c a t p thu c tính C {C} {A,C}

B {B} {A,B}

= A = B

{B,C}

C+ = BC AC+ = ABC = ABC BC+ =

A+ B+ {AB}+ BC

{A,B,C}

ụ

ể B2: T t c các ph thuôc hàm có th có: C(cid:0) A

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

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

AC(cid:0) ABC(cid:0) F+ BC(cid:0) ABC

ấ ả A(cid:0) B A(cid:0) BC B(cid:0) C 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 A(cid:0) C B(cid:0) A B(cid:0) BC AB(cid:0) BC(cid:0) F+ C(cid:0) AB A(cid:0) AC B(cid:0) AB B(cid:0) ABC AB(cid:0) ABC(cid:0) F+C(cid:0) AC

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

F+ = { AB(cid:0) C, AB(cid:0) AC, AB(cid:0) BC,AB(cid:0) ABC, C(cid:0) BC, C(cid:0) B, AC(cid:0) B, AC(cid:0) AB, AC(cid:0) BC,AC(cid:0) ABC} Trần Thi Kim Chi

C , C (cid:0) B}

VD (sgk) : cho Q (A,B,C) , F = {AB (cid:0) Tìm F+ ? (Thuật toán cải tiến)

ấ ả ủ ậ B1: tìm t t c các t p con c a Q+

{A} {B} {C }

{AB} {AC}

{BC}

{ABC}

B2: Tìm bao đóng của tất cả các tập con trên

A+ = A B+ = B C+ = CB

AB+ = ABC AC+ =ACB BC+ =BC

Trần Thi Kim Chi

ABC+ = ABC

C , C (cid:0) B}

ể

ộ ỉ ồ

ể

B3: rút ra các pth thu c F+ (không k các pth hi n nhiên) § Các bao đóng ch g m pth hi n nhiên (không tính): A+ = A B+ = B BC+ =BC ABC+ = ABC

• Các t p con c a {ABC} : {A} ,{B} , {C} , {AB}, {AC} ,{BC},

§ Xét AB+ = ABC : ủ ậ {ABC}

ỏ

ậ

ả ủ

ế

ạ

• B các t p con c a {AB} : {A} ,{B} , {AB} • Các t p còn l ậ

ủ i: {C} ,{AC} ,{BC},{ABC} chính là v ph i c a

ự

ế pth có v trái là AB § Xét AC+ =ACB : làm t

ng t

ạ

ế

ả

i :

ươ {B} , {AB}, ,{BC},{ABC} chính là v ph i

VD (sgk) : cho Q (A,B,C) , F = {AB (cid:0) Tìm F+ ? (Thuật toán cải tiến)

ươ

ự

§ Các t p còn l ậ ế ủ c a pth có v trái là AC ng t

§ Xét C+ = CB : làm t

=> C

B ,CBC

AC , AB (cid:0)

BC , AB (cid:0)

ABC , AC (cid:0)

AB, AC

B , AC (cid:0) 48

F+ = { AB (cid:0) BC , AC (cid:0) (cid:0)

C , AB (cid:0) ABC , C (cid:0)

Trần Thi Kim Chi B ,CBC}

(cid:0)

Bài tập 1 : Chứng tỏ các pth sau được suy diễn từ F nhờ bộ luật dẫn Amstrong ?

A ,

DA CE , ?

DH H ,

AC (cid:0) AC (cid:0) AC (cid:0) EH F = { B (cid:0) DA (cid:0) D (cid:0) AC (cid:0) D }

A ,

CE , ? EH

CB , BD (cid:0) B (cid:0) CG

G ,

Trần Thi Kim Chi

F = { B (cid:0) BD (cid:0) A (cid:0) C (cid:0) GE (cid:0) H }

Bài tập 2: Cho Q(ABCDEGH) và tập pth F thỏa trên Q.

Tìm bao đóng của AC ?

A ,

CE , AC + = ?

H ,

F = { B (cid:0) DA (cid:0) D (cid:0) AC (cid:0) D }

A ,

CE ,

CB , B + = ?

G ,

Trần Thi Kim Chi

F = { B (cid:0) BD (cid:0) A (cid:0) C (cid:0) GE (cid:0) H }

Bài tập 3

n Cho R = {A, B, C, D, E, G} và F = {AB (cid:0)

C, BC (cid:0) D, D (cid:0)

n Cho R = (A, B, C, G, H, I) và F = {A (cid:0)

ằ EG, BE (cid:0) C}, AB (cid:0) EG có n m trong F+?

C, CG (cid:0) H,

ộ ố B, A (cid:0) ủ H}. Tìm m t s thành viên c a F+

I, B (cid:0) H

Trần Thi Kim Chi

CG (cid:0) ¨A (cid:0) ¨AG (cid:0) ¨CG (cid:0)

Bài tập 4

C}. Tính AB+

D, D (cid:0)

BC (cid:0)

Trần Thi Kim Chi

n Cho R = {A, B, C, D, E, G} và F = {AB (cid:0) EG, BE (cid:0)

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

(equivalences among sets of dependencies)

n N u F và G là 2 t p FD. F

ế ế suy di nễ G ( F entails G) n u F

ễ ế ng nhau n u F suy di n G và G suy

(cid:0) ậ ễ ượ ấ ả c t t c các FD có trong G. ươ ươ ng đ F+=G+ G.

Trần Thi Kim Chi

(cid:0) ủ ế suy di n đ n F và G là t ễ di n F hay ¨ Ký hi u F ệ ¨ Ta nói F ph G n u F+ G+

Kiểm tra các tập FD tương đương

n Input: F,G – các t p FDậ

n Output: true n u F t

ế ươ ươ ng đ ng G,

false n u ng ượ ạ c l i

ế For each f (cid:0) F do

if G does not entail f then return false

For each g (cid:0) G do

if G does not entail g then return false

Trần Thi Kim Chi

Return true

ả

Kiểm tra các tập FD tương đương Ví dụ n Hãy kh o sát 2 t p FD sau:

ươ ươ ậ ¨ F={ ACB, AC, DA} ¨ G={AB, AC, DA, DB} ng nhau không??? ng đ F và G có t

B (B c c u)

ừ ừ ừ A và T (2) A ắ ầ  AB (2) B (B c c u) ắ ầ  D B

T Aừ C (Thêm vào)  AAC (1) T (1), ta có AC T (gt) D F suy di n Gễ

ươ ự ễ T ng t

khi xét G suy di n F Trần Thi Kim Chi

ượ ồ ụ ệ ậ ộ

ươ ươ ươ ươ ớ ớ

Kiểm tra các tập FD tương đương Ví du: Cho l c đ quan h Q(ABCDE) hai t p ph thu c hàm: F={A(cid:0) BC,A(cid:0) D,CD(cid:0) E} và G={A(cid:0) BCE,A(cid:0) ABD,CD(cid:0) E} ng v i G không? ng v i G’={A

(cid:0) BCDE} không? ng đ ng đ

V y ậ F (cid:0) A(cid:0) BC (1)

A(cid:0) D (2)

E (3)

a) F có t b) F có t i:ả Xét A(cid:0) BCE; A (cid:0) BC; A (cid:0) E; Xét A(cid:0) ABD; A (cid:0) AB; A (cid:0) D; Xét CD(cid:0) E; (1),(2),(3) suy ra G+ (cid:0) F (cid:0) V y ậ F (cid:0) CD(cid:0) Trần Thi Kim Chi F+

Kiểm tra các tập FD tương đương

ệ

ượ ồ

ụ

ậ

ộ

c đ quan h Q(ABCDE) hai t p ph thu c hàm:

ươ ươ

ớ ớ

Ví du: Cho l F={A(cid:0) BC,A(cid:0) D,CD(cid:0) E} và G={A(cid:0) BCE,A(cid:0) ABD,CD(cid:0) E} ng v i G không? ng v i G’={A

(cid:0) BCDE} không?

ng đ ng đ

a) F có t b) F có t i:ả

Xét A(cid:0)

A(cid:0)

ABD (1)

ả A (ph n x ); ABCD (h p); ợ

Xét A(cid:0)

G (cid:0) V y ậ ABCD (cmt),

ế

t);

ế V y ậ

G (cid:0)

A(cid:0)

BCE (2)

BC và A(cid:0) D; A(cid:0) ạ A(cid:0) BCD (do A(cid:0) CD; A(cid:0) A(cid:0) CD(cid:0) E (gi A(cid:0) mà A(cid:0) E; G (cid:0)

B (phân rã) ả t) thi ắ ầ E (b c c u) ả thi BC (gi C(cid:0) E (3)

Xét C(cid:0)

(1),(2),(3) suy ra F+ (cid:0)

Trần Thi Kim Chi G+

ươ

ằ ằ

Kiểm tra các tập FD tương đương n Đ ch ng minh F và G t ươ ng đ (cid:0) XY(cid:0) G (cid:0) (cid:0) XY(cid:0) F (cid:0)

ứ ng ta ch ng minh: XY (cid:0) F+ XY (cid:0) G+

G B ng cách: F B ng cách:

ể ứ ¨ F+ (cid:0) ¨ G+ (cid:0)

ượ ồ

ụ

ậ

c đ quan h Q(ABCDE) hai t p ph thu c hàm:

ươ

ớ

n Ví du: Cho l ộ ệ F={A(cid:0) BC,A(cid:0) D,CD(cid:0) E} và G={A(cid:0) BCE,A(cid:0) ABD,CD(cid:0) E} F có t

ng v i G không?

ng đ

Ta có AF+ =ABCDE (cid:0)

ABCE (cid:0) F+, AABD (cid:0) F+

CDF+= CDE (cid:0)

CDE (cid:0) F+

F+ (cid:0)

Ta có AG+=ABCED (cid:0)

ABC(cid:0) G+, AD(cid:0) G+, Trần Thi Kim Chi

CDE(cid:0) G+

CDG+=CDE (cid:0) G+ (cid:0)

(cid:0)

ậ

V y F+=G+

ụ

ộ ằ

PHỦ CỦA TẬP PHỤ THUỘC HÀM (cover of dependencies) ư ừ ế Ph thu c hàm có v trái d th a (cid:0) n Nói r ng ph thu c hàm Z ư ừ ế ế ộ ụ Y có v trái d th a n u có Y}(cid:0) {(ZA) (cid:0) F{Z (cid:0) Y} ộ

n Ví du: cho t p ph thu c hàm F={A

m t Aộ (cid:0) Z sao cho F (cid:0) ậ

ụ ế (cid:0) BC, B(cid:0) C, AB(cid:0) D} thì (cid:0) D có v trái d th a B vì A+ = ABCD ư ừ

ụ ộ ph thu c hàm AB V y Aậ  D thuoc F+ nên thay AB D bang AD

ầ ủ

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

B+ = BC suy ra BB, BC đ y đ nên không thay F (cid:0) (cid:0) ậ F – {AB (cid:0) {A (cid:0) ộ ụ BC,B (cid:0) n T p ph thu c hàm có v trái không d th a ế

Trần Thi Kim Chi

ậ ư ừ ụ ế ộ ộ ụ ư ừ là t p ph thu c hàm không có ph thu c hàm có v trái d th a

ụ ộ ộ ế ậ

PHỦ TỐI THIỂU CỦA TẬP PTH (Minimal cover of dependencies) n T p ph thu c hàm có v ph i là m t thu c tính

ộ ụ ả ề ươ ộ ộ ậ ươ ớ

ỗ ậ ộ ng đ ụ

M i t p ph thu c hàm F đ u t ụ ỉ ồ ộ

ng v i m t t p ộ ả ủ ế ph thu c hàm G mà v ph i c a các ph thu c hàm trong G ộ ch g m m t thu c tính. n Ví du: cho F = {A(cid:0) BC, B(cid:0) C, AB(cid:0) D} ta suy ra

{A(cid:0) B, A(cid:0) C ,B(cid:0) C, AB(cid:0) D} = G

ậ ộ F (cid:0) ụ

(cid:0) ộ

n T p ph thu c hàm không d th a ư ừ ậ ụ F sao cho F’(cid:0)

ư ừ ế Nói r ng F là t p ph thu c hàm không d th a n u không ụ ậ i F là t p ph thu c hàm ộ F.Ng ượ ạ c l

ư ừ

ằ ồ ạ t n t i F’ ư ừ d th a. n Ví dụ: cho F = {A(cid:0) BC, B(cid:0) D, AB(cid:0) D} thì F d th a vì Trần Thi Kim Chi F’= {A(cid:0) BC, B(cid:0) D} F (cid:0)

ụ ộ

ộ Y c a Fủ

ậ ướ ướ ủ Y} thì lo i ạ

PHỦ TỐI THIỂU CỦA TẬP PTH (Minimal cover of dependencies) ỏ ạ ư ừ Thu t toán lo i kh i F các ph thu c hàm d th a n B c 1 : L n l ầ ượ ụ t xét các ph thu c hàm X ế Y là thành viên c a F – {X n B c 2 : N u X X Y kh i F.ỏ ệ

n B c 3 : th c hi n b

ướ ướ ự ụ ộ ế c 2 cho các ph thu c hàm ti p theo

Trần Thi Kim Chi

c a F.ủ

ượ ọ ụ ể ố ộ c g i là m t t p ph thu c hàm t

ế ế

ộ ộ

ả

ộ

ộ ậ ệ ề ụ ụ ờ ậ ậ

PHỦ TỐI THIỂU CỦA TẬP PTH n F đ ỏ ế 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.

Trần Thi Kim Chi

PHỦ TỐI THIỂU CỦA TẬP PTH

ộ ậ

ạ ể ủ ụ ụ ế

ậ ướ ướ ộ ư ừ ộ ủ ố Thu t toán tìm ph t n B ỏ n B c 1: c 2:

ụ ộ ế ả ộ

n B

Trần Thi Kim Chi

i thi u c a m t t p ph thu c hàm ộ Lo i kh i F các ph thu c hàm có v trái d th a. ộ Tách các ph thu c hàm có v ph i trê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. ụ Lo i kh i F các ph thu c hàm d th a. c 3:

ụ

ậ

ộ

ệ

PHỦ TỐI THIỂU CỦA TẬP PTH Ví dụ: Cho l c đ quan h Q(A,B,C,D) và t p ph thu c F nh sau:

ậ

CD Thay ABCD b ng Bằ CD

B(cid:0)

ượ ồ F={AB(cid:0) CD, B(cid:0) C, C(cid:0) D} ể ủ ủ ố Hãy tính ph t i thi u c a F. Xét AB(cid:0) ướ CD; B c 1: A+(cid:0) A B+(cid:0) BCD V y F F={B(cid:0) CD, B(cid:0) C, C(cid:0) D }

ướ B c 2: ướ B c 3:

F={B(cid:0) C, B(cid:0) D, C(cid:0) D } Lo i Bạ (cid:0)

C , F’={B(cid:0) D,C(cid:0) D}

ạ ượ

B+=D; Không lo i đ

c D, F’={B(cid:0) C,C(cid:0) D}

Lo i Bạ (cid:0)

ạ

ỏ

D thu c F’+ nên lo i kh i F

B+=CBD; B(cid:0)

Lo i Cạ (cid:0)

ể

ậ

ộ D , F’ = {B(cid:0) C} ọ ượ C+=C Không l ai đ c; Trần Thi Kim Chi (cid:0) C,C(cid:0) D} ủ ố i thi u là F ={B

V y ph t

(cid:0)

Giải thuật tìm phủ tối thiểu (C2)

n Input: t p ph thu c hàm F ụ n Output: G là 1 ph t

ậ ộ

ướ ế ổ ộ B c 1: c bi n đ i thành thu c

ể ủ ủ ố i thi u c a F ề ượ ấ ả t c FD đ u đ G:=F, t ả ơ tính đ n bên phía ph i

ướ ấ ả ư ừ ủ ỏ ộ B c 2: t c thu c tính d th a kh i phía trái c a FD

Xóa t trong G

ướ ấ ả ư ừ ỏ B c 3: Xóa t t c các FD d th a kh i G

Trần Thi Kim Chi

Return G

Giải thuật tìm phủ tối thiểu (C2)

Ví dụ

n Cho t p thu c tính ABCDEFGH, và t p ph thu c hàm F

ụ ậ ậ ộ

Trần Thi Kim Chi

ộ ABHC AD CE BGHF FAD EF BHE

Giải thuật tìm phủ tối thiểu (C2)

Ví dụ (tt)

n B c 1: xác đ nh G v i t

ớ ấ ả ả ộ ị ế t c các FD có v ph i thu c tính

ướ đ nơ

Trần Thi Kim Chi

ABHC AD CE BGHF FA FD EF BHE

Giải thuật tìm phủ tối thiểu (C2)

n B c 2: Xóa t

ấ ả ư ừ ủ ỏ ộ t c thu c tính d th a kh i phía trái c a FD

ướ trong G ü Xe t ABH ́

Vi ̀

C A+= {AD}, B+={B}, H+={H} (AB)+ = {ABD}, (AH)+={AHD} (BH)+={BHEFAD}

Ø Xe t BGH ́

́ ̀ ư ư ́  FD ABHC không d th a vê tra i

F B+={B}, H+={H}, G+={G}, (GH)+={GH} Vi ̀

(BG)+={BG}, (BH)+={BHEFAD}

Trần Thi Kim Chi

́ ư ư ̀  BGH F co G d th a

Giải thuật tìm phủ tối thiểu (C2)

n B c 2: Xóa t

ấ ả ư ừ ủ ộ ỏ t c thu c tính d th a kh i phía trái c a FD

ướ trong G

ạ ỏ

Trần Thi Kim Chi

ABHC AD CE BHF (Lo i b G) FA FD EF BHE

Giải thuật tìm phủ tối thiểu (C2)

ướ ấ ả ư ừ

ỏ t c các FD d th a kh i G D (vi F̀ A, AD)

̣ ̉ B c 3: Xóa t n Lo i b FD F ạ ỏ n Loai bo FD BH F (vi BH̀  E, EF)

G còn l i các FD sau:

ạ G= {ABHC, AD, CE, FA, EF,

BHE}

Trần Thi Kim Chi

̀ ́ ̉ ̉ ̉  G la phu tô i thiêu cua F

Khóa của lược đồ quan hệ

n Xét Q(A1,A2,…,An) là l ượ ồ ủ ậ

ậ

ộ

ậ

ệ c đ quan h .

ủ ế ằ

¨ 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+. ủ n Nói r ng K là m t khóa c a Q n u: ộ

(cid:0) K sao cho K’+= Q+ ượ ọ

(cid:0) ế c g i là

¨ K+ = Q+ và ¨ Không t n t ồ ạ i K' n T p thu c tính S đ ộ ậ n Thu c tính A đ

ộ ượ ọ n u Aế

ượ ọ ộ siêu khóa n u S ộ thu c tính khóa ượ ạ i A đ c l c g i là K (cid:0) K v i K ớ thu c tính

Trần Thi Kim Chi

c g i là ấ ỳ ủ là khóa b t k c a Q. Ng không khóa.

ộ ượ ồ ủ ệ c đ quan h Q

gán K = Q+

ủ ộ

Khóa của lược đồ quan hệ ộ ậ Thu t toán tìm m t khóa c a m t l n B c 1 ướ : n B c 2 ặ ướ : A là m t thu c tính c a K, đ t K’=K ộ ự ế K = K' th c hi n l

ủ ượ ồ

ậ

n Ví dụ: Tìm t ộ

ấ ả t c các khóa c a l ư

thu c hàm nh sau: Q(C,S,Z); F={CS

ụ ệ c đ quan h và t p ph (cid:0) Z; Z(cid:0) C}

Siêu khóa

khóa

Xi+ C

Xi C

CSZ ZC

CS Z

SZ 72

SZ CSZ

SZC Trần Thi Kim Chi CSZ

SZ CSZ

N u K’+=Q+ thì gán (cid:0) A. ệ ạ ướ i b c 2

Giải thuật tìm khóa của lược đồ quan hệ

ậ ụ ộ

ấ ậ ấ ả ồ ủ t c khóa c a R

n Nh p: R(U) và t p ph thu c hàm F ậ n Xu t: t p h p K bao g m t ợ n T p thu c tính ngu n (TN) ch a t

ồ ứ ấ ả

ấ

ệ ở ế ấ ấ ộ t c các thu c tính xu t ụ ả ủ v ph i c a các ph ệ ở ả ế c v trái

ả ủ ế

Trần Thi Kim Chi

(cid:0) ộ ậ ệ ở ế hi n v trái và không xu t hi n ộ ộ thu c hàm và các thu c tính không xu t hi n ụ ẫ l n v ph i c a các ph thu c hàm TN=U (cid:0) ộ f(cid:0) F right(f)

Giải thuật tìm khóa của lược đồ quan hệ

n T p thu c tính đích (TD) ch a t ả

ộ

ấ t c các thu c tính có xu t ụ ủ ệ ở ế v trái c a các ph

ứ ấ ả ậ ộ ấ ệ ở ế v ph i và không xu t hi n hi n ộ thu c hàm

(cid:0) (cid:0) TD= (cid:0) f(cid:0) F right(f) (cid:0) f(cid:0) F left(f)

n T p thu c tính trung gian (TG) ch a t

ứ ấ ả ộ

ậ ấ ế ẫ t c các thu c tính ộ ụ ộ ệ ở ả ế xu t hi n ả ủ c v trái l n v ph i c a các ph thu c hàm

(cid:0) ủ ế K và TD (cid:0) K = ả: N u K là khóa c a Q thì TN

n H quệ

Trần Thi Kim Chi

(cid:0)

Thuật toán tìm tất cả khóa

ạ ậ

ậ

ồ

ộ

T o t p thu c tính ngu n TN. T p thu c tính trung

n B

ế

ượ ồ

(cid:0)

ướ c 1: gian TG ướ

N u TG =

ệ ỉ c đ quan h ch có 1 khóa K

c 2:

n B

ế

c 3

ủ ậ

thì l K=TN K t thúc ướ ượ ạ c l i qua b ậ ấ ả t c các t p con Xi c a t p trung gian TG

(cid:0)

Ng ướ ướ

c 3: c 4:

n B n B

ế

ằ Xi Xi)+ = Q+ thì Si = TN (cid:0)

ằ

ố

Tìm t Tìm các siêu khóa Si b ng cách N u (TN ạ ỏ Tìm khóa b ng cách lo i b các siêu khóa không t

n B

c 5:

(cid:0)

ướ thi uể Si, Sj (cid:0)

ỏ ậ

S if Si(cid:0)

Sj thì Lo i Sj ra kh i t p siêu khóa S

ậ

ạ

ạ Trần Thi Kim Chi ầ i chính là t p khóa c n tìm

S còn l

Thuật toán tìm tất cả khóa Ví d 1ụ

n Cho R(A,B,C,D,E,F) và F={DB, AC, ADE, CF}. Tìm

ủ ấ ả t

ủ t c các khóa c a R n B1: TN={AD}, TG={C} n Xi là các t p con c a TG ậ

Xi Xi (cid:0) TN (Xi (cid:0) TN)+ Siêu khóa Khóa

(cid:0) AD ADBCEF=R+ AD AD

Trần Thi Kim Chi

C ADC ADBCEF=R+ ADC

Thuật toán tìm tất cả khóa Ví d 2ụ

n Cho R(A,B,C,D,E,F) và F={AD, CAF, AB EC}. Tìm

ủ khóa c a R?

n TN={B} , TG={AC} n Khóa c a R là {AB} và {BC}

ủ

Xi Xi (cid:0) TN (Xi (cid:0) TN)+ Siêu khóa Khóa

(cid:0) B B

CB C ABCDEF=R+ BC BC

AB A ABCDEF=R+ AB AB

Trần Thi Kim Chi

AC ABC ABCDEF=R+ ABC

ộ

ủ

ế

ằ Nói r ng K là m t khóa c a Q n u: K+ = Q+ và ồ ạ Không t n t

i K'

(cid:0) K sao cho K’+= Q+

ủ

ả

ộ

Ghi chú: ồ ộ ậ tính ngu n (TN) thu c T p ộ ả ấ ứ t c các thu c tính có ch a t ệ ở ế ấ v trái và không xu t hi n ấ ệ ở ế xu t hi n v ph i c a các ộ ụ ph thu c hàm và các thu c ệ ở ả ế ấ c v tính không xu t hi n ụ ủ ả ế ẫ trái l n v ph i c a các ph thu c hàm.

Let a relation R have three candidate keys A, B, and (C,D). Which of the following must not be correct. a) AB b) BA c) AC d) CAB

ệ

ậ

ấ ả

ủ ượ ồ

c đ quan h và t p pth nh sau:

ấ ả

ộ

ậ ộ T p thu c tính trung gian (TG) ứ ấ ả ộ t c các thu c tính xu t ch a t ế ẫ ệ ở ả ế hi n c v trái l n v ph i ụ ủ c a các ph thu c hàm.

Tìm t t c các khóa c a l Q(C,S,Z); F={CS(cid:0) Z; Z(cid:0) C} Giải:

TN = {S};

ủ ậ

ậ

ọ

G i Xi là các t p con c a t p TG:

TG = {C,Z}

Xi

khóa

DE and D (cid:0)

AB.

(cid:0)

(TN (cid:0) Xi) (TN(cid:0) Xi)+ Siêu khóa S

Q+

Trần Thi Kim Chi

Consider a relation R(A,B,C,D,E) with the following functional dependencies: ABC (cid:0) The number of superkeys of R is: a) 2 b) 7 c) 10 d) 12

SCZ

Q+

SCZ

Bài T pậ

ệ ậ ộ

1. Cho m t quan h R ={A, B, C, D, E, F, G, H, I, J} và t p ộ ph thu c hàm

ụ F = { A,B C A D, E B F F G, H D I, J

ệ

Trần Thi Kim Chi

ể ệ ấ } Yêu c u:ầ Tìm {A}+ ={D, E, I ,J } ủ Tìm khóa c a quan h R. ệ Tách quan h R thành BCNF. Ki m tra xem vi c tách trên có m t mát thông tin không?

Bài T pậ

ED , BD (cid:0) BD , ABC (cid:0) DH }

Trần Thi Kim Chi

1. Cho quan hệ R(ABCDEH) và tập các phụ thuộc hàm F = { AB (cid:0) CH , AC (cid:0) 2.1 : Tìm tất cả các khoá của R suy ra từ tập phụ thuộc hàm

Bài T pậ

ệ ậ ộ

ụ 2. Cho m t quan h R ={A, B, C, D, E, F, G, H, I, J} và t p ộ ph thu c hàm

G= { A,B  C B, DE, F A, D  G, H A I HJ}

ệ

Trần Thi Kim Chi

ể ệ ấ Yêu c u:ầ Tìm {A}+ ={D, E, I ,J } ủ Tìm khóa c a quan h R. ệ Tách quan h R thành BCNF. Ki m tra xem vi c tách trên có m t mát thông tin không?

Bài T pậ

ộ

ệ

ậ

ộ

3. Cho m t quan h R ={CourseNo, SecNo, OfferingDept, Credit_Hours, CourseLevel, InstructorSSN, Semester, Year, ụ Days_Hours, RoomNo, NoOfStudents} và t p ph thu c hàm: F ={ CourseNo  OfferingDept, Credit_Hours, CourseLevel; CourseNo, SecNo, Semester, Year Days_Hours, RoomNo, NoOfStudents, InstructorSSN; RoomNo, Days_Hours, Semester, Year  InstructorSSN, CourseNo, SecNo }

ệ

ệ ấ ẩ ạ

Trần Thi Kim Chi

ệ ề ạ ệ ể ấ Yêu c u:ầ ủ Tìm khóa c a quan h R. ộ Quan h trên thu c d ng chu n m y? Tách quan h v d ng 3NF. Ki m tra xem vi c tách trên có m t mát thông tin không?