Over a million developers have joined DZone.

Linked Lists in Datomic

· Java Zone

Easily build powerful user management, authentication, and authorization into your web and mobile applications. Download this Forrester report on the new landscape of Customer Identity and Access Management, brought to you in partnership with Stormpath.

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.

 

 

 

 

 

 

The Java Zone is brought to you by Stormpath—a complete, pre-built User Management API. Want to learn how to use JWTs to protect microservices from CSRF and more? Check out this on-demand webinar with our Java Developer Evangelist, Micah Silverman.

Topics:

Published at DZone with permission of Joachim Hofer, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}