Bài tập lý thuyết CSDL quan hệ - bài tập phụ thộc hàm

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ệ

ề

ạ

ầ

7

2. BµI TËP VÒ ph THU C HÀM Ộ Ụ

I H C

ụ ọ ộ

Ụ   M C TIÊU C A BÀI NÀY GIÚP NG Ủ ƯỜ Ọ Hi u đ c t m quan tr ng c a lý thuy t c a ph thu c hàm ủ ễ V n d ng các thu t toán tính bao đóng, đ nh nghĩa suy di n ế ủ ị ậ

i thi u, bài toán thành viên ể ượ ầ ậ ụ ề ủ ố ể

ế

 ụ ậ

theo tiên đ , theo quan h , tìm ph t ệ i quy t các bài t p c th . đ gi ậ ụ ể ể ả Áp d ng các thu t toán đ gi ậ ứ ư ừ ế ộ

i quy t các bài t p liên quan: ể ả Tìm bao đóng, ch ng minh m t ph thu c hàm có d th a trong ụ ộ t p các ph thu c hàm không,... ộ ậ ụ

Ắ Ế

A/ NH C L I LÝ THUY T I. M T S Đ NH NGHĨA, TÍNH CH T Ạ Ộ Ố Ị Ấ

1. Đ nh nghĩa ph thu c hàm ụ ộ ị

cho U là m t t p thu c tính, m t ph thu c hàm trên U là ộ ộ ậ ụ ộ ộ

ị ộ

ạ Y, trong đó X,Y˝ U. ằ ệ ả

ộ ấ ộ ớ ụ ế

ậ ậ ộ

Đ nh nghĩa: m t phát bi u có d ng X ể Cho R là quan h trên t p thu c tính U, nói r ng quan h R tho mãn ậ ệ Y, n u v i 2 b b t kì trong R mà chúng gi ng ố ph thu c hàm X ộ nhau trên t p thu c tính X thì chúng cũng gi ng nhau trên t p thu c tính ố ộ Y, nghĩa là " u,v ˛ R, n u u.X=v.X thì u.Y=v.Y. ế

ộ ụ ậ ộ ộ

ậ ộ

ế ụ ặ ậ ậ ộ ị

Y là m t ph thu c hàm trên U thì ta nói t p thu c tính Y N u f= X ph thu c hàm vào t p thu c tính X (Y functional dependent on X ) ộ ho c t p thu c tính X xác đ nh hàm t p thu c tính Y (X functional ộ determines Y).

ộ ụ ụ ế ệ ả ộ

ụ ệ ế ả ộ

ộ Cho f là m t ph thu c hàm trên U, n u quan h R tho mãn ph thu c hàm f thì ta ký hi u R(f), n u R không tho mãn ph thu c hàm thì ta ký hi u ệ ø R(f).

ụ ằ

f ˛ ậ ộ ậ ụ ế ộ

ng quan h R tho mãn t p ph ỉ ế ả ậ ộ ả F ụ

Cho F là m t t p các ph thu c hàm trên U, nói r ng quan h R tho ệ ộ ớ " mãn t p ph thu c hàm F, ký hi u là R(F) n u và ch n u v i ệ ng đ thì R(f) hay nói m t cách t thu c hàm F n u nh nó tho mãn t ng ph thu c hàm trong t p đó. ế ươ ừ ươ ả ệ ộ ụ ư ậ ộ

Trang 1

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ệ

ề

ạ

ầ

7

ộ ặ a =(U, F) trong đó U là t pậ ồ

c đ quan h là m t c p Đ nh nghĩa: L ệ ượ ị h u h n các thu c tính còn F là t p các ph thu c hàm trên U. ụ ộ ữ ạ ậ ộ

ộ ố

ụ ả ạ " X, Y˝ U, Y˝ X, thì XY

Y và YZ ế

" X, Y˝ U, n u Xế  Y và " Z˝ U thì

ắ ầ " X, Y, Z, W ˝ U, n u Xế Y,

ả ạ ặ " X˝ U thì XX ấ

" X, Y, Z ˝ U, n u có X 2. M t s tính ch t c a ph thu c hàm: ộ ấ ủ 1) Tính ch t ph n x : ấ ấ ắ ầ " X, Y, Z˝ U, n u có X 2) Tính ch t b c c u: thì XZ 3) Tính ch t gia tăng: ấ XZYZ 4) Tính ch t t a b c c u: ấ ự YZ W thì XZW 5) Tính ch t ph n x ch t: 6) Lu t tách: ậ ế YZ thì có:

