DB normalization/joining

[si14]

This issue is mostly an invitation to continue the Slack discussion.

The problem

I frequently find myself writing normalization/denormalization code in various places. It would be nice to have an "officially blessed" (or documented) approach, be it a part of re-frame, a library or just a documented pattern.

What's normalization?

The long explanation can be found in Om.Next wiki. In short, in this particular context, it's a practice of storing "objects" (or entity's properties if you may) in an (often) top-level map by their ID. For example, if we have some Snippets belonging to a bunch of Users, we may structure app DB as follows:

{:user/by-id {:joe-id {:name "Joe"
                       :id :joe-id
                       :snippets [1 3 5]}
              :jane-id {:name "Jane"
                        :id :jane-id
                        :snippets [2 4]}}
 :snippet/by-id {1 {:id 1
                    :creation-date ...
                    :text "..."}
                 2 {...}}}

There are two separate concerns resolved by normalization: ordering and modification consistency.

Modification consistency

I'll lift an example from Om.Next docs. Let's say you have the following structure:

(def init-data
  {:list/one [{:name "John" :points 0}
              {:name "Mary" :points 0}
              {:name "Bob"  :points 0}]
   :list/two [{:name "Mary" :points 0 :age 27}
              {:name "Gwen" :points 0}
              {:name "Jeff" :points 0}]})

You see that "Mary" occurs in both lists? If you want to increment Mary's points, you'll need to ensure that you are incrementing them in both places. On the other hand, if you normalize the structure like this

{:list/one
 [[:person/by-name "John"]
  [:person/by-name "Mary"]
  [:person/by-name "Bob"]],
 :list/two
 [[:person/by-name "Mary"]
  [:person/by-name "Gwen"]
  [:person/by-name "Jeff"]],
 :person/by-name
 {"John" {:name "John", :points 0},
  "Mary" {:name "Mary", :points 0, :age 27},
  "Bob" {:name "Bob", :points 0},
  "Gwen" {:name "Gwen", :points 0}, 
  "Jeff" {:name "Jeff", :points 0}}}

you can increment the value only once while ensuring consistent data across your app. Please note that Om.Next uses explicit "reference typing" like [:person/by-name "Mary"], while in others examples in this issue I use "implicit" one with int IDs. Which one do you think is better?

Ordering

Sometimes you want to preserve a server-provided ordering (let's say you receive a vector of Snippets) while having a way to access "objects" by IDs. You have at least three alternatives:

1. create both a vector and a map of Snippets, hopefully exploiting pointer sharing. Now you need to manually ensure modification consistency between both structures.
2. use something like map-indexed to add an index into each Snippet and use either sorted-map-by or sort by that index in your views. It's workable but honestly doesn't feel right.
3. accumulate all Snippets in a map, use a vector of IDs to preserve order.

Questions

• Do you think there is a problem here?
• Do you see normalization as a way to structure data in your webapps?
• Do you think re-frame should facilitate a solution, either through docs, code or a link to a library?
• Which "reference style" would you prefer, "typed"/"explicit" or "implicit" one?

[mccraigmccraig]

• i like normalization because it corresponds well to my server-side data model
• i don't think it should be part of re-frame core
• a library would be nice
• library scope could include
  • unpacking api responses
  • caching (which associated ids need refreshing according to some policy)
  • joining
• i like both types of reference style - i would not want a dependency on, say, IDs being ints though - most of my IDs are UUIDs, some are strings, none are ints
• support for compound keys would be nice, though perhaps overkill
• if there is a model defining entity keys, foreign keys etc it would be nice if this was in a .cljc so it can be shared with the backend

[mbertheau]

I definitely see a challenge here for bigger apps. I also definitely think re-frame should facilitate an approach; a best practices document would help re-frame users a lot. If these best practices need non-trivial code, the code could be in re-frame or in an external library.

[arichiardi]

I had this discussed with a friend while engaging in a rethinkdb project not long ago.

We/he ended working on a custom language/middleware that was able to denormalize the data in the backend given data relations and send it to the frontend shaped right. While investigating this, I though about the ol' good datalog for defining relations on data and then perform the queries on a map.
I haven't applied this approach eventually but it sounds totally doable and I would love to try it "for real".

The immense @fogus even revived it and made it cljs compatilble in bacwn so it would theoretically be possible to apply this to the app-db. But as @mccraigmccraig said I see it more as a separate lib.

[mike-thompson-day8]

It is difficult for me to comment in any depth on this. Because of the kinds of apps we write, I don't struggle (yet) with this problem. So I have no opinions distilled from hand to hand combat.

It does seem like this should start as a library, or maybe just a tutorial enumerating options and techniques. I'd be happy to see these tutorials end up in the developing /docs folder.

If you are keeping normalised data around, then it is just a matter of time before you'll need to join with clojure.set/join. Many don't know the function even exists. So it would be useful to have that kind of suggestion available, along with other pointers.

I do have a further cautious observation: at core, it seems as if the goal is to turn app-db into a more capable in-memory relational database. At the moment, app-db is a plain map and you have to build a relational structure within it. Entries like [:person/by-name "John"] are really just foreign keys as map paths. So, am I right in seeing this as an attempt to make app-db more relational and database-y?

If so, we should acknowledge that this can be achieved via the disciplined application of certain techniques and conventions OR ...

... I wonder if the goal should be bring DataScript into re-frame more directly. With the adjustments in 0.8.0 that should now be easier to do (claim untested).

Imagine a world in which event handlers are given app-db and a connection to a DataScript database. Or maybe just a Database connection. Same with subscriptions. So the "one big atom" becomes "an atom and a DataScript database" which together form "the one place" for data. Certain data put in one, and certain data put in the other.

Like I say, the pieces are all there to make this happen pretty easily (claim untested).

[mike-thompson-day8]

There was good enthusiasm on this initially. I can't work on this, myself, but I'd like to encourage someone else to take this forward. Leaving open for the moment, but will close if no further progress.

[mike-thompson-day8]

In the absence of further activity or input, and in the interests of tiding up ahead of v0.9,, I'm going to close this issue.

I reiterate my earlier assessment:

at core, it seems as if the goal here is to turn app-db into a more capable in-memory relational database. At the moment, app-db is a plain map and you have to build a relational structure within it. Entries like [:person/by-name "John"] are really just foreign keys as map paths. So, am I right in seeing this as an attempt to make app-db more relational and database-y?

I believe the real job here is for someone to document techniques and best practice around representing relational data in a map. But that someone isn't going to be me (I don't have that itch).

[julienfantin]

If you're interested in this issue you might want to check out our pre-release of SubGraph. It handles normalization transparently for the user and uses datomic or om.next style pull queries to retrieve subscription graphs. Still alpha quality and more documentation is needed but we've been using it in production for months.

[mike-thompson-day8]

There is also this pull library from Juxt: https://github.com/juxt/pull which may give inspiration.

[mike-thompson-day8]

Libraries are listed in an FAQ:
https://github.com/Day8/re-frame/blob/master/docs/FAQs/DB_Normalisation.md

If there are any additions can you supply a PR updating that FAQ document please.