Title

Multiple Query Optimization with Depth-First Branch-and-Bound and Dynamic Query Ordering

Publication Type

Journal Article

Publication Date

1995

Abstract

In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., usually a single query gets transformed into a set of closely related database queries. Also, 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 (multi-plan) which can be executed to obtain the required outputs for all queries at once. In this paper a new heuristic function (hc), 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 hc, DFBB, and dynamic query ordering help to improve the performance of our MQO algorithm.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Management and Analytics

Publication

Journal of Database Management

Volume

6

Issue

1

First Page

14

Last Page

19

ISSN

1063-8016

Identifier

10.4018/jdm.1995010102

Publisher

IGI Global

Additional URL

http://dx.doi.org/10.4018/jdm.1995010102