Constructive negation under the well-founded semantics

Constructive negation derives constraint answers for non-ground negative li terals. Its incorporation into query evaluation under the well-founded sema ntics introduces two problems. One is the detection of repeated subgoals an d the elimination of redundant answers, which is required in order to guara ntee termination. The other is the interaction between constraint answers o f non-ground negative literals and recursion through negation. This paper p resents SLG(CN) for effective query evaluation with constructive negation u nder the well-founded semantics. It has two unique features. First, it supp orts reduction of constraint answers and redundant answer elimination and p rovides the first termination result for goal-oriented query evaluation wit h constructive negation for function-free programs. Second, it avoids repea ted computation in a subgoal. Even if a non-ground negative literal depends upon some ground negative literals whose truth values are not completely d etermined when they are selected, the constraints and bindings for variable s in the non-ground negative literal can still be propagated once and for a ll. (C) 1999 Elsevier Science Inc. All rights reserved.