Tiểu luận Chương trình Datalog

n cña r, kÕt qu¶ b trë thµnh mét tËp c¸c nguyªn tè nÒn. Bao hµm ®ång d¹ng r Ͳ P1 tháa m·n nÕu vµ chØ nÕu P1(bq) chøa nguyªn tè nÒn hq, trong ®ã: +q lµ mét phÐp thÕ mét-mét mµ ¸nh x¹ mçi biÕn cña r vµo mét h»ng sè ph©n biÖt kh«ng cã trong r hoÆc P1 +bq lµ tËp hîp c¸c nguyªn tè nÒn thu ®­îc tõ b b»ng c¸ch thÕ theo q +hq lµ nguyªn tè nÒn thu ®­îc tõ h b»ng c¸ch thÕ theo q Nh÷ng ®iÒu kiÖn ë trªn hµm ý r»ng nÕu b lµ rçng, th× r Ͳ P1 ®¹t ®­îc nÕu vµ chØ nÕu r còng lµ mét quy t¾c cña P1. VÝ dô 2.1.1: Cho P1 lµ ch­¬ng tr×nh cña vÝ dô 1.1.6 g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) vµ cho P2 lµ ch­¬ng tr×nh: g(X,Z) ¬ a(X,Z) g(X,Z) ¬ a(X,Y) Ù g(Y,Z) Ta sÏ chØ ra r»ng P2 Ͳ P1. Tr­íc hÕt, c¸c biÕn cña P2 ph¶i ®­îc thay thÕ bëi c¸c h»ng ph©n biÖt. Ta dïng chØ sè d­íi 0 ®Ó biÓu thÞ c¸c h»ng, biÕn X ®­îc thay víi mét h»ng lµ X0, biÕn Y ®­îc thay víi mét h»ng Y0 vµ biÕn Z ®­îc thay víi mét h»ng Z0. Ta xem xÐt tõng quy t¾c cña P2. §èi víi quy t¾c thø nhÊt r1: g(X,Z) ¬ a(X,Z) HiÖn hµnh th©n cña r1 lµ DB {a(X0,Z0)}. Khi ¸p dông P1 vµo DB nµy, kÕt qu¶ lµ {g(X0,Z0), a(X0,Z0)}. V× kÕt qu¶ chøa hiÖn hµnh ®Çu cña r1 nªn r1ͲP1 XÐt quy t¾c thø hai r2 cña P2: g(X,Z) ¬ a(X,Y) Ù g(Y,Z) HiÖn hµnh th©n cña r2 lµ {a(X0,Z0), g(X0,Z0)}. ¸p dông quy t¾c thø nhÊt cña P1 vµo a(X0,Z0) sinh ra g(X0,Y0). ¸p dông quy t¾c thø hai sinh ra g(X0,Z0). Nh­ vËy, hiÖn hµnh ®Çu cña r2 (G(X0,Z0)) cã trong kÕt qu¶. Do ®ã r2ͲP1. Ta sÏ chØ ra r»ng P1 Ú² P2. XÐt quy t¾c thø hai s cña P1: g(X,Z) ¬ g(X,Y) Ù g(Y,Z) HiÖn hµnh th©n lµ DB {g(X0,Y0),g(X0,Z0)}. Kh«ng cã nguyªn tè míi nµo ®­îc sinh ra khi P2 ®­îc ¸p dông vµo DB nµy. V× vËy s Ú² P2, do ®ã P1 Ú² P2 VÝ dô 2.1.2: Cho P1 lµ ch­¬ng tr×nh: g(X,Y,Z) ¬ g(X,W,Z) Ù a(W,Y) Ù a(W,Z) Ù a(Z,Z) Ù a(Z,Y) vµ P2 lµ ch­¬ng tr×nh: g(X,Y,Z) ¬ g(X,W,Z) Ù a(W,Z) Ù a(Z,Z) Ù a(Z,Y) V× th©n cña quy t¾c cña ch­¬ng tr×nh P2 lµ mét tËp con cña quy t¾c cña P1, râ rµng P1 Ͳ P2. (1) Ta sÏ chØ ra r»ng P2 Ͳ P1. HiÖn hµnh th©n cña quy t¾c cña P2 lµ DB {g(X0,W0,Z0), a(W0,Z0), a(Z0,Z0), a(Z0,Y0)}. ¸p dông P1 vµo DB nµy b»ng c¸ch thay thÕ c¸c biÕn cña P1 nh­ sau: biÕn X ®­îc thay bëi X0, biÕn W thay bëi W0 vµ Z vµ Y thay bëi Z0. Víi phÐp thÕ nµy, th©n cña quy t¾c P1 trë thµnh mét tËp con cña DB, v× vËy nguyªn tè nÒn g(X0,W0,Z0) ®­îc thªm vµo DB. ¸p dông l¹i P1 b»ng c¸ch thay X víi X0, W vµ Z víi Z0, Y víi Y0. KÕt qu¶ g(X0,W0,Z0) lµ hiÖn hµnh ®Çu cña quy t¾c cña P2. V× vËy P2 Ͳ P1. (2) Tõ (1) vµ (2) suy ra P1ºP2. 2.2-Cùc tiÓu hãa ch­¬ng tr×nh trong tÝnh t­¬ng ®­¬ng ®ång d¹ng Tõ thuËt to¸n kiÓm tra sù t­¬ng ®­¬ng ®ång d¹ng, ta cã thÓ tèi ­u ch­¬ng tr×nh Datalog. ViÖc lo¹i trõ nh÷ng nguyªn tè thõa trong th©n cña mét quy t¾c ®­îc thùc hiÖn nh­ sau: XÐt mét quy t¾c r vµ cho q lµ kÕt qu¶ cña viÖc xãa mét nguyªn tè trong th©n cña r. NÕu q Ͳ r th× quy t¾c r cã thÓ ®­îc thay thÕ bëi q. Khi r ®­îc thay thÕ bëi q, qu¸ tr×nh tiÕp tôc xãa c¸c nguyªn tè thõa kh¸c trong th©n cña q. NÕu quy t¾c kÕt qu¶ lµ ®­îc bao hµm ®ång d¹ng trong q th× q ®­îc thay thÕ b»ng quy t¾c ®ã. C¸c b­íc ®­îc tãm t¾t trong thuËt to¸n d­íi ®©y: Begin Repeat §Æt a lµ mét nguyªn tè trong th©n cña r mµ ch­a ®­îc xem xÐt. §Æt q lµ quy t¾c thu ®­îc b»ng c¸ch xãa a trong r NÕu q Ͳ r th× thay thÕ r bëi q Until mçi nguyªn tè ®­îc xem xÐt mét lÇn End; ThuËt to¸n H1. Cùc tiÓu mét quy t¾c. KÕt qu¶ cuèi cïng lµ mét quy t¾c t­¬ng ®­¬ng ®ång d¹ng víi quy t¾c gèc nh­ng kh«ng tån t¹i nguyªn tè thõa §Ó chøng minh tÝnh ®óng ®¾n cña thuËt to¸n, ta ph¶i chØ ra r»ng kh«ng nguyªn tè nµo ph¶i xem xÐt nhiÒu h¬n mét lÇn. Nãi c¸ch kh¸c, nÕu mét nguyªn tè a lµ kh«ng thõa khi nã ®­îc xem xÐt lÇn thø nhÊt th× viÖc xãa tiÕp theo cña nguyªn tè kh¸c kh«ng lµm cho a trë thµnh thõa. Ta sÏ chøng minh ®iÒu nµy trong phÇn phô lôc. Nãi chung, kÕt qu¶ cuèi cïng cña thuËt to¸n lµ kh«ng duy nhÊt vµ tïy thuéc vµo thø tù trong ®ã c¸c nguyªn tè ®­îc xem xÐt. Cuèi cïng chó ý r»ng nÕu q thu ®­îc tõ r b»ng c¸ch xãa mét nguyªn tè a trong th©n, vµ mét sè biÕn trong ®Çu cña r xuÊt hiÖn chØ trong th©n a th× q tu©n theo giíi h¹n ta trªn nh÷ng quy t¾c. Râ rµng thuËt to¸n kiÓm tra sÏ x¸c ®Þnh r»ng q Ú² r nªn a kh«ng thÓ thõa. VÝ dô 2.2.1: XÐt ch­¬ng tr×nh P1 vµ P2 cña vÝ dô 2.1.2. Mçi ch­¬ng tr×nh cã mét quy t¾c vµ quy t¾c cña ch­¬ng tr×nh P2 thu ®­îc tõ quy t¾c cña ch­¬ng tr×nh P1 b»ng c¸ch xãa ®i nguyªn tè a(W,Y). Trong vÝ dô 2.1.2, ta ®· chØ ra r»ng P2 Ͳ P1. Nh­ vËy nÕu ta thùc hiÖn thuËt to¸n H1 víi quy t¾c cña P1 th× nã sÏ ®­îc thay thÕ bëi quy t¾c cña P2. DÔ dµng chØ ra r»ng quy t¾c cña P2 kh«ng cã nguyªn tè thõa nµo. V× thÕ, thuËt to¸n dõng víi quy t¾c cña P2 lµ mét d¹ng tèi thiÓu cña quy t¾c cña P1. Nh÷ng quy t¾c thõa cã thÓ ®­îc xãa trong mét ch­¬ng tr×nh P t­¬ng tù víi sù lo¹i bá nh÷ng nguyªn tè thõa trong th©n cña mét quy t¾c. Mét quy t¾c r bÞ xãa trong P ®Ó thu ®­îc mét ch­¬ng tr×nh P’, vµ nÕu r Ͳ P’, th× P º² P’ vµ nh­ vËy P’ cã thÓ thay thÕ P. §Ó cùc tiÓu mét ch­¬ng tr×nh P, tr­íc hÕt ta cùc tiÓu mçi quy t¾c b»ng c¸ch xãa ®i nh÷ng nguyªn tè thõa cña nã, vµ sau ®ã xãa nh÷ng quy t¾c thõa. Tuy nhiªn cã thÓ tån t¹i t×nh huèng mµ mét nguyªn tè trong mét sè quy t¾c r cña P cã thÓ kh«ng thõa nÕu r ®­îc xem xÐt mét m×nh, nh­ng nã bÞ thõa nÕu xem xÐt trong mäi quy t¾c cña P. §Ó cùc tiÓu mét quy t¾c r cña P, ta ph¶i söa l¹i thuËt to¸n H1 b»ng c¸ch thay thÕ ®iÒu kiÖn q Ͳ r trong lÖnh “NÕu q Ͳ r th× thay thÕ r bëi q” b»ng ®iÒu kiÖn q Ͳ P. ThuËt to¸n ®Ó cùc tiÓu mét ch­¬ng tr×nh cã thÓ viÕt nh­ sau: Begin For mçi quy t¾c cña r do Repeat -§Æt a lµ mét nguyªn tè trong th©n cña r mµ ch­a ®­îc xem xÐt. -§Æt q lµ quy t¾c thu ®­îc b»ng c¸ch xãa a trong r -NÕu q Ͳ P th× thay thÕ r bëi q Until mçi nguyªn tè ®­îc xem xÐt mét lÇn Repeat -§Æt r lµ mét quy t¾c cña P mµ ch­a ®­îc xem xÐt. -§Æt P’ lµ ch­¬ng tr×nh thu ®­îc b»ng c¸ch xãa r trong P -NÕu r Ͳ P’ th× thay thÕ P bëi P’ Untill mçi quy t¾c ®­îc xem xÐt mét lÇn End; ThuËt to¸n H2: Cùc tiÓu mét ch­¬ng tr×nh P. Trong phÇn phô lôc ta chøng minh r»ng kÕt qu¶ cuèi cïng cña thuËt to¸n kh«ng cã quy t¾c thõa vµ nguyªn tè thõa. Ngoµi ra ta cßn chØ ra r»ng kh«ng cã quy t¾c hoÆc nguyªn tè ph¶i ®­îc xem xÐt nhiÒu h¬n mét lÇn. Chøng minh dùa trªn quy ®Þnh mçi quy t¾c ®­îc cùc tiÓu vµ sau ®ã chØ ®­îc xãa nh÷ng quy t¾c thõa. KÕt qu¶ cuèi cïng cña thuËt to¸n kh«ng ph¶i lµ duy nhÊt. III- Tèi ­u hãa ch­¬ng tr×nh ®Ö quy trong tÝnh t­¬ng ®­¬ng. PhÇn nµy m« t¶ mét thñ tôc phøc t¹p h¬n ®Ó xãa nh÷ng nguyªn tè thõa trong khi vÉn duy tr× tÝnh t­¬ng ®­¬ng nh­ng kh«ng t­¬ng ®­¬ng ®ång d¹ng. Thñ tôc nµy kh«ng ph¶i lµ thuËt to¸n ®Çy ®ñ, v× nã ph¶i dïng mét sè heuristic, nh­ vËy nã kh«ng lu«n xãa tÊt c¶ c¸c nguyªn tè thõa trong d¹ng t­¬ng ®­¬ng. Tuy nhiªn, ®©y lµ mét c«ng cô kh¸ hiÖu qu¶ ®Ó tèi ­u ch­¬ng tr×nh datalog. 3.1-Phô thuéc sinh bé §Þnh nghÜa 3.1.1 (Phô thuéc sinh bé) Mét phô thuéc sinh bé (Tuple-Generating Dependency-tgd) lµ mét c«ng thøc cã d¹ng "x’$y’[Y1(x’)®Y2(x’,y’)] trong ®ã x’ vµ y’ lµ nh÷ng vect¬ cña c¸c biÕn vµ Y1, Y2 lµ sù kÕt hîp cña nh÷ng nguyªn tè. Ta cã thÓ viÕt mét tgd mµ kh«ng cã c¸c l­îng tõ g(Y,Z)®g(Y,W)Ùc(W) thay v×: "Y "Z $W [g(Y,Z)®g(Y,W)Ùc(W)] §Þnh nghÜa 3.1.2 (L­îng tõ phæ biÕn, l­îng tõ tån t¹i) Nh÷ng biÕn l­îng tõ phæ biÕn (universally) lµ nh÷ng biÕn xuÊt hiÖn trong vÕ tr¸i cña c«ng thøc (nh÷ng biÕn nµy cã thÓ xuÊt hiÖn trong vÕ ph¶i) Nh÷ng biÕn l­îng tõ tån t¹i lµ chØ xuÊt hiÖn ë vÕ ph¶i cña tgd. Th«ng th­êng, ta nãi r»ng mét DB d tháa m·n mét tgd t nÕu ®èi víi mäi thÓ hiÖn q cña nh÷ng biÕn l­îng tõ phæ biÕn th× ®iÒu sau ®©y lµ ®óng: NÕu vÕ tr¸i cña t ®­îc thÕ bëi q thµnh nh÷ng nguyªn tè nÒn cña d th× vÕ ph¶i cña t còng ®­îc thÕ thµnh nh÷ng nguyªn tè nÒn cña d b»ng c¸ch më réng q thµnh mét phÐp thÕ cña tÊt c¶ c¸c biÕn cña t. VÝ dô 3.1.3: XÐt tgd g(X,Y) ® a(Y,Z) Ù a(Z,X), vµ DB ®­îc sinh ra trong vÝ dô 1.2.1: {a(1,2), a(1,4), a(4,1), g(1,2), g(1,4), g(4,1), g(1,1), g(4,4), g(4,2)}. NÕu ta thÕ c¶ X vµ Y bëi 4, th× hiÖn hµnh phÝa bªn tr¸i g(4,4) lµ mét nguyªn tè nÒn cña DB. Ta cã thÓ chän ®Ó thay thÕ 1 vµo Z, kÕt qu¶ hiÖn hµnh bªn ph¶i gåm cã c¸c nguyªn tè nÒn a(4,1) vµ a(1,4) cña DB. Tuy nhiªn DB kh«ng tháa m·n tgd v× sù thay thÕ 4 vµo X vµ 2 vµo Y lµm biÕn ®æi vÕ tr¸i thµnh mét nguyªn tè nÒn cña DB, nh­ng kh«ng cã sù thay thÕ nµo cña Z sao cho biÕn ®æi vÕ ph¶i thµnh nh÷ng nguyªn tè nÒn cña DB. tgd g(X,Y) ® g(X,Z) Ù a(Z,Y) lµ tháa m·n DB. Ch¼ng h¹n: nÕu X ®­îc thay thÕ bëi 1 vµ Y ®­îc thay thÕ bëi 2, th× sù thay thÕ Z víi 1 biÕn ®æi vÕ ph¶i thµnh nh÷ng nguyªn tè nÒn cña DB. Cho S lµ mét tËp cña nh÷ng DB. Ta nãi r»ng ch­¬ng tr×nh P1 bao hµm ®ång d¹ng P2 trªn S, ®­îc viÕt P2ͲsP1, nÕu P2(d) Í P1(d) ®èi víi mäi DB dÎS. Trong hÇu hÕt c¸c tr­êng hîp, ta gi¶ sö r»ng S lµ tËp tÊt c¶ DB tháa m·n mét tËp c¸c tgd T ®· cho, ta ký hiÖu tËp nµy bëi SAT(T). Phô thuéc sinh bé rÊt quan träng trong Datalog, v× trong nhiÒu tr­êng hîp tèi ­u cña mét ch­¬ng tr×nh chØ yªu cÇu xem xÐt nh÷ng DB mµ tháa m·n mét sè tgd. Mét tr­êng hîp lµ khi EDB tháa m·n mét sè rµng buéc mµ cã thÓ ®­îc biÓu diÔn nh­ lµ nh÷ng tgd. Cã thª sö dông nh÷ng rµng buéc nµy ®Ó tèi ­u ch­¬ng tr×nh. Ta sÏ chØ ra c¸ch ®Ó sö dông nh÷ng tgd mét c¸ch tæng qu¸t h¬n. VÒ c¬ b¶n, ta ®­a ra mét thñ tôc minh chøng cho biÓu diÔn P2 ͲSAT(T) P1 vµ ph¸t triÓn mét kü thuËt dÓ xãa nh÷ng nguyªn tè thõa trong mét ch­¬ng tr×nh P b»ng c¸ch thùc hiÖn nh÷ng b­íc sau: Thø nhÊt: Ph¶i chØ ra r»ng P2 ͲSAT(T) P1 ®èi víi mét sè T thÝch hîp, trong ®ã P2 thu ®­îc tõ P1 b»ng c¸ch xãa mét nguyªn tè a trong mét sè quy t¾c. Thø hai: Ph¶i chØ ra r»ng P2 ͲSAT(T) P1 bao hµm P2 Í P1. NÕu ta chØ ra ®­îc c¶ hai th× a lµ thõa trong P1, dï nã kh«ng thõa trong tÝnh t­¬ng ®­¬ng ®ång d¹ng. §Ó chØ ra P2ͲSAT(T)P1, ta ph¶i chØ ra SAT(T)ÇM(P1)ÍM(P2), nghÜa lµ mäi m« h×nh cña P1 tháa m·n T còng lµ mét m« h×nh cña P2. SAT(T)ÇM(P1)ÍM(P2) ch­a thÓ suy ra P2ͲSAT(T)P1. PhÇn tiÕp theo ta sÏ m« t¶ mét b­íc thø hai ®Ó kÕt luËn P2 ͲSAT(T) P1. §Ó kiÓm tra SAT(T)ÇM(P1) Í M(P2), ta ph¶i xÐt tõng quy t¾c r cña P2 vµ chØ ra r»ng khi c¶ P1 vµ T ®­îc ¸p vµo th©n cña r th× kÕt qu¶ bao gåm ®Çu cña r. ¸p dông tgd cña T vµo mét DB t­¬ng tù víi ¸p dông mét quy t¾c, v× tgd còng lµ mÖnh ®Ò Horn. §Þnh nghÜa 3.1.4 (tgd ®Çy ®ñ vµ tgd nhóng) tgd ®Çy ®ñ (Full) lµ nh÷ng tgd mµ kh«ng cã biÕn l­îng tõ tån t¹i. tgd nhóng (Embedded) lµ nh÷ng tgd mµ cã mét sè biÕn l­îng tõ tån t¹i. VÝ dô d­íi ®©y minh häa cho viÖc ¸p dông mét tgd ®Çy ®ñ vµo mét DB (gièng nh­ ¸p dông mét quy t¾c). VÝ dô 3.1.5: Cho tgd ®Çy ®ñ: a(X,Y,Z) Ù b(W,Y,V) ® a(X,Y,V) Ù t(W,Y,Z). ¸p dông nã vµo mét DB gièng nh­ ¸p dông hai quy t¾c d­íi ®©y. Mçi quy t¾c xem vÕ tr¸i cña tgd lµ th©n vµ mét trong nh÷ng nguyªn tè ë vÒ ph¶i cña tgd lµ ®Çu. a(X,Y,V) ¬ a(X,Y,Z) Ù b(W,Y,V) t(W,Y,Z) ¬ a(X,Y,Z) Ù b(W,Y,V) Mét tgd nhóng cã c¸c biÕn l­îng tö tån t¹i v× vËy ®Ó ¸p dông nã ta ph¶i sö dông c¸c hµm Slolem. Sau ®©y ta tiÕp cËn lý thuyÕt c¬ së d÷ liÖu vµ xem c¸c hµm Skolem lµ nh÷ng gi¸ trÞ null. Ta biÓu thÞ nh÷ng gi¸ trÞ null lµ d1,...,di,... Mét tgd t ®­îc ¸p dông vµo mét DB nh­ sau: Gi¶ sö r»ng q lµ mét phÐp thÕ cña nh÷ng biÕn l­îng tõ phæ biÕn cña t, sao cho q chØ ra r¼ng DB kh«ng vi ph¹m t. §ã lµ, q biÕn ®æi vÕ tr¸i cña t thµnh nh÷ng nguyªn tè nÒn cña DB, vµ kh«ng cã më réng nµo cña q mµ biÕn ®æi vÕ ph¶i cña t thµnh nh÷ng nguyªn tè nÒn cña DB. §èi víi mçi biÕn l­îng tõ tån t¹i cña t, ta chän mét di duy nhÊt (kh«ng cã trong DB) vµ më réng q thµnh mét phÐp thÕ mµ ¸nh x¹ mçi biÕn l­îng tõ tån t¹i thµnh gi¸ trÞ rçng t­¬ng øng cña nã. Nh÷ng nguyªn tè ®­îc thay thÕ ë vÕ ph¶i cña t ®­îc thªm vµo DB. VÝ dô: nÕu t lµ tgd g(X,Y)®a(X,W)Ùg(W,Y) vµ nguyªn tè g(3,2) thuéc DB th× ta thªm a(3,d23) vµ g(d23,2) (tÊt nhiªn DB ®ã kh«ng chøa d23 còng kh«ng chøa cÆp nguyªn tè d¹ng a(3,e) vµ g(e,2) trong ®ã e lµ mét h»ng hoÆc null). Nh÷ng nguyªn tè a(3,d23) vµ g(d23,2) nghÜa lµ cã mét sè gi¸ trÞ ch­a biÕt c sao cho a(3,c) vµ g(c,2) thuéc DB. Nh÷ng ¸p dông kÕt hîp mét ch­¬ng tr×nh P vµ mét tËp tgd T ®­îc biÓu thÞ [P,T]. Ta ¸p dông [P,T] vµo mét DB d cho ®Õn khi kh«ng cã mét nguyªn tè míi nµo cã thÓ ®­îc thªm vµo DB vµ kÕt qu¶ cuèi cïng ®­îc biÓu thÞ [P,T](d). Râ rµng, [P,T](d) lµ mét m« h×nh cña P vµ mét DB mµ tháa m·n T. V× viÖc ¸p dông cña tgd cã thÓ thªm c¸c gi¸ trÞ null mµ kh«ng cã trong DB, mét sè tËp cña tgd cã thÓ ®­îc ¸p dông vµo mét DB khëi ®Çu m·i m·i. Chó ý r»ng, mét lÇn mét nguyªn tè víi gi¸ trÞ null ®­îc thªm vµo DB th× nã ®­îc xem nh­ lµ mét nguyªn tè nÒn vµ nh÷ng gi¸ trÞ null ®­îc xem nh­ nh÷ng h»ng sè, cho ®Õn khi nh÷ng ¸p dông cña c¸c quy t¾c vµ c¸c tgd ®­îc nhóng vµo. VÝ dô 3.1.6: Cho P1 lµ ch­¬ng tr×nh: g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) Ù a(Y,W) vµ cho P2 lµ ch­¬ng tr×nh: g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) DÔ dµng chØ ra r»ng P1 Ͳ P2. Ta sÏ chØ ra r»ng SAT(T)ÇM(P1)ÍM(P2), trong ®ã T gåm cã phô thuéc ®¬n g(X,Z) ® a(X,W). Nh÷ng quy t¾c cña P2 ph¶i ®­îc xem xÐt tõng c¸i mét. Ta b¾t ®Çu víi quy t¾c thø nhÊt. Th©n cña quy t¾c trë thµnh DB {a(X0,Z0)}. ¸p dông [P1,T] vµo DB nµy thu ®­îc {a(X0,Z0), g(X0,Z0)} (chØ ¸p dông quy t¾c thø nhÊt cña P1 vµo DB nµy). KÕt qu¶ nµy chøa hiÖn hµnh ®Çu cña quy t¾c thø nhÊt cña ch­¬ng tr×nh P2. TiÕp theo, xÐt DB {g(X0,Y0), g(Y0,Z0)} lµ hiÖn hµnh th©n cña quy t¾c thø hai cña P2. Tr­íc hÕt, chØ cã thÓ ¸p dông [P1,T] vµo tgd cña T. NÕu vÕ tr¸i cña tgd ®­îc thay thÕ thµnh g(X0,Z0) th× phÐp thÕ nµy kh«ng thÓ më réng thµnh bÊt kú phÐp thÕ nµo mµ biÕn ®æi vÕ ph¶i thµnh mét nguyªn tè nÒn cña DB, v× vËy a(Y0,d1) ®­îc thªm vµo DB. Mét c¸ch t­¬ng tù, vÕ tr¸i cña tgd cã thÓ ®­îc thay thÕ thµnh g(X0,Y0), mµ kÕt qu¶ lµ thªm a(X0,d2) vµo DB. B©y giê th©n cña quy t¾c thø hai cña P1 cã thÓ ®­îc thÕ vµo g(X0,Y0), g(X0,Z0), a(X0,d1), v× vËy g(X0,Z0) ®­îc thªm vµo DB, b»ng c¸ch chØ ra r»ng hiÖn hµnh ®Çu cña quy t¾c thø hai lµ thuéc kÕt qu¶. V× vËy ta ®· chØ ra r»ng SAT(T)ÇM(P1)ÍM(P2). Trong phÇn tiÕp theo, ta sÏ sö dông sù kiÖn nµy ®Ó kÕt luËn P2 ͲSAT(T) P1 ViÖc chØ ra P2 ͲSAT(T) P1 lµ rÊt h÷u Ých, bëi v× sÏ dÉn ®Õn P2 Í P1. ThËt vËy, ¸p dông ch­¬ng tr×nh P1 (hoÆc P2) vµo mét EDB gièng nh­ ¸p dông P1 (hoÆc P2) vµo DB c¬ së (lµ DB gåm cã d÷ liÖu vµo vµ nh÷ng nguyªn tè nÒn ®­îc sinh ra bëi nh÷ng quy t¾c khëi ®éng. Mét quy t¾c khëi ®éng lµ mét quy t¾c mµ th©n cña nã chØ cã mét vÞ tõ EDB). V× P1 vµ P2 cã cïng quy t¾c khëi ®éng, chóng cã cïng DB c¬ së ®èi víi mäi EDB, vµ dÔ dµng thÊy r»ng tÊt c¶ nh÷ng DB c¬ së tháa m·n T. V× vËy P2 ͲSAT(T) P1 hµm ý P2ÍP1. Râ rµng P2 Í P1 nªn P2 º P1. V× vËy nã kÐo theo nguyªn tè a(Y,W) trong quy t¾c thø hai cña P1 lµ d thõa trong d¹ng t­¬ng ®­¬ng, mÆc dï nã kh«ng thõa trong d¹ng t­¬ng ®­¬ng ®ång d¹ng. 3.2-Duy tr× phô thuéc sinh bé (Preserving Tuple-Generating Dependencies) Nh­ ®· giíi thiÖu, chØ víi SAT(T)ÇM(P1)ÍM(P2) sÏ kh«ng thÓ dÉn ®Õn P2ͲSAT(T)P1. Nh­ng nÕu ta chØ ra ®­îc P1 duy tr× T, th× P2 ͲSAT(T) P1. Ta nãi r»ng P1 duy tr× T nÕu P1(d)ÎSAT(T) ®èi víi tÊt c¶ DB d ÎSAT(T). Kh«ng thÓ biÕt liÖu cã mét thñ tôc ®Ó chØ ra r»ng mét ch­¬ng tr×nh P duy tr× mét tËp c¸c tgd T. Trong phÇn nµy ta sÏ m« t¶ mét qu¸ tr×nh mµ cã thÓ chØ ra r»ng P duy tr× T. ý t­ëng lµ nÕu ta b¾t ®Çu víi mét DB d ÎSAT(T) th× mçi lÇn lÆp l¹i trong sù tÝnh to¸n bottom-up cña P(d) duy tr× T. ¸p dông ch­¬ng tr×nh kh«ng ®Ö quy P vµo mét DB d nghÜa lµ ¸p dông nã trªn nh÷ng nguyªn tè nÒn cña d mµ kh«ng trªn nh÷ng nguyªn tè nÒn ®­îc sinh ra tõ d bëi nh÷ng ¸p dông tr­íc. Khi P ®­îc ¸p dông kh«ng ®Ö quy, ta biÓu thÞ nã lµ Pn. Râ rµng, kÕt qu¶ cña viÖc ¸p dông Pn vµo mét DB d, biÓu thÞ lµ Pn(d) lµ {hq | ®èi víi mét sè quy t¾c h ¬ b cña P vµ phÐp thÕ q, nh÷ng nguyªn tè cña bq thuéc d} Víi ®Þnh nghÜa tr­íc, ®Çu ra P(d) chøa ®Çu vµo d. Pn(d) chØ chøa nh÷ng nguyªn tè ®­îc sinh ra b»ng viÖc ¸p dông nh÷ng quy t¾c kh«ng ®Ö quy vµo d nh­ng kh«ng nhÊt thiÕt chøa nh÷ng nguyªn tè cña d. VÝ dô 3.2.1: Cho P lµ mét ch­¬ng tr×nh g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) vµ cho d={a(1,2),g(2,3),g(3,4)} vµ Pn(d) lµ {g(1,2), g(2,4)} vµ P(d) lµ {a(1,2),g(2,3),g(3,4) g(1,2), g(1,3), g(2,4), g(1,4)} ý t­ëng lµ ®Ó chØ ra r»ng P duy tr× T b»ng c¸ch chØ ra r»ng P duy tr× T mét c¸ch kh«ng ®Ö quy, ®ã lµ Î SAT(T) ®èi víi mäi d Î SAT(T) ( lµ sù kÕt hîp cña d vµ Pn(d)). NÕu P duy tr× T mét c¸ch kh«ng ®Ö quy th× P duy tr× T nh­ng ng­îc l¹i lµ kh«ng ®óng. Víi ®iÒu kiÖn lµ P duy tr× T kh«ng ®Ö quy ®­îc thùc hiÖn bëi biÕn ®æi cña qu¸ tr×nh gèi nhau. Qu¸ tr×nh nµy chøng minh cho sù duy tr× kh«ng ®Ö quy cña T, nã dõng víi mét c©u tr¶ lêi kh¼ng ®Þnh nÕu thùc sù P duy tr× T mét c¸ch kh«ng ®Ö quy, nh­ng nã cã thÓ lÆp kh«ng dõng nÕu T lµ nh÷ng tgd nhóng vµ c©u tr¶ lêi lµ phñ ®Þnh. Tr­íc khi ®Þnh nghÜa mét c¸ch ®Çy ®ñ vÒ qu¸ tr×nh nµy, ta minh häa b»ng mét vÝ dô ®¬n gi¶n. VÝ dô 3.2.2: XÐt quy t¾c ®Ö quy r d­íi ®©y: g(X,Z) ¬ g(X,Y) Ù g(Y,Z) Ù a(Y,W) vµ cho t lµ tgd g(X,Z) ® a(X,W) §Ó chØ ra r»ng r duy tr× t kh«ng ®Ö quy, ta sÏ thö chøng minh ®iÒu ng­îc l¹i b»ng c¸ch x©y dùng mét ph¶n vÝ dô, nÕu thùc hiÖn sai th× r duy tr× t kh«ng ®Ö quy. Mét ph¶n vÝ dô lµ mét DB d Î SAT(t) sao cho vi ph¹m t. DB vi ph¹m t nÕu nã cã mét nguyªn tè nÒn g(X0,Z0) xuÊt hiÖn mét vi ph¹m cña t, ®ã lµ mét nguyªn tè nÒn g(X0,Z0) sao cho ®èi víi tÊt c¶ W0, DB kh«ng cã mét nguyªn tè nÒn nµo cña d¹ng a(X0,W0). Mét nguyªn tè nÒn g(X0,Z0) cña mµ xuÊt hiÖn mét vi ph¹m cña t ph¶i thuéc rn(d) (nã kh«ng thÓ lµ thuéc d, v× d Î SAT(t)). Nh­ vËy ta thö x©y dùng mét ph¶n vÝ dô b»ng gi¶ sö r»ng g(X0,Z0) thuéc rn(d) vµ sau ®ã thªm nh÷ng nguyªn tè cÇn thiÕt vµo d ®Ó: (1)- cã nguyªn tè g(X0,Z0) trong rn(d) (2)- lµm d tháa m·n t Nguyªn tè g(X0,Z0) cã thÓ thuéc rn(d) chØ nh­ lµ mét kÕt qu¶ cña viÖc ¸p dông rn vµo d. B»ng c¸ch hîp g(X0,Z0) víi ®Çu cña r, ta cã thÓ x¸c ®Þnh nh÷ng nguyªn tè nÒn nµo ph¶i thuéc d ®Ó sinh ra g(X0,Z0). Trong tr­êng hîp nµy, phÐp hîp chØ ra r»ng d ph¶i cã nh÷ng nguyªn tè d­íi ®©y: g(X0,Y0), g(X0,Z0), a(Y0,W0). Trong ®ã Y0, W0 lµ c¸c h»ng. V× d tháa m·n t, cã thÓ ¸p dông tgd t vµo d. ¸p dông t vµo g(X0,Y0) sinh ra a(X0,d1), vµ ¸p dông nã vµo g(Y0,Z0) thu ®­îc a(Y0,d2). KÕt qu¶ cña nh÷ng ¸p dông nµy thuéc nh÷ng nguyªn tè nÒn mµ ph¶i lµ thuéc d (tr¸i víi ¸p dông cña rn mµ sinh ra nh÷ng nguyªn tè nÒn thuéc rn(d)). VÒ c¬ b¶n, sù ¸p dông cña t t­¬ng øng víi ®iÒu suy ra ®­îc hµm chøa bëi d tháa m·n t vµ b»ng mét ®iÒu r»ng ch¾c ch¾n nh÷ng nguyªn tè nÒn ®­îc biÕt lµ thuéc d. VÒ nguyªn t¾c, tgd t ph¶i ®­îc ¸p dông mét c¸ch lÆp l¹i vµo nh÷ng nguyªn tè cña d (c¶ nh÷ng nguyªn tè gèc ë trong d vµ nh÷ng c¸i ®­îc thªm vµo d b»ng nh÷ng ¸p dông tr­íc cña tgd). Trong tr­êng hîp ®Æc biÖt nµy, tgd chØ cã thÓ ®­îc ¸p dông vµo nh÷ng nguyªn tè nÒn gèc ®­îc biÕt lµ thuéc d (nghÜa lµ nã ®­îc sinh ra bëi phÐp hîp g(X0,Z0) víi ®Çu cña r). KÕt qu¶ nh÷ng nguyªn tè nÒn ph¶i thuéc d lµ: g(X0,Y0), g(Y0,Z0), a(Y0,W0), a(X0,d1), a(Y0,d2) Trong sè chóng cã a(X0,d1) mµ ®­îc chØ ra r»ng g(X0,Z0) kh«ng xuÊt hiÖn vi ph¹m cña t. Nh­ vËy, kh«ng cã mét ph¶n vÝ dô vµ v× vËy r duy tr× t kh«ng ®Ö quy. Ta cã thÓ kh¸i qu¸t hãa vÝ dô trªn thµnh mét P vµ T tïy ý. §Ó chøng minh r»ng P duy tr× T kh«ng ®Ö quy, ta thùc hiÖn ®èi víi mçi t Î T. §Çu tiªn vÕ tr¸i cña t ®­îc thÕ mçi biÕn víi mét h»ng sè ph©n biÖt mµ kh«ng thuéc P. Nh÷ng nguyªn tè nÒn cña phÐp thÕ vÕ tr¸i ®­îc xem xÐt theo mét trong hai tr­êng hîp d­íi ®©y: (1)- Nh÷ng nguyªn tè nÒn cña vÞ tõ EDB trë thµnh mét phÇn cña d (2)- Nh÷ng nguyªn tè nÒn cña vÞ tõ IDB trë thµnh mét phÇn cña Pn(d) §èi víi mçi nguyªn tè nÒn a thuéc Pn(d), ta ph¶i thªm vµo d mét sè nguyªn tè mµ sinh ra a khi P ®­îc ¸p dông kh«ng ®Ö quy vµo d. Nãi chung, cã nhiÒu c¸ch ®Ó thªm nh÷ng nguyªn tè sinh ra a. Mçi c¸ch ®­îc x¸c ®Þnh b»ng mét sè quy t¾c víi ®Çu cã thÓ ®­îc hîp nhÊt víi a. Nh­ vËy, ta ph¶i xem xÐt tÊt c¶ nh÷ng kÕt hîp cã thÓ cña viÖc hîp nhÊt nh÷ng nguyªn tè nÒn mµ ®· ®­îc thªm vµo Pn(d) víi ®Çu cña nh÷ng quy t¾c (nÕu cã k nguyªn tè nÒn thuéc Pn(d) vµ mçi i cã thÓ hîp nhÊt víi m quy t¾c, th× cã mk kÕt hîp ®­îc xem xÐt). VÒ c¬ b¶n, ta ph¶i chØ ra r»ng, ®èi víi mçi kÕt hîp cã thÓ, kh«ng cã vi ph¹m t. V× vËy xem xÐt mét kÕt hîp cã thÓ mµ hîp nhÊt mçi nguyªn tè nÒn a cña mét vÞ tõ IDB g (trong phÐp thÕ vÕ tr¸i cña t) víi ®Çu cña mét sè quy t¾c r ®èi víi g. KÕt qu¶ cña viÖc hîp nhÊt, nh÷ng biÕn cña r mµ xuÊt hiÖn trong ®Çu quy t¾c ®­îc thÕ vµo nh÷ng h»ng. §Ó biÕn ®æi th©n cña r thµnh nh÷ng nguyªn tè nÒn, nh÷ng biÕn cßn l¹i cña r ®­îc thay thÕ b»ng mét h»ng ph©n biÖt míi, vµ nh÷ng nguyªn tè nÒn cña th©n ®­îc thªm vµo d. Nãi tãm l¹i, d chøa tÊt c¶ nh÷ng nguyªn tè nÒn mµ lµ: (1)- Nh÷ng nguyªn tè cña vÞ tõ EDB tõ phÐp thÕ vÕ tr¸i cña tgd t hoÆc (2)- Nh÷ng nguyªn tè (EDB hoÆc IDB) tõ th©n cña quy t¾c mµ ®­îc hîp nhÊt víi nh÷ng nguyªn tè cña vÞ tõ IDB tõ vÕ tr¸i cña t VÒ phÝa Pn(d), nã chøa nh÷ng nguyªn tè cña vÞ tõ IDB tõ phÐp thÕ vÕ tr¸i cña t. Trong b­íc thø hai, nh÷ng tgd cña T ®­îc ¸p dông vµo d ®Ó sinh ra nhiÒu nguyªn tè nÒn h¬n mµ ph¶i thuéc d. Nh÷ng tgd ®­îc ¸p dông lÆp l¹i cho ®Õn khi kh«ng cã nguyªn tè nÒn nµo cã thÓ ®­îc sinh ra tõ nh÷ng c¸i ®· cã (kÕt qu¶, d trë thµnh mét DB tháa m·n T) TiÕp theo, ch­¬ng tr×nh P ®­îc ¸p dông kh«ng ®Ö quy vµo d ®Ó lÊy Pn(d). Cuèi cïng, ta ph¶i kiÓm tra liÖu tháa m·n t. §Ó kiÓm tra ®iÒu ®ã, chØ cÇn xem xÐt phÐp thÕ vÕ tr¸i cña t vµ kiÓm tra liÖu t cã vi ph¹m trong . Kh«ng xuÊt hiÖn vi ph¹m nÕu hiÖn hµnh vÕ tr¸i cã thÓ ®­îc më réng thµnh mét hiÖn hµnh mµ còng gåm cã c¸c biÕn l­îng tõ tån t¹i cña t, sao cho vÕ ph¶i cña t trë thµnh mét tËp con cña . ThËt ra, nã dÉn ®Õn kh«ng cÇn thiÕt tÝnh to¸n tÊt c¶ Pn(d) mµ chØ cÇn x¸c ®Þnh liÖu chøa c¸c nguyªn tè nÒn chØ ra r»ng hiÖn hµnh vÕ tr¸i cña t kh«ng xuÊt hiÖn vi ph¹m. §Ó biÓu diÔn mét c¸ch râ rµng ta sÏ tiÕp tôc dïng b­íc tÝnh to¸n Pn(d) Ch­¬ng tr×nh P duy tr× T kh«ng ®Ö quy, nÕu ®èi víi tÊt c¶ tÎT vµ ®èi víi tÊt c¶ sù kÕt hîp hiÖn hµnh vÕ tr¸i cña t víi ®Çu cña quy t¾c cña P, kh«ng biÓu hiÖn vi ph¹m t. Trong vÝ dô 3.2.2, vÕ tr¸i cña tgd t chØ cã mét nguyªn tè vµ chØ cã mét quy t¾c. Nh­ vËy chØ cã mét kÕt hîp ®Ó kiÓm tra, vµ nã kh«ng xuÊt hiÖn vi ph¹m. D­íi ®©y lµ thuËt to¸n ®Ó kiÓm tra P duy tr× T kh«ng ®Ö quy. Begin Repeat -T¹o d empty -Chän a, t Î T -Cho q ¸nh x¹ nh÷ng biÕn l­îng tõ phæ biÕn cña t vµo nh÷ng h»ng ph©n biÖt mµ ch­a thuéc P -ThÕ vÕ tr¸i cña t theo q -Thªm nh÷ng nguyªn tè hiÖn hµnh cña vÞ tõ EDB vµo d Repeat -Chän mét quy t¾c ®èi víi mçi nguyªn tè hiÖn hµnh cña mét vÞ tõ IDB -Hîp mçi nguyªn tè víi ®Çu cña quy t¾c ®­îc chän cho nã, vµ thªm hiÖn hµnh th©n vµo d. -¸p dông nh÷ng tgd cña T vµo d -TÝnh Pn(d) -KiÓm tra liÖu hiÖn hµnh vÕ tr¸i xuÊt hiÖn vi ph¹m t trong Until xuÊt hiÖn vi ph¹m hoÆc ®· kiÓm tra tÊt c¶ c¸c kÕt hîp cña quy t¾c ®­îc chän. Until xuÊt hiÖn vi ph¹m hoÆc tÊt c¶ t Î T ®· ®­îc chän If xuÊt hiÖn vi ph¹m th× P kh«ng duy tr× T mét c¸ch kh«ng ®Ö quy Else P duy tr× T mét c¸ch ®Ö quy. End; ThuËt to¸n H3: KiÓm tra duy tr× kh«ng ®Ö quy cña T B­íc ¸p dông T vµo d cã thÓ kh«ng dõng nÕu nh÷ng gi¸ trÞ null míi ®­îc ®­a vµo mét c¸ch lÆp l¹i. Tuy nhiªn, vÉn cã thÓ dõng vßng lÆp bªn trong víi thêi gian h÷u h¹n (®èi víi bÊt kú sù lùa chän t ÎT vµ bÊt kú sù lùa chän quy t¾c ®èi víi t) nÕu t kh«ng xuÊt hiÖn vi ph¹m. §Ó ®¹t ®­îc ®iÒu ®ã, ba b­íc cuèi cïng cña vßng lÆp bªn trong ph¶i ®­îc chÌn thªm nh­ sau: Thø nhÊt, T ®­îc ¸p dông vµo d ®Ó sinh ra mét sè nguyªn tè míi mµ ph¶i thuéc d. TiÕp theo, Pn(d) ®­îc tÝnh l¹i, v× gi¸ trÞ cña nã cã thÓ bÞ thay ®æi nh­ lµ mét kÕt qu¶ cña nh÷ng nguyªn tè míi mµ võa ®­îc thªm vµo d. Thø ba lµ ®Ó kiÓm tra liÖu hiÖn hµnh vÕ tr¸i cña t xuÊt hiÖn mét vi ph¹m trong hiÖn t¹i. NÕu kh«ng xuÊt hiÖn vi ph¹m th× t ®­îc duy tr× vµ kh«ng cÇn thiÕt ®Ó tiÕp tôc. NÕu cßn tån t¹i vi ph¹m th× b­íc tr­íc ph¶i ®­îc lÆp l¹i. Nh­ ®· nªu, mçi nguyªn tè cña mét vÞ tõ IDB, trong hiÖn hµnh vÕ tr¸i cña t, ®­îc hîp víi ®Çu cña mét sè quy t¾c. §iÒu nµy cã ¶nh h­ëng cña kiÓm tra liÖu t ®­îc tháa m·n khi nh÷ng nguyªn tè cña nh÷ng vÞ tõ IDB trong vÕ tr¸i cña nã ®­îc giíi h¹n lµ thuéc Pn(d). Trong vÝ dô 3.2.2, cã mét nguyªn tè ®¬n trong vÕ tr¸i cña t, vµ nh­ vËy t ®­îc tháa m·n trong nÕu: (1)- t tho¶ m·n trong khi vÕ tr¸i ®­îc giíi h¹n thuéc Pn(d) vµ (2)- t tháa m·n trong khi vÕ tr¸i ®­îc giíi h¹n thuéc d. (1) ®· ®­îc chØ ra trong vÝ dô 3.2.2 b»ng viÖc hîp vÕ tr¸i víi ®Çu cña r. (2) tõ sù kiÖn d tháa m·n t. Tuy nhiªn t×nh huèng nµy lµ kh«ng ®¬n gi¶n nÕu vÕ tr¸i cña t cã nhiÒu h¬n mét nguyªn tè cña mét vÞ tõ IDB. Khi ®ã, ta ph¶i kiÓm tra r»ng t còng ®­îc tháa m·n khi mét sè nguyªn tè lµ thuéc Pn(d), trong khi nh÷ng nguyªn tè kh¸c lµ thuéc d. Nh­ vËy ta ph¶i xem xÐt nhiÒu kÕt hîp h¬n. Sù kÕt hîp lµ tÊt c¶ mµ trong ®ã mét nguyªn tè cña vÞ tõ IDB trong vÕ tr¸i cña t ®­îc hîp nhÊt víi ®Çu cña mét sè quy t¾c hoÆc ®­îc gi¶ sö lµ thuéc d. NÕu mét nguyªn tè ®­îc hîp víi ®Çu cña mét sè quy t¾c th× nguyªn tè trë thµnh mét phÇn cña Pn(d), trong khi hiÖn hµnh th©n cña quy t¾c trë thµnh mét phÇn cña d. Ta vÉn dïng ®Þnh nghÜa cò cña phÐp kÕt hîp ®Ó ®­îc xem xÐt nÕu ®èi víi mçi vÞ tõ IDB q, ta thªm mét quy t¾c tÇm th­êng cã d¹ng: q(X1,...,Xn)¬ q(X1,...,Xn). Tõ ®©y ta gi¶ sö r»ng mçi ch­¬ng tr×nh ®­îc t¨ng lªn víi nh÷ng quy t¾c tÇm th­êng nµy. V× vËy, phÐp kÕt hîp ®­îc xem xÐt lµ gièng nh­ ®Þnh nghÜa ®Çu tiªn, ®ã lµ phÐp kÕt hîp mçi nguyªn tè cña mét vÞ tõ IDB víi ®Çu cña mét sè quy t¾c. VÝ dô 3.2.3: XÐt l¹i ch­¬ng tr×nh P1 ®· cho trong vÝ dô 3.1.6 g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) Ù a(Y,W) vµ vµ tgd t g(X,Z) ® a(X,W) Ta sÏ chØ ra r»ng P1 duy tr× T={t} kh«ng ®Ö quy, v× vËy nã còng duy tr× T. KÕt hîp víi sù kiÖn SAT(T) Ç M(P1) Í M(P2), (®­îc chØ ra trong vÝ dô 3.1.6) dÉn ®Õn lµ P2 ͲSAT(T) P1. Cho g(X0,Z0) lµ hiÖn hµnh vÕ tr¸i cña t. Trong vÝ dô 3.2.2, ta ®· chØ ra kh«ng xuÊt hiÖn vi ph¹m khi g(X0,Z0) ®­îc hîp nhÊt víi ®Çu cña quy t¾c thø hai cña P1. T­¬ng tù, cã thÓ kh«ng vi ph¹m khi g(X0,Z0) ®­îc hîp nhÊt víi quy t¾c tÇm th­êng g(X,Z) ¬g(X,Z). Tr­êng hîp cuèi cïng ®Ó xem xÐt lµ sù hîp nhÊt víi quy t¾c: g(X,Z) ¬ a(X,Z) KÕt qu¶ cña phÐp hîp nhÊt g(X0,Z0) víi ®Çu cña quy t¾c trªn, d trë thµnh DB {a(X0,Z0)}. Nh÷ng tgd cña T kh«ng ®­îc ¸p dông vµo d. TiÕp theo b»ng c¸ch ¸p dông Pn1 vµo d, ta thu ®­îc Pn1(d) lµ {g(X0,Z0)}. V× a(X0,Z0) thuéc , t kh«ng xuÊt hiÖn vi ph¹m, v× vËy P1 duy tr× T. VÝ dô 3.2.4: Cho r lµ quy t¾c nh­ trong vÝ dô 3.2.2: g(X,Z) ¬ g(X,Y) Ù g(Y,Z) Ù a(Y,W) vµ tgd lµ g(X,Y) Ù g(Y,Z) ® a(Y,W) Ta sÏ chØ ra r»ng r duy tr× t kh«ng ®Ö quy. Ta sÏ xem xÐt ch­¬ng tr×nh ngay c¶ khi nÕu nã cã quy t¾c tÇm th­êng: g(X,Z) ¬ g(X,Z). Nh­ vËy cã bèn kh¶ n¨ng kÕt hîp cña sù hîp nhÊt cña nh÷ng nguyªn tè trong vÕ tr¸i cña t víi ®Çu cña c¸c quy t¾c. Cho g(X0,Y0) Ù g(Y0,Z0) lµ hiÖn hµnh vÕ tr¸i cña t vµ xÐt bèn kÕt hîp d­íi ®©y: KÕt hîp thø nhÊt: g(X0,Y0) hîp nhÊt víi ®Çu cña r. KÕt qu¶, nh÷ng nguyªn tè nÒn g(X0,Y1), g(Y1,Y0), a(Y1,W0) thuéc d vµ g(Y0,Z0) ®­îc hîp nhÊt víi ®Çu cña quy t¾c tÇm th­êng vµ nguyªn tè g(Y0,Z0) ®­îc thªm vµo d TiÕp theo, T={t} ph¶i ®­îc ¸p dông vµo d vµ vÕ tr¸i cña t ®­îc thay thÕ víi nguyªn tè nÒn g(Y1,Y0), g(Y0,Z0) cña d. V× phÐp thÕ nµy kh«ng ®­îc më réng ®Ó biÕn ®æi vÕ ph¶i thµnh nh÷ng nguyªn tè nÒn cña d, nguyªn tè nÒn a(Y0,d1) ®­îc thªm vµo d. Nguyªn tè a(Y0,d1) cña d cho thÊy kh«ng xuÊt hiÖn vi ph¹m cña t trong ®èi víi phÐp kÕt hîp ®­îc xÐt. PhÐp kÕt hîp thø hai: g(X0,Y0) hîp nhÊt víi ®Çu cña quy t¾c tÇm th­êng, nguyªn tè nÒn g(X0,Y0) ®­îc thªm vµo d vµ g(Y0,Z0) ®­îc hîp nhÊt víi ®Çu cña r, nh÷ng nguyªn tè nÒn g(Y0,Y1), g(Y1,Z0), a(Y1,W0) ®­îc thªm vµo d. TiÕp theo, T={t} ®­îc ¸p dông vµo d vµ vÕ tr¸i cña t ®­îc thay thÕ vµo nh÷ng nguyªn tè nÒn g(X0,Y0), g(Y0,Y1) cña d. PhÐp thÕ nµy thªm a(Y0,d1) vµo d, vµ nguyªn tè nÒn nµy chØ ra r»ng t kh«ng vi ph¹m trong PhÐp kÕt hîp thø ba: g(X0,Y0) ®­îc hîp nhÊt víi ®Çu cña quy t¾c r, nh÷ng nguyªn tè nÒn g(X0,Y1), g(Y1,Y0), a(Y1,W0) ®­îc thªm vµo d vµ g(Y0,Z0) ®­îc hîp nhÊt víi ®Çu cña r, nh÷ng nguyªn tè nÒn g(Y0,Y2), g(Y2,Z0), a(Y2,W1) ®­îc thªm vµo d. TiÕp theo T={t} ®­îc ¸p vµo d b»ng c¸ch thÕ vÕ tr¸i cña t vµo nh÷ng nguyªn tè nÒn g(Y1,Y0), g(Y0,Y2) cña d, kÕt qu¶ a(Y0,d1) ®­îc thªm vµo d. Nguyªn tè a(Y0,d1) chØ ra r»ng t kh«ng vi ph¹m trong ®èi víi phÐp kÕt nèi ®­îc xem xÐt. PhÐp kÕt hîp thø t­: C¶ g(X0,Y0) vµ g(Y0,Z0) ®­îc hîp nhÊt víi ®Çu cña quy t¾c tÇm th­êng v× vËy trë thµnh mét phÇn cña d. Râ rµng, kh«ng thÓ cã vi ph¹m trong tr­êng hîp nµy, v× d thâa m·n T. V× kh«ng cã phÐp kÕt nèi nµo xuÊt hiÖn vi ph¹m nªn r duy tr× t VÝ dô 3.2.5: XÐt quy t¾c r g(X,Z) ¬ a(X,Y) Ù g(Y,Z) Ù g(Y,W) Ù c(W) vµ tgd t d­íi ®©y g(Y,Z) ® g(Y,W) Ù c(W) §Ó chØ ra r duy tr× t kh«ng ®Ö quy, ta thÕ vÕ tr¸i cña t víi g(Y0,Z0) vµ hîp nhÊt nã víi ®Çu cña r. KÕt qu¶, nh÷ng nguyªn tè nÒn g(Y1,Z0), g(Y1,W0), a(Y0,Y1), c(W0) lµ thuéc d Trong tr­êng hîp nµy, tgd t kh«ng thÓ ¸p dông vµo d ®Ó sinh ra nh÷ng nguyªn tè míi. Nh­ng khi r ®­îc ¸p dông kh«ng ®Ö quy vµo d, DB rn(d) trë thµnh g(Y0,Z0), g(Y0,W0) §Ó thÊy g(Y0,Z0) lµ thuéc rn(d), ta l­u ý, nguyªn tè nµy ®· ®­îc hîp nhÊt víi ®Çu cña r vµ hiÖn hµnh th©n trë thµnh mét phÇn cña d. §Ó thÊy g(Y0,W0) lµ thuéc rn(d), ta thÕ c¸c biÕn cña r: X víi Y0, Y víi Y1, Z vµ W víi W0. Nh÷ng nguyªn tè nÒn g(Y0,W0) vµ c(W0) chØ ra r»ng kh«ng vi ph¹m t khi vÕ tr¸i ®­îc thÕ víi g(Y0,Z0). Nh­ vËy r duy tr× t. 3.3-X¸c ®Þnh tÝnh t­¬ng ®­¬ng (Determining Equivalence) PhÇn nµy ta sÏ chØ ra c¸ch ®Ó cã thÓ kÕt luËn P2 Í P1 tõ P2ͲSAT(T)P1. Ta sÏ sö dông kü thuËt nµy ®Ó tèi ­u hãa c¸c ch­¬ng tr×nh. Mét quy t¾c r cña mét ch­¬ng tr×nh P lµ mét quy t¾c khëi ®éng nÕu th©n cña r chØ cã nh÷ng vÞ tõ EDB. Pi lµ ch­¬ng tr×nh gåm cã nh÷ng quy t¾c khëi ®éng cña P (Pi lµ mét ch­¬ng tr×nh kh«ng ®Ö quy). Cho mét EDB d lµ d÷ liÖu vµo cña P, ta ®Þnh nghÜa Pi(d) lµ tËp c¸c nguyªn tè nÒn ®­îc sinh ra b»ng viÖc ¸p dông Pi vµo d (Pi(d) kh«ng bao gåm d). DB c¬ së (preliminary) ®èi víi mét EDB d lµ VÝ dô 3.3.1: Cho P lµ ch­¬ng tr×nh g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) vµ d={a(1,2), a(2,3), a(3,4)} Pi(d) lµ {g(1,2), g(2,3), g(3,4)} vµ DB c¬ së ®èi víi d lµ {a(1,2), a(2,3), a(3,4), g(1,2), g(2,3), g(3,4)}. VÝ dô d­íi ®©y minh häa c¸ch kÕt luËn P2 Í P1 tõ P2 ͲSAT(T) P1. VÝ dô 3.3.2: XÐt l¹i hai ch­¬ng tr×nh cña vÝ dô 3.1.6 Cho P1 lµ ch­¬ng tr×nh: g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) Ù a(Y,W) vµ P2 lµ ch­¬ng tr×nh: g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) Râ rµng P1 Ͳ P2. Trong vÝ dô 3.1.6 ta ®· cã SAT(T) Ç M(P1) Í M(P2). Trong ®ã T gåm cã nh÷ng tgd ®¬n: g(X,Z) ® a(X,W) Trong vÝ dô 3.2.3 ta ®· chØ ra: P1 duy tr× T, kÕt qu¶, P2 ͲSAT(T) P1. Trong vÝ dô nµy ta sÏ chØ ra: P2 Í P1 nªn P2 º P1. (v× P1 Ͳ P2 nªn P1 Í P2). Thø nhÊt, ta sÏ chØ ra r»ng ®èi víi mäi EDB d, DB c¬ së, , tháa m·n T. Trong ®ã Pi1 gåm cã c¸c quy t¾c: g(X,Z) ¬ a(X,Z) VÒ c¬ b¶n, thuËt to¸n H3 dïng ®Ó chØ ra r»ng tháa m·n T. Nh­ng cã hai thay ®æi: Thø nhÊt, ta kh«ng gi¶ sö d tháa m·n T v× vËy ta bá qua b­íc mµ nh÷ng tgd cña T ®­îc ¸p dông vµo d. Thø hai, d lµ mét EDB ®­îc cho nh­ mét ®Çu vµo cña P1 do ®ã nã kh«ng cã bÊt kú mét nguyªn tè nÒn nµo cña mét vÞ tõ IDB. V× vËy, ta kh«ng thªm vµo ch­¬ng tr×nh Pi1 nh÷ng quy t¾c tÇm th­êng ®èi víi nh÷ng vÞ tõ IDB. Nh­ vËy, ta b¾t ®Çu b»ng viÖc thÕ vÕ tr¸i cña tgd trong T, kÕt qu¶ lµ g(X0,Z0). ChØ cã mét quy t¾c trong Pi1 v× vËy chØ cã mét kÕt hîp cña sù hîp nhÊt hiÖn hµnh vÕ tr¸i víi ®Çu cña c¸c quy t¾c. KÕt qu¶ cña phÐp hîp nhÊt nµy trong d lµ DB {a(X0,Z0)}. V× a(X0,Z0) ®­îc chØ ra lµ thuéc , tgd kh«ng xuÊt hiÖn vi ph¹m, v× vËy tÊt c¶ DB c¬ së cña P1 tháa m·n T. P1 vµ P2 cã cïng mét quy t¾c khëi ®éng vµ kÕt qu¶ nh÷ng DB c¬ së cña nã gièng nhau (khi ®­îc cho cïng EDB lµ ®Çu vµo). V× vËy P2 ͲSAT(T) P1 bao hµm P2 Í P1, v× tÊt c¶ nh÷ng DB c¬ së tháa m·n T. Tõ viÖc chØ ra P2 Í P1 ®· dÉn ®Õn: (1)-SAT(T) Ç M(P1) Í M(P2). (2)-P1 duy tr× T (3)-§èi víi tÊt c¶ EDB d, ch­¬ng tr×nh P1 vµ P2 cã cïng mét DB c¬ së. (4)-TÊt c¶ DB c¬ së tháa m·n T PhÇn (1) cã thÓ ®­îc chØ ra dïng qu¸ tr×nh gèi nhau ®­îc m« t¶ trong phÇn “Phô thuéc sinh bé”. PhÇn (2) cã thÓ ®­îc chØ b»ng thuËt to¸n H3. PhÇn (3) yªu cÇu chØ ra r»ng Pi1 vµ Pi2 lµ t­¬ng ®­¬ng. Sù t­¬ng ®­¬ng cña ch­¬ng tr×nh kh«ng ®Ö quy gièng nh­ t­¬ng ®­¬ng ®ång d¹ng vµ thuËt to¸n ®­îc m« t¶ trong phÇn “KiÓm tra tÝnh bao hµm vµ t­¬ng ®­¬ng ®ång d¹ng ®· chØ ra ®iÒu ®ã. PhÇn (4) cã thÓ ®­îc chØ ra bëi thuËt to¸n H3 víi nh÷ng söa ®æi nh­ sau: Thø nhÊt, b­íc ¸p dông nh÷ng tgd cña T vµo d bÞ xãa. Thø hai, ch­¬ng tr×nh Pi1 kh«ng ®­îc lµm t¨ng lªn b»ng nh÷ng quy t¾c tÇm th­êng ®èi víi c¸c vÞ tõ IDB. Ph­¬ng ph¸p ®Ó chØ ra P2 Í P1 cã mét sè h¹n chÕ dÉn ®Õn gi¶m kh¶ n¨ng øng dông cña nã. Thø nhÊt, kh«ng ph¶i lu«n t×m ®­îc mét tËp tgd T ®èi víi c¸i mµ (1)-(4) ®­a ra. H¬n n÷a, sù kiÖn P2 Í P1 kh«ng nhÊt thiÕt hµm ý cã mét T nh­ vËy. Thø hai, thñ tôc ®Ó kiÓm tra (1) hoÆc (2), dõng trong thêi gian h÷u h¹n nÕu c©u tr¶ lêi lµ kh¼ng ®Þnh nh­ng cã thÓ kh«ng dõng nÕu c©u tr¶ lêi lµ phñ ®Þnh. Tuy nhiªn, ta tin r»ng trong nhiÒu tr­êng hîp thùc tÕ tiÕp cËn nµy lµ h÷u Ých trong viÖc tèi ­u hãa c¸c ch­¬ng tr×nh. Thùc ra, kh«ng cÇn thiÕt ®Ó xem xÐt nh÷ng DB c¬ së cña P1 vµ cho thÊy r»ng chóng tháa m·n T. Nãi c¸ch kh¸c, nh÷ng ®iÒu kiÖn 3 vµ 4 cã thÓ ®­îc thay thÕ bëi ®iÒu kiÖn d­íi ®©y: (3’)- §èi víi tÊt c¶ EDB (d), DB c¬ së tháa m·n T. Lý do: Ta biÕt r»ng P2 ͲSAT(T) P1 vµ ta muèn kÕt luËn lµ P2 Í P1, tøc lµ muèn chØ ra r»ng nÕu d lµ mét EDB th× P2(d) Í P1(d). VËy, cho d’ lµ DB c¬ së cña P1 thu ®­îc tõ d (nghÜa lµ dÍd’) vµ gi¶ sö r»ng d’ tháa m·n T. V× P2ͲSAT(T)P1 vµ d’ tháa m·n T, kÐo theo P2(d’) Í P1(d’). (A) V× ch­¬ng tr×nh Datalog lµ ®¬n ®iÖu, nªn: P2(d) Í P1(d). (B) V× d Í d’, H¬n n÷a, d’ lµ DB c¬ së thu ®­îc b»ng c¸ch ¸p dông c¸c quy t¾c khëi ®éng cña P1 vµo d, v× vËy: P1(d) Í P1(d’) (C) Tõ (A), (B) vµ (C) suy ra P2(d) Í P1(d). Mét chó ý kh¸c, khi ®Þnh nghÜa DB c¬ së, kh«ng cÇn chän c¸i ®­îc sinh bëi nh÷ng quy t¾c khëi ®éng mµ chØ cÇn xem xÐt bÊt kú tËp c¸c quy t¾c cña P1 vµ ¸p dông nã mét sè l­îng lÇn cè ®Þnh vµo EDB ban ®Çu ®­îc cho nh­ mét d÷ liÖu vµo. ViÖc ¸p dông mét tËp quy t¾c ®· cho víi mét sè lÇn cè ®Þnh (c¶ nh÷ng quy t¾c ®Ö quy) cã thÓ ®­îc diÔn t¶ trong ®iÒu kiÖn nh÷ng quy t¾c kh«ng ®Ö quy. V× vËy viÖc kiÓm tra liÖu DB c¬ së tháa m·n T cã thÓ ®­îc thùc hiÖn nh­ ®· m« t¶ ®èi víi DB ®­îc t¹o ra bëi nh÷ng quy t¾c khëi ®éng. 3.4-Tèi ­u hãa trong tÝnh t­¬ng ®­¬ng (Optimizing under Equivalence) Trong vÝ dô 3.3.2, ta d· chØ ra nguyªn tè a(Y,W) thõa trong quy t¾c ®Ö quy cña P1. Dïng thuËt to¸n H2 kh«ng thÓ chØ ra ®iÒu nµy v× a(Y,W) lµ kh«ng thõa trong tÝnh t­¬ng ®­¬ng ®ång d¹ng. VÊn ®Ò lµ b»ng c¸ch nµo ®Ó t×m ra mét tgd mµ cho thÊy sù thõa cña a(Y,W). Trong thùc tÕ, tiÕp cËn thÝch hîp lµ dïng mét sè Heuristics. tgd g(X,Z)®a(X,W) ®­îc dïng trong vÝ dô 3.3.2 cã mét thuéc tÝnh mµ dÔ dµng chØ ra: SAT(T) Ç M(P1) Í M(P2) (1) Nh¾c l¹i r»ng T gåm cã tgd trªn vµ P2 thu ®­îc tõ P1 b»ng c¸ch xãa a(Y,W). Cô thÓ, mét ¸p dông ®¬n cña T vµo th©n cña quy t¾c ®Ö quy cña P2 lµm th©n ®ã ®ång nhÊt víi th©n cña quy t¾c ®Ö quy cña P1 vµ nh­ vËy cho (1) Quy t¾c ®­îc tèi ­u hãa trong vÝ dô 3.3.2 lµ: g(X,Z) ¬ g(X,Y) Ù g(Y,Z) Ù a(Y,W) vµ tgd ®· chän còng cã thÓ lµ g(Y,Z)®a(Y,W), nã gåm cã nh÷ng nguyªn tè xuÊt hiÖn trong th©n cña quy t¾c trªn vµ cã c¸c thuéc tÝnh d­íi ®©y: 1-VÕ tr¸i cña tgd cã cïng vÞ tõ nh­ ®Çu cña quy t¾c ®ang ®­îc tèi ­u. 2-NÕu tgd cã mét biÕn W mµ xuÊt hiÖn chØ trong vÕ ph¶i cña nã th× tÊt c¶ nh÷ng nguyªn tè (trong th©n cña quy t¾c) mµ chøa W lµ ë vÕ ph¶i cña tgd. 3-TÊt c¶ nh÷ng biÕn cña tgd mµ chØ xuÊt hiÖn trong vÕ ph¶i cña nã lµ kh«ng ë ®Çu cña quy t¾c. Mét khi mét tgd ®­îc chän, b­íc tiÕp theo lµ kiÓm tra liÖu nh÷ng nguyªn tè trong vÕ ph¶i cña tgd lµ thõa trong th©n cña quy t¾c. Khi t×m thÊy mét tgd, vÉn cßn ph¶i kiÓm tra nh÷ng ®iÒu kiÖn trong phÇn tr­íc. Mét vÊn ®Ò lµ nã cã thÓ kh«ng dõng. C¸ch ®Ó ®iÒu khiÓn mét qu¸ tr×nh tèi ­u hãa mµ thùc hiÖn qu¸ chËm ®ã lµ sö dông thêi gian tèi ­u hãa mét quyÕt ®Þnh tr­íc cña thêi gian. VÝ dô d­íi ®©y minh häa cho ý t­ëng trªn: VÝ dô 3.4.1: XÐt ch­¬ng tr×nh d­íi ®©y g(X,Z) ¬ a(X,Z) Ù c(Z) g(X,Z) ¬ a(X,Y) Ù g(Y,Z) Ù g(Y,W) Ù c(W) Râ rµng mét phÇn tö tgd ®Ó chØ ra thõa lµ g(Y,Z) ® g(Y,W) Ù c(W) mµ ®­îc biÓu thÞ bëi t. Cho P1 lµ ch­¬ng tr×nh gèc vµ cho P2 lµ ch­¬ng tr×nh thu ®­îc b»ng c¸ch xãa g(Y,W) vµ c(W) tõ th©n cña quy t¾c ®Ö quy cña P1. Râ rµng P1 Ͳ P2. Ta sÏ chØ ra P2 Í P1 b»ng c¸ch sau: (1)-SAT(T) Ç M(P1) Í M(P2) (2)-P1 duy tr× T (3)-§èi víi mäi EDB d, DB c¬ së tháa m·n T DÔ dµng chØ ra (1). VÝ dô 3.2.5 ®· cho thÊy quy t¾c ®Ö quy cña ch­¬ng tr×nh P1 duy tr× T. V× T cã mét tgd ®¬n chØ cã mét nguyªn tè trong vÕ tr¸i cña nã. (3’) vµ quy t¾c ®Ö quy cña P1 duy tr× T hµm ý (2). Nh­ vËy, cÇn ph¶i chØ ra (3’). VËy cho g(Y0,Z0) lµ hiÖn hµnh vÕ tr¸i cña tgd t. Hîp nhÊt nã víi ®Çu cña quy t¾c cña Pi1 sinh ra DB {a(Y0,Z0), c(Z0)}. Nh÷ng nguyªn tè nÒn g(Y0,Z0) vµ c(Z0) cho thÊy t kh«ng vi ph¹m, khi vÕ tr¸i cña nã ®­îc thÕ vµo g(Y0,Z0). Nh­ vËy, tÊt c¶ DB c¬ së tháa m·n t. V× vËy, ta cã thÓ kÕt luËn r»ng nh÷ng nguyªn tè g(Y,W) vµ c(W) thõa trong quy t¾c ®Ö quy cña P1. C. KÕt luËn TiÓu luËn ®· t×m hiÓu mét thuËt to¸n ®Ó tèi ­u hãa nh÷ng ch­¬ng tr×nh Datalog trong tÝnh t­¬ng ®­¬ng ®ång d¹ng. PhÐp cùc tiÓu nµy gi¶m sè l­îng nh÷ng kÕt nèi cÇn thiÕt ®Ó t×m tÊt c¶ c¸c c©u tr¶ lêi cho mét truy vÊn. TiÓu luËn còng ®· t×m hiÓu mét thuËt to¸n ®Ó kiÓm tra quan hÖ bao hµm ®ång d¹ng vµ t­¬ng ®­¬ng ®ång d¹ng cña ch­¬ng tr×nh. TiÓu luËn ®· t×m hiÓu c¸c vÊn ®Ò kiÓm ®Þnh tÝnh bao hµm ®ång d¹ng khi DB tháa m·n mét sè rµng buéc ®­îc m« t¶ nh­ nh÷ng phô thuéc sinh bé. P2ͲSAT(T)P1 hµm ý: (1)-SAT(T) Ç M(P1) Í M(P2) (2)-P1 duy tr× T. (1) ®­îc kiÓm ®Þnh bëi qu¸ tr×nh gèi nhau ®­îc m« t¶ trong phÇn “Phô thuéc sinh bé”. Qu¸ tr×nh nµy lu«n dõng víi c©u tr¶ lêi ®óng nÕu chØ cã nh÷ng tgd ®Çy ®ñ. NÕu cã c¶ nh÷ng tgd nhóng, th× qu¸ tr×nh gèi nhau cã thÓ kh«ng dõng khi (1) kh«ng ®óng. Víi (2), thñ tôc ®­îc m« t¶ trong “Duy tr× phô thuéc sinh bé” chøng minh nã ®óng trong mét sè tr­êng hîp. Thñ tôc ®ã cã thÓ kh«ng dõng nÕu cã nh÷ng tgd nhóng. Mét tr­êng hîp mµ (2) ®óng lµ khi nh÷ng tgd chØ cã nh÷ng vÞ tõ EDB trªn vÕ tr¸i. §Æc biÖt, nÕu nh÷ng tgd biÓu diÔn nh÷ng rµng buéc mµ EDB tháa m·n th× chóng chØ cã nh÷ng vÞ tõ EDB, khi ®ã qu¸ tr×nh gèi nhau cã thÓ ®­îc dïng ®Ó chuyÓn mét ch­¬ng tr×nh thµnh mét ch­¬ng tr×nh t­¬ng ®­¬ng hiÖu qu¶ h¬n. TiÓu luËn ®· ®­a ra c¸ch sö dông thñ tôc x¸c ®Þnh (1) vµ (2) ®Ó tèi ­u hãa ch­¬ng tr×nh trong tÝnh t­¬ng ®­¬ng. §Ó ®­a ra kiÓu tèi ­u hãa nµy cÇn mét sè heuristic. Mét sè vÊn ®Ò cÇn ®­îc tiÕp tôc nghiªn cøu: Thø nhÊt, cÇn m« t¶ dÆc ®iÓm c¸c tr­êng hîp mµ nh÷ng thñ tôc kiÓm tra (1) vµ (2) b¶o ®¶m dõng. Thø hai, biÓu thÞ nh÷ng tr­êng hîp mµ cã thuËt to¸n ®Ó t×m nh÷ng tgd ®Ó chØ ra sù d­ thõa khi mét sè nguyªn tè thõa hoÆc sù d­ thõa cã thÓ ®­îc chØ ra nÕu nh÷ng thuËt to¸n ®­îc t×m thÊy, th× nhiÒu heuristic ph¶i ®­îc ph¸t triÓn ®Ó t×m nh÷ng tgd mµ cã thÓ chØ ra d­ thõa. Lêi kÕt: §Ó hoµn thµnh ®­îc tiÓu luËn 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 TS Tr­¬ng C«ng TuÊn. 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«i 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 ý ®Ó b¶n th©n t«i 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. Phô lôc 1-TÝnh ®óng ®¾n cña kiÓm tra sù bao hµm ®ång d¹ng Tr­íc hÕt ta chøng minh hai bæ ®Ò vÒ mèi quan hÖ gi÷a tÝnh bao hµm ®ång d¹ng cña hai ch­¬ng tr×nh vµ tÝnh bao hµm cña nh÷ng tËp m« h×nh cña chóng. Cho S lµ mét tËp c¸c DB, S cã thÓ lµ tËp bÊt kú vµ kh«ng nhÊt thiÕt tËp nh÷ng DB mµ tháa m·n mét sè tËp T cña tgd. §èi víi mét ch­¬ng tr×nh P, tËp P(S) gåm cã tÊt c¶ d÷ liÖu ra ®èi víi d÷ liÖu vµo trong S, P(S)={P(d) | dÎS}. M(P) lµ tËp tÊt c¶ c¸c m« h×nh cña P. Bæ ®Ò 1: P2 ͲS P1 Þ S Ç M(P1) Í M(P2) Chøng minh: Gi¶ sö P2 ͲS P1. §Æt d Î S Ç M(P1). Ta chøng minh d Í P2(d) Í P1(d) = d lµ ®óng (1) ThËt vËy: V× d÷ liÖu ra lu«n chøa d÷ liÖu vµo cña nã nªn d Í P2(d). V× P2 ͲS P1 vµ d Î S nªn P2(d) Í P1(d). V× d Î M(P1) nªn ®¼ng thøc thoa m·n. VËy (1) cho ta: d Î M(P2). Bæ ®Ò 2: P1(S) Ç M(P1) Í M(P2) Þ P2 ͲS P1 Chøng minh: Gi¶ sö P1(S) Ç M(P1) Í M(P2), vµ cho d Î S lµ mét d÷ liÖu vµo cña P2 (d kh«ng nhÊt thiÕt lµ m« h×nh cña P2). §Æt d1=P1(d) vµ d2=P2(d). Ta ph¶i chøng minh d2 Í d1. ThËt vËy: V× d1 Î P1(S) Ç M(P1) kÐo theo d1 Î M(P2). V× d2 lµ m« h×nh cùc tiÓu cña P2 mµ chøa d vµ d1 còng lµ m« h×nh cña P2 mµ chøa d. V× vËy d2 Í d1, Hai bæ ®Ò trªn dÉn ®Õn hÖ qu¶ sau: HÖ qu¶ 1: Cho P1 lµ mét ch­¬ng tr×nh vµ S lµ mét tËp c¸c DB sao cho P1(S)ÍS khÝ ®ã: P2 ͲS P1 Û S Ç M(P1) Í M(P2) Chó ý r»ng nÕu S lµ tËp hîp cña tÊt c¶ DB tháa m·n nh÷ng tgd cña mét sè T, nghÜa lµ S=SAT(T) th× P1(S) Í S nghÜa lµ P1 duy tr× T. Râ rµng SAT(T)ÇM(P1)ÍM(P2) nÕu vµ chØ nÕu SAT(T)ÇM(P1)ÍM(r) ®èi víi mäi quy t¾c r cña P2, bëi v× mét DB lµ mét m« h×nh cña P2 nÕu vµ chØ nÕu nã lµ mét m« h×nh cña mçi quy t¾c r cña P2. Qu¸ tr×nh gèi nhau, ®­îc m« t¶ trong phÇn “Phô thuéc sinh bé”, kiÓm tra SAT(T) Ç M(P1) Í M(r) vµ ®Þnh lý d­íi ®©y chøng minh tÝnh ®óng ®¾n cña nã. §Ó thùc hiÖn qu¸ tr×nh nµy, th©n cña r ph¶i ®­îc xem nh­ lµ mét DB, vµ ®iÒu nµy ®­îc thùc hiÖn b»ng c¸ch thÕ nh÷ng biÕn cña r víi nh÷ng h»ng ph©n biÖt mµ ch­a cã trong r hoÆc P, theo mét sè phÐp thÕ q. ¸p dông kÕt hîp cña mét ch­¬ng tr×nh P vµ mét tËp c¸c tgd cña T, ®­îc biÓu thÞ bëi [P,T] §Þnh lý 1: Cho r lµ quy t¾c h¬b, vµ cho q lµ mét ¸nh x¹ mét-mét cña c¸c biÕn cña r vµo c¸c h»ng mµ ch­a xuÊt hiÖn trong r hoÆc P. Khi ®ã: hqÎ[P,T](bq) Û SAT(T)ÇM(P)ÍM(r) Chøng minh: ý t­ëng: Thø nhÊt ta gi¶ sö r»ng SAT(T)ÇM(P) Í M(r) vµ sÏ chØ ra r»ng hqÎ[P,T](bq). V× thÕ, xem xÐt nh÷ng DB bq vµ [P,T](bq). Râ rµng, [P,T](bq)ÎSAT(T)ÇM(P), v× [P,T](bq) ®­îc ®Þnh nghÜa lµ DB thu ®­îc tõ bq b»ng c¸ch ¸p dông nh÷ng quy t¾c cña P vµ c¸c tgd cña T cho ®Õn khi kh«ng cã quy t¾c hoÆc tgd cã thÓ ®­îc ¸p dông thªm n÷a. V× vËy [P,T](bq) Î M(r), bëi v× ta gi¶ sö SAT(T) Ç M(P) Í M(r). B©y giê ta sÏ chØ ra r»ng [P,T](bq) Î M(r) hµm ý hq Î [P,T](bq). Theo ®Þnh nghÜa, DB [P,T](bq) chøa bq. NÕu ta ¸p dông r vµo bq, râ rµng hqÎr(bq), v× khi th©n cña r ®­îc thÕ theo q, nã trë thµnh bq vµ v× vËy hq lµ thuéc d÷ liÖu ra. Nh­ng [P,T](bq) ®­îc gi¶ sö lµ mét m« h×nh cña r, v× vËy ¸p dông r vµo [P,T](bq) kh«ng thÓ sinh ra nguyªn tè míi nµo. V× vËy hq Î [P,T](bq), v× ¸p dông r vµo bq sinh ra hq. Ta sÏ chøng minh chiÒu ng­îc l¹i. Gi¶ sö hq Î [P,T](bq), ta sÏ chØ ra SAT(T) Ç M(P) Í M(r). VËy, cho d lµ DB bÊt kú trong SAT(T)ÇM(P). Ta ph¶i chØ ra d Î M(r). Theo trùc quan, chøng minh b»ng c¸ch chØ ra r»ng bÊt kú sù ¸p dông nµo cña r vµo d còng cã thÓ ®­îc m« pháng bëi mét chuçi cña nh÷ng ¸p dông cña [P,T], vµ v× viÖc ¸p dông [T,P] vµo d kh«ng sinh ra nguyªn tè míi, vËy thùc hiÖn ¸p dông cña r. Ta xÐt mét phÐp thÕ tïy ý q mµ thay thÕ th©n cña r thµnh nh÷ng nguyªn tè nÒn cña d. §Ó hoµn thµnh chøng minh, ta ph¶i chØ ra hq còng thuéc d. Nh­ng hq Î [P,T](bq) vµ v× vËy cã mét chuçi c¸c phÐp thÕ j1, j2,..., jn mµ chØ ra hq Î [P,T](bq), ®ã lµ, ®èi víi mçi i cã mét quy t¾c cña P hoÆc mét tgd cña T, sao cho khi quy t¾c hoÆc tgd ®­îc thÕ theo ji, mét nguyªn tè míi ®­îc sinh ra, vµ sù ¸p dông cuèi cïng (®èi víi jn) sinh ra hq. Nh­ vËy, nã kÐo theo r»ng qoq-1oj1,..., qoq-1ojn lµ mét chuçi phÐp thÕ mµ [P,T](d) chøa hq. Nh­ng d Î SAT(T) Ç M(P) hµm ý d= [P,T](d) vµ v× vËy hq thuéc d NÕu quy t¾c r cã th©n rçng (nªn ®Çu cña nã lµ mét nguyªn tè nÒn), th× dÞnh lý 1 hµm ý SAT(T) Ç M(P) Í M(r) nÕu vµ chØ nÕu r lµ mét quy t¾c cña P. Chó ý, nÕu T cã c¸c tgd nhóng, th× DB [P,T](bq) cã thÓ lµ v« h¹n, v× vËy kh«ng cã giíi h¹n trªn thêi gian ®Ó chØ ra [P,T](bq) chøa hq (MÆc dï hq sÏ ®­îc t×m ra trong mét thêi gian h÷u h¹n nÕu nã lµ thùc sù thuéc [P,T](bq)). H¬n n÷a, nÕu [P,T](bq) kh«ng chøa hq, th× cã thÓ kh«ng x¸c ®Þnh ®­îc sù kiÖn nµy chØ b»ng tÝnh to¸n [P,T](bq), v× sù tÝnh to¸n cã thÓ lµ v« h¹n. Chó ý, nÕu [P,T](bq) kh«ng chøa hq, th× cã thÓ lµ chØ nh÷ng DB d lµ v« h¹n sao cho dÎSAT(T)ÇM(P) vµ dÏM(r). Nãi c¸ch kh¸c, nÕu T gåm cã nh÷ng tgd nhóng, th× chiÒu Ü trong ®Þnh lý 1 ®­îc cho lµ ®óng mµ tËp tÊt c¶ c¸c DB cã thÓ bao gåm c¶ DB h÷u h¹n vµ v« h¹n. Râ rµng, nÕu kh«ng cã tgd nµo th× ta cã hÖ qu¶ quan träng d­íi ®©y cho ®Þnh lý 1. HÖ qu¶ nµy lµ ®óng khi chØ nh÷ng DB h÷u h¹n ®­îc xem xÐt, vµ nã cho thÊy sù ®óng ®¾n cña thuËt to¸n ®Ó kiÓm ®Þnh quan hÖ bao hµm ®ång d¹ng. ThuËt to¸n nµy lu«n lu«n dõng. HÖ qu¶ 2: Cho r lµ mét quy t¾c víi ®Çu lµ h vµ th©n lµ b, vµ cho q lµ mét ¸nh x¹ mét-mét cña c¸c biÕn vµo c¸c h»ng mµ ch­a xuÊt hiÖn trong r hoÆc P. Khi ®ã hq Î P(bq) Û M(P) Í M(r) 2. TÝnh ®óng ®¾n cña kiÓm tra sù duy tr× kh«ng ®Ö quy cña nh÷ng tgd Thñ tôc ®­îc m« t¶ trong “Duy tr× phô thuéc sinh bé” ®Ó kiÓm tra liÖu mét ch­¬ng tr×nh P duy tr× kh«ng ®Ö quy mét tËp T c¸c tgd còng dùa trªn sù gèi nhau. Cã thÓ nãi r»ng nÕu thñ tôc hoÆc x¸c ®Þnh P kh«ng duy tr× kh«ng ®Ö quy mét sè t Î T hoÆc kh«ng dõng, th× nã x©y dùng mét DB d sao cho d tháa m·n T vµ vi ph¹m t. Chó ý, thñ tôc cã thÓ kh«ng dõng chØ nÕu T cã nh÷ng tgd nhóng, vµ trong tr­êng hîp nµy vÝ dô ph¶n chøng d lµ v« h¹n. NÕu thñ tôc x¸c ®Þnh P duy tr× T kh«ng ®Ö quy, th× nã thùc hiÖn b»ng c¸ch x©y dùng ®èi víi mçi kh¶ n¨ng vi ph¹m cña mét sè t Î T, mét DB hîp víi quy t¾c tiªu chuÈn trong ®ã kh«ng tån t¹i vi ph¹m, vµ DB hîp víi quy t¾c tiªu chuÈn ®ã cã thÓ ®­îc ¸nh x¹ ®ång cÊu vµo bÊt kú DB kh¸c mµ cã thÓ biÓu hiÖn mét sè vi ph¹m. Nh­ vËy, cã thÓ kh«ng vi ph¹m. 3. TÝnh ®óng ®¾n cña thuËt to¸n ®Ó cùc tiÓu hãa ch­¬ng tr×nh §Þnh lý 2: ThuËt to¸n ®Ó cùc tiÓu nh÷ng ch­¬ng tr×nh trong d¹ng t­¬ng ®­¬ng ®ång d¹ng lµ ®óng Chøng minh: Ta ph¶i chØ ra r»ng kh«ng cã nguyªn tè hoÆc quy t¾c ®· ®­îc xem xÐt nhiÒu h¬n mét lÇn. VËy, cho P¦ lµ ch­¬ng tr×nh cuèi cïng ®­îc sinh ra bëi thuËt to¸n. Ta ph¶i chØ ra r»ng P¦ kh«ng cã nguyªn tè vµ quy t¾c thõa. Tr­íc hÕt ta chØ ra P¦ kh«ng cã quy t¾c thõa. Gi¶ sö r»ng mét sè quy t¾c r thõa trong P¦. Gäi P lµ ch­¬ng tr×nh t¹i thêi ®iÓm b¾t ®Çu cña qu¸ tr×nh lÆp trong ®ã quy t¾c r ®­îc xem xÐt ®Ó xãa bá. §Æt P’ vµ P’¦ lµ ch­¬ng tr×nh t­¬ng øng P vµ P¦ khi r bÞ xãa. Râ rµng, P vµ P¦ lµ t­¬ng ®­¬ng ®ång d¹ng, v× thuËt to¸n xãa trong khi vÉn duy tr× tÝnh t­¬ng ®­¬ng ®ång d¹ng. V× r ch­a ®­îc xãa mét c¸ch vÜnh cöu, r Ú² P’. §Æt h vµ b lµ ®Çu vµ th©n t­¬ng øng cña quy t¾c r, vµ ®Æt q lµ ¸nh x¹ mét-mét cña c¸c biÕn cña r vµo c¸c h»ng ch­a cã trong r hoÆc P. Ta cã hqÏP’(bq), v× r Ú² P’, vµ ta còng cã hq Î P’¦(bq), v× r lµ thõa trong P¦. Nh­ng nã m©u thuÉn víi P’¦(bq) Í P’(bq) (V× mäi quy t¾c cña P’¦ còng lµ mét quy t¾c cña P’. Ta ®· xãa nh÷ng nguyªn tè thõa tr­íc khi xãa nh÷ng quy t¾c thõa, v× vËy mét quy t¾c xuÊt hiÖn trong P¦ cã chÝnh x¸c cïng mét th©n còng ë trong P; NÕu mét sè quy t¾c ®· xuÊt hiÖn trong P¦ víi mét sè nguyªn tè ®· xãa tõ th©n cña nã ®­îc so s¸nh víi P, nã sÏ kh«ng thÓ suy ra P’¦(bq) Í P’(bq)). Nh­ vËy, ta ®· chØ ra r»ng P¦ kh«ng cã quy t¾c thõa. TiÕp theo ta chØ ra P¦ kh«ng cã nguyªn tè thõa. Gi¶ sö mét sè quy t¾c r cña P¦ cã mét nguyªn tè a thõa trong th©n cña nã. Gäi P lµ ch­¬ng tr×nh t¹i thêi ®iÓm b¾t ®Çu cña qu¸ tr×nh lÆp trong ®ã a ®­îc xem xÐt ®Ó xãa. §Æt h lµ ®Çu cña quy t¾c r, ®Æt b vµ b¦ lµ th©n cña nã trong P vµ P¦ (mäi nguyªn tè cña b¦ còng lµ cña b). Th©n cña b’¦ vµ cña b’ thu ®­îc tõ b¦ vµ b b»ng c¸ch xãa ®i a. §Æt q lµ mét ¸nh x¹ mét-mét cña tÊt c¶ c¸c biÕn cña r vµo c¸c h»ng mµ ch­a cã trong r hoÆc P. V× a ch­a bÞ xãa vÜnh cöu, hq Ï P(b’q). V× a thõa trong P¦, kÐo theo hq Î P¦(b’¦q), v× b’¦q Í b’q, vµ ch­¬ng tr×nh Datalog lµ ®¬n ®iÖu, ®ã lµ thªm nhiÒu nguyªn tè vµo d÷ liÖu vµo mµ kh«ng xãa bÊt kú nguyªn tè nµo cña d÷ liÖu ra. Nh­ vËy ta còng ®· chØ ra r»ng P¦ kh«ng chøa nguyªn tè thõa. Tµi liÖu tham kh¶o 1- Tr­¬ng C«ng TuÊn-Bµi gi¶ng ch­¬ng tr×nh Datalog-2005 2- Yehoshua Sagiv-Optimizing Datalog Programs. 3- Jeffrey D. Ullman, TrÇn §øc Quang (dÞch)-Nguyªn lý c¸c hÖ c¬ së d÷ liÖu vµ c¬ së tri thøc, TËp 1-NXB TK-1998 4- S.Ceri G. Gottlob L. Tanca-Logic Programming and Databases-1989 Môc lôc Néi dung Trang Giíi thiÖu ..................................................................................................................................................... 1 Néi dung ....................................................................................................................................................... 2 I-KiÕn thøc c¬ së............................................................................................................................... 2 1.1 Nh÷ng kh¸i niÖm vÒ ch­¬ng tr×nh Datalog............................................. 2 1.2 Sù tÝnh to¸n cña ch­¬ng tr×nh................................................................................. 3 1.3 TÝnh t­¬ng ®­¬ng, t­¬ng ®­¬ng ®ång d¹ng vµ nh÷ng m« h×nh. 5 II-Tèi ­u hãa ch­¬ng tr×nh trong tÝnh t­¬ng ®­¬ng ®ång d¹ng................. 7 2.1 KiÓm tra tÝnh bao hµm ®ång d¹ng vµ t­¬ng ®­¬ng ®ång d¹ng...... 8 2.2 Cùc tiÓu hãa ch­¬ng tr×nh trong tÝnh t­¬ng ®­¬ng ®ång d¹ng....... 9 III-Tèi ­u hãa ch­¬ng tr×nh ®Ö quy trong tÝnh t­¬ng ®­¬ng......................... 11 3.1 Phô thuéc sinh bé.............................................................................................................................. 11 3.2 Duy tr× phô thuéc sinh bé......................................................................................................... 15 3.3 X¸c ®Þnh tÝnh t­¬ng ®­¬ng...................................................................................................... 21 3.4 Tèi ­u hãa trong tÝnh t­¬ng ®­¬ng................................................................................ 23 KÕt luËn...................................................................................................................................................................... 25 Phô lôc......................................................................................................................................................................... 26 Tµi liÖu tham kh¶o......................................................................................................................................... 30