Optimizations and Extensions for the Horn Transaction Logic Programs

Paul FodorAAAI 2008

Abstract

Transaction Logic (TR) provides a formal framework for reasoning about state-changing systems within a declarative logic programming paradigm. However, standard evaluation methods often suffer from infinite loops in recursive programs and struggle with incomplete information. This paper presents two significant enhancements to Horn Transaction Logic: a state-aware tabling mechanism to ensure termination and a definite semantics for existential values to handle unknown data. These optimizations improve the practicality of TR for complex domains such as AI planning and workflow verification.

Introduction

Traditional logic programming, exemplified by Prolog, is highly effective for querying static knowledge bases. However, many real-world applications—including banking, robotics, and workflow management—require the ability to modify the underlying database. Transaction Logic (TR) was developed to bridge this gap, offering a rigorous logical foundation for state updates.

A persistent challenge in TR is that standard SLD-style resolution is prone to infinite loops when evaluating recursive programs that modify the database. For instance, a program calculating reachability while deleting edges could cycle indefinitely if not properly managed. Additionally, TR has historically lacked robust mechanisms for handling "existential values"—situations where a fact is known to exist, but its specific identity is unknown.

Methods

The proposed optimizations focus on two areas: state-based caching and the handling of incomplete information.

Tabling for Transaction Logic

In static logic programming, "tabling" (or memoization) caches sub-query results to avoid redundant computations. Fodor extends this concept to TR by incorporating the database state into the cache key. A table entry in this system stores the initial call, the resulting answer, the initial database state, and the final state. This ensures that if a query is repeated in an identical state, the system can retrieve the result directly.

Initial branching in the derivation of reach(a, X) in state s0.

To make this computationally feasible, the author implemented "state signing" in XSB Prolog. This technique allows for rapid comparison of database states without excessive memory overhead. The approach to existential values mimics human intuition by using unique identifiers and a subsumption rule to prevent logical bloat.

Results

The effectiveness of these techniques is demonstrated through recursive examples like the reach/2 predicate. As shown in the derivation trees, the system can now navigate complex paths that would otherwise lead to infinite loops. For programs with the "bounded term depth property," this tabling technique is guaranteed to terminate.

Complete SLD-derivation tree for reach(a, X) showing state transitions and termination.

The integration of these methods into XSB Prolog proves that state-aware tabling is a viable approach for real-world logic engines. The "definite semantics" extension further clarifies the handling of "incomplete effects," where a transaction occurs but leaves some details of the resulting state unspecified.

Discussion and Conclusion

While the proposed methods significantly enhance the reliability and expressiveness of Transaction Logic, resource consumption remains a concern. Indexing calls based on database states can lead to large call-answer tables. Future work will focus on further optimizing state sharing and exploring applications in AI planning and automated workflow verification, where guaranteed termination is a critical requirement.

Summary updated

BibTeX
@inproceedings{fodor2008optimizations,
  author = {Paul Fodor},
  title = {{Optimizations and Extensions for the Horn Transaction Logic Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}

Loading related content...

Figure