Xỉí l thäng tin trong CSDL

Trang 1
Chỉång4: TẠCH KHÄNG MÁÚT THÄNG TIN

Cho lỉåüc âäư quang hãû R=(A1,A2, ,An), tạch lỉåüc âäư quang hãû R l thay nọ båíi mäüt
bäü cạc lỉåüc âäư P=(R1,R2, ,Rk) sao cho R1∪R2∪ ∪Rk =R
Vê dủ: xẹt 2 lỉåüc âäư quang hãû NGUOI_CCKTNT(TEN,DCHI,TENMH,GIA),
Khi âọ våïi lỉåüc âäư quang hãû NGUOI_CCKTNT cọ táûpphủ thüc hm sau:
F=(TEN→DCHI;TEN,MATH→GIA)
khi âọ ta cọ thãø tạch lỉåüc âäư quang hãû NGUOI_CCKTNT thnh 2 lỉåüc âäư quang hãû
sau:
R1(TEN,DCHI), R2=(TEN,MATH,GIA)
khi âọ mi hiãûn hnh r ca R âỉåüc tạch ra thnh 2 quang hãû r1=ΠR1(r), r2= ΠR2(r).
Âãø phủc häưi lải R tỉì R1 v R2 ta cáưn näúi phẹp näúi R1∞ R2. (r = r1 ∞ r2)
Váún âãư âàût ra l khi no r = r1 ∞ r2.
4.1 Phẹp näúi khäng máút thäng tin
Cho lỉåüc âäư quang hãû R v táûp phủ thüc hm F trãn R, phẹp tạch P=(R1,R2, ,Rk)
âỉåüc gi l tạch cọ näúi khäng máút thäng tin (hay gi tàõt l tạch khäng máút thäng tin )
nãúu våïi mi quang hãû r ca Rtha mn F thç
r= ΠR1(r) ∞ΠR2(r) ∞ ∞ ΠRk(r)
Âàût Mp(r)= ΠR1(r) ∞ΠR2(r) ∞ ∞ ΠRk(r)
khi âọ âiãưu kiãûn näúi khäng máút thäng tin l : Våïi mi quang hãû r thüc R thaman F
thç Mp(r)= r
Bäø Âãư
Cho lỉåüc âäư quang hãû R v mäüt phẹp tạch P=(R1,R2, ,Rk), gi r l quang hãû ca R.
Âàût ri = ΠRi(r) ta cọ:
1. r ⊆ Mp(r)
2. nãúu s = Mp(r) thç ΠRi(s)=ri
3. Mp(r)=Mp(Mp(r))

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) tacọ ri= ΠRi(s) ⇒ r1 ∞ r2 ∞ ∞rk= ΠR1(s) ∞ ΠR2(s) ∞ ∞ΠRk(s)
= Mp(s)= Mp(Mp(r).
4.2 Thût toạn xạc âënh phẹp tạch cọ máút thäng tin hay khäng
Thût toạn:
Dỉỵ liãûu vo:
- Lỉåüc âäư quang hãû R
- Táûp phủ thüc hm F
Phẹp tạch P(R1,R2, ,Rk)
Ra: Xạc âënh liãûu phẹp tạch P cọ máút thäng tin hay khäng.
Phỉång phạp:
R=(A1,A2, An)
Ta xáy dỉûng mäüt bng k dng, n cäüt. Cạc dng ca bng âỉåüc âạnh dáúu båíi cạc thüc
tênh R1, R2, ,Rk, cạc cäüt âỉåüc âạnh dáu båíi cạc thüc tênh A1,A2, ,An.
Trong bng âiãưn cạc k hiãûu nhỉ sau:
- Vë trê ỉïng våïi cäüt Ả v dng Ri thç ghi aj nãúu Aj∈Ri hồûc ghi bij nãúu Aj ∉Ri
- Biãún âäøi cạc k hiãûu trong bng theo quy tàõt sau:
1. ỈÏng våïi mäùi phủ thüc hm X → Y ∈ F tçm cạc càûp dng (2 dong mäüt) m giạ trë
ca nọ trng nhau trãn cạc vë trê tỉång ỉïng cạc cäüt trong X thç lm bàòng cạc k hiãûu
tỉång ỉïng våïi cạc vë trê trong Y, ngun tàõt lm bàòng nhỉ sau:
- nãúu mäüt trong hai k hiãûu ỉïng våïi thüc tênh Aj l aj thç thay giạ trë kia bàòng aj. Nãúu
c hai k hiãûu ỉïng våïi thüc tênh Aj l blj v bij thç thay chụng bàòng blj hồûc bij âãø
cho chụng giäúng nhau.
2. Làûp lải quạ trçnh 1 cho âãún khi khäng cn cọ sỉû thay âäøi no trãn bng.
3. Nãúu trong bng kãút qu cọ êt nháút mäüt dng ton k hiãûu a(a1,a2, an) thç phẹp tạch
l khäng máút thäng tin , ngỉåüc lải thç phpe tạch máút thäng tin.

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

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 chøn họa Chøn họa
3 500 1

4.2.1Cạc dảng chøn
Trong l thuút ban âáưu Codd âỉa ra 3 dảng chøn ca quan hãû sau:

Dảng ban âáưu(Khäng chøn họa) Dảng chøn thỉï nháút (1NF - first normal form)

Xỉí l thäng tin trong CSDL

Trang 5 Dảng chøn thỉï 2 (2NF)

Họa 11 Lan 20 30_LTT 7.0
Họa 12 Hue 21 24_PÂP 6.0
L 11 Lan 20 30_LTT 5.0
L 13 An 22 12_HV 4.0

Våïi 2 hiãûn hnh trãn xút hiãûn mäüt säú váún âãư nhỉ sau:

Xỉí l thäng tin trong CSDL

Trang 6
1 ÅÍ quan hãû SINHVIEN , viãûc lỉu trỉỵ thäng tin vê dủ nhỉ sinh viãn cọ m sinh viãn
11 phi làûp lải 3 láưn âëa chè, 3 láưn tøi. R rng l quạ dỉ thỉìa
2. Khi cáưn thay âäøi thäng tin âäúi våïi mäüt mäüt sinh viãn phi thay âäøi táút c cạc bäü
ỉïng våïi sinh viãn âọ. Vê dủ nhỉ âäúi våïi sinh viãn tãn l Lan thç phi thay âäøi åí c 3 bäü,
r rng l täún kẹm thåìi gian.Hån nỉỵa khi sỉỵa âäøi thäng tin vãư sinh viãn thç khäng liãn
quan gç âãún thäng tin vãư thi cỉí.
3. khäng thãø bäø sung mäüt sinh viãn måïi vo quan hãû SINHVIEN nãúu sinh viãn ny
chỉa thi män novç trong quan hãû SINHVIEN chè chỉïa thäng tin vãư nhỉỵng sinh viãn â
thi.
4. Gi sỉí vç mäüt l do no âọ cáưn phi hy b män thi L m danh sạch sinh viãn váùn
giỉỵ ngun . Khi âọ trong quan hãû THI ta xọa bäü (L, T.THANH), cn åí quan hãû
SINHVÈN nãúu xọa män thi L thç thäng tin vãư sinh viãn An s máút.

Âãø khàõc phủc cạc báút låüi trãn ta cọ thãø tạch Lỉåüc âäư quan hãû SINHVIEN thnh 2 lỉåüc
âäư quan hãû sau:
SINHVIẺN(MSSV,TEN,TUOI,DCHI) v THIXONG(MSSV,MONTHI,DIEM)
Nhỉ váûy lục ny CSDL thnh 3 quan hãû â âỉåüc chøn họa v åí dảng chøn thỉï hai.
Âënh nghéa
Lỉåüc âäư quan hãû U âỉåüc gi l dảng chøn 2 , k hiãûu l 2NF nãúu nọ åí dảng chøn 1
v mi khọa ca U phủ thüc hm âáưy â vo khọa chênh.


Trang 7
Y
A

Qua så âäư ta tháúy ràòng A cọ thãø xạc âënh hm Y. trong trỉåìng håüp A khäng xạc âënh
hm Y gi l tênh bàõt cáưu chàût.
Tênh bàõt cáưu s âỉåüc sỉí dủng trong 3NF. Âiãưu kiãûn A ∉XY l cáưn thiãút vç ràòng nãúu A
⊆Y⊆X thç theo lût phn xả ta ln cọ X → Y→ A. âiãưu kiãûn Y → X âãø loải b
nhiãưu khọa khi dảng chøn 3NF. Cng nhỉ åí 2NF viãûc loải b phủ thüc batỉï cáưu
âãø âi âãún 3NF nhàòm la b nhỉỵng dë thỉåìng gáy ra do quạ trçnh cáûp nháût dỉỵ liãûu vp
quan hãû . tỉì dọ ta cọ âënh nghéa sau:
Âënh nghéa
Lỉåüc âäư quan hãû R âỉåüc gi l åí dảng chøn 3NF nãúu R åí dảng chøn 2NF v mäùi
thüc tênh khäng khọa ca R l khäng phủ thuuc hm bàõt cáưu vo khọa chênh.
Vê dủ:
Cho lỉåüc âäư quan hãû R=( SAIP)
Våïi cạc phủ thüc hm nhỉ sau:
SI →P v S →A
Ta tháúy ràòng R khängåí dảng chøn 3NF. Gi sỉí X = SI, Y= S. A l thüc tênh khäng
khọa ( åí âáy khọa l SI). Vç X → Y v Y → A v X → Y ( S khäng suy ra SI) chỉïng
t ràòng A phủ thüc bàõt cáưu vo khọa chênh.

Hồûc

Âàût r1 = ΠR1(r), do âọ r1 tha mn F1= ΠR1(F), màût khạc do phẹp tạch Q=(S1,S2)
ca R1 l khäng máút thäng tin nãn
r1=ΠS1(r1) ∞ ΠS2(r1)
= ΠS1(ΠR1(r)) ∞ ΠS2(ΠR1(r))
= ΠS1(r) ∞ ΠS2(r)
Váûy ta cọ: r= ΠR1(r) ∞ ΠR2(r) ∞ ∞ ΠRn(r)
= ΠS1(r) ∞ ΠS2(r) ∞ ΠR2(r) ∞ ∞ ΠRn(r)
âiãưu ny chỉïng t phẹp tạch P’= {S1,S2,R2, ,Rn} cng khäng máút thäng tin.
Tỉì bäø âãư ny ta suy ra phỉång phạp tạch mäüt lỉåüc âäư quan hãû thnh cạc lỉåüc âäư åí dảng
chøn BCNF
Cho lỉåüc âäư quan hãû R v táûp phủ thüc hm F.Nãúu R khäng åí dảng chøn BCNF thç
tçm âỉåüc êt nháút l mäüt phủ thüc hm X→A, A∉X v X khäng phi l siãu khọa( X
khäng suy ra R). Khi âọ tạch R thnh 2 lỉåüc âäư quan hãû sau:
R-A v XA
Khi âọ ta cọ R-A ∩XA = X
X→A=(XA-(R-A))
Do âọ phẹp tạch l khäng máút thäng tin.
Nãúu lỉåüc âäư R1 åí dảng chøn BCNF âäúi våïi ΠR1(F) thç âỉa R1 vo phẹp tạch. Ngỉåüc
lải thç R1 chỉa åí dảng chøn BCNF âäúi våïi ΠR1(F) thç tiãúp tủc quạ trçnh trãn .
ÅÍ âáy R1= R-a hồûc R1=XA Bäø âãư:2
1. Mi lỉåüc âäư quan hãû chè cọ 2 thüc tênh âãưu åí dảng chøn BCNF
2. Nãúu lỉåüc âäư quan hãû R khäng åí dảng chøn BCNF thç cọ thãø tçm ra âỉåüc hai thüc
tênh A v B sao cho (R-AB ) → A âụng trong R
Chỉïng minh.
1 Mi lỉåüc âäư quan hãû chè cọ 2 thüc tênh âãưu åí dảng chøn BCNF

Xỉí l thäng tin trong CSDL

Th tủc Tạch
If Z khäng chỉïa A,B sao cho A∈(Z-AB)
+
then Return
Else
Begin
Láúy càûp A,B tha mn A∈(Z-AB)
+

Y:=Z-B
While Y cn chỉïa A,b sao cho A∈(Z-AB)
+
do
Y:= Y-B
Z:=Y
Return
Vê dủ:
Xẹt lỉåüc âäư quan hãû U= CTHRSG
Åí âáy:

Xổớ lyù thọng tin trong CSDL

Trang 10
C: mọn hoỹc (ngoaỷi ngổợ)
T: Giaùo vión
H: Giồỡ hoỹc
R: phoỡng hoỹc
G: trỗnh õọỹ
S: Sinh vión
Ta coù tỏỷp phuỷ thuọỹc haỡm F={ CT, RHC, HTR, CSG, HSR } trong õoù caùc

Khi õoù ta coù thóứ taùch U= CTHRSG thaỡnh
1. HRS : õoùng vai troỡ laỡ XA vồùi X=HS , A=R
2. Z:= CTHRSG-A = CTHSG
Tióỳp tuỷc taùch phỏửn coỡn laỷi Z= CTHSG nhổ õaợ laỡm ồớ trón
Danh saùch caùc cỷp A,B lỏửn lổồỹt nhổ sau:
1. trong CTHSG A= T, B= H Y= CTSG
2. trong CTSG A= T, B=S Y= CTG
2. trong CTG A= T, B=G Y= CT
Y= CT ồớ daỷng chuỏứn BCNF, trong õoù CT, õổa CT vaỡo pheùp taùch vồùi XA
=CT,X=C,A=T
Z= CHSG ( chổa ồớ daỷng BCNF) tióỳp tuỷc taùch
Trong CHSG A= G, B=H Y= CSG

Xổớ lyù thọng tin trong CSDL

Trang 11
Ta coù phuỷ thuọỹc haỡm CSG F nón Y= CSG ồớ daỷng chuỏứn BCNF, õổa BCNF vaỡo
pheùp taùch
XA=CSG, X=CS, A=G
Phỏửn coỡn laỷi Z= CHSG-A = CHS ồớ daỷng chuỏứn BCNF
Vỏỷy cuọỳi cung ta coù pheùp taùch P khọng mỏỳt thọng tin vaỡ caùc pheùp taùch ồớ daỷng BCNF
nhổ sau
P= { HRS, CT, CSG, CHS }