Counting methods for cyclic relations

ABSTRACT

In this paper we consider selections of the form “column = constant” on relations defined by linear recursive, two rule datalog programs. In general, counting methods perform well on such queries. However, counting methods fail in the presence of cycles in the database. We present an algorithm in the spirit of counting methods that correctly deals with cyclic data and has the same asymptotic running time as counting methods. The algorithm, which is based on reducing a query on a database to a question about intersections of semi-linear sets, works by using efficient methods to construct the appropriate semi-linear sets from the database and query constant.

REFERENCES

• BMSU86: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• BR86: F. Bancilhon , R. Ramakrishnan, Performance evaluation of data intensive logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• BR87: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• Bri86: D A Bnggs A Reconssderatzon of the Terrnznatzon Condztzons of the Henschen-Naqm Technzque Techmcal Report COINS 87-11, Umverslty of Massachusetts at Amherst, September 1986.
• GSS87: 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]
• HH87: 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
• HN84: 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]
• MPS87: 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]
• Nau87: J. F. Naughton, One-sided recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.340-348, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28695]
• SZ86a: Domenico Saccá , Carlo Zaniolo, The generalized counting method for recursive logic queries, Proceedings on International conference on database theory, p.31-53, December 1986, Rome, Italy
• SZ86b: Domenico Saccà , Carlo Zaniolo, On the implementation of a simple class of logic queries for databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.16-23, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6013]
• SZ87: 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
• Tar72: R.E. Tarjan. Depth first search and linear graph algorathms SL4M Journal of Computzng, 1(2) 146-160. 1972.