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



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

IVBAØI TAÄP


  1. Chöùng minh caùc tính chaát sau:

  1. Tính coäng ñaày ñuû X  Y vaø Z  W  XZ  YW

  2. Tính tích luõy X  Y vaø Y  ZW  X  YZW

  1. Cho G={ABC,AB,BC,AC}. F={ABC,AB,BC} coù töông ñöông vôùi G khoâng?

  2. Cho löôïc ñoà CSDL

Kehoach(NGAY(A),GIO(B),PHONG(C),MONHOC(D),GIAOVIENE)

F={NGAY,GIO,PHONG  MONHOC

MONHOC,NGAY  GIAOVIEN

NGAY,GIO,PHONG  GIAOVIEN

MONHOC  GIAOVIEN}

  1. Tính {NGAY,GIO,PHONG}+ ; {MONHOC}+

  2. Tìm phuû toái thieåu cuûa F

  3. Tìm taát caû caùc khoùa cuûa Kehoach

  1. Cho löôïc ñoà CSDL

Q(TENTAU,LOAITAU,MACHUYEN,LUONGHANG,BENCANG,NGAY)

F={TENTAU  LOAITAU

MACHUYEN  TENTAU, LUONGHANG

TENTAU,NGAY  BENCANG, MACHUYEN}

  1. Haõy tìm taäp phuû toái thieåu cuûa F

  2. Tìm taát caû caùc khoùa cuûa Q

  1. Q(A,B,C,D,E,G)

Cho F={ABC;CA;BCD;ACDB;DEG;BEC;CGBD;CE  AG}

X={B,D}, X+=?

Y={C,G}, Y+=?


  1. cho löôïc ñoà quan heä Q vaø taäp phuï thuoäc haøm F

  1. F={ABE;AGI;BEI;EG;GI H} chöùng minh raèng AB  GH.

  2. F={ABC;BD;CDE;CEGH;GA}chöùng minh raèng AB  E; AB  G

  1. Cho quan heä r

A

B

C

D

x

u

x

Y

y

x

z

x

z

y

y

y

y

z

w

z

Trong caùc phuï thuoäc haøm sau ñaây, PTH naøo khoâng thoûa

A  B; A  C; B  A; C  D; D  C; D  A



  1. Haõy tìm taát caû caùc khoùa cho löôïc ñoà quan heä sau:

Q(BROKER,OFFICE,STOCK,QUANTITY,INVESTOR,DIVIDENT)

F={STOCK  DIVIDENT

INVESTOR  BROKER

INVESTOR,STOCK  QUANTITY

BROKER  OFFICE }


  1. Xeùt löôïc ñoà quan heä vaø taäp phuï thuoäc döõ lieäu:

Q(C,T,H,R,S,G)

f={ f1: C T; f2: HR C; f3: HT R;

f4: CS G; f5: HS R}

Tìm phuû toái thieåu cuûa F




  1. Q(A,B,C,D,E,H)

F={A  E; C  D; E  DH}

Chöùng minh K={A,B,C} laø khoùa duy nhaát cuûa Q



  1. Q(A,B,C,D)

F={ABC; DB; CABD}

Haõy tìm taát caû caùc khoùa cuûa Q



  1. Q(A,B,C,D,E,G)

F={ABC;C A;BCD;ACDB;DEG;BEC;CGBD;CEG}

Haõy tìm taát caû caùc khoùa cuûa Q.



  1. Xaùc ñònh phuû toái thieåu cuûa taäp phuï thuoäc haøm sau:

  1. Q(A,B,C,D,E,G),

F={ABC;CA;BCD;ACDB;DEG;BEC;CGBD;CEAG}

  1. Q(A,B,C)

F={AB,AC,BA,CA,BC}


  1. Xaùc ñònh phuû toái thieåu cuûa caùc taäp phuï thuoäc haøm sau:

  1. Q1(ABCDEGH)

F1={A H,ABC,BCD;GB}

  1. Q2(ABCSXYZ)

F2={SA;AXB;SB;BYC;CZX}

  1. Q3(ABCDEGHIJ)

