Fork me on GitHub

I'm modelling deep recursive trees. I want to support: 1) a node can be in multiple locations 2) a node can appear multiple times within a parent. I've been dealing with this by wrapping the node and storing a ref to it in subsequent locations. This introduces a surprising amount of hard-to-follow logic across the whole stack. So, I've been thinking about doing something like this instead:

[{:id 1 :data "node 1"
  ;; just a clojure map
  :parents {[2 0] {:location-specific-data "foo"}
            [2 2] {:location-specific-data "bar"}
            [3 0] {:location-specific-data "baz"}}}
 {:id 2 :children [1 3 1]} ;; 2)
 {:id 3 :data "node 3"
  :parents {2 {}} :children [1]}]
Requirement 2) forces :children to be cardinality/one (i.e. just a meaningless vector to DataScript) instead of cardinality/many with type/ref. So, I lose a lot of 'Datalog features' for that attribute. However, writing custom functions to find a node's location and find all nodes within a location seem simple enough. For queries where location is a factor ("find all nodes where :data is "node 1" inside location 2"), I guess I can always first manually find all nodes within a location then pass it in as query input. I'm looking for a sanity check before committing to this 🙂 Any potential problems come to mind?

Linus Ericsson10:05:37

If I understand the problem, the reference between a children and parent always goes both ways, right? I would suggest you model that relation one-way [children->parent or parent->children]and let datascript take care of keeping that reference correct. Regarding localities it's a slightly hard one - the built in hierarchy function in clojure just keeps indexes of everything (if i remember correctly), ie one node would keep a "cached" of all it's ancestors or descendants, if practical. This would require some custom logic for keeping the system correct in updates.

Linus Ericsson10:05:21

If a node could appear many times inside a parent - is this like a customer basket with 10 apples or is it 10 individueal apperances? In the first case - make a reference between children and parent (as a separate entity) which can carry data, for instance a scalar. In the second case, the solution is sort of the same, the relation between child and parent is richer than what just a datascript attribute can describe.

Linus Ericsson10:05:02

Example {:id 1 :name "child1"} {:id 2 :name "parent1"} {:id 3 :relation/child 1 :relation/parent 2 :appearances 7} Or {:id 1 :name "child1"} {:id 2 :name "parent1"} {:id 3 :relation/child 1 :relation/parent 2 :relationship/type "parents favourite child"} {:id 4 :relation/child 1 :relation/parent 2 :relationship/type "parents first child"} {:id 5 :relation/child 1 :relation/parent 2 :relationship/type "childs favourite parent"}

Linus Ericsson10:05:53

Of course nothing prevents a node (child1 and parent1) to be referenced as child och parent in any relation. You decide what kind of relationships makes sense.

Linus Ericsson10:05:40

To query this kind of data - use either rules (that can be recursive), which can be somewhat slow, or use the datascript entity functionality (+ graph algorithms).

Linus Ericsson10:05:50

(or use Loom or some other specialized graph lib, at least for inspiration)


> children and parent always goes both ways, right :parents is forced by the desire the have a certain subset of node's data be location-specific. It's a bit of both apples and individual appearances. So, in the above example :data is shared between in all locations of a node, while :location-specific-data is not. (Both of these are just stand-ins for multiple attributes.) The above example is not fine-grained enough even, it should be:

{:id 1 :data "node 1"
 :parents {[2 0] {:location-specific-data "foo"}
           [2 2] {:location-specific-data "bar"}
           [3 0] {:location-specific-data "baz"}}}
where [2 0] encodes that this is the location where parent is 2 while the order (of 1 in :children of 2) is 0. I'd like to avoid creating additional entities. :location-specific-data is not going to be a significant part of querying, so, from a Datalog perspective, totally fine for it to live as a map. And creating additional entities is practically what I'm trying to move away from – wrapping.


To be explicit by what I mean by wrapping:

[{:id 1 :data "node 1" :location-specific-data "foo"}
 {:id 4 :wraps 1 :location-specific-data "bar"}
 {:id 5 :wraps 1 :location-specific-data "baz"}
 {:id 2 :children [1 3 4]} ;; this can be type/ref, cardinality/many
 {:id 3 :children [5]}]

Linus Ericsson11:05:11

So the data for id 2 is the "union" of data of nodes 1 3 4? and the data for id 3 is the union o data of node 5?


I guess you can think of it like that. For 2 it's union of 1 with 4 + 3. For 3 it's 1 with 5.

Linus Ericsson11:05:32

if the model fits your for your need, but the querying is a pain - consider create one or many separate index that first and foremost can be derived from the database, and in a later stage also updated, for instance from the transaction data results. These indexes (hashmaps for quick lookup) could be passed into the queries and be used alongside the database, like (from memory) (q '[:find ?parent ?child :in $ [[?parent [?child ...]]] :where [?parent :name "Leonard"]] db {1 #{3 2}}) And I'm not 100% sure the syntax i describe above really works but you can query different data structures, for sure. and these maps could be constructed with clojure.set


Hm, that's an interesting idea. Though, I guess I can kind of achieve the same thing by introducing an additonal attribute like:

{:id 1 :parents-index #{2 3} :parents {...} ...}


Where :parents-index can be type/ref, cardinality/many.

Linus Ericsson11:05:20

Ah, now I understand, you use :parents as normal data structure in the database. Yes, thats possible in datascript. If the data in that key is really local, they you have your lokal lookup table for that "place". And yes, sure, you can keep a "real" index to the "real" parent entities the way you suggest.


Sorry I didn't make that clear from the start. I guess I can proceed with my strategy. I can add :parents-index if I run into trouble.

Linus Ericsson11:05:59

I'm happy if this made it possible for you proceed!

gratitude 1