Query proof structure caching for incremental evaluation of tabled prolog programs / Taher Muhammad Ali

PROLOG is the most well known, widely used programming language for logic programming. PROLOG is a programming language that uses a small set of basic mechanisms to create surprisingly powerful programs. These mechanisms are pattern-matching, treebased data structuring and backtracking. PROLOG is used for the development of scheduling systems, knowledge systems, expert systems and many other applications. However, being goal-driven (query driven) PROLOG’S query engine suffers from some well-known problems such as susceptibility to infinite looping, repeated subcomputation and unsatisfactory semantics of negation. These limitations have been addressed by the tabled extensions (TLP) to PROLOG evaluation. The main idea of tabling is to cache the answers for computations and then reuse them when a repeated computation appears. The TLP approach assumes that the database of facts/rules, of which the query results drawn from, remains constant through time and therefore the tabulated results are assumed to remain valid. This prohibits the use of TLP in non-monotonic logic where such an assumption cannot be guaranteed. To overcome this problem the idea of incremental tabulation has been introduced. An incrementally maintained table is one that continually contains the correct answers in the presence of updates to underlying predicates on which the tabled predicate depends. The critical challenges for incremental evaluation are how to detect and update the tabled answers due to the changes in the database of facts and rules associated with the tabled answers. ii This thesis presents an alternative approach to incremental tabulation that is capable of working in non-monotonic situations. The basic idea of our approach is that, as the PROLOG inference engine evaluates the query for the first time, the answers returned by the engine for the query are converted into a justification-based truth-maintenance system (JTMS) network. Every successful branch is translated into a JTMS network that links the facts used in the proof branch to the answer generated by that branch. When the same query is re-evaluated, the query engine collects the valid answers for the query at that moment and returns them by using the cached proof structure for the query. When the state of database is changed, the JTMS component propagates the effect of the change through its network to maintain the consistency of old proofs. At the same time, the database monitor keeps watching the addition of the new data (facts/rules) to the system and triggers the resumption of previously proven queries in order to update their proof structure. The outcome of this thesis is JLOG. JLOG is a sub-system integrated with PROLOG inference engine which supports incremental tabled extensions to PROLOG evaluation. The thesis presents the design, necessary data structures, algorithms and implementation details of JLOG. The results of comparing the performance of JLOG to regular PROLOG and Tabled PROLOG systems are also presented