NoSQL Zone is brought to you in partnership with:

Joachim Hofer is a long-time senior consultant and lead developer on the Java platform who has recently become a fan of Scala. He regularly contributes to Open Source community projects and shares his experience in his blog and talks. Joachim is a DZone MVB and is not an employee of DZone and has posted 12 posts at DZone. You can read more from them at their website. View Full User Profile

Linked Lists in Datomic

08.21.2012
| 3252 views |
  • submit to reddit

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.

 

 

 

 

 

 

Published at DZone with permission of Joachim Hofer, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)