Analysis of some methods to avoid infinite loops in the process of query evaluation for the datalog programs.
Lê Mạnh Thạnh, Trương Công Tuấn · Journal of Computer Science and Cybernetics · 2012
Resolution is the main technique used by query answering systems for logic programs.This paper analyses and compares two methods that avoid infinite loops in the process of query evaluation for logic programs with finite models.We present some search strategies and discuss a particular tabulation technique, SLG resolution, and a particular transformation technique, Magic Templates.They are all goaloriented and can be applied to evaluate queries for the Datalog programs.The primary differences between direct implementations of both approaches are in the maintenance of data structures.T6111 t't.Phep ph an gi<l.iIiky thuat chinh du'o'c cac h~thong trd lai d.u truy van st!• dung trong cac chtrorig trlnh logic.Bai bao t~p trung phan tich va so sanh hai phu'ong ph ap nh Srn ngan ch~n cac vong l~p vo han trong qua trlnh iro-c hro-ng cau truy van d6i voi cac chiro'ng trlnh logic voi mo hlnh hiru han, Chung toi trlnh bay cac chign hro'c tlm kigm, thdo lu~n ve phep bign do'i ma t~p va ph ep U'Crchrong b:l.ngSLG.Ci hai phiro-ng ph ap nay d'eu 111.nhimg thuat toan hutmg dich, chting ta co the' ap dung M iro'c hrong cfiu truy van d6i v6i chu'o'ng trlnh Datalog.Sv' khac nhau CO' bdn trong vi~c thuc hi~n cd a cd hai each tiep c~n nay 111.ve m~t cau true dir li~u.Cac ky thu~t d~tn!.Uti cau truy van doi vrri cac chircng trinh logic da diro'c nghien ciru nhieu trong cac nam qua va co th~tlm thay nhi'eu cong trinh nghien crru [2,[4][5][6][7][8]11].Nhirng ky thu~t nay diro'c ap dung theo hai each khac nhau, thiro'ng diro'c goi la tren xudng (top-down) va dirci len (bottom-up).Cac phuo ng ph ap top-down co ve la cac phirong phap trtrc giac do di~m khci dau cna viec tinh toan la tir dich truy van, va chiing se khOng tinh cac fact khong thich ho'p v6i.cau truy van.Tuy nhien cac ket qua trung gian co th~du oc tinh toan l~p di l~p lai nhieu tan, ehhg han vai phircng phap tro'c hrong SLD [5], phtro'ng phap nay Ill.day dd, nghia la tat d cau td lei dung diro'c bi~u di~n trong cay SLD.Cay SLD da t ao ra m9t sV' phan ehia chinh xac trong khOng gian tlm kigm: Can tinh toan gi va thtr tV' t inh toan la nhir thg nao.M9t di'eu dang tiec doi voi phtro'ng phap nay la no khOng hi~u qua, viec tfnh toan tren cay SLD co th~keo dai va t~n.Cac phuong phap bottom-up dam bao tinh kgt thuc trong qua trlnh tinh toan lai giai ciia cau truy van, nhung di'eu nay khOng co nghia la no hi~u qua.Chung thirong khong dinh hiro'ng dich, nhieu fact khOng lien quan den cau truy van ciing duoc tinh toano M9t so phirong phap m& r9ng M tra len cau truy van diroc dira ra trong then gian gan day rna muc dich Ill.dira ra dtro'c m9t chien hroc tlm kiern huang dich nhir trong SLD, d<'mg thai co tinh hi~u qua la dam bao ket thtic qua trlnh tinh toan cau td loi truy van.