On Just in Time Indexing of Dynamic Predicates in Prolog

Vítor Santos Costa

October 2009

---

Abstract

Prolog is the most well-known and widely used logic programming language. A large number of Prolog applications maintains information by asserting and retracting clauses from the database. Such dynamic predicates raise a number of issues for Prolog implementations, such as what are the semantics of a procedure where clauses can be retracted and asserted while the procedure is being executed. One advantage of Logical Update semantics is that it allows indexing. In this paper, we discuss how one can implement just-in-time indexing with Logical Update semantics. Our algorithm is based on two ideas: stable structure and fragmented index trees. By stable structure one means that we define a structure for the indexing tree that not change, even as we assert and as we retract clauses. Second, by fragmented index tree we mean that the indexing tree will be built in such a way that the updates will be local to each fragment. The algorithm was implemented and results indicate significant speedups and reduction of memory usage in test applications.

Bibtex

@InProceedings{santoscosta-epia09,
  author =    {V. Santos Costa},
  title =     {{On Just in Time Indexing of Dynamic Predicates in Prolog}},
  booktitle = {Proceedings of the 14th Portuguese Conference on Artificial Intelligence (EPIA 2009)},
  pages =     {126--137},
  number =    {5816},
  series =    {LNAI},
  publisher = {Springer},
  editor =    {L. S. Lopes and N. Lau and P. Mariano and L. Rocha},
  month =     {October},
  year =      {2009},
  address =   {Aveiro, Portugal},
}

Download Paper

PDF file
Springer