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



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

IIIKHOÙA CUÛA LÖÔÏC ÑOÀ QUAN HEÄ (Key)

1Ñònh Nghóa


Q(A1,A2,…,An)laø löôïc ñoà quan heä.

Q+ laø taäp thuoäc tính cuûa Q.

F laø taäp phuï thuoäc haøm treân Q.

K laø taäp con cuûa Q+.



Noùi raèng K laø moät khoùa cuûa Q neáu:

  1. K+ = Q+ vaø

  2. Khoâng toàn taïi K'  K sao cho K’+= Q+

Taäp thuoäc tính S ñöôïc goïi laø sieâu khoùa neáu S  K

Thuoäc tính A ñöôïc goïi laø thuoäc tính khoùa neáu AK vôùi K laø khoùa baát kyø cuûa Q. Ngöôïc laïi A ñöôïc goïi laø thuoäc tính khoâng khoùa.
Moät löôïc ñoà quan heä coù theå coù nhieàu khoùa vaø taäp thuoäc tính khoâng khoùa cuõng coù theå baèng roãng.

(Khi thieát keá moät heä thoáng thoâng tin, thì vieäc laäp löôïc ñoà cô sôû döõ lieäu ñaït ñeán moät tieâu chuaån naøo ñoù laø moät vieäc laøm quan troïng. Vieäc xaùc ñònh chuaån cho moät löôïc ñoà quan heä coù lieân quan maät thieát vôùi thuaät toaùn tìm khoùa).



Thuaät toaùn tìm moät khoùa cuûa moät löôïc ñoà quan heä Q

Böôùc 1: gaùn K = Q+

Böôùc 2: A laø moät thuoäc tính cuûa K, ñaët K’ = K  A. Neáu K’+= Q+ thì gaùn K = K' thöïc hieän laïi böôùc 2

Neáu muoán tìm caùc khoùa khaùc (neáu coù) cuûa löôïc ñoà quan heä, ta coù theå thay ñoåi thöù töï loaïi boû caùc phaàn töû cuûa K.



Ví duï 7:

Q(A,B,C,D,E,G,H,I)F={AC B;BI  ACD;ABCD;HI;ACEBCG;CGAE}

Tìm K

Laàn löôït loaïi caùc thuoäc tính trong K theo thöù töï sau:



A, B, D, E, I

Ta ñöôïc moät khoùa laø cuûa löôïc ñoà quan heä laø {C,G,H}

(Löu yù laø thuaät toaùn naøy chæ neân söû duïng trong tröôøng hôïp chæ caàn tìm moät khoùa).

2Thuaät toaùn tìm taát caû khoùa

iThuaät toaùn cô baûn


Böôùc 1: Xaùc ñònh taát caû caùc taäp con khaùc roãng cuûa Q+. Keát quaû tìm ñöôïc giaû söû laø caùc taäp thuoäc tính X1, X2, …,X2n-1

Böôùc 2: Tìm bao ñoùng cuûa caùc Xi

Böôùc 3: Sieâu khoùa laø caùc Xi coù bao ñoùng ñuùng baèng Q+. Giaû söû ta ñaõ coù caùc sieâu khoùa laø S = {S1,S2,…,Sm}

Böôùc 4: Xaây döïng taäp chöùa taát caû caùc khoùa cuûa Q töø taäp S baèng caùch xeùt moïi Si, Sj con cuûa S (i  j), neáu Si  Sj thì ta loaïi Sj (i,j=1..n), keát quaû coøn laïi cuûa S chính laø taäp taát caû caùc khoùa caàn tìm.

Ví duï 8: Tìm taát caû caùc khoùa cuûa löôïc ñoà quan heä vaø taäp phuï thuoäc haøm nhö sau:

Q(C,S,Z); F = {f1:CS  Z; f2:Z  C}




Xi



Sieâu khoùa

khoùa

C

C







S

S







CS

CSZ

CS

CS

Z

ZC







CZ

CZ







SZ

SZC

SZ

SZ

CSZ

CSZ

CSZ




Vaäy löôïc ñoà quan heä Q coù hai khoùa laø: {C,S} vaø {S,Z}

Thuaät toaùn treân thì deã hieåu, deã caøi ñaët, tuy nhieân neáu vôùi n khaù lôùn thì pheùp duyeät ñeå tìm ra taäp taát caû caùc taäp con cuûa taäp Q+ laø khoâng hieäu quaû. Do vaäy caàn thu heïp khoâng gian duyeät. Chuùng ta seõ nghieân cöùu thuaät toaùn caûi tieán theo höôùng giaûm soá thuoäc tính cuûa taäp caàn duyeät taát caû caùc taäp con.


