Home » forums » LtU Forum

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?

By Milton Silva at 2017-07-04 08:48 | LtU Forum | previous forum topic | next forum topic | other blogs | 3143 reads

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.

By marco at Tue, 2017-07-04 10:58 | login or register to post comments

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.

By AntC at Tue, 2017-07-04 11:58 | login or register to post comments

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?

By Milton Silva at Wed, 2017-07-05 08:52 | login or register to post comments

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?

By marco at Wed, 2017-07-05 12:01 | login or register to post comments