Abstract
We introduce the problem of page thrashing in the seminaive algorithm for computing recursive queries. We present techniques that take into consideration the system's paging behavior during query computation to reduce this page thrashing. We also propose a buffering strategy based on the Query Locality Set Model that reduces the total memory requirement of a recursive query. We present simulation results that demonstrate the effectiveness of our techniques, both in single and multi-user environments.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rakesh Agrawal, Shaul Dar, and H. V. Jagadish. Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Transactions on Database Systems, 15(3):427–458, September 1990.
Rakesh Agrawal and Jerry Kiernan. An Access Structure for Generalized Transitive Closure Queries. In Proc. 9th IEEE International Conference on Data Engineering, Vienna, April 1993.
Francois Bancilhon. Naive Evaluation of Recursively Defined Relations. Technical Report DB-004-85, MCC, 1985.
Francois Bancilhon and Raghu Ramakrishnan. An Amateur's Introduction to Recursive Query Processing Strategies. In Proc. ACM-SIGMOD International Conference on Management of Data, pages 16–52, Washington, D.C., May 1986.
Josephine Cheng, Donald Haderle, Richard Hedges, Bala Iyer, Theodore Messinger, C. Mohan, and Yun Wang. An Efficient Hybrid Join Algorithm: a DB2 Prototype. In Proc. 7th IEEE International Conference on Data Engineering, Kobe, April 1991.
Hong-Tai Chou and David J. DeWitt. An Evaluation of Buffer Management Strategies for Relational Database Systems. In Proc. 11th International Conference on Very Large Data Bases, Stockholm, August 1985.
Ulrich Güntzer, Werner Kiessling, and Rudolf Bayer. On the Evaluation of Recursion in (Deductive) Database Systems by Efficient Differential Fixpoint Iteration. In Proc. 3rd IEEE International Conference on Data Engineering, pages 120–129, Los Angeles, February 1987.
Robert Kabler, Yannis E. Ioannidis, and Michael J. Carey. Performance Evaluation of Algorithms for Transitive Closure. Information Systems, 17(5):415–441, September 1992.
P.-A. Larson and V. Deshpande. A File Structure Supporting Traversal Recursion. In Proc. ACM-SIGMOD International Conference on Management of Data, pages 243–252, Portland, May–June 1989.
H. Lu. New Strategies for Computing the Transitive Closure of a Database Relation. In Proc. 13th International Conference on Very Large Data Bases, Brighton, September 1987.
John McPherson and Hamid Pirahesh. Table Queue Evaluation Strategy. Research Report, IBM Almaden Research Center, 1991.
Giovanni Maria Sacco and Mario Schkolnick. A Mechanism for Managing the Buffer Pool in a Relational Database System using the Hot Set Model. In Proc. 8th International Conference on Very Large Data Bases, pages 257–262, Mexico City, September 1982.
Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, volume 2. Computer Science Press, 1989.
Patrick Valduriez and Haran Boral. Evaluation of Recursive Queries Using Join Indices. In Proc. 1st International Conference on Expert Database Systems, pages 197–208, Charleston, South Carolina, April 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agrawal, R., Kiernan, J. (1993). Reducing page thrashing in recursive query processing. In: Lomet, D.B. (eds) Foundations of Data Organization and Algorithms. FODO 1993. Lecture Notes in Computer Science, vol 730. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57301-1_15
Download citation
DOI: https://doi.org/10.1007/3-540-57301-1_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57301-2
Online ISBN: 978-3-540-48047-1
eBook Packages: Springer Book Archive