Display Full Text | Download Full Text
2.85 MB PDF file

Degree

Doctor of Philosophy, Case Western Reserve University, Computer Engineering, 1990.

Abstract

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 assoc iated user interfaces are described. The test results reveal the potential advantages of a semantic optimizer in conjunction with a conventional. 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.

Subject Headings

Computer Science

Keywords

Semantic query processing database systems

Advisor

Zehra Meral Oz Soyoglu

Pages

131p.

Document number: case1054585075
Permalink: http://rave.ohiolink.edu/etdc/view?acc_num=case1054585075

This ETD has been downloaded 325 times (through March 2013)