Transitive relations in core.logic

Inspired by some recent blogs I’ve been playing with core.logic.

In our use RDF at work we have been developing on Jena, a Java library for processing and querying RDF triples. Overall, Jena is an excellent library and has powerful inference capabilities. While Clojure has great interop support for Java sometimes you find some mismatches between the two paradigms.

For example, Jena being a Java library supports concurrency via read/write locks rather than Clojure’s Software Transactional Memory. In practise this mismatch disrupts Clojure’s preference for lazy sequences – results have to be read in entirety to avoid concurrent modification errors. Jena’s concurrency model is also confusing to use, and we’ve had to fix a number of deadlocks in our code which have been hard to diagnose. Since we only use a small subset of OWL logical predicates in our dataset it may be possible to replace Jena with something that worked better with Clojure.

Both the RDFS and OWL inference engines in Jena work by extending the graph with additional links called ‘entailments’ which reflect the possible inferences that can be made, using both forward and backward chaining strategies. Creating an inference graph can be expensive and not something you want to do on every query. However, if your data model isn’t static you have to re-create the inference graph every time it changes. While there are inference engines that support such incremental updates efficiently, I was intrigued by core.logic to see if it was possible extending the data model and rather to put inferencing in the relations themselves.

Here’s an example. RDFS declares a subclass predicate which declares one class to be a subclass of another. Any instances of the subclass are, by inference, also instances of the superclass.

We can declare this relation in core.logic like so.

(defrel subclass-of p1 p2)

Here are some facts to illustrate the example.

(fact subclass-of "Royal Bengal Tiger" "Tiger")
(fact subclass-of "Tiger" "Cat")
(fact subclass-of "Cat" "Mammal")
(fact subclass-of "Mammal" "Animal")

Now we can get all the graph links with this query.

(run* [q]
      (fresh [a b]
             (subclass-of a b)
             (== q [a b])))

But rdfs:subclass-of is a owl:transitive. Never mind, we can transform the relation to act transitively. Here’s the transformer function :-

(defn transitive [r]
  (letfn [(t [p1 p2]
            (fresh [between]
                   (conde
                    ((r p1 p2))
                    ((r p1 between)
                     (t between p2)))))]
    t))

Now we can use it to get all the entailments as well.

;; This transforms the relation into a transitive relation
(run* [q]
      (fresh [a b]
             ((transitive subclass-of) a b)
             (== q [a b])))

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>