The generalized supplementary magic-sets transformation for stratified Datalog (Q685491)

One of the most promising algorithms for evaluating deductive databases expressed in Datalog (function-free Horn Logic) is to rewrite the original query and program by using a magic-sets transformation method and then to apply the semi-naive bottom-up evaluation strategy. These algorithms may also be applied to stratified Datalog, i.e. Datalog with stratified negation. But the magic-sets method in some cases does not produce a stratified Datalog program. The magic-sets method is extended to be even applicable to stratified Datalog without leaving the framework of stratified Datalog itself, i.e. neither other evaluation procedures nor other semantics are needed. The presented \(GSMS^{neg}\) transformation method is a very natural extension of the well known \(GSMS\) algorithm. It profits from the benefits of the \(GSMS\) transformations when the result is already stratified. The correctness of the algorithm is proven by referring to the completeness and soundness of the \(QSQR/SLS\) algorithm. The main idea is to correct the output of \(GSMS\) to be stratified. The first step is to rule out the negated subgoals. Obviously the computed relations may be different. Considering a rule with a negated subgoal, e.g. \(a(X,Y):-d(X,Y),\neg b(Y)\). The deletion of the negated subgoal \(\neg b(Y)\) generates a rule, which computes at least the same facts as the original rule. If the relation corresponding to \(b\) is empty, the same relation for \(a\) is calculated as if the original rule was used. But it may happen that the new rule computes some additional facts, e.g. if there are the facts \(d(a,b)\) and \(b(b)\), the original rule infers nothing, the modified rule instead computes the fact \(a(a,b)\). After applying these delations to the rules computing the magic-sets the relations corresponding to the magic predicates may contain some additional tuples, i.e. they restrict the set of answers only in a limited way. A parallel computation of magic and IDB predicates is in general no longer possible, since it could result in a wrong answer for a given query. Looking at the rule and the facts given above it is easily seen, that the answer for the query \(``?-a(X.Y).''\) consists of the empty set. Deleting the negated subgoal the incorrect answer is \(\{a(a,b)\}\). To evaluate the magic predicates so called positive predicates are introduced. The relations corresponding to these predicates contain all tuples being contained in the relation for the original predicate if there were no negated subgoals. A fact for an IDB predicate \(q\) is also contained in the relation for the corresponding positive predicate \(q-p\), but the latter may contain some additional tuples. Therefore the original rules have to be used to compute the relations for the IDB predicates, but they can be restricted to the set of facts, which have already been computed for the corresponding magic predicate of this IDB predicate. Furthermore it is shown that the efficiency of the evaluation depends on the EDB, but in almost all cases a \(GSMS^{neg}\) transformed program is superior to the original program when both are evaluated bottom-up.