Accession Number : ADA323806

Title :   Subtree-Elimination Algorithms in Deductive Databases.

Descriptive Note : Doctoral thesis,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Saraiya, Yatin

PDF Url : ADA323806

Report Date : JAN 1991

Pagination or Media Count : 160

Abstract : A deductive database consists of a set of stored facts, and a set of logical rules (typically, recursive Horn clauses) that are used to manipulate these facts. A number of optimizations in such databases involve the transformation of sets of logical rules (programs) to simpler, more efficiently evaluable programs. We consider a class of optimizations in which the transformation is a simple syntactic restriction on the form of the original program, and in which the correctness of the transformation indicates the existence of a normal form for the proof trees generated by the program. For example, the existence of basis-linearizability in a nonlinear program indicates that the program is inherently linear, and permits the use of special-purpose query evaluators for linear recursions. The canonical example of a basis-linearizable program is the program that computes the transitive closure of a binary relation; the corresponding normal form for the proof trees is that of right-linearity. Similarly, if a program is sequencable, then it is conducive to a pipelined evaluation. In addition, the existence of k-boundedness in a program permits the elimination of recursion overhead in evaluating the program. We investigate the complexity of detecting such optimization opportunities, and provide correct (but not always complete) algorithms for this purpose. Each of the problems that are mentioned above may be described in terms of the subtree-elimination problem, which we define and analyze. We relate the detection of basis-linearizability, sequencability and 1-boundedness to the complexity classes NC, P and NP, and show that the first two of these problems are, in general, undecidable. The techniques used in our analysis provide a complete description of the complexity of deciding the equivalence of conjunctive queries (single-rule, non recursive programs).

Descriptors :   *DATA BASES, *ALGORITHMS, SOFTWARE ENGINEERING, OPTIMIZATION, DATA MANAGEMENT, COMPUTER LOGIC, SEMANTICS, THESES, RECURSIVE FUNCTIONS, SYSTEMS ANALYSIS, COMPUTER PROGRAM VERIFICATION, MAPPING(TRANSFORMATIONS), SYNTAX, NONLINEAR PROGRAMMING, CONTROL SEQUENCES, STRUCTURED PROGRAMMING, CONTEXT FREE GRAMMARS.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE