TAÛP CHÊ KHOA HOÜC, Âaûi hoüc Huãú, Säú 14, 2002
MéT Sè C¶I TIÕN §èI VíI PHÐP BIÕN §æI MA TËP §Ó tèi u hãa c©u truy vÊn trªn ch¬ng tr×nh datalog
Lª M¹nh Th¹nh, Tr¬ng C«ng TuÊn
Trêng §¹i häc Khoa häc, §¹i häc HuÕ
1. Më ®Çu
PhÐp biÕn ®æi ma tËp ®îc ®¸nh gi¸ lµ mét trong nh÷ng kü thuËt tèi u c©u truy vÊn rÊt cã hiÖu qu¶ trong c¬ së d÷ liÖu suy diÔn. Lý do quan träng ®èi víi sù thµnh c«ng cña kü thuËt nµy lµ sù kÕt hîp ®îc c¸c u ®iÓm cña kü thuËt íc l- îng trªn xuèng (top-down) vµ díi lªn (bottom-up), tõ ®ã gi¶m thiÓu ®îc sè c¸c sù kiÖn cÇn tÝnh vµ t×m kiÕm trªn c¬ së d÷ liÖu. TÝnh l«i cuèn cña kü thuËt ma tËp ®îc thÓ hiÖn ë tÝnh hiÖu qu¶ cña nã ([3, 4, 5]). Tuy nhiªn, phÐp biÕn ®æi ma tËp cha h¼n lµ mét chiÕn lîc ®Þnh gi¸ c©u truy vÊn tèt nhÊt. Bµi b¸o tËp trung th¶o luËn mét sè vÊn ®Ò liªn quan ®Õn phÐp biÕn ®æi ma tËp vµ ®Ò xuÊt mét sè c¶i tiÕn nh»m n©ng cao hiÖu qu¶ cña nã trong viÖc tèi u c©u truy vÊn trªn ch¬ng tr×nh Datalog.
2. Mét sè kh¸i niÖm c¬ së
Trong khu«n khæ mét bµi b¸o, chóng t«i chØ tr×nh bµy tãm t¾t mét sè kh¸i niÖm c¬ së cña phÐp biÕn ®æi ma tËp. §Ó cã c¸c chi tiÕt ®Çy ®ñ h¬n còng nh mét sè kh¸i niÖm kh¸c cña c¬ së d÷ liÖu suy diÔn cã thÓ xem trong [1, 5].
2.1 T« ®iÓm (Adornment): T« ®iÓm lµ c¸ch chó thÝch trªn c¸c vÞ tõ ®Ó cung cÊp th«ng tin vÒ c¸c vÞ tõ sÏ ®îc sö dông nh thÕ nµo trong qu¸ tr×nh ®Þnh gi¸ c©u truy vÊn. Ta cã mét sè ®Þnh nghÜa:
(i) Mét ®èi cña mét ®Ých con trong quy t¾c r ®îc gäi lµ buéc nÕu trong suèt qu¸ tr×nh ®Þnh gi¸ c©u truy vÊn, mäi ®Ých ®îc t¹o ra tõ ®Ých con nµy cã gi¸ trÞ h»ng ë vÞ trÝ cña ®èi nµy. Ngîc l¹i, ®èi ®îc gäi lµ tù do.
5
(ii) Mét t« ®iÓm cña vÞ tõ p(t1,t2,...,tk) lµ mét d·y c¸c ký tù b vµ f cã chiÒu dµi k. NÕu ký hiÖu thø i cña t« ®iÓm lµ b th× ®èi thø i cña p lµ buéc, nÕu ký hiÖu thø i cña t« ®iÓm lµ f th× ®èi thø i cña p lµ tù do. ChØ cã c¸c vÞ tõ IDB lµ ®îc t« ®iÓm.
(iii) Cho quy t¾c p ‹ ,..., q1(cid:217) q2(cid:217) ...(cid:217) qn vµ w lµ t« ®iÓm cña vÞ tõ p, t« ®iÓm a t ) cña c¸c ®Ých con
i ®îc x¸c ®Þnh nh sau: NÕu ti,j lµ h»ng hoÆc biÕn
tq ( i
i
1,
ini ,
i[j] =b, ngoµi ra th× a
i[j] =f (víi a
®· xuÊt hiÖn trong ®Ých con qk tríc ®ã (k < i) hoÆc trong mét vÞ trÝ buéc cña p th× a i[j] lµ ký hiÖu ë vÞ trÝ thø j cña t« ®iÓm). (iv) Cho ch¬ng tr×nh P, ch¬ng tr×nh t« ®iÓm cña P, ký hiÖu lµ Pad, gåm
c¸c quy t¾c ®îc t« ®iÓm cña mäi quy t¾c trong P.
(v) T« ®iÓm a cña c©u truy vÊn p(t1,...,tn) ®îc x¸c ®Þnh bëi: a [i] = b nÕu ti
lµ h»ng vµ a [i] = f nÕu ngîc l¹i.
2.2 TruyÒn th«ng tin sang ngang (Sideway Information Passing): PhÐp biÕn ®æi ma tËp ®îc thùc hiÖn theo mét chiÕn lîc truyÒn th«ng tin sang ngang chän tríc, chiÕn lîc nµy chØ ra c¸ch thøc ®Ó c¸c trÞ buéc trong ®Çu quy t¾c ®îc truyÒn ®Õn th©n, thø tù mµ c¸c ®Ých con trong th©n sÏ ®îc tÝnh vµ c¸ch thøc ®Ó c¸c trÞ buéc nµy truyÒn sang ngang gi÷a c¸c ®Ých con trong th©n quy t¾c.
S
fi (cid:190) §Þnh nghÜa 2.2.1 Mét chiÕn lîc truyÒn th«ng tin sang ngang ®èi víi quy cña ®Çu quy t¾c r, ký hiÖu Sips(r,a ), lµ mét ®å thÞ cã h- {q} víi N lµ tËp c¸c vÞ tõ trong ch¬ng
t¾c r vµ t« ®iÓm a íng ®îc g¸n nh·n. C¸c c¹nh cã d¹ng N (cid:190) tr×nh, S lµ tËp c¸c biÕn vµ q lµ mét vÞ tõ. C¸c c¹nh vµ nh·n chØ ®Þnh c¸ch thøc th«ng tin ®îc truyÒn gi÷a c¸c ®Ých con. C¸c c¹nh cña ®å thÞ chØ ra mét thø tù ®Ó c¸c ®Ých con ®îc íc lîng, c¸c nh·n chØ ®Þnh th«ng tin ®îc truyÒn sang ngang tõ ®Ých con nµy ®Õn ®Ých con kh¸c.
VÝ dô 2.1 Xem quy t¾c sau: p(X,Y) ‹ (r):
q(X,Z) (cid:217) s(Z,Y) Gi¶ sö ®èi X cña vÞ tõ p bÞ buéc bëi h»ng 1, lóc ®ã Sips(r,a ) ®îc biÓu
diÔn nh sau:
X=1
X=1,Z
p q s
qbf(X,Z) (cid:217) sbf(Z,Y)
Quy t¾c r ®îc t« ®iÓm thµnh quy t¾c: pbf(X,Y) ‹ 2.3 PhÐp biÕn ®æi ma tËp ([4]): PhÐp biÕn ®æi ma tËp ®îc thùc hiÖn qua hai giai ®o¹n:
6
Giai ®o¹n 1: Thùc hiÖn viÖc t« ®iÓm ch¬ng tr×nh: BiÕn ®æi ch¬ng tr×nh Datalog P ban ®Çu thµnh ch¬ng tr×nh cã t« ®iÓm Pad theo mét chiÕn lîc truyÒn th«ng tin sang ®· chän tríc.
Giai ®o¹n 2: BiÕn ®æi ch¬ng tr×nh Pad thµnh ch¬ng tr×nh míi, ký hiÖu
MPad, ®îc thùc hiÖn nh sau:
_
1. §èi víi mçi vÞ tõ p víi ®èi lµ t trong ch¬ng tr×nh Pad ,t¹o ra mét vÞ tõ - - míi mag_p( ) víi lµ ®èi bÞ buéc cña vÞ tõ p.
bt
bt
_
_
2. §èi víi mçi quy t¾c r trong Pad: p( ) ta söa ®æi q1( t ) ‹
1t ) (cid:217) ... (cid:217) qn(
-
_
_
thµnh mét quy t¾c trong MPad : p( mag_p( ) (cid:217) q1( ) t ) ‹
_ nt
bt
_ nt 1t ) (cid:217) ... (cid:217) qn(
_
_
3. §èi víi mçi quy t¾c r trong Pad : p( q1( ) vµ víi mäi vÞ t ) ‹
_ nt
1t ) (cid:217) ... (cid:217) qn(
tõ IDB qi, 1£ i£ -
_
mag_p( ) (cid:217) q1( ) ‹ mag_qi( )
_ 1-it
bt
n ta thªm vµo MPad c¸c quy t¾c magic: 1t ) (cid:217) ... (cid:217) qi-1(
_ b it
_
_
4. C©u truy vÊn q( c ) ®îc chuyÓn thµnh sù kiÖn “h¹t nh©n” mag_q( c ),
_
trong ®ã
c lµ tËp c¸c h»ng t¬ng øng víi c¸c ®èi bÞ buéc cña c©u truy vÊn. §Þnh lý 2.3.1 ([4]) Cho ch¬ng tr×nh Datalog P vµ c©u truy vÊn q. Dïng phÐp biÕn ®æi ma tËp ®Ó biÕn ®æi ch¬ng tr×nh P vµ c©u truy vÊn q thµnh ch¬ng tr×nh MPad. Ch¬ng tr×nh nµy sÏ t¬ng ®¬ng víi P theo nghÜa khi íc lîng MPad sÏ cho ra cïng kÕt qu¶ cña c©u truy vÊn q.
3. Mét sè vÊn ®Ò liªn quan ®Õn phÐp biÕn ®æi ma tËp
Trong phÇn nµy chóng t«i tËp trung th¶o luËn mét sè vÊn ®Ò liªn quan ®Õn kü thuËt ma tËp vµ ®Ò xuÊt c¸c gi¶i ph¸p nh»m n©ng cao tÝnh hiÖu qu¶ cña nã trong qu¸ tr×nh ®Þnh gi¸ c©u truy vÊn.
3.1 H¹n chÕ tÝnh to¸n d thõa trªn ch¬ng tr×nh viÕt l¹i bëi phÐp biÕn
®æi ma tËp
Khi kÕt thóc giai ®o¹n hai cña phÐp biÕn ®æi ma tËp, ta nhËn ®îc mét ch¬ng tr×nh míi vµ viÖc t×m kiÕm lêi gi¶i cña ch¬ng tr×nh viÕt l¹i nµy thêng ®îc thùc hiÖn bëi c¸c thuËt to¸n íc lîng díi lªn, ch¼ng h¹n thuËt to¸n nöa ng©y th¬ (semi-naive) ([5]), thuËt to¸n nµy cho phÐp ng¨n chÆn viÖc tÝnh to¸n l¹i c¸c sù kiÖn ®· ®îc tÝnh ë bíc tríc. Tuy nhiªn, nã kh«ng ng¨n chÆn ®îc viÖc dÉn xuÊt ra c¸c vÞ tõ magic d thõa.
Gi÷a c¸c vÞ tõ magic t« ®iÓm, mÆc dÇu kh«ng cã quan hÖ vÒ có ph¸p nhng vÒ mÆt ng÷ nghÜa, mét vÞ tõ magic t« ®iÓm cã thÓ chøa c¸c vÞ tõ
7
magic t« ®iÓm kh¸c. VÊn ®Ò ë ®©y chÝnh lµ sö dông c¸c th«ng tin trong c¸c t« ®iÓm ®Ó x¸c ®Þnh xem mét vÞ tõ magic cã chøa vÞ tõ magic kh¸c hay kh«ng. ViÖc kiÓm tra quan hÖ gi÷a c¸c vÞ tõ magic cã thÓ thu hÑp thµnh viÖc kiÓm tra gi÷a c¸c vÞ tõ t¬ng øng cña chóng. §iÒu nµy ®îc thùc hiÖn qua thuËt to¸n sau ®©y:
) vµ mag_ lµ hai vÞ tõ magic lÇn lît cã t«
b )d(p 2
a c(p1
ThuËt to¸n kiÓm tra quan hÖ gi÷a c¸c vÞ tõ magic ®îc t« ®iÓm: Vµo: Gi¶ sö mag_ vµ b . ®iÓm lµ a
Ra: Cho kÕt qu¶ vÞ tõ mag_ cã chøa vÞ tõ mag_ hay kh«ng. )(p1 ca
b )d(p 2
Ph¬ng ph¸p: Bíc 1: BiÕn ®æi c¸c vÞ tõ mag_
)(p1 ca thµnh h¹ng thøc p1( x ), trong ®ã x bao gåm c¸c h»ng trong c t¬ng øng víi ký tù 'b' vµ c¸c biÕn ph©n biÖt t¬ng øng víi ký tù 'f'. T¬ng tù, biÕn ®æi vÞ tõ mag_ thµnh h¹ng thøc p2( y ).
b )d(p 2
Bíc 2: NÕu tån t¹i hîp nhÊt tö tæng qu¸t nhÊt (mgu - most general unifier) )(p1 ca . q cña p1( x ) vµ p2( y ) sao cho p1q chÝnh lµ p2 th× kÕt luËn vÞ tõ mag_ chøa vÞ tõ mag_ kh«ng chøa vÞ tõ mag_ , ngîc l¹i th× mag_
b )d(p 2
b )d(p 2
)(p1 ca
MÖnh ®Ò 3.1.1 ThuËt to¸n nµy lµ ®óng ®¾n. Chøng minh: Râ rµng nÕu tån t¹i mgu q cña p1( x ) vµ p2( y ) sao cho p1( x chøa mag_ )(p1 ca
. )q =p2( y ) th× p1( x ) chøa p2( y ), ®iÒu nµy cã nghÜa mag_ b )d(p 2
§Ó ý r»ng phÐp hîp nhÊt trë nªn ®¬n gi¶n h¬n nhiÒu nÕu mét trong hai vÞ tõ cÇn hîp nhÊt lµ nguyªn tè nÒn. Trong trêng hîp nµy th× phÐp hîp nhÊt thu hÑp thµnh phÐp ®èi s¸nh h¹ng thøc.
VÝ dô 3.1.1 XÐt hai vÞ tõ mag_pbff(a) vµ mag_pbbf(a,b). Ta cã mag_pbff(a) t¬ng øng víi ®Ých ?p(a,X,Y) vµ mag_pbbf(a,b) t¬ng øng víi ®Ých ?p(a,b,Z), mÆc kh¸c hîp nhÊt tö tæng qu¸t nhÊt q cña p(a,X,Y) vµ p(a,b,Z) lµ {X/b,Y/Z} vµ p(a,X,Y)q = p(a,b,Z). V× vËy mag_pbff(a) chøa mag_pbbf(a,b).
VÝ dô 3.1.2 XÐt ch¬ng tr×nh Datalog P bao gåm c¸c quy t¾c:
r1 : anc(X,Y) ‹ r2 : anc(X,Y) ‹ par(X,Y) par(X,Z) (cid:217) anc(Z,Y)
Trong ®ã: par lµ vÞ tõ EDB, anc lµ vÞ tõ IDB. Gi¶ sö quan hÖ ®èi víi vÞ tõ
EDB par gåm c¸c bé (a,b), (b,c), (c,d). C©u truy vÊn ?-anc(X,d).
Sö dông chiÕn lîc truyÒn th«ng tin tõ tr¸i sang ph¶i, sau giai ®o¹n 1 cña
phÐp biÕn ®æi ma tËp ta nhËn ®îc ch¬ng tr×nh t« ®iÓm Pad sau ®©y: par(X,Y) ancfb(Z,Y) (cid:217) par(X,Z) ar1 : ancfb(X,Y) ‹ ar2 : ancfb(X,Y) ‹
8
ar3 : ancbb(Z,Y) ‹ ar4 : ancbb(X,Y) ‹ par(X,Y) ancbb(Z,Y) (cid:217) par(X,Z)
§Ých truy vÊn cã t« ®iÓm: ?- ancfb(X,d) Sau giai ®o¹n 2 cña phÐp biÕn ®æi ma tËp, ta nhËn ®îc ch¬ng tr×nh
MPad: ‹
‹ mag_ancfb(Y) (cid:217) par(X,Y) mag_ancfb(Y) (cid:217) par(X,Z) (cid:217) ancbb(Z,Y) ‹ mag_ancfb(Y) (cid:217) par(X,Z) (a,b), (b,c), (c,d) ‹
‹ mag_ancbb(X,Y) (cid:217) par(X,Y) mag_ancbb(X,Y) (cid:217) par(X,Z) (cid:217) ancbb(Z,Y) ‹ mag_ancbb(X,Y) (cid:217) par(X,Z)
mar1 : ancfb(X,Y) mar2 : ancfb(X,Y) mar3 : mag_ancbb(Z,Y) mar4 : ancbb(X,Y) mar5 : ancbb(X,Y) mar6 : mag_ancbb(Z,Y) mar7 : mag_ancfb(d)
¸p dông thuËt to¸n nöa ng©y th¬ cho ch¬ng tr×nh MPad nµy, ta nhËn ®îc: Bíc 1: mag_ancfb(d) ®îc t¹o ra. Bíc 2: ancfb(c,d), mag_ancbb(b,d), mag_ancbb(c,d), mag_ancbb(d,d) ®îc
thªm vµo.
Bíc 3: ancbb(c,d) ®îc thªm vµo. Bíc 4: ancbb(b,d), ancfb(b,d) ®îc thªm vµo. Bíc 5: ancfb(a,d) ®îc thªm vµo. Bíc 6: KÕt thóc, ta nhËn ®îc lêi gi¶i c©u truy vÊn (c,d), (b,d), (a,d).
Râ rµng c¸c vÞ tõ mag_ancbb(b,d), mag_ancbb(c,d), mag_ancbb(d,d) ®îc t¹o ra ë bíc 2 lµ chøa trong vÞ tõ magic biÓu diÔn c©u truy vÊn ban ®Çu mag_ancfb(d), v× vËy chóng lµ d thõa vµ kh«ng cÇn ph¶i tÝnh.
Tãm l¹i, tÝnh to¸n d thõa trong c¸c thuËt to¸n ®Þnh gi¸ c©u truy vÊn trªn ch¬ng tr×nh viÕt l¹i bëi phÐp biÕn ®æi ma tËp sÏ tr¸nh ®îc b»ng c¸ch kÕt hîp thªm thuËt to¸n kiÓm tra vÞ tõ magic ®îc t¹o ra ë mçi bíc cã chøa trong vÞ tõ magic ®· t¹o ra ë bíc tríc hay kh«ng, nÕu cã th× ta lo¹i bá nã.
Ta cã mét vµi nhËn xÐt liªn quan ®Õn phÐp biÕn ®æi ma tËp:
• Trong phÐp biÕn ®æi ma tËp, mét chiÕn lîc truyÒn th«ng tin ®îc dïng
xuyªn suèt qu¸ tr×nh íc lîng c©u truy vÊn.
• ViÖc íc lîng ch¬ng tr×nh viÕt l¹i bëi phÐp biÕn ®æi ma tËp ®· kh«ng xem xÐt sè c¸c sù kiÖn ®îc ph¸t sinh trong qu¸ tr×nh ®Þnh gi¸ truy vÊn, tøc lµ sè c¸c sù kiÖn ®îc t¹o ra trong mçi bíc lÆp.
Trong phÇn tiÕp theo sau ®©y, chóng ta sÏ xem xÐt c¸c vÊn ®Ò nµy. 3.2 §Þnh gi¸ c©u truy vÊn b»ng c¸ch kÕt hîp c¸c chiÕn lîc truyÒn
th«ng tin sang ngang
9
Trªn tËp c¸c quy t¾c cña ch¬ng tr×nh ®· cho cã thÓ tån t¹i nhiÒu chiÕn l- îc truyÒn th«ng tin kh¸c nhau. V× vËy mét c©u hái tù nhiªn lµ liÖu cã thÓ kÕt hîp hiÖu qu¶ cña c¸c chiÕn lîc nµy ®Ó thùc hiÖn viÖc tèi u c©u truy vÊn hay kh«ng? Ta h·y xem vÝ dô sau ®©y:
VÝ dô 3.2.1 XÐt ch¬ng tr×nh Datalog P ®· cho trong vÝ dô 3.1.2. vµ c©u
truy vÊn ?anc(a,b).
§èi víi vÝ dô nµy, hai chiÕn lîc truyÒn th«ng tin cã thÓ ®îc chän ®Ó thùc hiÖn viÖc t« ®iÓm ch¬ng tr×nh lµ tõ tr¸i sang ph¶i vµ tõ ph¶i sang tr¸i. ViÖc kÕt hîp hai chiÕn lîc nµy sÏ dÉn ®Õn hai qu¸ tr×nh ®Þnh gi¸ c©u truy vÊn ?anc(a,Z) vµ ?anc(Z,b) cho ®Õn khi tÊt c¶ lêi gi¶i ®îc t×m thÊy ®èi víi ?anc(a,Z) hoÆc ? anc(Z,b).
ViÖc chän ra mét chiÕn lîc truyÒn th«ng tin "tèt" trong mçi bíc lÆp cã thÓ gi¶m bít c¸c sù kiÖn d thõa ®îc ph¸t sinh vµ ®¹t ®îc hiÖu qu¶ tèi u, ®iÒu nµy th- êng kh«ng thÓ nhËn ®îc bëi phÐp biÕn ®æi ma tËp dùa trªn c¬ së chiÕn lîc truyÒn th«ng tin ®îc chän tríc. C¸c quy t¾c ban ®Çu chØ nªn ®îc xem xÐt l¹i sau khi mét sè kh¸ lín c¸c sù kiÖn ®îc ph¸t sinh. Trong trêng hîp nµy râ rµng chiÕn lîc truyÒn th«ng tin ®îc chän sÏ dùa vµo kÝch thíc nhá nhÊt cña c¸c quan hÖ ®îc t¹o ra t¹i thêi ®iÓm ®ã. Ta cã thuËt to¸n sau:
ThuËt to¸n ma tËp cã kÕt hîp c¸c chiÕn lîc truyÒn th«ng tin sang
ngang:
Bíc 1: ¸p dông phÐp biÕn ®æi ma tËp ®Ó biÕn ®æi ch¬ng tr×nh P theo tÊt c¶ c¸c chiÕn lîc truyÒn th«ng tin chÊp nhËn ®îc, kÕt qu¶ nhËn ®îc mét tËp c¸c ch¬ng tr×nh t« ®iÓm theo c¸c chiÕn lîc nµy.
Bíc 2: ¸p dông c¸c thuËt to¸n lÆp kiÓu díi lªn Naive, Semi-naive ([5]) trªn c¸c ch¬ng tr×nh t« ®iÓm ®îc t¹o ra ë bíc 1, trong ®ã ë mçi bíc lÆp, mét chiÕn l- îc truyÒn th«ng tin sÏ ®îc chän dùa vµo kÝch thíc nhá nhÊt cña c¸c quan hÖ ®îc t¹o ra t¹i thêi ®iÓm ®ã,
TÝnh hiÖu qu¶ cña thuËt to¸n nµy ®îc thÓ hiÖn ë viÖc kÕt hîp ®îc c¸c chiÕn lîc truyÒn th«ng tin kh¸c nhau trong tõng bíc lÆp, tõ ®ã gi¶m ®îc chi phÝ tÝnh to¸n ®èi víi c¸c phÐp to¸n nèi trong th©n quy t¾c trong qu¸ tr×nh íc lîng ch- ¬ng tr×nh.
MÖnh ®Ò 3.2.1 ThuËt to¸n nµy héi tô vµ hiÖu qu¶ h¬n so víi c¸c thuËt
to¸n lÆp díi lªn Naive, Semi-Naive ®· ®îc ®Ò xuÊt trong [5].
Chøng minh: C¸c ch¬ng tr×nh t« ®iÓm ®îc t¹o ra trong bíc 1 cña thuËt to¸n lµ t¬ng ®¬ng víi ch¬ng tr×nh ban ®Çu (®Þnh lý 2.3.1) theo nghÜa chóng cho ra cïng kÕt qu¶ cña c©u truy vÊn, mÆt kh¸c c¸c thuËt to¸n díi lªn Naive, Semi-Naive lµ héi tô ([5]), tõ ®ã suy ra tÝnh héi tô cña thuËt to¸n nµy. ThuËt
10
to¸n ®· ®Ò xuÊt ch¾c ch¾n hiÖu qu¶ h¬n c¸c thuËt to¸n díi lªn Naive, Semi- Naive trong [5], bëi v× trong mçi bíc lÆp ®Òu cã xem xÐt sè c¸c bé cña c¸c quan hÖ ®îc t¹o ra t¹i thêi ®iÓm ®ã vµ chiÕn lîc truyÒn th«ng tin ë bíc tiÕp theo ®îc chän dùa vµo kÝch thíc nhá nhÊt cña c¸c quan hÖ ®ã.
VÝ dô 3.2.2 XÐt trë l¹i ch¬ng tr×nh Datalog (P) ë vÝ dô 3.1.1. víi c©u truy
vÊn lµ ?anc(a,Y).
Hai chiÕn lîc truyÒn th«ng tin cã thÓ ®îc chän ®Ó íc lîng c¸c ®Ých con
trong th©n quy t¾c cña anc lµ tõ tr¸i sang ph¶i vµ tõ ph¶i sang tr¸i. Dïng chiÕn lîc tr¸i sang ph¶i ta nhËn ®îc tËp c¸c quy t¾c sau:
ancbf(X,Y) ‹ ancbf(X,Y) ‹ mag_ancbf(Z) ‹ mag_ancbf(X) (cid:217) par(X,Y) mag_ancbf(X) (cid:217) par(X,Z) (cid:217) anc(Z,Y) mag_ancbf(X) (cid:217) par(X,Z)
Dïng chiÕn lîc ph¶i sang tr¸i ta nhËn ®îc tËp c¸c quy t¾c sau: ‹
‹
‹
‹
‹ ancbf(X,Y) ancbf(X,Y) mag_ancff ancff(X,Y) ancff(X,Y) mag_ancbf(X) (cid:217) par(X,Y) mag_ancbf(X) (cid:217) anc(Z,Y) (cid:217) par(X,Z) mag_ancbf(X) mag_ancff (cid:217) par(X,Y) mag_ancff (cid:217) anc(Z,Y) (cid:217) par(X,Z)
Hai chiÕn lîc nµy dÉn ®Õn c¸c tËp truy vÊn con Q1 = {mag_ancbf} vµ Q2 = {mag_ancbf , mag_ancff}. Trong Q2 truy vÊn con mag_ancff chøa truy vÊn con mag_ancbf. Nh vËy viÖc chän chiÕn lîc Sip tõ ph¶i sang tr¸i ®Ó íc lîng c¸c ®Ých con dÉn ®Õn qu¸ tr×nh c©u truy vÊn ?anc(X,Y) vµ kiÓm tra a cã thuéc X kh«ng? Tuy nhiªn, ®Ó ý r»ng mag_ancff chøa mag_ancbf, v× vËy chiÕn lîc tõ tr¸i sang ph¶i lµ tèt h¬n chiÕn lîc tõ ph¶i sang tr¸i.
4. KÕt luËn
Bµi b¸o ®· tËp trung th¶o luËn mét sè vÊn ®Ò liªn quan ®Õn viÖc tèi u ho¸ c©u truy vÊn trªn ch¬ng tr×nh Datalog b»ng phÐp biÕn ®æi ma tËp. Chóng t«i ®· ®Ò xuÊt c¸ch thøc nhËn ra c¸c sù kiÖn d thõa trong qu¸ tr×nh íc lîng vµ viÖc kÕt hîp c¸c chiÕn lîc truyÒn th«ng tin trong mçi bíc lÆp. C¸c gi¶i ph¸p ®a ra nh»m môc ®Ých lµm t¨ng tÝnh hiÖu qu¶ cña phÐp biÕn ®æi ma tËp, ®ång thêi ®iÒu nµy còng lµ mét thÓ hiÖn tèt vÒ tÝnh hiÖu qu¶ t¬ng ®èi cña mét ph¬ng ph¸p.
TµI LIÖU THAM KH¶O
1. S. Ceri, G. Gottlob, L.Tanca. Logic Programming and Databases, Springer-
Verlag Berlin Heidelberg (1990).
11
2. Lª M¹nh Th¹nh, Tr¬ng C«ng TuÊn. Mét sè ph¬ng ph¸p íc lîng c©u truy vÊn trong c¬ së d÷ liÖu suy diÔn, T¹p chÝ Khoa häc §¹i häc HuÕ, sè 7(2001) 49-
59.
3. Lª M¹nh Th¹nh, Tr¬ng C«ng TuÊn. Ph©n tÝch mét sè ph¬ng ph¸p xö lý vßng lÆp v« h¹n trong qu¸ tr×nh íc lîng c©u truy vÊn ®èi víi ch¬ng tr×nh Datalog, T¹p
chÝ Tin häc vµ §iÒu khiÓn häc, tËp 17, sè 4(2001) 87-96.
4. R. Ramakrishnan. Magic Templates: A Spellbinding Approach to Logic
Programs, Journal of Logic Progamming 11 (1991) 189-216.
5. J.D. Ullman. Principles of Database and Knowledge - Base Systems, Volume I
and II, Computer Science Press (1989).
Tãm t¾t
Trong c¸c ph¬ng ph¸p ®Þnh gi¸ c©u truy vÊn trªn c¬ së d÷ liÖu suy diÔn, phÐp
biÕn ®æi ma tËp (magic sets transformation) ®îc xem lµ mét kü thuËt tèi u c©u truy vÊn
tèt nhê vµo tÝnh hiÖu qu¶ cña nã, tuy nhiªn kü thuËt ma tËp cha h½n lµ mét chiÕn lîc tèi
u truy vÊn tèt nhÊt. Bµi b¸o nµy tËp trung th¶o luËn mét sè vÊn ®Ò liªn quan ®Õn phÐp
biÕn ®æi ma tËp vµ ®Ò xuÊt mét sè c¶i tiÕn nh»m n©ng cao hiÖu qu¶ cña nã.
some improvements of magic-sets transformation in optimizing queries for datalog programs
Le Manh Thanh, Truong Cong Tuan
College of Sciences, Hue University
SUMMARY
