Semantic query optimization for bottom-up evaluation

Semantic query optimization uses semantic knowledge in databases (represented in the form of integrity constraints) to rewrite queries and logic programs to achieve efficient query evaluation. Much work has been done to develop various techniques for optimization. Most of it, however, is applicable to top-down query evaluation strategies. Moreover, little attention has been paid to the cost of the optimization. We address the issue of semantic query optimization for bottom-up query evaluation strategies with an emphasis on overall efficiency. We focus on a single optimization technique, join elimination. We discuss factors that influence the cost of semantic optimization, and present two different abstract algorithms for optimization. The first pre-processes a query statically before it is evaluated; the second combines query evaluation with semantic optimization using heuristics to achieve the largest possible savings.