Questions about a Clojure Datalog

[smanek]

Hello all,

I'm a Common Lisp programmer who has just started learning Clojure. I
saw it mentioned online that several members of the existing community
were looking for someone to build a datalog for Clojure: I was
wondering what exactly you had in mind?

Were you thinking of a faithful implementation of the original Datalog
rule/query language? Or, if not, what features would you like this
datalog to have that aren't present in, say, the toy implementation of
Prolog that Norvig defines in PAIP? (See chapter11, if you have a copy
handy). Or, more to the point, what did you see this datalog being
used for?

It seems like this could potentially be a fun little non-trivial
problem to get started with Clojure in.

[Rich Hickey]

On Jan 26, 11:44 pm, smanek <sma...@gmail.com> wrote:
> Hello all,
>
> I'm a Common Lisp programmer who has just started learning Clojure. I
> saw it mentioned online that several members of the existing community
> were looking for someone to build a datalog for Clojure: I was
> wondering what exactly you had in mind?
>
> Were you thinking of a faithful implementation of the original Datalog
> rule/query language?

Yes, plus stratified negation at least.

> Or, if not, what features would you like this
> datalog to have that aren't present in, say, the toy implementation of
> Prolog that Norvig defines in PAIP? (See chapter11, if you have a copy
> handy).

I'd like it to be Datalog, and not Prolog, as I'd prefer the stronger
guarantees of Datalog. In particular, I like the fact that clause
order does not matter, queries will complete, the distinction between
intensional and extensional etc.

> Or, more to the point, what did you see this datalog being
> used for?
>

As a declarative query/rule language for in-memory use (although
mapping datalog queries to SQL is also possible).

> It seems like this could potentially be a fun little non-trivial
> problem to get started with Clojure in.

I think so. There are two ways to go depending on one's interests.

One would be a from-scratch Clojure implementation. The other would be
a Clojure wrapper for IRIS Reasoner:

http://iris-reasoner.org/

Unfortunately I haven't had time to pursue either of these beyond some
initial exploration, but I think a simple declarative rule engine
would be a terrific addition to Clojure.

Rich

[Jeffrey Straszheim]

Doing something like Datalog would be terrific fun. I might
contribute if there is interest.

I'm not an academic, so most of my contributions would be on a
practical level. We'd need someone else to provide the deeper aspects
of theory.