F3={BGD;GJ;AIC;CEH;BDG;JHA; DI }

  1. Q4(ABCDEGHIJ)

F4={BHI;GCA;IJ;AEG;DB;IH}

----oOo----

Chöông 6.

CHUAÅN HOÙA CÔ SÔÛ DÖÕ LIEÄU




IDAÏNG CHUAÅN CUÛA LÖÔÏC ÑOÀ QUAN HEÄ (normal forms for relation schemes)


Trong thöïc teá, moät öùng duïng cuï theå coù theå ñöôïc thieát keá thaønh nhieàu löôïc ñoà cô sôû döõ lieäu khaùc nhau, vaø taát nhieân chaát löôïng thieát keá cuûa caùc löôïc ñoà CSDL naøy cuõng khaùc nhau. Chaát löôïng thieát keá cuûa moät löôïc ñoà CSDL coù theå ñöôïc ñaùnh giaù döïa treân nhieàu tieâu chuaån trong ñoù söï truøng laép thoâng tin vaø chi phí kieåm tra caùc raøng buoäc toaøn veïn laø hai tieâu chuaån quan troïng.

Sau ñaây laø moät soá tieâu chuaån ñeå ñaùnh giaù ñoä toát/xaáu cuûa moät löôïc ñoà quan heä. Tröôùc tieân ta tìm hieåu moät soá khaùi nieäm lieân quan:


1Ñònh nghóa caùc daïng chuaån

iDaïng Chuaån Moät (First Normal Form)


Moät löôïc ñoà quan heä Q ôû daïng chuaån 1 neáu toaøn boä caùc thuoäc tính cuûa moïi boä ñeàu mang giaù trò ñôn.

Ví duï 1: Xeùt quan heä

MASV

HOVATEN

KHOA

TENMONHOC

DIEMTHI

99023

NGUYENTHITHU

CONG NGHE THONG TIN

KY THUAT LAP TRINH

6










TOAN ROI RAC

8










CO SO DU LIEU

4

99030

LE VAN THANH

DIEN TU

VI XULY

4

Quan heä naøy khoâng ñaït chuaån 1 vì caùc thuoäc tính TENMONHOC, DIEMTHI cuûa boä thöù nhaát khoâng mang giaù trò ñôn (chaúng haïn sinh vieân NGUYEN THI THU coù thuoäc tính TENMONHOC laø KY THUAT LAP TRINH, TOAN ROI RAC, CO SO DU LIEU).

Ta hoaøn toaøn coù theå ñöa quan heä treân veà daïng chuaån 1 nhö sau:



MASV

HOVATEN

KHOA

TENMONHOC

DIEMTHI

99023

NGUYENTHITHU

CONG NGHE THONG TIN

KY THUAT LAP TRINH

6

99023

NGUYENTHITHU

CONG NGHE THONG TIN

TOAN ROI RAC

8

99023

NGUYENTHITHU

CONG NGHE THONG TIN

CO SO DU LIEU

4

99030

LE VAN THANH

DIEN TU

VI XULY

4

Chuù yù raøng khi xeùt caùc daïng chuaån, neáu ta khoâng noùi gì theâm, ta hieåu daïng chuaån ñang xeùt ít nhaát laø ñaït daïng chuaån 1.

iiDaïng Chuaån 2 (Second Normal Form)


Moät löôïc ñoà quan heä Q ôû daïng chuaån 2 neáu Q ñaït chuaån 1 vaø moïi thuoäc tính khoâng khoùa cuûa Q ñeàu phuï thuoäc ñaày ñuû vaøo khoùa.
Thuaät toaùn kieåm tra daïng chuaån 2

Vaøo: löôïc ñoà quan heä Q, taäp phuï thuoäc haøm F

Ra: khaúng ñònh Q ñaït chuaån 2 hay khoâng ñaït chuaån 2.

Böôùc 1: Tìm taát caû khoùa cuûa Q

Böôùc 2: Vôùi moãi khoùa K, tìm bao ñoùng cuûa taát caû taäp con thaät söï S cuûa K.

