Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Grahne et al. have presented a graph algorithm for a subset of recursive queries. This method consists of two phases. In the first phase, the method transforms a linear binary-chain program into a set of equations over expressions containing predicate symbols. In the second phase, a graph is constructed from the equations and the answers are produced by traversing the relevant paths. Here we describe a new algorithm which requires less time than the algorithm of Grahne et al. The key idea of the improvement is to reduce the search space that will be traversed when a query is invoked. Further, we speed up the evaluation of cyclic data by generating most answers directly in terms of the answers already found and the associated “path information” instead of traversing the corresponding paths as usual. In this way, our algorithm achieves a linear time complexity for both cyclic and non-cyclic data.

REFERENCES

• 1: Hussien Aly , Z. Meral Özsoyoglu, Synchronized Counting Method, Proceedings of the Fifth International Conference on Data Engineering, p.366-373, February 06-10, 1989
• 2: Francois Bancilhon, Naive evaluation of recursively defined relations, On knowledge base management systems: integrating artificial intelligence and d atabase technologies, Springer-Verlag New York, Inc., New York, NY, 1986
• 3: 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]
• 4: 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
• 5: Catriel Beeri , Raghu Ramakrishnan, On the power of magic, Journal of Logic Programming, v.10 n.3-4, p.255-299, April/May 1991 [doi>10.1016/0743-1066(91)90038-Q]
• 6: C. Chang, On the Evaluation of Queries Containing Derived Relations in Relational Database, in: Advances in Data Base Theory, Vol. 1, Plenum, 1981.
• 7: Y. Chen, Processing of Recursive Rules in Knowledgebased Systems, Forthcoming Ph.D. thesis, University of Kaiserslautern, Germany, 1994.
• 8: Y. Chen and T. H#rder, Graph Traversal and Linear Binary-chain Programs, ZRi-Report 4/94, University of Kaiserslautern, Germany, 1994.
• 9: 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]
• 10: Gösta Grahne , Seppo Sippu , Eljas Soisalon-Soininen, Efficient evaluation for a subset of recursive queries, Journal of Logic Programming, v.10 n.3-4, p.301-332, April/May 1991 [doi>10.1016/0743-1066(91)90039-R]
• 11: Jiawei Han , Kangsheng Zeng , Tong Lu, Normalization of Linear Recursions in Deductive Databases, Proceedings of the Ninth International Conference on Data Engineering, p.559-567, April 19-23, 1993
• 12: J. Hen and S. Chert, Graphic Representation of Linear Recursive Rules, Int. Journal Of Intelligent Systems, VOL. 7, 317-337 (1992)
• 13: J. Han and L.J.Henschen, The Level-Cycle Merging Method, Proc. 1st Int. Conf. on Deductive and Object-oriented Databases, Kyoto, 1989.
• 14: 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]
• 15: 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]
• 16: Wolfgang Nejdl, Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy, Proceedings of the 13th International Conference on Very Large Data Bases, p.43-50, September 01-04, 1987
• 17: 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]
• 18: S. Shapiro and D. Mckay, Inference with Recursive Rules, in: Proc. 1st Annual National Conference on Artificial Intelligence, 1980.
• 19: R. Tarjan, Depth-first Search and Linear Graph Algorithm, SIAM J. Comput. Vol. 1. No. 2. June 1972.
• 20: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 21: L. Vieille, From QSQ to QoSaQ: Global Optimization of Recursive Queries, Proc. 2th Int. Con}. on E#.pert Database System, L.Kerschberg ed., Charleston, 1988.
• 22: C. Wu and L.J. Henschen, Answering Linear Recursive Queries in Cyclic Databases, Proc. 1988 Int. Conf. on F,fth Gen. Computer Systems, Tokyo, 1988.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Theory, Verification