Optimizing recursive queries in SQL

ABSTRACT

Recursion represents an important addition to the SQL language. This work focuses on the optimization of linear recursive queries in SQL. To provide an abstract framework for discussion, we focus on computing the transitive closure of a graph. Three optimizations are studied: (1) Early evaluation of row selection conditions. (2) Eliminating duplicate rows in intermediate tables. (3) Defining an enhanced index to accelerate join computation. Optimizations are evaluated on two types of graphs: binary trees and sparse graphs. Binary trees represent an ideal graph with no cycles and a linear number of edges. Sparse graphs represent an average case with some cycles and a linear number of edges. In general, the proposed optimizations produce a significant reduction in the evaluation time of recursive queries.

REFERENCES

• 1: Donald D. Chamberlin , Raymond F. Boyce, SEQUEL: A structured English query language, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.249-264, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811515]
• 2: Stavros Cosmadakis, Inherent complexity of recursive queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.148-154, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303991]
• 3: Shaul Dar , Rakesh Agrawal , H. V. Jagadish, Optimization of Generalized Transitive Closure Queries, Proceedings of the Seventh International Conference on Data Engineering, p.345-354, April 08-12, 1991
• 4: Guozhu Dong , Jianwen Su, Incremental maintenance of recursive views using relational calculus/SQL, ACM SIGMOD Record, v.29 n.1, p.44-51, March 2000 [doi>10.1145/344788.344808]
• 5: M. J. Fischer and A. R. Meyer. Boolean matrix multiplication and transitive closure. In IEEE FOCS Conference, pages 129--131, 1971.
• 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: ISO-ANSI. Database Language SQL-Part2: SQL/Foundation. ANSI, ISO 9075--2 edition, 1999.
• 8: Kemal Koymen , Qujun Cai, SQL*: a recursive SQL, Information Systems, v.18 n.2, p.121-128, March 1993 [doi>10.1016/0306-4379(93)90009-P]
• 9: Volker Linnemann, Non First Normal Form Relations and Recursive Queries: An SQL-Based Approach, Proceedings of the Third International Conference on Data Engineering, p.591-598, February 03-05, 1987
• 10: P. Valduriez and H. Boral. Evaluation of recursive queries using join indices. In Expert Database Systems, pages 271--293, 1986.
• 11: Moshe Y. Vardi, Decidability and undecidability results for boundedness of linear recursive queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.341-351, March 1988, Austin, Texas, United States [doi>10.1145/308386.308470]
• 12: C. Wu and L. J. Henschen. Answering linear recursive queries in cyclic databases. In FGCS, pages 727--734, 1988.