Böôùc 3: Neáu coù bao ñoùng S+ chöùa thuoäc tính khoâng khoùa thì Q khoâng ñaït chuaån 2

Ngöôïc laïi thì Q ñaït chuaån 2


Ví duï 2: Cho löôïc ñoà quan heä Q(A,B,C,D) vaø taäp phuï thuoäc haøm

F={ABC; BD; BCA}. Hoûi Q coù ñaït chuaån 2 khoâng?



Giaûi:

TN={B}, TG={AC}




Xi

(TN  Xi)

(TN Xi)+

Sieâu khoùa

khoùa



B

BD







A

AB

ABCD

AB

AB

C

BC

ABCD

BC

BC

AC

ABC

ABCD

ABC




Khoùa laø K1=AB vaø K2=BC. Ta thaáy BK1, BD,D laø thuoäc tính khoâng khoùa thuoäc tính khoâng khoùa khoâng phuï thuoäc ñaày ñuû vaøo khoùa  Q khoâng ñaït chuaån 2.
Ví duï 3: Quan heä sau ñaït chuaån 2.

Q(G,M,V,N,H,P) F={GM; GN; GH; GP; MV; NHPM}



Giaûi:

TN={G} TG={M,N,H,P}




Xi

(TN  Xi)

(TN Xi)+

Sieâu khoùa

khoùa



G

Q+

G

G

M

GM

Q+

GM




N

GN

Q+

GN




MN

GMN

Q+

GMN




H

GH

Q+

GH




MH

GMH

Q+

GMH




NH

GNH

Q+

GNH




MNH

GMNH

Q+

GMNH




P

GP

Q+

GP




MP

GMP

Q+

GMP




NP

GNP

Q+

GNP




MNP

GMNP

Q+

GMNP




HP

GHP

Q+

GHP




MHP

GMHP

Q+

GMHP




NHP

GNHP

Q+

GNHP




MNHP

GMNHP

Q+

GMNHP




Löôïc ñoà quan heä Q chæ coù moät khoùa vaø khoùa chæ coù moät thuoäc tính neân moïi thuoäc tính ñeàu phuï thuoäc ñaày ñuû vaøo khoùa  Q ñaït chuaån 2

Heä quaû:

  • Neáu Q ñaït chuaån 1 vaø taäp thuoäc tính khoâng khoùa cuûa Q baèng roãng thì Q ñaït chuaån 2

  • Neáu taát caû khoùa cuûa quan heä chæ goàm moät thuoäc tính thì quan heä ñoù ít nhaát ñaït chuaån 2.

Ví duï 4: Q(A,B,C,D,E,H) F={A  E; C  D; E  DH}

Giaûi:

TN={ACB} TG={E}



Xi

(TN  Xi)

(TN Xi)+

Sieâu khoùa

khoùa



ACB

ABCDEH

ACB

ACB

E

ACBE

ABCDEH

ACBE




 khoùa cuûa Q laø K = {ABC}.CK, CD, D laø thuoäc tính khoâng khoùa D phuï thuoäc khoâng ñaày ñuû vaøo khoùa neân Q khoâng ñaït chuaån 2.

iiiDaïng Chuaån 3 (Third Normal Form)


Thuoäc tính phuï thuoäc baéc caàu

Q laø löôïc ñoà quan heä, X,Y laø hai taäp con cuûa Q+, A laø moät thuoäc tính.

Noùi raèng A phuï thuoäc baéc caàu vaøo X neáu caû ba ñieàu sau thoûa:


  • X  Y,Y  A

  • Y X

  • A  XY

Ñònh nghóa 1:

Löôïc ñoà quan heä Q ôû daïng chuaån 3 neáu moïi phuï thuoäc haøm X  A  F+ vôùi A  X ñeàu coù:

  • Hoaëc X laø sieâu khoùa

  • Hoaëc A laø thuoäc tính khoùa


Ñònh nghóa 2:

