As my last contact with Prolog was over ten years ago, I think it’s time for some fun with Datomic and Datalog. In order to learn to know Datomic better, I will attempt to implement linked lists as a Datomic data structure.

First, I need a database “schema”, which in Datomic means that I have to define a few attributes. I’ll define one :content/name (as a string) for naming my list items, and also the attributes for the list data structure itself, namely :linkedList/head and :linkedList/tail (both are refs):

[{:db/id #db/id[:db.part/db], 
  :db/ident :content/name, 
  :db/valueType :db.type/string, 
  :db/cardinality :db.cardinality/one, 
  :db/doc "Simple demo list content.", 
  :db.install/_attribute :db.part/db}
  
 {:db/id #db/id[:db.part/db], 
  :db/ident :linkedList/head, 
  :db/valueType :db.type/ref, 
  :db/cardinality :db.cardinality/one, 
  :db/doc "The head of a linked list.", 
  :db.install/_attribute :db.part/db}
  
 {:db/id #db/id[:db.part/db], 
  :db/ident :linkedList/tail, 
  :db/valueType :db.type/ref, 
  :db/cardinality :db.cardinality/one, 
  :db/doc "The tail of a linked list. Should point to a linked list.", 
  :db.install/_attribute :db.part/db}]

Next, I’ll create some sample data. I’ll define a simple list (A, B, C, D):

[{:db/id #db/id[:db.part/user -1], :content/name "A"}
 {:db/id #db/id[:db.part/user -2], :content/name "B"}
 {:db/id #db/id[:db.part/user -3], :content/name "C"}
 {:db/id #db/id[:db.part/user -4], :content/name "D"}

 {:db/id #db/id[:db.part/user -5], 
  :linkedList/head #db/id[:db.part/user -1], 
  :linkedList/tail #db/id[:db.part/user -6]}
  
 {:db/id #db/id[:db.part/user -6], 
  :linkedList/head #db/id[:db.part/user -2], 
  :linkedList/tail #db/id[:db.part/user -7]}
  
 {:db/id #db/id[:db.part/user -7], 
  :linkedList/head #db/id[:db.part/user -3], 
  :linkedList/tail #db/id[:db.part/user -8]}
  
 {:db/id #db/id[:db.part/user -8], 
  :linkedList/head #db/id[:db.part/user -4]}]

Now, for some queries. Let’s warm up a bit first.

Finding all contents (not by list):

[:find ?n :where [_ :content/name ?n]]

Finding the head of our list (knowing it starts with A):

[:find ?h :where [?h :linkedList/head ?c] [?c :content/name \"A\"]]

Next we need a rule that defines when two list items are linked. The first thing that comes to mind is that two items are linked when one is the head and the other is the (head of the) tail. So:

[[[linked ?h ?t] [?h :linkedList/tail ?t]]]

Now I can query for the list item linked to A, using this rule:

[:find ?n :in $ % :where 
  [?c :content/name ?n] 
  [?e :linkedList/head ?c] 
  [linked ?f ?e] 
  [?f :linkedList/head ?a] 
  [?a :content/name \"A\"]]

This will only return B, of course. To get the whole list, I’ll need a recursive rule. Now how does that work? - Let’s see:

[[[linked ?h ?t]
    [?h :linkedList/tail ?t]]
 [[linked ?h ?t] 
    [linked ?h ?x]
    [?x :linkedList/tail ?t]]]

So, I say that two list items are linked when they are directly linked, or when there is an intermediate list item that recursively is linked to one and directly linked to the other input item.

Now what happens when I run the query from before with the new rule(s)? - Hmmm, I get B, C and D, but am still missing the A itself.

How to include the A, too, so that I get the complete list contents? - I’ll have to again extend the rules. Two list items should also be viewed as linked when they are the same:

[[[linked ?h ?t]
    [?h :linkedList/head]
    [?t :linkedList/head]
    [(= ?h ?t)]]
 [[linked ?h ?t] 
    [linked ?h ?x]
    [?x :linkedList/tail ?t]]]

These rules view two items as linked when they both are list items (insofar as they have the :linkedList/head attribute), and they are equal. Or, as above, when the two items are linked via an intermediate item.

Finally, I get A, B, C and D as a result. Of course, if I query like this, I won’t get them ordered. If I need them ordered, I’ll have to simply query one after the other, iterating through the list ourselves…

So, that’s all for today’s finger exercises…

In my humble opinion, Datomic is the best kind of NoSQL database I ever happened upon. It’s visionary: I’d absolutely love to do away with mutability (like Datomic does) in all my current projects with database backends…

I’ve also started a little project to create an easy-to-use Scala API for Datomic. I’m not yet sure which direction this will take, however. See here.