XY XZ

" X, Y, Z ˝ U, n u có X  Y và XZ thì có ế

7) Lu t h p: ậ ợ XYZ 8) Tính ch t c ng tính: ấ ộ " X, Y, Z, W ˝ U, n u Xế Y, Z W thì

XZYW

ệ

˝ Y thì Y X

3. H tiên đ Amstrong ề ả ạ " X,Y˝ U, n u Xế F1 - Lu t ph n x ậ ắ ầ " X, Y, Z ˝ U n u cóế F2 - B c c u

thì XZ

XY YZ

F3 - Lu t gia tăng " X, Y, Z ˝ U, n u có X ậ ế Y thì XZYZ

4. Đ nh nghĩa suy d n theo h tiên đ ị ệ ẫ

ậ ộ ộ

ề Cho F là t p ph thu c hàm trên U, f là m t ph thu c hàm trên F theo h tiên ộ ụ c t U ( f có th không thu c F), nói r ng f suy d n đ ượ ừ ụ ộ ể ệ ằ ẫ

Trang 2

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ệ

ề

ầ

ạ

7

t p F ể ế ư c t ượ ừ ậ

ậ ề ậ ủ ệ ệ ộ ố ữ ạ ầ

ậ

F thì F├ f

c suy d n t t p F theo ậ ấ ả t c các ph thu c hàm đ ụ ẫ ừ ậ ượ ộ

˝ F+

ế ộ

c g i là bao đóng c a t p ph thu c hàm F, n u F ọ ộ ậ ủ ậ ụ ủ ầ

đ Amstrong và kí hi u là F├ f n u nh f có th nh n đ ề sau m t s h u h n l n áp d ng các lu t c a h tiên đ Amstrong. ụ Nh n xét: f ˛ V iớ " + là t p t Kí hi u Fệ h tiên đ Amstrong. ề ệ Ta th y Fấ + =F thì ta nói F+ đ ụ ượ F là m t t p đ y đ các ph thu c hàm, đôi khi ta còn nói F là t p ậ ộ đóng. 5. Đ nh nghĩa suy d n theo quan h ị ệ ẫ

ộ ậ ụ ậ ộ

ộ ộ ể

ộ ẫ ừ ậ ằ ỉ ế ộ ế ệ

Cho F là m t t p các ph thu c hàm trên t p thu c tính U, f là ượ c m t ph thu c hàm trên U, (f có th không thu c F), nói r ng f đ ụ suy d n t ọ t p F theo quan h và ký hi u F ╞f, n u và ch n u v i m i ệ ớ quan h R trên U, n u R tho mãn F thì R cũng tho mãn f. ả ệ ế ả

c suy d n t t p F theo ệ ậ ấ ả t c các ph thu c hàm đ ụ ộ ượ ẫ ừ ậ

Ký hi u F* là t p t quan h .ệ F*={f:XY | X,Y˝ U, F╞f}

ộ ˝ đây ta suy ra F F*. ˝ ạ ệ

ừ G*. ộ

Tính ch t c a F*: ấ ủ Cho F và G là hai t p ph hàm trên t p thu c tính U khi đó ta có: ụ ậ ậ f ˛ ớ " F thì F ╞f t 1. Tính ph n x : V i ả G thì F* ˝ 2. Tính đ n đi u: N u F ế ơ 3. Tính lu đ ng: V i m i t p ph thu c hàm F thì ta luôn có (F*)*=F*. ụ ớ ỹ ẳ 6. Bao đóng c a t p thu c tính ủ ậ ọ ậ ộ

˝ U, bao đóng c a t p thu c ộ ủ ậ

+ đ

ụ tính X, kí hi u là X ậ ệ ị

Cho t p ph thu c hàm F trên U, X ộ c xác đ nh nh sau: ư ượ X+= { A | A˛ U và XA˛ F+ }

* Thu t toán tìm bao đóng c a m t t p thu c tính ộ ậ ủ ộ ậ

Input a = (U,F), X˝ U Output X+ =?

(0), X(1), X(2),... theo quy n p nh sau

Thu t toán ậ

Ta xác đ nh dãy X ị ư ạ

Trang 3

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ệ

ề

ạ

ầ

7

s r ng đã xây d ng đ c th i t c là đã ự c đ n b ượ ế ướ ứ ứ

