Efficient evaluation for a subset of recursive queries

ABSTRACT

Well-known results on graph traversal are used to develop a practical, efficient algorithm for evaluating regularly and linearly recursive queries in databases that contain only binary relations. Transformations are given that reduce a subset of regular and linear queries involving n-ary relations (n > 2) to queries involving only binary relations.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 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, ACM SIGMOD Record, v.15 n.2, p.16-52, June 1986
• 5: C.Chang: On the evaluatlon of querles confalnlng derlved relatlons in relatlonal databases. In: Advances in Data Base Theory, Vol 1 Plenum Press, 1981.
• 6: 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]
• 7: H. B. Hunt, III , J. D. Ullman , T. G. Szymanski, Operations on sparse relations, Communications of the ACM, v.20 n.3, p.171-176, March 1977 [doi>10.1145/359436.359446]
• 8: M Kifer and E.Lozlnsk~l. A framework for an efflcient implementatlon of deductive database systems. Proc. 6th Advanced Database Symp., Tokyo, 1986.
• 9: Michael Kifer , Eliezer L Lozinskii, Filtering data flow in deductive databases, Proceedings on International conference on database theory, p.186-202, December 1986, Rome, Italy
• 10: J.Kulttinen: Binary relations and relatzonal expresslons (in Finnish). Internal Report, Dept. of Computer Sc~., Univ. of Helsank~, 1986.
• 11: E.Lozlnskil: Evaluating queries in deductlve databases by generating. Proc. 11th Internat. Jolnt Conf. on Artlflcial Intelllgence, 1985.
• 12: 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
• 13: S.Shaplro and D.McKay. Inference wlth recursive rules Proc Ist Annual National Conf on ArtJf}clal Intelllqence, 1980.
• 14: Seppo Sippu , Eljas Soisalon-Soininen, On the Use of Relational Expressions in the Design of Efficient Algorithms (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.456-464, July 15-19, 1985
• 15: T.Szymanskl and J.Ullman: Evaluating relational exure~blonb wlth dense and sparse arguments. SIAM J. Comput. 6-I (1977).
• 16: R Tar3an: Depth-flrst search and l~near graph algorithms. SIAM J. Comput. 1-2 (1972).
• 17: L.Vieille: Recursive axioms in deductive databases- the Query/Subquery aporoach. Proc. 1st Internat. Conf. on Expert Database Systems, 1986.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

General Terms:
Algorithms, Management, Measurement, Performance, Theory