Querying Sequential and Concurrent Horn Transaction Logic Programs Using Tabling Techniques

Paul FodorAAAI 2008

Abstract

In computational logic, programs that modify their own database state during execution present significant challenges for standard evaluation algorithms. This paper introduces tabling techniques for Transaction Logic (TR) to handle recursive programs that perform database updates. By memoizing query results alongside initial and final database states, the proposed method prevents infinite loops and ensures termination for Transaction Datalog programs. We explore applications in both sequential and concurrent Transaction Logic, demonstrating the feasibility of this approach through an implementation in XSB Prolog.

1. Introduction

Classical logic programming, such as standard Prolog, typically operates on a static set of facts. Transaction Logic (TR) extends this paradigm by incorporating "transactions"—actions that explicitly change the state of the database through insertions or deletions. However, recursion in the presence of state changes often leads to non-termination in standard SLD-resolution. For instance, a "consuming reachability" program that deletes edges as it traverses them can fall into infinite loops if the system lacks a memory of previously explored states.

2. The Challenge of State-Changing Recursion

Consider a graph where finding a path involves "consuming" the edges used. In such a scenario, the state of the database changes with every step. Without a mechanism to track these changes, a recursive rule might repeatedly attempt the same query in the same state, or fail to recognize that a state has already been processed.

Figure 1: A sample graph used to demonstrate consuming reachability.

3. Proposed Tabling Methodologies

To address the termination problem, the paper proposes two distinct tabling techniques based on the logic type:

3.1 Sequential Transaction Logic

For sequential execution, the system employs a Call-Answer Table. Unlike traditional tabling which only stores (Query, Result), this extended table records a four-part tuple: (Call, Initial State, Answer Unification, Return State). When a query is initiated, the system checks the cache for the specific query-state pair. If a match is found, the cached result and the corresponding final database state are returned immediately, bypassing redundant computation.

3.2 Concurrent Transaction Logic

In concurrent environments where multiple actions may occur simultaneously, linear state-caching is insufficient. The authors suggest utilizing an AND-OR graph to represent the execution space. By memoizing "hot" vertices—active points in the execution graph—the system ensures that identical execution paths are not re-processed, maintaining efficiency and ensuring termination.

4. Implementation and Results

The proposed techniques were implemented in XSB Prolog. To manage the potential memory overhead of storing entire database states, an efficient "state signing" technique was used to represent and compare states without consuming excessive resources.

The effectiveness of the tabling mechanism is demonstrated by its ability to compute all possible final states for complex transactional queries. As shown in the results below, the system correctly identifies various reachability outcomes and their resulting database states (e.g., which edges remain after a consuming path is found).

Figure 6: Results of reachability queries showing answer unifications and the resulting database states.

5. Conclusion and Future Work

This research provides a robust framework for evaluating recursive Transaction Logic programs. By treating the database state as a primary component of the cache key, the authors bridge the gap between static logic tabling and dynamic state-transition systems. While "state signing" mitigates memory issues, future work will focus on addressing potential "state explosion" in very large databases and further optimizing the concurrent execution models for high-scale applications in AI planning and workflow verification.

Summary updated

BibTeX
@inproceedings{fodor2008querying,
  author = {Paul Fodor},
  title = {{Querying Sequential and Concurrent Horn Transaction Logic Programs Using Tabling Techniques}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}

Loading related content...

Figure