c i+1 nh sau 1. Đ t Xặ (0)=X 2. Gi ả ử ằ t Xế (i) (i>=0) bi 3. Xây d ng ti p b ự ế ướ

ư Z(i) trong đó X(i+1)= X(i) ¨

˛

X

j

X

Y

Y F (1) ˝ Xi (2) J ¸ X(i) (3)

Z(i) = ¨ Yj v i đi u ki n : ề ệ ớ

(i) chính là h p c a các v ph i c a các ph thu c hàm ụ ư c mà có v ph i ch a ế

Vì v y Zậ ậ ợ ủ ậ ả ủ ướ ế ủ ậ ộ ả ế

c thêm vào.

trong t p F mà có v trái là t p con c a t p tr đ ượ đi u ki n (3) ch có tác d ng tăng t c đ tính toán ụ ề ố ộ ệ ỉ

ậ

ở

i ch s i nào đó đ X ộ ể (i)= X(i+1) (*), g i i là ch s nh nh t khi đó X ị ặ ỉ ố ỉ ố ấ ọ ỏ

Nh n xét: X(0), X(1), X(2),... là m t dãy không gi m và b ch n trên b i U, do đó t n ồ ả + = t ạ X(i) hay khi X(i) = U thì X+ = X(i) = U.

ộ 7. Ph thu c hàm d th a ư ừ

ụ ộ Cho F là m t t p các ph thu c hàm trên U, f là m t ph thu c ụ

ụ + =F+ hàm c a F t c f ộ ư ừ ứ

ộ ế ư ế c g i là d th a trong F n n ư ừ ươ ượ

nó suy d n đ ộ ậ ˛ F, f đ ủ Hay có th nói t ể c t ẫ ượ ừ ậ c g i là d th a trong F n u nh (F-f) ượ ọ ng đ ọ ươ ụ ng f đ t p F sau khi đã b đi ph thu c hàm f. ỏ ộ

Thu t toán thành viên ậ

Input

ậ ụ ộ

- T p ph thu c hàm F - f ˛ F

Output

ư ừ

- True n u nh f là d th a trong F - False n u nh f là không d th a trong F ư ừ ư ư ế ế

Method

Trang 4

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ề

ệ

ạ

ầ

7

ỏ ọ ạ ậ

„f

1) t m xoá f kh i F, g i G là t p thu đ thì chuy n qua b G=F-f, n u Gế ướ ể thúc thu t toán và k t lu n f là không d th a trong F ậ ế ậ c ượ c 2, còn không thì k t ế ư ừ + 2) Gi s f=X ả ử Y n u G├ f t c Y ế ứ ư ừ thì f là d th a

c l ượ ạ ư ừ + và so sánh v i t p con Y ta có ngay câu tr ˝ X G i f là không d th a. ớ ậ ả

+ hay không.

ﬁ ỉ ầ Y có thu c vào F ộ

trong F còn ng Nh v y, ta ch c n tính X l ờ 8. Ph thu c hàm d th a ư ừ ư ậ i X ụ ộ

II. CÁC VÍ DỤ

ệ a c đ quan h = (U,F) v iớ

Ví d 1:ụ Cho l ượ ồ U = ABCDEGH F={ BC ADE, AC BDG, BE ABC, CD BDH, BCH ACG}

ng h p ườ ợ

Hãy tính X+ trong các tr a) X=BD b) X=ABE c) X=CDG

F =BD + =X=BD

(ADE ¨

Z(0) =ABE ¨ ABC=ABCE Z(1) =ABCE ¨ Z(2) = ABCDEG ¨ BDG)=ABCDEG BDH=ABCDEGH=U

iả Gi a) đ t X(0)=BD (=X) ặ X(1) = X(0) ¨ Z(0) =BD ¨ Suy ra X(0)= X(1) v y Xậ b) đ t X(0)=ABE (=X) ặ X(1) = X(0) ¨ X(2) = X(1) ¨ X(3) = X(2) ¨ +=U V y Xậ

ụ

Gi ả ử Hãy cho bi Ví d 2 :ụ Áp d ng bài toán thành viên YW, XWZ, ZY, XYZ} s có t p F={X ậ t XYế Z có d th a trong F hay không? ư ừ

Trang 5

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ệ

ề

ầ

ạ

7

G ( bao đóng c a XY trong t p G)

iả ạ Z ra kh i Fỏ

ủ

G= XYWZ th nên Z

˝ (XY)+ ế ụ

Gi 1) T m th i xoá XY ờ G:=F-{XYZ}={XYW, XWZ, ZY} 2) Tính (XY)+ ậ ta có (XY)+ G hay G├ (XYZ) th nên ph thu c hàm XY ế Z là d th a trong F. ư ừ ộ

