Tiểu luận Cơ sở dữ liệu nâng cao

A. Giíi thiÖu Ngµy nay, nh÷ng øng dông lµ ngµy cµng phøc t¹p, chóng yªu cÇu hç trî nh÷ng hÖ thèng phÇn mÒm th«ng minh, trong ®ã cã hÖ thèng qu¶n trÞ c¬ së d÷ liÖu. Ch¾c ch¾n trong t­¬ng lai, ®Ó ph¶n ¸nh thùc tÕ mét c¸ch trung thùc, nh÷ng hÖ thèng qu¶n trÞ c¬ së d÷ liÖu sÏ ph¶i qu¶n lý nh÷ng d÷ liÖu kh«ng hoµn thiÖn. Mét vµi c«ng tr×nh ®· ®­îc ®­a ra trong ph¹m vi cña nh÷ng gi¸ trÞ rçng, nh­ng kh«ng thÓ thiÕt kÕ mét ®¹i sè quan hÖ më réng hoµn thiÖn trong ng÷ c¶nh nµy, nghÜa lµ thiÕt kÕ mét m« h×nh mµ kÕt qu¶ bÊt kú phÐp to¸n nµo vÉn lµ mét quan hÖ cña m« h×nh. Ch¼ng h¹n nÕu ta cã mét kÕt nèi trong tr­êng hîp mét thuéc tÝnh kÕt nèi mang gi¸ trÞ kh«ng chÝnh x¸c, khi ®ã mét bé cña quan hÖ thø nhÊt cã thÓ ®­îc kÕt nèi víi nhiÒu bé cña quan hÖ thø hai vµ kÕt qu¶ trong c¸c bé kh¸c nhau lµ kh«ng ®éc lËp. Bµi viÕt nµy xem xÐt mét kh¶ n¨ng më réng m« h×nh quan hÖ d÷ liÖu trong ®ã nh÷ng gi¸ trÞ m¬ hå ®­îc cho phÐp vµ ®­îc biÓu diÔn nh­ lµ nh÷ng ®¹i diÖn (candidate) ph©n biÖt. Môc tiªu cña bµi viÕt lµ ®Ó chØ ra r»ng cã thÓ nghÜ ra mét hÖ thèng biÓu diÔn hîp lÖ ®èi víi mét tËp h÷u h¹n c¸c phÐp to¸n bao gåm phÐp chän, phÐp chiÕu, phÐp nèi trªn nh÷ng thuéc tÝnh mang gi¸ trÞ chÝnh x¸c vµ fk-join lµ mét lo¹i kÕt nèi ®Æc biÖt th­êng xuÊt hiÖn trong thùc tiÔn. Bµi viÕt nµy ®Ò cËp hai phÇn c¬ b¶n: M« h×nh n»m d­íi hÖ thèng biÓu diÔn vµ kh¶ n¨ng sö dông mét lo¹i phÐp to¸n kÕt nèi nµo ®ã trong sù hiÓn diÖn cña nh÷ng gi¸ trÞ m¬ hå. Néi dung bµi viÕt ®­îc chia lµm 3 phÇn. PhÇn 1: giíi thiÖu hai lo¹i yÕu tè chÝnh cã ¶nh h­ëng trªn m« h×nh. Mét mÆt chóng liªn quan ®Õn sù lùa chän c¬ chÕ cã thÓ ®Ó biÓu diÔn nh÷ng gi¸ trÞ m¬ hå vµ sù thÓ hiÖn cña mét c¬ së d÷ liÖu cã thÓ d­íi d¹ng cña nh÷ng c¬ së d÷ liÖu th«ng th­êng chØ chøa nh÷ng th«ng tin chÝnh x¸c vµ mÆt kh¸c sù thËt r»ng ®«i khi cÇn thiÕt ®Ó ®­a vµo sù ®¸nh gi¸ sù phô thuéc gi÷a nh÷ng gi¸ trÞ ®¹i diÖn lÊy tõ nh÷ng thuéc tÝnh kh¸c nhau. PhÇn 2: giíi thiÖu nh÷ng khÝa c¹nh chÝnh cña m« h×nh d÷ liÖu n»m d­íi hÖ thèng biÓu diÔn. ý t­ëng chÝnh lµ c«ng nhËn kh¶ n¨ng ph©n phèi trªn nh÷ng bé gi¸ trÞ mµ t­¬ng ®­¬ng víi mét cÊu tróc bao hµm quan hÖ lång nhau. PhÇn 3: tr×nh bµy ho¹t ®éng cña hai phÐp to¸n víi m« h×nh: phÐp chän vµ fk-join. B. Néi dung I/ Nh÷ng yÕu tè c¬ b¶n cña m« h×nh PhÇn nµy chØ ra hai yÕu tè chÝnh ¶nh h­ëng ®Õn m« h×nh. YÕu tè thø nhÊt liªn quan ®Õn biÓu diÔn cña nh÷ng gi¸ trÞ kh«ng chÝnh x¸c b»ng kh¶ n¨ng ph©n phèi vµ sù gi¶i thÝch cña nh÷ng c¬ së d÷ liÖu nh­ vËy d­íi d¹ng cña c¬ së d÷ liÖu chÝnh quy. YÕu tè thø hai ®ã lµ mét sè phÐp to¸n cã thÓ yªu cÇu biÓu diÔn mµ gi¸ trÞ ®¹i diÖn kh«ng ®éc lËp ®èi víi nh÷ng thuéc tÝnh kh¸c nhau. 1.1/ Nh÷ng gi¸ trÞ kh«ng chÝnh x¸c, kh¶ n¨ng ph©n phèi vµ worlds Lý thuyÕt kh¶ n¨ng cung cÊp mét m« h×nh thø tù cho sù kh«ng ch¾c ch¾n trong ®ã sù m¬ hå ®­îc biÓu diÔn bëi mét quan hÖ ®· m· hãa b»ng mét thø tù chung trªn nh÷ng t×nh huèng cã thÓ. C¬ chÕ nµy quan hÖ gÇn gòi víi lý thuyÕt tËp mê (fuzzy) v× ý t­ëng lµ g¸n gi¸ trÞ nhËn bëi mét biÕn nhê mét tËp fuzzy gäi lµ mét kh¶ n¨ng ph©n phèi. ChÝnh x¸c h¬n, mét kh¶ n¨ng ph©n phèi lµ mét ¸nh x¹ p tõ mét miÒn X ®· cho ®Õn mét kho¶ng ®¬n vÞ [0,1] vµ p(a) biÓu diÔn møc ®é cã thÓ cña biÕn. Sù tiªu chuÈn hãa ®iÒu kiÖn cho r»ng Ýt nhÊt mét gi¸ trÞ cña miÒn (a0) lµ hoµn toµn cã thÓ, nghÜa lµ p(a0)=1. ThiÕt lËp nµy phï hîp ®Ó ®­a vµo tÝnh to¸n sù biÓu diÔn kh«ng ch¾c ch¾n bëi nh÷ng to¸n h¹ng thuéc ng«n ng÷, ch¼ng h¹n nh­ lµ cao, lín, võa vµ v©n v©n. Khi miÒn lµ rêi r¹c, mét kh¶ n¨ng ph©n phèi ®­îc viÕt {p1/a1+p2/a2+...+pn/an} Trong ®ã ai lµ mét gi¸ trÞ ®¹i diÖn vµ pi t­¬ng øng ®é ®o kh¶ n¨ng cña nã. Mét ®é ®o kh¶ n¨ng P thuéc mét trong c¸c tr­êng hîp sau: P (Æ)=0 P(X)=1 P(AÈB)=max(P(A),P(B)). V× tÝnh chÊt kh«ng céng ®­îc cña m« h×nh, gi¸ trÞ cña P() kh«ng thÓ ®­îc suy ra tõ P(A) vµ ®é ®o thø hai N ®· ®­îc ®­a ra, N(A)=1-P(). C¸ch tiÕp cËn nµy ®­a ra mét khung thèng nhÊt ®Ó biÓu diÔn gi¸ trÞ ch¾c ch¾n, còng nh­ nh÷ng gi¸ trÞ m¬ hå, bao gåm c¶ “gi¸ trÞ rçng”. T­¬ng tù víi m« h×nh x¸c suÊt, nã cã thÓ ®­îc xem nh­ mét sù chän läc nh÷ng gi¸ trÞ ph©n biÖt vµ còng ®­îc gäi lµ or-sets. ChÝnh x¸c h¬n, mét or-set cã thÓ ®­îc m« h×nh nh­ lµ mét kh¶ n¨ng ph©n phèi trong ®ã bÊt kú ®¹i diÖn nµo còng lµ hoµn toµn cã thÓ. Mét thuËn lîi cña m« h×nh x¸c suÊt lµ kh¶ n¨ng cña nã ®Ó gi¶i quyÕt ®ång thêi víi gi¸ trÞ m¬ hå vµ nh÷ng truy vÊn mê víi cïng nh÷ng ­u tiªn ng÷ nghÜa. Mét c¬ së d÷ liÖu D chøa nh÷ng gi¸ trÞ ch­a biÕt tr­íc cã thÓ ®­îc hiÓu nh­ lµ mét tËp c¬ së d÷ liÖu th«ng th­êng D1,D2,...,Dp (ký hiÖu lµ rep(D)), mµ kh¶ n¨ng cña c¸c Di lµ kh¸c nhau. BÊt kú Di nµo thu ®­îc b»ng viÖc chän mét ®¹i diÖn trong mçi ph©n phèi kh¶ n¨ng xuÊt hiÖn ë trong D vµ mét trong nh÷ng c¬ së d÷ liÖu chÝnh quy Dk ®­îc cho ®Ó t­¬ng øng víi tr¹ng th¸i hiÖn thêi cña world. Møc ®é Ên ®Þnh cho mét world (Di) lµ gi¸ trÞ cùc tiÓu cña nh÷ng møc ®é kh¶ n¨ng ®èi víi mçi ®¹i diÖn ®· chän. Ch¼ng h¹n, quan hÖ emp d­íi ®©y trªn thuéc tÝnh #id, years vµ job emp: #id years job 1 {1/5+0.8/4+0.3/3} Cashier 2 {1/8+0.5/9} {1/salesman+0.6/cashier} 3 {1/4+0.8/5} salesman 4 2 salesman Cã thÓ ®­îc kÕt hîp víi kho¶ng chõng 24 (3*2*2*2) worlds cã thÓ. Nh÷ng sù lùa chän: 5 ®èi víi thuéc tÝnh years trong bé thø nhÊt; 8 ®èi víi thuéc tÝnh years vµ cashier ®èi víi thuéc tÝnh job trong bé thø 2; 5 ®èi víi thuéc tÝnh years trong bé thø 3. §iÒu nµy dÉn ®Õn mét world lµ 0.6 cã thÓ. Tõ ®ã ta nh»m vµo thiÕt kÕ mét hÖ thèng biÓu diÔn m¹nh, nã ph¶i cã kh¶ n¨ng “t×m thÊy nguån gèc” tÊt c¶ world cã thÓ bao gåm nh÷ng c¸i mµ trong ®ã mét sè bé v¾ng mÆt. §Ó ®¹t ®­îc môc ®Ých nµy, bÊt kú bé t cña mét quan hÖ cã thÓ ph¶i ®­îc cung cÊp mét møc ®é N cÇn thiÕt cho biÕt kho¶ng mµ ch¾c ch¾n r»ng t thuéc vµo quan hÖ ®· ®Ò cËp. N b»ng 1 khi ch­a cã phÇn tö nµo bÞ hñy bá. Khi N kh¸c 1, gi¸ trÞ cña nã cung cÊp ®Ó tÝnh to¸n møc ®é kh¶ n¨ng (1-N) g¾n víi sù lùa chän cña mét world n¬i bé v¾ng mÆt. Ta minh häa ®iÒu nµy b»ng vÝ dô cña quan hÖ tr­íc víi sù lùa chän job=’salesman’. Râ rµng, bé thø nhÊt lµ kh«ng ®ñ tiªu chuÈn, tr¸i l¹i hai bé cuèi cïng lµ ®ñ tiªu chuÈn. §Ó cã mét sù biÓu diÔn ®¸ng tin cËy trong nghÜa cña mét hÖ thèng biÓu diÔn m¹nh, cÇn ph¶i gi÷ l¹i bé thø hai v× nã vÉn tháa m·n ®iÒu kiÖn mÆc dï kh«ng ch¾c ch¾n. Tr­êng hîp nµy, ta cã quan hÖ kÕt qu¶ nh­ sau: salesmen #id years job N 2 {1/8+0.5/9} Salesmen 0.4 3 {1/4+0.8/5} Salesmen 1 4 2 Salesmen 1 Qua ®ã ta thÊy cã thÓ bé ®Çu tiªn bÞ thiÕu v¾ng trong world nµo ®ã. Ch¼ng h¹n word: #id years job 3 5 Salesmen 4 2 Salesmen lµ cã thÓ ë møc ®é: min(0.6, 0.8, 1)=0.6 vµ nã phï hîp víi sù lùa chän cña gi¸ trÞ ‘cashier’ ë trong quan hÖ ban ®Çu emp. 1.2/ Sù phô thuéc cña nh÷ng gi¸ trÞ ®¹i diÖn M« h×nh cã thÓ chÝnh quy ®Òu ®­îc dùa trªn nh÷ng thuéc tÝnh cã thÓ nhËn nh÷ng gi¸ trÞ lµ kh¶ n¨ng ph©n phèi. Râ rµng, víi mét m« h×nh tr¹ng th¸i nh­ vËy, nh÷ng gi¸ trÞ ®¹i diÖn xuÊt hiÖn trong nh÷ng thuéc tÝnh kh¸c biÖt cña mét bé ®· cho lµ ®éc lËp. Ch¼ng h¹n, trong bé: kh«ng cã sù rµng buéc kÕt nèi nh÷ng lùa chän cña mét sè cña thuéc tÝnh years vµ mét job. Tr­êng hîp nµy hiÕm khi x¶y ra. Trong thùc tÕ, ®«i khi cÇn biÓu diÔn mµ bªn trong mét bé ®· cho cã mét sè gi¸ trÞ ®¹i diÖn xuÊt hiÖn tõ nh÷ng thuéc tÝnh kh¸c nhau bÞ rµng buéc víi nhau. §Ó minh häa, ta ®Þnh nghÜa mét quan hÖ emp trªn nh÷ng thuéc tÝnh name, years, job, l-city and b-city, hai thuéc tÝnh l-city vµ b-city m« t¶ thµnh phè ®ang sèng vµ thµnh phè n¬i sinh cña mét nh©n c«ng. Sau ®ã xÐt phÐp to¸n lùa chän trªn quan hÖ nµy víi ®iÒu kiÖn l-cityb-city. Sù biÓu diÔn cña tÊt c¶ worlds cã thÓ lµm cho nã cÇn thiÕt ®Ó hiÖn lªn nh÷ng cÆp ®¹i diÖn mµ tháa m·n ®iÒu kiÖn. Ch¼ng h¹n, víi bé: , ba cÆp cã thÓ chÊp nhËn ®­îc cña thµnh phè lµ: 0.7/(Paris,Marseille), 1/( Paris,Nice) vµ 0.4/(Nice,Marseille). Râ rµng víi mét t×nh huèng nh­ vËy kh«ng thÓ ®­îc biÓu diÔn mét tËp hîp c¸c gi¸ trÞ ®¹i diÖn ®éc lËp trªn l-city vµ b-city. §iÒu ®ã lµ cÇn thiÕt ®Ó më réng m« h×nh sao cho ®¹t ®­îc yªu cÇu nµy. II/ Tæng quan cña m« h×nh cã thÓ më réng. Nh­ ®· ®­îc nªu ra, cã mét sù cÇn thiÕt khi biÓu diÔn mµ bªn trong mét bé ®· cho cã mét vµi gi¸ trÞ ®¹i diÖn xuÊt hiÖn tõ nh÷ng thuéc tÝnh kh¸c nhau vµ bÞ rµng buéc víi nhau. ý t­ëng lµ ph¶i c¶i tiÕn m« h×nh do ®ã mét sè gi¸ trÞ thuéc tÝnh cã thÓ ph©n phèi trªn nhiÒu miÒn h¬n trªn mét miÒn nguyªn tö (ë ®©y ta h¹n chÕ vµo nh÷ng thuéc tÝnh cã miÒn rêi r¹c). Nãi c¸ch kh¸c, mét sè ®¹i diÖn lµ nh÷ng bé ®­îc ph×nh ra vµ m« h×nh ®­îc dùa trªn kh¸i niÖm quan hÖ lång nhau. M« h×nh ®­îc ®­a ra ë ®©y nh»m h¹n chÕ sè l­îng møc lång nhau ®Ó ®­îc mét d¹ng ®¬n. Trong phÇn cßn l¹i, hÖ thèng ký hiÖu R(A1,..., Am, X1(Ap,...,Aq), ..., Xn(Ak,...,Al)) thay thÕ cho mét l­îc ®å trong ®ã A1 ®Õn Am lµ thuéc tÝnh c¬ së mµ gi¸ trÞ lµ hoÆc lµ chÝnh x¸c hoÆc lµ kh¶ n¨ng ph©n phèi vµ Xi(Ah,...,Aj) biÓu diÔn mét thuéc tÝnh “cã cÊu tróc” mµ gi¸ trÞ cña nã lµ kh¶ n¨ng ph©n phèi trªn c¸c bé ®­îc x©y dùng trªn c¸c thuéc tÝnh tõ Ah ®Õn Aj . ThËt vËy, mét thuéc tÝnh c¬ së cã thÓ ®­îc xem nh­ mét tr­êng hîp ®Æc biÖt cña thuéc tÝnh cÊu tróc trong ®ã sè l­îng cña quan hÖ lång nhau lµ 1. Râ rµng nh÷ng quan hÖ nh­ vËy cã sù thÓ hiÖn d­íi d¹ng world khi nã lµ tr­êng hîp cña quan hÖ cã kh¶ n¨ng th«ng th­êng. ThËt vËy, khi mét c¸i chuyÓn vµo mét world ®· cho, l­îc ®å trë thµnh kh«ng lång nhau, v× mét gi¸ trÞ ®¹i diÖn cÊu tróc cã thÓ ®­îc chia thµnh nh÷ng gi¸ trÞ nguyªn tö. §èi víi mèi quan hÖ gi÷a quan hÖ kh¶ n¨ng th«ng th­êng vµ quan hÖ ®· më réng, ta thÊy r»ng, tõ mét quan hÖ kh¶ n¨ng th«ng th­êng cã thÓ x©y dùng mét quan hÖ më réng t­¬ng ®­¬ng bao hµm mét sè l­îng quan hÖ lång nhau. Ch¼ng h¹n, l­îc ®å R(A,B,C,D) cã thÓ ®­îc biÓu diÔn lµ R1(A,X(B,C),D), nh­ng còng cã thÓ lµ R2(X(A,B,C),D) hoÆc thËm chÝ R3(X(A,B,C,D)). Tuy nhiªn, ®¶o l¹i nãi chung lµ kh«ng kh¶ thi v× nh÷ng lý do ®· ®Ò cËp ë trong phÇn 1. §iÒu thó vÞ lµ sù t­¬ng ®­¬ng cña tÊt c¶ nh÷ng biÓu diÔn nµy d­íi d¹ng world vµ tÝnh chÊt nµy sÏ ®­îc vËn dông ë phÇn tiÕp theo trong ®ã nã ®­îc dïng nh­ lµ c¬ së ®Ó ®Þnh nghÜa phÐp chän vµ kÕt nèi. Nh­ vËy, râ rµng R(A,B,C,D) lµ thÝch hîp nhÊt v× nh÷ng quan hÖ lång nhau t­¬ng ®­¬ng bao hµm tÝch §Ò-c¸c yªu cÇu kh«ng gian nhiÒu h¬n. Tõ mét quan ®iÓm cô thÓ, ta nhÊn m¹nh nh÷ng quan hÖ ban ®Çu gi÷ nguyªn quan hÖ kh¶ n¨ng th«ng th­êng vµ m« h×nh më réng ®ã ®­îc dïng trong suèt qu¸ tr×nh tÝnh to¸n ®Ó biÓu diÔn ®óng kÕt qu¶ cña thao t¸c trung gian bao gåm c¶ kÕt qu¶ cuèi cïng. Theo m« h×nh nµy, gi¶ sö cã l­îc ®å quan hÖ R(ss#,date,X(car-t,brand)) m« t¶ kiÓu (car-t) vµ nh·n (brand) cña nh÷ng xe « t« ®­îc mua t¹i mét ngµy (date) nµo ®ã bëi mét ng­êi (ss#) ®Ó biÓu diÔn mét vµi kÕt qu¶ trung gian. Mét më réng cã thÓ cña mét quan hÖ r(R) lµ: r ss# date X Car-t Brand P N 1 d1 camry Toyota 1 1 2 d3 camry taurus avensis Toyota Ford Toyota 1 0.7 0.4 1 Tªn vµ nh·n cña nh÷ng xe « t« ®­îc biÓu diÔn nh­ nh÷ng cÆp ®¹i diÖn cã rµng buéc víi nhau. ë ®©y, trong bé thø nhÊt chØ cã mét ®¹i diÖn vµ trong bé thø hai cã 3 phÇn tö trong quan hÖ lång nhau trªn l­îc ®å X(car-t, brand). BiÓu diÔn t­¬ng ®­¬ng ®­îc thÓ hiÖn nh­ sau: r ss# date X Car-t Brand N 1 d1 {1/} 1 2 d3 {1/+0.7/+0.4/ 1 NÕu gi¸ trÞ ®¹i diÖn thø hai ®­îc chän ë trong bé thø hai, ta lÊy quan hÖ , lµ mét phÇn cña world mµ kh¶ n¨ng nhiÒu nhÊt lµ 0.7. III/ Nh÷ng phÐp to¸n cña m« h×nh PhÇn nµy, tËp trung vµo hai phÐp to¸n mµ ho¹t ®éng trong ng÷ c¶nh cña hÖ thèng biÓu diÔn, nghÜa lµ nh÷ng phÐp to¸n tháa m·n nguyªn t¾c: rep(Q(D))= Q(rep(D)). Nãi c¸ch kh¸c, kÕt qu¶ cña truy vÊn Q ®· xö lý trªn c¬ së d÷ liÖu ‘compact’ D lµ gièng nh­ truy vÊn Q trªn tËp hîp cña c¬ së d÷ liÖu chÝnh quy xuÊt ph¸t tõ D. 3.1/ PhÐp chän (Selection) §èi víi phÐp chän, cã hai vÊn ®Ò cÇn gi¶i quyÕt. Thø nhÊt, gi÷ l¹i trong quan hÖ kÕt qu¶ nh÷ng gi¸ trÞ phÇn tö tháa m·n tiªu chuÈn lùa chän. §iÒu nµy ®­îc gi¶i quyÕt kh¸ dÔ dµng, v× chØ cÇn söa ®æi gi¸ trÞ ®­îc xem lµ kh«ng chÝnh x¸c vµ gi÷ l¹i phÇn tö mµ tháa m·n ®iÒu kiÖn, sau ®ã söa ®æi møc ®é cÇn thiÕt (N) ®· g¸n cho bé, tïy thuéc vµo møc ®é cña phÇn tö ®· bÞ lo¹i bá. Thø hai, ®­a vµo tiªu chuÈn ®¸nh gi¸ mµ thiÕt lËp mét sù phô thuéc gi÷a nh÷ng thuéc tÝnh. ë ®©y, cã hai tr­êng hîp trong ®ã mét phÐp to¸n lùa chän cã thÓ dÉn ®Õn mét quan hÖ kÕt qu¶ mµ l­îc ®å cña nã bao hµm mét quan hÖ lång nhau. Tr­êng hîp thø nhÊt liªn quan ®Õn tiªu chuÈn lùa chän nguyªn tö lµm tõ hai thuéc tÝnh, nghÜa lµ cã d¹ng “Ai q Ak” trong ®ã q lµ mét to¸n tö so s¸nh, ë ®©y l­îc ®å quan hÖ kÕt qu¶ bao hµm quan hÖ lång nhau X(Ai,Ak) ®Ó biÓu diÔn sù phô thuéc gi÷a nh÷ng gi¸ trÞ c¸c phÇn tö mét mÆt tõ Ai mÆt kh¸c tõ Ak. Trong tr­êng hîp nµy, gi¶ sö r»ng quan hÖ ®Çu vµo r lµ l­îc ®å kh«ng lång nhau R(A1,...,An), ta cã: SEL(r, Ai q Ak)={N’/}| $t=N/ and (tÎr) and (ai,p q ak,l) and aj={lj,l/aj,l + ... + lj,nj/aj,nj} and N’=min(N,1-supp,l | not()min(li,plk.l))} Tr­êng hîp thø hai lµ khi ®iÒu kiÖn ®­îc ghÐp tõ nh÷ng ®iÒu kiÖn s¬ cÊp rêi r¹c cã d¹ng: ci(Ai) or ... or ck(Ak) trong ®ã cj lµ mét ®iÒu kiÖn nguyªn tö cã d¹ng “Aj q value” víi q lµ mét to¸n tö so s¸nh. Khi ®ã, kÕt qu¶ cña phÐp lùa chän lµ mét quan hÖ mµ l­îc ®å cña nã bao hµm c¶ quan hÖ lång nhau X(Ai,...,Ak). Ta minh häa ®iÒu nµy víi l­îc ®å quan hÖ PUR(ss#,date,car-t,l-city,p-city) miªu t¶ kiÓu (car-t) cña xe cars ®· mua t¹i mét ngµy nµo ®ã trong mét thµnh phè (p-city) bëi mét ng­êi (ss#) sèng ë trong thµnh phè (l-city). Truy vÊn t×m kiÕm ®èi víi nh÷ng ng­êi ®ã mµ ®· mua xe ë ngoµi thµnh phè hä sèng hoÆc ng­êi ®· mua mét chiÕc Avensis hoÆc mét chiÕc Taurus, lµ mét phÐp chän ((car-t Î {avensis,taurus}) or (p-cityl-city)). Víi p(PUR) p ss# date car-t l-city p-city 1 d1 taurus {1/antibes+0.3/nice} nice 1 d2 jeep paris {1/paris+0.5/nice} 2 {1/d3 +1/d4} {0.5/vensis+ 1/camry} {0.4/madrid+ 1/granada} madrid Ta thu ®­îc kÕt qu¶: ss# date X car-t l-city p-city N 1 d1 {1/+0.3/} 1 1 d2 {0.5/} 0 2 {1/d3 +1/d4} {1/+0.4+0.5/} 0.6 Gi¸ trÞ cña N trong bé cuèi cïng lµ (0.6) biÓu diÔn phÇn tö cã thÓ nhÊt mµ kh«ng tháa m·n ®iÒu kiÖn cã møc ®é 0.4 (t­¬ng øng víi sù lùa chän trong p). Trªn thùc tÕ, kÕt qu¶ cña phÐp lùa chän cã thÓ ®­îc xem nh­ mét sù h¹n chÕ cña nh÷ng phÇn tö sinh ra tõ tÝch §Ò-c¸c cña nh÷ng phÇn tö ban ®Çu trªn nh÷ng thuéc tÝnh liªn quan sang nh÷ng phÇn tö kia mµ tháa m·n ®iÒu kiÖn. VËy th×, tÝnh chÊt mong muèn ®èi víi world ®· ®¹t ®­îc. 3.2/ Foreign key join (kÕt nèi khãa ngoµi) To¸n tö nµy ®­îc dïng trong nh÷ng truy vÊn trªn mét quan hÖ chÝnh quy s trªn l­îc ®å S(X,Y) m« t¶ mét hµm chÝnh x¸c gi÷a nh÷ng tËp hîp c¸c thuéc tÝnh X vµ Y vµ mét quan hÖ cã thÓ r mµ l­îc ®å cña nã lµ R(X,Z) trong ®ã X vµ Z cã thÓ nhËn gi¸ trÞ kh«ng ch¾c ch¾n. Theo [3], mét tr­êng hîp nh­ vËy ®­îc liªn kÕt víi kh¸i niÖm cña mét phô thuéc hµm. ThËt vËy, quan hÖ r vµ s xuÊt ph¸t tõ sù ph©n t¸ch cña mét quan hÖ ban ®Çu (lÊy l¹i X,Y vµ Z) nh»m giíi h¹n cña sù d­ thõa. PhÐp nèi ®Æc biÖt nµy ®­îc gäi lµ foreign key join (fk-join), lµ mét equi-join mµ nh»m t×m cña mét gi¸ trÞ thuéc tÝnh kÕt nèi th«ng qua hµm. Mçi bé cña kÕt qu¶ cã thÓ ®­îc xem nh­ lµ mét hoµn thµnh cña mét bé cña r nhê th«ng tin cña hµm kÕt nèi X vµ Y-nh÷ng gi¸ trÞ cô thÓ ë trong s. §iÒu ®¸ng nãi lµ nh÷ng gi¸ trÞ ®ang xuÊt hiÖn trong ph©n phèi ®èi víi X trong mét bé kÕt qu¶ phï hîp víi nh÷ng phÇn tö ®ã mµ cã mét ¶nh ë trong s. B»ng viÖc x©y dùng, phÐp to¸n nµy m« t¶ mét kÕt nèi gi÷a hai gi¸ trÞ X vµ Y (®èi vµ ¶nh) vµ cÇn ph¶i duy tr× nã trong kÕt qu¶ ®Ó tho¶ m·n ®iÒu kiÖn cÇn thiÕt cña mét hÖ thèng biÓu diÔn m¹nh. Theo m« h×nh ®· giíi thiÖu trong phÇn 2, kü thuËt quan hÖ lång nhau ®­îc dïng ®Ó ®¹t ®­îc môc ®Ých nµy. NÕu ta b¾t ®Çu víi quan hÖ cã thÓ r vµ quan hÖ chÝnh quy (function) s mµ l­îc ®å t­¬ng øng cña nã lµ R(A1,...,Am,B1,...Bq) vµ S(A1,...,Am,C), fk-join ®­îc ®Þnh nghÜa lµ: fk-join(r,s,{ A1,...,Am}) = {N’/ + ...}, c, b1,..., bq> | $ t=N/ and $ u= and (t Î r) and (u Î s) and ai={} and "j Î[1,m], Î scv(ai) and N’=min(N,1-min())} trong ®ã scv(ai) lµ tËp hîp c¸c gi¸ trÞ phÇn tö xuÊt hiÖn trong ai. Nãi c¸ch kh¸c, mét t×m kiÕm ¶nh ë trong s cña mçi gi¸ trÞ phÇn tö trªn nh÷ng thuéc tÝnh A1,...,Am cña mét bé t cña quan hÖ r. NÕu ta sö dông l­îc ®å R(A,B,C) vµ S(A,B,D) vµ nh÷ng më réng: r A B C {1/a1+1/a2+0.7/a3} {1/b1+0.3/b2} c1 {1/a1+0.3/a4} b2 c2 s A B D a1 b1 d1 a1 b2 d2 a2 b1 d3 a3 b2 d2 KÕt qu¶ cña phÐp fk-join(r,s,{A,B}) lµ: X A B D C N {1/+0.3/+1/+0.3/} c1 0.3 {1/} c2 0.7 Nh­ vËy bÊt cø quan hÖ cã thÓ r (kh«ng lång nhau) cã mét sù biÓu diÔn t­¬ng ®­¬ng bao hµm mét quan hÖ lång nhau. Khi ®ã, nh÷ng yÕu tè nguyªn tö ®­îc gi÷ l¹i trong quan hÖ kÕt qu¶ chØ lµ nh÷ng c¸i cã sù phï hîp. Còng t­¬ng tù nh­ phÐp chän, nÕu mét thuéc tÝnh thuéc vÒ nh÷ng c¸i mµ ®­îc bao hµm trong ®iÒu kiÖn kÕt nèi lµ mét phÇn cña quan hÖ lång nhau trong r, toµn bé l­îc ®å cña quan hÖ lång nhau nµy ®­îc s¸t nhËp trong quan hÖ kÕt qu¶. C. KÕt luËn Bµi viÕt nµy ®· ®­a ra më réng cña m« h×nh quan hÖ kh¶ n¨ng cña d÷ liÖu ®­îc t×m ra tr­íc ®©y bëi Prade vµ Testemale. §Æc ®iÓm chÝnh cña nã n»m trong sù ®­a vµo møc ®¬n quan hÖ lång nhau bªn trong c¸c l­îc ®å, c¸i mµ dÉn ®Õn nh÷ng gi¸ trÞ thuéc tÝnh ph©n phèi kh¶ n¨ng trªn tÝch §Ò-c¸c cña miÒn nguyªn tö. Mét m« h×nh nh­ vËy ®­a ra mét sè thuËn lîi quan träng ®èi víi quan hÖ ban ®Çu. §Æc biÖt, nã thiÕt lËp mét hÖ thèng biÓu diÔn chÆt chÏ cho phÐp to¸n lùa chän (víi mét ph¹m vi réng cña tiªu chuÈn), fk-join (bao gåm c¶ tr­êng hîp thuéc tÝnh phøc t¹p), phÐp chiÕu vµ kÕt nèi tù nhiªn. Bµi viÕt nµy cßn ph¶i ®­îc tiÕp tôc nghiªn cøu theo c¸c h­íng nh­: i/ ph©n phèi kh¶ n¨ng trªn mét miÒn liªn tôc vµ ii/ sù phøc t¹p cña truy vÊn ®­îc göi ®Õn c¬ së d÷ liÖu trong mét ng÷ c¶nh cña mét m« h×nh míi. Râ rµng c¸ch dïng nh÷ng quan hÖ lång nhau g©y ra nhiÒu thao t¸c mµ tèn kÐm nhiÒu h¬n nh÷ng thùc hiÖn ®ã ë trªn quan hÖ kh¶ n¨ng chÝnh quy vµ sÏ lµ h÷u Ých ®Ó nhËn biÕt nh÷ng truy vÊn ®èi víi c¸i mµ kü thuËt lång nhau cã thÓ bÞ bá qua mµ kh«ng ¶nh h­ëng sù chÝnh x¸c cña c©u tr¶ lêi cuèi cïng. H¬n n÷a, ®iÒu quan t©m lµ bæ sung mét hÖ thèng qu¶n lý th«ng tin kh«ng chÝnh x¸c vµ ®­a ra nhiÒu kh¶ n¨ng thao t¸c trong bµi viÕt nµy. Lêi kÕt: §Ó hoµn thµnh ®­îc ®Ò tµi nµy, ngoµi sù nç lùc vµ cè g¾ng cña b¶n th©n, t¸c gi¶ ®· nhËn ®­îc sù gióp ®ì qóy b¸u cña Quý ThÇy, GS.TS. Lª M¹nh Th¹nh. Lµ mét häc viªn chuyªn ngµnh Tin häc vµ dï rÊt t©m ®¾c víi ®Ò tµi ®ang nghiªn cøu nh­ng víi thêi gian cã h¹n vµ khèi l­îng kiÕn thøc cña b¶n th©n cßn Ýt ái nªn ch¾c ch¾n tiÓu luËn kh«ng tr¸nh khái nh÷ng h¹n chÕ trong viÖc tiÕp cËn, nghiªn cøu vµ tr×nh bµy. T¸c gi¶ xin kÝnh träng c¶m ¬n sù gióp ®ì quý b¸u cña Quý ThÇy vµ mong ®­îc ®ãn nhËn tõ Quý ThÇy sù gãp ý ®Ó gióp t¸c gi¶ cã ®­îc hiÓu biÕt ®óng h¬n ®èi víi vÊn ®Ò ®ang nghiªn cøu ®ång thêi mong ®­îc sù l­îng thø cho nh÷ng s¬ suÊt trong tiÓu luËn nµy. tµi liÖu tham kh¶o [1] Lª TiÕn V­¬ng-NhËp m«n c¬ së d÷ liÖu quan hÖ-NXBKHKT-1996 [2] NguyÔn Kim Anh-Nguyªn lý cña c¸c hÖ c¬ së d÷ liÖu-NXB§HQGHN-2004 [3] Jeffrey D. Ullman-Nguyªn lý c¸c hÖ c¬ së d÷ liÖu vµ c¬ së tri thøc-TrÇn §øc Quang vµ Hå ThuÇn dÞch-NXBTK-1998 [4] Patrick Bosc, Olivier Pivert-Towards a representation system for possibilistic relation Phô lôc Néi dung bµi b¸o mµ tiÓu luËn tham kh¶o Môc lôc Néi dung Trang Giíi thiÖu ...................................................................................................................................................................... 1 Néi dung ...................................................................................................................................................................... 2 1. Nh÷ng yÕu tè c¬ b¶n cña m« h×nh ............................................................................................ 2 1.1 Nh÷ng gi¸ trÞ kh«ng chÝnh x¸c, kh¶ n¨ng ph©n phèi vµ world ..... 3 1.2 Sù phô thuéc cña nh÷ng gi¸ trÞ ®¹i diÖn.................................................................... 4 2. Tæng quan cña m« h×nh cã thÓ më réng ............................................................................ 5 3. Nh÷ng to¸n tö cña m« h×nh ............................................................................................................. 7 3.1 PhÐp chän (Selection) ................................................................................................................. 7 3.2 PhÐp kÕt nèi khãa ngoµi (Foreign key join) ..................................................... 8 KÕt luËn ........................................................................................................................................................................ 11 Tµi liÖu tham kh¶o ........................................................................................................................................... 12 Phô lôc: Néi dung bµi b¸o mµ tiÓu luËn tham kh¶o..................................................... 13