Multiple-Query Optimization.

Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988)
  author    = {Timos K. Sellis},
  title     = {Multiple-Query Optimization},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {1},
  year      = {1988},
  pages     = {23-52},
  ee        = {, db/journals/tods/Sellis88.html},
  bibsource = {DBLP,}


Some recently proposed extensions to relational database systems, as well as to deductive database systems, require support for multiple-query processing. For example, in a database system enhanced with inference capabilities, a simple query involving a rule with multiple definitions may expand to more than one actual query that has to be run over the database. It is an interesting problem then to come up with algorithms that process these queries together instead of one query at a time. The main motivation for performing such an interquery optimization lies in the fact that queries may share common data. We examine the problem of multiple-query optimization in this paper. The first major contribution of the paper is a systematic look at the problem, along with the presentation and analysis of algorithms that can be used for multiple-query optimization. The second contribution lies in the presentation of experimental results. Our results show that using multiple-query processing algorithms may reduce execution cost considerably.

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
Upen S. Chakravarthy, Daniel H. Fishman, Jack Minker: Semantic Query Optimization in Expert Systems and Database Systems. Expert Database Workshop 1984: 659-674 BibTeX
Upen S. Chakravarthy, Jack Minker: Processing Multiple Queries in Database Systems. IEEE Database Eng. Bull. 5(3): 38-43(1982) BibTeX
Upen S. Chakravarthy, Jack Minker, John Grant: Semantic Query Optimization: Additional Constraints and Control Strategies. Expert Database Conf. 1986: 345-379 BibTeX
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX
John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234 BibTeX
Antonin Guttman: New Features for Relational Database Systems to Support CAD Applications. Ph.D. thesis, University of California, Berkeley 1984
Patrick A. V. Hall: Common Subexpression Identification in General Algebraic Systems. Technical Rep. UKSC 0060, IBM United Kingdom Scientific Centre : (1974) BibTeX
Patrick A. V. Hall: Optimization of a Single Relation Expression in a Relational Data Base System. IBM J. Res. Dev. 20(3): 244-257(1976) BibTeX
Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 BibTeX
Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205 BibTeX
Won Kim: Global Optimization of Relational Queries: A First Step. Query Processing in Database Systems 1985: 206-216 BibTeX
Ru-Mei Kung, Eric N. Hanson, Yannis E. Ioannidis, Timos K. Sellis, Leonard D. Shapiro, Michael Stonebraker: Heuristic Search in Data Base Systems. Expert Database Workshop 1984: 537-548 BibTeX
Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 BibTeX
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 BibTeX
Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982) BibTeX
Nick Roussopoulos: The Logical Access Path Schema of a Database. IEEE Trans. Software Eng. 8(6): 563-573(1982) BibTeX
Timos K. Sellis, Leonard D. Shapiro: Optimization of Extended Database Query Languages. SIGMOD Conference 1985: 424-436 BibTeX
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX

