Xæí lyï thäng tin trong CSDL
Trang 1
Chæång4: TAÏCH KHÄNG MÁÚT THÄNG TIN
Cho læåüc âäö quang hãû R=(A1,A2,...,An), taïch læåüc âäö quang hãû R laì thay noï båíi mäüt
bäü caïc læåüc âäö P=(R1,R2,...,Rk) sao cho R1∪R2∪...∪Rk =R
Vê duû: xeït 2 læåüc âäö quang hãû NGUOI_CCKTNT(TEN,DCHI,TENMH,GIA),
Khi âoï våïi læåüc âäö quang hãû NGUOI_CCKTNT coï táûpphuû thuäüc haìm sau:
F=(TEN→DCHI;TEN,MATH→GIA)
khi âoï ta coï thãø taïch læåüc âäö quang hãû NGUOI_CCKTNT thaình 2 læåüc âäö quang hãû
sau:
R1(TEN,DCHI), R2=(TEN,MATH,GIA)
khi âoï moüi hiãûn haình r cuía R âæåüc taïch ra thaình 2 quang hãû r1=ΠR1(r), r2= ΠR2(r).
Âãø phuûc häöi laûi R tæì R1 vaì R2 ta cáön näúi pheïp näúi R1∞ R2. (r = r1 ∞ r2)
Váún âãö âàût ra laì khi naìo r = r1 ∞ r2.
4.1 Pheïp näúi khäng máút thäng tin
Cho læåüc âäö quang hãû R vaì táûp phuû thuäüc haìm F trãn R, pheïp taïch P=(R1,R2,...,Rk)
âæåüc goüi laì taïch coï näúi khäng máút thäng tin (hay goüi tàõt laì taïch khäng máút thäng tin )
nãúu våïi moüi quang hãû r cuía Rthoía maîn F thç
r= ΠR1(r) ∞ΠR2(r) ∞ ...∞ ΠRk(r)
Âàût Mp(r)= ΠR1(r) ∞ΠR2(r) ∞ ...∞ ΠRk(r)
khi âoï âiãöu kiãûn näúi khäng máút thäng tin laì : Våïi moüi quang hãû r thuäüc R thoîaman F
thç Mp(r)= r
Bäø Âãö
Cho læåüc âäö quang hãû R vaì mäüt pheïp taïch P=(R1,R2,...,Rk), goüi r laì quang hãû cuía R.
Âàût ri = ΠRi(r) ta coï:
1. r ⊆ Mp(r)
2. nãúu s = Mp(r) thç ΠRi(s)=ri
3. Mp(r)=Mp(Mp(r))
chæïng minh
1. r ⊆ Mp(r)
Chuï yï r laì quang hãû (táûp håüp), mäùi pháön tæí cuía r laì mäüt bäü (xãúp theo ma tráûn laì mäüt
haìng). Láúy mäüt bäü t∈r; âàût ti=t(Ri)
(t=(a1,a2,...,an)
Trong âoï t(Ri) laì nhæîng thaình pháön æïng våïi caïc thuäüc tênh cuía Ri
Vê duû
A
B C D
1 4 5 2
t=3 2 7 6
3 3 7 4
R1=BC khi âoï ΠR1(r) = B C
4 5
Xæí lyï thäng tin trong CSDL
Trang 2
2 7
3 7
Khi âoï t(r1) = 2 7
Ti = t(Ri) ∈ ΠRi(r)
t= t1 ∞ t2 ∞...∞ tk ⊆ ΠR1(r) ∞ ΠR2(r)∞...∞ ΠRk(r)
t ⊆ Mp(r)
2. nãúu s = Mp(r) thç ΠRi(s)=ri
tæì (1) ta coï r ⊆ Mp(r) ⇒ ΠRi(r)⊆ΠRi(Mp(r))
⇒ ri⊆ΠRi(s)
Chæïng minh ngæåüc laûi ΠRi(s) ⊆ ri
Láúy ti ∈ ΠRi(s) (i=1..k)
Âàût t= t1∞ t2∞...∞ tk ∈Mp(Mp(r)) =Mp(s)
(vç ΠR1(s) ∞ ΠR2(s) ∞ ... ∞ΠRk(s) = Mp(s)= Mp(Mp(r)))
ti ∈ΠR1(r) ∞ ΠR2(r) ∞ ... ∞ΠRk(r) =ΠRi(ΠRi(r)) = ΠRi(r) = ri (dpcm)
3. Mp(r)=Mp(Mp(r))
tæì (2) tacoï ri= ΠRi(s) ⇒ r1 ∞ r2 ∞...∞rk= ΠR1(s) ∞ ΠR2(s) ∞ ... ∞ΠRk(s)
= Mp(s)= Mp(Mp(r).
4.2 Thuáût toaïn xaïc âënh pheïp taïch coï máút thäng tin hay khäng
Thuáût toaïn:
Dæî liãûu vaìo:
- Læåüc âäö quang hãû R
- Táûp phuû thuäüc haìm F
Pheïp taïch P(R1,R2,...,Rk)
Ra: Xaïc âënh liãûu pheïp taïch P coï máút thäng tin hay khäng.
Phæång phaïp:
R=(A1,A2,...An)
Ta xáy dæûng mäüt baíng k doìng, n cäüt. Caïc doìng cuía baíng âæåüc âaïnh dáúu båíi caïc thuäüc
tênh R1, R2,...,Rk, caïc cäüt âæåüc âaïnh dáu båíi caïc thuäüc tênh A1,A2,...,An.
Trong baíng âiãön caïc kyï hiãûu nhæ sau:
- Vë trê æïng våïi cäüt AÛ vaì doìng Ri thç ghi aj nãúu Aj∈Ri hoàûc ghi bij nãúu Aj ∉Ri
- Biãún âäøi caïc kyï hiãûu trong baíng theo quy tàõt sau:
1. ÆÏng våïi mäùi phuû thuäüc haìm X → Y ∈ F tçm caïc càûp doìng (2 dong mäüt) maì giaï trë
cuía noï truìng nhau trãn caïc vë trê tæång æïng caïc cäüt trong X thç laìm bàòng caïc kyï hiãûu
tæång æïng våïi caïc vë trê trong Y, nguyãn tàõt laìm bàòng nhæ sau:
- nãúu mäüt trong hai kyï hiãûu æïng våïi thuäüc tênh Aj laì aj thç thay giaï trë kia bàòng aj. Nãúu
caí hai kyï hiãûu æïng våïi thuäüc tênh Aj laì blj vaì bij thç thay chuïng bàòng blj hoàûc bij âãø
cho chuïng giäúng nhau.
2. Làûp laûi quaï trçnh 1 cho âãún khi khäng coìn coï sæû thay âäøi naìo trãn baíng.
3. Nãúu trong baíng kãút quaí coï êt nháút mäüt doìng toaìn kyï hiãûu a(a1,a2,...an) thç pheïp taïch
laì khäng máút thäng tin , ngæåüc laûi thç phpe taïch máút thäng tin.
Vê duû1
Xæí lyï thäng tin trong CSDL
Trang 3
Cho læåüc âäö quang hãû R=ABCDE
Taïch R thaình caïc læåüc âäö sau:
R1 = AD, R2=AB, R3= BE, R4= CDE, R5= AE
táûp phuû thuäüc haìm F=(A→C,B→C,C→D,DE→C,CE→A)
Xaïc âënh pheïp taïch trãn coï máút thäng tin hay khäng
láûp baíng:
A B C D E
AD a1 b12 b13 a4 b15
AB a1 a2 b23
(b13)
b24
(a4)
b25
BE b31
(a1)
a2 b33
(b13)(a3)
b34
(a4)
a5
CDE b41 b42 a3 a4 a5
AE a1 b52 b53
(b13)(a3)
b54
(a4)
a5
Pheïp taïch trãn khäng máút thäng tin vç coï doìng BE toaìn kyï hiãûu a
Vê duû 2:
Xeït quan hãû ngæåìi cung cáúp nhæ sau:
S(PRO, PRICE, ADD, PRO, PRICE)
Âæåüc taïch thaình 2 læåüc âäö quan hãû sau
S1(SNAME, ADD)
S2(SNAME, PRO, PRICE)
Våïi caïc phuû thuäüc haìm nhæ sau:
SNAME → ADD
SNAME,PRO →PRICE
Ban âáöu ta thiãút láûp baíng nhæ sau:
SNAME ADD PRO PRICE
S1 a1 a2 b13 b14
S2 a1 b22 (a2) a3 a4
Xæí lyï thäng tin trong CSDL
Trang 4
AÏp duûng phuû thuäüc haìm SNAME→ADD cho hai haìng cuía baíng. Hai baíng bàòng nhau
trãn cäüt SNAME ( âãöu bàòng a1) nãn åí cäüt ADD chuïng âæåüc laìm bàòng vaì laìm bàòng a2
Baíng kãút quaí laì
SNAME ADD PRO PRICE
S1 a1 a2 b13 b14
S2 a1 a2 a3 a4
Baíng kãút quaí coï doìng thæï hai giaï trë toaìn laì a , do âoï kãút quaí näúi laì khäng máút thäng
tin
4.2 Chuáøn hoïa læåüc âäö quang hãû
Do viãûc cáûp nháút dæî liãûu (qua caïc pheïp tênha cheìn, loaûi boí, sæía âäøi) gáy nãn nhæîng dë
thæåìng cho nãn caïc quan hãû cáön thiãút phaíi âæåüc biãún âäøi thaình nhæîng daûng phuì håüp.
Quaï trçnh âoï âæåüc xem laì quaï trçnh chuáøn hoïa. Quan hãû âæåüc chuáøn hoïa laì quan hãû
trong âoï mäùi miãön cuía mäüt thuäüc tênh chê chæïa nhæîng giaï trë nguyãn täú tæïc laì khäng
phán nhoí âæåüc næîa.
Quan hãû coï chæïa caïc miãön trë khäng nguyãn täú goüi laì quan hãû khäng chuáøn hoïa . Mäüt
quan hãû âæåüc chuáøn hoïa coï thãø thaình mäüt hoàûc nhiãöu quan hãû chuáøn hoïa khaïc vaì
khäng laìm máút thäng tin.
Vê duû
S# PRO S# P# QTY
P# QTY
100 1 1 100 1
200 2 1 200 2
1
300 1 1 300 1
100 4 2 100 4 2
200 2 2 200 2
400 5 3 400 5 3
500 1
Khäng chuáøn hoïa
Chuáøn hoïa
3 500 1
4.2.1Caïc daûng chuáøn
Trong lyï thuyãút ban âáöu Codd âæa ra 3 daûng chuáøn cuía quan hãû sau:
Daûng ban âáöu(Khäng chuáøn hoïa)
Daûng chuáøn thæï nháút (1NF - first normal form)
Xæí lyï thäng tin trong CSDL
Trang 5
Daûng chuáøn thæï 2 (2NF)
Daûng chuáøn thæï 3 (3NF)
1. Daûng chuáøn 1 (1NF - first normal form)
Mäüt læåüc âäö quan hãû R âæåüc goüi laì åí daûng chuáøn mäüt (1NF) nãúu vaìchè nãúu táút caí miãön
giaï trë cuía caïc thuäüc tênh cuía R âãöu nguyãn täú (khäng thãø phán chia âæåüc)
Chuï yï: Tênh khäng thãø phán chia âwoüc coï tênh cháút tæång âäúi.
Âënh nghéa naìy cho tháúy ngay ràòng báút kyì quan hãû chuáøn hoïa naìo cuîng åí 1NF.
2. Daûng chuáøn 2 ( 2NF- Second normal form)
træåïc khi nghiãn cæïu daûng áønnnn thæ 2 , ta xeït Vê duû sau âáy:
Xeït CSDL gäöm 2 læåüc âäö quan hãû THI(MONTHI,GIAOVIEN) vaì
SINHVIEN(MONTHI, MSSV, TEN, TUOI, DCHI, DIEM) phaín aïnh thäng tin vãö kãút
quaí thi cuía mäüt âån vë naìo âoï.
Trong quan hãû THI thç MONTHI laì khoïa vaì trong quan hãû SINHVIEN thç MOMTHI
vaì MSSV laì khoïa.
ÅÍ quan hãû thæï hai dãù nháûn tháúy ràòng MONTHI, MSSV,DIEM xaïc âënh kãút quaí thi cuía
sinh viãn coìn MSSV,TEN,TUOI,DCHI xaïc âënh âäúi tæåüng dæû thi
Xeït caïc hiãûn haình cuía 2 læåüc âäö quan hãû THI vaì SINHVIEN nhæ sau:
THI
MOÜNTHI GIAOVIEN
Toaïn T.ÂINH
Lyï T.THAÛNH
Hoïa T.DUÎNG
SINHVIEN
MONTHI MSSV TEN TUOI DCHI DIEM
Toaïn 11 Lan 20 30_LTT 8.0
Toaïn 12 Hue 21 24_PÂP 7.5
Hoïa 11 Lan 20 30_LTT 7.0
Hoïa 12 Hue 21 24_PÂP 6.0
Lyï 11 Lan 20 30_LTT 5.0
Lyï 13 An 22 12_HV 4.0
Våïi 2 hiãûn haình trãn xuáút hiãûn mäüt säú váún âãö nhæ sau: