Multiple-query optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multiple-query optimization

Full text

Pdf (2.19 MB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 13 , Issue 1 (March 1988) table of contents

Pages: 23 - 52

Year of Publication: 1988

ISSN:0362-5915

Author

Timos K. Sellis

Univ. of Maryland, College Park

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 43, Downloads (12 Months): 251, Citation Count: 132

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/42201.42203 What is a DOI?

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
	2	U S Chakravarthy , D H Fishman , J Minker, Semantic query optimization in expert systems and database systems, Proceedings from the first international workshop on Expert database systems, p.659-674, January 1986, Kiawah Island, South Carolina, United States
	3	CHAKRAVARTHY, U. S., AND MINKER, J. Processing multiple queries in database systems. Database Eng. 5, 3 (Sept. 1982), 38-44.
	4	CHAKRAVARTHY, U. S., AND MINKER, J. Multiple query processing in deductive databases. Tech. Rep. TR-1554, Dept. of Computer Science, Univ. of Maryland, College Park, Md., Aug. 1985.
	5	CHAKRAVARTHY, U. S., MINKER, J., AND GRANT, J. Semantic query optimization: additional constraints and control strategies. In Proceedings of the 1st International Conference on Expert Database Systems (Charleston, S. C., April 1986). Institute of Information Management and Policy, Univ. of South Carolina, Apr. 1986, 259-270.
	6	W. F. Clocksin , C. S. Mellish, Programming in Prolog, Springer-Verlag New York, Inc., New York, NY, 1987
	7	Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582400]
	8	Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
	9	GRANT, J., AND MINKER, J. On optimizing the evaluation of a set of expressions. Tech. Rep. TR-916, Univ. of Maryland, College Park, Md., July 1980.
	10	GRANT, J., AND MINKER, J. Optimization in deductive and conventional relational database systems. In Advances in Data Base Theory, Vol. 1, H. Gallaire, J. Minker, and J.-M. Nicolas, Eds. Plenum Press, New York, 1981, 195-234.
	11	GU2"rMAN, A. New features for relational database systems to support CAD applications. Ph.D. dissertation, Computer Science Div., Univ. of California, Berkeley, June 1984.
	12	HALL, P. V. Common subexpression identification in general algebraic systems, Tech. Rep. UKSC 0060, IBM United Kingdom Scientific Centre, Nov. 1974.
	13	HALL, P.V. Optimization of a single relational expression in a relational data base system. IBM J. Res. Dev. 20, 3 (May 1976), 244-257.
	14	IOANNIDIS, Y. Processing recursion in deductive database systems. Ph.D. dissertation, Univ. of California, Berkeley, July 1986.
	15	Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	16	JARKE, M. Common subexpression isolation in multiple query optimization. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer-Verlag, New York, 1984, 191-205.
	17	KIM, W. Global optimization of relational queries: a first step. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds. Springer-Verlag, New York, 1984, 206-216.
	18	R-M Kung , E Hanson , Y Ioannidis , T Sellis , L Shapiro , M Stonebraker, Heuristic search in database systems, Proceedings from the first international workshop on Expert database systems, p.537-548, January 1986, Kiawah Island, South Carolina, United States
	19	LARSON, P., AND YANG, H. Computing queries from derived relations. In Proceedings of International Conference on Very Large Data Bases (Stockholm, Aug. 1985), 259-269.
	20	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]
	21	N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
	22	RELATIONAL TECHNOLOGY, INC. EQUEL/C User's Guide. Version 2.1, Relational Technology, Inc., Berkeley, Calif., July 1984.
	23	ROSENKRANTZ, D. J., AND HUNT, H. B. Processing conjunctive predicates and queries. In Proceedings of the International Conference on Very Large Data Bases (Montreal, Oct. 1980), 64-72.
	24	Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982 [doi>10.1145/319702.319729]
	25	I~OUSSOPOULOS, N. The logical access path schema of a database. IEEE "l'rans. Softw. Eng. SE-8, 6 (Nov. 1982), 563-573.
	26	Timos K. Sellis , Leonard Shapiro, Optimization of extended database query languages, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.424-436, May 1985, Austin, Texas, United States
	27	Michael Stonebraker , Lawrence A. Rowe, The design of POSTGRES, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.340-355, May 28-30, 1986, Washington, D.C., United States
	28	Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
	29	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]
	30	Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
	31	Carlo Zaniolo, The database language GEM, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California

