An experimental performance study of a pipelined recursive query processing strategy

ABSTRACT

In [16] a pipelined strategy is presented for processing recursive queries in deductive database systems. As a follow-up, this paper studies the run-time performance of the proposed strategy. The algorithm, introduced informally by examples in this paper, is coded in occam2 and runs on a network of transputers. A wide range of recursive queries and database structures are used as benchmarks in this study. Both the speedup factors achieved and the elapsed time spent by the strategy in answering recursive queries are analysed. Experimental results show that it is possible to achieve significant performance improvement when queries are evaluated in parallel, and provide insights into the success of this strategy in meeting the primary objective of focusing on relevant data.

REFERENCES

• 1: R. Agrawal , H. V. Jagadish, Multiprocessor transitive closure algorithms, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.56-66, December 05-07, 1988, Austin, Texas, United States
• 2: 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
• 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, 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
• 5: 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
• 6: 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]
• 7: Jiawei Han , Hongjun Lu, Some Performance Results on Recursive Query Processing in Relational Database Systems, Proceedings of the Second International Conference on Data Engineering, p.533-541, February 05-07, 1986
• 8: 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]
• 9: G. Hulin, Parallel processing of recursive queries in distributed architectures, Proceedings of the 15th international conference on Very large data bases, p.87-96, July 1989, Amsterdam, The Netherlands
• 10: CORPORATE INMOS Limited, Transputer reference manual, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
• 11: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• 12: Jeffrey F. Naughton, Compiling separable recursions, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.312-319, June 01-03, 1988, Chicago, Illinois, United States
• 13: J. F. Naughton , R. Ramakrishnan , Y. Sagiv , J. D. Ullman, Efficient evaluation of right-, left-, and multi-linear rules, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.235-242, June 1989, Portland, Oregon, United States
• 14: 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
• 15: 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
• 16: J. Shao, D.A. Bell, M.E.C Hull, "A Pipelined Strategy for Processing Recursive Queries in Parallel", Internal Report, University of Ulster, submitted for publication, 1989.
• 17: Harold S. Stone, High-performance computer architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 18: Jeffrey D. Ullman, Implementation of logical query languages for databases, ACM Transactions on Database Systems (TODS), v.10 n.3, p.289-321, Sept. 1985 [doi>10.1145/3979.3980]
• 19: Patrick Valduriez , Georges Gardarin, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Transactions on Database Systems (TODS), v.9 n.1, p.133-161, March 1984 [doi>10.1145/348.318590]
• 20: Allen Van Gelder, A message passing framework for logical query evaluation, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.155-165, May 28-30, 1986, Washington, D.C., United States
• 21: L. Vieille, "Recursive Axioms in Deductive Databases: The Query/Subquery Approach", Proc. of Expert Database System Conf, 1986, pp 173-193.
• 22: O. Wolfson, Sharing the load of logic-program evaluation, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.46-55, December 05-07, 1988, Austin, Texas, United States
• 23: C. Zaniolo, D. Sacca, "The Rule Rewriting Methods in the Implementing of the Logic Data Language LDL", Proc of IFIP Conf. on "The Role of AI in Databases and Information Systems, 1988.

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Management, Performance