Data all the Query: Composition and Abstraction of Datomic Queries

Introduction

Composition and abstraction are the downforce and acceleration of coding. Yet when dealing with databases these operations are usually unavailable due to the limitations of SQL as a DSL. Thus database code is invariably ugly: string manipulations or ORM. Datomic presents a radical change that allows queries to be composed and abstracted naturally, which it achieves through the idea of queries-as-data. In this post I hope to demonstrate the query-as-data idea and how it enables clean composition and abstraction.

We'll demonstrate this by building a small analysis around some US presidential election data. The code and data are available on Github at. Load up the core.clj file and go.

The Dataset

We'll work with tiny dataset of Electoral College Votes for US President by State and Year courtesy of the good peole of Infochimps.. This dataset shows by year and state how many Electoral College votes the state cast and whether they were for Team Red, Blue or Independent.

We need a database schema. Our entities are parties, states and votes. A vote has a year, a party, and a state. I'm discarding the number of college votes and just storing whether the state plumped for R, D or I (nobody understand the electoral college anyway!). The ingestion of the data file into the db is handled by ingest.clj. Its not especially interesting. The schema is ubersimple:

  [;; ------- States ---------
   {:db/id #db/id[:db.part/db]
    :db/ident :state/name
    :db/valueType :db.type/string
    :db/cardinality :db.cardinality/one
    :db/index true
    :db/unique :db.unique/value
    :db/doc "Name of a state"
    :db.install/_attribute :db.part/db}

   ;; ------- Party ----------
   {:db/id #db/id[:db.part/db]
    :db/ident :party/name
    :db/valueType :db.type/string
    :db/cardinality :db.cardinality/one
    :db/index true
    :db/unique :db.unique/value
    :db/doc "Political Party"
    :db.install/_attribute :db.part/db}

   ;; ------- Vote ----------
   {:db/id #db/id[:db.part/db]
    :db/ident :year
    :db/valueType :db.type/string
    :db/cardinality :db.cardinality/one
    :db/index true
    :db/unique :db.unique/value
    :db/doc "In which year was the vote"
    :db.install/_attribute :db.part/db}

   {:db/id #db/id[:db.part/db]
    :db/ident :party
    :db/valueType :db.type/ref
    :db/cardinality :db.cardinality/one
    :db/index true
    :db/unique :db.unique/value
    :db/doc "For which party"
    :db.install/_attribute :db.part/db}

   {:db/id #db/id[:db.part/db]
    :db/ident :state
    :db/valueType :db.type/ref
    :db/cardinality :db.cardinality/one
    :db/index true
    :db/unique :db.unique/value
    :db/doc "From which state"
    :db.install/_attribute :db.part/db}]

The Base Query

Now that the data is input we want to query it, which we handle in query.clj. The idea is create a base query which is returns the results of a big join of all the entities we care about: votes, states and parties.

So starting at the bottom, the join is expressed as a datomic rule.

(def vote-join
  '[[vote-join ?v ?y ?p ?s]
    [?v :year ?y]
    [?v :state ?s-id]
    [?v :party ?p-id]
    [?s-id :state/name ?s]
    [?p-id :party/name ?p]])

This is a list that expresses the join between the entities. The key thing here is that this is one element of a database query and I can pull it out and put a handle on it: I've abstracted the join. We'll return to this in a moment.

Next I have to put the join into a query:

