Semantic query optimization in deductive databases. (volumes i and ii) (integrity constraints, intelligent processing, logic)

This thesis addresses the problem of efficient query evaluation over a deductive database and proposes several methods to optimize the evaluation of a query. The problems addressed in this thesis and the solutions proposed, under the central theme of query optimization can be discussed under- (i) Techniques for interfacing PROLOG with relational databases, (ii) A formalism for semantic query optimization using integrity constraints, and (iii) Multiple query evaluation in deductive databases. We propose several ways in which a PROLOG interpreter can be modified so that it can be interfaced effectively with a database system. Three solutions, namely, a simple modification to the PROLOG query evaluation strategy to accomplish the complied approach, a meta-level interpreter without any modifications to PROLOG and a set evaluation strategy using tables, are proposed in this thesis. A general framework in which domain specific knowledge--in the form of integrity constraints, is used to transform a query, is proposed in this thesis and is termed semantic query optimization. The process of semantic query optimization is carried out in two phases. Initially, the axioms of a database are semantically compiled, wherein, integrity constraints are integrated into the axioms in a suitable manner. Semantic compilation is performed only once prior to the submission of any query. Subsequently, the compiled axioms are utilized for query transformation at the time of query evaluation. The transformed query has restrictions imposed on it by the integrity constraints and hence it may be evaluated more efficiently over the database than the original query. Multiple queries arise in several contexts. In the case of deductive databases, a single query on an intensional predicate may result in several disjunctive queries which may have overlapping computations. We extend the connection graph decomposition algorithm to generate a single plan for a set of disjunctive queries. A multi-query graph is used as a non-procedural representation for a set of queries. The algorithm proposed in this thesis minimizes the number of accesses to the secondary storage where the relations are physically stored as well as the total number of joins.