## 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.

E.g.

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

### 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

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 Syntax: - 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?