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

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

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

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

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

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

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

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

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

• 
  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.
  

TN={ACB} TG={E}

Xi	(TN  Xi)	(TN Xi)+	Sieâu khoùa	khoùa
	ACB	ABCDEH	ACB	ACB
E	ACBE	ABCDEH	ACBE

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

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
  

• 
  Hoaëc X laø sieâu khoùa
  
• 
  Hoaëc A laø thuoäc tính khoùa
  

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

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
  

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: 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 X_i  ôû moãi böôùc X_i cuõng khoâng laø sieâu khoùa.

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

Böôùc qui naïp: giaû söû coù X_i-1  X  {caùc thuoäc tính khoùa}. Bao ñoùng X_i ñöôïc hình thaønh do coù f_j = X_j  Y_j ñeå X_i-1  X_j vaø X_i = X_i-1  Y_j  f_j = X_j  Y_j laø phuï thuoäc haøm coù X_j khoâng laø sieâu khoùa  f_j = X_j  Y_j laø phuï thuoäc haøm coù Y_j laø thuoäc tính khoùa  X_i = X_i-1  Y_j  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.

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

K₁ = {AB}; K₂ = {AD}; K₃={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

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

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.

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

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

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

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