ụ ề

III. M T S L U Ý Ộ Ố Ư  Tiên đ Amstrong. Áp d ng h tiên đ amstrong trong các bài toán ề ệ ch ng minh.

 Ph thu c hàm theo quan h và theo tiên đ , bao đóng c a t p các ủ ậ ề ộ

thu c tính và c a t p các ph thu c hàm. ủ ậ ộ ệ ụ ứ ụ ộ

Ẫ

CD, ACEBG, BCD AE, CH ậ ậ ộ ụ

˛ B/ BÀI T P M U Ậ Bài s 1:ố Cho t p thu c tính U=ABCDEGH Cho t p ph thu c hàm F={ AB ộ DG} f=BCDH AG, h i r ng F├ f hay không (f F+) ? ỏ ằ

ẫ ướ

ệ ầ

H ng d n: ụ ế Áp d ng h tiên đ Amstrong đ ch ng minh, đ u tiên c n làm ầ ầ ượ t ệ ể ứ ầ ề ụ ứ ấ ộ

xu t hi n v trái c a ph thu c hàm c n ch ng minh sau đó l n l ủ áp d ng 3 tiên đ đ suy ra ĐPCM. ề ể ụ

Gi iả

ấ ả ạ

ả ạ

ấ ắ ầ

thi

BCDH BCD (1) ( tính ch t ph n x ) BCDAE ( gt) (2) BCDACE ( gia tăng) (3) ACE A (ph n x ) (4) Suy ra BCDH A theo tính ch t b c c u(5) ACE BG (6) gi t ế ả BGG (7) ph n xả ạ Suy ra ACE G(8) b c c u ắ ầ Suy ra BCDH G (9) b c c u ắ ầ

Trang 6

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ề

ệ

ầ

ạ

7

ậ

T (5) và (9) theo lu t c ng tính ( lu t ghép) ậ ộ ừ Suy ra BCDH AG ˛ F+ ( đpcm)

Bài s 2:ố

ng h p ợ

Cho a =(U,F); U=ABCDEGH F={ ABBCP, EBGH, ACD BG, DAEH} Hãy tính X+ trong các tr ườ a) X=AC b) X=CD c) X=ABG

t các b c c a thu t toán tính bao đóng. H ng d n: ướ Áp d ng l n l ụ ẫ ầ ượ ướ ủ ậ

Gi iả

= X(0) nên X+=AC

AEH =ACDEH ( BGH ¨ BG) = ACDEH ¨ ( BGH ¨ BG) =

AEH)= ABCDEGH =U