iiThuaät toaùn caûi tieán


Tröôùc khi ñi vaøo thuaät toaùn caûi tieán, ta caàn quan taâm moät soá khaùi nieäm sau:

  • Taäp thuoäc tính nguoàn (TN) chöùa taát caû caùc thuoäc tính coù xuaát hieän ôû veá traùi vaø khoâng xuaát hieän ôû veá phaûi cuûa caùc phuï thuoäc haøm vaø caùc thuoäc tính khoâng xuaát hieän ôû caû veá traùi laãn veá phaûi cuûa caùc phuï thuoäc haøm.

  • Taäp thuoäc tính ñích (TD) chöùa taát caû caùc thuoäc tính coù xuaát hieän ôû veá phaûi vaø khoâng xuaát hieän ôû veá traùi cuûa caùc phuï thuoäc haøm.

  • Taäp thuoäc tính trung gian (TG) chöùa taát caû caùc thuoäc tính xuaát hieän ôû caû veá traùi laãn veá phaûi cuûa caùc phuï thuoäc haøm.

Heä quaû: Neáu K laø khoùa cuûa Q thì TN  K vaø TD  K = 

Chöùng minh TN  K

Theo heä quaû 2 cuûa thuaät toaùn tìm bao ñoùng ta coù K+  KTDTG

Ta chöùng minh A  TN  A  K. Thaät vaäy:

Neáu A  K  K+  KTDTG  Q+-A  K khoâng laø khoùa  maâu thuaãn



Chöùng minh TD  K = 

Giaû söû coù thuoäc tính A  TD  K ta seõ daãn ñeán ñieàu maâu thuaãn. Thaät vaäy:

Theo heä quaû 1 cuûa thuaät toaùn tìm bao ñoùng thì K+ = (K-A)+  A

A  TD  coù X laø veá traùi cuûa moät phuï thuoäc haøm trong F sao cho X  A (1) vaø A  X  X  K+ = (K-A)+  A vì A  X  X  (K-A)+  (K-A)  X (2)

(1) vaø (2) cho (K-A)  A  A(K-A)+  (K-A)+  A = (K-A)+  K+ = (K-A)+ maâu thuaãn vôùi ñieàu K laø khoùa.

Döïa vaøo heä quaû treân ta coù thuaät toaùn tìm taát caû khoùa sau:



Döõ lieäu vaøo: Löôïc ñoà quan heä Q vaø taäp phuï thuoäc haøm F

Döõ lieäu ra: Taát caû caùc khoùa cuûa quan heä

Thuaät toaùn tìm taát caû khoùa cuûa moät löôïc ñoà quan heä

Böôùc 1: taïo taäp thuoäc tính nguoàn TN, taäp thuoäc tính trung gian TG

Böôùc 2: if TG =  then löôïc ñoà quan heä chæ coù moät khoùa K

K  TN

keát thuùc

Ngöôïc laïi

Qua böôùc 3

Böôùc 3: tìm taát caû caùc taäp con Xi cuûa taäp trung gian TG

Böôùc 4: tìm caùc sieâu khoùa Si baèng caùch Xi

if (TN  Xi)+ = Q+ then

Si = TN  Xi

Böôùc 5: tìm khoùa baèng caùch loaïi boû caùc sieâu khoùa khoâng toái tieåu

 Si, Sj  S

if Si  Sj then Loaïi Sj ra khoûi Taäp sieâu khoùa S

S coøn laïi chính laø taäp khoùa caàn tìm.
Ví duï 9: Giaûi laïi baøi taäp ví duï 8

Aùp duïng thuaät toaùn caûi tieán ta coù lôøi giaûi nhö sau:

TN = {S}; TG = {C,Z}

Goïi Xi laø caùc taäp con cuûa taäp TG:



Xi

(TN  Xi)

(TN Xi)+

Sieâu khoùa

khoùa



S

S







C

SC

Q+

SC

SC

Z

SZ

Q+

SZ

SZ

CZ

SCZ

Q+

SCZ




Keát quaû quan heä treân coù hai khoùa laø : {S,C} vaø {S,Z}
1   ...   10   11   12   13   14   15   16   17   ...   20


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

    Quê hương