IIITHUAÄT TOAÙN TÌM F+ 1Thuaät toaùn cô baûn
Ñeå tính bao ñoùng F+ cuûa taäp caùc phuï thuoäc haøm F ta thöïc hieän caùc böôùc sau:
Böôùc 1: Tìm taát caû taäp con cuûa Q+
Böôùc 2: Tìm taát caû caùc phuï thuoäc haøm coù theå coù cuûa Q.
Böôùc 3: Tìm bao ñoùng cuûa taát caû taäp con cuûa Q.
Böôùc 4: Döïa vaøo bao ñoùng cuûa taát caû caùc taäp con ñaõ tìm ñeå xaùc ñònh phuï thuoäc haøm naøo thuoäc F+
Ví duï 3:
Cho löôïc ñoà quan heä Q(A,B,C) F = {AB C,C B} laø taäp phuï thuoäc haøm treân Q. F+ ñöôïc tính laàn löôït theo caùc böôùc treân laø nhö sau:
Böôùc 1: Caùc taäp con cuûa Q+
|
A
|
B
|
C
|
|
{A}
|
{B}
|
{C}
|
|
|
{A,B}
|
{A,C}
|
|
|
|
{B,C}
|
|
|
|
{A,B,C}
|
Böôùc 2: caùc phuï thuoäc haøm coù theå coù cuûa F (khoâng keâ caùc phuï thuoäc haøm hieån nhieân)
AB
|
ABC
|
BC
|
ABCF
|
CA
|
CBCF+
|
ACBCF+
|
BCAC
|
AAB
|
AABC
|
BAC
|
ABACF+
|
CBF
|
CABC
|
ACABCF+
|
BCABC
|
AC
|
BA
|
BBC
|
ABBCF+
|
CAB
|
ACBF+
|
BCA
|
|
AAC
|
BAB
|
BABC
|
ABABCF+
|
CAC
|
ACABF+
|
BCAB
|
|
Böôùc 3: bao ñoùng cuûa caùc taäp con cuûa Q ñoái vôùi F
+ = A+ = A C+ = BC
ABC+ =ABC B+ = B AC+ = ABC
AB+ = ABC BC+ = BC
Böôùc 4: F = {AB C,C B} suy ra:
F+ = {ABC,ABAC,ABBC,ABABC,CB,CBC,ACB,ACAB,ACBC,ACABC}
2Thuaät toaùn caûi tieán
Döïa vaøo thuaät toaùn cô baûn treân, ta nhaän thaáy coù theå tính F+ theo caùc böôùc sau:
Böôùc 1: Tìm taát caû taäp con cuûa Q+
Böôùc 2: Tìm bao ñoùng cuûa taát caû taäp con cuûa Q+.
Böôùc 4: Döïa vaøo bao ñoùng cuûa caùc taäp con ñaõ tìm ñeå suy ra caùc phuï thuoäc haøm thuoäc F+.
Ví duï bao ñoùng A+ = A chæ goàm caùc phuï thuoäc haøm hieån nhieân
bao ñoùng {AB}+ = ABC cho caùc phuï thuoäc haøm khoâng hieån nhieân sau
ABC,ABAC,ABBC,ABABC
(Tìm taát caû caùc taäp con cuûa {ABC} roài boû caùc taäp con cuûa {AB})
Caùc taäp con cuûa {ABC} laø: , {A},{B},{AB},{C},{AC},{BC},{ABC}
Boû caùc taäp con cuûa {AB} laø: , {A},{B},{AB},{C},{AC},{BC},{ABC}
Caùc taäp coøn laïi chính laø veá phaûi cuûa phuï thuoäc haøm coù veá traùi laø AB
IV BAØI TAÄP -
Cho quan heä sau:
r(
|
A
|
B
|
C
|
D
|
E)
|
|
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
|
Phuï thuoäc haøm naøo sau ñaây thoûa r:
AD,ABD,CBDE,EA,AE
-
Cho Q+={ABCD}
-
Tìm taát caùc caùc taäp con cuûa Q
-
Tìm taát caû caùc phuï thuoäc haøm coù theå coù cuûa Q (khoâng lieät keâ phuï thuoäc haøm hieån nhieân)
-
Tìm bao ñoùng F+ cuûa quan heä phanCong(PHICONG,MAYBAY,NGAYKH,GIOKH)
Với tập phụ hàm sau:
F=({MAYBAY} GIOKH,
{PHICONG,NGAYKH,GIOKH} MABAY ,
{MAYBAY,NGAYKH} PHICONG)
-
Cho F = {ABC,BD,CDE,CEGH,GA}
-
Haõy chöùng toû phuï thuoäc haøm ABE,ABG ñöôïc suy dieãn töø F nhôø luaät daãn Armstrong
-
Tìm bao ñoùng cuûa AB(vôùi baøi toaùn khoâng noùi gì veà löôïc ñoà quan heä Q ta ngaàm hieåu Q+ laø taäp thuoäc tính coù trong F nghóa laø Q+={ABCDEGH})
-
Chứng minh rằng:
{ABE, AG I, BE I, EG, GIH} |= (AB GH)
-
Cho F = {AD,ABDE,CEG,EH}. Haõy tìm bao ñoùng cuûa AB.
-
Cho F={ABE,AGI,BEI,EG,GIH}.
-
Haõy chöùng toû phuï thuoäc haøm ABGH ñöôïc suy dieãn töø F nhôø luaät daãn Armstrong
-
Tìm bao ñoùng cuûa {AB}
-
Cho F={AD,ABE,BIE,CDI,EC} tìm bao ñoùng cuûa {AE}+={ACDEI}
----oOo----
Chia sẻ với bạn bè của bạn: |