Design and Implementation of a Semantic Query
Sreekumar T. Shenoy, Zehra Meral Ozsoyoglu · 1989
In this paper we describe a scheme to utilize semantic knowledge in optimizing a user specified query. The semantics is rep- resented as function-free clauses in predicate logic. The scheme uses a graph theoretic approach to identify redundant joins and restrictions present in a given query. An optimization algorithm is presented which eliminates redundant nonprofitable specifications from a query while adding additional profitable specifications to it. Dynamic and heuristic interaction of three entities-schema, semantics, and query-forms the basis of the algorithm. The implementation architecture of the algo- rithm and test results on a representative set of data are presented. Issues associated with updating of semantic constraints are addressed and an algorithm for semantic maintenance is introduced. Index Terms-Algorithms, graph theory, heuristics, implication in- tegrity constraints, query optimization, redundancy, relational data- bases, secondary index, semantic rules, subset integrity constraints.