Tradeoff in Rule Induction for Semantic Query Optimization

Research Papers

Semantic query optimization (SQO) is a promising approach to the optimization of increasingly complex query plans in global information systems. The idea of SQO is to use semantic rules about data to reformulate a query into an equivalent but less expensive one. Since it is difficult to encode required semantic rules, a complete SQO system also includes a rule induction system and a rule maintainer. To maximize the net utility of learning, a rule induction system needs to learn those rules that are effective in reducing the query execution cost while robust against data changes to minimize the rule maintenance cost. This paper focuses on this tradeoff between effectiveness and robustness in the rule induction for SQO. The solution is to explicitly estimate the degree of the robustness of rules. The system can use the estimated robustness to make decisions to guide rule construction, guide rule repair, and control the size of a rule set. This paper also briefly reviews how robustness can be efficiently estimated and reports the initial experimental results.