Incremental Evaluation of Tabled Logic Programs

Diptikalyan Saha, C. R. Ramakrishnan


Tabling has emerged as an important evaluation technique in logic programming. Currently, changes to a program (due to addition/deletion of rules/facts) after query evaluation compromise the completeness and soundness of the answers in the tables. This paper presents incremental algorithms for maintaining the freshness of tables upon addition or deletion of facts. Our algorithms improve on existing materialized view maintenance algorithms and can be easily extended to handle changes to rules as well. We describe an implementation of our algorithms in the XSB tabled logic programming system. Preliminary experimental results indicate that our incremental algorithms are efficient. Our implementation represents a first step towards building a practical system for incremental evaluation of tabled logic programs.

Bibtex Entry:

author = {Diptikalyan Saha and  C. R. Ramakrishnan},
title = {Incremental Evaluation of Tabled Logic Programs},
booktitle = {International Conference on Logic Programming ({ICLP})},
address = {Mumbai, India},
month = {December},
series = {Lecture Notes in Computer Science},
volume = {2916},
publisher = {Springer},
pages = {389--406},
year = {2003}

Full Paper: [pdf]

Home | Papers

C. R. Ramakrishnan