A correction of the termination conditions of the Henschen-Naqvi technique

ABSTRACT

Henschen and Naqvi described a technique for translating queries on recursively defined relations of a Datalog database into iterative programs that invoke a query processor for conventional select-project-join queries of the relational algebra. Although the technique has been cited as one of the most efficient available, it will in some cases fail to produce all answers defined by the usual semantics for such databases. The technique is reviewed, a recursive query is exhibited where it fails, the cause of failure is noted, and a correction is described. A graphical representation of the computation based on a formal representation of rule expansions is employed.

REFERENCES

• 1: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 2: David A. Briggs, Towards Determining Variable Overlap in Recursive Rule Expansions, University of Massachusetts, Amherst, MA, 1987
• 3: David Allan Briggs, Linear recursion and graph traversal, University of Massachusetts, Amherst, MA, 1988
• 4: G. Grahne , S. Sippu , E. Soisalon-Soininen, Efficient evaluation for a subset of recursive queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.284-293, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28690]
• 5: Ramsey W. Haddad , Jeffrey F. Naughton, Counting methods for cyclic relations, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.333-340, March 1988, Austin, Texas, United States [doi>10.1145/308386.308469]
• 6: Jiawei Han , Lawrence J. Henschen, Handling redundancy in the processing of recursive database queries, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.73-81, May 27-29, 1987, San Francisco, California, United States
• 7: Lawrence J. Henschen , Shamim A. Naqvi, On compiling queries in recursive first-order databases, Journal of the ACM (JACM), v.31 n.1, p.47-85, Jan. 1984 [doi>10.1145/2422.2423]
• 8: H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.331-344, May 27-29, 1987, San Francisco, California, United States
• 9: A. Marchetti-Spaccamella , A. Pelaggi , D. Sacca, Worst-case complexity analysis of methods for logic query implementation, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.294-301, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28691]
• 10: Jeff Naughton, Data independent recursion in deductive databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.267-279, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15420]
• 11: Domenico Sacca , Carlo Zaniolo, Magic counting methods, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.49-59, May 27-29, 1987, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Algorithms, Languages, Theory