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Ụ Ộ
M C TIÊU C A BÀI NÀY GIÚP NG I H CỤ Ủ ƯỜ Ọ
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ậ ụ ậ ị ễ
theo tiên đ , theo quan h , tìm ph t i thi u, bài toán thành viênề ệ ủ ố ể
đ gi i quy t các bài t p c th .ể ả ế ậ ụ ể
Á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ị ụ ộ
Đ nh nghĩa:ị cho U là m t t p thu c tính, m t ph thu c hàm trên U làộ ậ ộ ộ ụ ộ
m t phát bi u có d ng Xộ ể ạ Y, trong đó X,Y⊆U.
Cho R là quan h trên t p thu c tính U, nói r ng quan h R tho mãnệ ậ ộ ằ ệ ả
ph thu c hàm Xụ ộ Y, n u v i 2 b b t kì trong R mà chúng gi ngế ớ ộ ấ ố
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.ế
N u f= XếY là m t ph thu c hàm trên U thì ta nói t p thu c tính Yộ ụ ộ ậ ộ
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).
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 ậ ụ ộ ệ ế ỉ ế ớ ∀ f ∈ F
thì R(f) hay nói m t cách t ng đ ng quan h R tho mãn t p phộ ươ ươ ệ ả ậ ụ
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
Đ nh nghĩa: L c đ quan h là m t c p ị ượ ồ ệ ộ ặ α=(U, F) trong đó U là t pậ
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.ữ ạ ộ ậ ụ ộ
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
⊆
U, Y
⊆
X, thì X
Y
2) Tính ch t b c c u: ấ ắ ầ
∀
X, Y, Z
⊆
U, n u có Xế
Y và Y
Z
thì X
Z
3) Tính ch t gia tăng: ấ
∀
X, Y
⊆
U, n u Xế
Y và
∀
Z
⊆
U thì
XZ
YZ
4) Tính ch t t a b c c u: ấ ự ắ ầ
∀
X, Y, Z, W
⊆
U, n u Xế
Y,
YZ
W thì XZ
W
5) Tính ch t ph n x ch t: ấ ả ạ ặ
∀
X
⊆
U thì X
X
6) Lu t tách: ậ
∀
X, Y, Z
⊆
U, n u có Xế
YZ thì có:
7) Lu t h p: ậ ợ
∀
X, Y, Z
⊆
U, n u có Xế
Y và X
Z thì có
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
3. H tiên đ Amstrongệ ề
F1 - Lu t ph n x ậ ả ạ
∀
X,Y
⊆
U, n u Xế
⊆
Y thì Y
X
F2 - B c c u ắ ầ
∀
X, Y, Z
⊆
U n u cóế
thì X
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ậ ụ ộ ộ ụ ộ
U ( f có th không thu c F), nói r ng f suy d n đ c t F theo h tiênể ộ ằ ẫ ượ ừ ệ
Trang 2
XY
YZ
XY
XZ
NH P MÔN CSDL QUAN HẬ Ệ So n b i b môn Công ngh ph n m m - 200ạ ở ộ ệ ầ ề 7
đ Amstrong và kí hi u là F├ f n u nh f có th nh n đ c t t p Fề ệ ế ư ể ậ ượ ừ ậ
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: ậ
V iớ ∀ f ∈ F thì F├ f
Kí hi u Fệ+ là t p t t c các ph thu c hàm đ c suy d n t t p F theoậ ấ ả ụ ộ ượ ẫ ừ ậ
h tiên đ Amstrong. ệ ề
Ta th y Fấ⊆ F+
F+ đ c g i là bao đóng c a t p ph thu c hàm F, n u Fượ ọ ủ ậ ụ ộ ế + =F thì ta nói
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àộ ậ ụ ộ ậ ộ
m t ph thu c hàm trên U, (f có th không thu c F), nói r ng f đ cộ ụ ộ ể ộ ằ ượ
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.ệ ế ả ả
Ký hi u F* là t p t t c các ph thu c hàm đ c suy d n t t p F theoệ ậ ấ ả ụ ộ ượ ẫ ừ ậ
quan h .ệ
F*={f:XY | X,Y⊆U, F╞f}
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ó:ậ ụ ậ ộ
1. Tính ph n x : V iảạớ ∀ f ∈ F thì F ╞f t đây ta suy ra F ừ⊆ F*.
2. Tính đ n đi u: N u Fơ ệ ế ⊆ G thì F* ⊆ G*.
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ủ ậ ộ
Cho t p ph thu c hàm F trên U, Xậ ụ ộ ⊆U, bao đóng c a t p thu củ ậ ộ
tính X, kí hi u là 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
α
= (U,F), X
⊆
U
Output X+ =?
Thu t toánậ
Ta xác đ nh dãy Xị(0), X(1), X(2),... theo quy n p nh sauạ ư
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
1. Đ t Xặ(0)=X
2. Gi s r ng đã xây d ng đ c đ n b c th i t c là đãả ử ằ ự ượ ế ướ ứ ứ
bi t Xế(i) (i>=0)
3. Xây d ng ti p b c i+1 nh sauự ế ướ ư
X(i+1)= X(i) ∪ Z(i) trong đó
Z(i) = ∪ Yj v i đi u ki n :ớ ề ệ
Vì v y Zậ(i) chính là h p c a các v ph i c a các ph thu c hàmợ ủ ế ả ủ ụ ộ
trong t p F mà có v trái là t p con c a t p tr c mà có v ph i ch aậ ế ậ ủ ậ ướ ế ả ư
đ c thêm vào.ượ
đi u ki n (3) ch có tác d ng tăng t c đ tính toánề ệ ỉ ụ ố ộ
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 i ch s i nào đó đ Xạ ỉ ố ể (i)= X(i+1) (*), g i i là ch s nh nh t khi đó Xọ ỉ ố ỏ ấ + =
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ộ ậ ụ ộ ộ ụ ộ
hàm c a F t c f ủ ứ ∈F, f đ c g i là d th a trong F n u nh (F-f)ượ ọ ư ừ ế ư + =F+
Hay có th nói t ng đ ng f đ c g i là d th a trong F n nể ươ ươ ượ ọ ư ừ ế
nó suy d n đ c t 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
Xj Yj ∈ F (1)
Xj ⊆Xi (2)
YJ ⊄ X(i) (3)
NH P MÔN CSDL QUAN HẬ Ệ So n b i b môn Công ngh ph n m m - 200ạ ở ộ ệ ầ ề 7
1) t m xoá f kh i F, g i G là t p thu đ cạ ỏ ọ ậ ượ
G=F-f, n u Gế
≠φ
thì chuy n qua b c 2, còn không thì k tể ướ ế
thúc thu t toán và k t lu n f là không d th a trong Fậ ế ậ ư ừ
2) Gi s f=Xả ử
Y n u G├ f t c Yế ứ
⊆
XG
+
thì f là d th aư ừ
trong F còn ng c l i f là không d th a.ượ ạ ư ừ
Nh v y, ta ch c n tính Xư ậ ỉ ầ + và so sánh v i t p con Y ta có ngay câu trớ ậ ả
l i X ờ→ Y có thu c vào Fộ+ hay không.
8. Ph thu c hàm d th aụ ộ ư ừ
II. CÁC VÍ DỤ
Ví d 1:ụ
Cho l c đ quan h ượ ồ ệ α = (U,F) v iớ
U = ABCDEGH
F={ BC ADE, AC BDG, BE ABC, CD BDH, BCH ACG}
Hãy tính X+ trong các tr ng h pườ ợ
a) X=BD
b) X=ABE
c) X=CDG
Gi iả
a) đ t X(0)=BD (=X)ặ
X(1) = X(0) ∪ Z(0) =BD ∪ Φ=BD
Suy ra X(0)= X(1) v y Xậ+ =X=BD
b) đ t X(0)=ABE (=X)ặ
X(1) = X(0) ∪ Z(0) =ABE ∪ABC=ABCE
X(2) = X(1) ∪ Z(1) =ABCE ∪ (ADE ∪ BDG)=ABCDEG
X(3) = X(2) ∪ Z(2) = ABCDEG ∪ BDH=ABCDEGH=U
V y Xậ+=U
Ví d 2 :ụ Áp d ng bài toán thành viênụ
Gi s có t p F={Xả ử ậ YW, XWZ, ZY, XYZ}
Hãy cho bi t XYếZ có d th a trong F hay không?ư ừ
Trang 5