Löôïc ñoà quan heä Q ôû daïng chuaån 3 neáu moïi thuoäc tính khoâng khoùa cuûa Q ñeàu khoâng phuï thuoäc baéc caàu vaøo moät khoùa baát kyø cuûa Q
Hai ñònh nghóa treân laø töông ñöông, tuy nhieân vieäc caøi ñaët thuaät toaùn kieåm tra daïng chuaån 3 theo ñònh nghóa 1 thì hieäu quaû hôn nhieàu vì khoâng phaûi kieåm tra tính phuï thuoäc baéc caàu.

Ta chöùng minh hai ñònh nghóa töông ñöông baèng caùch:



Töø ñònh nghóa 1 khoâng coù phuï thuoäc baéc caàu vaøo moät khoùa baát kyø cuûa Q. Thaät vaäy:

Giaû söû coù phuï thuoäc baéc caàu vaøo khoùa nghóa laø coù K  Y,Y  A,Y K vaø A  KY. Y  A laø moät phuï thuoäc haøm neân theo ñònh nghóa 1 coù hai tröôøng hôïp xaûy ra cho Y:



  • Y laø sieâu khoùa  YK ñieàu naøy maâu thuaãn vôùi Y K.

  • Y khoâng laø sieâu khoùa  A laø thuoäc tính khoùa  ñieàu naøy traùi vôùi giaû thieát A  KY

Töø ñònh nghóa 2  neáu XAF+ vôùi AX thì X laø sieâu khoùa hoaëc A laø thuoäc tính khoùa

Neáu XAF+ vôùi AX coù X khoâng laø sieâu khoùa vaø A khoâng laø thuoäc tính khoùa thì daãn ñeán moät soá ñieàu sau:

A khoâng laø thuoäc tính khoùa  A  K

X khoâng laø sieâu khoùa  X K

Toùm laïi ta coù KX, XA,X K vaø A  KX 

A phuï thuoäc baéc caàu vaøo K ñieàu naøy maâu thuaãn vôùi ñònh nghóa 2.



Heä quaû 1: Neáu Q ñaït chuaån 3 thì Q ñaït chuaån 2

Heä quaû 2: Neáu Q khoâng coù thuoäc tính khoâng khoùa thì Q ñaït chuaån 3.

Chöùng minh:

Heä quaû 1: Giaû söû Q ñaït daïng chuaån 3 vaø coù thuoäc tính khoâng khoùa A khoâng phuï thuoäc haøm ñaày ñuû vaøo khoùa K  K’ K sao cho K’A nhö vaäy ta coù KK’,K’A,K’ K, A  KK’ Q coù phuï thuoäc baéc caàu.

Heä quaû 2: moïi phuï thuoäc haøm trong Q ñeàu coù veá phaûi laø thuoäc tính khoùa  Q ñaït daïng chuaån 3

Ñònh lyù:

Q laø löôïc ñoà quan heä

F laø taäp caùc phuï thuoäc haøm coù veá phaûi moät thuoäc tính.

Q ñaït chuaån 3 neáu vaø chæ neáu moïi phuï thuoäc haøm XAF vôùi AX ñeàu coù X laø sieâu khoùa hay A laø thuoäc tính khoùa

Chöùng minh:

Q ñaït daïng chuaån 3 theo ñònh nghóa ta suy ra moïi phuï thuoäc haøm XAF vôùi AX coù X laø sieâu khoùa hoaëc A laø thuoäc tính khoùa.

Ngöôïc laïi ta phaûi chöùng minh neáu moïi phuï thuoäc haøm XAF vôùi AX coù X laø sieâu khoùa hoaëc A laø thuoäc tính khoùa thì moïi phuï thuoäc haøm XAF+ vôùi AX cuõng coù X laø sieâu khoùa hoaëc A laø thuoäc tính khoùa

Giaû söû coù phuï thuoäc haøm XAF+ vôùi AX sao cho X khoâng laø sieâu khoùa vaø A khoâng laø thuoäc tính khoùa seõ daãn ñeán A  X+  X  {caùc thuoäc tính khoùa} ñieàu naøy maâu thuaãn vôùi A  K.Tröôùc khi chöùng minh A  X+  X  {caùc thuoäc tính khoùa} ta coù nhaän xeùt sau:

