Giáo trình về Cơ sở dữ liệu - Chương 4

Tài liệu tham khảo giáo trình tổng quan về cơ sở dữ liệu
Nội dung trích xuất từ tài liệu:
Giáo trình về Cơ sở dữ liệu - Chương 4 Xæí lyï thäng tin trong CSDL Chæång4: TAÏCH KHÄNG MÁÚT THÄNG TINCho læåüc âäö quang hãû R=(A1,A2,...,An), taïch læåüc âäö quang hãû R laì thay noï båíi mäütbäü caïc læåüc âäö P=(R1,R2,...,Rk) sao cho R1∪R2∪...∪Rk =RVê 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 tinCho 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 Fthç Mp(r)= rBäø Âãö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)=ri3. Mp(r)=Mp(Mp(r))chæïng minh1. 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äüthaì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 RiVê duû AB C D 14 5 2t=3 2 7 6 33 7 4R1=BC khi âoï ΠR1(r) = BC 45 Trang 1 Xæí lyï thäng tin trong CSDL 2 7 3 7Khi âoï t(r1) = 2 7Ti = 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)=ritæì (1) ta coï r ⊆ Mp(r) ⇒ ΠRi(r)⊆ΠRi(Mp(r))⇒ ri⊆ΠRi(s)Chæïng minh ngæåüc laûi ΠRi(s) ⊆ riLáú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ängThuáût toaïn:Dæî liãûu vaìo:- Læåüc âäö quang hãû R- Táûp phuû thuäüc haìm FPheï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äüctê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ãûutæå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ãúucaí 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ïchlaì khäng máút thäng tin , ngæåüc laûi thç phpe taïch máút thäng tin.Vê duû1 Trang 2 Xæí lyï thäng tin trong CSDLCho læåüc âäö quang hãû R=ABCDETaïch R thaình caïc læåüc âäö sau:R1 = AD, R2=AB, R3= BE, R4= CDE, R5= AEtáû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ängláûp baíng: A B C D EAD a1 b12 b13 a4 b15 b23(b13) b24(a4)AB a1 a2 b25 b31(a1) b33(b13)(a3) b34(a4)BE a2 ...