Abstract:
This paper considers the problem of efficient incremental maintenance of memo tables in a tabled logic programming system when the underlying data are changed. Most existing techniques for incremental evaluation (or materialized view maintenance in deductive databases) consider insertion and deletion of facts as primitive changes, and treat update as deletion of the old version followed by insertion of the new version. They handle insertion and deletion using independent algorithms, consequently performing many redundant computations when processing updates. In this paper, we present a local algorithm for handling updates to facts. We maintain a dynamic (and potentially cyclic) dependency graph between and among calls and answers in the memo tables. The key idea is to interleave the propagation of deletion and insertion operations generated by the updates through this graph. The dependency graph used in our algorithm is more general than that used in algorithms previously proposed for incremental evaluation of attribute grammars and functional programs. Nevertheless, our algorithm's complexity matches that of the most efficient algorithms built for these specialized cases. We demonstrate the effectiveness of our algorithm using data-flow analysis and parsing examples.
Bibtex Entry:
@inproceedings{SR:ICLP06, author = {Diptikalyan Saha and C. R. Ramakrishnan}, title = {A Local Algorithm for Incremental Evaluation of Tabled Logic Programs}, booktitle = {International Conference on Logic Programming ({ICLP})}, address = {Seattle, Washington}, month = {August}, series = {Lecture Notes in Computer Science}, volume = {4079}, publisher = {Springer}, pages = {56--71}, year = {2006} }
| Full Paper: | [pdf] |
C. R. Ramakrishnan
(cram@cs.sunysb.edu)