Evaluation of Extended Recursive Queries in Deductive Databases
Sang Ho Lee, Lawrence J. Henschen · Database Systems for Advanced Applications · 1991
In order to extend the expressive power of deductive databases, there have been efforts to allow existential quantifiers in the IDB rule of Prenex Normal Form to occur. A formula which can have an existential quantifier in front in a restricted way is defined as an extended rule. With the extended rule, we ca.n easily define a virtual view which requires a division operation of relational algebra. Even though there have been numerous efforts to answer recursive queries, the formula under investigation so far is assumed to be free of existential quantifiers in the beginning so that no Skolem functions are allowed to occur in the formula. This paper addresses an extended recursive query evaluation where at least one formula in a recursive rule set is of an extended rule. We investigate reducible recursion as well as four cases of non-reducible recursion of transitive closure and linear recursion type. We have found that occurrences of existentially quantified variables in the extended recursive body predicate dramatically limit the level of recursive search. The number of iterations to answer extended recursive queries can be determined by the structure of the extended recursive rule set.