A formal model of trade-off between optimization and execution costs in semantic query optimization

Conventional query optimizers assume that the cost of optimization is negligible. This assumption does not hold for much larger search spaces (of possible execution plans) such as those encountered during semantic query optimization. In particular, the optimization cost can become comparable to the execution cost, and thus a significant fraction of the response time for interactive queries [1]. This paper discusses the trade-off between the two costs in the context of semantic query optimization with regard to a set of integrity constraints, and reports a heuristic search algorithm which minimizes a weighted sum of both the costs. A detailed analysis of an experiment is presented to strengthen the claim. The optimization considered in this paper is with respect to a set of semantic integrity constraints.