Introduction to Datalog(x775.net) |
Introduction to Datalog(x775.net) |
I haven't tried datascript, which appears to support negation. Maybe I will try that if/when I revisit this interest someday.
You can give http://www.dlvsystem.com/dlv/ a shot!
Alternatively, if you prefer open-source solutions, check https://abcdatalog.seas.harvard.edu/.
Due to a number of complications on my machine, I used DLV.
TY for the link to abcdatalog though!
p(X,Y) ← q(Y,X)
The interactive tutorials on http://www.learndatalogtoday.org (Datomic's dialect) quickly sold me on the idea.
Though coming from Datomic, I'm curious how much of my knowledge is Datomic-specific rather than how you'd generally approach a database queryable with Datalog. For example, do you need four indexes like Datomic (https://docs.datomic.com/on-prem/indexes.html) to make Datalog queries fast?
Datalog is fascinating, but the blog post makes me curious about more concrete impl-related follow-up questions.
For those interested in the mentioned paper, see: https://www.utdallas.edu/~gupta/courses/acl/papers/datalog-p...
Is it really the case?
Human("Socrates").
Animal("Turtle").
Mortal(x) :- Human(x).
Mortal(x) :- Animal(x).
Is it really valid according to Datalog semantics?
No, you and sdbrady who commented above are correct; the :- only means "if". I have edited accordingly and apologise for the misunderstanding!
In particular: https://www.youtube.com/watch?v=R2Aa4PivG0g
Edge("a", "b").
Edge("b", "c").
Path(x, y) :-
Edge(x, y).
Path(x, z) :-
Path(x, y),
Edge(y, z).
SymmetricEdge(Left, Right) :-
Edge(Left, Right).
SymmetricEdge(Left, Right) :-
Edge(Right, Left).It might be more accurate to say that Datalog programs cannot derive new atoms and this allows Datalog interpreters to use a search strategy which is guaranteed to terminate.
EDIT: Thinking about this more, I'm not sure why Prolog couldn't also use breadth-first search. So maybe both are necessary: Datalog not only disallows creating new atoms, but it also has a better search strategy; the combination of the two results in guaranteed termination.
P(f(x)).
p(f(f(x)).
p(f(f(f(x)))).
... etc
(but I might be wrong about this- corrections welcome).
The minimal model (result of derivation) is defined as the fixpoint of this operation. And the minimal model is finite because of the fixed number of atoms.
Every other evaluation strategy must be equivalent to this. Both in terms of termination and minimal model.
Prolog could use breadth first instead of SLD (and there are other Prolog evaluation strategies that, for example, use tabling for derived facts) but then you might get an infinite number of backtracking points instead of terms of infinite depth. You haven't really won anything by doing that.
p(X) :- p(X). does usually not terminate in a top-down (Prolog) system but does in a bottom-up (Datalog) system. Datalog doesn't even allow terms as predicate arguments so of course you can't construct them of infinite size. But also this isn't allowed (where it is in Prolog)
p(X) :- p(Y), X is Y + 1.
Given a fact p(0) you get p(X) true for any integer X or generate all positive integers. This doesn't terminate for some binding patterns.
is/2 is not Datalog though- it takes an arithmetic function as an argument; +/2 in your example. So the above would not terminate because it's Prolog, not because it's a Datalog program evaluated by Prolog.
>> Datalog doesn't even allow terms as predicate arguments so of course you can't construct them of infinite size.
Usual confusion: I think you mean "terms" as in Prolog terms, i.e. atoms of predicates (as opposed to terms in logic programming, i.e. variables, constants and functions). Datalog accepts constants and variables so with a finite vocabulary you can't create infinite atoms. I don't think that has to do with bottom-up or top-down evaluation.
To be honest, I haven't read any Datalog papers, but I'd be surprised if the termination guaranteed rested upon a specific implementation rather than the language semantics. Maybe not surprised- but it would be less interersting if you can only guarantee termination if you implement the language just so, vs. if it's a property of the language.
So the "biggest" model is only as large as any atom in any position for any predicate and that is always finite for a finite number of sorts or predicates.
Is gave is/2 as an example of how Prologo allows you to generate new atoms/terms that have not been facts before.