1 min read

Deductive Databases, COOL!

Everyone knows about the XML type databases that are out there right now. Sure they're cool. Everyone knows about the standby relational databases, which are also cool. But what if you had a relational database that can do deductions? How cool would that be? As it turns out, there have been these things, called deductive databases, for a long time. Research can be found on them back in the 80's, when the A.I. and Logic programming world was full of hope.

Unfortunately, it seems that logic programming in general has not caught on quite as well as some people might hope, and especially, declarative style languages haven't done quite as well in the general market either. However, declarative languages have really won out in Database Query languages. SQL is a declarative style language and the one I care about right now, called Datalog, is also declarative.

Datalog is a logic deductive database query language. It is a subset of Prolog that guarantees termination. That doesn't make it particularly nice for doing generalized programming, but it makes it especially nice when dealing with database queries.

Racket already has a Datalog library in PlaneT, and they have integrated it into their core system as well. I have ported this library, and am currently extending it in my own way, to be a ChezWEB program. Right now the comments are not there, but if you check out my repository, you'll find a running, workable datalog library in us.sacrideo.misc.

Here's an example of a recursive ancestor relationship that can be defined easily and succinctly based on the parent relationship, in Datalog:

(! (parent mom kid))
(! (parent dad kid))
(! (parent grandfather dad))
(! (parent grandmother dad))
(! (:- (ancestor ,x ,y) (parent ,x ,y)))
(! (:- (ancestor ,x ,y) (parent ,x ,z) (ancestor ,z ,y)))

Now we can query this and see who all the ancestors of KID are:

(? (ancestor ,x kid))

We'll get something like this for our output:

ancestor(grandfather, kid).
ancestor(grandmother, kid).
ancestor(dad, kid).
ancestor(mom, kid).

Now, tell me that's not super cool.