X khoâng laø sieâu khoùa  X+ cuõng khoâng laø sieâu khoùa. Theo thuaät toaùn tìm bao ñoùng, X+ ñöôïc hình thaønh töø caùc Xi  ôû moãi böôùc Xi cuõng khoâng laø sieâu khoùa.

Böôùc cô sôû: X0 = X  X0  X  {caùc thuoäc tính khoùa}

Böôùc qui naïp: giaû söû coù Xi-1  X  {caùc thuoäc tính khoùa}. Bao ñoùng Xi ñöôïc hình thaønh do coù fj = Xj  Yj ñeå Xi-1  Xj vaø Xi = Xi-1  Yj  fj = Xj  Yj laø phuï thuoäc haøm coù Xj khoâng laø sieâu khoùa  fj = Xj  Yj laø phuï thuoäc haøm coù Yj laø thuoäc tính khoùa  Xi = Xi-1  Yj  X  {caùc thuoäc tính khoùa}

Qua chöùng minh treân  AX+  X  {caùc thuoäc tính khoùa} A X{caùc thuoäc tính khoùa}  A{caùc thuoäc tính khoùa} ñieàu naøy nghòch lyù vôùi ñieàu A  K.



Thuaät toaùn kieåm tra daïng chuaån 3

Vaøo: löôïc ñoà quan heä Q, taäp phuï thuoäc haøm F

Ra: khaúng ñònh Q ñaït chuaån 3 hay khoâng ñaït chuaån 3.

Böôùc 1: Tìm taát caû khoùa cuûa Q

Böôùc 2: Töø F taïo taäp phuï thuoäc haøm töông ñöông F1tt coù veá phaûi moät thuoäc tính.

Böôùc 3: Neáu moïi phuï thuoäc haøm X  A  F1tt vôùi AX ñeàu coù X laø sieâu khoùa hoaëc A laø thuoäc tính khoaù thì Q ñaït chuaån 3 ngöôïc laïi Q khoâng ñaït chuaån 3

Ví duï 5: Cho löôïc ñoà quan heä Q(A,B,C,D) F={ABC; DB; CABD}.Hoûi Q coù ñaït chuaån 3 khoâng?

Giaûi:

TN= TG={ABCD}



Xi

(TN  Xi)

(TN Xi)+

Sieâu khoùa

khoùa













A

A

A







B

B

B







AB

AB

ABCD

AB

AB

C

C

ABCD

C

C

AC

AC

ABCD

AC




BC

BC

ABCD

BC




ABC

ABC

ABCD

ABC




D

D

BD







AD

AD

ABCD

AD

AD

BD

BD

BD







ABD

ABD

ABCD

ABD




CD

CD

ABCD

CD




ACD

ACD

ABCD

ACD




BCD

BCD

ABCD

BCD




ABCD

ABCD

ABCD

ABCD



K1 = {AB}; K2 = {AD}; K3={C} laø caùc khoùa  moïi phuï thuoäc haøm XAF ñeàu coù A laø thuoäc tính khoùa. Vaäy Q ñaït chuaån 3


Ví duï 6: Quan heä sau ñaït chuaån 3. Q(N,G,P,M) F = {NGPM,MP}

ivDaïng Chuaån BC (Boyce-Codd Normal Form)


Moät quan heä Q ôû daïng chuaån BC neáu moïi phuï thuoäc haøm XA  F+ vôùi AX ñeàu coù X laø sieâu khoùa.
Heä quaû 1: Neáu Q ñaït chuaån BC thì Q ñaït chuaån 3 (hieån nhieân do ñònh nghóa)

Heä quaû 2: Moãi löôïc ñoà coù hai thuoäc tính ñeàu ñaït chuaån BC (xeùt phuï thuoäc haøm coù theå coù cuûa Q )

Ñònh lyù:

Q laø löôïc ñoà quan heä

F laø taäp caùc phuï thuoäc haøm coù veá phaûi moät thuoäc tính.

Q ñaït chuaån BC neáu vaø chæ neáu moïi phuï thuoäc haøm XAF vôùi AX ñeàu coù X laø sieâu khoùa

