Is Datalog negation(¬) similar to the built-in predicate (≠)?

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 ≠ would solve those problems.


bachelor(X) :- male(X) & ¬married(X,Y).

would become:

bachelor(X) :- male(X) & married(Y,Z) & X ≠ Y.

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 ≠ Y.
q(X) :- r(X) & p(Y) & X ≠ 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 ≠ with recursion?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Wild guess

Not knowing anything about Datalog I am pretty sure equality and non-equality are conservative extensions of some core logic. So = is likely interpreted as some shorthand for a binary predicate 'eq', and != the negation of 'eq'. [EDIT: removed capitals]

My guess is that it is simply assumed you understand that.

beware quantifiers

bachelor(X) :- male(X) & married(Y,Z) & X ≠ Y.

There's an implicit forall quantifier over those free vars. So one of your conjunctions amounts to

forall Y, Z. married(Y, Z)

which says: everybody is married to somebody.

Whether that's true or not has nothing to do with X being a bachelor. You could go:

bachelor(X) :- male(X) & (married(Y,Z) -> X ≠ Y). // equivalently
bachelor(X) :- male(X) & (¬married(Y,Z) \/ X ≠ Y).

That's not wrong, but it's unnecessary to testing whether X is married. It's like proving "all swans are white" by examining all the non-white objects and checking they're not swans.

The 'problem' with negation for datalog is that you really don't want to go hunting through all the non-bachelor people. Your query that's going to use the definition of Bachelor should at least be able to see it's a subset of male( )s.

I don't understand how your

I don't understand how your answer answers my question.

There's an implicit forall quantifier over those free vars.

Is this relevant considering the closed world assumption?

I understand (I think) the problem with datalog negation my question however is that the book seems to imply that safe rules will lead to a unique minimal fixed point. Yet, the rule for p/q with ≠ seem to produce 2 minimal fixed points(depending on the order that the rules are evaluated).

p = {} or r.
q = {} or r.

Safe rules as defined by the book are:

1. Any variable that appears as an argument in an ordinary predicate of the body is limited.

2. Any variable X that appears in a subgoal X = a or a = X, where a is a constant, is limited.

3. Variable X is limited if it appears in a subgoal X = Y or Y = X, where Y is a variable already known to be limited.

Does ≠ and recursion produce non-unique minimal fixed points?
Does ≠ by itself produce non-unique minimal fixed points?
Is ≠ equivalent to ¬ in expressive power?

There's a short reference

There's a short reference here.

Datalog: Query Language for Relational Databases
- Atomic Formula:
 (1) p(x1, ..., xn) where p is a relation name and
 x1, ..., xn are either constants or variables.
 (2) x <op> y where x and y are either constants or variables and <op> is
 one of the six comparison operators: <, , >=, =, !=
 Variables that appear only once in a rule can be replaced by
 anonymous variables (represented by underscores). NOTE: Every
 anonymous variable is different from all other variables.
- Datalog rule:
 p :- q1, ..., qn.
 where p is an atomic formula and
 q1, ..., qn are either atomic formula or
 negated atomic formula (i.e. atomic formula preceded by not)
 p is referred to as the head of the rule.
 q1, ..., qn are referred to as subgoals.
- Safe Datalog rule: A Datalog rule p :- q1, ..., qn. is safe
 (1) if every variable that occurs in a negated subgoal also
 appears in a positive subgoal and
 (2) if every variable that appears in the head of the rule also
 appears in the body of the rule.

You sure you got the right rules?