Referenced by

  1. Weifa Liang, Maria E. Orlowska, Jeffrey Xu Yu: Optimizing Multiple Dimensional Queries Simultaneously in Multidimensional Databases. VLDB J. 8(3-4): 319-338(2000)
  2. Prasan Roy, S. Seshadri, S. Sudarshan, Siddhesh Bhobe: Efficient and Extensible Algorithms for Multi Query Optimization. SIGMOD Conference 2000: 249-260
  3. Jianjun Chen, David J. DeWitt, Feng Tian, Yuan Wang: NiagaraCQ: A Scalable Continuous Query System for Internet Databases. SIGMOD Conference 2000: 379-390
  4. Jayavel Shanmugasundaram, Kristin Tufte, Chun Zhang, Gang He, David J. DeWitt, Jeffrey F. Naughton: Relational Databases for Querying XML Documents: Limitations and Opportunities. VLDB 1999: 302-314
  5. Daniela Florescu, Alon Y. Levy, Dan Suciu, Khaled Yagoub: Optimization of Run-time Management of Data Intensive Web-sites. VLDB 1999: 627-638
  6. Damianos Chatziantoniou: Evaluation of Ad Hoc OLAP: In-Place Computation. SSDBM 1999: 34-43
  7. Dimitri Theodoratos: Detecting Redundancy in Data Warehouse Evolution. ER 1999: 340-353
  8. Fa-Chung Fred Chen, Margaret H. Dunham: Common Subexpression Processing in Multiple-Query Processing. IEEE Trans. Knowl. Data Eng. 10(3): 493-499(1998)
  9. Minos N. Garofalakis, Yannis E. Ioannidis, Banu Özden: Resource Scheduling for Composite Multimedia Objects. VLDB 1998: 74-85
  10. Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton, Amit Shukla: Simultaneous Optimization and Evaluation of Multiple Dimensional Queries. SIGMOD Conference 1998: 271-282
  11. Subbu N. Subramanian, Shivakumar Venkataraman: Cost-Based Optimization of Decision Support Queries Using Transient Views. SIGMOD Conference 1998: 319-330
  12. Jun Rao, Kenneth A. Ross: Reusing Invariants: A New Strategy for Correlated Queries. SIGMOD Conference 1998: 37-48
  13. Dimitri Theodoratos, Timos K. Sellis: Data Warehouse Schema and Instance Design. ER 1998: 363-376
  14. Apostolos Papadopoulos, Yannis Manolopoulos: Multiple Range Query Optimization in Spatial Databases. ADBIS 1998: 71-82
  15. Manish Mehta, David J. DeWitt: Data Placement in Shared-Nothing Parallel Database Systems. VLDB J. 6(1): 53-72(1997)
  16. Dimitri Theodoratos, Timos K. Sellis: Data Warehouse Configuration. VLDB 1997: 126-135
  17. Himanshu Gupta: Selection of Views to Materialize in a Data Warehouse. ICDT 1997: 98-112
  18. Wilburt Labio, Dallan Quass, Brad Adelberg: Physical Database Design for Data Warehouses. ICDE 1997: 277-288
  19. Ming-Syan Chen, Philip S. Yu, Kun-Lung Wu: Optimization of Parallel Execution for Multi-Join Queries. IEEE Trans. Knowl. Data Eng. 8(3): 416-428(1996)
  20. Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conference 1996: 447-458
  21. Joseph M. Hellerstein, Jeffrey F. Naughton: Query Execution Techniques for Caching Expensive Methods. SIGMOD Conference 1996: 423-434
  22. Yigit Kulabas, Özgür Ulusoy: Heuristic Algorithms for Inter-Query Scheduling in Database Systems. ADBIS 1996: 141-145
  23. Bojan Groselj, Qutaibah M. Malluhi: Combinatorial Optimization of Distributed Queries. IEEE Trans. Knowl. Data Eng. 7(6): 915-927(1995)
  24. Ram D. Gopal, Ram Ramesh: The Query Clustering Problem: A Set Partitioning Approach. IEEE Trans. Knowl. Data Eng. 7(6): 885-899(1995)
  25. Hongjun Lu, Kian-Lee Tan: Batch Query Processing in Shared-Nothing Multiprocessors. DASFAA 1995: 238-245
  26. Wei Sun, Mark Allen Weiss: An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities. IEEE Trans. Knowl. Data Eng. 6(6): 997-1001(1994)
  27. Martin L. Kersten, M. F. N. de Boer: Query Optimization Strategies for Browsing Sessions. ICDE 1994: 478-487
  28. Jamal R. Alsabbagh, Vijay V. Raghavan: Analysis of Common Subexpression Exploitation Models in Multiple-Query Processing. ICDE 1994: 488-497
  29. Christian S. Jensen, Leo Mark, Nick Roussopoulos, Timos K. Sellis: Using Differential Techniques to Efficiently Support Transaction Time. VLDB J. 2(1): 75-111(1993)
  30. John Grant, Witold Litwin, Nick Roussopoulos, Timos K. Sellis: Query Languages for Relational Multidatabases. VLDB J. 2(2): 153-171(1993)
  31. Song Bong Yoo, Phillip C.-Y. Sheu: Evaluation and Optimization of Query Programs in an Object-Oriented and Symbolic Information System. IEEE Trans. Knowl. Data Eng. 5(3): 479-495(1993)
  32. Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Coupling Production Systems and Database Systems: A Homogeneous Approach. IEEE Trans. Knowl. Data Eng. 5(2): 240-256(1993)
  33. Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554
  34. Manish Mehta, Valery Soloviev, David J. DeWitt: Batch Scheduling in Parallel Database Systems. ICDE 1993: 400-410
  35. Michael Siegel, Edward Sciore, Sharon C. Salveter: A Method for Automatic Rule Derivation to Support Semantic Query Optimization. ACM Trans. Database Syst. 17(4): 563-600(1992)
  36. Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
  37. Peter Bodorik, J. Spruce Riordon, James S. Pyra: Deciding on Correct Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 4(3): 253-265(1992)
  38. Daniel F. Lieuwen, David J. DeWitt: A Transformation-Based Approach to Optimizing Loops in Database Programming Languages. SIGMOD Conference 1992: 91-100
  39. Thodoros Topaloglou, Arantza Illarramendi, Licia Sbattella: Query Optimization for KBMSs: Temporal, Syntactic and Semantic Transformantions. ICDE 1992: 310-319
  40. Nick Roussopoulos: An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis. ACM Trans. Database Syst. 16(3): 535-563(1991)
  41. Sharma Chakravarthy: Divide and Conquer: A Basis for Augmenting a Conventional Query Optimizer with Multiple Query Proceesing Capabilities. ICDE 1991: 482-490
  42. Daniel F. Lieuwen, David J. DeWitt: Optimizing Loops in Database Programming Languages. DBPL 1991: 287-305
  43. Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990)
  44. Timos K. Sellis, Subrata Ghosh: On the Multiple-Query Optimization Problem. IEEE Trans. Knowl. Data Eng. 2(2): 262-266(1990)
  45. Witold Litwin, Leo Mark, Nick Roussopoulos: Interoperability of Multiple Autonomous Databases. ACM Comput. Surv. 22(3): 267-293(1990)
  46. Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321
  47. Edward Sciore, John Sieg Jr.: A Modular Query Optimizer Generator. ICDE 1990: 146-153
  48. Hyuck Yoo, Stéphane Lafortune: An Intelligent Search Method for Query Optimization by Semijoins. IEEE Trans. Knowl. Data Eng. 1(2): 226-237(1989)
  49. Arie Segev, Jooseok Park: Updating Distributed Materialized Views. IEEE Trans. Knowl. Data Eng. 1(2): 173-184(1989)
  50. Xian-He Sun, Nabil Kamel, Lionel M. Ni: Solving Implication Problems in Database Applications. SIGMOD Conference 1989: 185-192
  51. Nikolaus Steger, Helmut Schmidt, Ulrich Güntzer, Werner Kießling: Semantics and Efficient Compilation for Quantitative Deductive Databases. ICDE 1989: 660-669
  52. Arie Segev, Jooseok Park: Maintaining Materialized Views in Distributed Databases. ICDE 1989: 262-270
  53. Nobuhiro Ajitomi, Hiroyasu Kurose: An Enhanced RETE Algorithm for Large Scale Data Access. DASFAA 1989: 117-124
  54. Anant Jhingran: A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures. VLDB 1988: 88-99
  55. Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms. SIGMOD Conference 1988: 404-412
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:04 2008