Chöùng minh:

Q ñaït daïng chuaån BC theo ñònh nghóa ta suy ra moïi phuï thuoäc haøm XAF vôùi AX coù X laø sieâu khoùa.



Ngöôïc laïi ta phaûi chöùng minh neáu moïi phuï thuoäc haøm XAF vôùi AX coù X laø sieâu khoùa thì moïi phuï thuoäc haøm ZBF+ vôùi BZ cuõng coù Z laø sieâu khoùa. Thaät vaäy, do ZB khoâng laø phuï thuoäc haøm hieån nhieân neân theo thuaät toaùn tìm bao ñoùng phaûi coù XAF sao cho ZX (X laø sieâu khoùa) Z laø sieâu khoùa.
Thuaät toaùn kieåm tra daïng chuaån BC

Vaøo: löôïc ñoà quan heä Q, taäp phuï thuoäc haøm F

Ra: khaúng ñònh Q ñaït chuaån BC hay khoâng ñaït chuaån BC.

Böôùc 1: Tìm taát caû khoùa cuûa Q

Böôùc 2: Töø F taïo taäp phuï thuoäc haøm töông ñöông F1tt coù veá phaûi moät thuoäc tính

Böôùc 3: Neáu moïi phuï thuoäc haøm X  A  F1tt vôùi AX ñeàu coù X laø sieâu khoùa thì Q ñaït chuaån BC ngöôïc laïi Q khoâng ñaït chuaån BC

Ví duï 7: Q(A,B,C,D,E,I) F={ACDEBI;CEAD}. Hoûi Q coù ñaït chuaån BC khoâng?

Giaûi: TN={C} TG={ADE}

Xi

(TN  Xi)

(TN Xi)+

Sieâu khoùa

khoùa



C

C







A

AC

AC







D

CD

CD







AD

ACD

ABCDEI

ACD

ACD

E

CE

ABCDEI

CE

CE

AE

ACE

ABCDEI

ACE




DE

CDE

ABCDEI

CDE




ADE

ACDE

ABCDEI

ACDE




F  F1tt={ACDE,ACDB,ACDI,CEA,CED}

Moïi phuï thuoäc haøm cuûa F1tt ñeàu coù veá traùi laø sieâu khoùa  Q ñaït daïng chuaån BC



Ví duï 8: Q(SV,MH,THAY)F = {SV,MH  THAY;THAY  MH}

Quan heä treân ñaït chuaån 3 nhöng khoâng ñaït chuaån BC..



Ví duï 9:

Chaúng haïn cho Q(A,B,C,D) vaø F={AB  C; D  B; C  ABD}

thì Q laø 3NF nhöng khoâng laø BCNF

Neáu F={B  D,A  C,C  ABD} laø 2 NF nhöng khoâng laø 3 NF


Thuaät toaùn kieåm tra daïng chuaån cuûa moät löôïc ñoà quan heä.

Vaøo: löôïc ñoà quan heä Q, taäp phuï thuoäc haøm F

Ra: khaúng ñònh Q ñaït chuaån gì?

Böôùc 1: Tìm taát caû khoùa cuûa Q

Böôùc 2: Kieåm tra chuaån BC neáu ñuùng thì Q ñaït chuaån BC, keát thuùc thuaät toaùn

ngöôïc laïi qua böôùc 3

Böôùc 3: Kieåm tra chuaån 3 neáu ñuùng thì Q ñaït chuaån 3, keát thuùc thuaät toaùn

ngöôïc laïi qua böôùc 4

Böôùc 4: Kieåm tra chuaån 2 neáu ñuùng thì Q ñaït chuaån 2, keát thuùc thuaät toaùn.

ngöôïc laïi Q ñaït chuaån 1
Ñònh nghóa: Daïng chuaån cuûa moät löôïc ñoà cô sôû döõ lieäu laø daïng chuaån thaáp nhaát trong caùc daïng chuaån cuûa caùc löôïc ñoà quan heä con.
1   ...   12   13   14   15   16   17   18   19   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