Multiple query optimization with depth-first branch-and-bound and dynamic query ordering

Ahmet Cosar, Ee Peng Lim, Jaideep Srivastava

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., a single query can be transformed into a set of closely related database queries. Great benefits can be obtained by executing a group of related queries all together in a single unified multi-plan instead of executing each query separately. In order to achieve this, Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subexpressions, joins, etc.) among a set of query plans and creates a single unified plan (multiplan) which can be executed to obtain the required outputs for all queries at once. In this paper, a new heuristic function (fc), dynamic query ordering heuristics, and Depth-First Branch-and-Bound (DFBB) are defined and experimentally evaluated, and compared with existing methods which use A* and static query ordering. Our experiments show that all three of fc, DFBB, and dynamic query ordering help to improve the performance of our MQO algorithm.

Original languageEnglish (US)
Title of host publicationProc 2 Int Conf Inf Knowl Manage
PublisherPubl by ACM
Pages433-438
Number of pages6
ISBN (Print)0897916263, 9780897916264
DOIs
StatePublished - 1993
EventProceedings of the 2nd International Conference on Information and Knowledge Management - Washington, DC, USA
Duration: Nov 1 1993Nov 5 1993

Publication series

NameProc 2 Int Conf Inf Knowl Manage

Other

OtherProceedings of the 2nd International Conference on Information and Knowledge Management
CityWashington, DC, USA
Period11/1/9311/5/93

Fingerprint Dive into the research topics of 'Multiple query optimization with depth-first branch-and-bound and dynamic query ordering'. Together they form a unique fingerprint.

Cite this