Structural query optimization—a uniform framework for semantic query optimization in deductive databases
Laks V. S. Lakshmanan, Héctor J. Hernández · 1991
this paper we propose the factoring technique as a general technique which can detect opportunities for making the recursion less "intensive". For example, this technique can detect that certain subgoals need only be examined a bounded number of times in certain subtrees of the proof trees of the query predicate. More precisely, given a program and a query predicate (the recursive predicate), the factoring technique can determine when it is possible to limit the number of occurrences of a subgoal in selected subtrees of the proof trees of the query predicate. We call this property of subgoals proof tree removability. Our technique can also exploit the knowledge about proof tree removability in transforming a program into an equivalent program such that the proof trees constructed using the transformed program always contain a limited number of occurrences of the subgoal in selected subtrees. Proof tree removability is thus a notion that generalizes the notion of "recursively redundant" introduced by Naughton [N1, N2] in the sense that a subgoal a need not be recursively redundant w.r.t. a predicate and yet its repeated occurrences in certain subtrees of the query predicate may well be redundant. (See Section 9 for examples.) Factoring is one type of proof tree transformation, (e.g. see [RSUV, Sar]), only that it is achieved at the level of rules. In principle it may be possible to start with Naughton and others' characterization of recursively redundant predicates and then try to generalize the conditions to a larger class of rules to capture the notion of "subtree redundancy of predicates" above. Such a generalization is not at all obvious and we find it convenient to start with simple syntactic criteria for predicates to be "factored" out of linear sirups and then ...