Tài liệu Một số phụ thuộc dữ liệu trong cơ sở dữ liệu dạng khối

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN TRỊNH ĐÌNH VINH MỘT SỐ PHỤ THUỘC DỮ LIỆU TRONG CƠ SỞ DỮ LIỆU DẠNG KHỐI LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2011 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN TRỊNH ĐÌNH VINH MỘT SỐ PHỤ THUỘC DỮ LIỆU TRONG CƠ SỞ DỮ LIỆU DẠNG KHỐI Chuyên ngành: BẢO ĐẢM TOÁN HỌC CHO MÁY TÍNH VÀ HỆ THỐNG TÍNH TOÁN Mã số: 62.46.35.01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. GS.TS. Vũ Đức Thi 2. PGS.TS. Nguyễn Kim Anh HÀ NỘI – 2011 2 Lêi c¶m ¬n ®Ó hoµn thµnh luËn ¸n nµy, t«i ®· nhËn ®−îc sù gióp ®ì rÊt tËn t×nh cña c¸c thÇy c« h−íng dÉn khoa häc, c¸c thÇy c« trong ViÖn CNTT vµ tr−êng §HSP Hµ Néi 2. T«i xin c¶m ¬n c¸c thÇy c« trong ViÖn CNTT vµ tr−êng §HSP Hµ Néi 2 ®· t¹o ®iÒu kiÖn häc tËp, nghiªn cøu, gióp ®ì t«i rÊt nhiÒu trong qu¸ tr×nh lµm luËn ¸n. §Æc biÖt t«i xin c¶m ¬n thÇy GS. TS. Vò §øc Thi, c« PGS.TS. NguyÔn Kim Anh ®· tËn t×nh h−íng dÉn, chØ b¶o cho t«i trong toµn bé qu¸ tr×nh häc tËp, nghiªn cøu ®Ò tµi vµ gióp t«i hoµn thµnh b¶n luËn ¸n nµy. TrÞnh §×nh Vinh 3 Lêi cam ®oan T«i xin cam ®oan ®©y lµ c«ng tr×nh nghiªn cøu cña t«i d−íi sù h−íng dÉn khoa häc cña c¸c thÇy c« GS.TS. Vò §øc Thi vµ PGS. TS. NguyÔn Kim Anh. C¸c sè liÖu, kÕt qu¶ nªu trong luËn ¸n lµ trung thùc vµ ch−a tõng ®−îc ai c«ng bè trong bÊt k× c«ng tr×nh nµo kh¸c. T¸c gi¶ luËn ¸n TrÞnh §×nh Vinh 4 môc lôc Trang Danh môc c¸c ký hiÖu vµ ch÷ viÕt t¾t ………………………………7 Danh môc b¶ng biÓu vµ h×nh vÏ …………………………………….8 Lêi më ®Çu …………………………………………………………....9 Ch−¬ng 1: M« h×nh c¬ së d÷ liÖu quan hÖ ………………………...13 1.1. C¸c kh¸i niÖm c¬ b¶n ……………………………………...13 1.1.1. Thuéc tÝnh vµ miÒn thuéc tÝnh ……………………13 1.1.2. Quan hÖ, l−îc ®å quan hÖ ………………………...13 1.1.3. Kho¸ cña quan hÖ ………………………………...14 1.2. C¸c phÐp to¸n ®¹i sè quan hÖ ……………………………...15 1.2.1. PhÐp hîp ………………………………………….15 1.2.2. PhÐp giao ………………………………………….15 1.2.3. PhÐp trõ …………………………………………...16 1.2.4. TÝch ®Ò c¸c ………………………………………...16 1.2.5. PhÐp chiÕu …………………………………………17 1.2.6. PhÐp chän …………………………………………17 1.2.7. PhÐp kÕt nèi ………………………………………..18 1.2.8. PhÐp chia …………………………………………..20 1.3. Phô thuéc hµm ……………………………………………..20 1.3.1. C¸c tÝnh chÊt cña phô thuéc hµm …………………21 1.3.2. HÖ tiªn ®Ò Armstrong vµ phÐp suy dÉn …..……….21 1.4. Bao ®ãng …………………………………………………...22 1.4.1. Bao ®ãng cña tËp phô thuéc hµm …………………22 1.4.2. Bao ®ãng cña tËp thuéc tÝnh ………………………22 1.4.3. Bµi to¸n thµnh viªn vµ thuËt to¸n t×m 5 bao ®ãng cña tËp thuéc tÝnh ………………………22 1.5. Khãa cña l−îc ®å quan hÖ ………………………………...24 1.6. Phñ cña tËp phô thuéc hµm ………………………………..26 1.7. Phñ tèi thiÓu cña tËp phô thuéc hµm ………………………26 1.7.1. Phô thuéc hµm cã vÕ tr¸i d− thõa …………………26 1.7.2. TËp phô thuéc hµm cã vÕ ph¶i gåm 1 thuéc tÝnh ….27 1.7.3. TËp phô thuéc hµm kh«ng d− thõa ……………….27 1.7.4. TËp phô thuéc hµm tèi thiÓu ………………………28 (Phñ tèi thiÓu cña tËp phô thuéc hµm) 1.8. C¸c d¹ng chuÈn cña l−îc ®å quan hÖ ………………………28 1.9. Phô thuéc ®a trÞ ……………………………………………30 1.9.1. §Þnh nghÜa phô thuéc ®a trÞ ………………………30 1.9.2. C¸c tÝnh chÊt cña phô thuéc ®a trÞ ………………..31 1.10. KÕt luËn ch−¬ng 1 ………………………………………..32 Ch−¬ng 2 : M« h×nh c¬ së d÷ liÖu d¹ng khèi …………………..33 2.1. Khèi, l−îc ®å khèi ………………………………................33 2.2. L¸t c¾t ...................................................................................34 2.3. Kho¸ cña khèi …………………………………………….35 2.4. §¹i sè quan hÖ trªn khèi …………………………………...37 2.4.1. PhÐp hîp …………………………………………..37 2.4.2. PhÐp giao ………………………………………….37 2.4.3. PhÐp trõ …………………………………………..37 2.4.4. TÝch §Ò C¸c ………………………………………38 2.4.5. TÝch §Ò C¸c theo tËp chØ sè ……………………….38 2.4.6. PhÐp chiÕu …………………………………………38 2.4.7. PhÐp chän …………………………………………39 2.4.8. PhÐp kÕt nèi ……………………………………….39 6 2.4.9. PhÐp chia ………………………………………….40 2.5. Phô thuéc hµm ……………………………………………41 2.6. Bao ®ãng cña tËp thuéc tÝnh chØ sè ………………………..43 2.7. Kho¸ cña l−îc ®å khèi R ®èi víi tËp c¸c phô thuéc hµm F trªn R ……………………………45 2. 8. D¹ng chuÈn cña khèi ……………………………………...46 2.9. Phñ cña tËp phô thuéc hµm ………………………………...48 2.10. KÕt luËn ch−¬ng 2 ………………………………………..50 Ch−¬ng 3: phô thuéc ®a trÞ, phô thuéc ®a trÞ xÊp xØ vµ α-phô thuéc hµm trong m« h×nh d÷ liÖu d¹ng khèi ……51 3.1. Phô thuéc ®a trÞ trong m« h×nh d÷ liÖu d¹ng khèi ………….51 3.2. C¸c tÝnh chÊt cña Phô thuéc ®a trÞ ………………………….53 3.3. Phô thuéc ®a trÞ xÊp xØ trong m« h×nh d÷ liÖu d¹ng khèi …..61 3.4. C¸c tÝnh chÊt cña phô thuéc ®a trÞ xÊp xØ …………………..63 3.5. α-Phô thuéc hµm vµ α-bao ®ãng trong m« h×nh d÷ liÖu d¹ng khèi ………………………………………….71 3.5.1. Kh¸i niÖm xÊp xØ møc α ………………………….71 3.5.2. α-phô thuéc hµm vµ α-bao ®ãng …………………..73 3.6. KÕt luËn ch−¬ng 3 ………………………………………….84 PhÇn kÕt luËn ………………………………………………………...85 Danh môc c«ng tr×nh c«ng bè cña t¸c gi¶ …………………………..87 Danh môc tµi liÖu tham kh¶o ………………………………………..88 7 danh môc c¸c ký hiÖu vµ c¸c ch÷ viÕt t¾t Trong luËn ¸n nµy dïng thèng nhÊt c¸c kÝ hiÖu vµ c¸c ch÷ viÕt t¾t sau: KÝ hiÖu ý nghÜa A, B, C thuéc tÝnh. X, Y, Z tËp thuéc tÝnh. XY X∪Y (hîp cña 2 tËp thuéc tÝnh X vµ Y). ABC [A, B, C] (tËp thuéc tÝnh gåm 3 phÇn tö A, B, C). Dom(A) miÒn gi¸ trÞ cña thuéc tÝnh A. r hoÆc r(R) khèi r trªn tËp R. x(i)= (x, Ai) c¸c thuéc tÝnh chØ sè cña l−îc ®å khèi (x∈ id, i= 1.. n). id(i) = {x(i)⎜x ∈ id } tËp c¸c thuéc tÝnh chØ sè cña l−îc ®å khèi. r sè phÇn tö cña khèi r. r' sè phÇn tö cña khèi con r’ cña khèi r. 8 danh môc c¸c b¶ng biÓu vµ c¸c h×nh vÏ B¶ng biÓu ý nghÜa B¶ng 1.1 BiÓu diÔn quan hÖ r………………………………..13 B¶ng 1.2 BiÓu diÔn c¸c quan hÖ r, s vµ r x s…………………16 B¶ng 3.1 Quan hÖ gÇn nhau trªn miÒn gi¸ trÞ cña A1………..74 H×nh vÏ ý nghÜa H×nh 2.1 BiÓu diÔn khèi nh©n viªn (NV(R))…..……………34 H×nh 2.2 BiÓu diÔn khèi Canbo……………………………..41 H×nh 3.1 BiÓu diÔn khèi Sinhviªn1………………………....52 H×nh 3.2 BiÓu diÔn khèi Sinhviªn2………………………....62 H×nh 3.3 BiÓu diÔn khèi Sinhviªn3………………………....74 9 Më ®Çu §Ó x©y dùng ®−îc mét hÖ thèng c¬ së d÷ liÖu tèt, ng−êi ta th−êng sö dông c¸c m« h×nh d÷ liÖu thÝch hîp. Mçi m« h×nh d÷ liÖu lµ mét hÖ h×nh thøc to¸n häc gåm cã hai phÇn: 1. Mét hÖ thèng kÝ hiÖu ®Ó m« t¶ d÷ liÖu. 2. Mét tËp hîp c¸c phÐp to¸n thao t¸c trªn d÷ liÖu ®ã. Tõ tr−íc ®Õn nay ®· cã mét sè lo¹i m« h×nh ®−îc sö dông trong c¸c hÖ thèng c¬ së d÷ liÖu nh−: m« h×nh thùc thÓ - liªn kÕt, m« h×nh m¹ng, m« h×nh ph©n cÊp, m« h×nh h−íng ®èi t−îng, m« h×nh d÷ liÖu datalog vµ m« h×nh quan hÖ. Trong sè c¸c m« h×nh nµy th× m« h×nh quan hÖ lµ mét trong nh÷ng m« h×nh ®−îc nhiÒu nhµ khoa häc quan t©m nghiªn cøu, khai th¸c øng dông v× nã ®−îc x©y dùng trªn mét c¬ së to¸n häc chÆt chÏ [8], [15], [16], [20], [23], [25]. Tuy nhiªn, do c¸c quan hÖ cã cÊu tróc ph¼ng (tuyÕn tÝnh) nªn m« h×nh nµy sÏ rÊt khã kh¨n khi biÓu diÔn c¸c d÷ liÖu cã tÝnh chÊt ®éng (phi tuyÕn). Trong nh÷ng n¨m gÇn ®©y, viÖc nghiªn cøu nh»m më réng m« h×nh quan hÖ ®−îc nhiÒu nhµ khoa häc quan t©m. Theo h−íng nghiªn cøu nµy ®· cã mét sè h−íng më réng m« h×nh quan hÖ ®−îc ®Ò xuÊt nghiªn cøu nh−: m« h×nh d÷ liÖu ®a chiÒu [2], [19], [26], [31]; khèi d÷ liÖu [17], [27], [28], [33]; kho d÷ liÖu [22], [29], [32]; m« h×nh d÷ liÖu d¹ng khèi [3], [4], [5], [6], [13], … Trong ®ã chóng t«i thÊy ë m« h×nh d÷ liÖu d¹ng khèi, c¸c khèi lµ kh¸i niÖm c¬ b¶n ®−îc më réng tõ c¸c quan hÖ trong m« h×nh quan hÖ, c¸c khèi nµy cã thÓ biÓu diÔn c¸c d÷ liÖu cã tÝnh chÊt ®éng (biÓu diÔn c¸c d÷ liÖu cã thuéc tÝnh thay ®æi theo thêi gian). VÝ dô: khi chóng ta dïng c¸c quan hÖ trong m« h×nh quan hÖ ®Ó t¹o c¬ së d÷ liÖu trong ch−¬ng tr×nh qu¶n lý l−¬ng cña c¸c c¸n bé trong mét c¬ quan th× mçi khi cËp nhËt l−¬ng míi cho c¸n bé ®−îc t¨ng l−¬ng nã sÏ lµm mÊt d÷ liÖu l−¬ng cò tr−íc ®ã. Do ®ã, khi ®Õn kú h¹n xÐt t¨ng l−¬ng cho c¸c c¸n bé 10 th× viÖc t×m kiÕm c¸c c¸n bé ®Õn kú h¹n t¨ng l−¬ng còng gÆp kh«ng Ýt khã kh¨n (bëi v× sÏ ph¶i t×m kiÕm c¸c c¸n bé ®· ®−îc t¨ng l−¬ng trong thêi gian 2 hoÆc 3 n¨m tr−íc tuú theo c¸n bé ®ã ë ng¹ch l−¬ng nµo). Tuy nhiªn, nÕu qu¶n lý l−¬ng b»ng khèi trong m« h×nh khèi th× nhê viÖc sö dông trôc id (cét chØ sè) lµm trôc thêi gian ®Ó l−u tr÷ d÷ liÖu l−¬ng theo tõng thêi ®iÓm th× chóng ta sÏ dÔ dµng ®−a ra c¸c c¸n bé ®Õn kú h¹n t¨ng l−¬ng trong c¬ quan ®ã. Mét vÝ dô kh¸c n÷a lµ khi muèn m« t¶ c¸c d÷ liÖu cña con tµu khi nã di chuyÓn vµo bÕn c¶ng (vËn tèc, kho¶ng c¸ch so víi bê, ®é s©u,…) th× nÕu ta dïng m« h×nh quan hÖ sÏ rÊt khã kh¨n trong viÖc m« t¶ c¸c d÷ liÖu trªn cña con tµu khi nã di chuyÓn dÇn vµo c¶ng. Nh−ng nÕu chóng ta dïng khèi trong m« h×nh khèi sÏ dÔ dµng biÓu diÔn ®−îc c¸c d÷ liÖu trªn cña con tµu trong qu¸ tr×nh chuyÓn ®éng b»ng c¸ch sö dông trôc id lµm trôc thêi gian, mçi bé gi¸ trÞ cña c¸c thuéc tÝnh chØ sè sÏ biÓu diÔn d÷ liÖu cña con tµu t¹i mét thêi ®iÓm nhÊt ®Þnh khi con tµu di chuyÓn vµo bê. Tuy nhiªn, trong m« h×nh khèi nµy còng cßn nhiÒu lo¹i phô thuéc d÷ liÖu ch−a ®−îc nghiªn cøu. V× vËy: Môc tiªu cña luËn ¸n lµ nghiªn cøu c¸c phô thuéc d÷ liÖu trong c¬ së d÷ liÖu, cô thÓ lµ tËp trung vµo nghiªn cøu c¸c phô thuéc d÷ liÖu trong m« h×nh d÷ liÖu d¹ng khèi nh»m ®Ó gãp phÇn bæ sung thªm vµo lý thuyÕt thiÕt kÕ m« h×nh d÷ liÖu d¹ng khèi. LuËn ¸n bao gåm: Lêi më ®Çu, ba ch−¬ng néi dung, phÇn kÕt luËn, danh môc c«ng tr×nh c«ng bè vµ tµi liÖu tham kh¶o. Ch−¬ng 1 tr×nh bµy c¸c kh¸i niÖm c¬ b¶n nhÊt vÒ m« h×nh quan hÖ. Tr×nh bµy c¸c phÐp to¸n ®¹i sè trªn m« h×nh quan hÖ, c¸c vÊn ®Ò vÒ phô thuéc hµm, kho¸, bao ®ãng, phñ cña tËp phô thuéc hµm còng ®−îc giíi thiÖu cïng c¸c tÝnh chÊt cña chóng. PhÇn cuèi ch−¬ng tr×nh bµy kh¸i niÖm vÒ phô thuéc ®a trÞ trong m« h×nh quan hÖ vµ c¸c tÝnh chÊt cña chóng [1], [7], [8], [15], [16], [20]. 11 C¸c kÕt qu¶ nghiªn cøu cña luËn ¸n ®−îc tr×nh bµy trong phÇn cuèi cña ch−¬ng 2 vµ toµn bé ch−¬ng 3. Ch−¬ng 2 giíi thiÖu tæng quan vÒ m« h×nh khèi: ®Þnh nghÜa khèi, l−îc ®å khèi, l¸t c¾t, phô thuéc hµm, c¸c d¹ng chuÈn trong khèi. C¸c phÐp to¸n ®¹i sè trªn khèi, kho¸ cña khèi, l−îc ®å khèi còng ®−îc giíi thiÖu [3], [4], [5], [6], [13]. Cuèi ch−¬ng 2 chóng t«i x©y dùng c¸c kh¸i niÖm míi vÒ: phñ, phñ kh«ng d− thõa, phñ tèi thiÓu cña tËp c¸c phô thuéc hµm trªn l−îc ®å khèi; c¸c tÝnh chÊt vÒ phñ, phñ tèi thiÓu cña tËp c¸c phô thuéc hµm; ®−a ra ®iÒu kiÖn cÇn vµ ®ñ cña mét phñ tèi thiÓu trong m« h×nh d¹ng khèi [12]. Ch−¬ng 3 tr×nh bµy kh¸i niÖm míi vÒ phô thuéc ®a trÞ trong m« h×nh d÷ liÖu d¹ng khèi; ph¸t biÓu vµ chøng minh c¸c tÝnh chÊt cña phô thuéc ®a trÞ trong m« h×nh d÷ liÖu khèi; ®−a ra tiªu chuÈn cÇn vµ ®ñ cña mét phô thuéc ®a trÞ trong m« h×nh nµy [14]. Kh¸i niÖm míi tiÕp theo ®−îc tr×nh bµy trong ch−¬ng nµy lµ kh¸i niÖm phô thuéc ®a trÞ xÊp xØ møc k gi÷a c¸c thuéc tÝnh chØ sè cña mét khèi trong m« h×nh d÷ liÖu d¹ng khèi. Trªn c¬ së ®ã, c¸c tÝnh chÊt cña phô thuéc ®a trÞ xÊp xØ, mèi liªn hÖ gi÷a phô thuéc ®a trÞ xÊp xØ trªn c¸c l¸t c¾t víi c¸c phô thuéc ®a trÞ xÊp xØ trªn khèi ®· ®−îc ph¸t biÓu vµ chøng minh [10]. Ch−¬ng nµy còng tr×nh bµy thªm mét kh¸i niÖm míi n÷a vÒ α-phô thuéc hµm; ph¸t biÓu vµ chøng minh c¸c tÝnh chÊt cña nã trong m« h×nh d÷ liÖu d¹ng khèi, ®iÒu kiÖn cÇn vµ ®ñ cña α-phô thuéc hµm theo quan ®iÓm tËp th« còng ®−îc ph¸t biÓu vµ chøng minh [9], [11]. Ngoµi ra ë ch−¬ng nµy cßn ph¸t biÓu vµ chøng minh ®iÒu kiÖn cÇn vµ ®ñ cña mét α-phô thuéc hµm tõ X vµo Y khi mµ X, Y cã d¹ng riªng; x©y dùng kh¸i niÖm míi vÒ α-bao ®ãng trong m« h×nh c¬ së d÷ liÖu d¹ng khèi, chøng minh ®iÒu kiÖn cÇn vµ ®ñ cña tËp α-bao ®ãng ®èi víi tËp c¸c phô thuéc 12 α hµm F h; x©y dùng thuËt to¸n tÝnh α-bao ®ãng cho c¸c tËp thuéc tÝnh chØ sè α ®èi víi F h [11]. Cuèi cïng, phÇn kÕt luËn nªu nh÷ng kÕt qu¶ luËn ¸n ®· ®¹t ®−îc vµ h−íng ph¸t triÓn tiÕp theo cña luËn ¸n. 13 Ch−¬ng 1: M« h×nh c¬ së d÷ liÖu quan hÖ 1. 1. C¸c kh¸i niÖm c¬ b¶n 1.1.1. Thuéc tÝnh vµ miÒn thuéc tÝnh §Þnh nghÜa 1.1 [7], [8] - Thuéc tÝnh lµ ®Æc tr−ng cña c¸c quan hÖ. - TËp tÊt c¶ c¸c gi¸ trÞ cã thÓ cã cña thuéc tÝnh Ai gäi lµ miÒn gi¸ trÞ cña thuéc tÝnh ®ã, ký hiÖu: Dom(Ai) hay viÕt t¾t lµ D A i . VÝ dô 1.1: Nhanvien(MaNV, Hoten, NgSinh, §chi) Dom(MaNV) = {char(4)} ; Dom(Hoten) = {char(3)} ; Dom(NgSinh) = {date} Dom(§chi) = {‘HN’, ‘HP’, ‘VP’, …}. ; 1.1.2. Quan hÖ, l−îc ®å quan hÖ §Þnh nghÜa 1.2 [7], [8] Cho U= {A1, A2, …, An} lµ mét tËp h÷u h¹n kh«ng rçng c¸c thuéc tÝnh. Mçi thuéc tÝnh Ai (i=1,2, …, n) cã miÒn gi¸ trÞ lµ D A i . Khi ®ã r lµ mét tËp c¸c bé {h1, h2, …, hm} ®−îc gäi lµ quan hÖ trªn U víi hj (j=1, 2, …, m) lµ mét hj: U → hµm: ∪ D Ai Ai∈U sao cho hj(Ai) ∈ D A i (i=1, 2, …, n). Ta cã thÓ xem mét quan hÖ nh− mét b¶ng, trong ®ã mçi hµng (phÇn tö) lµ mét bé vµ mçi cét t−¬ng øng víi mét thµnh phÇn gäi lµ thuéc tÝnh. BiÓu diÔn quan hÖ r thµnh b¶ng nh− sau: A1 A2 … An h1 h1(A1) h1(A2) … h1(An) h2 h2(A1) h2(A2) … h2(An) … … … … … hm hm(A1) hm(A2) … hm(An) B¶ng 1.1: BiÓu diÔn quan hÖ r. 14 VÝ dô 1.2: Nh©nviªn(MNV HOTEN NS DC PLV) No1 A 2/04/76 HN P1 No2 A 4/05/70 HN P1 No3 B 2/04/76 HP P2 Trong ®ã c¸c thuéc tÝnh lµ MNV: m· nh©n viªn; HOTEN: hä tªn; NS: ngµy sinh; DC: ®Þa chØ; PLV: phßng lµm viÖc. Bé gi¸ trÞ: (No1, A, 2/04/76, HN, P1) lµ mét bé. NÕu cã mét bé t = (d1, d2, d3, , dm) ∈ r, r x¸c ®Þnh trªn U, X ⊆ U th× t(X) (hoÆc t.X) ®−îc gäi lµ gi¸ trÞ cña tËp thuéc tÝnh X trªn bé t. §Þnh nghÜa 1.3 [7], [8] TËp tÊt c¶ c¸c thuéc tÝnh trong mét quan hÖ cïng víi mèi liªn hÖ gi÷a chóng ®−îc gäi lµ l−îc ®å quan hÖ. L−îc ®å quan hÖ R víi tËp thuéc tÝnh U={A1, A2, .., An} ®−îc viÕt lµ R(U) hoÆc R(A1, A2, .., An). 1.1.3. Kho¸ cña quan hÖ §Þnh nghÜa 1.4 [1],[7], [16] Kho¸ cña quan hÖ r x¸c ®Þnh trªn tËp thuéc U={A1, A2, .., An} lµ tËp con K ⊆ U sao cho bÊt kú hai bé kh¸c nhau t1, t2 ∈ r lu«n tho¶ t1(K) ≠ t2(K) vµ bÊt kú tËp con thùc sù K1 ⊂ K nµo ®ã ®Òu kh«ng cã tÝnh chÊt ®ã. TËp thuéc tÝnh K’ ®−îc gäi lµ siªu kho¸ nÕu K’ ⊇ K vµ K lµ mét kho¸ cña quan hÖ r. VÝ dô 1.3: Nh©nviªn(MNV HOTEN NS DC PLV) No1 A 2/04/76 HN P1 No2 A 4/05/70 HN P1 No3 B 2/04/76 HP P2 Ta cã thuéc tÝnh MNV lµ kho¸ cña quan hÖ. 15 1.2. C¸c phÐp to¸n ®¹i sè quan hÖ x PhÐp to¸n tËp hîp: hîp, giao, trõ, tÝch §Ò-c¸c. x PhÐp to¸n quan hÖ: chiÕu, chän, kÕt nèi, chia. §Þnh nghÜa 1.5 [1], [7],[16] Hai quan hÖ r vµ s ®−îc gäi lµ kh¶ hîp nÕu nh− hai quan hÖ nµy x¸c ®Þnh trªn cïng tËp thuéc tÝnh vµ c¸c thuéc tÝnh cïng tªn cã cïng miÒn gi¸ trÞ. 1.2.1. PhÐp hîp PhÐp hîp hai quan hÖ kh¶ hîp r vµ s, kÝ hiÖu lµ r ∪ s, lµ tËp tÊt c¶ c¸c bé thuéc r hoÆc thuéc s. Ta cã: t ∈ r ∨ t ∈s} r ∪ s = {t VÝ dô 1.4: r (A B C) a1 b1 c1 a2 b1 c2 a2 b2 c1 r∪s ; s (A (A B C) a1 b1 c1 a2 b1 c2 a2 b2 c1 a2 b2 c2 B C) a1 b1 c1 a2 b2 c2 1.2.2. PhÐp giao PhÐp giao cña hai quan hÖ kh¶ hîp r vµ s, kÝ hiÖu lµ r ∩s, lµ tËp tÊt c¶ c¸c bé thuéc c¶ hai quan hÖ r vµ s. Ta cã: r ∩ s = {t t ∈ r ∧ t ∈s} VÝ dô 1.5: tõ ®Þnh nghÜa cña r vµ s trong vÝ dô 1.4 ta cã: r ∩ s = (A a1 B C) b1 c1 16 1.2.3. PhÐp trõ PhÐp trõ cña hai quan hÖ kh¶ hîp r vµ s, kÝ hiÖu: r - s lµ tËp tÊt c¶ c¸c bé thuéc r nh−ng kh«ng thuéc s. Ta cã: r - s = {t t ∈ r ∧ t ∉ s} VÝ dô 1.6: tõ ®Þnh nghÜa cña r vµ s trong vÝ dô 1.4 ta cã: r-s= s-r= (A B C) a2 b1 c2 a2 b2 c1 (A B C) a2 b2 C2 1.2.4. TÝch §Ò-c¸c Cho quan hÖ r x¸c ®Þnh trªn tËp thuéc tÝnh {A1, A2, .., An} vµ quan hÖ s x¸c ®Þnh trªn tËp thuéc tÝnh {B1, B2, .., Bm}. TÝch §Ò-c¸c cña hai quan hÖ r vµ s kÝ hiÖu lµ r s, lµ tËp tÊt c¶ c¸c (m+n) - bé cã n thµnh phÇn ®Çu tiªn lµ mét bé thuéc r vµ m thµnh phÇn sau lµ mét bé thuéc s. Ta cã: r s = {t=(a1, a2, .., an, b1, b2, .., bm) (a1, a2, .., an)∈ r ∧ (b1 b2, .., bm)∈ s} VÝ dô 1.7: r r MASV MAMH DIEM 99001 CSDL 5.0 99001 CSDL 5.0 CSDL CO SO DU LIEU 99002 CTDL 2.0 99001 CSDL 5.0 FOX FOXPRO 99003 MANG 8.0 99002 CTDL 2.0 CSDL CO SO DU LIEU 99002 CTDL 2.0 FOX FOXPRO s MASV s MAMH DIEM MAMH TENMH MAMH TENMH 99003 MANG 8.0 CSDL CO SO DU LIEU CSDL CO SO DU LIEU 99003 MANG 8.0 FOX FOXPRO FOX FOXPRO B¶ng 1.2: BiÓu diÔn c¸c quan hÖ r, s vµ quan hÖ r s. 17 1.2.5. PhÐp chiÕu Cho r lµ mét quan hÖ n ng«i x¸c ®Þnh trªn tËp thuéc tÝnh U={A1, A2, .., An}, X lµ tËp con cña U. PhÐp chiÕu cña quan hÖ r trªn tËp thuéc tÝnh X, kÝ hiÖu lµ ΠX(r), lµ tËp c¸c bé cña r x¸c ®Þnh trªn tËp thuéc tÝnh X. Ta cã: ΠX(r) = {t.X ⎢t ∈ r }. PhÐp chiÕu thùc chÊt lµ phÐp to¸n gi÷ l¹i mét sè thuéc tÝnh cÇn thiÕt cña quan hÖ vµ lo¹i bá nh÷ng thuéc tÝnh kh«ng cÇn thiÕt. VÝ dô 1.8: r (A B C D) a 1 x 4 b 2 y 5 c 4 z 4 d 8 x 5 e 1 y 4 ΠD(r) (D) 4 5 ΠBD(r) = (B D) 1 4 2 5 4 4 8 5 1.2.6. PhÐp chän - PhÐp chän lµ phÐp to¸n läc lÊy ra mét tËp con c¸c bé cña quan hÖ ®· cho tho¶ m·n mét ®iÒu kiÖn x¸c ®Þnh. §iÒu kiÖn ®ã ®−îc gäi lµ ®iÒu kiÖn chän hay biÓu thøc chän. 18 - BiÓu thøc chän F ®−îc ®Þnh nghÜa lµ mét tæ hîp logic cña c¸c to¸n h¹ng, mçi to¸n h¹ng lµ mét phÐp so s¸nh ®¬n gi¶n gi÷a hai biÕn lµ hai thuéc tÝnh hoÆc gi÷a mét biÕn lµ mét thuéc tÝnh vµ mét gi¸ trÞ h»ng. BiÓu thøc chän F cho gi¸ trÞ ®óng hoÆc sai ®èi víi mçi bé ®· cho cña quan hÖ khi kiÓm tra riªng bé ®ã. - C¸c phÐp to¸n so s¸nh trong biÓu thøc F: >, <, =, ≥, ≠, ≤. - C¸c phÐp to¸n logic trong biÓu thøc F: ∧ (vµ), ∨ (hoÆc), ¬ (phñ ®Þnh). Cho r lµ mét quan hÖ vµ F lµ mét biÓu thøc logic trªn c¸c thuéc tÝnh cña r. PhÐp chän trªn quan hÖ r víi biÓu thøc chän F, kÝ hiÖu lµ δ F (r) , lµ tËp tÊt c¶ c¸c bé cña r tho¶ m·n F. Ta cã: δ F (r) = { t ⎮ t∈r ∧ F(t) = đúng}. VÝ dô 1.9: δ B≥ D (r ) (A B C D) 4 c 4 z 4 y 5 d 8 x 5 c 4 z 4 d 8 x 5 e 1 y 4 r (A B C D) a 1 x b 2 ; 1.2.7. PhÐp kÕt nèi Cho quan hÖ r x¸c ®Þnh trªn tËp thuéc tÝnh {A1, A2, .., An} vµ quan hÖ s x¸c ®Þnh trªn tËp thuéc tÝnh {B1, B2, .., Bm}. §Ó ®Þnh nghÜa phÐp kÕt nèi cña hai quan hÖ, tr−íc hÕt chóng ta lµm quen víi kh¸i niÖm ghÐp bé. Gi¶ sö cho hai bé u=(a1, a2, .., an) vµ v=(b1, b2, .., bm). PhÐp ghÐp bé u víi bé v, kÝ hiÖu (u,v), ®−îc ®Þnh nghÜa lµ: (u,v)=(a1, a2, .., an, b1, b2, .., bm). PhÐp kÕt nèi hai quan hÖ thùc chÊt lµ phÐp ghÐp c¸c cÆp bé cña hai quan hÖ tho¶ m·n mét ®iÒu kiÖn nµo ®ã trªn chóng. §iÒu kiÖn ®ã ®−îc gäi lµ ®iÒu kiÖn kÕt nèi hay biÓu thøc kÕt nèi. 19 BiÓu thøc kÕt nèi ®−îc ®Þnh nghÜa lµ phÐp héi cña c¸c to¸n h¹ng, mçi to¸n h¹ng lµ mét phÐp so s¸nh ®¬n gi¶n gi÷a mét thuéc tÝnh cña quan hÖ r vµ mét thuéc tÝnh cña quan hÖ s. PhÐp kÕt nèi cña quan hÖ r víi quan hÖ s víi biÓu thøc kÕt nèi F ®−îc s = {t = (u, v) u ∈ r ∧ v ∈ s ∧ F(t ) = ®óng}. ®Þnh nghÜa nh− sau: r F TÊt nhiªn ë ®©y cÇn gi¶ thiÕt r»ng c¸c phÐp so s¸nh cña c¸c cÆp thuéc tÝnh thuéc hai quan hÖ lµ cã nghÜa, hay mçi gi¸ trÞ cña thuéc tÝnh nµy cã thÓ so s¸nh ®−îc víi mçi gi¸ trÞ cña thuéc tÝnh kia. Trong tr−êng hîp phÐp so s¸nh lµ “=”, chóng ta gäi phÐp kÕt nèi ®ã lµ phÐp kÕt nèi b»ng. Tr−êng phÐp hîp kÕt nèi b»ng trªn c¸c thuéc tÝnh cïng tªn cña hai quan hÖ vµ sau khi kÕt nèi mét trong hai thuéc tÝnh cña phÐp so s¸nh “=” ®−îc lo¹i bá th«ng qua phÐp chiÕu th× phÐp kÕt nèi nµy ®−îc gäi lµ kÕt nèi tù nhiªn vµ sö dông kÝ hiÖu “ * ”. PhÐp kÕt nèi tù nhiªn cña hai quan hÖ cã thÓ r(U) * s(V) = {t.(U∪V) ⎜t.U ∈r ∧ t.V ∈s}. ®−îc ®Þnh nghÜa nh− sau: VÝ dô 1.10: r r s B>E (A B C D) a 1 x b 2 c s (E F) 4 2 a y 5 4 b 4 z 4 4 c d 8 x 5 e 1 y 4 A B C D E F c 4 z 4 2 a d 8 x 5 2 a d 8 x 5 4 b d 8 x 5 4 c