Tách không mất thông tin

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=PR1(r), r2= PR2(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= PR1(r) ¥PR2(r) ¥ ...¥ PRk(r) Âàût Mp(r)= PR1(r) ¥PR2(r) ¥ ...¥ PRk(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 = PRi(r) ta coï: 1. r Í Mp(r) 2. nãúu s = Mp(r) thç PRi(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ï PR1(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) Î PRi(r) t= t1 ¥ t2 ¥...¥ tk Í PR1(r) ¥ PR2(r)¥...¥ PRk(r) t Í Mp(r) 2. nãúu s = Mp(r) thç PRi(s)=ri tæì (1) ta coï r Í Mp(r) Þ PRi(r)ÍPRi(Mp(r)) Þ riÍPRi(s) Chæïng minh ngæåüc laûi PRi(s) Í ri Láúy ti Î PRi(s) (i=1..k) Âàût t= t1¥ t2¥...¥ tk ÎMp(Mp(r)) =Mp(s) (vç PR1(s) ¥ PR2(s) ¥ ... ¥PRk(s) = Mp(s)= Mp(Mp(r))) ti ÎPR1(r) ¥ PR2(r) ¥ ... ¥PRk(r) =PRi(PRi(r)) = PRi(r) = ri (dpcm) 3. Mp(r)=Mp(Mp(r)) tæì (2) tacoï ri= PRi(s) Þ r1 ¥ r2 ¥...¥rk= PR1(s) ¥ PR2(s) ¥ ... ¥PRk(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: Xæí lyï thäng tin trong CSDL Trang 6 1 ÅÍ quan hãû SINHVIEN , viãûc læu træî thäng tin vê duû nhæ sinh viãn coï maî sinh viãn 11 phaíi làûp laûi 3 láön âëa chè, 3 láön tuäøi. Roî raìng laì quaï dæ thæìa 2. Khi cáön thay âäøi thäng tin âäúi våïi mäüt mäüt sinh viãn phaíi thay âäøi táút caí caïc bäü æïng våïi sinh viãn âoï. Vê duû nhæ âäúi våïi sinh viãn tãn laì Lan thç phaíi thay âäøi åí caí 3 bäü, roî raìng laì täún keï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 vaìo quan hãû SINHVIEN nãúu sinh viãn naìy chæa thi män naìovç trong quan hãû SINHVIEN chè chæïa thäng tin vãö nhæîng sinh viãn âaî thi. 4. Giaí sæí vç mäüt lyï do naìo âoï cáön phaíi huíy boí män thi Lyï maì danh saïch sinh viãn váùn giæî nguyãn . Khi âoï trong quan hãû THI ta xoïa bäü (Lyï, T.THANH), coìn åí quan hãû SINHVÈN nãúu xoïa män thi Lyï thç thäng tin vãö sinh viãn An seî máút. Âãø khàõc phuûc caïc báút låüi trãn ta coï thãø taïch Læåüc âäö quan hãû SINHVIEN thaình 2 læåüc âäö quan hãû sau: SINHVIEÛN(MSSV,TEN,TUOI,DCHI) vaì THIXONG(MSSV,MONTHI,DIEM) Nhæ váûy luïc naìy CSDL thaình 3 quan hãû âaî âæåüc chuáøn hoïa vaì åí daûng chuáøn thæï hai. Âënh nghéa Læåüc âäö quan hãû U âæåüc goüi laì daûng chuáøn 2 , kyï hiãûu laì 2NF nãúu noï åí daûng chuáøn 1 vaì moüi khoïa cuía U phuû thuäüc haìm âáöy âuí vaìo khoïa chênh. (Chuï yï: X®Y laì phuû thuäüc haìm âáöy âuí nãúu khäng täön taûi mäüt ZÌX maì Z®Y laì âuïng.) 4. Daûng chuáøn 3 cho læåüc âäö quan hãû U vaì táûp phuû thuäüc haìm F. nãúu thuäüc tênh A cuía U âæåüc goüi laì thuäüc tênh khoïa nãúu A laì thaình pháön cuía 1 khoïa naìo âoï. Ngæåüc laì A âæåüc goüi laì thuäüc tênh khäng khoïa nãúu noï khäng phaíi laì thaình pháön cuía mäüt khoïa naìo caí trong U Vê duû: U= ABCD F=(AB®C, B®D, BC®A) Dãù daìng kiãøm tra AB vaì BC laì caïc khoïa cuía U , tæì âoï suy ra A,B,C laì caïc thuäüc tênh khoïa D khäng phaíi laì thuäüc tênh khoïa Khaïi niãûm vãö phuû thuäüc bàõt cáöu Cho mäüt læåüc âäö quan hãû R(U); X laì táûp con caíu caïc thuäüc tênh X ÍU, A laì mäüt thuäüc tênh thuäüc U.A âæåüc goüi laì phuû thuäüc bàõt cáöu vaìo X trãn R nãúu täön taûi mäüt táûp con Y cuía U sao cho X ®Y, Y®A nhæng Y ®X (Khäng xaïc âënh haìm X) våïi A ÏXY Tênh bàõt cáöu thãø hiãûn qua så âäö sau: X Xæí lyï thäng tin trong CSDL Trang 7 Y A Qua så âäö ta tháúy ràòng A coï thãø xaïc âënh haìm Y. trong træåìng håüp A khäng xaïc âënh haìm Y goüi laì tênh bàõt cáöu chàût. Tênh bàõt cáöu seî âæåüc sæí duûng trong 3NF. Âiãöu kiãûn A ÏXY laì cáön thiãút vç ràòng nãúu A ÍYÍX thç theo luáût phaín xaû ta luän coï X ® Y® A. âiãöu kiãûn Y ® X âãø loaûi boí nhiãöu khoïa khoíi daûng chuáøn 3NF. Cuîng nhæ åí 2NF viãûc loaûi boí phuû thuäüc batæï cáöu âãø âi âãún 3NF nhàòm loëa boí nhæîng dë thæåìng gáy ra do quaï trçnh cáûp nháût dæî liãûu vaìp quan hãû . tæì doï ta coï âënh nghéa sau: Âënh nghéa Læåüc âäö quan hãû R âæåüc goüi laì åí daûng chuáøn 3NF nãúu R åí daûng chuáøn 2NF vaì mäùi thuäüc tênh khäng khoïa cuía R laì khäng phuû thuuoüc haìm bàõt cáöu vaìo khoïa chênh. Vê duû: Cho læåüc âäö quan hãû R=( SAIP) Våïi caïc phuû thuäüc haìm nhæ sau: SI ®P vaì S ®A Ta tháúy ràòng R khängåí daûng chuáøn 3NF. Giaí sæí X = SI, Y= S. A laì thuäüc tênh khäng khoïa ( åí âáy khoïa laì SI). Vç X ® Y vaì Y ® A vaì X ® Y ( S khäng suy ra SI) chæïng toí ràòng A phuû thuäüc bàõt cáöu vaìo khoïa chênh. Hoàûc Cho læåüc âäö quan hãû R=(CSZ) våïi caïc phuû thuäüc haìm nhæ sau: CS®Z, Z® C Trong læåüc âäö quan hãû naìy moüi thuäüc tênh âãöu laì thuäüc tênh khoïa . do âoï R åí daûng chuáøn 3NF 3 Daûng chuáøn Boyce Codd Cho læåüc âäö quan hãû R vaì táûp phuû thuäüc haìm F, R âæåüc goüi lag daûng chuáøn Boyce Codd , kyï hiãûu BCNF nãúu X®A âuïng trong R vaì AÏX thç X phaíi laì mäüt khoïa cuía R. Vê duû: R= CZS nhæ trãn F=(CS®Z, Z®C) Ta tháúy Z®C âuïng trong F, CÏZ vaì Z khäng phaíi laì mäüt khoïa cuía R( khoïa cuía R laì CS hoàûc CZ) suy ra R åí 3NF nhæng khäng phaíi laì chuáøn BCNF Tæì vê duû naìy ta tháúy mäüt læåüc âäö quan hãû coï thãø åí chuáøn 3NF nhæng khäng åí BCNF. Xæí lyï thäng tin trong CSDL Trang 8 4.2.3 Taïch khäng máút thäng tin thaình caïc daûng chuáøn BCBF Cho læåüc âäö quan hãû U, táûp phuû thuäüc haìm F, R ÍU. Chiãúu cuía F lãn R laì táûp phuû thuäüc haìm Kyï hiãûu PR(F) âæåüc xaïc âënh nhæ sau: PR(F) = (X®Y sao cho X,Y ÍR, F suy ra logic X®Y) Bäø âãö:1 Giaí sæí R laì læåüc âäö quan hãû ,F laì táûp phuû thuäüc haìm trãn R, P={R1,R2,..,Rn} laì pheïp taïch khäng máút thäng tin âäúi våïi R.Nãúu Q=(S1,S2) laì pheïp taïch khäng máút thäng tin cuía R1 âäúi våïi táûp phuû thuäüc haìm F1= PR1(F) Thç pheïp taïch P’= {S1,S2,R2,..,Rn} cuîng khäng máút thäng tin. Chæïng minh: Láúy 1 quan hãû r thoía maîn F do P laì pheïp taïch khäng máút thäng tin nãn r= PR1(r) ¥ PR2(r) ¥ ... ¥ PRn(r) Âàût r1 = PR1(r), do âoï r1 thoía maîn F1= PR1(F), màût khaïc do pheïp taïch Q=(S1,S2) cuía R1 laì khäng máút thäng tin nãn r1=PS1(r1) ¥ PS2(r1) = PS1(PR1(r)) ¥ PS2(PR1(r)) = PS1(r) ¥ PS2(r) Váûy ta coï: r= PR1(r) ¥ PR2(r) ¥ ... ¥ PRn(r) = PS1(r) ¥ PS2(r) ¥ PR2(r) ¥ ... ¥ PRn(r) âiãöu naìy chæïng toí pheïp taïch P’= {S1,S2,R2,..,Rn} cuîng khäng máút thäng tin. Tæì bäø âãö naìy ta suy ra phæång phaïp taïch mäüt læåüc âäö quan hãû thaình caïc læåüc âäö åí daûng chuáøn BCNF Cho læåüc âäö quan hãû R vaì táûp phuû thuäüc haìm F.Nãúu R khäng åí daûng chuáøn BCNF thç tçm âæåüc êt nháút laì mäüt phuû thuäüc haìm X®A, AÏX vaì X khäng phaíi laì siãu khoïa( X khäng suy ra R). Khi âoï taïch R thaình 2 læåüc âäö quan hãû sau: R-A vaì XA Khi âoï ta coï R-A ÇXA = X X®A=(XA-(R-A)) Do âoï pheïp taïch laì khäng máút thäng tin. Nãúu læåüc âäö R1 åí daûng chuáøn BCNF âäúi våïi PR1(F) thç âæa R1 vaìo pheïp taïch. Ngæåüc laûi thç R1 chæa åí daûng chuáøn BCNF âäúi våïi PR1(F) thç tiãúp tuûc quaï trçnh trãn . ÅÍ âáy R1= R-a hoàûc R1=XA Bäø âãö:2 1. Moüi læåüc âäö quan hãû chè coï 2 thuäüc tênh âãöu åí daûng chuáøn BCNF 2. Nãúu læåüc âäö quan hãû R khäng åí daûng chuáøn BCNF thç coï thãø tçm ra âæåüc hai thuäüc tênh A vaì B sao cho (R-AB ) ® A âuïng trong R Chæïng minh. 1 Moüi læåüc âäö quan hãû chè coï 2 thuäüc tênh âãöu åí daûng chuáøn BCNF Xæí lyï thäng tin trong CSDL Trang 9 Nãúu R = AB thç táûp phuû thuäüc haìm trãn R coï thãø laì F1= {A®B}, F2 = { B®A}, F3= { A®B, B®A}. Âäúi våïi F1 ta coï A®B, BÏA , A laì khoïa msuy ra R åí daûng BCNF Âäúi våïi F2 ta coï B®A, AÏB, B laì khoïa suy ra R åí daûng BCNF Âäúi våïi F3 ta coï hoàûc A hoàûc B laì khoïa suy ra R åí daûng chuáøn BCNF 2. Nãúu læåüc âäö quan hãû R khäng åí daûng chuáøn BCNF thç coï thãø tçm ra âæåüc hai thuäüc tênh A vaì B sao cho (R-AB ) ® A âuïng trong R Nãúu R khäng åí daûng chuáøn BCNF thç täön taûi mäüt phuû thuäüc haìm X®A, AÏX vaì X khäng phaíi laì khoïa (X khäng suy ra R), thç trong R phaíi täön taûi êt nháút mäüt thuäüc tênh B khäng thuäüc XA( nãúu khäng thç XA=R vaì X®R). Nhæ váûy (R-AB)®A lad âuïng trong R (Vç X Í R_AB do AÏX vaì BÏX) Thuáût toaïn taïch khäng máút thäng tin thaình caïc læåüc âäö åí daûng BCNF Âáöu vaìo: Læåüc âäö quan hãû R Táûp phuû thuäüc haìm F trãn R Âáöu ra: Pheïp taïch P = { R1, R2,...,Rn } cuía R khäng máút thäng tin Coï nghéa laì Mp(r)= r våïi moüi r thoía maîn F Phæång phaïp: Chæång trçnh chênh: Z:=R { Bàõt âáöu pheïp taïch gaïn Z= R} Repeat Taïch {Thuí tuûc taïch} Z thaình Z-A vaì XA åí âáy Xa åí daûng chuáøn BCNF vaì X®A Âæa XA vaìo pheïp taïch Z:=Z-A Until Z khäng thãø taïch âæåüc båíi bäü âãö âaî nãu Âæa Z vaìo pheïp taïch Thuí tuûc Taïch If Z khäng chæïa A,B sao cho AÎ(Z-AB)+ then Return Else Begin Láúy càûp A,B thoía maîn AÎ(Z-AB)+ Y:=Z-B While Y coìn chæïa A,b sao cho AÎ(Z-AB)+ do Y:= Y-B Z:=Y Return Vê duû: Xeï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={ C®T, RH®C, HT®R, CS®G, HS®R } trong âoï caïc phuû thuäüc haìm âæåüc giaíi thêch nhæ sau: C®T: mäùi män hoüc chè coï mäüt giaïo viãn RH®C: Taûi mäüt phoìng hoüc ,åí mäüt giåì nháút âënh thç chè hoüc mäüt män hoüc HT®R: Mäùi giaïo viãn , taûi mäüt giåì nháút âënh chè åí mäüt phoìng nháút âënh CS®G: Mäùi sinh viãn hoüc män ngoaûi ngæî naìo âoï chè åí mäüt trçnh âäü nháút âënh HS®R: Mäùi sinh viãn taûi mäüt giåì hoüc taûi mäüt phoìng nháút âënh Yãu cáöu: Duìng thuáût toaïn âaî trçnh baìy , taïch læåüc âäö quan hãû U trãn thaình caïc læåüc âäö quan hãû åí daûng BCNF vaì pheïp taïch khäng máút thäng tin. Ta coï U= CTHRSG Xeït càûp C,T Ta coï (HRSG)+ = U= CTHRSG chæïa C vaì T Âàût A=C,B=T Y=CHRSG { Loaûi B ra khoíi læåüc âäö quan hãû } Xeït càûp C,H , ta coï (RSG)+ khäng chæïa C vaì H Xeït càûp C,R ta coï (HSG)+ chæïa R Âàût A= R, B=C Âàût Y= HRSG { loaûi B ra khoíi Y } Xeït càûp R,G ta coï (HS)+ chæïa R Âàût A=R, B=G Y= HRS { loaûi B ra khoíi Y } Tiãúp tuûc ta tháúy khäng coï càûp naìo bë loaûi khoíi Y nãn Y= HRS åí daûng chuáøn BCNF 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ï C®T, âæ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 CS®G Î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 }