Đề tài Mô hình cơ sở dữ liệu có tính thời gian

Phaàn Giôùi Thieäu Veà Ñeà Taøi: gaøy nay, trong nhieàu öùng duïng thöïc teá, beân caïnh nhöõng döõ lieäu tónh- döõ lieäu coù tính oån ñònh, coøn coù raát nhieàu loaïi döõ lieäu ñoäng- döõ lieäu ñöôïc truy xuaát thay ñoåi theo thôøi gian. Trong moät soá tröôøng hôïp, nhöõng döõ lieäu ñoäng naøy coù nhöõng quy luaät thay ñoåi naøo ñoù. Vì vaäy moâ hình CSDL coù tính thôøi gian(temporal database) ñöôïc ñeà xuaát ñeå nghieân cöùu vaán ñeà treân. N Nhieàu taùc giaû ñaõ nghieân cöùu veà: moâ hình döõ lieäu coù tính thôøi gian, vaø caùc daïng chuaån coù tính thôøi gian. Coù theå neâu moät soá nhöõng teân tuoåi nhö: D.Dey ñöa ra moät soá khaùi nieäm veà ñaïi soá quan heä cho moâ hình döõ lieäu thôøi gian; Z.M. Ozsoyoglu ñeà nghò moâ hình quan heä loàng nhau; J. Wijsen, J. Vandenbulcke vaø H. Olive ñeà nghò moät soá khaùi nieäm veà caùc phuï thuoäc haøm coù tính thôøi gian; vaø gaàn ñaây S. Y. Liao, H.Q. Wang, W.Y. Liu ñöa ra khaùi nieäm veà daïng chuaån 3 coù tính thôøi gian; E. Bertino, C. Bettini, E.Ferrari, P. Samarati ñöa ra khaùi nieäm veà ñieàu khieån truy xuaát trong moâ hình coù tính thôøi gian. Trong ñeà taøi naøy ñeà caäp ñeán caùc khaùi nieäm vaø moät soá keát quaû veà caùc vaán ñeà trong cô sôû döõ lieäu coù tính thôøi gian nhö sau: - Caùc khaùi nieäm veà cô sôû döõ lieäu coù tính thôøi gian: löôïc ñoà quan heä tính thôùi gian vaø quan heä tính thôøi gian. - Caùc pheùp toaùn veà ñaïi soá quan heä treân CSDL coù tính thôøi gian. - Caùc khaùi nieäm veà phuï thuoäc haøm vaø caùc daïng chuaån coù tính thôøi gian. - Caùc raøng buoäc oån ñònh coù tính thôøi gian. - Phaân raõ baûo toaøn thoâng tin coù tính thôøi gian. -----------------------------****---------------------------- Giôùi thieäu khaùi nieäm cô baûn trong lyù thuyeát CSDL PHAÀN I GIÔÙI THIEÄU KHAÙI NIEÄM CÔ BAÛN TRONG LYÙ THUYEÁT CSDL I.1 Khaùi nieäm veà CSDL: CSDL laø moät taäp hôïp coù caáu truùc cuûa döõ lieäu ñöôïc löu tröõ treân caùc thieát bò kyù tin nhaèm thoûa maõn ñoàng thôøi nhieàu ngöôøi söû duïng, moät caùch coù choïn loïc vaøo luùc caàn. I.2 Taäp caáu truùc thuoäc tính: Moät thuoäc tính: moâ taû moät ñaëc tính hoaëc ñaëc ñieåm naøo ñoù cuûa moät thöïc theå(söï vaät). R={A1, A2,…,An} goïi laø moät taäp caáu truùc thuoäc tính neáu nhö R goàm höõu haïn caùc kyù hieäu goïi laø caùc thuoäc tính. Moãi thuoäc tính Ai coù giaù trò theå hieän thuoäc taäp Di= Domain(Ai). I.3 Quan heä(bieåu dieãn quan heä baèng aùnh xaï): • Moät quan heä r(R) laø moät taäp höõu haïn caùc aùnh xaï töø R={A1, A2,…,An} vaøo hôïp mieàn giaù trò caùc thuoäc tính(kyù hieäu: D= Υ laø hôïp mieàn giaù trò caùc thuoäc tính). n i iD 1= • Moät quan heä r(R) vôùi m aùnh xaï cho nhö sau: r= {t1,t2,….,tm}, trong ñoù: ti laø aùnh xaï: R Æ D Aj Æ ti(Aj) ∈ Dj (i=1,..,m; j=1,…,n) Ta coù: ti(R)= {ti1,ti2,…tin} I.4 Raøng buoäc toaøn veïn: • Laø nhöõng raøng buoäc, ñieàu kieän baát bieán maø CSDL phaûi thoaû taïi moïi thôøi ñieåm. • Raøng buoäc toaøn veïn coù theå ñònh nghóa treân moät quan heä hay nhieàu quan heä khaùc nhau. • Raøng buoäc toaøn veïn treân moät quan heä:RBTV mieàn giaù trò, RBTV lieân boä, RBTV lieân thuoäc tính. NGUYEÃN THÒ LAN ANH Trang 1 Giôùi thieäu khaùi nieäm cô baûn trong lyù thuyeát CSDL • Raøng buoäc toaøn veïn treân nhieàu quan heä: RBTV tham chieáu, RBTV do thuoäc tính toång hôïp, RBTV lieân boä- lieân quan heä, RBTV lieân thuoäc tính lieân quan heä, RBTV chu trình. I.5 Phuï thuoäc haøm treân taäp(caáu truùc) thuoäc tính R: Moät phuï thuoäc haøm treân taäp R coù kyù hieäu: (X,Y), hoaëc XÆ Y Trong ñoù: X,Y ⊆ R. I.6 Ñònh nghóa löôïc ñoà quan heä: Moät löôïc ñoà quan heä kyù hieäu S laø moät boä S=. Trong ñoù, R laø taäp caáu truùc thuoäc tính naøo ñoù cho tröôùc vaø F laø taäp caùc phuï thuoäc haøm treân taäp R cho tröôùc. Sau naøy ta coøn goïi löôïc ñoà quan heä S laø löôïc ñoà quan heä R, vôùi R laø taäp caáu truùc thuoäc tính naøo ñoù cho tröôùc vaø F laø taäp caùc phuï thuoäc haøm treân taäp R cho tröôùc. I.7 Phuï thuoäc haøm: • Cho r(R) laø moät quan heä treân taäp thuoäc tính R. X,Y ⊆ R, ta noùi coù phuï thuoäc haøm: XÆY treân quan heä r. Kyù hieäu: (X,Y)r hay X Y ⎯→⎯r Neáu nhö: ∀ t,s ∈ r neáu t[X]= s[X] thì t[Y]= s[Y]. • Vôùi r(R) laø moät quan heä treân R seõ toàn taïi duy nhaát moät taäp phuï thuoäc haøm goàm taát caû caùc phuï thuoäc haøm cuûa quan heä r, kyù hieäu: Fr. I.8 Quan heä hôïp leä: • Cho taäp thuoäc tính R, X,Y ⊆ R. Ta noùi, phuï thuoäc haøm (X,Y) ñuùng treân r(quan heä r hôïp leä ñoái vôùi phuï thuoäc haøm (X,Y)) neáu nhö (X,Y) ∈ Fr. • Vôùi S= laø moät löôïc ñoà quan heä. Ta noùi quan heä r(R) laø hôïp leä ñoái vôùi S neáu nhö noù hôùp leä ñoái vôùi moïi phuï thuoäc haøm trong F. • Cho R={A1, A2,…,An} laø moät löôïc ñoà quan heä, X,Y ⊆ R, ta noùi coù phuï thuoäc haøm: XÆY cuûa löôïc ñoà quan heä R(hay X xaùc ñònh Y theo kieåu haøm; hay Y phuï thuoäc haøm NGUYEÃN THÒ LAN ANH Trang 2 Giôùi thieäu khaùi nieäm cô baûn trong lyù thuyeát CSDL vaøo X) neáu:∀ r(R) hôïp leä(quan heä r laø giaù trò hieän haønh cuûa R): XÆY laø phuï thuoäc haøm treân quan heä r. Töø ñoù ta coù khaùi nieäm quan heä hôïp leä nhö sau I.9 Phuï thuoäc haøm suy dieãn vaø bao ñoùng cuûa caùc taäp phuï thuoäc: Cho LÑQH S=, X,Y ⊆ R • (X,Y) laø phuï thuoäc haøm ñöôïc suy dieãn töø caùc phuï thuoäc haøm trong F(ñoái vôùi caùc quan heä hôïp leä) neáu nhö: Vôùi moïi quan heä r(R) hôïp leä ñoái vôùi F thì r(R) cuõng hôïp leä ñoái vôùi (X,Y). • F+ ñöôïc goïi laø bao ñoùng(closure) cuûa F neáu F+ goàm taát caû caùc phuï thuoäc haøm ñöôïc suy dieãn töø caùc phuï thuoäc haøm trong F, nghóa laø: F+ ={(X,Y): (X,Y) ñöôïc suy dieãn töø caùc phuï thuoäc haøm trong F. Nhaän xeùt: Chuùng ta khoâng xem xeùt moät quan heä r cuï theå cuûa löôïc ñoà R nhaèm suy ra caùc phuï thuoäc ñuùng trong R. Tuy nhieân, chuùng ta coù theå xem xeùt moät quan heä cuï theå cuûa R ñeå khaùm phaù ra moät soá phuï thuoäc khoâng ñuùng. I.10 Heä tieân ñeà Amstrong: Laø moät taäp nhöõng quy taéc suy dieãn ñaày ñuû, nhôø nhöõng quy taéc naøy ta coù theå suy dieãn taát caû caùc phuï thuoäc haøm trong taäp F+ töø taát caû caùc phuï thuoäc haøm trong taäp F(ñieàu naøy ñaõ ñöôïc chöùng minh): Vôùi X,Y,Z,T⊆R • Quy taéc phaûn xaï: Neáu Y⊆ X thì XÆY, quy taéc naøy ñöa ra nhöõng phuï haøm taàm thöôøng. • Quy taéc taêng tröôûng: Neáu XÆY, Z ⊆ R thì XZÆYZ. • Quy taéc baéc caàu: neáu XÆY, YÆZ thì XÆZ Caùc luaät suy dieãn boå sung: • Quy taéc hôïp: neáu XÆY vaø XÆZ thì XÆYZ. NGUYEÃN THÒ LAN ANH Trang 3 Giôùi thieäu khaùi nieäm cô baûn trong lyù thuyeát CSDL • Quy taéc taùch: neáu XÆYZ thì XÆY vaø XÆZ. • Quy taéc töïa baéc caàu: neáu XÆY vaø YZÆT thì XZÆT I.11 Bao ñoùng cuûa taäp thuoäc tính: Cho LÑQH S=, X⊆R Kyù hieäu: X+F laø bao ñoùng cuûa cuûa X treân F laø taäp taát caû caùc thuoäc tính A sao cho XÆA coù theå suy ra töø F baèng heä tieân ñeà Amstrong. X+F ={A: XÆA ∈F+} Nhaän xeùt: Muoán kieåm tra phuï thuoäc haøm XÆY coù thuoäc F+ hay khoâng, ta xeùt thaáy: Baøi toaùn tìm F+ töø F laø khoù thöïc hieän vôùi soá thuoäc tính trong R lôùn. Thay vì xaùc ñònh F+ ta tính X+F, neáu Y⊆ X+F thì XÆY thuoäc F+. I.12 Khoaù cuûa löôïc ñoà quan heä: Ñeå phaân bieät caùc thöïc theå trong moät taäp thöïc theå ta coù khaùi nieäm khoaù nhö sau: Cho LÑQH S=, K⊆ R • K goïi laø sieâu khoaù(super key) cuûa löôïc ñoà quan heä R neáu vaø chæ neáu: KÆR∈F+ Hay: K goïi laø sieâu khoaù cuûa löôïc ñoà quan heä R neáu vaø chæ neáu K+F=R. • K goïi laø khoaù ñeà nghò(candidate key) cuûa löôïc ñoà quan heä R neáu vaø chæ neáu: o K+F=R o Khoâng ∃K’⊂ K, K’+F=R (khoaù ñeà nghò cuõng laø khoaù toái tieåu) NGUYEÃN THÒ LAN ANH Trang 4 Caùc daïng chuaån trong CSDL PHAÀN II CAÙC DAÏNG CHUAÅN TRONG CSDL Vieäc chuaån hoaù caùc quan heä cuõng nhö caùc löôïc ñoà quan heä ñoùng vai troø cöïc kyø quan troïng trong vieäc thieát keá caùc heä quaûn trò cô sôû döõ lieäu. Nhôø coù söï chuaån hoaù caùc quan heä vaø caùc löôïc ñoà quan heä chuùng ta traùnh ñöôïc vieäc dö thöøa döõ lieäu vaø taêng toác ñoä cuûa caùc pheùp toaùn xöû lyù quan heä. Trong CSDL coù söï truøng laép thoâng tin. Daïng chuaån: laø caùc tieâu chuaån ñeå ñaùnh giaù ñoä truøng laép thoâng tin trong CSDL. Vì theá: - Phaûi quaûn lyù söï truøng laép thoâng tin( baûo ñaûm taát caû caùc thoâng tin truøng laép phaûi nhö nhau). - Khi caäp nhaät moät thoâng tin bò truøng laép thì phaûi caäp nhaät taát caû nhöng nôi maø thoâng tin ñoù xuaát hieän. Döïa vaøo phuï thuoäc haøm ta coù nhöõng daïng chuaån nhö sau: Cho LÑQH S=(coøn goïi laø LÑQH R) F: laø taäp caùc phuï thuoäc haøm. R: taäp caùc thuoäc tính. II.1 Ñònh nghóa Daïng chuaån 1NF: Löôïc ñoà quan heä R ñaït daïng chuaån 1NF neáu moïi thuoäc tính cuûa noù ñeàu laø thuoäc tính ñôn(nguyeân toá ). Thuoäc tính ñôn(nguyeân toá):mieàn giaù trò khoâng theå phaân chia ñöôïc nöõa. Thuoäc tính phöùc: mieàn giaù trò coù theå phaân chia ñöôïc. VD: - MSSV laø thuoäc tính ñôn NGUYEÃN THÒ LAN ANH Trang 5 Caùc daïng chuaån trong CSDL - NgaySinh laø thuoäc tính phöùc vì mieàn giaù trò coù theå phaân chia thaønh caùc giaù trò ñôn: Ngay, Thang, Nam. YÙ nghóa cuûa daïng chuaån 1NF: loaïi boû moïi nhoùm laëp. Moät thieát keá CSDL goïi laø ôû daïng chuaån 1NF neáu taát caû caùc LÑQH trong ñoù laø 1NF. LÑQH R muoán ñaït caùc chuaån 2NF, 3NF vaø BCNF thì tröôùc heát phaûi ñaït chuaån 1NF II.2 Ñònh nghóa Daïng chuaån 2NF: Phuï thuoäc haøm ñaày ñuû: Moät phuï thuoäc haøm AÆ B ñöôïc goïi laø ñaày ñuû neáu:Khoâng toàn taïi moät taäp hôïp A1⊂ A sao cho A1 Æ B. Trong tröôøng hôïp naøy ta noùi: B phuï thuoäc ñaày ñuû vaøo A. Ngöôïc laïi, ta noùi: B phuï thuoäc boä phaän vaøo A Nhö vaäy, neáu A laø moät thuoäc tính ñôn thì phuï thuoäc haøm AÆ B laø ñaày ñuû. Thuoäc tính thöù caáp: thuoäc tính a∈R goïi laø thöù caáp neáu vaø chæ neáu a ∉ ∪K(a coøn goïi laø thuoäc tính khoâng khoaùù). Ngöôïc laïi: neáu a ∈ ∪K ta goïi a laø thuoäc tính khoaù. Töø ñoù ta coù: Löôïc ñoà quan heä R ñaït 2NF khi vaø chæ khi: - Löôïc ñoà quan heä R ñaït 1NF - Moïi thuoäc tính thöù caáp ñeàu phuï thuoäc ñaày ñuû vaøo khoaù toái tieåu baát kyø. Coù theå thaáy baûn chaát daïng chuaån 2NF laø loaïi boû caùc phuï thuoäc boä phaän giöõa caùc thuoäc tính thöù caáp vaø caùc khoaù toái tieåu. Caùc daïng chuaån quan troïng nhaát laø daïng chuaån caáp 3 vaø daïng chuaån BCNF. Muïc ñích cuûa chuùng laø traùnh ñöôïc caùc dö thöøa vaø caùc baát thöôøng. II.3 Ñònh nghóa Daïng chuaån 3NF: Ñònh nghóa phuï thuoäc haøm tröïc tieáp vaø phuï thuoäc haøm baéc caàu: NGUYEÃN THÒ LAN ANH Trang 6 Caùc daïng chuaån trong CSDL Moät phuï thuoäc haøm AÆ C, ñöôïc goïi laø tröïc tieáp neáu khoâng coù B(B≠ A vaø B ≠C) thoaû: AÆB vaø BÆC Trong tröôøng hôïp neáu coù B nhö vaäy thì B ñöôïc goïi laø taäp thuoäc tính baéc caàu vaø AÆ C laø phuï thuoäc baéc caàu. Khi ñoù: R laø 3NF neáu vaø chæ neáu: - Löôïc ñoà quan heä R ñaït 1NF - Khoâng coù 1 thuoäc tính thöù caáp naøo cuûa R phuï thuoäc baéc caàu vaøo 1 khoaù toái tieåu. Löu yù: ∀ XÆY∈F, F goïi laø chính quy neáu vaø chæ neáu: ⎭⎬ ⎫ ⎩⎨ ⎧ ≠ =∩ φ φ Y YX Ta coù ñònh nghóa töông töï: LÑQH S= 3NF neáu ∀ XÆY∈ F thì: - Phu thuoäc haøm XÆY laø chính quy. - X laø sieâu khoaù cuûa S - Y laø thuoäc tính khoaù. II. 4 Ñònh nghóa Daïng chuaån BCNF: R ñaït daïng chuaån BCNF neáu ∀ XÆY∈ F thì: - Phu thuoäc haøm XÆY laø chính quy. - X laø sieâu khoaù cuûa S. Hay: R ñaït daïng chuaån BCNF ⇔∀ XÆY∈F: X+=R. Muïc ñích cuûa daïng chuaån BCNF laø loaïi boû dö thöøa maø caùc phuï thuoäc haøm coù theå gaây ra. Chuùng ta keát luaän raèng trong quan heä coù daïng BCNF, khoâng coù giaù trò naøo coù theå tieân ñoaùn töø nhöõng giaù trò khaùc baèng caùch chæ duøng phuï thuoäc haøm. Nhaän xeùt: • Tuyø muïc tieâu cuûa CSDL maø quyeát ñònh choïn daïng chuaån 3 hay BCNF, bôûi vì: NGUYEÃN THÒ LAN ANH Trang 7 Caùc daïng chuaån trong CSDL o Moãi daïng chuaån ñeàu coù ñieåm maïnh yeáu. o Daïng chuaån 3 tuy ñaõ loaïi boû ñöôïc nhöõng phuï thuoäc baéc caàu, boä phaän giöõa caùc thuoäc tính thöù caáp vaø caùc khoaù toái tieåu, nhöng coøn truøng laép thoâng tin. Tuy nhieân, ñieåm maïnh laø kieåm tra raøng buoäc ít toán keùm. o Daïng chuaån BCNF öu ñieåm laø trieät tieâu söï truøng laép thoâng tin nhöng nhöôïc ñieåm laø kieåm tra raøng buoäc toaøn veïn toán keùm hôn. • Lôùp quan heä BCNF laø lôùp con thöïc söï cuûa lôùp quan heä 3NF vaø lôùp quan heä 3NF laø lôùp con thöïc söï cuûa lôùp caùc quan heä 2NF. II.5 Phaân raõ coù noái khoâng maát: Neáu R laø moät LÑQH ñöôïc phaân raõ thaønh caùc löôïc ñoà R1, R2,. . ., Rn, F laø taäp phuï thuoäc, ta goïi ñaây laø phaân raõ noái khoâng maát(öùng vôùi F) neáu vôùi moãi quan heä r cuûa R thoaû F, ta coù: r = )(1 rRπ >< )(rRnπ Neáu ρ=( R1, R2,. . ., Rn) laø moät phaân raõ thì mρ(r) laø moät aùnh xaï ñöôïc ñònh nghóa laø mρ(r)= , nghóa laø m)(1 rRini π=>< ρ(r) laø noái caùc hình chieáu cuûa r treân caùc LÑQH trong ρ. Vì vaäy ñieàu kieän noái khoâng maát öùng vôùi taäp phuï thuoäc F laø: r= mρ(r) Nhaän xeùt: ñaëc tính noái khoâng maát laø caàn thieát neáu quan heä bò phaân raõ caàn phaûi ñöôïc khoâng phuïc töø phaân raõ cuûa chính noù. Kieåm tra tính chaát noái khoâng maát:(taøi lieäu) Ñònh lyù: neáu ρ=(R1,R2) laø moät phaân raõ cuûa R, vaø F laø taäp caùc phuï thuoäc haøm, thì ρ coù noái khoâng maát öùng vôùi F neáu vaø chæ neáu: (R1∩R2)ÆR1 hoaëc (R1∩R2)ÆR2 II.6 Phaân raõ baûo toaøn phuï thuoäc: Neáu R laø moät LÑQH ñöôïc phaân raõ thaønh caùc löôïc ñoà R1, R2,. . ., Rn, F laø taäp phuï thuoäc. NGUYEÃN THÒ LAN ANH Trang 8 Caùc daïng chuaån trong CSDL Lyù do ρ caàn baûo toaøn taäp F ñoù laø caùc phuï thuoäc trong F coù theå ñöôïc xem laø caùc raøng buoäc toaøn veïn cho quan heä R. Neáu caùc phuï thuoäc hình chieáu khoâng suy ra ñöôïc F thì khi bieåu dieãn R baèng ρ=( R1, R2,. . ., Rn), chuùng ta coù theå thaáy raèng giaù trò hieän haønh cuûa caùc Ri bieåu dieãn moät quan heä R khoâng thoaû F, ngay caû neáu ρ noái khoâng maát öùng vôùi F. Khi ñoù moãi thao taùc caäp nhaät treân Ri seõ caàn phaûi thöïc hieän moät pheùp noái ñeå kieåm tra laïi caùc raøng buoäc khoâng vi phaïm. Kieåm tra tính baûo toaøn phuï thuoäc:(taøi lieäu) II.7 Thuaät toaùn phaân raõ noái khoâng maát thaønh daïng chuaån BCNF Nhaäp: LÑQH S= Xuaát: Moät phaân raõ cuûa R coù noái khoâng maát, sao cho moãi LÑQH trong phaân raõ coù daïng BCNF öùng vôùi hình chieáu cuûa F treân löôïc ñoà. Phöông phaùp: Troïng taâm cuûa thuaät toaùn laø laáy LÑQH R roài phaân raõ thaønh hai löôïc ñoà. Moät löôïc ñoà coù taäp thuoäc tính XA; noù coù daïng BCNF vaø phuï thuoäc XÆA ñuùng. Löôïc ñoà thöù hai seõ laø R- A, do ñoù noái cuûa R-A vôùi XA laø noái khoâng maát. Thöïc hieän ñeä quy thuû tuïc phaân raõ, vôùi R-A ôû vò trí cuûa R cho ñeán khi löôïc ñoà R khoâng theå phaân raõ ñöôïc nöõa. Minh hoaï: result := {R }; done := false; Tính F +; while (not done) do if (coù löôïc ñoà Ri trong result maø khoâng laø BCNF) then begin Neáu AÆB laø moät phuï thuoäc haøm khoâng taàm thöôøng trong Ri maø AÆRi ∉F+ NGUYEÃN THÒ LAN ANH Trang 9 Caùc daïng chuaån trong CSDL vaø A ∩ B = ∅; result := (result – Ri ) ∪ (Ri – B) ∪ (A, B ); end else done := true; Nhaän xeùt: chuùng ta nhaän thaáy moïi LÑQH ñeàu coù moät phaân raõ noái khoâng maát thoâng tin thaønh daïng chuaån BCNF, tuy nhieân khoâng phaûi phaân raõ naøo cho moät LÑQH thaønh daïng BCNF maø vaãn baûo toaøn ñöôïc phuï thuoäc. Daïng chuaån 3NF ít khaét khe hôn BCNR, khoâng theå loaïi boû ñöôïc taát caû caùc dö thöøa. Tuy nhieân moät LÑQH phaân raõ thaønh daïng 3NF coù noái khoâng maát vaø baûo toaøn phuï thuoäc. II.8 Phuû toái thieåu: Cho LÑQH S= F={f: XÆA}, A laø moät thuoäc tính. • Phuû toái thieåu cuûa F, kyù hieåu PTT(F) laø moät taäp phuï thuoäc haøm thoaû: (PTT(F))+= F+ • Khoâng coù phuï thuoäc haøm naøo thöøa trong PTT(F), töùc laø: ¬ ∃ f: XÆA, f ∈PTT(F) sao cho: (PTT(F)/f)+= F+ • PTT(F) chæ goàm caùc phuï thuoäc haøm ñaày ñuû. II.9 Thuaät toaùn phaân raõ noái khoâng maát thaønh daïng chuaån 3NF: Nhaäp:LÑQH R vaø taäp phuï thuoäc F, chuùng ta coù theå giaû söû raèng F laø phuû cöïc tieåu maø khoâng laøm maát ñi tính toång quaùt. Xuaát: moät phaân raõ baûo toaøn phuï thuoäc cuûa R sao cho moãi LÑQH ñeàu coù daïng 3NF öùng vôùi hình chieáu cuûa F treân löôïc ñoà ñoù. Phöông phaùp: NGUYEÃN THÒ LAN ANH Trang 10 Caùc daïng chuaån trong CSDL Neáu coù nhöõng thuoäc tính cuûa R khoâng naèm trong moät phuï thuoäc naøo cuûa F duø ôû veá phaûi hay veá traùi, thì veà nguyeân taéc, moïi thuoäc tính nhö theá ñeàu coù theå taïo ra moät löôïc ñoà vaø chuùng ta coù theå loaïi chuùng ra khoûi R. Neáu moät trong nhöõng phuï thuoäc trong F coù chöùa taát caû caùc thuoäc tính cuûa R thì keát xuaát chính laø R, ngöôïc laïi, phaân raõ keát xuaát ρ seõ chöùa löôïc ñoà XA cho moãi phuï thuoäc XÆA trong F. Neáu khoâng coù löôïc ñoà naøo trong ρ chöùa moät khoaù baát kyø cuûa R thì ta thöïc hieän theâm vaøo ρ moät löôïc ñoà coù taäp thuoäc tính laø moät khoaù baát kyø cuûa R. Minh hoaï: Cho Fc laø moät phuû cöïc tieåu cuûa F; i := 0; for each phuï thuoäc haøm AÆB trong Fc do if khoâng coù löôïc ñoà Rj, 1 ≤ j ≤ i chöùa AB then begin i := i + 1; Ri := AB end if khoâng coù löôïc ñoà Rj, 1 ≤ j ≤ i chöùa moät khoaù cuûa R then begin i := i + 1; Ri := baát kyø khoaù naøo cuûa R; end return (R1, R2, ..., Ri) NGUYEÃN THÒ LAN ANH Trang 11 Khaùi nieäm veà CSDL coù tính thôøi gian PHAÀN III KHAÙI NIEÄM VEÀ CÔ SÔÛ DÖÕ LIEÄU COÙ TÍNH THÔØI GIAN Moät thuoäc tính: moâ taû moät ñaëc tính hoaëc ñaëc ñieåm naøo ñoù cuûa moät thöïc theå(söï vaät). Ví duï: Mscb, HoTen, QueQuan, DiaChi, ChucVu, PhongBan, BacLuong. . . Coù nhaän xeùt raèng, trong taäp thuoäc tính coù: - Nhöõng thuoäc tính maø giaù trò oån ñònh theo thôøi gian. Ví duï: Mscb, HoTen, . . . - Nhöõng thuoäc tính maø giaù trò thay ñoåi theo thôøi gian.Ví du: DiaChi, ChucVu, PhongBan, BacLuong,. . . Nhö vaäy, chuùng ta seõ môû roäng caùc khaùi nieäm LÑQH, quan heä, phuï thuoäc haøm, thuoäc tính thoâng thöôøng vôùi thuoäc tính thôøi gian. III.1 Khaùi nieäm thuoäc tính thôøi gian: Ta tìm hieåu veà khaùi nieäm thôøi ñieåm vaø khoaûng thôøi gian trong thuoäc tính thôøi gian. - Ta goïi khoâng gian caùc thôøi ñieåm C: laø khoâng gian 1 chieàu lieân tuïc khoâng aâm [0,+∞ ]. Vaø treân ñoù coù xaùc ñònh quan heä thöù töï “≤”. 0 C it ∞+ - Vôùi ti ∈ C laø moät thôøi ñieåm baát kyø, ta kyù hieäu: + Moät taäp con caùc thôøi ñieåm ⊂α C ñöôïc goïi laø moät khoaûng thôøi gian neáu: C, ∈∀ 321 ,, ttt 321 ttt ≤≤ , αα ∈⇒∈ 231 , ttt + Goïi T laø taäp hôïp taát caû caùc khoaûng thôøi gian: ⊂α C T= }:{ C⊂αα + Hai khoaûng keà nhau: 1α vaø 2α goïi laø keà nhau, kyù hieäu 21 αα < neáu: 1α =[a,b) vaø 2α =[c,d) vaø b=c Hoaëc 1α =[a,b] vaø 2α =[c,d] vaø b=c - 1 NGUYEÃN THÒ LAN ANH Trang 12 Khaùi nieäm veà CSDL coù tính thôøi gian Ví duï: Cho 3 thôøi ñieåm a,b,c bieåu thò giaù trò Naêm nhö sau: a = 1999, b= 2003, c= 2006. Coù: a,b,c ∈ thuoäc khoâng gian caùc thôøi ñieåm C. 1α =[1999,2003), 2α =[2003,2006) laø 2 khoaûng thôøi gian keà nhau. Coù: ∈21,αα T vaø 21 αα < III.2 Löôïc ñoà quan heä coù tính thôøi gian: Môû roäng cuûa LÑQH bình thöôøng, LÑQH thôøi gian xeùt theâm vaøo trong taäp thuoäc tính R moät thuoäc tính thôøi gian. LÑQH coù tính thôøi gian(TTG) ST laø moät boä ST =(RT, FT). Trong ñoù: RT laø taäp thuoäc tính. FT laø taäp caùc phuï thuoäc haøm treân taäp RT hay phuï thuoäc haøm tính thôøi gian. Nhaän xeùt: trong LÑQH TTG, caùc thuoäc tính bao goàm : - Thuoäc tính coù giaù trò oån ñònh theo thôøi gian, goïi laø thuoäc tính oån ñònh, kyù kieäu: R - Thuoäc tính coù giaù trò thay ñoåi theo thôøi gian, goïi laø thuoäc tính coù tính thôøi gian, kyù hieäu: R . - T: laø taäp thuoäc tính thôøi gian. Nhaän xeùt: trong ñeà taøi naøy, chæ xeùt tröôøng hôïp taäp thuoäc tính thôøi gian goàm moät thuoäc tính |T|=1. Xeùt thuoäc tính thôøi gian: - Trong moät soá baøi baùo ñeà xuaát: giaù trò thuoäc tính thôøi gian T laø moät khoaûng thôøi gian [Ts, Te] hoaëc [Ts,Te) - Trong moät soá baøi baùo khaùc laïi ñeà xuaát: giaù trò thuoäc tính thôøi gian T taùch thaønh 2 giaù trò thuoäc tính thôøi gian Ts vaø Te. ∀Ai ∈RT(i=1,…,n), moãi thuoäc tính Ai coù mieàn giaù trò D(Ai)=Di töông öùng. NGUYEÃN THÒ LAN ANH Trang 13 Khaùi nieäm veà CSDL coù tính thôøi gian Neáu Ai=T(T: thuoäc tính thôøi gian) thì D(Ai)⊂ T (T: laø taäp hôïp caùc khoaûng thôøi gian). Ví duï: Xeùt quan heä THOÂNG_TIN_CAÙN_BOÄ(MACB, HOTEN, GIÔÙITINH, QUEQUAN, PHONGBAN, CHUCVU, LUONGHS, DANGVIEN) MSCB HOTEN GIOI TINH QUE QUAN PHONG BAN CHUC VU LUONG HS DANG VIEN 1234 NG.V.A NÖÕ THANH HOA MOI TRUONG CAN BO GIANG DAY 2.34 KHOÂNG 1235 NG.V.B NAM HA NOI HOA HOC CAN BO GIANG DAY 2.67 COÙ 1236 NG.V.C NAM TP.HCM VAT LY PHO KHOA 4.32 KHOÂNG 1237 NG.V.D NÖÕ HA TINH NGOAI NGU GIANG VIEÂN 3 KHOÂNG …. ….. …… …… ….. …… ….. ….. Baûng döõ lieäu naøy löu thoâng tin veà caùn boä cuûa moät tröôøng ñaïi hoïc trong khoaûng thôøi gian [2004,2005]. Moãi doøng döõ lieäu löu thoâng tin cuûa moät caùn boä vaø moät thoâng tin cuûa moät caùn boä chæ ñöôïc bieåu dieãn duy nhaát treân moät doøng. Vôùi quan heä treân deã daøng nhaän thaáy khoaù cuûa quan heä Kr laø MSCB Trong quaù trình quaûn lyù, do thoâng tin cuûa caùc caùn boä coù söï thay ñoåi neân haøng naêm seõ coù moät baûng thoâng tin môùi veà caùc caùn boä. Söï thay ñoåi coù theå naèm ôû caùc thuoäc tính: PHONGBAN, CHUCVU, LUONGHS, DANGVIEN. Do yeâu caàu quaûn lyù, ngöôøi söû duïng caàn quan taâm tôùi thoâng tin veà caùc caùn boä trong taát caùc khoaûng thôøi gian. Nhö vaäy ta coù moät quan heä THOÂNG_TIN_CAÙN_BOÄ môùi theå hieân bôûi moät baûng döõ lieäu chung, laø taäp hôïp caùc baûng döõ lieäu THOÂNG_TIN_CAÙN_BOÄ trong taát caû caùc khoaûng thôøi gian, nhö sau: NGUYEÃN THÒ LAN ANH Trang 14 Khaùi nieäm veà CSDL coù tính thôøi gian MSCB HOTEN GIOI TINH QUE QUAN PHONG BAN CHUC VU LUONG HS DANG VIEN THÔØI GIAN 1234 NG.V.A NÖÕ THANH HOA MOI TRUONG CAN BO GIANG DAY 2.34 KHOÂNG [2004,2005) 1234 NG.V.A NÖÕ THANH HOA MOI TRUONG CAN BO GIANG DAY 2.34 COÙ [2005,2006) 1235 NG.V.B NAM HA NOI HOA HOC CAN BO GIANG DAY 2.67 COÙ [2004,2005) 1235 NG.V.B NAM HA NOI HOA HOC CAN BO GIANG DAY 2.67 COÙ [2005,2006) 1236 NG.V.C NAM TP.HCM VAT LY GIAÛNG VIEÂN 3.0 KHOÂNG [2000,2001) 1236 NG.V.C NAM TP.HCM VAT LY GIAÛNG VIEÂN 3.0 KHOÂNG [2001,2002) 1236 NG.V.C NAM TP.HCM VAT LY GIAÛNG VIEÂN 3.5 KHOÂNG [2002,2003) 1236 NG.V.C NAM TP.HCM VAT LY GIAÛNG VIEÂN 3.5 KHOÂNG [2003,2004) 1236 NG.V.C NAM TP.HCM VAT LY PHO KHOA 4.32 KHOÂNG [2004,2005) 1236 NG.V.C NAM TP.HCM VAT LY PHO KHOA 4.32 COÙ [2005,2006) 1237 NG.V.D NÖÕ HA TINH NGOAI NGU GIANG VIEÂN 2.67 KHOÂNG [2000,2001) 1237 NG.V.D NÖÕ HA TINH NGOAI NGU GIANG VIEÂN 2.67 KHOÂNG [2001,2002) 1237 NG.V.D NÖÕ HA TINH NGOAI NGU GIANG VIEÂN 2.67 KHOÂNG [2002,2003) 1237 NG.V.D NÖÕ HA TINH NGOAI NGU GIANG VIEÂN 2.67 KHOÂNG [2003,2004) 1237 NG.V.D NÖÕ HA TINH NGOAI NGU GIANG VIEÂN 3.0 KHOÂNG [2004,2005) 1237 NG.V.D NÖÕ HA TINH NGOAI NGU GIANG VIEÂN 3.0 COÙ [2005,2006) …. ….. …… …… ….. …… ….. ….. Quan heä THOÂNG_TIN_CAÙN_BOÄ môùi coù tính toång quaùt hôn quan heä THOÂNG_TIN_CAÙN_BOÄ cuõ bôûi thuoäc tính coù tính thôøi gian T. Khoaù cuûa quan heä THOÂNG_TIN_CAÙN_BOÄ thôøi gian khoâng coøn laø MSCB. Vieäc xeùt khoaù cuûa quan heä thôøi gian ta seõ ñeà caäp ôû phaàn sau. III.3 Ñònh nghóa quan heä tính thôøi gian r(RT) hay rT: Cho: RT={A1, A2,…,An} Moät quan heä r(RT) laø moät taäp höõu haïn caùc aùnh xaï töø taäp thuoäc tính RT vaøo hôïp mieàn giaù trò caùc thuoäc tính. Goïi D(RT)= )()()( TDRDRD ∪∪ laø hôïp mieàn giaù trò caùc thuoäc tính RT Moät quan heä r(RT) (hay rT ) vôùi m aùnh xaï cho nhö sau: rT= {t1,t2,….,tm}, trong ñoù: ti laø aùnh xaï: RT Æ D(RT) Aj Æ ti(Aj) ∈ Dj (i=1,..,m; j=1,…,n) Nhö vaäy: giaù trò cuûa ti(Aj) laø giaù trò öùng vôùi khoaûng thôøi gian ti(T), noùi caùch khaùc, moïi thuoäc tính cuûa RT ñeàu xeùt giaù trò treân nhöõng khoaûng thôøi gian. III.4 Ñònh nghóa tính töông ñöông: Xeùt quan heä r(RT) hay rT NGUYEÃN THÒ LAN ANH Trang 15 Khaùi nieäm veà CSDL coù tính thôøi gian Ta noùi hai boä t, t’∈rT laø töông ñöông, KH: t≅ t’ t t’ ≅ ))(')(( AtAtRA =⇒∈∀⇔ YÙ nghóa: Hai boä töông ñöông neáu vaø chæ neáu giaù trò caùc thuoäc tính oån ñònh (R) cuûa chuùng gioáng nhau treân 2 boä. Ví duï: 1236 NG.V.C NAM TP.HCM VAT LY GIAÛNG VIEÂN 3.5 COÙ [2003,2004) 1236 NG.V.C NAM TP.HCM VAT LY PHO KHOA 4.32 COÙ [2004,2005) Nhaän xeùt: Coù söï truøng laép thoâng tin ôû nhöõng boä töông ñöông. Cuï theå laø truøng laép thoâng tin ôû caùc thuoäc tính oån ñònh. Coù theå xoùa bôùt caùc boä truøng laép baèng pheùp hôïp nhaát, pheùp hôïp nhaát 2 boä t’ vaø t” ∈rT (KH: ⊕ )ñöôïc ñònh nghóa nhö sau: t=t’⊕ t” ))(")(')(:()"'( AtAtAtRAtt ∪=∈∀∧≅⇔ Vaäy: muoán hôïp nhaát 2 boä t’ vaø t” cuûa quan heä thôøi gian rT tröôùc heát 2 boä t’ vaø t” phaûi töông ñöông. Keát quaû cuûa pheùp hôïp nhaát laø boä t coù: giaù trò nhöõng thuoäc tính oån ñònh(R) cuûa t gioáng hai boä t’ vaø t”, giaù trò nhöõng thuoäc tính tính thôøi gian( R ) cuûa t laø hôïp cuûa 2 boä t’ vaø t”. - Toång quaùt cho n boä töông ñöông t1,t2,. . .,tn laø: t= i n t⊕1 YÙ nghóa: Pheùp hôïp nhaát phaân quan heä r thaønh caùc lôùp töông ñöông. Caùc phaàn töû trong moät lôùp töông ñöông coù giaù trò gioáng nhau ôû caùc thuoäc tính oån ñònh. Xeùt quan heä THOÂNG_TIN_CAÙN_BOÄ(MACB, HOTEN, GIÔÙITINH, QUEQUAN, PHONGBAN, CHUCVU, LUONGHS, DANGVIEN) Trong thöïc teá, thôøi ñieåm moät caùn boä thay ñoåi phoøng ban, chöùc vu, löônghs hay vaøo ñaûng laø khaùc nhau. Ta ñöa ra ñònh nghóa veà quan heä loàng, cho pheùp bieåu dieãn khoaûng thôøi NGUYEÃN THÒ LAN ANH Trang 16 Khaùi nieäm veà CSDL coù tính thôøi gian gian thay ñoåi giaù trò cuûa töøng thuoäc tính vaø giuùp giaûm thieåu söï truøng laép ôû nhöõng boä töông ñöông. III.5 Quan heä loàng vôùi giaù trò thôøi gian:(moâ hình khaéc phuïc) Cuõng töông töï nhö ñònh nghóa quan heä thöôøng, quan heä loàng cuõng coù taäp thuoäc tính R nhöng thuoäc tính cuûa quan heä loàng ñöôïc bieåu dieãn bôûi 1 caëp trong ñoù: • T bieåu dieãn giaù trò thôøi gian, cuï theå laø khoaûng thôøi gian. • v bieåu dieãn giaù trò cuûa thuoäc tính töông öùng vôùi khoaûng thôøi gian t. Nhaän thaáy: trong quan heä loàng khoâng coù thuoäc tính thôøi gian T ñöùng ñoäc laäp maø thuoäc tính thôøi gian ñöôïc loàng vaøo trong caùc thuoäc tính khaùc. Ví duï: xeùt moät quan heä QUAN_LY_NHAÂN_VIEÂN nhö sau: MSCB HOTEN PHONGBAN LUONGHS Nhaän thaáy: khoaù cuûa quan heä laø thuoäc tính MSCB Ta coù theå phaù quan heä loàng thaønh quan heä sau: MSCB HOTEN PHONGBAN LUONGHS Moät nhaân vieân trong suoát quaù trình laøm vieäc coù theå laøm ôû nhieàu phoøng vaø coù nhieàu baäc löông. Baûng thöù 2 coù theå gaây ra sö thöøa döõ lieäu khi caäp nhaät. Lyù do xaûy ra tình traïng treân laø tính khoâng phuï thuoäc laãn nhau giöõa hai thuoäc tính PHONGBAN vaø LUONGHS. Ta coù 2 phuï thuoäc ña trò :MSCB →→ PHONGBAN vaø MSCB →→LUONGHS. III.6 Caùc thao taùc treân quan heä coù TTG: NGUYEÃN THÒ LAN ANH Trang 17 Khaùi nieäm veà CSDL coù tính thôøi gian Trong ñeà taøi naøy chæ xeùt giaù trò thuoäc tính thôøi gian T laø moät khoaûng thôøi gian [Ts, Te] hoaëc [Ts,Te) vaø trong taäp thuoäc tính RT coù moät thuoäc tính thôøi gian duy nhaát. Nghóa laø: xeùt caùc thuoäc tính theo moät thuoäc tính thôøi gian. Cho t, t’∈rT. Pheùp keùo theo: Ta goïi t laø keùo theo t’ treân rT, KH: t t’ neáu: t= t⎯→⎯T ⊕ t’. Nghóa laø: giaù trò nhöõng thuoäc tính TTG cuûa t’ phaûi laø taäp con cuûa t, t[ R ]⊃t’[R ]. Ví duï:(*) Boä t’ cho nhö sau: 1236 NG.V.C NAM TP.HCM VAT LY GIAÛNG VIEÂN 3.0 KHOÂNG [2000,2001) Boä t cho nhö sau: 1236 NG.V.C NAM TP.HCM VAT LY GIAÛNG VIEÂN, PHOÙ KHOA 3.0, 3.5, 4.32, 4.32 KHOÂNG COÙ [2000,2001), [2001,2002), [2002,2003), [2003,2004) [2004,2005) [2005.2006) Quan heä tính thôøi gian rT: Cho r laø moät quan heä bình thöôøng, quan heä TTG rT vôùi thuoäc tính thôøi gian T theâm vaøo trong taäp thuoäc tính. Khi ñoù quan heä tính thôøi gian rT laø taäp hôïp: rT={t: '} :',' ttttrt T⎯→⎯≅∈∃ Nhaän xeùt: Caùc bieåu dieãn quan heä tính thôøi gian nhö trong ví duï (*) deã daãn tôùi tình traïng thoâng tin khoâng roõ raøng, vì khoâng bieát söï thay ñoåi cuûa caùc thuoâc tính öùng vôùi khoaûng thôøi gian naøo. Vì theá sau naøy, ta coù theå duøng quan heä loàng ñeå bieåu dieãn quan heä tính thôøi gian. NGUYEÃN THÒ LAN ANH Trang 18 Khaùi nieäm veà CSDL coù tính thôøi gian MSCB HOTEN GIOI TINH QUE QUAN PHONG BAN CHUC VU LUONG HS DANG VIEN <[2004,20 06), 1234> <[2004,2006), NG.V.A> <[2004,2006), NÖÕ> <[2004,2006), THANH HOA> <[2004,2006), MOI TRUONG> <[2004,2006), CAN BO GIANG DAY> <[2004,2006), 2.34> <[2004,2005), KHOÂNG>, <[2005,2006), COÙ> <[2004,20 06), 1235> <[2004,2006), NG.V.B> <[2004,2006), NAM> <[2004,2006), HA NOI> <[2004,2006), HOA HOC> <[2004,2006), CAN BO GIANG DAY> <[2004,2006), 2.67> <[2004,2006), COÙ> <[2000,20 06), 1236> <[2000,2006), NG.V.C> <[2000,2006), NAM> <[2004,2006), TP.HCM> <[2000,2006), HOA HOC> <[2000,2004) GIAÛNG VIEÂN>, <[2004,2006), PHOÙ KHOA> <[2000,2002), 3.0>, <[2002,2004), 3.5> <[2004,2006), 4.32> <[2000,2005), KHOÂNG>, <[2005,2006), COÙ> <[2000,20 06), 1237> <[2000,2006), NG.V.D> <[2000,2006), NÖÕ> <[2000,2006), HA TINH> <[2000,2006), NGOAI NGU> <[2000,2006), GIAÛNG VIEÂN> <[2000,2004), 2.67>, <[2004,2006), 3.0> <[2000,2005), KHOÂNG>, <[2005,2006), COÙ> Ví duï: Xeùt quan heä TTG- THOÂNG_TIN_CAÙN_BOÄ(MACB, HOTEN, GIÔÙITINH, QUEQUAN, PHONGBAN, CHUCVU, LUONGHS, DANGVIEN) ñöôïc bieåu dieãn döôùi daïng quan heä loàng, nhö sau: Nhaän thaáy: Thuoäc tính thôøi gian T khoâng ñöùng ñoäc laäp maø ñöôïc loàng vaøo trong caùc thuoäc tính khaùc. Ñònh nghóa taäp con: Quan heä rT1 ñöôïc goïi laø taäp con TTG cuûa quan heä rT2, KH: rT1 ⊆ rT2 Neáu: ∀ t∈rT1 ⇒ t∈rT2 (moïi boä cuûa quan heä rT1 ñeàu thuoäc rT2) Pheùp hôïp TTG: Cho rT1 vaø rT2. Pheùp hôïp TTG, KH: r1 r T∪ 2 r1 r T∪ 2 neáu ∀t ∈(r1 rT∪ 2) ⇔ (t T∈r1) ∧ (t T∈r2) ∧ (∃ t’∈rT1, ∃ t” t∈rT2 :t=t’ t”) ⊕ Pheùp hieäu TTG: Cho rT1 vaø rT2. Pheùp hieäu TTG, KH: r1 T− r2 r1 r T− 2 neáu ∀t∈ (r1 rT− 2) ⇔ (t∈rT1) ∧ (t∉rT2) Nhaän xeùt: Cho rT1 vaø rT2. Pheùp giao TTG, KH: r1 T∩ r2 NGUYEÃN THÒ LAN ANH Trang 19 Khaùi nieäm veà CSDL coù tính thôøi gian r1 r T∩ 2 = rT1 \ (r1 r T− 2) hoaëc r1 T∩ r2 = rT2 \ (r2 T− r1) Pheùp keát noái TTG: Cho rT1 laø quan heä thuoäc LÑQH TTG RT1, rT2 laø quan heä thuoäc LÑQH TTG RT2 RT1: taäp thuoäc tính thôøi gian cuûa LÑQH 1 RT2: taäp thuoäc tính thôøi gian cuûa LÑQH 2 Pheùp keát noái TTG, KH: neáu t∈( ) ⇔ (∀A∈(R21 || rr T>< 21 || rr T>< T1∩RT2), ∃t’∈rT1 ,∃t”∈ rT2, t(A)=t’(A)=t”(A)). III.7 Khaùi nieäm veà phuï thuoäc haøm TTG: Cho rT laø moät quan heä TTG treân RT X,Y laø taäp con cuûa RT. • Ta goïi laø phuï thuoäc haøm TTG cuûa rYX T→ T neáu∀ t, t’∈rT, ∀α ∈T(T: laø taäp hôïp caùc khoaûng thôøi gian): (t[X]/α =t’[X]/α ) ⇒ (t[Y]/α =t’[Y]/α ) Trong ñoù: t[X]/α laø bieåu dieãn cuûa giaù trò t[X] trong khoaûng thôøi gian α . Ví duï: Xeùt quan heä TTG- THOÂNG_TIN_CAÙN_BOÄ(MACB, HOTEN, GIÔÙITINH, QUEQUAN, PHONGBAN, CHUCVU, LUONGHS, DANGVIEN,THOIGIAN): ∀ t, t’∈rT, ∀α ∈T: (t[MACB]/α =t’[MACB]/α ) ⇒ (t[HOTEN]/α =t’[HOTEN]/α ), phuï thuoäc haøm TTG: . HOTENMACB T→ Töông töï, ta coù caùc phuï thuoäc haøm TTG: GIOITINHMACB T→ QUEQUANMACB T→ PHONGBANMACB T→ CHUCVUMACB T→ LUONGHSMACB T→ DANGVIENMACB T→ THOIGIANMACB T→ Ta goïi laø phuï thuoäc haøm TTG cuûa löôïc ñoà quan heä TTG RYX T→ T(hay X xaùc ñònh Y theo kieåu haøm; hay Y phuï thuoäc haøm vaøo X) neáu: ∀ quan heä TTG rT laø NGUYEÃN THÒ LAN ANH Trang 20 Khaùi nieäm veà CSDL coù tính thôøi gian giaù trò hieän haønh cuûa RT: phuï thuoäc haøm ñuùng treân quan heä rYX T→ T( hay rT hôïp leä ñoái vôùi phuï thuoäc haøm ) YX T→ Nhaän xeùt: o So vôùi khaùi nieäm phuï thuoäc haøm, khaùi nieäm phuï thuoäc haøm TTG coù tính toång quaùt hôn. Trong ñònh nghóa phuï thuoäc haøm bình thöôøng, giaù trò cuûa caùc thuoäc tính ñöôïc xem nhö xeùt treân 1 khoaûng thôøi gian chung duy nhaát. Trong ñònh nghóa phuï thuoäc haøm TTG, giaù trò cuûa caùc thuoäc tính ñöôïc xeùt treân caùc khoaûng thôøi gian khaùc nhau. o Vôùi nhöõng thuoäc tính giaù trò oån ñònh theo thôøi gian thì trong caùc khoaûng khoaûng thôøi gian khaùc nhau vaãn giöõ nguyeân giaù trò. Vì vaäy ñònh nghóa phuï thuoäc haøm TTG vaãn ñaûm baûo cho nhöõng phuï thuoäc haøm chöùa thuoäc tính oån ñònh thôøi gian. III.8 Ñònh nghóa Khoùa TTG Ñònh nghóa bao ñoùng phuï thuoäc haøm vaø bao ñoùng thuoäc tính TTG cuõng gioáng ñònh nghóa bao ñoùng phuï thuoäc haøm vaø bao ñoùng thuoäc tính bình thöôøng. LÑQH TTG ST laø moät boä ST =(RT, FT). Trong ñoù: RT laø taäp thuoäc tính. FT laø taäp caùc phuï thuoäc haøm treân taäp RT hay phuï thuoäc haøm TTG. K⊆ RT • K goïi laø sieâu khoaù(super key) TTG cuûa löôïc ñoà quan heä TTG RT neáu vaø chæ neáu: ∀ X∈ RT thì ∈FXK T→ T+ Hay: K goïi laø sieâu khoaù TTG cuûa löôïc ñoà quan heä TTG RT neáu vaø chæ neáu K+F=RT. • K goïi laø khoaù ñeà nghò(candidate key) TTG cuûa löôïc ñoà quan heä TTG RT neáu vaø chæ neáu: o K+F=RT o Khoâng ∃K’⊂ K, K’+F=RT NGUYEÃN THÒ LAN ANH Trang 21 Khaùi nieäm veà CSDL coù tính thôøi gian Ví duï: Xeùt quan heä TTG- THOÂNG_TIN_CAÙN_BOÄ(MACB, HOTEN, GIÔÙITINH, QUEQUAN, PHONGBAN, CHUCVU, LUONGHS, DANGVIEN,THOIGIAN) K={MSCB }, laø moät khoaù TTG. NGUYEÃN THÒ LAN ANH Trang 22 Caùc daïng chuaån TTG PHAÀN IV CAÙC DAÏNG CHUAÅN TTG Cho LÑQH TTG ST= RT: taäp thuoäc tính. FT laø taäp phuï thuoäc haøm TTG IV.1 Daïng chuaån 1 TTG(1TNF) Cho LÑQH S=, khoaù K. LÑQH TTG ST= laø môû roäng cuûa S, quan heä TTG r(RT) laø môû roäng cuûa r(R)(quan heä r chöa xeùt thuoäc tính thôøi gian) LÑQH TTG ST ñaït daïng chuaån 1TNF neáu thoaû ñieàu kieän: ∀r(RT)(hay rT), ∀t,t’∈rT neáu t(K)=t’(K) thì t(T) vaø t’(T) khoâng giao nhau. Trong ñoù K laø khoaù cuûa quan heä r khi chöa xeùt tính thôøi gian. Ví duï: Quan heä cho sau ñaït daïng chuaån 1NF vì vôùi 2 boä t,t∈rT, K={MSNV} t[MSNV]=t’[MSNV] nhöng t[T] vaø t’[T] khoâng truøng nhau. MSNV TENNV PHONG THÔØIGIAN(T) 1234 N.V.A KEÁ TOAÙN [1,5) 1234 N.V.A THIEÁTBÒ [5,10} Ñònh nghóa veà daïng chuaån 2TNF, 3TNF vaø TBCNF cuõng gioáng ñònh nghóa cuûa LÑQH bình thöôøng. Cho LÑQH TTG ST=(coøn goïi laø LÑQH TTG RT), K laø moät khoaù toái tieåu TTG. LÑQH TTG RT muoán ñaït 2TNF, 3TNF vaø TBCNF thì phaûi ñaït 1TNF. IV.2 Daïng chuaån 2 TTG(2TNF): Löôïc ñoà quan heä TTG RT ñaït daïng chuaån 2 khi vaø chæ khi: - Löôïc ñoà quan heä RT ñaït 1TNF NGUYEÃN THÒ LAN ANH Trang 23 Caùc daïng chuaån TTG - Moïi thuoäc tính thöù caáp ñeàu phuï thuoäc ñaày ñuû vaøo khoaù toái tieåu baát kyø. Hay: ∉ FYX T→ t+ , ∀X⊂ K vaø Y⊄ K(X laø taäp con thöïc söï cuûa K vaø Y khoâng thuoäc moät khoaù toái tieåu naøo cuûa RT) IV.3 Daïng chuaån 3 TTG(3TNF): RT thoûa daïng chuaån 3 TTG(3-TNF) neáu: YX T→ ∉ FT+ ñoái vôùi moïi X sao cho X+F ≠ RT, Y∉ X vaø Y⊄ K Noùi khaùc, RT laø thoûa daïng chuaån 3 TTG neáu vôùi moïi phuï thuoäc haøm khoâng taàm thöôøng ∈ FYX T→ T+ thì X hoaëc laø sieâu khoùa TTG cuûa RT hoaëc Y thuoäc vaøo moät khoùa toái thieåu naøo ñoù cuûa RT. IV.4 Daïng chuaån TBCNF: LÑQH TTG RT thoûa daïng chuaån BCNF TTG neáu: YX T→ ∉ FT+ ñoái vôùi moïi X sao cho X+F ≠RT, Y∉ X( khoâng taàm thöôøng) YX T→ Noùi khaùc, RT laø thoûa daïng chuaån TBCNF neáu vôùi moïi phuï thuoäc haøm khoâng taàm thöôøng ∈ FYX T→ T+ thì X laø sieâu khoùa TTG cuûa RT NGUYEÃN THÒ LAN ANH Trang 24 Raøng buoäc oån ñònh TTG PHAÀN V RAØNG BUOÄC OÅN ÑÒNH TTG Xeùt LÑQH TTG THOÂNG_TIN_CAÙN_BOÄ(MACB, HOTEN, GIÔÙITINH, QUEQUAN, PHONGBAN, CHUCVU, LUONGHS, DANGVIEN, THOIGIAN) Caùc thuoäc tính oån ñònh: MACB, HOTEN, GIOITINH, QUEQUAN. Caùc thuoäc tính TTG: PHONGBAN, CHUCVU, LUONGHS, DANGVIEN. Thuoäc tính thôøi gian: THOIGIAN . Xeùt 2 thuoäc tính: CHUCVU vaø LUONGHS(laø nhöõng thuoäc tính thay ñoåi theo thôøi gian), tuy nhieân möùc ñoä thay ñoåi cuûa 2 thuoäc tính naøy khoâng gioáng nhau. Khi CHUCVU cuûa moät ñoái töôïng thay ñoåi, LUONGHS cuõng thay ñoåi theo. Neáu LUONGHS cuûa moät ñoái töôïng thay ñoåi, CHUCVU chöa chaéc ñaõ thay ñoåi. Ta noùi, giöõa CHUCVU vaø LUONGHS coù tính raøng buoäc oån ñònh, CHUCVU oån ñònh hôn LUONGHS. Vieäc phaân tích phuï thuoäc haøm TTG, caùc daïng chuaån TTG laø ñeå taïo cô sôû ñeå phaân tích moät moät ñaëc tröng cuûa CSDL TTG, cuõng laø moät öu ñieåm cuûa CSDL TTG khaùc vôùi nhöõng ñaëc ñieåm cuûa CSDL bình thöôøng laø khaùi nieäm tính raøng buoäc oån ñònh TTG. V.1 Ñònh nghóa veà tính raøng buoäc oån ñònh TTG: LÑQH TTG ST=, K laø khoaù TTG, quan heä TTG r(RT) ∀X,Y ⊆RT, ta noùi giöõa X vaø Y coù tính raøng buoäc oån ñònh vaø X oån ñònh hôn Y(kyù hieäu X Y) neáu ∀t,t’ ∈ r>− T thoaû 2 ñieàu kieän: • t[K]=t’[K] • 21 αα < , neáu t[X]/ 1α ≠t’[X]/ 2α ⇒ t[Y]/ 1α ≠t’[Y]/ 2α hay t[Y]/ 1α =t’[Y]/ 2α ⇒ t[X]/ 1α =t’[X]/ 2α NGUYEÃN THÒ LAN ANH Trang 25 Raøng buoäc oån ñònh TTG Phaùt bieåu: neáu 2 boä baát kyø cuûa quan heä r baèng nhau treân khoaù TTG, thì söï baèng nhau treân Y keùo theo söï baèng nhau treân X. Neáu X vaø Y oån ñònh ngang caáp nhau(kyù hieäu: X >− >− X Ví duï: ta coù moät raøng buoäc oån ñònh TTG: CHUCVU >− LUONGHS HOTEN QUOCGIA, HOTEN vaø QUOCGIA laø caùc thuoäc tính oån ñònh ngang caáp. >< − Nhaän xeùt: Khoaù toái thieåu KT laø thuoäc tính oån ñònh nhaát(cm döïa vaøo ñònh nghóa raøng buoäc oån ñònh TTG) V.2 Caùc luaät daãn AMSTRONG veà raøng buoäc oån ñònh TTG: Luaät daãn 1: Neáu X⊂Y ⇒ X Y(raøng buoäc taàm thöôøng) >− Luaät daãn 2: Neáu X Y vaø W⊂Z ⇒ XW>− >− YZ Luaät daãn 3: Neáu X Y vaø Y>− >− X ⇒ X >− Z(tính baéc caàu) Chöùng minh ñöôïc luaät daãn 1, luaät daãn 2, luaät daãn 3 laø ñaày ñuû. Chöùng minh: Cho rT laø moät quan heä TTG treân RT, ∀t,t’∈rT baèng nhau treân khoaù TTG K , 21 αα < laø hai khoaûng keà nhau Luaät daãn 1: Neáu t[Y]/ 1α =t’[Y]/ 2α , X⊂Y (giaû thieát) ⇒ t[X]/ 1α =t’[X]/ 2α Theo ñònh nghóa raøng buoäc oån ñònh TTG ta coù: Y >− X(Ñpcm). Luaät daãn 2: giaû söû coù t[YZ]/ 1α =t’[YZ]/ 2α ⇒ (1) ⎭⎬ ⎫ ⎩⎨ ⎧ = = 21 21 /]['/][ /]['/][ αα αα YtYt ZtZt ta coù: X Y(gt) theo ñònh nghóa cuûa raøng buoäc oån ñònh neân >− (1)⇔ (2) ⎭⎬ ⎫ ⎩⎨ ⎧ = = 21 21 /]['/][ /]['/][ αα αα XtXt ZtZt ta coù: W⊂Z(gt)⇒ W Z(Luaät daãn 1) neân >− (2) ⇔ ⇔ t[XW]/ ⎭⎬ ⎫ ⎩⎨ ⎧ = = 21 21 /]['/][ /]['/][ αα αα XtXt WtWt 1α =t’[XW]/ 2α Ta coù: t[YZ]/ 1α =t’[YZ]/ 2α ⇒ t[XW]/ 1α =t’[XW]/ 2α ⇒ XW >− YZ(Ñpcm) NGUYEÃN THÒ LAN ANH Trang 26 Raøng buoäc oån ñònh TTG Luaät daãn 3: Coù X Y(gt) ⇒ t[Y]/>− 1α =t’[Y]/ 2α ⇒ t[X]/ 1α =t’[X]/ 2α Y Z(gt) ⇒ t[Z]/>− 1α =t’[Z]/ 2α ⇒ t[Y]/ 1α =t’[Y]/ 2α Töø ñoù suy ra: t[Z]/ 1α =t’[Z]/ 2α ⇒ t[X]/ 1α =t’[X]/ 2α ⇒ X >− Z(Ñpcm) V.3 Bao ñoùng taäp caùc raøng buoäc oån ñònh TTG Cho LÑQH TTG RT vaø G laø taäp caùc raøng buoäc oån ñònh TTG treân RT. Bao ñoùng cua G(kyù hieäu laø G+) goàm caùc raøng buoäc oån ñònh TTG ñöôïc suy daãn töø G baèng caùch aùp duïng luaät daãn Amstrong veà raøng buoäc oàn ñònh TTG. G+={X Y: X Yñöôïc suy dieãn töø caùc raøng buoäc oån ñònh TTG trong G} >− >− V.4 Bao ñoùng taäp thuoäc tính oån ñònh TTG: Cho LÑQH TTG RT vaø G laø taäp caùc raøng buoäc oån ñònh TTG treân RT, X ⊆RT Bao ñoùng cuûa taäp thuoäc tính X ñoái vôùi taäp G(Kyù hieäu: X+G) laø taäp hôïp: X+G={Y| X Y ∈G>− +} Thuaät toaùn tìm bao ñoùng taäp thuoäc tính oån ñònh TTG: )1( +iX Nhaäp: RT, X, G Xuaát: X+G Phöông phaùp: Laàn löôït tìm tuaàn töï X(0), X(1), X(2),. . . Böôùc 1: i:=0, X(i)=X Böôùc 2: tìm B={W: V W∈G, ∃V∈X>− (i) } Böôùc 3: X(i+1)= X(i) ∪ B Böôùc 4: Neáu X(i+1)≠X(i) thì i:=i+1, chuyeån veà böôùc 2. Böôùc 5: traû veà X(i) laø X+G Ta chöùng minh ñöôïc theo phöông phaùp treân: ∀Y∈ X+G thì X >− Y∈ G+ V.5 Khoaù cuûa taäp raøng buoäc oån ñònh TTG(kyù hieäu KT) NGUYEÃN THÒ LAN ANH Trang 27 Raøng buoäc oån ñònh TTG Cho G laø taäp raøng buoäc oån ñònh treân löôïc ñoà RT, X⊆RT ñöôïc goïi laø khoaù oån ñònh TTG cuûa RT neáu: • X+G=RT hay RT >− X+G • ¬∃X’⊂X: Y X’ vôùi Y⊂R>− T nhöng Y⊄X YÙ nghóa: nhöõng thuoäc tính trong cuøng khoaù oån ñònh TTG coù tính oån ñònh ngang nhau vaø oån ñònh hôn caùc thuoäc tính khoâng khoaù. Nhaän xeùt: töø ñònh nghóa ta thaáy raèng khoaù oån ñònh TTG laø duy nhaát vaø khoaù toái tieåu K laø taäp con cuûa khoùa oån ñònh TTG. V.6 Thuaät toaùn tìm khoaù oån ñònh TTG Nhaäp: löôïc ñoà quan heä TTG, RT, FT, G Trong ñoù: RT ={A1, A2, . . ., An, T}laø taäp caùc thuoäc tính trong ñoù coù moät thuoäc tính thôøi gian T. FT laø taäp caùc phuï thuoäc haøm TTG. G laø taäp caùc raøng buoäc oån ñònh TTG. Xuaát: Khoaù oån ñònh TTG KT. Nhaän xeùt: Trong quaù trình xeùt caùc phuï thuoäc haøm vaø caùc raøng buoäc oån ñònh TTG, ta luoân xeùt giaù trò cuûa caùc thuoäc tính gaén vôùi giaù trò thuoäc tính thôøi gian. Theá neân trong quaù trình tìm khoaù oån ñònh TTG KT ta khoâng xeùt thuoäc tính thôøi gian T vaøo khoaù. Phöông phaùp: Böôùc 1: döïa vaøo taäp FT tìm khoaù toái thieåu K cuûa löôïc ñoà RT. Böôùc 2: goïi G0 =G + ⎨X Y:X>− >− Y}-{X >− Y: X⊆K} Böôùc 3: laàn löôït tính caùc taäp thuoäc tính KT0, KT1,. . ., KTn, nhö sau: +− −− 01 }){( GiTiT AKR > KT0=RT\{T}(T: thuoäc tính thôøi gian) KTi= ⎩⎨ ⎧ − − − 1 1 }{ Ti iTi K AK ngöôïc laïi neáu RT >− (KTi-1-{Ai})+G0 i ={1, 2,. . ., n} NGUYEÃN THÒ LAN ANH Trang 28 Raøng buoäc oån ñònh TTG Cuoái cuøng ta coù KTn Böôùc 4: KT=KTn∪K laø moät khoaù oån ñònh TTG. Giaûi thích böôùc 2: Nhöõng thuoäc tính thuoäc khoaù toái thieåu K laø nhöõng thuoäc tính oån ñònh nhaát neân trong taäp caùc raøng buoäc G ta khoâng caàn phaûi xeùt nhöõng thuoäc tính ñoù baèng caùch loaïi ra nhöõng raøng buoäc oån ñònh coù veá traùi laø thuoäc tính khoaù toái thieåu K.(*) Tuy nhieân, neáu trong taäp thuoâc tính coù nhöõng thuoäc tính X oån ñònh ngang caáp vôùi caùc thuoäc tính thuoäc khoaù K, ñeå traùnh maát caùc raøng buoäc oån ñònh tröôùc thöïc hieän (*) ta theâm vaøo trong taäp raøng buoäc oån ñònh nhöõng raøng buoäc môùi X >− Y sao cho X >< − X’⊆K vaø X’ Y >− Ví duï: Cho RT={HoTen, GioiTinh, QuocGia, PhongBan, ChucVu, BacLuong, TG} FT={ , , , , , } GioiTinhHoTen T→ QuocGiaHoTen T→ PhongBanHoTen T→ ChucVuHoTen T→ BacLuongHoTen T→ TGHoTen T→ Cho G={K HoTen, HoTen>− >< − QuocGia, HoTen PhongBan, HoTen ChucVu, ChucVu>− >− >− BacLuong} Böôùc 1: tìm khoaù toái thieåu K cuûa löôïc ñoà RT. Xeùt: (HoTen)+FT=RT neân coù khoaù toái thieåu K={HoTen} Böôùc 2: goïi G0 =G + ⎨X Y:X>− >− Y}-{X >− Y: X⊆K} G0=G Theâm vaøo trong G0 raøng buoäc oån ñònh TTG: GioiTinh >− ChucVu, GioiTinh PhongBan, QuocGia>− >− ChucVu, QuocGia >− PhongBan. Loaïi ra khoûi G0 nhöõng raøng buoäc oån ñònh TTG: HoTen PhongBan, HoTen ChucVu. >− >− Vaäy taäp G0 sau böôùc 2 nhö sau: NGUYEÃN THÒ LAN ANH Trang 29 Raøng buoäc oån ñònh TTG G0= ={GioiTinh HoTen, QuocGia>− >− HoTen,GioiTinh PhongBan, GioiTinh ChucVu, QuocGia >− >− >− PhongBan, QuocGia >− ChucVu, ChucVu BacLuong} >− Böôùc 3: laàn löôït tính caùc taäp thuoäc tính KT0, KT1,. . ., KTn KT0=RT Xeùt (KT0 – {HoTen})+G0={HoTen, GioiTinh, QuocGia, PhongBan, ChucVu, BacLuong}=RT, khi ñoù KT1=KT0– {HoTen}={GioiTinh, QuocGia, PhongBan, ChucVu, BacLuong} Xeùt KT2=(KT1 – {GioiTinh})+G0) ={HoTen, QuocGia, PhongBan, ChucVu, BacLuong}≠RT, khi ñoù KT2=KT1. Xeùt KT3=(KT2 – {QuocGia})+G0) ={HoTen, GioiTinh, PhongBan, ChucVu, BacLuong}≠RT, khi ñoù KT3=KT2. Xeùt (KT3 – {PhongBan})+G0={HoTen, GioiTinh, QuocGia, PhongBan, ChucVu, BacLuong}=RT, khi ñoù KT4=KT3– {PhongBan}={GioiTinh, QuocGia, ChucVu, BacLuong} Xeùt (KT4 – {ChucVu})+G0={HoTen, GioiTinh, QuocGia, PhongBan, ChucVu, BacLuong}=RT, khi ñoù KT5=KT4– {ChucVu}={GioiTinh, QuocGia, BacLuong} Xeùt (KT5 – {BacLuong})+G0={HoTen, GioiTinh, QuocGia, PhongBan, ChucVu, BacLuong}=RT, khi ñoù KT6=KT5– {BacLuong}={GioiTinh, QuocGia} Ñeán ñaây böôùc 3 keát thuùc: KT6= GioiTinh, QuocGia} Böôùc 4: KT=KT6∪K ={HoTen, GioiTinh, QuocGia}laø moät khoaù oån ñònh TTG. V.7 Phaân raõ baûo toaøn thoâng tin TTG: Cho LÑQH TTG RT vaø phaân raõ ρT=(S1,S2,. . .Sp) cuûa RT. Ta goïi pheùp nhaân raõ ρ baûo toaøn thoâng tin TTG neáu vôùi moïi quan heä TTG rT treân RT thì: rT= )(1 TS rπ >< NGUYEÃN THÒ LAN ANH Trang 30 Raøng buoäc oån ñònh TTG V.8 Thuaät toaùn phaân raõ TTG: Cho löôïc ñoà RT, G laø taäp caùc raøng buoäc oån ñònh TTG treân RT vaø KT (hay KT= SK: Stability Key)laø khoaù oån ñònh TTG ñoái vôùi G. Goïi RT1=RT, SK1=SK vaø G1=G Goïi RT2=RT1 – SK1 vaø G2=∏RT2(G1)(laø pheùp chieáu cuûa G1 treân RT2) . . . Goïi RTp=RTp-1 – SKp-1 vaø Gp=∏RTp(Gp-1)(laø pheùp chieáu cuûa Gp-1 treân RTp) Ta ñöôïc taäp caùc thuoäc tính SK1, SK2,. . .,SKp Goïi: S1=(K∪SK1), S2=(K∪SK2),. . ., Sp=(K∪SKp) Keát quaû: ρT=(S1,S2,. . .Sp) laø phaân raõ cuûa RT Xeùt laïi ví duï treân: Cho RT={HoTen, GioiTinh, QuocGia, PhongBan, ChucVu, BacLuong, TG} FT={ , , , , } GioiTinhHoTen T→ QuocGiaHoTen T→ PhongBanHoTen T→ ChucVuHoTen T→ BacLuongHoTen T→ Cho G={K HoTen, HoTen>− >< − QuocGia, HoTen PhongBan, HoTen ChucVu, ChucVu>− >− >− BacLuong} Coù: RT1=RT, G1=G vaø SK1=SK={HoTen, GioiTinh, QuocGia} Goïi RT2=RT1 – SK1={PhongBan, ChucVu, BacLuong, TG} G2=∏RT2(G1)={ ChucVu BacLuong} >− KT0= RT2 Xeùt (KT0 – {PhongBan})+G2={ChucVu, BacLuong}}≠RT2, khi ñoù KT1=KT0 Xeùt (KT1 – {ChucVu})+G2) ={PhongBan, BacLuong}≠RT2, khi ñoù KT2=KT1. Xeùt (KT2 – {BacLuong})+G2) ={PhongBan, ChucVu, BacLuong}=RT2, NGUYEÃN THÒ LAN ANH Trang 31 Raøng buoäc oån ñònh TTG khi ñoù KT3=KT2 – {BacLuong}={PhongBan, ChucVu} SK2={PhongBan, ChucVu} RT3=RT2 – SK1={BacLuong, TG} SK3={BacLuong} Vaäy ta coù: S1={HoTen, GioiTinh, QuocGia} S2={HoTen, PhongBan, ChucVu} S3={HoTen, BacLuong} Ñònh lyù: cho LÑQH RT thoaû daïng chuaån 3TNF. Pheùp phaân raõ ρT=(S1,S2,. . .Sp) nhö treân laø baûo toaøn thoâng tin TTG.(Ñònh lyù treân ñaõ ñöôïc chöùng minh) NGUYEÃN THÒ LAN ANH Trang 32 Moâ taû phaàn caøi ñaët PHAÀN VI MOÂ TAÛ PHAÀN CAØI ÑAËT VI.1 Noäi dung caøi ñaët: • Cho pheùp nhaäp, söûa ñoåi, xoaù, löu taäp thuoäc tính RT • Cho pheùp nhaäp, söûa ñoåi, xoaù, löu taäp phuï thuoäc haøm TTG- FT • Cho pheùp nhaäp, söûa ñoåi, xoaù, löu taäp caùc raøng buoäc oån ñònh TTG- G • Tìm khoùa toái thieåu TTG- K • Tìm khoaù raøng buoäc oån ñònh TTG- KT • Phaân raõ baûo toaøn thoâng tin TTG VI.2 Ngoân ngöõ söû duïng trong chöông trình caøi ñaët: • Microsoft Visual Basic 6.0 • Microsoft Office Access 2003 VI.3 Döõ lieäu söû duïng trong chöông trình demo: RT={HoTen, GioiTinh, QuocGia, PhongBan, ChucVu, BacLuong, TG} NGUYEÃN THÒ LAN ANH Trang 33 Moâ taû phaàn caøi ñaët FT={ , , , , , } GioiTinhHoTen T→ QuocGiaHoTen T→ PhongBanHoTen T→ ChucVuHoTen T→ BacLuongHoTen T→ TGHoTen T→ G={K HoTen, HoTen GioiTinh, HoTen>− >< − QuocGia, HoTen PhongBan, HoTen ChucVu, ChucVu BacLuong} >− >− >− NGUYEÃN THÒ LAN ANH Trang 34 Moâ taû phaàn caøi ñaët Keát quaû sau khi chaïy chöông trình: Khoùa TTG K={Hoïteân} Khoùa raøng buoäc oån ñònh TTG KT={Hoïteân, Giôùitính, Quoácgia} NGUYEÃN THÒ LAN ANH Trang 35 Moâ taû phaàn caøi ñaët Vaø keát quaû phaân raõ TTG: S1={HoTen, GioiTinh, QuocGia} S2={HoTen, PhongBan, ChucVu} S3={HoTen, BacLuong} NGUYEÃN THÒ LAN ANH Trang 36 Toång Keát Veà Keát Quaû Ñeà Taøi Nghieân Cöùu Khoa Hoïc Caáp Tröôøng: Cô Sôû Döõ Lieäu Quan Heä Coù Tính Thôì Gian. Nhöõng muïc tieâu ñaõ thöïc hieän ñöôïc: Ñeà taøi ñaõ ñöa ra ñöôïc caùc khaùi nieäm - Caùc khaùi nieäm veà cô sôû döõ lieäu coù tính thôøi gian: löôïc ñoà quan heä coù tính thôùi gian vaø quan heä coù tính thôøi gian. - Caùc pheùp toaùn veà ñaïi soá quan heä treân CSDL coù tính thôøi gian. - Caùc khaùi nieäm veà phuï thuoäc haøm vaø caùc daïng chuaån coù tính thôøi gian. - Caùc raøng buoäc oån ñònh coù tính thôøi gian. - Phaân raõ baûo toaøn thoâng tin coù tính thôøi gian. Tieán haønh caøi ñaët moät chöông trình demo cho caùc noäi dung treân. Nhöõng muïc tieâu chöa thöïc hieän ñöôïc: - Caùc khaùi nieäm ñöa ra chöa hoaøn toaøn ñaày ñuû. - Phaàn chöông trình demo chöa thöû nghieäm treân CSDL coù tính thôì gian vôùi taäp thuoäc tính lôùn neân chöa ñaûm baûo hoaøn chính xaùc. Taøi lieäu tham khaûo: [1] Giaùo trình Cô Sôû Döõ Lieäu 1, Giaùo trình Cô Sôû Döõ Lieäu 2, Thaày Ñaëng Phöôùc Huy, Ñaïi Hoïc Ñaø Laït. [2] Tuyeån taäp Moät soá vaán ñeà choïn loïc cuûa Coâng Ngheä Thoâng Tin, Nha Trang, 5-7 thaùng 6 naêm 2002. [3] Chapter 29, Extending Existing Dependency Theory to Temporal Databases, Christian S. Jensen, Richard T. Snodgrass, and Michael D. Soo. [4] The Consensus Glossary of Temporal Database Concepts - February 1998 Version. ---------------------------***--------------------------