1
$\begingroup$

I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking that using the predicate $ \neq $ would solve those problems but then I see the following:

p(X) :- r(X) & ¬q(X).

q(X) :- r(X) & ¬p(X).

The problem is this has 2 minimal models and if I'm not mistaken so does this:

p(X) :- r(X) & q(Y) & X $ \neq $ Y.

q(X) :- r(X) & p(Y) & X $ \neq $ Y.

Is there an equivalence between these 2 operators? If so, did I miss it or is it not mentioned that it's unsafe to use $ \neq $ with recursion?

$\endgroup$
  • $\begingroup$ Doesn't choosing $p,q$ to be the empty set satisfy the second clause set? I would expect that to be the least fixed point. $\endgroup$ – chi Jun 29 '17 at 8:36
  • $\begingroup$ I've answered your same q on lambda-the-ultimate. $\endgroup$ – AntC Jul 4 '17 at 12:04
1
$\begingroup$

There was a misunderstanding in regards to the evaluation algorithm/minimal model.

The derivation of new values is atomic e.g.:

step 1:

  • p = {}
  • q = {}

step 2:

  • p = r
  • q = r

In step 2 p and q only see the value that each other had at step 1(the old value). I thought p and q would have access to the value of the current step and thus, the order of evaluation would produce different results.

To answer the question:

p(X) :- r(X) & q(Y) & X ≠ Y.

q(X) :- r(X) & p(Y) & X ≠ Y.

only has one minimal model: p = r and q = r.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.