Performing Inferences over Recursive Data Bases

Shamim A. Naqvi, Lawrence J. HenschenAAAI 1980

Abstract

Handling recursion in relational databases is a long-standing challenge, often leading to infinite loops or computational inefficiency. This paper introduces a method to "compile" recursive logical rules into equivalent, non-recursive iterative programs. By utilizing connection graphs to identify potential recursive loops, the authors synthesize algorithms that use queues to efficiently retrieve facts, ensuring termination within finite databases.

Introduction: The Recursion Gap in Deductive Databases

In the late 1970s, the evolution of relational databases toward "smarter" inferential systems led to the distinction between the Extensional Data Base (EDB)—containing explicit facts—and the Intensional Data Base (IDB)—containing general rules. While non-recursive rules were straightforward to process, recursive rules (e.g., defining "ancestor" in terms of itself) posed significant risks for standard query processors, such as non-termination. This research addresses the need to transform these logical definitions into stable, iterative algorithms.

Methodology: From Logic to Connection Graphs

The proposed approach consists of two primary phases: Detection and Synthesis.

  1. Connection Graphs: Logical rules are represented as graphs where nodes are axioms and edges represent unifiable literals.
  2. Potential Recursive Loops (PRLs): Cycles within these graphs are identified as PRLs, where variable changes suggest a recursive chain.
  3. Edge Classification: The system distinguishes between cycle edges (maintaining recursion) and exit edges (leading to base cases in the EDB).
Figure 3: Connection graph for the Ancestor relation, showing unifiable literals and variable substitutions.

Program Synthesis and Iterative Execution

Instead of relying on standard logical resolution at query time, the algorithm generates a compact iterative program. This program typically employs a Queue data structure to track new values discovered in each iteration. By enqueuing new values and dequeuing them to find related facts, the system "drives" the recursion until the queue is exhausted.

Figure 6: Synthesized iterative program snippet using queue operations (ENQUE/DEQUE) to handle recursion.

Key Insights

  • Compilation vs. Interpretation: The fundamental shift is "compiling" recursive rules into known algorithmic structures once, rather than solving the logic problem for every query.
  • The Driver Variable: Recursive loops typically feature a "driver" variable that changes per iteration (e.g., moving from child to parent). Identifying this is crucial for program synthesis.
  • Structural Sensitivity: The method accounts for structural differences like left-recursion versus right-recursion, which result in different iterative paths (e.g., moving "up" vs. "down" a family tree).
  • Guaranteed Termination: In databases without complex function signs, the number of unique constants is finite. A queue-based approach that enqueues only unique values is thus guaranteed to terminate.

Conclusion and Future Directions

This work provides a formal framework for identifying recursive structures and generating iterative code using WHILE, ENQUE, and DEQUE primitives. While robust for simple recursion, the authors note that "mutually recursive" rules or those involving complex function signs (e.g., $f(x)$) require more sophisticated control mechanisms. Future work involves optimizing these generated programs for massive, real-world datasets.

Summary updated

BibTeX
@inproceedings{naqvi1980performing,
  author = {Shamim A. Naqvi and Lawrence J. Henschen},
  title = {{Performing Inferences over Recursive Data Bases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}

Loading related content...

Figure