CITED BY 132

	Ladjel Bellatreche , Kamalakar Karlapalem , Michel Schneider, On efficient storage space distribution among materialized views and indices in data warehousing environments, Proceedings of the ninth international conference on Information and knowledge management, p.397-404, November 06-11, 2000, McLean, Virginia, United States
	Nicholas Roussopoulos, An incremental access method for ViewCache: concept, algorithms, and cost analysis, ACM Transactions on Database Systems (TODS), v.16 n.3, p.535-563, Sept. 1991
	Dieter Pfoser , Christian S. Jensen, Querying the trajectories of on-line mobile objects, Proceedings of the 2nd ACM international workshop on Data engineering for wireless and mobile access, p.66-73, May 2001, Santa Barbara, California, United States
	Hoshi Mistry , Prasan Roy , S. Sudarshan , Krithi Ramamritham, Materialized view selection and maintenance using multi-query optimization, ACM SIGMOD Record, v.30 n.2, p.307-318, June 2001
	Jun Rao , Kenneth A. Ross, Reusing invariants: a new strategy for correlated queries, ACM SIGMOD Record, v.27 n.2, p.37-48, June 1998
	Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000
	Kenneth A. Ross , Divesh Srivastava , S. Sudarshan, Materialized view maintenance and integrity constraint checking: trading space for time, ACM SIGMOD Record, v.25 n.2, p.447-458, June 1996
	Xian-He Sun , Nabil Kamel , Lionel M. Ni, Solving implication problems in database applications, ACM SIGMOD Record, v.18 n.2, p.185-192, June 1989
	Donald Kossmann , Michael J. Franklin , Gerhard Drasch , Wig Ag, Cache investment: integrating query optimization and distributed data placement, ACM Transactions on Database Systems (TODS), v.25 n.4, p.517-558, Dec. 2000
	P. Bodorik , J. S. Riordon , C. Jacob, Dynamic distributed query processing techniques, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.348-357, February 21-23, 1989, Louisville, Kentucky
	Subbu N. Subramanian , Shivakumar Venkataraman, Cost-based optimization of decision support queries using transient-views, ACM SIGMOD Record, v.27 n.2, p.319-330, June 1998
	Daniel F. Lieuwen , David J. DeWitt, A transformation-based approach to optimizing loops in database programming languages, ACM SIGMOD Record, v.21 n.2, p.91-100, June 1, 1992
	Joseph M. Hellerstein , Jeffrey F. Naughton, Query execution techniques for caching expensive methods, ACM SIGMOD Record, v.25 n.2, p.423-434, June 1996
	Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, ACM SIGMOD Record, v.29 n.2, p.249-260, June 2000
	Gene Fuh , Jyh-Herng Chow , Nelson Mattos , Brian Tran, Supporting procedural constructs in existing SQL compilers, Proceedings of the 1996 conference of the Centre for Advanced Studies on Collaborative research, p.11, November 12-14, 1996, Toronto, Ontario, Canada
	Nilesh N. Dalvi , Sumit K. Sanghai , Prasan Roy , S. Sudarshan, Pipelining in multi-query optimization, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.59-70, May 2001, Santa Barbara, California, United States
	Michael Siegel , Edward Sciore , Sharon Salveter, A method for automatic rule derivation to support semantic query optimization, ACM Transactions on Database Systems (TODS), v.17 n.4, p.563-600, Dec. 1992
	J. Thomas , B. Mitschang , N. Mattos , S. Deßloch, Enhancing knowledge processing in client/server environments, Proceedings of the second international conference on Information and knowledge management, p.324-334, November 01-05, 1993, Washington, D.C., United States
	Ahmet Cosar , Ee-Peng Lim , Jaideep Srivastava, Multiple query optimization with Depth-First Branch-and-Bound and dynamic query ordering, Proceedings of the second international conference on Information and knowledge management, p.433-438, November 01-05, 1993, Washington, D.C., United States
	Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton , Amit Shukla, Simultaneous optimization and evaluation of multiple dimensional queries, ACM SIGMOD Record, v.27 n.2, p.271-282, June 1998
	Dimitri Theodoratos , Mokrane Bouzeghoub, A general framework for the view selection problem for data warehouse design and evolution, Proceedings of the 3rd ACM international workshop on Data warehousing and OLAP, p.1-8, November 06-11, 2000, McLean, Virginia, United States
	T. Sellis , C. C. Lin , L. Raschid, Implementing large production systems in a DBMS environment: concepts and algorithms, ACM SIGMOD Record, v.17 n.3, p.404-423, June 1988
	Paolo Barone , Paola Bonizzoni , Gianluca Delta Vedova , Giancarlo Mauri, An approximation algorithm for the shortest common supersequence problem: an experimental analysis, Proceedings of the 2001 ACM symposium on Applied computing, p.56-60, March 2001, Las Vegas, Nevada, United States
	A. Segev , J. Park, Updating Distributed Materialized Views, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.173-184, June 1989
	Chengwen Liu , Andrei Ursu, A framework for global optimization of aggregate queries, Proceedings of the sixth international conference on Information and knowledge management, p.262-269, November 10-14, 1997, Las Vegas, Nevada, United States
	W. Sun , M. A. Weiss, An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities, IEEE Transactions on Knowledge and Data Engineering, v.6 n.6, p.997-1001, December 1994
	Henrique Andrade , Tahsin Kurc , Alan Sussman , Joel Saltz, Efficient execution of multiple query workloads in data analysis applications, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.53-53, November 10-16, 2001, Denver, Colorado
	Witold Litwin , Leo Mark , Nick Roussopoulos, Interoperability of multiple autonomous databases, ACM Computing Surveys (CSUR), v.22 n.3, p.267-293, Sept. 1990
	Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, ACM SIGMOD Record, v.19 n.2, p.312-321, Jun. 1990
	Upen S. Chakravarthy , John Grant , Jack Minker, Logic-based approach to semantic query optimization, ACM Transactions on Database Systems (TODS), v.15 n.2, p.162-207, June 1990
	T. Sellis , C.-C. Lin , L. Raschid, Coupling Production Systems and Database Systems: A Homogeneous Approach, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.240-256, April 1993
	W. Lehner , W. Hümmer , L. Schlesinger , A. Bauer, On the problem of generating common predecessors, Proceedings of the 5th ACM international workshop on Data Warehousing and OLAP, p.43-48, November 08-08, 2002, McLean, Virginia, USA
	Minwen Ji, Affinity-based management of main memory database clusters, ACM Transactions on Internet Technology (TOIT), v.2 n.4, p.307-339, November 2002
	T. Sellis , S. Ghosh, On the Multiple-Query Optimization Problem, IEEE Transactions on Knowledge and Data Engineering, v.2 n.2, p.262-266, June 1990
	S. B. Yoo , P. C.-Y. Sheu, Evaluation and Optimization of Query Programs in an Object-Oriented and Symbolic Information System, IEEE Transactions on Knowledge and Data Engineering, v.5 n.3, p.479-495, June 1993
	Brian Dunkel , Qiang Zhu , Wing Lau , Suyun Chen, Multiple-granularity interleaving for piggyback query processing, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.2, November 08-11, 1999, Mississauga, Ontario, Canada
	Ming-Syan Chen , Philip S. Yu , Kun-Lung Wu, Optimization of Parallel Execution for Multi-Join Queries, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.416-428, June 1996
	Nilesh N. Dalvi , Sumit K. Sanghai , Prasan Roy , S. Sudarshan, Pipelining in multi-query optimization, Journal of Computer and System Sciences, v.66 n.4, p.728-762, 1 June 2003
	Neoklis Polyzotis, Selectivity-based partitioning: a divide-and-union paradigm for effective query optimization, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Fa-Chung Fred Chen , Margaret H. Dunham, Common Subexpression Processing in Multiple-Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.493-499, May 1998
	Mohamed F. Mokbel , Walid G. Aref , Susanne E. Hambrusch , Sunil Prabhakar, Towards scalable location-aware services: requirements and research issues, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.110-117, November 07-08, 2003, New Orleans, Louisiana, USA
	Feng Tian , Berthold Reinwald , Hamid Pirahesh , Tobias Mayr , Jussi Myllymaki, Implementing a scalable XML publish/subscribe system using relational database systems, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Dimitri Theodoratos , Wugang Xu, Constructing search spaces for materialized view selection, Proceedings of the 7th ACM international workshop on Data warehousing and OLAP, November 12-13, 2004, Washington, DC, USA
	Yannis Kotidis , Nick Roussopoulos, A case for dynamic view management, ACM Transactions on Database Systems (TODS), v.26 n.4, p.388-423, December 2001
	P. Bodorik , J. S. Riordon, Heuristic algorithms for distributed query processing, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.144-155, December 05-07, 1988, Austin, Texas, United States
	P. Bodorik , J. Pyra , J. S. Riordon, Correcting execution of distributed queries, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.192-201, July 02-04, 1990, Dublin, Ireland
	Timos K. Sellis , Leonard Shapiro, Query Optimization for Nontraditional Database Applications, IEEE Transactions on Software Engineering, v.17 n.1, p.77-86, January 1991
	P. Bodorik , J. S. Riordan , J. S. Pyra, Deciding to Correct Distributed Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.4 n.3, p.253-265, June 1992
	Ivan T. Bowman , Kenneth Salem, Optimization of query streams using semantic prefetching, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Suresh Aryangat , Henrique Andrade , Alan Sussman, Time and space optimization for processing groups of multi-dimensional scientific queries, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Huamin Chen , Prasant Mohapatra, Using service brokers for accessing backend servers for web applications, Journal of Network and Computer Applications, v.28 n.1, p.57-74, January 2005
	Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Dimitri Theodoratos , Timos Sellis, Incremental Design of a Data Warehouse, Journal of Intelligent Information Systems, v.15 n.1, p.7-27, July—Aug. 2000
	H. Yoo , S. Lafortune, An Intelligent Search Method for Query Optimization by Semijoins, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.226-237, June 1989
	Ismail H. Toroslu , Ahmet Cosar, Dynamic programming solution for multiple query optimization problem, Information Processing Letters, v.92 n.3, p.149-155, 15 November 2004
	Vinay Kanitkar , Alex Delis, Efficient processing of client transactions in real-time, Distributed and Parallel Databases, v.17 n.1, p.39-74, January 2005
	Rui Zhang , Nick Koudas , Beng Chin Ooi , Divesh Srivastava, Multiple aggregations over data streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Ram D. Gopal , R. Ramesh, The Query Clustering Problem: A Set Partitioning Approach, IEEE Transactions on Knowledge and Data Engineering, v.7 n.6, p.885-899, December 1995
	Bojan Groselj , Qutaibah M. Malluhi, Combinatorial Optimization of Distributed Queries, IEEE Transactions on Knowledge and Data Engineering, v.7 n.6, p.915-927, December 1995
	Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
	Panos Kalnis , Dimitris Papadias, Multi-query optimization for on-line analytical processing, Information Systems, v.28 n.5, p.457-473, July 2003
	Shimin Chen , Anastassia Ailamaki , Phillip B. Gibbons , Todd C. Mowry, Inspector joins, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Shen-Tat Goh , Beng Chin Ooi , Kian-Lee Tan, Demand-Driven Caching in Multiuser Environment, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.112-124, January 2004
	Stavros Harizopoulos , Vladislav Shkapenyuk , Anastassia Ailamaki, QPipe: a simultaneously pipelined relational query engine, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Ruoming Jin , Kaushik Sinha , Gagan Agrawal, Simultaneous optimization of complex mining tasks with a knowledgeable cache, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	K. O'Gorman , A. El Abbadi , D. Agrawal, Multiple query optimization in middleware using query teamwork, Software—Practice & Experience, v.35 n.4, p.361-391, 10 April 2005
	Ivan T. Bowman , Kenneth Salem, Optimization of query streams using semantic prefetching, ACM Transactions on Database Systems (TODS), v.30 n.4, p.1056-1101, December 2005
	Himanshu Gupta , Inderpal Singh Mumick, Selection of Views to Materialize in a Data Warehouse, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.24-43, January 2005
	Zhimin Chen , Vivek Narasayya, Efficient computation of multiple group by queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Boon Thau Loo , Tyson Condie , Joseph M. Hellerstein , Petros Maniatis , Timothy Roscoe , Ion Stoica, Implementing declarative overlays, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
	Bernhard Stegmaier , Richard Kuntschke , Alfons Kemper, StreamGlobe: adaptive query processing and optimization in streaming P2P environments, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada
	Damianos Chatziantoniou , Kenneth A. Ross, Partitioned optimization of complex queries, Information Systems, v.32 n.2, p.248-282, April, 2007
	Christian S. Jensen , Leo Mark , Nick Roussopoulos , Timos Sellis, Using differential techniques to efficiently support transaction time, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.75-116, January 1993
	John Grant , Witold Litwin , Nick Roussopoulos , Timos Sellis, Query languages for relational multidatabases, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.2, April 1993
	Sailesh Krishnamurthy , Chung Wu , Michael Franklin, On-the-fly sharing for streamed aggregation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Nicolas Bruno , Surajit Chaudhuri, Physical design refinement: The ‘merge-reduce’ approach, ACM Transactions on Database Systems (TODS), v.32 n.4, p.28-es, November 2007
	Henrique Andrade , Tahsin Kurc , Alan Sussman , Joel Saltz, Active semantic caching to optimize multidimensional data analysis in parallel and distributed environments, Parallel Computing, v.33 n.7-8, p.497-520, August, 2007
	Lukasz Golab , Theodore Johnson , Oliver Spatscheck, Prefilter: predicate pushdown at streaming speeds, Proceedings of the 2nd international workshop on Scalable stream processing system, March 29-29, 2008, Nantes, France
	Nabil Kamel , Roger King, Intelligent database caching through the use of page-answers and page-traces, ACM Transactions on Database Systems (TODS), v.17 n.4, p.601-646, Dec. 1992
	Clint Morgan , Kris De Volder , Eric Wohlstadter, A static aspect language for checking design rules, Proceedings of the 6th international conference on Aspect-oriented software development, March 12-16, 2007, Vancouver, British Columbia, Canada
	Young-Kyoon Suh , Jin Hyun Son , Myoung Ho Kim, GAGPC: optimization of multiple continuous queries on data, Proceedings of the 24th IASTED international conference on Database and applications, p.215-220, February 13-15, 2006, Innsbruck, Austria
	Song Wang , Elke Rundensteiner , Samrat Ganguly , Sudeept Bhatnagar, State-slice: new paradigm of multi-query optimization of window-based stream queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Gang Luo, Efficient detection of empty-result queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Mohamed A. Sharaf , Panos K. Chrysanthis , Alexandros Labrinidis , Kirk Pruhs, Efficient scheduling of heterogeneous continuous queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Ruoming Jin , Kaushik Sinha , Gagan Agrawal, A framework to support multiple query optimization for complex mining tasks, Proceedings of the 6th international workshop on Multimedia data mining: mining integrated media and complex data, p.23-32, August 21-21, 2005, Chicago, Illinois
	Quinn Hart , Michael Gertz, Optimization of multiple continuous queries over streaming satellite data, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA
	Wugang Xu , Dimitri Theodoratos , Calisto Zuzarte, Computing closest common subexpressions for view selection problems, Proceedings of the 9th ACM international workshop on Data warehousing and OLAP, November 10-10, 2006, Arlington, Virginia, USA
	Bin Liu , Elke A. Rundensteiner , David Finkel, Maintaining large update batches by restructuring and grouping, Information Systems, v.32 n.4, p.621-639, June, 2007
	Jingren Zhou , Per-Ake Larson , Johann-Christoph Freytag , Wolfgang Lehner, Efficient exploitation of similar subexpressions for query processing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Ki Yong Lee , Jin Hyun Son , Myoung Ho Kim, Reducing the cost of accessing relations in incremental view maintenance, Decision Support Systems, v.43 n.2, p.512-526, March, 2007
	Rubao Lee , Minghong Zhou , Huaming Liao, Request Window: an approach to improve throughput of RDBMS-based data integration system by utilizing data sharing across concurrent distributed queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Yanlei Diao , Michael Franklin, Query processing for high-volume XML message brokering, Proceedings of the 29th international conference on Very large data bases, p.261-272, September 09-12, 2003, Berlin, Germany
	Sailesh Krishnamurthy , Michael J. Franklin , Joseph M. Hellerstein , Garrett Jacobson, The case for precision sharing, Proceedings of the Thirtieth international conference on Very large data bases, p.972-984, August 31-September 03, 2004, Toronto, Canada
	Arvind Arasu , Jennifer Widom, Resource sharing in continuous sliding-window aggregates, Proceedings of the Thirtieth international conference on Very large data bases, p.336-347, August 31-September 03, 2004, Toronto, Canada
	Rakesh Agrawal , Roberto Bayardo , Christos Faloutsos , Jerry Kiernan , Ralf Rantzau , Ramakrishnan Srikant, Auditing compliance with a Hippocratic database, Proceedings of the Thirtieth international conference on Very large data bases, p.516-527, August 31-September 03, 2004, Toronto, Canada
	Tobias Kraft , Holger Schwarz, CHICAGO: a test and evaluation environment for coarse-grained optimization, Proceedings of the Thirtieth international conference on Very large data bases, p.1345-1348, August 31-September 03, 2004, Toronto, Canada
	Yan Zhang , Zhi-Feng Chen , Yuan-Yuan Zhou, Efficient execution of multiple queries on deep memory hierarchy, Journal of Computer Science and Technology, v.22 n.2, p.273-279, March 2007
	Tobias Kraft , Holger Schwarz , Ralf Rantzau , Bernhard Mitschang, Coarse-grained optimization: techniques for rewriting SQL statement sequences, Proceedings of the 29th international conference on Very large data bases, p.488-499, September 09-12, 2003, Berlin, Germany
	Vagelis Hristidis , Yannis Papakonstantinou, Discover: keyword search in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.670-681, August 20-23, 2002, Hong Kong, China
	Antara Ghosh , Jignashu Parikh , Vibhuti S. Sengar , Jayant R. Haritsa, Plan selection based on query clustering, Proceedings of the 28th international conference on Very Large Data Bases, p.179-190, August 20-23, 2002, Hong Kong, China
	Anastasios Kementsietsidis , Frank Neven , Dieter Van de Craen, BioScout: a life-science query monitoring system, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Weifa Liang , Maria E. Orlowska , Jeffrey X. Yu, Optimizing multiple dimensional queries simultaneously in multidimensional databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.319-338, February 2000
	Manish Mehta , David J. DeWitt, Data placement in shared-nothing parallel database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.1, p.53-72, February 1997
	Amol Deshpande , Zachary Ives , Vijayshankar Raman, Adaptive query processing, Foundations and Trends in Databases, v.1 n.1, p.1-140, January 2007
	Damianos Chatziantoniou , Kenneth A. Ross, Groupwise Processing of Relational Queries, Proceedings of the 23rd International Conference on Very Large Data Bases, p.476-485, August 25-29, 1997
	Anant Jhingran, A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures, Proceedings of the 14th International Conference on Very Large Data Bases, p.88-99, August 29-September 01, 1988
	Dimitri Theodoratos , Timos K. Sellis, Data Warehouse Configuration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.126-135, August 25-29, 1997
	Minos N. Garofalakis , Yannis E. Ioannidis , Banu Özden, Resource Scheduling for Composite Multimedia Objects, Proceedings of the 24rd International Conference on Very Large Data Bases, p.74-85, August 24-27, 1998
	Alfons Kemper , Guido Moerkotte , Klaus Peithner, A Blackboard Architecture for Query Optimization in Object Bases, Proceedings of the 19th International Conference on Very Large Data Bases, p.543-554, August 24-27, 1993
	Daniela Florescu , Alon Y. Levy , Dan Suciu , Khaled Yagoub, Optimization of Run-time Management of Data Intensive Web-sites, Proceedings of the 25th International Conference on Very Large Data Bases, p.627-638, September 07-10, 1999
	Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
	Harald Kosch , Ahmed Mostefaoui , László Böszörményi , Lionel Brunie, Heuristics for Optimizing Multi-Clip Queries in Video Databases, Multimedia Tools and Applications, v.22 n.3, p.235-262, March 2004
	Anastasios Kementsietsidis , Frank Neven , Dieter Van de Craen , Stijn Vansummeren, Scalable multi-query optimization for exploratory queries over federated scientific databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Liang Zhu , Weiyi Meng , Wenzhu Yang , Chunnian Liu, Region clustering based evaluation of multiple top-N selection queries, Data & Knowledge Engineering, v.64 n.2, p.439-461, February, 2008
	Marko Vrhovnik , Holger Schwarz , Oliver Suhre , Bernhard Mitschang , Volker Markl , Albert Maier , Tobias Kraft, An approach to optimize data processing in business processes, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Mohamed A. Sharaf , Panos K. Chrysanthis , Alexandros Labrinidis , Kirk Pruhs, Algorithms and metrics for processing multiple heterogeneous continuous queries, ACM Transactions on Database Systems (TODS), v.33 n.1, p.1-44, March 2008
	Ryan Johnson , Stavros Harizopoulos , Nikos Hardavellas , Kivanc Sabirli , Ippokratis Pandis , Anastasia Ailamaki , Naju G. Mancheril , Babak Falsafi, To share or not to share?, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Mert Akdere , Uǧur Çetintemel , Nesime Tatbul, Plan-based complex event detection across distributed sources, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Jie Shao , Heng Tao Shen , Xiaofang Zhou, Challenges and techniques for effective and efficient similarity search in large video databases, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Gang Luo , Jeffrey F. Naughton , Curt J. Ellmann , Michael W. Watzke, Transaction reordering with application to synchronized scans, Proceeding of the ACM 11th international workshop on Data warehousing and OLAP, October 30-30, 2008, Napa Valley, California, USA
	Jürgen Krämer , Bernhard Seeger, Semantics and implementation of continuous sliding window queries over data streams, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-49, April 2009
	Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Multi-query optimization for sketch-based estimation, Information Systems, v.34 n.2, p.209-230, April, 2009
	Christian Blum , Maria J. Blesa , Manuel López-Ibáñez, Beam search for the longest common subsequence problem, Computers and Operations Research, v.36 n.12, p.3178-3186, December, 2009
	Li Weng , Umit Catalyurek , Tahsin Kurc , Gagan Agrawal , Joel Saltz, Optimizing multiple queries on scientific datasets with partial replicas, Proceedings of the 8th IEEE/ACM International Conference on Grid Computing, p.259-266, September 19-21, 2007
	Mingsheng Hong , Mirek Riedewald , Christoph Koch , Johannes Gehrke , Alan Demers, Rule-based multi-query optimization, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Danzhou Liu , Kien A. Hua , Ning Yu, Efficiently support concurrent queries in multiuser CBIR systems, Multimedia Tools and Applications, v.42 n.3, p.273-293, May 2009
	Umeshwar Dayal , Malu Castellanos , Alkis Simitsis , Kevin Wilkinson, Data integration flows for business intelligence, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Alkis Simitsis , Kevin Wilkinson , Malu Castellanos , Umeshwar Dayal, QoX-driven ETL design: reducing the cost of ETL consulting engagements, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Hendrik Blockeel , Luc Dehaspe , Bart Demoen , Gerda Janssens , Jan Ramon , Henk Vandecasteele, Improving the efficiency of inductive logic programming through the use of query packs, Journal of Artificial Intelligence Research, v.16 n.1, p.135-166, January 2002
	Yoram Moses , Moshe Tennenholtz, Off-line reasoning for on-line efficiency, Proceedings of the 13th international joint conference on Artifical intelligence, p.490-495, August 28-September 03, 1993, Chambery, France
	José Luis Ambite , Craig A. Knoblock, Planning by rewriting, Journal of Artificial Intelligence Research, v.15 n.1, p.207-261, July 2001

INDEX TERMS

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

General Terms:
Algorithms, Performance

REVIEW

"Edward Sava-Segal : Reviewer"

Given a set of queries that are supposed to share some tasks, a considerable reduction of execution time may be achieved by avoiding redundant page access. Sharing common temporary results among queries is cheaper than serial execution. This is more...

Collaborative Colleagues:

Timos K. Sellis: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player