Semantic Query Optimization for Bottom-Up Evaluation
Abstract
Semantic query optimization uses semantic knowledge in databases
(represented in the form of integrity constraints) to rewrite queries and
logic programs for the purpose of more efficient query evaluation. Much
work has been done to develop various techniques for optimization. Most of
it, however, is only applicable to top-down query evaluation strategies.
Moreover, little attention has been paid to the cost of the optimization
itself. In this paper, we address the issue of semantic query optimization
for bottom-up query evaluation strategies with an emphasis on overall
efficiency. We restrict our attention to a single optimization technique,
join elimination. We discuss various factors that influence the cost of
semantic optimization, and present two abstract algorithms for different
optimization approaches. The first one pre-processes a query statically
before it is evaluated; the second approach combines query evaluation with
semantic optimization using heuristics to achieve the largest possible
savings.
(Also cross-referenced as UMIACS-TR-95-109)