Semantic query processing in database systems
Sreekumar T. Shenoy, Zehra Meral Ozsoyoglu · OhioLink ETD Center (Ohio Library and Information Network) · 1990
In this thesis we describe a scheme to represent, utilize, and maintain semantic knowledge in optimizing user specified queries. The semantics is represented as function-free clauses in predicate logic. Knowledge is formulated as semantic constraints pertaining to the database, and is assumed to be satisfied by all the instances of the database. We use three distinct types of semantic constraints, namely, implication constraints, subset constraints, and aggregate constraints. The proposed scheme uses a graph theoretic approach to identify redundant joins and restrictions present in a given query. An optimization algorithm is presented which eliminates semantically redundant non-profitable specifications from a query while adding redundant profitable specifications to it. The optimization algorithm is guided by a set of heuristics and utilizes dynamic interaction of three entities--schema, semantics, and query--for semantic query transformation. Various sequential stages of the algorithm are described that deal with semantic expansion, relation elimination, restriction elimination etc. The complexity of the algorithm and cost reduction of semantic optimization are analyzed in detail. The implementation architecture of the algorithm and test results on a representative set of data are presented. Details on all the associated user interfaces are described. The test results reveal the potential advantages of a semantic optimizer in conjunction with a conventional one. Many potential inconsistencies possible with a growing set of semantic constraints are identified. Maintenance issues associated with different types of constraints are addressed. Algorithms for semantic maintenance regarding redundancy and contradiction are introduced for subset, implication, and aggregate constraints.