Datalog vs CLIPS vs Prolog

Question

As many programmers I studied Prolog in university, but only very little. I understand that Prolog and Datalog are closely related, but Datalog is simpler? Also, I believe that I read that Datalog does not depend on ordering of the logic clauses, but I am not sure why this is advantages. CLIPS is supposedly altogether different, but it is too subtle for me to understand. Can someone please to provide a general highlights of the languages over the other languages?

Solution 1

datalog is a subset of prolog. the subset which datalog carries has two things in mind:

1. adopt an API which would support rules and queries
2. make sure all queries terminate

prolog is Turing complete. datalog is not.

getting datalog out of the way, let's see how prolog compares with clips.

prolog's expertise is "problem solving" while clips is an "expert system". if i understand correctly, "problem solving" involves expertise using code and data. "expert systems" mostly use data structures to express expertise. see http://en.wikipedia.org/wiki/Expert_system#Comparison_to_problem-solving_systems

another way to look at it is:

expert systems operate on the premise that most (if not all) outcomes are known. all of these outcomes are compiled into data and then is fed into an expert system. give the expert system a scenario, the expert system computes the outcome from the compiled data, aka knowledge base. it's always a "an even number plus an even number is always even" kind of thinking.

problem solving systems have an incomplete view of the problem. so one starts out with modeling data and behavior, which would comprise the knowledge base (this gives justice to the term "corner case") and ends up with "if we add two to six, we end up with eight. is eight divisible by two? then it is even"

Solution 2

The difference between CLIPS and Prolog/Datalog is that CLIPS is a "production rule system" that operates by forward chaining: given a set of facts and rules, it will try to make every possible derivation of new facts and store those in memory. A query is then answered by checking whether it matches something in the fact store. So, in CLIPS, if you have (pseudo-syntax):

parent(X,Y) => child(Y,X)
parent(john,mary)

it will immediately derive child(mary,john) and remember that fact. This can be very fast, but puts restrictions on the possible ruleset and takes up memory.

Prolog and Datalog operate by backward chaining, meaning that a query (predicate call) is answered by trying to prove the query, i.e. running the Prolog/Datalog program. Prolog is a Turing complete programming language, so any algorithm can be implemented in it.

Datalog is a non-Turing complete subset of Prolog that does not allow, e.g., negation. Its main advantage is that every Datalog program terminates (no infinite loops). This makes it useful for so-called "deductive databases," i.e. databases with rules in addition to facts.

Comments

[David Tonhofer]

In particular, Datalog is for "querying relational databases" and is equivalent to recursive SQL. See this presentation. The Datomic database supports Datalog queries.

[David Tonhofer]

Relative to Prolog, Datalog has no function symbols (and thus no tree-oriented structures to work with, just constants and variables) and is purely declarative (no cuts, and no varying behaviour by rearranging clauses).

[David Tonhofer]

For CLIPS (a production system with an OPS5 ancestry), the idea is to "deduce" new facts (or fire actions) whenever a match with existing facts in the fact database occurs, and the fact database can change during computation. This is "hacky/scruffy" and weak theory-wise. For Prolog, the philosophy is "proving" a theorem from known implications and facts in the database which is not supposed to change! This is based on sound theory (first-order logic based on Horn clauses), which can be weakened at will by pulling in "non-logic" elements of the language (similar to adding GOTOs to nice code).

[David Tonhofer]

...and finally, you can implement the forward-chainer in Prolog.

[seanmcl]

Unlike for Prolog, nothing in the semantics of datalog specifies backward chaining. Both forward and backward chaining can be and are used.

[Anderson Green]

@seanmcl Forward chaining is also possible in Prolog using constraint handling rules.

[TomR]

@DavidTonhofer are there any such implementations? Someone suggested me for CHR (Constraing Handling Rules) for forward-chaining inference with the Prolog grammar. I am reading, but I would be happy to know about other efforts as well.

[David Tonhofer]

@TomR I can't give you a deep answer here, as I haven't burrowed too deep. I once took a look at CHR and although they looked like a good generic model of computation (in particular something to bring up in the classroom) they felt too basic for real work (maybe I'm mistaken). Pre-2000 efforts for adding production system functionality that I am aware of: Adding forward chaining and truth maintenance to Prolog (1989) ...

[David Tonhofer]

... Efficient Support for Reactive Rules in Prolog (1997). Today there is the Logic Production System by Kowalski and Sadri, which is very interesting as it has a logical interpretation for reactive rules: The underlying Prolog system computes a model making the reactive rules true, from there irreversible world-changing actions can be issued (that stuff needs a good textbook, I wanted to get into it last year but gave up for the moment)....

[David Tonhofer]

... There are maintained implementations, and papers. The KELPS part of LPS is a reduced core. Check this: Programming in logic without logic programming and Reactive Computing as Model Generation.