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

Date

1993-09-01

Author

Coşar, Ahmet
Lım, Ee Peng
Srıvastava, Jaıdeep

Metadata

Show full item record

Item Usage Stats

10
views

0
downloads

Cite This

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.

Subject Keywords

Algorithms, Data processing, Error analysis, Function evaluation, Graph theory, Heuristic methods

URI

http://dl.acm.org/citation.cfm?id=170181
https://hdl.handle.net/11511/82430

Collections

Graduate School of Natural and Applied Sciences, Conference / Seminar