ươ
Môn C S D LI U Ph thu c Ch
ng 5:
Ơ Ở Ữ Ệ ộ ụ ụ ộ ố ứ hàm và m t s ng d ng
ộ
N i dung
Ụ
Ộ
ụ
ộ
ị
ệ ậ ẫ
ấ ủ
ộ
1. PH THU C HÀM Đ nh Nghĩa Ph Thu c Hàm M t s tính ch t c a ph thu c hàm h lu t d n ụ
ộ ố armstrong
Ộ
Ụ
Ủ
Ủ
Ậ
2. BAO ĐÓNG C A T P PH THU C HÀM F & C A
Ậ
Ộ T P THU C TÍNH X
ủ ậ
ụ
ộ
ộ
Bao đóng c a t p ph thu c hàm F Bao đóng c a t p thu c tính X ủ ậ
Ậ
3. THU T TOÁN TÌM BAO ĐÓNG F+ VÀ X+, BÀI
TOÁN THÀNH VIÊN
ộ ậ
ủ
ậ
ộ
Bài toán thành viên Thu t toán tìm bao đóng c a m t t p thu c tính (X) 2
ộ
N i dung (tt) Ể Ủ Ố
Ộ Ậ Ộ Ủ Ụ 4. PH T I THI U C A M T T P PH THU C HÀM
ụ ể ậ ộ ố T p Ph Thu c Hàm T i Thi u
ụ ậ ộ ươ T p Ph Thu c Hàm T ươ ng Đ ng
ộ ậ ủ ố ủ ụ ể ậ ộ Thu t Toán Tìm Ph T i Thi u C a M t T p Ph Thu c Hàm
Ủ ƯỢ Ồ Ộ Ố Ậ Ệ C Đ QUAN H M T S THU T TOÁN
ị
5. KHÓA C A L TÌM KHÓA Đ nh Nghĩa ộ ượ ồ ủ ệ ậ ộ Thu t toán tìm m t khóa c a m t l c đ quan h Q
ấ ả ộ ượ ủ ậ ồ Thu t Toán Tìm T t C Các Khóa C a M t L ệ c Đ Quan H
Ủ ƯỢ Ồ Ệ Ẩ Ạ C Đ QUAN H
ạ ẩ
6. D NG CHU N C A L D ng chu n 1, 2, 3 D ng chu n Boyce Codd ẩ
ạ 3
Ụ
Ộ
ộ
1. PH THU C HÀM Ph thu c hàm (functional dependancy) là m t công c dùng đ ể
ụ ể ộ ễ ẹ ộ ộ ụ ứ bi u di n m t cách hình th c các ràng bu c toàn v n.
ụ ộ ị Đ nh Nghĩa Ph Thu c Hàm
Cho l
1,A2,…,An} là t p các thu c tính. X,
ớ ậ ộ
ệ ượ ồ c đ quan h Q v i {A ậ ủ ỗ
ụ ớ ộ
ệ ế ộ
(cid:0) ệ ộ ấ ỳ Y Y là hai t p con khác r ng c a Q. ế ị Ta nói X xác đ nh Y (hay Y ph thu c hàm vào X) n u v i r là m t ộ 1,t2 b t k thu c r mà t 1.X = t2.X ==> quan h trên Q và n u hai b t t1.Y = t2.Y. Khi đó ta ký hi u là X
(cid:0) ượ ọ ụ ể ộ X đ c g i là ph thu c hàm hi n nhiên.
Ph thu c hàm X ộ i ta th
ụ ườ ườ ể ỉ ậ ụ ộ ị
ữ ạ ể ố
1, f2, .., fm.
ủ ộ ng ng dùng F đ ch t p các ph thu c hàm đ nh nghĩa ụ ữ ạ trên Q. Vì Q h u h n nên F cũng h u h n, ta có th đánh s các ph thu c hàm c a F là f
Quy
ụ ả ộ c r ng ch c n mô t các ph thu c hàm không hi n nhiên
ỉ ầ ụ ể ộ ầ ượ ể ể c ng m hi u là đã có
ướ ằ ậ trong t p F (các ph thu c hàm hi n nhiên đ trong F}.
4
Ụ
Ộ 1. PH THU C HÀM (tt)
ệ ậ ẫ ấ ủ ộ ố ụ ộ M t s tính ch t c a ph thu c hàm h lu t d n armstrong
Đ có th xác đ nh đ ượ ể ệ
ể ị
ừ ậ ộ c các ph thu c hàm khác t ồ ề ộ ụ ụ t p ph thu c ậ hàm đã có, ta dùng h tiên đ Armstrong (1974), g m các lu t sau:
(cid:0) ớ v i X,Y,Z,W Q+
ậ ả ạ 1. Lu t ph n x :
2. Lu t thêm vào:
ậ
3. Lu t b c c u:
ậ ắ ầ X (cid:0) X (cid:0) X (cid:0) X Y ==> XZ (cid:0) Y, Y (cid:0) YZ Z ==> X (cid:0) Z
4. Lu t b c c u gi
ậ ắ ầ Y, WY (cid:0) Z ==> XW (cid:0) Z
5. Lu t h p:
ậ ợ
6. Lu t phân rã:
ậ ả : Cho X (cid:0) Cho X (cid:0) Cho X (cid:0) Y, X (cid:0) Y, Z (cid:0) Z ==> X YZ Y ==> X (cid:0) Z
ệ ề ượ ọ ệ ậ ẫ (các h tiên đ 1,2,3 đ c g i chung là H lu t d n Armstrong)
5
2. BAO ĐÓNG
ủ ậ ụ ộ Bao đóng c a t p ph thu c hàm F
Bao đóng c a t p ph thu c hàm F (th ụ
ủ ậ ườ ụ ậ ng ký hi u là F+) là t p
ể ộ ừ ệ ự ộ t c các ph thu c hàm có th suy ra t ề F d a trên các tiên đ
ợ ấ ả h p t Armstrong.
ệ ượ ồ ệ ậ c đ quan h Q(A,B,C,D) và t p F
Ví d :ụ Cho r là quan h trên l ư c cho nh sau:
C; A (cid:0) B; B (cid:0) D ; B (cid:0) C; A (cid:0) D} D ; B (cid:0) D;A (cid:0) BD; A (cid:0) BCD; A (cid:0) ượ đ B; B (cid:0) F = {A (cid:0) khi đó F+= { A (cid:0)
CD; A (cid:0) BC; B (cid:0) CD;….}
C; A (cid:0) Rõ ràng F (cid:0) F+
ấ ủ ậ
Các tính ch t c a t p F+ ọ ậ ả
F+
(cid:0)
ạ ệ
ơ
ộ G+ ộ
ớ ế ớ
ọ ậ
ụ
(cid:0) Tính ph n x : V i m i t p ph thu c hàm F+ ta luôn luôn có F ụ G thì F+ (cid:0) (cid:0) Tính đ n đi u: N u F (cid:0) Tính lũy đ ng: V i m i t p ph thu c hàm F ta luôn luôn có F++ = F+. ẳ
(cid:0)
6
2. BAO ĐÓNG (tt)
ủ ậ
ộ
Bao đóng c a t p thu c tính X
ệ
ượ ồ
ệ
ả ử
s F
Cho r là quan h trên l
ụ
ậ
ộ là t p các ph thu c hàm trong Q, X
c đ quan h Q. gi Q+.
ệ
Bao đóng c a t p thu c tính X đ i v i F ký hi u là
ủ
ệ
ố ớ ộ ề
ậ ấ ả ự
t c các thu c tính A c a Q X d a vào h tiên đ Armstrong và
ụ
ủ ậ ộ X+ (ho c Xặ F) là t p t + ừ ượ c suy ra t đ ộ các ph thu c hàm trong F. A (cid:0) Q và X (cid:0)
X+ = {A : A (cid:0)
F+}
(cid:0)
7
2. BAO ĐÓNG (tt)
ủ ậ
ộ
ụ
Bao đóng c a t p thu c tính X – Ví d
EG; B (cid:0)
D; G (cid:0)
E};
C; A (cid:0)
Q(A,B,C,D,E,G); F={A (cid:0) X={A,B};
Y={C,G,D}
Thì X+ = {A,B,C,D,E,G};
Y+ = {C,G,D,E}
ự ư ậ
T
ng t
+, t p bao nh t p bao đóng c a t p PTH F ứ
ủ ậ ầ ử ủ
ứ
ươ đóng X+ cũng ch a các ph n t
c a X
ậ +, t c là X 8
(cid:0)
X+.
2. BAO ĐÓNG (tt)
ủ ậ
ộ
ụ
Bao đóng c a t p thu c tính X – Ví d
ậ
ộ
ủ ậ N u X,Y là các t p con c a t p thu c tính Q thì ta có
Y thì X+ (cid:0)
Y+
(cid:0)
(cid:0)
ế ấ các tính ch t sau đây: X (cid:0) (cid:0) Tính ph n x : ạ ả X+ (cid:0) Tính đ n đi u: ế ệ ơ N u X (cid:0) Tính lũy đ ng:ẳ X++ = X+ (XY)+ (cid:0) X+Y+ (X+Y)+ = (XY+)+ = (X+Y+)+
X+
F+ (cid:0) Y(cid:0) Y+ (cid:0) Y (cid:0) X+ và X+ (cid:0) X (cid:0)
Y (cid:0) X+ X Y và Y (cid:0)
X
(cid:0) X (cid:0) (cid:0) X (cid:0) (cid:0) X (cid:0) (cid:0) X+ = Y+ (cid:0)
(cid:0)
9
3. TT TÌM BAO ĐÓNG F+ VÀ X+
Bài toán thành viên
ượ ị
c đ nh nghĩa thông qua
+ đ
ấ ằ ọ
ứ ộ
ụ
ướ ậ ộ
ị
c t p các PTH F và m t ph thu c hàm c ượ
F+ ? bài toán này đ
ọ
Trên đây ta nh n th y r ng X ậ ế ề ộ ấ F+. M t v n đ quan tr ng khi nghiên c u lý thuy t ộ CSDL là: Cho tr ẳ f, có hay không m t kh ng đ nh f g i là bài toán thành viên.
ỏ
ơ
Đ tr l ể ả ờ ả
i câu h i này (bài toán thành viên) không đ n ể ấ ớ ư ặ
ấ
ỏ
gi n, vì m c dù F là r t nh nh ng F
+ thì có th r t l n.
Tuy nhiên đ gi
(cid:0)
ể i bài toán thành viên, chúng ta có th ủ ậ
ấ
+. đó là tính ch t X
ỉ ầ
ể ả ấ Y (cid:0)
X . Do v y ch c n tính X
F+ (cid:0)
(cid:0)
i X
Y (cid:0) ế ơ
ượ
c gi
+ đ
dùng tính ch t 6 c a t p bao đóng X Y (cid:0) ậ ả ờ ậ t p Y, ta có ngay câu tr l ả ệ đó, vi c tính X
+ và so sánh v i ớ F+ hay không ? Do ề ơ ấ ả i quy t đ n gi n h n r t nhi u. 10
(cid:0)
ộ ậ
ộ
ậ
3. TT TÌM BAO ĐÓNG F+ VÀ X+ (tt) ủ Thu t toán tìm bao đóng c a m t t p thu c tính (X)
ộ ứ ạ
ủ
ộ
ớ
(đ ph c t p O(N2), v i N là s thu c tính c a Q)
ữ ệ
Q+
D Li u Vào
ữ ệ
ố Q, F, X (cid:0) X+
Đ t Xặ
+ = X
D Li u Ra B c 1: ướ B c 2: ướ
Temp = X+ V (cid:0) F X+ thì V
(cid:0)
B c 3: ướ
ế
ậ
N u Xế ế
X+ chính là k t qu c n tìm và k t thúc thu t toán. Ng
tr l
c 2.
+=Temp thì ả ầ ở ạ ướ i b
ượ ạ i c l
f U (cid:0) Neáu U (cid:0) X+ = X+ (cid:0)
11
ớ ộ ứ ạ
ế
ự
ề
ả
ộ
Xây d ng m ng m t chi u COUNT ụ
ủ
ế
ộ
ố
ộ
3. TT TÌM BAO ĐÓNG F+ VÀ X+ (tt) ậ Thu t toán tìm bao đóng v i đ ph c t p tuy n tính B c 1: ướ ớ V i COUNT(i) là s thu c tính v trái c a ph thu c hàm th iứ B c 2: ướ
ỉ ố
LIST(A) = {X (cid:0)
ớ ả Xây d ng m ng LIST v i F, A (cid:0) ư
ự Y| (cid:0)
X} (l u ch s PTH)
+
ộ
B c 3: ướ B c 4: ướ
ộ ế
X
(cid:0) (cid:0)
Y
ạ
ộ
ầ ử ủ
ạ
Y| đi m t n u A Y| = 0 thì X+ = X+ (cid:0) ế ế c a X
ừ + thì d ng l
ọ ầ
X+ = X ọ M i thu c tính A X ả Gi m COUNT|X ế N u COUNT|X ế ệ i duy t thu c tính k ti p trong X+ cho đ n khi Quay l ả ế ệ ế nào duy t h t m i ph n t i. K t qu X+ là bao đóng c n tìm. 12
(cid:0)
Ộ Ậ
Ủ Ố
Ủ
Ể
4. PH T I THI U C A M T T P PTH
ụ
ộ
ố
ể
ậ
T p Ph Thu c Hàm T i Thi u
ầ ư
ậ
ể ụ ụ ế ế ơ ở ữ ệ ể Đ có th ph c v quá trình thi t k c s d li u, c n đ a ể ố ệ i thi u. ra thêm khái ni m t p PTH t
ề ượ
ụ
B đ : M i t p các ph thu c hàm F đ u đ
ỗ ậ ộ
ả ủ
ụ ỉ ồ
ộ
ộ ủ ở ậ ổ ề c ph b i t p ộ ụ ế các ph thu c hàm G mà v ph i c a các ph thu c hàm ộ G ch g m m t thu c tính.
ụ
ộ
ố
ể
ỏ
F đ
ế i thi u n u F th a
c g i là m t t p ph thu c hàm t ệ
ộ ậ ề
ượ ọ ờ ồ đ ng th i ba đi u ki n sau:
ộ ỉ F và Z (cid:0)
ả ủ X (cid:0)
ộ X mà: F + = (F (cid:0) (X (cid:0)
A (cid:0)
A) (cid:0)
ế (a) V ph i c a F ch có m t thu c tính. (b) Không (cid:0) (Z (cid:0)
X (cid:0)
A (cid:0)
F mà: F + = (F (cid:0)
(X (cid:0)
A))+
A))+ (c) Không (cid:0)
13
Ộ Ậ
Ủ Ố
Ủ
Ể
4. PH T I THI U C A M T T P PTH
ề
ệ
(tt) Trong đó đi u ki n
ả
ả
ụ
ộ
ộ
ệ
ề
ậ (c)b o đ m cho t p F không có m t ph thu c ư ừ hàm nào là d th a, và đi u ki n
ả
ụ
ế
ộ ư ừ ệ
ế ỗ
ộ
ả ộ (b) b o đ m không có m t thu c tính nào tham gia ả ủ ộ ủ v trái c a ph thu c hàm là d th a. V ph i c a ở ề ụ m i ph thu c hàm
đi u ki n
ỉ
ộ
ả ả ư ừ
ế
ộ
ộ (a) ch có m t thu c tính, nên b o đ m không có ả thu c tính nào trên v ph i là d th a.
14
Ộ Ậ
Ủ Ố
Ủ
Ể
4. PH T I THI U C A M T T P PTH
ấ
ộ
ể i thi u và
ứ ự
M t t p PTH luôn tìm ra ít nh t m t ph t ụ
ủ ố ậ ủ ố
ể ẽ
các ph thu c hàm trong t p F là khác ể ữ i thi u
c nh ng ph t
ộ ậ ộ ế n u th t ượ nhau thì có th s thu đ khác nhau.
ụ
ộ
ậ
ươ
T p Ph Thu c Hàm T
ươ ng Đ ng
ậ
ươ
ặ
ủ ụ
ế
ộ
ỗ
ề
ộ
ỗ
ộ ng (hay F ph G ho c G ph F ) ký ỉ ế + = G + n u và ch n u m i ph thu c ụ + và m i ph thu c hàm
ộ
ộ
ươ ng đ t ệ hi u là F ộ ộ hàm thu c F đ u thu c G ề + . thu c G đ u thu c F
Cho F và G là hai t p ph thu c hàm, ta nói F và G ụ ủ
15
Ộ Ậ
Ủ Ố
Ủ
Ể
4. PH T I THI U C A M T T P PTH
ậ
ể
ủ
ủ ố
ộ ậ
ượ ồ
Thu t Toán Tìm Ph T i Thi u C a M t T p PTH D li u vào : L
ộ
ữ ệ ổ
ầ ố ượ
ượ ồ ụ ậ
ộ
ệ c đ quan h ụ ng ph thu c
ộ
D li u ra :L ữ ệ ể ủ
ệ ụ
ệ c đ quan h ban đ u (l ph quát) Q và t p ph thu c hàm F, s l hàm trong F là cardF. ố ụ ậ ượ ồ i c đ quan h Q và t p ph thu c hàm t ủ ố ộ ữ ệ ố ượ ng ph thu c d li u trong ph t i
ế
ả
ỗ
ộ
ả ủ
ụ
ỗ
ộ
ự
thi u c a F và s l thi u.ể ụ ướ B c 1: Tách v ph i m i ph thu c hàm trong F sao cho ế ộ v ph i c a m i ph thu c hàm ch ch a m t thu c tính ệ ượ ề (đ u này luôn th c hi n đ
ỉ ứ ộ ổ ề c do b đ trên)
F
(cid:0)
f: X (cid:0) A (cid:0)
Y (cid:0) Y g = X (cid:0) F = F (cid:0)
A g Cardf = Cardf + 1
(cid:0)
Cu i ố (cid:0) Cu i ố (cid:0)
16
Ộ Ậ
Ủ Ố
Ủ
Ể
4. PH T I THI U C A M T T P PTH
ộ ậ
ủ ố
ủ
ể
ậ
Thu t Toán Tìm Ph T i Thi u C a M t T p PTH
ậ
ầ ủ ằ ủ ừ
ụ
ộ
B c 2: Tìm t p ph thu c hàm đ y đ b ng cách lo i ụ ạ ộ ướ ộ ư ừ ở ế ỏ v trái c a t ng ph thu c b các thu c tính d th a hàm.
F
(cid:0)
f X (cid:0) B (cid:0)
F+ then
A (cid:0) X X' =X (cid:0) B A (cid:0) If X'(cid:0)
X = X'
Cu i ố (cid:0)
Cu i ố (cid:0)
ư ừ
ạ ỏ
ướ
ộ
B c 3: Lo i b các ph thu c hàm d th a trong F. ụ
(cid:0)
ạ
{lo i f ra kh i F. và l u { F – f } vào G } ươ
ể
ươ
ng đ
ng
i}
ỏ ọ ậ
ớ
F = G
ư ủ ụ {g i th t c ki m tra F, G t ậ ạ {c p nh t l
i F m i}
ở ướ d 17
f (cid:0) F G = F – f If F + =G + then Cu i ố (cid:0)
.
(cid:0)
Ủ ƯỢ Ồ
Ệ
5. KHÓA C A L
C Đ QUAN H …
ị
Đ nh Nghĩa
ở ậ
ượ
ị
Cho quan h Q(A1,A2,…,An) đ
c xác đ nh b i t p
ụ
ậ
ộ
ị
ệ ộ thu c tính Q + và t p ph thu c hàm F đ nh nghĩa trên Q, cho K (cid:0)
Q +.
ỏ ồ
ờ ả
ủ
ề
ệ
ế
ộ
K là m t khóa c a Q n u th a đ ng th i c hai đi u ki n
sau: (cid:0) K (cid:0) ọ g i là siêu khóa)
(cid:0) ỉ ỏ ệ ề ượ Q + (cid:0) Q +) (K ch th a đi u ki n 1 thì đ c F + (hay K+ F
(cid:0) Không t n t
ộ ượ ồ
ậ
ộ
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.
(cid:0) ồ ạ i K' K sao cho K'+ = Q +
18
Ủ ƯỢ Ồ
Ệ
5. KHÓA C A L
C Đ QUAN H …
ộ ượ ồ
ủ
ệ
ậ
ộ Thu t toán tìm m t khóa c a m t l
c đ quan h Q
ỗ
K=Q+; ớ K do V i m i A if (KA)+ = Q then K=KA
ố
c
ế ồ
(cid:0)
ế ứ ự
ổ
ủ ượ ạ ỏ lo i b các
đ quan h , ta có th thay đ i th t ph n t
ệ ầ ử ủ c a K.
N u mu n tìm các khóa khác (n u có) c a l ể
19
Ủ ƯỢ Ồ
Ệ
5. KHÓA C A L
C Đ QUAN H …
ấ ả ộ ượ ủ ồ Thu t Toán Tìm T t C Các Khóa C a M t L ệ c Đ Quan H
ơ ả ậ ậ (Thu t toán c b n)
B c 1:Xác đ nh t
ướ ị ấ ả ủ ậ t c các t p con c a Q
ị ể ấ ả ủ t c các t p con c a m t l
ậ t duy t t
1,A2, ệ ấ ả n1 t p h p con khác r ng c a Q+ ả ử ế s
ủ ượ ồ ượ ệ ả c đ quan h Q(A ủ c gi
Đ xác đ nh t ầ ượ …,An) ta l n l ộ ố (n là s thu c tính c a l ộ ậ là các t p thu c tính: S={X ộ ượ ồ ệ ỗ ợ ậ t c 2 c đ quan h Q),k t qu tìm đ 1, X2, …,X2n1 }
B c 2: Ch n trong S ra t p siêu khóa c a Q
ướ ủ ậ ọ
n1) c a Q+ có bao đóng đúng b ng Q+
ế ộ ậ ủ
ủ ậ ộ ị ằ N u m t t p con Xi (i=1..,2 thì t p con dó (theo đ nh nghĩa trên) là m t siêu khóa c a Q.
1,S2,…,Sm}
ả ử Gi s ta đã có các siêu khóa là S = {S
B c 3:Xây d ng t p ch a t
ứ ấ ả ướ ự ủ ậ ừ ậ t c các khóa c a Q t t p S
(cid:0) (cid:0) ủ Sj thì ta lo i Sj (i,j=1..n), 20
ậ ấ ả ạ ủ ạ ầ ọ Xét m i Si,Sj con c a S (i ả ế k t qu còn l ế j), n u Si i c a S chính là t p t t c các khóa c n tìm.
Ủ ƯỢ Ồ
Ệ
5. KHÓA C A L
C Đ QUAN H …
ấ ả
ộ ượ
ủ
ậ
Thu t Toán Tìm T t C Các Khóa C a M t L
ồ c Đ
ả ế
ậ Quan H ệ (Thu t toán c i ti n)
M t s khái ni m:
ấ
ứ ấ ả ệ ở ế ộ ả ủ ậ ụ ấ t c các thu c tính có xu t ộ v ph i c a t p ph thu c
(cid:0) T p thu c tính đích ch a t
ứ ấ ả ộ ấ t c các thu c tính có xu t hi n
ệ ộ ố (cid:0) T p thu c tính ngu n(TN) ch a t ồ ộ ậ ệ ở ế hi n v trái và không xu t hi n hàm. ậ ế v ph i và không xu t hi n ậ
ả ấ ệ ở ế ụ ộ
(cid:0) T p thu c tính trung gian(TG) ch a t
ộ
ộ ủ ậ ộ ứ ấ ả t c các thu c tính thu c ồ ộ ậ ộ ộ
ượ ồ
ệ
ậ
ổ
ữ ệ
ụ c đ quan h ph quát Q và t p ph
D li u vào: L ộ ữ ệ thu c d li u F
ộ ệ ở v trái c a t p ph thu c hàm. ộ Q+ và không thu c t p thu c tính ngu n và cũng không thu c ậ t p thu c tính đích.
21
ấ ả
ủ
ệ
ữ ệ D li u ra: T t c các khóa c a quan h
Ủ ƯỢ Ồ
Ệ
5. KHÓA C A L
C Đ QUAN H …
ộ ượ
ủ
Thu t Toán Tìm T t C Các Khóa C a M t L
c
ả ế
ấ ả ậ
ậ ồ
ệ (Thu t toán c i ti n)
Đ Quan H
ướ
ậ
ậ
ồ
ộ
ộ
tính trung gian(TG)
ậ
B c 1: Tìm t p thu c tính ngu n(TN), t p thu c
ướ ọ
ươ
ị
ấ ả g i là Xi (b ng ph
ủ ậ t c các t p con c a t p trung gian ệ ng pháp duy t nh phân)
B c 2: Tìm t ằ
ậ
then
ậ
ộ
ồ
ướ
If t p trung gian= ậ T p Khóa = T p thu c tính ngu n ; ế K t thúc ượ ạ c l
i Qua b
c 4
Ng
(cid:0) B c 3: ướ
22
Ủ ƯỢ Ồ
Ệ
5. KHÓA C A L
C Đ QUAN H …
ộ ượ
ủ
Thu t Toán Tìm T t C Các Khóa C a M t L
c
ả ế
ấ ả ậ
ậ ồ
ệ (Thu t toán c i ti n)
Đ Quan H
S= (cid:0)
ồ ậ
ậ ậ S = S (cid:0) ậ
Xi t p trung gian if (T p ngu n Xi)+ = Q+ then ồ (cid:0) Xi} { T p ngu n ầ {S là t p các siêu khóa c n tìm}
ạ ỏ
B c 4: ướ
ạ
S
Lo i b các siêu khóa không t if Si (cid:0) ỏ ậ
ố ể i ti u Sj then Lo i Sj ra kh i T p siêu
(cid:0)
ạ
ậ
ầ
i chính là t p khóa c n tìm.
S còn l
B c 5: ướ SI, Sj (cid:0) khóa S
23
Ủ ƯỢ Ồ
Ạ
Ẩ
Ệ
6. D NG CHU N C A L
C Đ Q.H
ấ ượ
ế ế ủ
Ch t l
t k c a m t l
c đ CSDL có th đ
c
ng thi ự
ộ ượ ồ ẩ
ộ
ể ượ ắ ự s trùng l p ẹ là hai
ẩ
ọ
ề đánh giá d a trên nhi u tiêu chu n trong đó ể thông tin và chi phí ki m tra các ràng bu c toàn v n tiêu chu n quan tr ng.
ộ
ế
ộ
Thu c tính khóa/không khóa: A là m t thu c tính khóa n u
ấ ỳ ộ ộ
ọ
ộ ệ ủ A có tham gia vào b t k m t khóa nào c a quan h , i A g i là thu c tính không khóa. ng
ượ ạ c l
ụ
Thu c tính ph thu c đ y đ : A là m t thu c tính ph ụ ộ
ộ ầ ủ ậ
ộ ế
(cid:0)
ầ ủ ứ
ồ
thu c đ y đ vào t p thu c tính X n u X thu c hàm đ y đ (t c la không t n tai X'
ộ ụ ộ A là m t ph X sao cho X'
(cid:0)
ộ ộ ầ ủ ộ A (cid:0)
F)
(cid:0)
24
Ủ
Ạ
Ẩ
6. D NG CHU N C A LĐ QH (tt)
ộ
ạ
ẩ
ị
Đ nh Nghĩa D ng Chu n M t (First Normal Form)
ệ
ượ ồ
ượ ọ
c đ quan h Q, Q đ ỉ ế
ạ ạ ộ
ộ
ị ơ
ề
ẩ
c g i là đ t d ng ế chu n 1 (1NF) n u và ch n u toàn b các thu c tính c a Q đ u mang giá tr đ n. (cid:0) L ạ ạ ệ
ủ ượ ồ c đ quan h này không đ t d ng chu n 1
ề ạ
ư
ệ
ẩ
(cid:0) Đ a quan h trên v d ng chu n 1:
Cho l ẩ
25
Ủ
Ạ
Ẩ
6. D NG CHU N C A LĐ QH (tt)
ẩ
ị
ạ Đ nh Nghĩa D ng Chu n Hai
ồ
ế
ẩ
ạ
ệ ấ ả
ủ
M t l ộ ượ ạ ề
ụ
ạ ạ c đ quan h Q đ t d ng chu n 2 n u Q đ t ộ ẩ d ng chu n 1 và t t c các thu c tính không khóa c a Q ộ ầ ủ đ u ph thu c đ y đ vào khóa.
ẩ
VD: L F={G (cid:0)
ượ ồ c đ quan h sau đ t chu n 2: Q(G,M,V,N,H,P) N; G (cid:0)
ệ H; G (cid:0)
ạ P; M (cid:0)
V; N,H,P (cid:0)
M}
H qu : ả ệ (cid:0) Q đ t 2NF n u Q là 1NF và t p thu c tính không khóa c a Q ậ ạ
ủ ế ộ
ỗ
(cid:0) N u khóa c a quan h ch có m t thu c tính thì quan h đó ít
ệ ỉ ệ ộ ộ
ủ ẩ nh t đ t chu n 2.
ằ b ng r ng. ế ấ ạ 26
Ủ
Ạ
Ẩ
6. D NG CHU N C A LĐ QH (tt)
ẩ ị ạ Đ nh Nghĩa D ng Chu n Ba
ộ ượ ồ ụ ế ộ ọ
ậ ệ ụ ạ ạ ộ ị ẩ c đ quan h Q đ t d ng chu n 3 n u m i ph thu c hàm ể F+ (là t p ph thu c không hi n nhiên đ nh nghĩa trên Q, A
ề ệ ậ ộ ộ
ộ
ấ ỳ ủ
ộ
M t l X(cid:0) A (cid:0) ộ là thu c tính đ n, X là t p thu c tính), thì m t trong hai đi u ki n ượ sau đ (cid:0) Ho c X ch a m t khóa c a Q ặ ủ (cid:0) Ho c A là m t thành viên c a m t khóa b t k c a Q ủ ộ ặ
ơ ỏ c th a: ứ
D ng chu n 3 còn đ
ạ ượ ị ạ ạ :" l
ẩ ế c đ nh nghĩa ẩ ệ c đ quan h Q đ t d ng ủ
ẩ ề ạ ạ ộ ụ ấ ỳ ủ ượ ồ ộ ọ ộ
chu n 3 n u Q đ t d ng chu n 2 và m i thu c tính không khóa c a ắ ầ Q đ u không ph thu c hàm b c c u vào m t khóa b t k c a Q + "
Hai đ nh nghĩa là t
ị ươ ệ ặ ng đ
ng, tuy nhiên vi c cài đ t thu t toán ề ậ ả ơ ươ ẩ ứ ể
ệ ắ ầ ạ ả ụ ể ki m tra d ng chu n 3 theo cách th nhát thì hi u qu h n nhi u vì ộ không ph i ki m tra tính ph thu c hàm b c c u.
H qu : ệ
ệ ộ 27 c đ quan h Q,F mà Q không có thu c tính không ẩ ế ượ ồ ả N u l ạ khóa thì Q đ t chu n 3.
Ủ
Ạ
Ẩ
6. D NG CHU N C A LĐ QH (tt)
ẩ
ị
ạ Đ nh Nghĩa D ng Chu n BCK
ẩ
ớ
ế
M t l
d ng chu n BCK n u v i m i
ỗ F thì X ch a ứ
A (cid:0)
ủ
ộ ượ ồ ệ ở ạ c đ quan h Q ể ộ ụ ph thu c hàm không hi n nhiên X ộ m t khóa c a Q.
ế
ẩ
ạ
ẩ
ạ
(N u Q đ t chu n BC thì Q đ t chu n 3)
Ị
ộ ượ ồ
ạ
ớ
Đ NH LÝ : Các l p d ng chu n c a m t l ằ
ớ
(cid:0)
ướ
ệ c đ quan h ọ có quan h l ng nhau: nghĩa là l p sau n m tr n trong l p tr
ẩ ủ ớ 1NF
ệ ồ c. BCNF
2NF (cid:0)
3NF (cid:0)
VD: Q(A,C,D,E,I,B)
F={A,C,D(cid:0) E,B,I; C,E(cid:0) A,D}
(cid:0)
28