a) Vì X=AC X(0)= X=AC X(1) = X(0) ¨ f b) Vì X=CD X(0)=X=CD X(1) = X(0) ¨ X(2)= X(1)¨ ABCDEGH =U Do X(2)=U nên X+=U c) Vì X=ABG X(0)=X=ABG X(1)= ABG ¨ BCD=ABCDG X(2)= ABCDG ¨ (BCD ¨ BG ¨ Do X(2)=U nên X(3)= X(2) hay X(3)=U

C/ BÀI T P T GI I Ậ Ự Ả

Bài t p 1:ậ Cho l c đ quan h ượ ồ ệ a =(u, F) v iớ

Trang 7

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ệ

ề

ạ

ầ

7

ậ D, CDﬁ ằ ụ ộ E, CEﬁ ớ ế ả

U=ABCDEGH và t p ph th c hàm C, Bﬁ F={AB ﬁ GH, Gﬁ A} f=ABﬁ E, ch ng minh r ng v i m i quan h R trên U n u R tho F thì ệ ọ ứ R cũng tho f.ả

ượ ồ

Bài t p 2:ậ c đ quan h (=(U, F) v i Cho l ớ ệ U=ABCDEGHIJ và t p ph th c hàm ậ F={ABﬁ J, BEﬁ H} f=ABﬁ GH, ch ng minh r ng f suy d n đ c t F ụ ộ I, Eﬁ G, GIﬁ ằ E, AGﬁ ứ ẫ ượ ừ

ượ ồ

c đ quan h (=(u, F) v i ớ ệ ậ ụ ộ

Bài t p 3ậ Cho l U=ABCDEGH và t p ph th c hàm F={ABﬁ C, Bﬁ D, CDﬁ E, CEﬁ GH, Gﬁ A}

Hãy ch ng minh ứ a. ABﬁ E b. BGﬁ C c. ABﬁ G

c đ quan h (=(u, F) và t p ph th c hàm ụ ộ ậ

I, Eﬁ G, GIﬁ H}

ﬁ GH suy d n đ c t F Bài t pậ 4 Cho l ệ ượ ồ F={ABﬁ E, AGﬁ I, BEﬁ Ch ng minh r ng AB ằ ứ ẫ ượ ừ

c đ quan h (=(u, F) và t p ph th c hàm ượ ồ ụ ộ ậ

Bài t p 5ậ Cho l ệ F={ABﬁ C, Bﬁ D, CDﬁ E, CEﬁ GH, Gﬁ A} Ch ng minh r ng AB ﬁ E v à ABﬁ G suy d n đ c t F ứ ằ ẫ ượ ừ

ụ ộ

Bài t p 6ậ Tìm ph không d c a t p ph thu c hàm ư ủ ậ ủ F={Aﬁ C, ABﬁ C, Cﬁ DI, ECﬁ AB, EIﬁ C}

Trang 8

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ệ

ề

ạ

ầ

7

ﬁ D suy d n đ c t ứ ẫ ượ ừ

Bài t p 7ậ Cho F={Aﬁ B, Cﬁ D} v i Cớ (cid:204) B, hãy ch ng minh A F

ﬁ Y đ ộ ượ ọ ộ c g i là d th a trong t p ph thu c ư ừ ụ ậ

ộ ư += (F-{Xﬁ Y})+

ﬁ Z có d th a trong F hay không Bài t p 8ậ M t ph thu c hàm X ụ hàm F n u nh F ế cho F={Xﬁ YW, XWﬁ Z, Zﬁ Y, XYﬁ Z} t ph thu c hàm XY hãy cho bi ộ ụ ế ư ừ

Bài t p 9ậ Tìm ph không d c a ư ủ ủ F={ Xﬁ YZ, ZWﬁ P, Pﬁ Z, Wﬁ XPQ, XYQﬁ YW, WQﬁ YZ}

c đ quan h R(ABCD) v à F={A ﬁ B, BCﬁ D}

t các ph th c hàm nào d c t F Bài t p 10ậ Cho l hãy cho bi ướ i đây có th suy d n đ ể ẫ ượ ừ ệ ụ ộ ượ ồ ế

1. ACﬁ D 2. Bﬁ D 3. ADﬁ B

Bài t p 11ậ F={XYﬁ W, Yﬁ Z, WZﬁ P, WPﬁ QR, Qﬁ X} F ch ng minh r ng XY ﬁ P suy d n đ c t ẫ ượ ừ ứ ằ

ư ừ ụ

Bài t p 12ậ Lo i b các ph thu c hàm d th a trong t p ậ ộ ạ ỏ F={Xﬁ Y, Yﬁ X, Yﬁ Z. Zﬁ Y, Xﬁ Z, Zﬁ X}

Bài t p 13ậ cho F={XYﬁ W, Yﬁ Z, WZﬁ P, WPﬁ ﬁ Q suy d n đ ch ng minh r ng XY QR, Qﬁ X} F c t ứ ằ ẫ ượ ừ

Bài t p 14ậ Cho F={Aﬁ BC, Eﬁ C, Dﬁ AEF, AFﬁ B,AFﬁ D}

Trang 9

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ề

ệ

ầ

ạ

7

ph thu c hàm AF(B có d th a trong F không ư ừ ụ ộ

ﬁ Y ˛ F , A˛ X, thu c tính A đ ộ ượ ọ c g i là d th a n u ư ừ ế

Y ˛ F+

ư ừ ạ ỏ ậ

Bài t p 15ậ N u Xế { X- A } ﬁ hãy lo i b các thu c tính d th a trong các t p sau: ộ a. F={Xﬁ YW, XWﬁ Z, Zﬁ Y, XYﬁ Z } b. F={Aﬁ BC, Eﬁ C, Dﬁ AEF, ABFﬁ BD }

ề ứ ử ụ ậ ủ ệ

ﬁ Y và YZﬁ W thì XZﬁ W

ạ ặ

ộ

ﬁ Y và Zﬁ W thì XZﬁ YW ﬁ Y và Xﬁ Z th ì Xﬁ YZ

ế ế ﬁ YZ thì Xﬁ Y v à Xﬁ Z

ﬁ YZ, Zﬁ VW thì Xﬁ YVW Bài t p 16ậ ấ S d ng các lu t c a h tiên đ Amstrong ch ng minh các tính ch t sau: a. Tính t a b c c u: N u X ế ự ắ ầ ﬁ X b. Tính ph n x ch t X ả c. Tính c ng tính : N u X d. Tính ch t h p : N u X ấ ợ e. Tính tách : N u Xế f. Tính tích lu : N u X ế ỹ

ệ a =(U, F) v i U=ABCDEG và ớ ượ ồ

Bài t pậ 17 c đ quan h Cho l F={Aﬁ C, BCﬁ D, Dﬁ E, Eﬁ A}. Hãy tính

a) (AB)+ b) ((DE)+A)+

c đ quan h ệ a =(U, F) v i U=ABCDEG và ượ ồ ớ

Bài t p 18ậ Cho l F={Bﬁ C, ACﬁ D, Dﬁ G, AGﬁ E} hãy cho bi tế

a) ABﬁ G˛ F+ b) BDﬁ AD˛ F+

Bài t pậ 19

Trang 10

NH P MÔN CSDL QUAN H

Ậ

Ệ

So n b i b môn Công ngh ph n m m - 200

ở ộ

ề

ệ

ạ

ầ

7

c đ quan h ớ ượ ồ ệ a =(U, F) v i U=ABCDEGH

c t F

ẫ ượ ừ ế ả ớ

ả

Cho l F={ABﬁ GH, GDﬁ AHE, Cﬁ AGH, HEﬁ BC } a) tính (CE)+ b) tính (CD)+ ﬁ DH không suy d n đ c) Ch ng minh r ng ABE ằ ứ d) Ch ng minh r ng v i m i quan h R trên U N u R tho F thì R cũng ằ ệ ọ ứ ﬁ BHE tho ACD e) Ch ng minh r ng F├ ABE ằ ứ