(def base-query
  {:find   ['?v]
   :in     ['$ '%]
   :where  ['(vote-join ?v ?y ?p ?s)]})

This is a map, expressing a database query that returns all the votes from the vote-join. I've stitched the join into the query by using it as a rule in the query (thanks to @tgkristensen who showed me how)...

Finally, I want to call execute the query against the database:

(defn votes
  "Return all the votes from the db"
  [query]
  (q query (db @db/conn) [vote-join]))

I can now get all the votes in the database by calling

(votes base-query)

.

Composition

The base query is not especially, interesting. I want to be able to ask things about states and years. Now, because the query is expressed as a datastructure (the key point) I can use data manipulation functions to modify it. In this case be adding a constraint.

Lets start with years:

(defn year [y]
  [['?v :year y]])

This is a datomic rule, a little fragment that says the year attribute for the vote must have value v. To stitch it into query:

(defn constrain
  "Apply constraints to a query"
  [query constraints]
  (update-in query [:where] (partial apply concat) constraints))

This is the key magic function. I take an input query, and, because its a map, I just add a new assertion to the :where value using familiar update-in! That's pretty amazing.

So the query before constraining is base-query:

{:find [?v], :in [$ %], :where [(vote-join ?v ?y ?p ?s)]}

and after

(constrain base-query [(year "2000")])

{:find [?v], :in [$ %], :where ((vote-join ?v ?y ?p ?s) [?v :year "2000"])}

The output just a vector, so its a normal Clojure datastructure so I can

(count (votes (constrain base-query [(year "2000")])))

and have it return 51 (50 states and Washington DC).

Of course I can add more than one constraint identically. Here's the constraint fragment for states, by joining to the vote:

(defn state [s]
  [['?v :state '?s-id]
   ['?s-id :state/name s]])

and as you expect

(count (votes (constrain base-query [(state "Georgia") (year "2000")])))

returns 1!

As you can pass arbitrary functions into Datomic queries you can make rather powerful and useful constraints. Here the code to constrain the resuts to votes after a given year:

(defn >year* [y1 y2] (> (Integer. y1) (Integer. y2)))
(defn >year [y]
  [`[(dataquery.query/>year* ~(symbol '?y) ~y)]])

Its a little tricksy because I haven't quite figured out how to properly quote namespace qualified symbols. Anyway.

So that's how, by representing the queries as data structures Datomic allows you to compose queries in a really natural fashion.

Abstraction

Next up the food chain from composition is abstraction. Here I'll give a little example of how to abstract database queries to probabilistic queries. Say we want to answer questions like what is the probability of a west coast state voting Republican (say), this can be expressed mathematically as the conditional probability: P(Vote is Republican | State is West Coast). Datomic is a beautiful for this sort of work because it deals in "facts", where probability deals in "events", both are different domain jargon for the same thing! An impedence matching property, perhaps.

So lets raise the level of abstraction. To do probability queries we don't care what the actual votes are, just the counts. So lets create a function that returns the number of votes that meet a given constraint.

(def num-votes (comp count (partial votes base-query)))

That could have been achieved using the count aggregate function in Datomic itself as well.

(def count-query
  (assoc base-query :find ['(count ?v)]))
(def num-votes (comp ffirst (partial votes count-query)))

OK, now for the probability function, which is now trivial

(defn p
  ([J]    (p J []))
  ([J C] (/ (num-votes (concat J C))
             (num-votes C))))

Here we are returning P(J |C), the probability of event J given event C, which matches directely to the probability of the set of events matching constraint J given the set of events matching constraint C. We have just utilised the maths fact that P(J | C) = P(J,C) / P(C) = #{J,C}/N / #{C}/N = #{J,C}/#{C}, so we can just divide out the counts to get the probabilities.

So, what's the probability of a state voting independent ?

(p [(party "I")])

=> 2/187. Not so good. How about of Texas voting Democrat post 1980 ?

(p [(party "D")] [(state "Texas") (>year 1980)])

=> 0.

Probability Summary

In summary we can abstract up from database queries to probability queries very cleanly. This is due not only to a nice match between our database and our domain, but emerges from the ability of datomic to compose queries. I state my probability problem with a datastructure of functions:

[(state "Texas")  (>year 1980)]

etc, these are then composed into database queries. The probability "DSL" is thin and natural. All the query and probability code are 75 lines, with comments, formatting and the rest in the buffer.

Bits and bobs

One potential weakness in this scheme is that the logic variables used in the various query fragments have to match up. This is a leaky, and I don't especially like it, but I can't see a way around it right now. Suggestions ?

A cool trick is to memoize the votes function to prevent the query having to run every time. To get that right though you need to parameterised by the database value, which would make this code a bit messy for demo.

Summary

The advantages of Datomic are often hard to explain because its more than the sum of its parts, and the parts themselves are quite unfamiliar. I hope that this little example explains the idea of query-as-data and shows how it allows great composition of queries, and thus abstraction of the database layer up into the domain layer.