I've read Norvig's book, and understand his code, and my database book
(Mollina, Ullman, and Wisdom's) has a chapter on Datalog.

On Jan 29, 8:34 am, Rich Hickey <richhic...@gmail.com> wrote:
> On Jan 26, 11:44 pm, smanek <sma...@gmail.com> wrote:
>
> > Hello all,
>
> > I'm a Common Lisp programmer who has just started learning Clojure. I
> > saw it mentioned online that several members of the existing community

> > were looking for someone to build adatalogfor Clojure: I was

> > wondering what exactly you had in mind?
>
> > Were you thinking of a faithful implementation of the originalDatalog
> > rule/query language?
>
> Yes, plus stratified negation at least.
>
> > Or, if not, what features would you like this

> >datalogto have that aren't present in, say, the toy implementation of

> > Prolog that Norvig defines in PAIP? (See chapter11, if you have a copy
> > handy).
>

> I'd like it to beDatalog, and not Prolog, as I'd prefer the stronger
> guarantees ofDatalog. In particular, I like the fact that clause

> order does not matter, queries will complete, the distinction between
> intensional and extensional etc.
>
> > Or, more to the point, what did you see thisdatalogbeing
> > used for?
>
> As a declarative query/rule language for in-memory use (although

> mappingdatalogqueries to SQL is also possible).

[Jeffrey Straszheim]

Iris looks really good. They seem to have put a lot of work into
multiple, efficient evaluation strategies, and various levels of
expressivity versus safety. That kind of work is priceless.

However, I'm not sure if you can built your own predicates in Java
code (and therefore in Clojure code). That seems like a feature we'd
want. I've sent an email to their support folks to find out if this
is possible.

On Jan 29, 8:34 am, Rich Hickey <richhic...@gmail.com> wrote:

[Jeffrey Straszheim]

I've been doing some more research on this. This article seems a good
introduction:

http://www.dcc.uchile.cl/~cgutierr/cursos/FDB/p16-bancilhon.pdf

It turns out the naive implementation (a bottom-up fixed point
iterator) is pretty easy to understand, and would not be hard to
implement -- minus some hairy graph algorithms to get the stratified
negation stuff right, and some other optimizations. In fact, it is an
almost-freaking-perfect example of something that can run on map/
reduce. I *expect* that a lot of the implementation you find of this
stuff will be very good single threaded versions with focus on
minimising disk activity, which is not what we want.

There is a lot of parallelism to be exploited here. This is a good
target for Clojure, I believe.

[Timothy Pratley]

Hi Jeffrey,

On Feb 1, 4:50 am, Jeffrey Straszheim <straszheimjeff...@gmail.com>
wrote:

> However, I'm not sure if you can built your own predicates in Java
> code (and therefore in Clojure code).  That seems like a feature we'd
> want.  I've sent an email to their support folks to find out if this
> is possible.

I gave it a crack. It is definitely possible (perhaps even easy if you
are familiar with the nomenclature). Setting up the primitive support
is trivial, but combining the parts sent me into a spin - enter a DSL
which seems the logical aim (is this indeed the intention?)...

http://github.com/timothypratley/strive/blob/80a3e41af4c8d882c0330ff1ae42bc7916c5cbf9/src/clj/iris.clj

Here is where I got to so far... does the cheats method (parse) to
demonstrate simple facts/rules/query, then exposes the underlying
primitives that could be used to build the same expression without
parsing. Then I got somewhat lost and figured I'd call it a night :)

I couldn't find much info (any?) at all on the web about Datalog or
how to use IRIS in general... it certainly seems interesting as a
solver, but in practical terms how can I take advantage of it? Ok I
can think of some classic solver type problems (which are indeed
practical), but I get the impression Datalog is slated for greater
things, ie: general data modeling?


Regards,
Tim

[Timothy Pratley]

Just thought I'd share this link:
http://www.murat-knecht.de/schuerfen/irisdoc/html-single/index.html
Particularly Examples 1.2 and 1.6 show how the parts fit together.
I really wish I saw that before attempting anything :) Well now I know
for next time.

[Jeffrey Straszheim]

It would have been nice if that link was prominent on their website.

They still haven't responded to the email I sent them.

[Jeffrey Straszheim]

Datalog is a cool problem.

I've started writing some code. The rule-unification part of the
algorithm is trivial -- its not even proper unification at all. The
hard part seems to be optimising the query strategy to avoid
materialising too much. The advantage is you can support rules that
would make Prolog barf:

ancestor(X,Y) - parent(X,Y)
ancestor(X,Z) - ancestor(X,Y), ancestor(Y,Z).

I'm pretty sure that is infinite recursion in Prolog land (correct me
if I'm wrong), but works find in Datalog.

Anyhow, my progress will be here: http://code.google.com/p/clojure-datalog/

I'll say more when I have more to show.

[hoeck]

Hi,

On Feb 2, 3:42 pm, Timothy Pratley <timothyprat...@gmail.com> wrote:
> Hi Jeffrey,
>
> On Feb 1, 4:50 am, Jeffrey Straszheim <straszheimjeff...@gmail.com>
> wrote:
>
> > However, I'm not sure if you can built your own predicates in Java
> > code (and therefore in Clojure code). That seems like a feature we'd
> > want. I've sent an email to their support folks to find out if this
> > is possible.
>
> I gave it a crack. It is definitely possible (perhaps even easy if you
> are familiar with the nomenclature). Setting up the primitive support
> is trivial, but combining the parts sent me into a spin - enter a DSL
> which seems the logical aim (is this indeed the intention?)...
>

> http://github.com/timothypratley/strive/blob/80a3e41af4c8d882c0330ff1...