= (U, F) v i U = ABCDEGH và ượ ồ ệ a c đ quan h ớ

CH , ACD ﬁ

BEG } . ứ ỏ ph thu c hàm f ộ

Bài t p 20ậ Cho l F = { B ﬁ B ng các lu t c a h tiên đ Armstrong hãy ch ng t ằ = BD ﬁ AEG , ABE ﬁ ậ ủ ệ CGH suy d n đ ụ t p các ph thu c hàm F. ề c t ẫ ượ ừ ậ ụ ộ

= (U,F) v i U = ABCDEGH và ượ ồ ệ a c đ quan h ớ

DE}

ﬁ ộ BCD, ABC ﬁ DEG. Hãy ch ra r ng f có th ỉ ằ ể

ụ c t Bài t p 22ậ Cho l BD , DG ﬁ BEG , CEH ﬁ F = { AE ﬁ và m t ph thu c hàm f = ACE ộ d n đ ẫ ượ ừ ậ t p F theo các lu t c a h tiên đ Armstrong. ậ ủ ệ ề

ượ ồ ệ a c đ quan h ậ

ủ ậ ứ ự

ﬁ c suy d n t YZ đ ệ ượ ộ ỉ

ﬁ Z cũng suy d n đ Y và X ﬁ t p F. c t Bài t p 23ậ ộ = (U, F) và X,Y,Z là các t p con c a t p thu c Cho l tính U. D a vào các lu t c a h tiên đ Armstrong hãy ch ng minh ậ ủ r ng ph thu c hàm X t p F khi và ch khi các ụ ằ ph thu c hàm X ộ ề ẫ ừ ậ ẫ ượ ừ ậ ụ

= (U,F) v i U = ABCDEGH và ượ ồ ệ a c đ quan h ớ

BEG , CEH ﬁ BD , DG ﬁ DE}

ﬁ ộ ằ ẫ ượ c

t p F b ng vi c ng d ng các lu t c a h tiên đ Armstrong. Bài t p 24ậ Cho l F = { AE ﬁ và m t ph thu c hàm f = ACE ụ ộ t ằ ừ ậ ệ ứ ụ BCD, ABC ﬁ DEG. Hãy ch ra r ng f d n đ ỉ ề ậ ủ ệ