Giaùo trình CÔ SÔÛ DÖÕ lieäu trang



tải về 1.89 Mb.
trang12/20
Chuyển đổi dữ liệu07.07.2016
Kích1.89 Mb.
#203
1   ...   8   9   10   11   12   13   14   15   ...   20

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)

AB

ABC

BC

ABCF

CA

CBCF+

ACBCF+

BCAC

AAB

AABC

BAC

ABACF+

CBF

CABC

ACABCF+

BCABC

AC

BA

BBC

ABBCF+

CAB

ACBF+

BCA




AAC

BAB

BABC

ABABCF+

CAC

ACABF+

BCAB




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+ = {ABC,ABAC,ABBC,ABABC,CB,CBC,ACB,ACAB,ACBC,ACABC}


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

ABC,ABAC,ABBC,ABABC

(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


  1. 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:

AD,ABD,CBDE,EA,AE



  1. Cho Q+={ABCD}

  1. Tìm taát caùc caùc taäp con cuûa Q

  2. 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)

  1. 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)


  1. Cho F = {ABC,BD,CDE,CEGH,GA}

  1. Haõy chöùng toû phuï thuoäc haøm ABE,ABG ñöôïc suy dieãn töø F nhôø luaät daãn Armstrong

  2. 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})

  3. Chứng minh rằng:

{ABE, AG I, BE I, EG, GIH} |= (AB GH)


  1. Cho F = {AD,ABDE,CEG,EH}. Haõy tìm bao ñoùng cuûa AB.

  2. Cho F={ABE,AGI,BEI,EG,GIH}.

  1. Haõy chöùng toû phuï thuoäc haøm ABGH ñöôïc suy dieãn töø F nhôø luaät daãn Armstrong

  2. Tìm bao ñoùng cuûa {AB}

  1. Cho F={AD,ABE,BIE,CDI,EC} tìm bao ñoùng cuûa {AE}+={ACDEI}

----oOo----


tải về 1.89 Mb.

Chia sẻ với bạn bè của bạn:
1   ...   8   9   10   11   12   13   14   15   ...   20




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương