Tiểu luận kết thúc môn học: Chương trình Datalog

A. Giíi thiÖu Ch­¬ng tr×nh Datalog lµ mét phÇn quan träng cña c¬ së d÷ liÖu suy diÔn. NhiÒu c«ng tr×nh nghiªn cøu nh»m t×m kiÕm nh÷ng ph­¬ng ph¸p ­íc l­îng hiÖu qu¶ ®èi víi nh÷ng truy vÊn. TiÓu luËn nh»m gi¶i quyÕt vÊn ®Ò lµ b»ng c¸ch nµo ®Ó lo¹i bá phÇn thõa cña mét ch­¬ng tr×nh Datalog. PhÇn thõa cña mét ch­¬ng tr×nh lµ mét quy t¾c thõa hoÆc mét nguyªn tè thõa trong th©n cña mét quy t¾c. Lo¹i bá mét phÇn thõa nh»m gi¶m thêi gian cÇn thiÕt ®Ó l­îng gi¸ mét truy vÊn bëi v× nã gi¶m sè l­îng nh÷ng kÕt nèi trong suèt qu¸ tr×nh l­îng gi¸. Mét ch­¬ng tr×nh datalog th­êng nhËn d÷ liÖu vµo lµ nh÷ng quan hÖ ®èi víi vÞ tõ EDB vµ tr¶ lêi lµ nh÷ng quan hÖ ®èi víi vÞ tõ IDB. Quy tr×nh tèi ­u hãa yªu cÇu t×m kiÕm mét ch­¬ng tr×nh cã gi¸ nhá nhÊt t­¬ng ®­¬ng víi ch­¬ng tr×nh gèc, sao cho ®èi víi mäi kh¶ n¨ng cña ®Çu vµo, ch­¬ng tr×nh gèc vµ ch­¬ng tr×nh ®­îc tèi ­u tÝnh to¸n ra cïng mét kÕt qu¶. TiÓu luËn tr×nh bµy mét sè kh¸i niÖm nh­ quan hÖ bao hµm, quan hÖ t­¬ng ®­¬ng, bao hµm ®ång d¹ng, t­¬ng ®­¬ng ®ång d¹ng. Trong ®ã, tÝnh t­¬ng ®­¬ng ®ång d¹ng hµm chøa tÝnh t­¬ng ®­¬ng. §Ó cùc tiÓu mét ch­¬ng tr×nh trong tÝnh t­¬ng ®­¬ng ®ång d¹ng, ta ®­a ra mét thuËt to¸n ®Ó xãa tÊt c¶ nh÷ng quy t¾c thõa vµ nguyªn tè thõa trong nh÷ng quy t¾c trong khi vÉn duy tr× t­¬ng ®­¬ng ®ång d¹ng. Thêi gian thùc hiÖn cña thuËt to¸n, trong tr­êng hîp xÊu nhÊt lµ theo luËt sè mò cña kÝch cë cña ch­¬ng tr×nh. Tuy nhiªn nÕu sè l­îng ®èi sè cña c¸c vÞ tõ h÷u h¹n th× thêi gian thùc hiÖn lµ ®a thøc. Trªn thùc tÕ, th­êng sè l­îng ®èi sè cña c¸c vÞ tõ kh«ng lín nªn ®©y lµ mét thuËt to¸n hiÖu qu¶. TiÓu luËn còng ®­a ra mét kü thuËt ®Ó cùc tiÓu hãa ch­¬ng tr×nh Datalog trong tÝnh t­¬ng ®­¬ng. §©y lµ mét bµi to¸n bÊt kh¶ quyÕt, kü thuËt nµy kh«ng t×m thÊy tÊt c¶ c¸c phÇn thõa cña mét ch­¬ng tr×nh trong tÝnh t­¬ng ®­¬ng. Thùc ra, ch­¬ng tr×nh Datalog ®· ®­îc nghiªn cøu s©u vµ ®­îc øng dông m¹nh mÏ. TiÓu luËn kh«ng nh»m môc ®Ých ®­a ra nh÷ng vÊn ®Ò míi mµ chØ tãm t¾t vµ tr×nh bµy l¹i nh÷ng tri thøc mµ b¶n th©n thu nhËn ®­îc th«ng qua mét thêi gian häc tËp ng¾n vµ qua tham kh¶o mét sè tµi liÖu. TiÓu luËn ®­îc tr×nh bµy trong ba phÇn. PhÇn 1: §­a ra mét sè kiÕn thøc c¬ së. PhÇn 2: Tèi ­u hãa nh÷ng ch­¬ng tr×nh ®Ò quy trong tÝnh t­¬ng ®­¬ng ®ång d¹ng. PhÇn nµy tr×nh bµy mét thuËt to¸n ®Ó t×m vµ xãa nh÷ng nguyªn tè vµ quy t¾c thõa trong khi vÉn duy tr× tÝnh t­¬ng ®­¬ng ®ång d¹ng. PhÇn 3: Tèi ­u hãa nh÷ng ch­¬ng tr×nh ®Ö quy trong tÝnh t­¬ng ®­¬ng. PhÇn nµy tr×nh bµy mét thuËt to¸n ®Ó t×m vµ xãa nh÷ng nguyªn tè vµ quy t¾c thõa trong khi vÉn duy tr× tÝnh t­¬ng ®­¬ng, nh­ng cã thÓ kh«ng t­¬ng ®­¬ng ®ång d¹ng. B. Néi dung I. KiÕn thøc c¬ së 1.1-Nh÷ng kh¸i niÖm vÒ ch­¬ng tr×nh Datalog. §Þnh nghÜa 1.1.1 (VÞ tõ EDB vµ vÞ tõ IDB) -VÞ tõ EDB (Extensional database relation) lµ vÞ tõ mµ quan hÖ cña nã ®­îc chøa trong c¬ së d÷ liÖu. -VÞ tõ IDB (Intensional database relation) lµ vÞ tõ ®­îc ®Þnh nghÜa bëi c¸c quy t¾c logic. VÞ tõ IDB trong mét ch­¬ng tr×nh P cã thÓ xuÊt hiÖn ë ®Çu hoÆc th©n cña quy t¾c. VÞ tõ EDB lµ c¸c vÞ tõ kh«ng xuÊt hiÖn trong ®Çu quy t¾c mµ chØ xuÊt hiÖn trong th©n quy t¾c. §Þnh nghÜa 1.1.2 (Nguyªn tè-atom) NÕu A1, A2,...,An lµ c¸c biÕn hoÆc h»ng vµ p lµ ký hiÖu vÞ tõ th× p(A1,A2,...,An) ®­îc gäi lµ mét nguyªn tè. Quy ­íc: C¸c vÞ tõ ®­îc viÕt b»ng ch÷ th­êng, c¸c biÕn ®­îc viÕt b»ng ch÷ in hoa. §Þnh nghÜa 1.1.3 (VÞ tõ x©y dùng trong) Mét vÞ tõ x©y dùng trong lµ mét vÞ tõ so s¸nh sè häc (=, ¹, £, ³, >, <) víi ng÷ nghÜa ®· x¸c ®Þnh. NÕu q lµ vÞ tõ x©y dùng trong th× ta viÕt XqY thay cho q(X,Y). VÞ tõ x©y dùng trong chØ xuÊt hiÖn trong th©n quy t¾c. §Þnh nghÜa 1.1.4 (MÖnh ®Ò Horn) MÖnh ®Ò Horn lµ mét c«ng thøc bËc nhÊt chøa nhiÒu nhÊt mét literal d­¬ng. Cã ba d¹ng mÖnh ®Ò Horn: -MÖnh ®Ò ®¬n vÞ (cßn gäi lµ c¸c sù kiÖn-fact) p -§Ých (goal) lµ mét mÖnh ®Ò mµ chØ chøa mét hoÆc nhiÒu literal ©m vµ kh«ng cã literal d­¬ng. q1 q2 ...qn -Quy t¾c lµ mét c«ng thøc bËc nhÊt cã ®óng mét literal d­¬ng vµ mét hoÆc nhiÒu literal ©m. p q1 q2 ...qn Ng÷ nghÜa cña quy t¾c nµy lµ: nÕu q1 q2 ... qn ®Òu lµ true th× p true. p lµ ®Çu cña quy t¾c, q1 q2 ...qn lµ th©n cña quy t¾c §Þnh nghÜa 1.1.5 (Ch­¬ng tr×nh Datalog) Mét ch­¬ng tr×nh Datalog lµ mét tËp h÷u h¹n c¸c mÖnh ®Ò Horn tháa m·n ba ®iÒu kiÖn sau: -Kh«ng chøa ®Ých -NÕu chøa sù kiÖn víi ký hiÖu vÞ tõ p th× sÏ kh«ng chøa quy t¾c cã ®Çu quy t¾c lµ p. -Kh«ng chøa ký hiÖu hµm. Nh­ vËy, ta cã thÓ xem mét ch­¬ng tr×nh Datalog lµ ch­¬ng tr×nh logic kh«ng chøa ký hiÖu hµm. VÝ dô 1.1.6: §©y lµ mét ch­¬ng tr×nh cã hai quy t¾c: g(X,Z) ¬ a(X,Z) g(X,Z) ¬ g(X,Y) Ù g(Y,Z) Trong tiÓu luËn ta còng gi¶ sö mäi biÕn trong ®Çu cña quy t¾c còng ph¶i xuÊt hiÖn trong th©n. §èi víi nh÷ng quy t¾c cã th©n rçng th× ®Çu quy t¾c chØ cã h»ng vµ kh«ng cã biÕn. §ång thêi c¸c quy t¾c lu«n lµ nh÷ng c«ng thøc an toµn. Mét quan hÖ Q ®èi víi mét vÞ tõ q lµ mét tËp c¸c nguyªn tè nÒn cña q. Trõ c¸c tr­êng hîp ®· ®Þnh kh¸c, ta gi¶ sö c¸c quan hÖ lµ h÷u h¹n. Mét tËp hîp c¸c quan hÖ ®­îc xem nh­ lµ mét tËp gåm cã tÊt c¶ nh÷ng nguyªn tè nÒn cña nh÷ng quan hÖ nµy. NÕu Q1,Q2,...,Qn lµ c¸c quan hÖ t­¬ng øng ®èi víi c¸c vÞ tõ q1,q2,..,qn th× biÓu diÔn phÐp hîp cña chóng, ®ã lµ tËp hîp chøa nh÷ng nguyªn tè nÒn cña tÊt c¶ Qi. TËp cßn ®­îc gäi lµ mét thÓ hiÖn. §Þnh nghÜa 1.1.7 (§å thÞ phô thuéc) Mét ®å thÞ liªn hîp víi mét ch­¬ng tr×nh P ®­îc gäi lµ ®å thÞ phô thuéc. Trong ®ã mét nót øng víi mçi vÞ tõ cña ch­¬ng tr×nh, vµ mét cung tõ vÞ tõ q ®Õn vÞ tõ r khi vÞ tõ q lµ trong th©n cña mét sè quy t¾c vµ vÞ tõ r lµ trong ®Çu cña cïng quy t¾c ®ã. §Þnh nghÜa 1.1.8 (Ch­¬ng tr×nh Datalog ®Ö quy) Ch­¬ng tr×nh Datalog P lµ ®Ö quy nÕu ®å thÞ phô thuéc cña nã cã mét chu tr×nh. Mét vÞ tõ q lµ ®Ö quy trong ch­¬ng tr×nh P nÕu cã mét ®­êng ®i tõ q ®Õn chÝnh nã. VÞ tõ ®Ö quy lµ vÞ tõ IDB, nh­ng mét vÞ tõ IDB lµ kh«ng nhÊt thiÕt ®Ö quy. Mét quy t¾c lµ ®Ö quy nÕu ®å thÞ phô thuéc cã mét chu tr×nh bao gåm vÞ tõ ë ®Çu cña quy t¾c vµ mét vÞ tõ ë th©n cña quy t¾c. Cô thÓ, mét quy t¾c lµ ®Ö quy nÕu vÞ tõ ë trong ®Çu cña quy t¾c còng xuÊt hiÖn trong th©n. 1.2-Sù tÝnh to¸n cña ch­¬ng tr×nh. D÷ liÖu vµo cña mét ch­¬ng tr×nh P lµ mét quan hÖ ®èi víi mçi vÞ tõ EDB. D÷ liÖu ra ®­îc tÝnh to¸n bëi P lµ mét quan hÖ ®èi víi mçi vÞ tõ IDB. §Ó ®¬n gi¶n, ta ®Þnh nghÜa d÷ liÖu ra lµ DB. B»ng c¸ch nµo ®Ó tÝnh d÷ liÖu ra. Nh÷ng nguyªn tè nÒn cña DB ®­îc gäi lµ nh÷ng sù kiÖn. Ban ®Çu, nh÷ng sù kiÖn ®ã lµ EDB. Mét quy t¾c cña mét ch­¬ng tr×nh nh»m ®Ó suy diÔn mét sù kiÖn míi tõ mét sè sù kiÖn ®· biÕt. Nh÷ng sù kiÖn ®­îc suy diÔn míi nµy trë thµnh nh÷ng nguyªn tè nÒn cña IDB. Quy t¾c cã thÓ ®­îc sö dông l¹i ®Ó suy diÔn nh÷ng sù kiÖn míi h¬n. Mét quy t¾c r ®­îc dïng ®Ó suy diÔn mét sù kiÖn míi b»ng c¸ch thÕ c¸c biÕn cña nã b»ng c¸c h»ng (thÕ mét h»ng cho tÊt c¶ sù xuÊt hiÖn cña mçi biÕn). NÕu víi phÐp thÕ, mçi nguyªn tè trong th©n cña quy t¾c r trë thµnh mét nguyªn tè nÒn cña DB, th× hiÖn hµnh cña ®Çu cña quy t¾c ®­îc thªm vµo cho IDB. VÝ dô 1.2.1: XÐt 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 EDB lµ tËp c¸c nguyªn tè nÒn d­íi ®©y {a(1,2), a(1,4), a(4,,1)}. Ban ®Çu, IDB lµ tËp rçng. NÕu trong quy t¾c thø nhÊt, ta thay thÕ 1 vµo X vµ 2 vµo Z th× th©n cña quy t¾c trë thµnh a(1,2) vµ nã trë thµnh mét nguyªn tè nÒn cña EDB. V× vËy g(1,2) ®­îc thªm vµo IDB. Hai hiÖn hµnh t­¬ng tù cña quy t¾c thø nhÊt lµ g(1,4) vµ g(4,1) ®­îc thªm vµo IDB. §èi víi quy t¾c thø hai, ta thÕ 1 vµo X, 4 vµo Y vµ 1 vµo Z sinh ra nh÷ng nguyªn tè nÒn g(1,4), g(4,1) trong th©n cña quy t¾c. V× c¶ hai lµ ®· cã trong DB, hiÖn hµnh ®Çu quy t¾c lµ g(1,1) ®­îc thªm vµo IDB. T­¬ng tù, thÕ 4 vµo X vµ Z vµ 1 vµo 1 vµo Y ta ®­îc g(4,4). Cuèi cïng, thÕ 4 vµo X, 1 vµo Y vµ 2 vµo Z, ta thu ®­îc g(4,2). Kh«ng cã nguyªn tè nÒn nµo ®­îc sinh ra bëi phÐp thÕ nµy n÷a. Nh­ vËy DB lµ: {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)} lµ d÷ liÖu ra tÝnh ®­îc bëi ch­¬ng tr×nh ®èi víi EDB ë trªn. V× ta gi¶ sö r»ng ®Çu vµo cho mét ch­¬ng tr×nh bao gåm nh÷ng quan hÖ h÷u h¹n nªn ®Çu ra còng lµ mét tËp c¸c quan hÖ h÷u h¹n. Sù tÝnh to¸n ®Çu ra b»ng c¸ch lÆp l¹i viÖc thÕ nh÷ng quy t¾c cho ®Õn khi kh«ng cã nguyªn tè nÒn nµo míi ®­îc sinh ra ®­îc gäi lµ sù tÝnh to¸n bottom-up. §èi víi mét ch­¬ng tr×nh, ph­¬ng ph¸p nµy thùc hiÖn trong thêi gian ®a thøc theo kÝch cë cña EDB. Cho P lµ mét ch­¬ng tr×nh víi c¸c vÞ tõ EDB e1,e2,...,en vµ vÞ tõ IDB i1,i2,...,im. Cho mét EDB trong ®ã mçi Ek lµ mét quan hÖ ®èi víi vÞ tõ ek. DB ®­îc tÝnh bëi P ®­îc biÓu diÔn bëi P() lµ mét tËp cña c¸c nguyªn tè nÒn. Ta còng cã thÓ xem P lµ mét ch­¬ng tr×nh mµ ®Çu vµo cña nã lµ c¶ EDB vµ IDB. §Çu ra ®­îc tÝnh b»ng c¸ch lÆp l¹i phÐp thÕ c¸c quy t¾c cho ®Õn khi kh«ng cßn nguyªn tè nÒn míi ®­îc thªm vµo IDB. Râ rµng ®Çu ra lµ mét DB mµ chøa ®Çu vµo. Khi P lµ mét ch­¬ng tr×nh mµ ®Çu vµo cña nã lµ c¶ EDB vµ IDB th× ®Çu ra ®­îc tÝnh bëi P ®­îc biÓu diÔn lµ P() VÝ dô 1.2.2: Cho P lµ mét 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) Trong vÝ dô 1.2.1, khi d÷ liÖu vµo lµ {a(1,2), a(1,4), a(4,,1)}, ta ®· tÝnh ®­îc d÷ liÖu ra cña P lµ O1={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 cho d÷ liÖu vµo lµ {a(1,2), a(1,4), g(4,,1)}, ta còng tÝnh ®­îc d÷ liÖu ra lµ O2={a(1,2), a(1,4), g(1,2), g(1,4), g(4,1), g(1,1), g(4,4), g(4,2)} Nh­ vËy O2 = O1 - {a(4,1)} Ta giíi h¹n, mét ch­¬ng tr×nh P cã nh÷ng quy t¾c víi th©n rçng th× nh÷ng quy t¾c nµy lµ nh÷ng nguyªn tè nÒn. Nh÷ng nguyªn tè nÒn nµy cã trong ®Çu ra cña P ngay c¶ khi ®Çu vµo lµ rçng. 1.3-TÝnh t­¬ng ®­¬ng, t­¬ng ®­¬ng ®ång d¹ng vµ nh÷ng m« h×nh. §Þnh nghÜa 1.3.1 (TÝnh bao hµm cña hai ch­¬ng tr×nh) Cho P1 vµ P2 lµ nh÷ng ch­¬ng tr×nh víi cïng mét tËp vÞ tõ EDB vµ IDB. Ch­¬ng tr×nh P1 bao hµm ch­¬ng tr×nh P2, ®­îc viÕt P2 Í P1, nÕu ®èi víi mäi EDB th× P2() Í P1() (d÷ liÖu ra cña P1 chøa d÷ liÖu ra cña P2). NghÜa lµ ®èi víi mçi vÞ tõ q, quan hÖ ®èi víi q trong DB P2() lµ mét tËp con cña quan hÖ ®èi víi q trong DB P1() §Þnh nghÜa 1.3.2 (TÝnh t­¬ng ®­ong cña hai ch­¬ng tr×nh) Ch­¬ng tr×nh P1 vµ ch­¬ng tr×nh P2 lµ t­¬ng ®­¬ng (equivalent), ký hiÖu P2ºP1 nÕu P2 Í P1 vµ P1 Í P2. Hai ch­¬ng tr×nh t­¬ng ®­¬ng nÕu chóng ®­a ra cïng mét d÷ liÖu ra mçi khi chóng ®­îc cho cïng mét d÷ liÖu vµo EDB. §Þnh nghÜa 1.3.3 (TÝnh bao hµm ®ång d¹ng cña hai ch­¬ng tr×nh) Ch­¬ng tr×nh P1 bao hµm ®ång d¹ng (uniformly contains) P2, ký hiÖu P2ͲP1 nÕu ®èi víi tÊt c¶ c¸c cÆp cña mét EDB vµ mét IDB ta cã: P2() Í P1() §Þnh nghÜa 1.3.4 (TÝnh t­¬ng ®­¬ng ®ång d¹ng cña hai ch­¬ng tr×nh) Ch­¬ng tr×nh P1 vµ ch­¬ng tr×nh P2 lµ t­¬ng ®­¬ng ®ång d¹ng (Uniformly equivalent), ký hiÖu P2 º² P1 nÕu P2 Ͳ P1 vµ P1 Ͳ P2. Hai ch­¬ng tr×nh t­¬ng ®­¬ng ®ång d¹ng nÕu chóng ®­a ra cïng mét d÷ liÖu ra khi chóng ®­îc cho cïng mét d÷ liÖu vµo, trong ®ã d÷ liÖu vµo cã thÓ gåm c¶ nh÷ng nguyªn tè nÒn ®èi víi nh÷ng vÞ tõ IDB. MÖnh ®Ò 1.3.5: NÕu ch­¬ng tr×nh P1 bao hµm ®ång d¹ng P2 th× P1 bao hµm P2. Chøng minh: NÕu P2() Í P1() ®èi víi tÊt c¶ vµ khi ®ã xÐt tr­êng hîp riªng ®èi víi EDB ta cã: P2(), trong ®ã Æ biÓu thÞ quan hÖ rçng. V× vËy: P2() Í P1() ®èi víi tÊt c¶ c¸c EDB . Do ®ã P2 Í P1 (§PCM) VÝ dô 1.3.6: VÝ dô nµy nh»m chØ ra quan hÖ bao hµm lµ kh«ng hµm chøa quan hÖ bao hµm ®ång d¹ng. 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) C¶ hai ch­¬ng tr×nh tÝnh bao ®ãng b¾c cÇu cña a khi ®Çu vµo chØ cã nh÷ng nguyªn tè nÒn cña a nghÜa lµ chóng lµ t­¬ng ®­¬ng. H¬n n÷a ta thÊy: P1 bao hµm ®ång d¹ng P2, nh­ng P2 kh«ng bao hµm ®ång d¹ng P1. ThËt vËy, gi¶ sö d÷ liÖu vµo lµ quan hÖ rçng ®èi víi a vµ mét sè quan hÖ kh¸c rçng G ®èi víi g, ch¼ng h¹n G kh«ng lµ bao ®ãng b¾c cÇu cña chÝnh nã. Th× d÷ liÖu ra cña P2 lµ gièng nh­ d÷ liÖu vµo. Trong khi ®ã d÷ liÖu ra cña P1 lµ bao ®ãng b¾c cÇu cña G. Nh­ vËy, quan hÖ bao hµm kh«ng hµm chøa quan hÖ bao hµm ®ång d¹ng. §Þnh nghÜa 1.3.7 (M« h×nh) Mét DB lµ mét m« h×nh cña P nÕu: = P(). NghÜa lµ kh«ng cã nguyªn tè nÒn míi nµo ®­îc sinh ra khi ¸p dông ch­¬ng tr×nh P vµo DB ®· cho. §Æt M(P) lµ tËp hîp cña tÊt c¶ c¸c m« h×nh cña P. Nã ®­îc gäi lµ tËp hîp M(P) ®ãng trong d¹ng giao nhau. Víi mét d÷ liÖu vµo cho tr­íc th× d÷ liÖu ra cña P lµ m« h×nh cùc tiÓu cña P mµ chøa d÷ liÖu vµo. KÕt qu¶ trªn hµm ý r»ng hai ch­¬ng tr×nh ®­îc gäi lµ t­¬ng ®­¬ng nÕu ®èi víi mäi d÷ liÖu vµo , c¸c ch­¬ng tr×nh cã cïng mét m« h×nh cùc tiÓu mµ chøa . Ch­¬ng tr×nh P1 vµ ch­¬ng tr×nh P2 lµ t­¬ng ®­¬ng ®ång d¹ng nÕu chóng cã cïng mét tËp m« h×nh, nghÜa lµ M(P1)=M(P2). MÖnh ®Ò 1.3.8: P2 Ͳ P1 Û M(P1) Í M(P2) Khi th¶o luËn vÒ quan hÖ bao hµm ®ång d¹ng cña hai ch­¬ng tr×nh P1 vµ P2, kh«ng cÇn thiÕt chóng ph¶i cã cïng tËp hîp c¸c vÞ tõ, quy ®Þnh ®Çu vµo lµ tËp bÊt kú nh÷ng nguyªn tè nÒn ®èi víi nh÷ng vÞ tõ xuÊt hiÖn trong P1 hoÆc P2. ThËm chÝ cã thÓ cho mét vÞ tõ EDB trong ch­¬ng tr×nh nµy lµ mét vÞ tõ IDB trong ch­¬ng tr×nh kia. VÝ dô 1.3.9: 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µ P2 thu ®­îc tõ P1 b»ng c¸ch thªm quy t¾c: a(X,Z) ¬ a(X,Y) Ù g(Y,Z). Ch­¬ng tr×nh P2 chØ cã c¸c vÞ tõ IDB, nghÜa lµ cã d÷ liÖu vµo lµ mét IDB kh¸c rçng. V× tÊt c¶ c¸c quy t¾c cña P1 còng lµ mét quy t¾c cña P2, dÔ dµng kiÓm tra r»ng P1(d) Í P2(d) ®èi víi tÊt c¶ DB d gåm cã c¸c nguyªn tè nÒn ®èi víi a vµ g. V× vËy, cã bao hµm ®ång d¹ng nghÜa lµ P1 Ͳ P2 Víi ch­¬ng tr×nh P1 vµ P2 ®· cho, ta cã thÓ x©y dùng ch­¬ng tr×nh P1’ vµ P2’ sao cho P2 Ͳ P1 nÕu vµ chØ nÕu P2’ Í P1’. Ch­¬ng tr×nh P1’ vµ P2’ thu ®­îc b»ng c¸ch thªm c¸c quy t¾c cã gi¸ trÞ khëi ®éng tïy ý cho vÞ tõ IDB. Quy t¾c ®­îc thªm cho mét vÞ tõ IDB b(X1,..,Xn) lµ b(X1,..,Xn)¬b0(X1,..,Xn). Trong ®ã b0 lµ mét vÞ tõ mµ kh«ng xuÊt hiÖn ë bÊt kú quy t¾c nµo kh¸c. NÕu P1 vµ P2 ®· cã mét quy t¾c cã d¹ng b(X1,..,Xn)¬g(X1,..,Xn), trong ®ã g chØ xuÊt hiÖn ë trong quy t¾c nµy, th× kh«ng cÇn ph¶i thªm quy t¾c ®èi víi b. §Æc biÖt, nÕu ®èi víi mäi vÞ tõ IDB b, trong P1 vµ P2 ®· cã mét quy t¾c cã d¹ng b(X1,..,Xn)¬g(X1,..,Xn), trong ®ã g chØ xuÊt hiÖn trong quy t¾c nµy th× P2 Ͳ P1 nÕu vµ chØ nÕu P2 Í P1. II-Tèi ­u hãa ch­¬ng tr×nh ®Ö quy trong tÝnh t­¬ng ®­¬ng ®ång d¹ng. Ta xÐt mét kiÓu tèi ­u ®Æc biÖt ®ã lµ xãa nh÷ng nguyªn tè thõa trong th©n cña mét quy t¾c vµ xãa nh÷ng quy t¾c thõa trong mét ch­¬ng tr×nh. Sù tèi ­u nµy rÊt h÷u Ých v× nã gi¶m sè l­îng c¸c kÕt nèi cÇn thiÕt khi tÝnh to¸n d÷ liÖu ra. VÊn ®Ò tèi ­u cña ch­¬ng tr×nh kh«ng ®Ö quy ®· ®­îc gi¶i quyÕt. Mét ch­¬ng tr×nh gåm cã nh÷ng quy t¾c kh«ng ®Ö quy cã mét ch­¬ng tr×nh t­¬ng ®­¬ng duy nhÊt víi mét sè l­îng cùc tiÓu c¸c quy t¾c vµ mét sè l­îng cùc tiÓu c¸c nguyªn tè trong th©n cña mçi quy t¾c. Tèi ­u nh÷ng ch­¬ng tr×nh ®Ö quy ®­îc xem xÐt khã h¬n. Thùc tÕ, cã thÓ kh«ng tån t¹i thuËt to¸n ®Ó tèi ­u ch­¬ng tr×nh ®Ö quy, v× sù t­¬ng ®­¬ng cña ch­¬ng tr×nh ®Ö quy lµ vÊn ®Ò bÊt kh¶ quyÕt. Trong phÇn “Cùc tiÓu ch­¬ng tr×nh trong tÝnh t­¬ng ®­¬ng ®ång d¹ng” ta sÏ ®­a ra mét thuËt to¸n ®Ó t×m nh÷ng nguyªn tè thõa trong th©n quy t¾c còng nh­ nh÷ng quy t¾c thõa trong mét ch­¬ng tr×nh vµ xãa chóng trong khi vÉn duy tr× tÝnh t­¬ng ®­¬ng ®ång d¹ng. KÕt qu¶ cuèi cïng lµ mét ch­¬ng tr×nh mµ kh«ng cßn mét nguyªn tè hoÆc quy t¾c thõa. Kh¸c víi tr­êng hîp kh«ng ®Ö quy, kÕt qu¶ cuèi cïng cña sù tèi ­u hãa nµy kh«ng ph¶i lµ duy nhÊt mµ nã tïy thuéc vµo thø tù trong ®ã c¸c nguyªn tè vµ quy t¾c ®­îc xem xÐt ®Ó xãa. 2.1-KiÓm tra tÝnh bao hµm ®ång d¹ng vµ t­¬ng ®­¬ng ®ång d¹ng. KiÓm tra M(P1) Í M(P2) (vµ víi mÖnh ®Ò 2, P2 Ͳ P1) cã thÓ thùc hiÖn bëi qu¸ tr×nh gèi nhau (chase process). Mét DB d 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. Do ®ã M(P1) Í M(P2) nÕu vµ chØ nÕu ®èi víi mäi quy t¾c r cña P2 ta lu«n cã M(P1) Í M(r). V× vËy, víi mÖnh ®Ò 2, P2 Ͳ P1 nÕu vµ chØ nÕu víi mäi quy t¾c r cña P2 th× r Ͳ P1 (r ®­îc xem nh­ lµ mét ch­¬ng tr×nh mét quy t¾c). Ta sÏ chØ ra c¸ch ®Ó kiÓm tra r Ͳ P1 (r lµ mét quy t¾c). Cho r lµ quy t¾c h¬ b (h lµ ®Çu vµ b lµ th©n cña quy t¾c, b cã thÓ lµ rçng, khi ®ã h lµ mét nguyªn tè nÒn). §Ó kiÓm tra r Ͳ P1, ta xem nguyªn tè cña b nh­ lµ mét DB d÷ liÖu vµo cho P1. Nh÷ng nguyªn tè cña b ®­îc biÕn ®æi thµnh mét DB b»ng c¸ch thay thÕ nh÷ng h»ng ph©n biÖt cho nh÷ng biÕ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­ên