.png){kind=icon}
.png){kind=icon}
Return
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
Abstract
En 中文
Semantic query optimization, or knowledge-based query optimization, has received increasing interest in recent years. This paper provides an effective and systematic approach to optimizing queries by appropriately choosing semantically equivalent transformations. Basically, there are two different types of transformations: transformations by eliminating unnecessary joins, and transformations by adding/eliminating redundant 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 with the exception of the closure chain queries whose query graphs are chains and all equi-join attributes are distinct. An algorithm is provided to minimize the number of joins in tree queries. This algorithm has an important property that, when applied to a closure chain query, it will yield an optimal solution with the time complexity 0(n * m), where n is the number of relations referenced in the chain query, and m is the time complexity of a restriction closure computation. (A restriction closure consists of all deducible restrictions of a query qualification under a given set of constraints. An algorithm to compute it was given in [46]).
Keywords:
CHAIN
COMPLEXITY
JOIN
NP-COMPLETE
QUERY TRANSFORMATION
RESTRICTION
SEMANTIC QUERY OPTIMIZATION
TREE
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W
Organization
No organization information available