Relation Table data structure in Clojure

Question

I am looking for Clojure data structure, that works like relation table (as in relational databases).

Map (even biderectional) id -> (val1, val2, val3, ...) does not do the job. If I, for example, want to find all rows with val2 = "something" it will took O(n).

But I want to perform search in a column in O(log n)!

[This answer](http://stackoverflow.com/a/28808003/1562315) suggests you look at [DataScript](https://github.com/tonsky/datascript). By the way, a search for equality can be achieved in almost constant time by using a hash-table index (assuming that hits are rare). — Thumbnail, Apr 08 '16 at 22:54

score 1 · Answer 1 · answered Apr 09 '16 at 20:24

Searching for rows in database with a column predicate without an index is O(n) as every row has to be checked if it matches the predicate. If there is an index for a column that your predicate uses then the index can be used to find all the rows for a specific value by looking up that value as the key in the index to fetch all the matching rows. Then it is usually log(n) operation (it depends on the internal implementation of the index, e.g. for B-tree it is log(n)).

I am not aware of out-of-the-box implementation of a Clojure data structure having such characteristics as they have usually single-purpose (e.g. map is an associative datastructure for lookup by a single key, not multiple keys as in DB with multiple indexes). You would rather need a library providing some kind of an in-memory database, for example (as mentioned by Thumbnail in his comment) DataScript, or even in-memory SQL DB with JDBC interface (e.g. H2SQL, HSQLDB or DerbyDB using their in-memory stores).

I am not sure of your specific requirements, but you could also implement some of the features yourself using basic API from Clojure. For example, you could use a Clojure set as your "table" and enhance it with some functions from clojure.set:

Your table:

(def my-table #{{:id 1 :name "John" :age 30 :gender :male}
                {:id 2 :name "Jane" :age 25 :gender :female}
                {:id 3 :name "Joe"  :age 40 :gender :male}})

And specify your indices:

(def by-id (clojure.set/index my-table [:id]))
(def by-age (clojure.set/index my-table [:age]))
(def by-gender (clojure.set/index my-table [:gender]))

And then use your indices when querying/filtering your table:

(clojure.set/intersection
  (by-age {:age 30})
  (by-gender {:gender :male}))

;; => #{{:id 1, :name "John", :age 30, :gender :male}}

Relation Table data structure in Clojure

1 Answers1