>
> Here is where I got to so far... does the cheats method (parse) to
> demonstrate simple facts/rules/query, then exposes the underlying
> primitives that could be used to build the same expression without
> parsing. Then I got somewhat lost and figured I'd call it a night :)

Did the same thing some time ago. Iris has good (at least good enough)
API docs in pdf and javadoc form. Inspired by the Allegro CL Prolog
syntax i set up a little DSL for writing datalog programs and
providing relations from clojure-sets and sql-queries. Unfortunately
the whole package is currently broken while I'm completing the
surrounding relational algebra library.
But maybe someone wants to look at the code:

http://github.com/hoeck/ra/blob/a018f2347fb409e7adc438f9c8b74fe8fecc57e9/hoeck/rel/iris.clj

the simpsons example would then look like:
(clear-universe)
(<- (man '#{homer}))
(<- (woman '#{marge}))
(<- (hasSon '#{[homer bart]}))
(<- (isMale ?x) (man ?x))
(<- (isFemale ?x) (woman ?x))
(<- (isMale ?y) (hasSon ?x ?y))

(?- (isMale ?x))

I hope to get it running again soon.

> I couldn't find much info (any?) at all on the web about Datalog or
> how to use IRIS in general... it certainly seems interesting as a
> solver, but in practical terms how can I take advantage of it? Ok I
> can think of some classic solver type problems (which are indeed
> practical), but I get the impression Datalog is slated for greater
> things, ie: general data modeling?

Iris is hosted at the Semantic Technology Institute (STI) Innsbruck,
reading through their research projects page leads to a new iris page,
describing its goal as:
"It is the mission of the IRIS research unit to define languages for
describing data and Web services, and to build software components to
reason about these data and service descriptions in order to make the
vision of the Semantic Web a reality." (http://iris.sti-innsbruck.at)

So you're probably right about it being for greater things.

erik

[Jeffrey Straszheim]

Erik,

Did you use a bottom up evaluation strategy? What top level
optimizations did you use (e.g. magic sets and so on)?

> http://github.com/hoeck/ra/blob/a018f2347fb409e7adc438f9c8b74fe8fecc5...

[hoeck]

hi jeffrey,

On Feb 3, 2:50 pm, Jeffrey Straszheim <straszheimjeff...@gmail.com>
wrote:

> Erik,
>
> Did you use a bottom up evaluation strategy?  What top level
> optimizations did you use (e.g. magic sets and so on)?

I only wrote a clojure-wrapper for the iris-reasoner (www.iris-
reasoner.org) mentioned above.
One thing i added is the possiblity to add clojure-sets as named
relations to a iris datalog program.
All the evaluation is done by iris. The wrapper is part of a larger
library dealing with lazy relational operators and sets.

erik

[Jeffrey Straszheim]

I see. Iris does look pretty good, but I think I'm going to give
writing this in Clojure a try -- the worst outcome is I waste some
time and learn a lot about logic programming. I think Clojure's
superior handling of state and concurrency will pay off here.

[Timothy Pratley]

> providing relations from clojure-sets and sql-queries.

Wow - this is really neat Erik - thanks for showing

[John Fries]

AFAICT, Datalog only supports the closed-world assumption. Does
anyone prefer an open-world assumption reasoner? In my opinion, they
are significantly more powerful.

[Jeffrey Straszheim]

Well, Datalog does give you guaranteed termination, so there is that,
although its bottom-up strategy is A LOT harder to implement (I'm now
trolling trough about a billion journal articles on "magic sets" and
so on to try to fix this).

I expect to provide full-on evaluable predicates, which I believe are
outside of the original Datalog scope, but I will still require the
"safe query" rules for those.

[John Fries]

Guaranteed-termination is very desirable.  However, you can have guaranteed termination with an open-world assumption just as well.  And I think an open-world assumption does a better job of mimicking human reasoning.

[Rich Hickey]

On Feb 4, 5:22 pm, John Fries <john.a.fr...@gmail.com> wrote:
> Guaranteed-termination is very desirable. However, you can have guaranteed
> termination with an open-world assumption just as well. And I think an
> open-world assumption does a better job of mimicking human reasoning.
>

Do you have a specific reasoner/algorithm in mind?

Rich

[John Fries]

Yes.  I can make a strong endorsement for Kodkod, a Java-based relational model finder.
http://alloy.mit.edu/kodkod/
I used it fairly extensively last year to solve scheduling problems, and I've corresponded with its creator.

One problem with Datalog-style reasoners is that, because they want to guarantee a certain execution time, they give up much of the expressiveness of relational logic.  Instead, Kodkod provides the correct interface to relational logic, and relies on an underlying SAT solver (such as MiniSat) to solve the problems in a reasonable amount of time.  This has proven to be a good approach, because SAT solvers have been improving at a tremendous rate over the last 10 years, and are now blazingly fast.

Another advantage of Kodkod over, say, FaCT++ or Pellet (which also provide open-world semantics) is that you are not tied into all the assumptions of the semantic web (OWL, RDF, XML, etc), which can get pretty clunky when all you want is an in-memory reasoner.  You only have to be reasonably comfortable with relational logic (e.g. "for all x: Red x") to be able to use Kodkod.

The only deficiency I found in Kodkod was that, because the author wanted to support an audience whose primary language was Java, the user must express their queries using a Java class-based syntax.  But this seems like a perfect use of Clojure, which could provide a much more natural query syntax.

[Rich Hickey]

Thanks for the pointer to Kodkod - it looks very interesting.

I wonder if we aren't talking apples and oranges though. Datalog may
be a basic reasoner, but it's a simple recursive query language for
data. Can you even get all results out of a SAT solver or do they stop
when satisfiable?

It's for this query purpose that I envisioned primary use of Datalog,
although I can certainly see the utility of more powerful reasoners
too.

Rich

On Feb 5, 12:22 pm, John Fries <john.a.fr...@gmail.com> wrote:
> Yes. I can make a strong endorsement for Kodkod, a Java-based relational

> model finder.http://alloy.mit.edu/kodkod/

> I used it fairly extensively last year to solve scheduling problems, and
> I've corresponded with its creator.
>
> One problem with Datalog-style reasoners is that, because they want to
> guarantee a certain execution time, they give up much of the expressiveness
> of relational logic. Instead, Kodkod provides the correct interface to
> relational logic, and relies on an underlying SAT solver (such as MiniSat)
> to solve the problems in a reasonable amount of time. This has proven to be
> a good approach, because SAT solvers have been improving at a tremendous
> rate over the last 10 years, and are now blazingly fast.
>
> Another advantage of Kodkod over, say, FaCT++ or Pellet (which also provide
> open-world semantics) is that you are not tied into all the assumptions of
> the semantic web (OWL, RDF, XML, etc), which can get pretty clunky when all
> you want is an in-memory reasoner. You only have to be reasonably
> comfortable with relational logic (e.g. "for all x: Red x") to be able to
> use Kodkod.
>
> The only deficiency I found in Kodkod was that, because the author wanted to
> support an audience whose primary language was Java, the user must express
> their queries using a Java class-based syntax. But this seems like a
> perfect use of Clojure, which could provide a much more natural query
> syntax.
>

[Jeffrey Straszheim]

There is no reason to have just one option.

[John Fries]

I agree with Jeffrey that there is no reason to have just one option.  Sometimes you want your reasoner to find a single model; sometimes you want it to find all models (assuming you are reasoning over a finite set).

I've appended a long rant about SAT-based reasoners and open-world semantics.  I hope it is relevant, and apologize for the length.

-John

Initially, I had a lot of trouble understanding why the concept of satisfiability was relevant to reasoning.  I just wanted to know whether or not a sentence was true; whether or not it was satisfiable didn't seem relevant.  Here's how you *could* use a SAT solver to answer a practical question (later I will explain why you would want to):

Let's say you have a list of sentences A:
A = ((man socrates) (for all X: man X -> mortal X)). 
A is your database of previous assertions.  Now let's say that you want to determine the truth state of a new sentence B:
B = (mortal socrates)
In other words, you want to know whether or not B is true, given all your previous assertions A.

So you form two new sentences, Y & Z:
X = (A and B) = ((man socrates) and (for all X: man X -> mortal X) and (mortal socrates))
Y = (A and (not B)) = ((man socrates) and (for all X: man X -> mortal X) and (not (mortal socrates)))

You then plug X into your SAT solver, and plug Y into your SAT solver.
If X is satisfiable and Y is satisfiable, then we say that B's truthstate, relative to A, is UNKNOWN.
If X is satisfiable and Y is unsatisfiable, then we say that B's truthstate, relative to A, is TRUE.
If X is unsatisifiable and Y is satisfiable, then we say that B's truthstate, relative to A, is FALSE.
If X is unsatisfiable and Y is unsatisfiable, then we say that B's truthstate, relative to A, is CONTRADICTION.

In this example, I'm pretending we have a first-order logic SAT solver (i.e. we can quantify, and our predicates take arguments), whereas usually we only have a boolean logic SAT solver, but the former can be easily built upon the latter (although it would be more efficient to build a first-order SAT solver).  Also, the actual implementation can be much more optimized than this; there is usually overlapping work done during the evaluation of X and Y.

This example only shows you how to evaluate (truthstate A B).  If you wanted to find a *model* (i.e. a list of tuples of things that satisfy some sentence), then you would say something like "get X: red X" (i.e. get me all X's that you can prove are red).  In a system with finitely many things, the vanilla unoptimized reasoner simply loops through each thing in the system and asks for its truthstate:
for each X:
  if (truthstate A (red X)) == TRUE:
    add X to output

There can be situations where you would want, not just the things for which the predicate is TRUE, but also the things for which the predicate is UNKNOWN.  You can include that as a argument to your query.  Also, there is a separate mechanism for performing default reasoning (which I am eliding here because this is already a pretty long rant).

Why go through all this trouble to get open-world semantics?  Why not just use a close-world reasoner?  First, I think open-world semantics does a better job of mimicing human reasoning.  If humans don't know that a sentence is true, they don't generally conclude that it's false.  Second, basing your reasoner on a SAT solver makes a lot of sense computationally.  SAT is a hard problem (NP-complete), but so much work has been done on it that in practice we can solve very large instances efficiently (and any SAT problem is solvable given enough time and memory).  The underlying SAT solvers seem to be improving at a tremendous rate, so a system that interfaces to them benefits from all that work.

-John

[John Fries]

reposted to correct a  mistake in my use of X, Y and Z:
---------------

I agree with Jeffrey that there is no reason to have just one option.  Sometimes you want your reasoner to find a single model; sometimes you want it to find all models (assuming you are reasoning over a finite set).

I've appended a long rant about SAT-based reasoners and open-world semantics.  I hope it is relevant, and apologize for the length.

-John

Initially, I had a lot of trouble understanding why the concept of satisfiability was relevant to reasoning.  I just wanted to know whether or not a sentence was true; whether or not it was satisfiable didn't seem relevant.  Here's how you *could* use a SAT solver to answer a practical question (later I will explain why you would want to):

Let's say you have a list of sentences A:
A = ((man socrates) (for all X: man X -> mortal X)). 
A is your database of previous assertions.  Now let's say that you want to determine the truth state of a new sentence B:
B = (mortal socrates)
In other words, you want to know whether or not B is true, given all your previous assertions A.

So you form two new sentences, Y & Z:

Y = (A and B) = ((man socrates) and (for all X: man X -> mortal X) and (mortal socrates))
Z = (A and (not B)) = ((man socrates) and (for all X: man X -> mortal X) and (not (mortal socrates)))

You then plug Y into your SAT solver, and also plug Z into your SAT solver.
If Y is satisfiable and Z is satisfiable, then we say that B's truthstate, relative to A, is UNKNOWN.
If Y is satisfiable and Z is unsatisfiable, then we say that B's truthstate, relative to A, is TRUE.
If Y is unsatisifiable and Z is satisfiable, then we say that B's truthstate, relative to A, is FALSE.
If Y is unsatisfiable and Z is unsatisfiable, then we say that B's truthstate, relative to A, is CONTRADICTION.

In this example, I'm pretending we have a first-order logic SAT solver (i.e. we can quantify, and our predicates take arguments), whereas usually we only have a boolean logic SAT solver, but the former can be easily built upon the latter (although it would be more efficient to build a first-order SAT solver).  Also, the actual implementation can be much more optimized than this; there is usually overlapping work done during the evaluation of X and Y.

This example only shows you how to evaluate (truthstate A B).  If you wanted to find a *model* (i.e. a list of tuples of things that satisfy some sentence), then you would say something like "get X: red X" (i.e. get me all X's that you can prove are red).  In a system with finitely many things, the vanilla unoptimized reasoner simply loops through each thing in the system and asks for its truthstate:
for each X:
  if (truthstate A (red X)) == TRUE:
    add X to output

There can be situations where you would want, not just the things for which the predicate is TRUE, but also the things for which the predicate is UNKNOWN.  You can include that as a argument to your query.  Also, there is a separate mechanism for performing default reasoning (which I am eliding here because this is already a pretty long rant).

Why go through all this trouble to get open-world semantics?  Why not just use a close-world reasoner?  First, I think open-world semantics does a better job of mimicing human reasoning.  If humans don't know that a sentence is true, they don't generally conclude that it's false.  Second, basing your reasoner on a SAT solver makes a lot of sense computationally.  SAT is a hard problem (NP-complete), but so much work has been done on it that in practice we can solve very large instances efficiently (and any SAT problem is solvable given enough time and memory).  The underlying SAT solvers seem to be improving at a tremendous rate, so a system that interfaces to them benefits from all that work.

-John

[Rich Hickey]

On Feb 7, 2:25 pm, John Fries <john.a.fr...@gmail.com> wrote:
> I agree with Jeffrey that there is no reason to have just one option.

I never suggested there ought to be only one option, nor am I trying
to argue against the utility of open-world reasoners. I merely asked,
given your assertion that open-world reasoners were more powerful than
Datalog, if they were therefor suitable for the tasks for which I
envisioned using Datalog, e.g. finding complete models, in a typical
data query manner. It seems from your description below that they
might not be, i.e. that it is supported but not efficient.

Rich

> straszheimjeff...@gmail.com> wrote:
> > There is no reason to have just one option.
>

[John Fries]

Sorry, I didn't mean to suggest that you held that opinion. 

In any case, I am still learning Clojure, so I think I should restrict myself to newbie questions until I am better at it.  I hope I will have time to implement an open-world reasoner, which would help make the discussion concrete.

[Jeffrey Straszheim]

I was considering extending my Datalog work with customized evaluable predicates, but have decided against it.  The safety guarantees of Datalog are just not worth giving up.  To compensate, I have (very tentative) plans of building some sort of logic oriented bottom up computation engine -- think Cells without state.  It would do fixed point work like Datalog, but with termination the programmer's problem.  Like Datalog, it would still be recursive (using fixed point), but it would focus on *computation* not queries.

I'll talk more about it when I get closer.

[Telman Yusupov]

Could this be of any help for your development? There is now a version
of Datalog for PLT Scheme:

Software:
http://planet.plt-scheme.org/display.ss?package=datalog.plt&owner=jaymccarthy

Documentation:
http://planet.plt-scheme.org/package-source/jaymccarthy/datalog.plt/1/0/planet-docs/datalog/index.html

[Jeffrey Straszheim]

It is worth looking at.

[Jeffrey Straszheim]

I see nothing in his code or documentation for handling negation or stratification.  Also, it appears to be a top down evaluator, and I don't see any fixed-point or other recursion handling.  I *suspect* this does not guarantee termination over arbitrary safe rules.  It is not real Datalog.

On Wed, Feb 18, 2009 at 12:42 PM, Telman Yusupov <use...@yusupov.com> wrote: