KI M TRA Ể
H C PH N: THI T K C S D LI UỌ Ầ Ế Ế Ơ Ở Ữ Ệ
TH I GIAN: 90 phút Ờ
CÂU 1
a) Xác đnh m i quan h cao nh t gi a các t p ph thu c hàm sau, gi i thích.ị ố ệ ấ ữ ậ ụ ộ ả
F1 = {ABC, BADE, CAG}
F2 = {ABCDE, BAC, CDG}
b) Tìm ph c c ti u c a t p ph thu c hàm F ={Aủ ự ể ủ ậ ụ ộ BC, ACDE, DEBC}
c) Cho l c đ quan h R(A, B, C, D, E, G, H) và t p ph thu c hàm:ượ ồ ệ ậ ụ ộ
F = {AEC, CDAH, BEG}
S d ng thu t toán Lucchesi-Osborn đ tìm t t c các khóa c a l c đ quan ử ụ ậ ể ấ ả ủ ượ ồ
h R.ệ
Bài làm:
a)
F1 = {ABC, BADE, CAG}
F2 = {ABCDE, BAC, CDG}
+) F2 |= F1 = {ABC, BADE, CAG}
F2 |= ABC: AF2+ = ABCDEG BC =>F2 |= ABC
F2 |= B ADE: BF2+ = BACDGE ADE =>F2 |= B ADE
F2 |= CAG: CF2+ = CDG AG =>F2 | CAG
Do đó: : F2| ≠ F1 (1)
+) F1 |= F2 = {ABCDE, BAC, CDG}
F1 |= ABCDE: AF1+ = ABCDEG BCDE =>F1 |= ABCDE
F1 |= BAC: BF1+ = BADECG AC =>F1 |= BAC
F1 |= CDG: CF1+ = CAGBDE DG =>F1 |= CDG
Do đó: : F1|= F2 (2)
K t lu n: ế ậ
T (1) và (2) suy ra m i quan h cao nh t c a 2 t p ph thu c hàm trên làừ ố ệ ấ ủ ậ ụ ộ
F1|= F2
b)
Tìm ph c c ti u c a t p ph thu c hàm F ={Aủ ự ể ủ ậ ụ ộ BC, ACDE, DEBC}
B c 1ướ : M i ph thu c hàm trong F ch có m t thu c tính v ph iỗ ụ ộ ỉ ộ ộ ở ế ả
F ={A B, A C, AC D, AC E, DE B, DEC }
B c 2:ướ Lo i b các thu c tính d th a v tráiạ ỏ ộ ư ừ ở ế
+) ACD:
Xét A có d th a hay không:ư ừ
(AC \ A)+F = C+F = C D
V y A không ph i thu c tính d th aậ ả ộ ư ừ
Xét C có d th a hay không:ư ừ
(AC \ C)+F = A+F = ABCDE D
V y C là thu c tính d th a.ậ ộ ư ừ
T p F tr thànhậ ở F ={A B, A C, A D, AC E, DE B, DEC }
+) AC E:
Xét A có d th a hay không:ư ừ
(AC \ A)+F = C+F = C E
V y A không ph i thu c tính d th aậ ả ộ ư ừ
Xét C có d th a hay không:ư ừ
(AC \ C)+F = A+F = ABCDE E
V y C là thu c tính d th a.ậ ộ ư ừ
T p F tr thànhậ ở F ={A B, A C, A D, A E, DE B, DEC }
+) DE B
Xét D có d th a hay không:ư ừ
(DE \ D)+F = E+F = E B
V y D không ph i thu c tính d th aậ ả ộ ư ừ
Xét E có d th a hay không:ư ừ
(DE \ E)+F = D+F = D E
V y D là không ph i thu c tính d th a.ậ ả ộ ư ừ
+) DE C
Xét D có d th a hay không:ư ừ
(DE \ D)+F = E+F = E C
V y D không ph i thu c tính d th aậ ả ộ ư ừ
Xét E có d th a hay không:ư ừ
(DE \ E)+F = D+F = D C
V y D là không ph i thu c tính d th a.ậ ả ộ ư ừ
V y sau b c th 2 t p F làậ ướ ứ ậ
F ={A B, A C, A D, A E, DE B, DEC }
B c 3: ướ Lo i b các ph thu c hàm d th a :ạ ỏ ụ ộ ư ừ
+) Xét A B có d th a hay không:→ư ừ
A+F\{A B}→ = ACDEB B
V y A B d th a→ậ ư ừ
Khi đó:
F ={A C, A D, A E, DE B, DEC }
+) Xét A C có d th a hay không:ư ừ
A+F\{A C}→ = ADEBC C
V y A C d th a→ậ ư ừ
Khi đó:
F ={A D, A E, DE B, DEC }
+) Xét A D có d th a hay không:ư ừ
A+F\{A D}→ = AE D
V y A D không d th a→ậ ư ừ
+) Xét A E có d th a hay không:ư ừ
A+F\{A E}→ = AD E
V y A E không d th a→ậ ư ừ
+) Xét DE B có d th a hay không:ư ừ
DE+F\{DE B}→ = DEC B
V y ậDE B không d th aư ừ
+) Xét DE C có d th a hay không:ư ừ
DE+F\{DE C}→ = DEB C
V y ậDE C không d th aư ừ
K t lu nế ậ : Fct ={A D, A E, DE B, DEC }
c) Cho l c đ quan h R(A, B, C, D, E, G, H) và t p ph thu c hàm:ượ ồ ệ ậ ụ ộ
F = {AEC, CDAH, BEG}
S d ng thu t toán Lucchesi-Osborn đ tìm t t c các khóa c a l c đ quan ử ụ ậ ể ấ ả ủ ượ ồ
h R.ệ
Ta có: F = {AEC, CDAH, BEG}
U = ABCDEGH
+) Xác đnh m t khoá c a Rị ộ ủ
T = ABCDE , P = ACEGH
TP = ACE
K = (U \ P) (T P) = BD ACE = ABCDE
Xét: A T P:
(K\A)F+ =(ABCDE\A) F+= BCDE F+ = BCDEAH = U => K = K\A = BCDE
Xét: C T P:
(K\C)F+ =(BCDE\C) F+= BDE F+ = BDEG ≠ U => K = BCDE
Xét: E T P:
(K\E)F+ =(BCDE\E) F+= BCD F+ = BCDAHEG = U => K = K\E = BCD
K t lu n: K = BCDế ậ
+)Tìm các khóa còn l i c a R b ng đnh lí ạ ủ ằ ị Lucchesi-Osborn
F = {AEC, CDAH, BEG} , K = BCD
K = BCD AEC CDAH BEG
BCD BDAE - -
BDAE - - BDA
BDA - - -
K t lu n K = {BCD, BDAE, BDA}ế ậ
CÂU 2.
Cho l c đ quan h R=<U,F> trong đó t p các thu c tính U=ABCDEGH và t pượ ồ ệ ậ ộ ậ
ph thu c hàm F = {Hụ ộ G, ABH, DE}. Hãy ki m tra tính ch t b o toànể ấ ả
thông tin c a phép tách ủ = (ABCD, DEG, ABH) đi v i l c đ quan h R.ố ớ ượ ồ ệ
Bài làm:
U=ABCDEGH ( 7 thu c tính)ộ
F = {HG, ABH, DE}.
= (ABCD, DEG, ABH) (3 phép tách)
B c 1: Kh i t o b ng g m 7 c t và 3 hàngướ ở ạ ả ồ ộ
A B C D E G H