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

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.
Nội dung trích xuất từ tài liệu:
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 DatalogTAÛ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©utruy vÊn rÊt cã hiÖu qu¶ trong c¬ së d÷ liÖu suy diÔn. Lý do quan träng ®èi víisù 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 matËp ®îc thÓ hiÖn ë tÝnh hiÖu qu¶ cña nã ([3, 4, 5]). Tuy nhiªn, phÐp biÕn ®æima 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Ëptrung 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 truyvÊ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¬ncò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étsè ®Þ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 trongsuè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Òudµ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õ IDBlµ ®î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ñap 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åmc¸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 tilµ 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 tinsang 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Ï ®îctÝnh vµ c¸ch thøc ®Ó c¸c trÞ buéc nµy truyÒn sang ngang gi÷a c¸c ®Ých controng 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 quyt¾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øcth«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 sangngang 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ÓudiÔ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×nhDatalog P ban ®Çu thµnh ch¬ng tr×nh cã t« ®iÓm Pad theo mét chiÕn lîctruyÒ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ÖuMPad, ®î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 ...