SEMANTIC QUERY OPTIMIZATION FOR TREE AND CHAIN QUERIES

Semantic query optimization, or knowledge-based query optimization, ha s received increasing interest in recent years. This paper provides an effective and systematic approach to optimizing queries by appropriat ely choosing semantically equivalent transformations. Basically, there are two different types of transformations: transformations by elimin ating unnecessary joins, and transformations by adding/eliminating red undant beneficial/nonbeneficial selection operations (restrictions). A necessary and sufficient condition to eliminate a single unnecessary join is provided. We prove that it is NP-Complete to eliminate as many unnecessary joins as possible for various types of acyclic queries wi th the exception of the closure chain queries whose query graphs are c hains and all equi-join attributes are distinct. An algorithm is provi ded to minimize the number of joins in tree queries. This algorithm ha s an important property that, when applied to a closure chain query, i t will yield an optimal solution with the time complexity 0(n m), wh ere n is the number of relations referenced in the chain query, and m is the time complexity of a restriction closure computation. (A restri ction closure consists of all deducible restrictions of a query qualif ication under a given set of constraints. An algorithm to compute it w as given in [46]).