Các mô hình dữ liệu cho các hệ cơ sở dữ liệu

Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 1 CHÆÅNG 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ CÅ SÅÍ DÆÎ LIÃÛU 2.1 MÄ HÇNH DÆÎ LIÃÛU Âënh nghéa: Mä hçnh dæî liãûu laì mäüt hãû hçnh thæïc toaïn hoüc gäöm hai pháön: 1. Mäüt hãû thäúng kyï hiãûu âãø mä taí dæî liãûu . 2. Táûp håüp caïc pheïp toaïn thao taïc trãn dæî liãûu âo.ï Trong chæång naìy ta seî tçm hiãøu caïc mä hçnh âæåüc sæí duûng räüng raîi hiãûn nay laì Mä hçnh THÆÛC THÃØ - QUAN HÃÛ ,mä hçnh QUAN HÃ, mä hçnh MAÛNG vaì mä hçnh PHÁN CÁÚP 2.2 MÄ HÇNH THÆÛC THÃØ -QUAN HÃÛ Muûc âêch cuía mä hçnh thæûc thãø -quan hãû (Entity - relationship model) laì cho pheïp mä taí læåüc âäö khaïi niãûm cuía thãú giåïi thæûc(xê nghiãûp, cå quan...) maì khäng cáön chuï yï âãún tênh hiãûu quaí hoàûc thiãút kãú Cå Såí Dæî Liãûu váût lyï. Âáy laì mä hçnh trung gian âãø chuyãøn âäøi qua caïc mä hçnh dæî liãûu khaïc nhæ mä hçnh quan hãû , mä hçnh maûng, mä hçnh phán cáúp... Sau âáy laì caïc khaïi niãûm sæí duûng trong mä hçnh naìy: 2.2.1THÆÛC THÃØ Thuáût ngæî “thæûc thãø ”(entity)khäng âæåüc âënh nghéa mäüt caïch hçnh thæïc , cuîng giäúng nhæ caïc thuáût ngæî “Âiãøm” vaì “âæåìng” trong hçnh hoüc, Chuïng ta coï thãø hiãøu ràòng thæûc thãø laì mäüt sæû váût hay mäüt caïi gç âoï täön taûi vaì phán biãût âæåüc. Thê duû mäùi con ngæåìi laì mäüt thæûc thãø , mäùi chiãúc xe maïy cuîng laì mäüt thæûc thãø , chuïng ta cuîng coï thãø noïi mäùi con kiãún laì mäüt thæûc thãø nãúu chuïng ta coï caïch phán biãût âæåüc con naìy våïi con khaïc( chàón haûn ta âaïnh mäüt säú cæûc nhoí trãn mäùi con kiãún). Khaïi niãûm vãö “tênh phán biãût âæåüc” âäöng nháút våïi khaïi niãûm “ nháûn daûng âäúi tæåüng” , vç lyï do naìy maì mä hçnh thæûc thãø -quan hãû thæåìng âæåüc xem nhæ laì mäüt mä hçnh hæåïng âäúi tæåüng. 2.2.2TÁÛP THÆÛC THÃØ Mäüt nhoïm bao gäöm caïc thæûc thãø “tæång tæû” taûo ra mäüt táûp thæûc thãø (entity set) vê duû 1. Táút caí moüi ngæåìi laì mäüt táûp thæûc thãø 2. Táút caí caïc Giaïo viãn thuäüc ÂHKT&QTKD laì mäüt táûp thæûc thãø 3. táút caí caïc sinh viãn khoa TC_THÄÚNG KÃ cuîng laì mäüt táûp thæûc thãø Âãø xaïc âënh táûp thæûc thãø cáön phaíi xaïc âënh mäüt táûp hæîu haûn caïc tênh cháút khaïc nhau cuía caïc thæûc thãø trong táûp thæûc thãø âoï. Mäüt trong nhæîng bæåïc then chäút trong viãûc læûa choün caïc mä hçnh Cå Såí Dæî Liãûu chæïa thäng tin phaín aïnh vãö mäüt hãû thäúng naìo âoï laì viãûc choün caïc táûp thæûc thãø trong hãû thäúng âoï. Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 2 2.2.3 THUÄÜC TÊNH vaì KHOÏA Mäüt táûp thæûc thãø coï mäüt táûp caïc tênh cháút âàûc træng goüi laì táûp thuäüc tênh(atribute), mäùi thæûc thãø âæåüc xaïc dënh båíi mäüt bäü dæî liãûu cuía caïc thuäüc tênh thãø hiãûn thäng tin vãö thuäüc tênh âoï. ÆÏng våïi mäùi thuäüc tênh coï mäüt táûp giaï trë maì thuäüc tênh âoï coï thãø nháûn goüi laì miãön(domain) giaï trë cuía thuäüc tênh âoï. Vê duû miãön giaï trë cuía thuäüc tênh Tuäøi laì (0,120), cuía thuäüc tênh Tãn laì caïc chuäøi kyï tæû coï âäü daìi täúi âa 30 kyï tæû , hay domain cuía thuäüc tênh Giåïi tênh laì { Nam, Næî},... Viãûc choün caïc thuäüc tênh laì bæåïc quan troüng trong thiãút kãú så âäö Cå Såí Dæî Liãûu. Mäüt thuäüc tênh hay 1 táûp täúi thiãøu caïc thuäüc tênh maì giaï trë cuía noï nháûn daûng 1 thæûc thãø mäüt caïch duy nháút trong táûp thæûc thãø goüi laì khoïa (key) cuía táûp thæûc thãø . vê duû 5 Xeït táûp thæûc thãø Sinh viãn cuía khoa TC_THÄÚNG KÃ våïi caïc thuäüc tênh Htãn, ngaìy sinh, Låïp, Âchè ta coï thãø choün Htãn laìm khoïa nãúu xaïc âënh âæåüc ràòng trong khoa khäng coï 2 ngæåìi naìo truìng hoü vaì tãn nhau, ngæåüc laûi ta coï thãø choü thãm caïc thuäüc tênh khaïc âãø phán biãût nhæ ngaìy sinh âãø laìm khaïo cho táûp thæûc thãø sinh viãn . 2.2.4.CAÏC MÄÚI QUAN HÃÛ Cho caïc táûp thæûc thãø E1, E2,..., Ek. Mäüt mäúi quan hãû R giæîa caïc táûp thæûc thãø laì mäüt danh saïch coï thæï tæû giæîa caïc táûp thæûc thãø âoï, Danh saïch caïc táûp thæûc thãø khäng nháút thiãút phaíi phán biãût. Coï nghéa laì mäüt táûp thæûc thãø coï thãø xuáút hiãûn nhiãöu hån mäüt láön trong Quan hãû. R= trong âoï Fi Î{ E1, E2,..., Ek}. Mäùi hiãûn haình cuía mäúi quan hãû R laì mäüt táûp caïc bäü <e1, e2,...,en> trong âoï ei ÎFi goüi laì n_bäü. Cho 2 táûp thæûc thãø E1 ,E2, R laì mäúi quan hãû giæîa E1 vaì E2 . ta coï caïc âënh nghéa sau: 1.Quan hãû ISA (is a) Nãúu mäùi thæûc thãø cuía E1 cuîng laì thæûc thãø cuía E2 thç quan hãû R goüi laì mäúi quan hãû ISA E1 ISA E2 âoüc laì E1laì “mäüt” E2. vê duû: E2 laì táûp thæûc thãø caïc sinh viãn khoa THÄÚNG KÃ-TIN HOÜC E1 laì táûp thæûc thãø caïc sinh viãn khoa THÄÚNG KÃ-TIN HOÜC coï hoüc bäøng nàm hoüc 98-99 khi âoï ta coï E1 ISA E2. Muûc âêch cuía mäúi quan hãû naìy laì caïc thæûc thãø cuía táûp thæûc thãø E1 thæìa hæåíng caïc thuäüc tênh cuía E2 ngoaìi ra E1 coìn coï nhæîng thuäüc tênh riãng cuía mçnh. Vê duû trong cäng ty coï táûp thæûc thãø NHÁN_VIÃN( MAÎNV, TÃNNV, TUÄØI, ÂËA_CHÈ,LÆÅNG). Nãúu cäng ty thaình láûp mäüt âäüi boïng chuyãön thç täút nháút nãn thiãút kãú mäüt táûp thæûc thãø PLAY(NÀM_ táûp thæûc thãø PLAY coï mäúi quan hãû ISA våïi táûp thæûc thãø NHÁN_VIÃN. Nhæ váûy mäùi thæûc Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 3 thãø trong THI_ÂÁÚU, CHIÃÖU_CAO) vaì táûp thæûc thãø PLAY cuîng coï táút caí caïc thuäüc tênh cuía táûp thæûc thãø NHÁN_VIÃN nhæng chè coï nhæîng thæûc thãø trong táûp thæûc thãø PLAY måïi coï caïc thuäüc tênh nhæ NÀM_THI_ÂÁÚU, CHIÃÖU_CAO. 2. Mäúi quan hãû mäüt_mäüt(one_one relationship) Nãúu mäùi thæûc thãø cuía E1 coï quan hãû våïi âuïng 1 thæûc thãø cuía E2 vaì ngæåüc laûi, thç mäúi quan hãû naìy goüi laì mäúi quan hãû mäüt_mäüt giæîa E1 vaì E2. Vê duû Mäúi quan hãû QUAÍN_LY Ï giæîa hai táûp thæûc thã LAÎNH_ÂAÛO vaì táûp thæûc thãø PHOÌNG_BAN laì mäúi quan hãû Mäüt_mäüt nãúu giaí thiãút ràòng mäüt laînh âaûo chè quaín lyï mäüt phoìng vaì mäüt phoìng chè coï mäüt ngæåìi quaín lyï. 3. Mäúi quan hãû nhiãöu_mäüt(many-one relationship) Nãúu mäùi thæûc thãø trong E1 coï quan hãû våïi nhiãöu nháút 1 thæûc thãø trong E2, vaì mäùi thæûc thãø trong E2 coï thãø khäng coï quan hãû våïi thæûc thãø naìo hoàûc coï quan hãû våïi 1 hoàûc nhiãöu thæûc thãø trong E1. Mäúi quan hãû naìy âæåüc goüi laì mäúi quan hãû nhiãöu_mäüt tæì E1 vaìo E2. Vê duû: mäúi quan hãû giæîa hai táûp thæûc thãø NHÁN_VIÃN vaì PHOÌNG_BAN laì mäúi quan hãû nhiãöu_mäüt tæì NHÁN_VIÃN vaìo PHONG_BAN, coï nghéa laì mäùi nhán viãn chè laìm viãûc trong mäüt phoìng vaì mäùi phoìng coï thãø coï nhiãöu nhán viãn laìm viãûc, cuîng coï træåìng håüp mäüt vaìi nhán viãn khäng thuäüc mäüt phoìng naìo caí nhæ giaïm âäúc. Khaïi niãûm mäúi quan hãû nhiãöu_mäüt âæåüc täøng quaït hoïa cho ba táûp thæûc thãø tråí lãn nhæ sau: Nãúu coï mäüt mäúi quan hãû R giæîa caïc táûp thæûc thãø E1,E2,...,Ek vaì våïi caïc thæûc thãø trong táút caí caïc táûp thæûc thãø træì Ei chè coï nhiãöu nháút mäüt thæûc thãø cuía Ei quan hãû våïi chuïng , thç ta goüi R laì mäúi quan hãû nhiãöu_mäüt tæì E1,...,Ei-1 ,...,Ek vaìo Ei. 4. mäúi quan hãû nhiãöu_nhiãöu( many_many relationship) Trong mäúi quan hãû naìy khäng coï mäüt haûn chãú trãn táûp caïc k_bäü cuía caïc thæûc thãø khi xuáút hiãûn trong caïc quan hãû . thê duû mäúi quan hãû CHA_MEÛ_CUÍA cuía táûp thæûc thãø NGÆÅÌI laì mäúi quan hãû nhiãöu nhiãöu, vç mäùi âæïa treí coï thãø tçm âæåüc cha meû cho chuïng vaì mäüt ngæåìi coï thãø coï säú læåüng con tuìy yï. vê duû: E1: táûp caïc sinh viãn cuía khoa TC_THÄÚNG KÃ E2 táûp håüp caïc män thãø thao R laì quan hãû thêch thãø thao laì mäúi quan hãû nhiãöu_nhiãöu Trong thæûc tãú caïc hãû quaín trë cå såí dæî liãûu khäng häù tråü mäúi quan hãû naìy, âãø biãøu diãùn mäúi quan hãû naìy trong thiãút kã thäng thæåìng ngæåìi ta taïch thaình caïc mäúi quan hãû nhiãöu _mäüt 2.2.5 Så âäö mäúi quan-hãû thæûc thãø Âãø mä taí thäng tin vãö caïc táûp thæûc thãø vaì caïc mäúi quan hãû giæîa chuïng ngæåìi ta sæí duûng så âäö goüi laì så âäö mäúi quan hãû thæûc thãø. Trong så âäö naìy: Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 4 1. Hçnh chæî nháût biãøu diãùn táûp thæûc thãø coï ghi tãn bãn trong 2. hçnh Oval biãøu diãùn thuäüc tênh, ghi tãn thuoüc tênh bãn trong 3. Hçnh thoi biãøu diãùn mäúi quan hãû giæîa caïc táûp thæûc thãø ghi tãn mäúi quan hãû bãn trong. 4. Nãúu R laì mäúi quan hãû mäüt_mäüt giæîa 2 táûp thæûc thãø E1 vaì E2 thç veî caïc caûnh âënh hæåïng tæì hçnh Oval nhaîn R âãún caïc hçnh chæî nháût nhaî E1 vaì E2. 5. Nãúu R laì mäúi quan hãû nhiãöu_mäüt tæì vaìo Ek thç veî caïc caûnh khäng âënh hæåïng tæì hçnh thoi nhaîn R âãún caïc HCN coï nhaîn E1,E2,..,Ek-1 vaì veî caûnh âënh hæåïng tæì hçnh thoi coï nhaîn R vaìo HCN nhaîn Ek. 6 Nãúu R laì mäúi quan hãû nhiãöu_nhiãöu giæîa E1 vaì E2 thç veî caïc caûnh khäng âënh hæåïng tæì hçnh thoi nhaîn R âãún hçnh chæî nháût nhaîn E1 vaì E2. Vê duû: så âäö sau trçnh baìy mäüt så âäö âån giaín, gäöm 3 táûp EMPS, DETPS vaì MANAGERS Hai táûp EMPS vaì DEPTS liãn kãút nhåì mäúi quan hãû WORK IN , âáy laì mäúi quan hãû nhiãöu_mäüt tæì EMPS vaìo DEPTS. Táûp thæûc thãø DEPTS vaì MANAGERS liãn kãút våïi nhau qua mäúi quan hãû MANAGES. Âáy laì mäúi quan hãû mäüt mäüt, Mäüt xuáút hiãûn cuía mäúi quan hãû naìy laì mäüt bäü(d,p) noïi ràòng vàn phoìng p âæåüc quaín lyï båíi nhán viãn d. Hoàûc så âäö quan hãû _thuûc thãø sau: Giæîa táûp thæûc thãø PERSONS vaì PERSONS våïi mäúi quan hãû PARENT_OF. Caûnh thæï nháút biãøu diãùn con coìn táûp thæï hai biãøu diãùn cha. Giaï trë hiãûn haình cuía mäúi quan hãû PARENT_OF laì táûp caïc càûp (p1,p2) noïi ràòng p2 laì cha cuía p1 Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 5 Vê duû: Sau dáy laì mäüt vê duû tæång âäúi âáöy âuí, så âäö mäúi quan hãû thæûc thãø sau âáy täø chæïc hãû thäúng thäng tin cáön thiãút âãø chè huy hoaût âäüng cuía siãu thë YVCB. Trong så âäö coï caïc táûp thæûc thãø vaì caïc mäúi quan hãû sau: 1.NHAN_VIEN: táûp thæûc thãø bao gäöm caïc nhán viãn laìm viãûc trong siãu thë , caïc thuäüc tênh : TENNV MANV LUONG 2. NGUOI_QL Ngæåìi quaín lyï goìm caïc træåíng phoìng trong siãu thë 3. GIAN_HANG: táûp thæûc thãø caïc gian haìng trong siãu thë goìm caïc thuäüc tênh TEN_GH MA_GH 4. MAT_HANG: táûp thæûc thãø caïc màût haìng baïn trong siãu thë, caïc thuäüc tênh TEN_MH MA_MH 5. NGUOI_CC: táûp thæûc thãø caïc ngæåìi cung cáúp caïc màût haìng cho siãu thë, caïc thuäüc tênh TEN_NCC DIA_CHI_NCC 6. DON_DATH: táûp thæûc thãø gäöm caïc âån dàût haìng cuía khaïch haìng, gäöm caïc thuäüc tênh SO_HOA_DON NGAY_DAT_HANG 7.KHACH_HANG: táûp thæûc thãø caïc khaïch haìng cuía siãu thi, gäöm caïc thuäüc tênh TEN_KH DIA_CHIKH TAI_K_KH Caïc mäúi quan hãû 8. LAM_VIEC: quan hãû laìm viãûc giæîa táûp thæûc thãø NHAN_VIEN vaì táûp thæûc thãø GIAN_HANG ta noïi: “nhán viãn x laìm viãûc åí gian haìng y” 9. QUAN_LY “: mäúi quan hãû quaín lyï giæîa táûp thæûc thãø GIAN_HANG vaì NGUOI_QL, ta noïi : “ gian haìng x âæåüc quaín lyï båíi ngæåìi quaín lyï y” 10. CHUA: quan hãû chæïa giæîa MAT_HANG våïi GIAN_HANG: ta noïi” màût haîng coï trong gian haìng y” 11. CUNG_CAP: quan hãû cung cáúp giæîa NGUOI_CC våïi MAT_HANG ta noïi” màût haìng x âæåüc cung cáúp båíi ngæåìi cung cáúp y”. 12. DAT_HANG: quan hãû âàût haìng giæîa KHACH_HANG våïi DON_DATH, ta noïi “ âån âàût haìng x âæåüc âàût båíi khaïch haìng y” 13. BAO_GOM: quan hãû bao gäöm giæuîa DON_DATH våïi MAT_HANG , ta noïi “ âån âàût haìng x âàût màût haìng y våïi säú læåüng z” Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 6 Så âäö mäúi quan hãû -thæûc thãø cuía YVCB nhæ sau (Hçnh veî) Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 7 Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 8 2.3 MÄ HÇNH DÆÎ LIÃÛU QUAN HÃÛ Nhæ âaî noïi, mä hçnh quan hãû-thæûc thãø khäng phaíi laì mä hçnh xæí lyï, noï mä hçnh hoïa thãú giåïi thæûc åí mæïc khaïi niãûm. Âãø læu træî thäng tin trãn maïy vaì duìng caïc hãû quaín trë Cå Såí Dæî Liãûu thao taïc trãn chuïng thç dæî liãûu phaíi âæåüc biãøu diãùn dæåïi daûng khaïc. Hiãûn nay mä hçnh dæî liãûu âæåüc sæí duûng räüng raîi nháút laì mä hçnh dæî liãûu quan hãû( Database Relationship Model) âæåüc E.F Code âãö xuáút nàm 1970 vaì ngaìy caìng coï nhiãöu hãû quían trë Cå Såí Dæî Liãûu cho mä hçnh naìy goüi laì caïc hãû quaín trë Cå Såí Dæî Liãûu quan hãû . Mä hçnh dæî liãûu quan hãû coï æu âiãøm laì tênh âäüc láûp dæî liãûu cao vaì mä hçnh âæåüc xáy dæûng dæûa trãn lyï thuyãút táûp håüp nãn dãù hiãøu vaì dãù biãøu diãùn bàòng toaïn hoüc. 2.3.1 Âënh nghéa quan hãû Quan hãû âæåüc âënh nghéa dæûa trãn lyï thuyãút táûp håüp vaì têch Âãö_caïc cuía caïc miãön. Miãön( Domain) laì táûp caïc giaï trë hæîu haûn hoàûc vä haûn. Vê duû: Táûp caïc säú nguyãn laì mäüt miãön, táûp caïc xáu kyï tæû coï âäü daìi 20 laì mäüt miãön, hoàûc táûp{0,1} laì mäüt miãön... Cho k miãön D1,D2,...,Dk. Khi âoï têch Âãö_caïc cuía k miãön D1,D2,...,Dk kyï hiãûu laì D1xD2x...xDk laì táûp caïc bäü coï daûng (v1,v2,...,vk) trong âoï vi thuäüc Di, mäùi bäü coï k thaình pháön goüi laì k_bäü(k_tupe) vê duû: Våïi k=2, D1={0,1},D2={a,b,c} Khi âoï D1xD2={(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)} tæì âoï quan hãû âæåüc âënh nghéa nhæ sau: Mäüt quan hãû (Relation)laì mäüt táûp håüp con báút kyì cuía têch Âãö_caïc cuía mäüt hoàûc nhiãöu miãön. Nhæ váûy mäüt quan hãû coï thãø laì vä haûn nhæng åí âáy luän giaí thiãút ràòng quan hãû laì hæîu haûn. vê duû Våïi D1 vaì D2 trong vê duû trãn thç táûp {(0,a),(0,c),(1,b)} laì mäüt quan hãû , mäüt táûp con cuía têch Âãö_caïc 2 miãön D1 vaì D2 Thaình pháön cuía quan hãû goüi laì bäü (tupe), quan hãû laì táûp con cuía têch Âãö_caïc k miãön goüi laì quan hãû k_ngäi(k_Arity). Mäùi bäü cuía quan hãû k_ngäi gäöm k thaình pháön goüi laì k_bäü coï daûng (v1,v2,...,vk) trong âoï vi thuäüc Di. Trong mä hçnh dæî liãûu quan hãû , mäùi quan hãû n_ngäi âæåüc biãøu diãùn båíi mäüt baíng n cäüt. Trong baíng mäùi cäüt tæång æïng våïi mäüt thaình pháön cuía quan hãû goüi laì thuäüc tênh vaì coï tãn laì tãn cuía thaình pháön tæång æïng trong quan hãû. Mäùi bäü trong quan hãû tæång æïng våïi 1 doìng cuía baíng. Tãn quan hãû cuìng våïi danh saïch caïc thuäüc tênh goüi laì læåüc âäö quan hãû (Relational Scheme). Nãúu quan hãû coï tãn laì REL vaì coï caïc thuäüc tênh laì A1,A2,...,Ak thç læåüc âäö quan hãû tæång æïng laì REL(A1,A2,...,Ak). Vê duû: Thäng tin vãö caïc thaình phäú âæåüc læu træî trong læåüc âäö quan hãû coï tãn laì CITY_INFO gäöm caïc thuäüc tênh nhæ TÃN_TP, SÄÚ_TRÆOÌNG_ÂH, SÄÚ_DÁN. Ta tháúy ràòng âáy laì læåüc âäö quan hãû 3_ngäi(Gäöm 3 thuäüc tênh )khi âoï læåüc âäö quan hãû tæång æïng Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 9 laì : CITY_INFO(TÃN_TP, SÄÚ_TRÆO ÌNG_ÂH, SÄÚ_DÁN) vaì (HUÃÚ, 6,2.000.000) laì mäüt bäü cuía læåüc âäö quan hãû . Vaì khi âoï TÃN_TP SÄÚ_TRÆOÌNG_ÂH SÄÚ_DÁN HUÃÚ 6 2.000.000 HAÌ NÄÜI 12 5.000.000 ÂAÌ NÀÔNG 5 3.000.000 Laì mäüt quan hãû cuía læåüc âäö quan hãû CITY_INFO, laì táûp con cuía têch âãö caïc 3 miãön TÃN_TP, SÄÚ_TRÆOÌNG_ÂH, SÄÚ_DÁN. ÆÏng våïi mäùi læåüc âäö quan hãû coï nhiãöu quan hãû goüi laì caïc hiãûn haình(Current Instance) cuía læåüc âäö quan hãû âoï. 2.3.2 Biãøu diãùn så âäöì Quan Hãû - Thæûc Thãø trong mä hçnh Quan Hãû Táûp caïc læåüc âäö quan hãû duìng âãø biãøu diãùn thäng tin cuía mäüt hãû thäúng âæåüc goüi laì læåüc âäö Cå Såí Dæî Liãûu quan hãû . (Relational Database Scheme)vaì nhæîng giaï trë hiãûn haình cuía caïc quan hãû tæång æïng taûo ra Cå Såí Dæî Liãûu quan hãû. Giaí sæí caïc thäng tin cuía hãû thäúng âæåüc biãøu diãùn båíi 1 så âäö vãö mäúi quan hãû thæûc thãø thç ta coï thãø thiãút láûp læåüc âäö Cå Såí Dæî Liãûu quan hãû cho hãû thäúng tæì så âäö mäúi quan hãû thæûc thãø dæûa trãn caïc nguyãn tàõt sau: 1. Mäüt táûp thæûc thãø E trong så âäö quan hãû -thæûc thãø âæåüc biãøu diãùn båíi mäüt læåüc âäö quan hãû coï tãn laì E vaì coï caïc thuäüc tênh laì táûp táút caí caïc thuäüc tênh cuía táûp thæûc thãø E.Mäùi thæûc thãø trong táûp thæûc thãø tæång æïng våïi mäüt bäü trong læåüc âäö quan hãû tæång æïng. Nãúu E laì mäüt táûp thæûc thãø maì caïc thæûc thãø cuía noï âæåüc âënh nghéa thäng qua mäüt mäúi quan hãû våïi mäüt táûp thæûc thãø F khaïc thç læåüc âäö quan hãû tæång æïng coï tãn laì E vaì coï thuäüc tênh laì caïc thuäüc tênh cuía F duìng laìm khoïa cho E 2.Mäüt mäúi quan hãû R giæîa caïc táûp thæûc thãø E1,E2,...,Ek âæåüc biãøu diãùn bàòng mäüt læåüc âäö quan hãû coï tãn laì R vaì coï caïc thuäüc tênh laì caïc thuäüc tênh khoïa cuía E1,E2,...,Ek. ÅÍ âáy coï thãø coï sæû âàût tãn laûi caïc thuäüc tênh nãúu coï hai hoàûc nhiãöu táûp thæûc thãø coï caïc thuäüc tênh truìng tãn âãø âaím baío ràòng giæîa caïc táûp thæûc thãø khäng coï caïc thuäüc tênh truìng tãn. Mäùi bäü t trong quan hãû naìy tæång æïng våïi mäüt danh saïch caïc thæûc thãø (e1,e2,...,ek) trong âoï ei thuäücEi. Âãø minh hoüa, thê duû sau âáy seî chuyãøn så âäö thæûc quan hãû -thæûc thãø cuía siãu thë YVCB sang læåüc âäö Cå Såí Dæî Liãûu quan hãû: Læåüc âäö cho caïc táûp thæûc thãø 1. EMPS(ENAME, SALARY) Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 10 2. MANAGERS(ENAME) 3. DEPTS(DNAME, DEPT#) 4. SUPPLIERS(SNAME, SADDR) 5. ITEMS(INAME, ITEM#) 6. ORDERS(O#, DATE) 7. CUSTUMERS(CNAME, CADDR, BALANCE) Læåüc âäö cho caïc mäúi quan hãû 8. WORK_IN(ENAME, DNAME) 9. MANAGES(ENAME, DNAME) 10. CARRIES(INAME, DNAME) 11. SUPPLIES(SNAME, INAME, PRICE) 12. INCLUDES(O#, INAME, QUANLITY) 13. PLACED_BY(O#, CNAME) 2.3.3 Khoïa cuía quan hãû (Keys of relation) Cuîng giäúng nhæ caïc táûp thæûc thãø , quan hãû cuîng coï khoïa âãø phán biãût caïc bäü trong quan hãû . Táûp con S caïc thuäüc tênh cuía quan hãû R goüi laì khoïa cuía R nãúu thoía maîn hai têch cháút sau: 1. Khäng coï hiãûn haình naìo cuía R coï hai bäü truìng nhau trãn táút caí caïc thuäüc tênh cuía S nhæng khäng phaíi laì mäüt bäü. 2. Khäng coï táûp con tháût sæû naìo cuía S coï têch cháút (1). Coï nghéa laì nãúu S laì khoïa cuía quan hãû R thç trong thiãút kãú Cå Såí Dæî Liãûu åí mæïc váût lyï khäng cho pheïp læu træî hai bäü maì caïc giaï trë cuía chuïng giäúng nhau trãn S. Vê duû: Trong læåüc âäö quan hãû SUPPLIES(SNAME, INAME,PRICE) coï khoïa gäöm hai thuäüc tênh SNAME vaì INAME. Nãúu trong mäüt hiãûn haình naìo âoï cuía læåüc âäö quan hãû SUPPLIES täön taûi hai bäü (s,i,p1) vaì (s,i,p2) coï nghéa laì ngæåìi cung cáúp s cung cáúp màût haìng i våïi hai giaï laì p1 vaì p2 nhæ váûy dæî liãûu bë läùi trong træåìng håüp naìy vç khäng thoía maîn tênh cháút khoïa. Mäüt âiãöu quan troüng cáön phaíi nhåï laì tênh cháút khoïa chè phuû thuäüc vaìo læåüc âäö maì khäng phuû thuäüc vaìo mäüt hiãûn haình naìo cuía læåüc âäö âoï. Vãö nguyãn tàõt âãø phán biãût caïc bäü trong quan hãû thç mäùi quan hãû phaíi coï êt nháút mäüt khoïa, nhæ váûy mäüt læåüc âäö coï thãú coï nhiãöu khoïa. Nãúu læåüc âäö quan hãû coï nhiãöu khoïa thç ta choün mäüt khoïa laìm khoïa chênh(Primary) vaì caïc khoïa coìn laûi âæåüc goüi laì khoïa æïng cæí(indicate). Nguyãn tàõt thaình láûp khoïa 1. Nãúu læåüc âäö quan hãû âæåüc thaình láûp tæì mäüt táûp thæûc thãø thç khoïa cuía táûp thæûc thãø âoï âæåüc láúy laìm khoïa cho læåüc âäö quan hãû. Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 11 2. Nãúu læåüc âäö quan hãû âæåüc thaình láûp tæì mäúi quan hãû nhiãöu_nhiãöu giæîa caïc táûp thæûc thãø E1 vaì E2 thç táûp táút caí caïc thuäüc tênh khoïa cuía E1 vaì E2 âæåüc duìng laìm khoïa cho læåüc âäö quan hãû . 3. Nãúu læåüc âäö quan hãû âæåüc thaình láûp tæì mäúi quan hãû mäüt_mäüt giæîa caïc táûp thæûc thãø E1 vaì E2 thç táûp táút caí caïc thuäüc tênh khoïa cuía E1 hoàûc khoïa E2 coï thãø láúy laìm khoïa cho læåüc âäö quan hãû . 4. Nãúu læåüc âäö quan hãû âæåüc thaình láûp tæì mäúi quan hãû nhiãöu_mäüt tæì E1,E2,...,Ek-1 vaìo Ek thç táûp táút caí thuäüc tênh khoïa cuía E1,E2,...,Ek-1 âæåüc duìng laìm khoïa cho læåüc âäö quan hãû . Báy giåì aïp duûng caïc nguyãn tàõt trãn âãø xaïc âënh khoïa cho 13 læåüc âäö quan hãû âæåüc thiãút láûp åí trãn. Khoïa chênh in âáûm, khoïa æïng cæí in nghiãn. 1. EMPS(ENAME, SALARY) 2. MANAGERS(ENAME) 3. DEPTS(DNAME, DEPT#) 4. SUPPLIERS(SNAME, SADDR) 5. ITEMS(INAME, ITEM#) 6. ORDERS(O#, DATE) 7. CUSTUMERS(CNAME, CADDR, BALANCE) Læåüc âäö cho caïc mäúi quan hãû 8. WORK_IN(ENAME, DNAME) 9. MANAGES(ENAME, DNAME) 10. CARRIES(INAME, DNAME) 11. SUPPLIES(SNAME, INAME, PRICE) 12. INCLUDES(O#, INAME, QUANLITY) 13. PLACED_BY(O#, CNAME) 2.3.3 Caïc pheïp toaïn trãn mä hçnh dæî liãûu quan hãû Coï hai loüai pheïp toaïn : 1. Âaûi säú quan hãû (relatinal algebra) 2. Pheïp tênh logic Trong pháön naìy chuïng ta chè tçm hiãøu caïc pheïp toaïn âaûi säú quan hãû Pheïp toaïn âaûi säú quan hãû coï caïc toaïn haûng laì caïc hàòng quan hãû , biãún quan hãû Coï 5 pheïp toaïn cå baín laì pheïp håüp(Union), Træì(difference), Têch Descarstes, Pheïp chiãúu(Projection), Pheïp choün(Selection) vaì mäüt säú pheïp toaïn måí räüng tæì 5 pheïp toaïn cå baín trãn. Sau âáy chuïng ta tçm hiãøu cuû thãø tæìng pheïp toaïn. Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 12 Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 13 Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 14 Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 15 Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 16 Mäüt säú vê duû æïng duûng caïc pheïp toaïn Âaûi säú quan hãû Giaí sæí trong caïc læåüc âäö quan hãû trong mä hçnh CSDL quan hãû YVCB, gheïp mäüt säú quan hãû thêch håüp âãø âæåüc âãø âæåüc caïc læåüc âäö quan hãû sau: NHAN_VIEN(TENNV,LUONG) GIAMH(SOGH, TENGH,NGUOIQL) MATH(MAMH, TENMH, TENGH) DONDH(SOHD, NGAYHD, TENKH) KHACHH(TENKH, DCHI,TAIK) CUNGCAP(TENCC,TENH,GIA) CHITIET(SOHD,TENH,SOLUONG) Chuïng ta coï thãø sæí duûng caïc pheïp toaïn âaûi säú quan hãû âãø traí låìi caïc cáu hoíi sau: 1.tçm ngæåìi cung cáúp cung cáúp saïch cå såí dæî liãûu (CSDL) PTENCC(sTENH=’saïch CSDL’ (CUNGCAP)) 2.Tçm xem nhaì cung cáúp A, cung cáúp nhæîng màût haìng naìo giaï tháúp hån 1000 PTENH(sTENCC=’A’ AND GIA <1000 (CUNGCAP)) 3. Xaïc âënh xem khaïch haìng naìo coï âàût mua quáng JEAN PTENKH(sTENH=’ JEAN’ (DONDH ¥ CHITIET)) Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 17 2.4 Mä hçnh dæî liãûu maûng Mä hçnh dæî liãûu maûng ( network model) laì mä hçnh quan hãû thæcû thãø. Trong âoï chè coï caïc mäúi quan hãû hai ngäi nhiãöu_mäüt. Trong mä hçnh dæî liãûu maûng ngæåìi ta thæåìng duìng caïc âäúi tæåüng sau: - Kiãøu baíng ghi thay cho táûp thæûc thãø - Format baín ghi thay cho táûp caïc thuäüc tênh - Mäùi baín ghi thay cho mäüt bäü giaï trë caíu caïc thuäüc tênh Nãúu so saïnh våïi mä hçnh quan hãû ta tháúy tæång æïng nhæ sau Mä liãûu maûng Mä hçnh quan hãû Kiãøu baíng ghi Tãn quan hãû Format baín ghi Læåüc âäö quan hãû Baín ghi Bäü cuía quan hãû 2.4.1 Caïc mäúi näúi ( Link) : Âãø biãøu diãùn caïc mäúi quan hãû hai ngäi nhiãöu _ mäüt giæîa hai âäúi tæåüng ngæåìi ta sæí duûng caïc mäúi näúi(link). Hay noïi caïch khaïc, thay cho 1 quan hãû hai ngäi R nhiãöu _1 tæì kiãøu baín ghi T1 âãún T2, ngæåìi ta veî mäüt caûnh âënh hæåïng coï nhaîn R tæì T1 âãún T2 trong md quan hãû thæûc thãø Trong mä hçnh maûng ngæåìi ta biãøu diãùn nhæ sau: 2.4.2Chuyãøn âäøi Så âäö quan hãû _thæûc thãø thaình Mä hçnh maûng Âãø xáy dæûng mä hçnh maûng tæì mä hçnh quan hãû _thæûc thãø ta aïp duûng caïc quy æåïc sau: 1. Mäùi táûp thæûc thãø âæåüc thay bàòng mäüt kiãøu baín ghi 2. Caïc thuäüc tênh cuía táûp thæûc thãø tråí thaình Format baín ghi 3. Caïc mäúi quan hãû nhiãöu_mäüt R âæåüc biãøu diãùn bàòng caïc link nhaîn R 4. Âäúi våïi caïc quan hãû nhiãöu ngäi giæîa E1,E2,..., En ngæåìi ta thãm kiãøu baín ghi ligic T våïi Format cuía noï khäng quan troüng, âäöng thåìi veî caïc caïc cung âënh hæåïng tæì T âãún E1, E2, ..., En T1 T2 T1 T2 R Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 18 Chuyãøn sang mä hçnh maûng Trong træåìng håüp R laì mäúi quan hãû nhiãöu _mäüt tæì E1,E2,..., En-1 vaìo En thç sæí duûng En thay cho T Chuyãøn thaình E1 E2 E3 E4 T E1 E3 E2 E4 E1 E2 E3 E4 Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 19 Vê duû chuïng ta aïp duûng nhæîng quy tàõt trãn âãø chuyãøn så âäö quan hãû thæûc thãø cuía siãu thë YVCB thaình mä haình maûng nhæ sau. LV QL Chæïa N-CC Chuï yï Format baín ghi T âæåüc âæa vaìo coï thãø räùng, tuy nhiãn ngæåìi ta thæåìng âæa vaìo caïc træåìng trong format âãø chæïa caïc thäng tin cáön thiãút. Vê duû: Cho hai táûp thæûc thãø sinh viãn bao gäöm caïc sinh viãn cuía khoa thäúng kã tin hoc våïi caïc thuäüc tênh Tãn, tuäøi, âëa chè. Vaì táûp thæûc thãø ngoaûi ngæî bao gäöm caïc låïp hoüc ngoaûi ngæî ban âãm do trung tám ngoaûi ngæî täø chæïc coï caïc thuäüc tênh låïp, sè säú, thåìi gian Giæîa haii thæûc thãø SINH VIEN vaì NGOAINGU coï mäúi quan hãû âàng kyï hoüc chè ra sinh viãn naìo âàng kyï hoüc låïp ngoaûi ngæî naìo, âáy laì mäúi quan hãû nhiãöu_nhiãöu Mä hçnh maûng nhæ sau: T E1 E3 E2 E4 NHAN_VIEN GIANH MATH NGUOI_CC NMG DONDH N-CC MDS B-D B-M KHACH_H DATH Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 20 Theo nguyãn tàõt thç format cuía T coï thãø räùng, nhæng åí âáy âãø mä ta âáöy âuí thäng tin thç ta coï thãø thãm vaìo caïc træåìng, ta thãm vaìo 2 træåìng nhæ sau: Træåìng SOTIET cho biãút säú tiãút trong tuáön hoüc Træåìng MUCDO cho biãút trçnh âäü cuía hoüc viãn (A,B,C..) Vaì cáúu truïc váût lyï cuía mä hçnh maûng nhæ sau: T 2.5 Mä hçnh phán cáúp Mä hçnh phán cáúp laì mä hçnh maûng coï cáúu truïc âàûc biãût nhæ laì mäüt ræìng (táûp håüp caïc cáy). Trong mäùi cáy, mäüt link chè theo hæåïng tæì nuït con âãún caïc nuït bäú meû, trong mä hçnh phán cáúp chuïng ta cuîng sæí duûng caïc âäúi tæåüng nhæ trong mä hçnh maûng( kiãøu baín ghi, format baín ghi, baín ghi). Chuïng ta coï thãø thiãút kãú mä hçnh phán cáúp tæì mä hçnh maûng bàòng caïch taïch dáön caïc cáy bàõt âáöu tæì nuït coï link âi âãún nhiãöu nháút maì khäng coï link âi ra laìm gäú c cuía cáy, gàõn caïc nuït coï link âi âãún nuït væìa choün laìm gäúc cho cáy con cuía noï. Vaì tiãúp tuûc gaïn caïc con chaïu cuía noï cho âãún khi khäng gaïn âæåüc næîa . Tiãúp theo choün cac nuït coìn laûi chæa âæåüc gaïn khäng coï link âi ra tæì noï laìm nuït gäúc cuía cáy måïi . Quaï trçnh tiãúp tuûc cho âãún khi khäng coìn nuït naìo cuía maûng chæa âæåüc gaïn vaìo mäüt cáy naìo âoï. Vê duû: Chuyãøn âäøi sang mä hçnh phán cáúp tæì mä hçnh maûng trong vê duû trong mä hçnh maûng vãö siãu thë YVCB SINHVIEN T NGOAINGU ANH PHAP NGA 2 A 4 C 3 B 1 A Hæng Lan Nguyãût Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 21 Chæång 3 LYÏ THUYÃÚT THIÃÚT KÃÚ CÅ SÅÍ DÆÎ LIÃÛU GIANH NHANVIEN NGUOIQL MATH DMS NMG NGUOICC NMG KHACHH DONDH MDS Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 22 Âàût váún âãö Cho læåüc âäö quan hãû R(A1,A2,...,An), æïng våïi mäüt táûp thæûc thãø hoàûc mäüt mäúi quan hãû trong så âäö mäúi quan hãû thæûc thãø . Mäùi hiãûn haình cuía R chæïa caïc dæî liãûu phaín aïnh thäng tin vãö mäüt âäúi tæåüng hoàûc mäúi quan hãû giæîa caïc âäúi tæåüng trong thãú giåïi thæûc. Tuy nhiãn, khäng phaíi táûp caïc bäü tuìy yï caïc giaï trë cuía thuäüc tênh âãöu laì hiãûn haình cuía 1 læåüc âäö quan hãû naìo âoï. Vê duû: xeït læåüc âäö quan hãû SINH_VIÃN(TÃN,TUÄØI) thç quan hãû sau TÃN TUÄØI Nguyãùn vàn A 21 Tráön thë B 100 Lã vàn C 24 âáy khäng phaíi laì mäüt hiãûn haình cuía quan hãû SINH_VIÃN, vç ràòng khäng coï sinh viãn naìo coï tuäøi 100. Hoàûc læåüc âäö quan hãû NGÆÅÌICC(TÃNCC,TÃNMH,GIAÏ), xeït quan hãû sau TÃNCC TÃNMH GIAÏ Nguyãùn vàn A Caì chua 2000â Tráön thë B Caíi 1500â Nguyãùn vàn A Caì chua 2500â Âáy cuîng khäng phaíi laì mäüt hiãûn haình cuía âäö quan hãû NGÆÅÌICC vç ràòng khäng thãø coï mäüt ngæåìi cung cáúp cuìng mäüt màût haìng våïi 2 giaï khaïc nhau. Nhæ váûytrong caïc hiãûn haình cuía caïc læåüc âäö quan hãû coï mäüt säú raìng buäüc vãö dæî liãûu 1. Raìng buäüc vãö ngæî nghéa miãön Raìng buäüc naìy phuû thuäüc vaìo khaí nàng hiãøu biãút vãö giaï trë cuía caïc thuäüc tênh (caïc thaình pháön cuía quan hãû ). Chàón haûn nãúu thuäüc tênh Ai laì tuäøi thç ta coï thãø haûn chãú miãön giaï trë Di cuía noï trong khoaín [0,200] 2. Raìng buäüc liãn quan âãún giaï trë cuía mäüt vaìi thuäüc tênh trong læåüc âäö quan hãû Chàón haûn sæû bàòng nhau giaï trë cuía caïc thuäüc tênh naìy dáùn âãún sæû bàòng nhau vãö giaï trë cuía caïc thuäüc tênh khaïc ta goüi laì phuû thuäüc haìm. 2.3.4.1 Âënh nghéa: Cho læåüc âäö quan hãû R(A1,A2,...,An), X,YÍ{ A1,A2,...,An}. Ta noïi ràòng X xaïc âënh Y hay Y phuû thuäüc haìm vaìo X nãúu trong moüi hiãûn haình r cuía R coï 2 bäü bàòng nhau trãn táûp thuäüc tênh X thç phaíi bàòng nhau trãn táûp thuäüc tênh Y. kyï hiãûu X®Y hay noïi caïch khaïc våïi 2 bäü h,jÎr; h(X)=j(X) Þ h(Y)=j(Y) vê duû trong læåüc âäö quan hãû NGÆÅÌICC(TÃNCC,TÃNMH,GIAÏ) ta coï phuû thuäüc haìm sau {TÃNCC,TÃNMH®GIAÏ} Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 23 Nhæ váûy moüi hiãûn haình cuía læåüc âäö quan hãû NGÆÅÌICC phaíi thoía maîn phuû thuäüc haìm {TÃNCC,TÃNMH®GIAÏ} Âãø thuáûn tiãûn cho viãûc mä taí mäüt säú váún âãö vãö phuû thuäüc haìm ta sæí duûng caïc kyï hiãûu sau: 1. caïc chæî caïi låïn âáöu daîy alpha kyï hiãûu caïc thuäüc tênh A,B,C,... 2. caïc chæî caïi låïn åí cuäúi daîy alpha kyï hiãûu caïc táûp thuäüc tênh V,Q,U,... 3. Mäüt táûp hæîu haûn caïc thuäüc tênh coï thãø thay cho læåüc âäö quan hãû . chàón haûn ta viãút (A1,A2,...,An) thay cho R(A1,A2,...,An) 4. Táûp caïc thuäüc tênh coï thãø thay bàòng daîy thuäüc tênh âoï vê duû ABCD thay cho {A,B,C,D} 5. pheïp gheïp 2 xáu kyï tæû thay cho pheïp håüp 2 táûp thuäüc tênh vê duû ABCÈDE=ABCDE 2.3.4.2 Cå såí lyï luáûn cuía phuû thuäüc haìm 1. Bao âoïng cuía táûp phuû thuäüc haìm Cho læåüc âäö quan hãû R, X,Y ÍR, r laì mäüt quan hãû cuía R . Ta noïi ràòng r thoía maîn phuû thuäüc haìm X®Y nãúu våïi 2 bäü báút kyì h,j,Îr sao cho h(X)=j(X) thç h(Y)=j(Y). -Nãúu X®Y laì mäüt phuû thuäüc haìm cuía R thç moüi hiãûn haình r cuía R phaíi thoía maîn phuû thuäüc haìm X®Y - Giaí sæí F laì mäüt táûp caïc phuû thuäüc haìm cuía R .Nãúu moüi quan hãû r cuía R laìm thoía maîn táút caí caïc phuû thuäüc haìm cuía F âãöu phaíi thoía maîn phuû thuäüc haìm X®Y ta noïi ràòng F keïo theo logic X®Y(hay F suy ra logic X®Y) Kyï hiãûu FÞX®Y Vê duû: Cho R=ABC F={A®B,B®C} roî raìng FÞA®C vç ràòng våïi 2 bäü báút kyì h,j ta coï A®B: h(A)=j(A)Þ h(B)=j(B) B®C: h(B)=j(B)Þh(C)=j(C) Suy ra h(A)=j(A)Þ h(C)=j(C) Tæïc A®C. Cho læåüc âäö quan hãû R vaì táûp phuû thuäüc haìm F. Bao âoïng cuía F laì mäüt táûp phuû thuäüc haìm gäöm caïc phuû thuäüc haìm âæåüc suy ra logic tæì F kyï hiãûu F+ âæåüc xaïc âënh nhæ sau: F+= {X®Y,X,YÍR|FÞX®Y} Vê duû cho R=ABC; F={A®B,B®C} F+= {A®A,A®B,A®C,...} Khi noïi vãö caïc læåüc âäö quan hãû chuïng ta âaî thæìa nháûn sæû täön taûimäüt táûp thuäüc tênh âàût biãût goüi laì khoïa cho læåüc âäö quan hãû. Táûp caïc giaï trë cuía caïc thuäüc tênh khoï a cuía læåüc âäö quan hãû xaïc âënh duy nháút mäüt bäü cuía quan hã. Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 24 Cho læåüc âäö quan hãû R vaì táûp phuû thuäüc haìm F , khoïa cuía læåüc âäö quan hãû R âæåüc xaïc âënh nhæ sau: 1. X âæåüc goüi laì khoïa cuía R ={A1,A2,...,An} nãúu X®A1A2...An âæåüc suy ra logic tæì F tæïc laì X®A1A2...AnÎ F+ 2. khäng coï mäüt táûp con thæûc sæû Y naìo cuía X maì Y®A1A2...AnÎ F+ Trong mäüt læåüc âäö quan hãû coï thãø coï nhiãöu khoïa, ngæåìi ta thæåìng choün mäüt khoïa laìm khoïa chênh (Primary key) caïc khoïa coìn laûi goüi laì khoïa phuû(cadidate key). Nãúu X laì khoïa , Y laì táûp chæïa X ( XÍY) thç Y dæåüc goüi laì siãu khoïa(Supper key). 2. Caïc tiãn âãö vãö phuû thuäüc haìm Âãø xaïc âënh khoïa cho quan hãû ngæåìi ta caìnn tçm F+ cuía táûp phuû thuäüc haìm F. Ta khäng thãø sæí duûng âënh nghéa vãö F+ âãø laìm âiãöu naìy (Vç quaï nhiãöu laìm khäng hiãûu quaí) Goüi U laì táûp táút caí caïc thuäüc tênh cuía læåüc âäö quan hãû , F laì táûp caïc phuû thuäüc haìm trãn U. Armstrong âaî âæa ra 3 quy tàõc suy dáùn goüi laì tiãn âãö Armstrong . T1.Tiãn âãö phaín xaû Nãúu YÍXÍU thç F suy dáùn ra X®Y. T2. Tiãn âãö Tàng træåíng Nãúu x®Y âæåüc suy ra tæì F vaì ZÍU thç XZ®YZ T3. Tiãn âãö bàõt cáöu Nãúu X®Y, Y®Z âæåüc suy ra tæì F thç X®Z cuîng âæåüc suy ra tæì F Vê duû: Cho læåüc âäö quan hãû U= ABCD vaì táûp phuû thuäüc haìm F={A®C,B®D} vaì giaí sæí tiãn âãö Armstrong âuïng våïi suy dáùn logic thç ta coï thãø xaïc âënh khoïa cuía læåüc âäö quan hãû U nhæ sau: 1. A®C Cho træåïc 2. AB®ABC:Luáût tàng træåíng håüp 2 vãú våïi AB 3. B®D : cho træåïc 4.ABC®ABCD: tàng træåíng, håüp 2 vãú våïi ABC 5. AB®ABCD: Bàõt cáöu AB laì khoïa vç A ®ABCD vaì B®ABCD. 3. Tênh âuïng cuía caïc tiãn âãö Armstrong Bäø âãö 1: caïc tiãn âãö Armstrong laì âuïng . Coï nghéa laì nãúu X®Y âæåüc suy ra tæì F bàòng caïc tiãn âãö Armstrong thç X®Y cuîng âæåüc suy ra tæì F bàòng logic Chæïng minh: Cho læåüc âäö quan hãû U vaì táûp phuû thuäüc haìm F trãn U ta cáön cm caïc tiãn âãö Armstrong laì âuïng. T1. YÍXÍU ta cáön cm X®Y âuïng (âæåüc suy ra tæì F) Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 25 Våïi moin quan hãû r thoía maîn F , láúy 2 bäü báút kyì h,jÎr nãúu h(X)=j(X)Ûh(A)=j(A) moüi aÎX Suy ra h(Y)=j(Y)(Vç YÍX) do âoï F Þ X®Y. T2. Moüi quan hãû r thoía maîn F , láúy 2 bäü h,jÎr.Vç X®Y âuïng nãn h(X)=j(X)Þh(Y)=j (Y) giaí thiãút h(XZ)=j(XZ) cáön cm h(YZ)=j(YZ) Ta coï h(XZ)=j(XZ) Þ h(X)=j(X)Þ h(Y)=j(Y)Þ h(YZ)=j(YZ) h(Z)=j(Z) h(Z)=j(Z) Váûy XZ®YZ âuïng T3. Moüi quan hãû r thoía maîn F , láúy 2 bäü h,jÎr. Vç X®Y Ûh(X)=j(X)Þh(Y)=j(Y) vaì Y®Z Û h(Y)=j(Y)Þh(Z)=j(Z) tæì âoï ta coï h(X)=j(X)Þh(Z)=j(Z) tæïc X®Z âuïng 4. Caïc quy tàõc dáùn suáút Tæì caïc tiãn âãö Armstrong ngæåìi ta âæa ra mäüt loaût caïc quy tàõt suy dáùn tiãûn låüi cho viãûc sæí duûng bàòng bäø âãö sau: Bäø âãö 2: 1. {X®Y,X®Z} thç X®Z (luáût håüp) 2. {X®Y,WY®Z} thç WX®Z( luáût tæûa bàõt cáöu) 3. Nãúu X®Y vaì ZÍY thç X®Z(luáût taïch) Chæïng minh 1. X®YÞX®XY(T2) X®ZÞXY®YZ(T2) X®YZ(T3) 2. X®YÞXW®YW(T2) YW®Z XW®Z 3. vç ZÍY nãn Y®Z(T1) X®Y(gt) nãn X®Z(T3) tæì caïc quy tàõt trãn suy ra hãû quaí quan troüng Hãû quaí: Nãúu Y=A1,A2,...,An thç X®Y ÛX®Ai("i =1,n) khi âoï X®Y=A1A2...AnÞX®Ai"i =1,n (Luáût taïch) X®Ai"i =1,n Þ X® A1A2...An (luáût håüp) 5. Bao âoïng cuía táûp thuäüc tênh Giaí sæí F laì táûp phuû thuäüc haìm trãn læåüc âäö quan hãû U, YÍU. Bao âoïng cuía táûp thuäüc tênh X kyï hiãûu laì X+ âæåüc xaïc âënh nhæ sau: X+= { AÎU: $X,YÍUAÍY, X®Y âæåüc suy ra tæì F bàòng Armstrong } Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 26 Bäø âãö 3 X®Y âæåüc suy ra tæì F bàòng Armstrong khi vaì chè khi YÍ X+ (âäúi våïi táûp phuû thuäüc haìm F) C/m giaí sæí Y=A1A2...An (AiÎU) Nãúu X®Y âæåüc suy ra tæì F bàòng Armstrong thç theo Armstrong X®Ai"i =1,n (luáût taïch) Þ Ai Î X+ "i =1,n ( âënh nghéa X+) Þ A1A2...AnÎ X+ hay YÎ X+ Ngæåüc laûi nãúu YÎ X+ Þ Ai Î X+ "i =1,nÞ X®Ai "i =1,n hay X®Y (luáût håüp) 6. tênh âuí cuía tiãn âãö Armstrong Ta seí C/m ràòng nãúu 1 phuû thuäüc haìm âæåüc suy dáùn logic tæì Armstrong tæì mäüt táûp phuû thuäüc haìm naìo âoï thç noï cuîng phaíi âæåüc suy dáùn bàòng caïc tiãn âãö Armstrong . Nãúu F(L)ÞX®Y thç F(A) ÞX®Y. Âënh lyï Hãû tiãn âãö Armstrong laì âuïng vaì âuí. C/m 1 tênh âuïng laì bäø âãö 1 âaî C/m 2/ Tênh âuí Giaí sæí F laì táûp phuû thuäüc haìm trãn U vaì X®Y khäng âæåüc suy ra tæì F bàòng Armstrong ta seî C/m X®Y cuîng khäng âæåüc suy ra tæì F bàòng logic. Âãø C/m X®Y khäng âæåüc suy ra logic tæì F ta tçm mäüt quan hãû r thoía maîn F maì khäng thoía maîn X®Y Láúy quan hãû r nhæ sau 1 1 . . .1 1 1 . . . 1 h 1 1 . . .1 0 0 . . . 0 j ta seî cm r thoía maîn F nhæng khäng thoía maîn X®Y a. r thoía maîn F Giaí sæí r khäng thoía maîn F thç täön taûi mäüt phuû thuäüc haìm W sao cho W®V ÎF sao cho r khäng thoía maîn W®V suy ra WÍ X+ vaì V Ë X+ Vç WÍ X+ nãn X®W âæåüc suy ra bàòng Armstrong theo luáût bàõt cáöu ta coï X®V âæåüc suy ra tæì F bàòng Armstrong . Âiãöu naìy máu thuáøn våïi V Ë X+. váûy r thoía maîn F b. r khäng thoía maîn X®Y Giaí thiãút r thoía maîn X®Y Vç XÍ X+ nãn YÍ X+ theo bäø âãö 3 X®Y âæåüc suy ra tæì Armstrong âiãöu naìy máu thuáøn våïi giaí thiãút X®Y khäng âæåüc suy ra tæì Armstrong do âoï r khäng thoía maîn X®Y. Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 27 Váûy : X®Y khäng âæåüc suy ra logic tæì F Kãút luáûn:Suy dáùn bàòng Armstrong vaì suy dáùn logic laì tæång âæång nhau. 7. Tênh bao âoïng cuía táûp phuû thuäüc haìm Cho táûp phuû thuäüc haìm F , Âãø tçm caïc phuû thuäüc haìm âæåüc suy ra tæì F ta phaíi tçm F+. Cäng viãûc naìy khaï phæïc taûp vaì máút nhiãöu thåìi gian. Chàón haûn Nãúu F={ A®B1,A® B2,...,A®Bn} Armstrong,Bi ÍU thç säú phuû thuäüc haìm daûng A®Y ,YÍB1B2,...Bn âaî laì 2n vç váûy viãûc tênh F+ laì khäng hiãûn thæûc vfa âäi khi khäng cáön thiãút . Baìi toaïn thææoìng âàût ra laì cho phuû thuäüc haìm X®Y xaïc âënh xem FÞX®Y hay khäng. Âãø laìm viãûc naìy ta chè cáön tênh X+ ( Âäúi våïi táûp phuû thuäüc haìm F) vaì xem YÍ X+ hay khäng: Nãúu YÍ X+ thç X®Y âæåüc suy ra tæì F Nãúu YÏ X+ thç X®Y khäng dæåüc suy ra tæì F Thuáût toïan Tênh X+ khaï âån giaín Thuáût toïan tênh bao âoïng cuat táûp phuû thuäüc haìm InPut: - Læåüc âäö quan hãû U - Táûp phuû thuäüc haìm F trãn U - XÍU Output: - X+ Bao âoïng cuía X âäúi våïi táûp phuû thuäüc haìm F Phæång Phaïp: Tênh daîy X(0),X(1),...,X(n) theo caïc bæåïc sau: 1. X(0)=X 2. X(i+1) = X(i) È{A: Y®ZÎF,AÍZ,YÍ X(i)} 3. Làûp laûi bæåïc 2 cho âãún khi X(i)= X(i+1) Roî raìng X(0)ÍX(1)Í...ÍX(n) Daîy X(i) (i=0,1,2,...) laì daîy âån âiãûu tàng vaì bë chàûn thç häüi tuû do âoï thuáût toaïn dæìng. Vê duû: Cho Læåüc âäö quan hãû U=ABCDGE F={AB®C,C®A, BC®D, D®EG,BE®C,CG®BD,CE®AC} X=BD Tçm X+ 1. X(0)=X=BD 2. X(1)= X(0) È{EG}=BDEG X(2) = BDEGÈ{C}=BCDEG X(3)= BDEGCÈ{A}=ABCDEG X(4)= X(3)=ABCDEG váûy X+= ABCDEG Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 28 Âiãöu naìy noïi lãn ràòng X laì khoïa cuía læåüc âäö quan hãû U ( Caìn C/m thãm ràòng B+ ¹ X+ vaì D+¹ X+). 8. Sæû tæång âæång giæîa caïc táûp phuû thuäüc haìm cho hai táûp phuû thuäüc haìm F vaì G trãn cuìng mäüt læåüc âäö quan hãû U. Ta noïi ràòngF tæång âæång våïi G nãúu vaì chè nãúu F+ = G+ Âãø xaïc âënh xem hai táûp phuû thuäüc haìm F vaì G coï tæång âæång våïi nhau hay khäng chuïng ta laìm nhæ sau: i. xaïc âënh xem mäùi phuû thuäüc haìm X ®Y Ï F coï thuäüc G+ hay khäng. Nãúu táút caí caïc phuû thuäüc haìm trong F âãöu Î G+ thç F+ Í G+ Ngæåüc laûi Y Í X+ thç X®Y Ï G+ Âãø xaïc âënh xem phuû thuäüc haìm X®Y coï thuäüc G+ hay khäng ta tênh X+ âäúi våïi G nãúu YÍX+ thç X®Y G+ ii. tæång tæû ta cáön xaïc âënh xem moüi phuû thuäüc haìm coï trong G coï thuäüc F+ hay khäng. Nãúu moüi phuû thuäüc haìm trong G âãöu Î F+ thç G+ Í F+ iii. Nãúu F+ Í G+ vaì G+ Í F+ thç F+ = G+ ta noïi hai táûp phuû thuäüc haìm F vaì G tæång âæång nhau. 9. Phuí cæûc tiãøu Âäúi våïi moüi táûp phuû thuäüc haìm âaî cho ta coï thãø tçm táûp phuû thuäüc haìm tæång âæång våïi noï coï caïc thuäüc tênh âàût biãth thuáûn tiãûn cho viãûc thiãút kãú CSDL . mäüt trong caïc tênh cháút âån giaín nhæng quan troüng âoï laì táûp phuû thuäüc haìm chè coï mäüt thuäüc tênh åí veï phaíi. Bäø âãö: Âäúi våïi moüi táûp phuû thuäüc haìm F âãöu täön taûi mäüt táûp phuû thuäüc haìm tæång âæång våïi noï trong âoï chè coï mäüt thuäüc tênh åí vãú phaíi Chæïng minh: Ta xáy dæûng táûp phuû thuäüc haìm G tæì F nhæ sau: G= {X®A |X®Y ÎF, AÎY} Ta seî cm F+ = G+ X®A ÎG suy ra täön taûi X®Y ÎFvaì AÎY Theo luáût taïch ta coï X®A Î F+ Ngæåüc laûi X ®Y ÎF âàût Y=A1A2...An Vç X®Y ÎF nãn theo luáût taïch X®Ai G moüi I=1,n Suy ra X®Y Î G+ (luáût håüp) Mäüt taûp phuû thuäüc haìm F dæåüc goüi laì phuí cæûc tiãøu nãúu noï thoía manc caïc âiãöu kiãûn sau: 1. caïc phuû thuäüc haìm trong F âãöu chè coï mäüt thuäüc tênh åí vãú phaíi 2. khäng täön taûi phuû thuäüc haìm X®A ÎF (AÎU) sao cho F+ = (F\X®A)+ 3. khäng täön taûi phuû thuäüc haìm X®A ÎF sao cho täön taûi B ÎX thoía F+ = ((F È {X’ ®A}\ {X®A})+ Trong âoï X’= X\ {B} Nãúu G laì phuû thuäüc haìm cæûc tiãøu tæång âæång våïi F thç G âæåüc goüi lag phuí cæûc tiãøu cuía F Âënh lyï: Chæång 2 CAÏC MÄ HÇNH DÆÎ LIÃÛU CHO CAÏC HÃÛ QUAÍN TRË CÅ SÅÍ DÆÎ LIÃÛU Baìi soaûn Cå såí dæî liãûu Trang 29 Moüi táûp phuû thuäüc haìm âãöu coï phuí cæûc tiãøu Chæïng minh: 1. Cho táûp phuû thuäüc haìm F, theo bäø âãö trãn ta coï thãø xáy dæûng F1 tæång dæång våïi F thoía maîn âiãöu kiãûn (1) cuía phuí cæûc tiãøu (bàòng luáût taïch). F1+ = F+ 2. láön læåüt láúy caïc phuû thuäüc haìm X®A ÎF1 vaì thæí F+ = (F1\X®A)+ hay khäng . nãúu bàòng thç loaûi X®A ra khoíi F1 Sau khi thæí táút caí caïc phuû thuäüc haìm trong F1 ta âæåüc táûp phuû thuäüc haìm F2 thoía maîn âiãöu kiãûn (1) vaì (2) cuía phuí cæûc tiãøu 3. láön læåüt láúy caïc phuû thuäüc haìm X®A Î F2, våïi mäùi X= B1B2...Bn láön læåüt thæí xem (F2\{ B1B2...Bn }) È ({ B1B2...Bi-1Bi+1...Bn ®A })+ = F2+ nãúu bàòng thç thay X®A båíi B1B2...Bi-1Bi+1...Bn ®A cho âãún khi khäng thãø thay âæåüc næîa ta âæåüc táûp phuû thuäüc haìm G tæång âæång våïi F2 thoía maîn táút caí caïc âiãöu kiãûn cuía phuí cæûc tiãøu. Vê duû Cho táûp phuû thuäüc haìm F= {AB®C, C®A, BC®D, ACD®B, D®GE, BE®C, CE®AG, CG®BD} Tçm phuí cæûc tiãøu tæång âæång våïi F Træåïc tiãn ta coï F1= {AB®C, C®A, BC®D, ACD®B, D®G, D®E,BE®C,CE®A,CE®G, CG®B,CG®D} Nãúu thæí våïi caïc phuû thuäüc haìm trong F1 ta coï CE ®A,CG®B laì thæìa ( Thæí CE®A tênh CE+ âäúi våïi F1 ta coï CE+ = ABCDEG ta coï A Î CE+ nãn CE®AÎ F1+ nãn roî raìng phuû thuäüc haìm CE®A thæìa trong F1 ta loaûi phuû thuäüc haìm CE®A ra khoíi F1 tæång tæû ta coï B Î CG+ nãn phuû thuäüc haìm CG®B thæìa, loaûi phuû thuäüc haìm CG®B ra khoíi F1 tiãúp tuûc thæí ta tháúy phuû thuäüc haìm ACD ®B cuîng thæìa trong F1