Báo khoa học: 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

Chia sẻ: VAN DE JONE | Ngày: | Loại File: DOC | Số trang:8

Thêm vào BST

Báo xấu

85
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Báo khoa học: 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 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo khoa học: 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

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(t 1,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∧ 2∧ qn vµ w lµ t« ®iÓm cña vÞ tõ p, t« ®iÓm αi q ...∧ cña c¸c ®Ých con qi (t i ,1 ,..., ti ,ni ) ®îc x¸c ®Þnh nh sau: NÕu ti,j lµ h»ng hoÆc biÕn ®· xuÊt hiÖn trong ®Ých con q k tríc ®ã (k < i) hoÆc trong mét vÞ trÝ buéc cña p th× αi[j] =b, ngoµi ra th× αi[j] =f (víi α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µ P ad, gåm c¸c quy t¾c ®îc t« ®iÓm cña mäi quy t¾c trong P. (v) T« ®iÓm α cña c©u truy vÊn p(t1,...,tn) ®îc x¸c ®Þnh bëi: α[i] = b nÕu ti lµ h»ng vµ α[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. §Þnh nghÜa 2.2.1 Mét chiÕn lîc truyÒn th«ng tin sang ngang ®èi víi quy t¾c r vµ t« ®iÓm α cña ®Çu quy t¾c r, ký hiÖu Sips(r,α), lµ mét ®å thÞ cã h- íng ®îc g¸n nh·n. C¸c c¹nh cã d¹ng N S {q} víi N lµ tËp c¸c vÞ tõ trong ch¬ng → 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: (r): p(X,Y) ← q(X,Z) ∧s(Z,Y) Gi¶ sö ®èi X cña vÞ tõ p bÞ buéc bëi h»ng 1, lóc ®ã Sips(r,α) ®îc biÓu diÔn nh sau: X=1 X=1,Z p q s Quy t¾c r ®îc t« ®iÓm thµnh quy t¾c: pbf(X,Y) ← qbf(X,Z) ∧sbf(Z,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( t b ) víi t b lµ ®èi bÞ buéc cña vÞ tõ p. _ _ _ 2. §èi víi mçi quy t¾c r trong Pad: p( t ) ← q1( t1 ) ∧ ... ∧ qn( t n ) ta söa ®æi _ − _ _ thµnh mét quy t¾c trong MPad : p( t ) ← mag_p( t b ) ∧q1( t1 ) ∧... ∧qn( t n ) _ _ _ 3. §èi víi mçi quy t¾c r trong Pad : p( t ) ← q1( t1 ) ∧ ... ∧ qn( t n ) vµ víi mäi vÞ tõ IDB qi, 1≤ i≤ n ta thªm vµo MPad c¸c quy t¾c magic: _ − _ _ mag_qi( t b ) ← mag_p( t b ) ∧q1( t1 ) ∧... ∧qi-1( t i −1 ) i _ _ 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: 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_ p 1 (c ) vµ mag_ p 2 (d) lµ hai vÞ tõ magic lÇn lît cã t« ®iÓm lµ α vµ β. α β Ra: Cho kÕt qu¶ vÞ tõ mag_ p 1 (c) cã chøa vÞ tõ mag_ p 2 (d ) hay kh«ng. Ph¬ng ph¸p: α Bíc 1: BiÕn ®æi c¸c vÞ tõ mag_ p 1 (c) 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_ p 2 (d ) thµnh h¹ng thøc p2( y ). Bíc 2: NÕu tån t¹i hîp nhÊt tö tæng qu¸t nhÊt (mgu - most general unifier) α θ cña p1( x ) vµ p2( y ) sao cho p1θ chÝnh lµ p2 th× kÕt luËn vÞ tõ mag_ p 1 (c) β α β chøa vÞ tõ mag_ p 2 (d ) , ngîc l¹i th× mag_ p 1 (c) kh«ng chøa vÞ tõ mag_ p 2 (d) . 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 θ cña p1( x ) vµ p2( y ) sao cho p1( x α )θ =p2( y ) th× p1( x ) chøa p2( y ), ®iÒu nµy cã nghÜa mag_ p 1 (c) chøa mag_ β p 2 (d ) . §Ó ý 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_p bbf(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 θ cña p(a,X,Y) vµ p(a,b,Z) lµ {X/b,Y/Z} vµ p(a,X,Y)θ = 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) ← par(X,Y) r2 : anc(X,Y) ← par(X,Z) ∧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: ar1 : ancfb(X,Y) ← par(X,Y) ar2 : ancfb(X,Y) ← ancfb(Z,Y) ∧par(X,Z) 8
ar3 : ancbb(Z,Y) ← par(X,Y) ar4 : ancbb(X,Y) ← ancbb(Z,Y) ∧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 ad MP : mar1 : ancfb(X,Y) ← mag_ancfb(Y) ∧par(X,Y) mar2 : ancfb(X,Y) ← mag_ancfb(Y) ∧par(X,Z) ∧ancbb(Z,Y) mar3 : mag_ancbb(Z,Y) ← mag_ancfb(Y) ∧par(X,Z) (a,b), (b,c), (c,d) mar4 : ancbb(X,Y) ← mag_ancbb(X,Y) ∧par(X,Y) mar5 : ancbb(X,Y) ← mag_ancbb(X,Y) ∧par(X,Z) ∧ancbb(Z,Y) mar6 : mag_ancbb(Z,Y) ← mag_ancbb(X,Y) ∧par(X,Z) 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) ← mag_ancbf(X) ∧par(X,Y) ancbf(X,Y) ← mag_ancbf(X) ∧par(X,Z) ∧anc(Z,Y) mag_ancbf(Z) ← mag_ancbf(X) ∧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) ← mag_ancbf(X) ∧par(X,Y) ancbf(X,Y) ← mag_ancbf(X) ∧anc(Z,Y) ∧par(X,Z) mag_ancff ← mag_ancbf(X) ancff(X,Y) ← mag_ancff ∧par(X,Y) ancff(X,Y) ← mag_ancff ∧anc(Z,Y) ∧par(X,Z) Hai chiÕn lîc nµy dÉn ®Õn c¸c tËp truy vÊn con Q 1 = {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_anc ff 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 One of the major tasks of deductive databases is query answering, many query evaluation methods have been proposed. Among these, the magic-sets transformation was a general query optimization technique in deductive databases. However, magic- sets technique may not be the best query optimization strategy. In this paper, we discuss some problems of magic sets and propose some improvements of magic-sets technique that allow efficient bottom-up computation of answers. 12