Copernic: versioned triple store

Using FoundationDB
1

I pleased to announce the immediate availability of copernic:

2

Interesting. Do you mind add copernic to https://github.com/FoundationDB/awesome-foundationdb?

3

I made a pull-request.

4

For more technical there is my blog or here:

The whole thing rely on the generic tuple store nstore(n) that is a tuple of n dynamically typed objects (uuid, number, boolean, string). It looks like a SQL table with n column without predefined types. To be able to query any pattern in on hop, there is a minimal set of indices that are permutations of range(n) that allows to construct the indices. The following answer gives the math result https://math.stackexchange.com/a/3146793/23663 and that one the Python algorithm to compute one minimal set of permutation https://stackoverflow.com/a/55148433/140837. Given that result, and n=3 you can do any SQL query that looks like:

SELECT item2 FROM tuples WHERE item1="hello", item3="world"

or

SELECT item1, item2 FROM tuples WHERE item3="world"

etc…

In the case n=3, the number of indices is also 3. But in the case n=5 the coefficient factor is 10.

I tried two approaches:

  • git-like Directed-Acyclic-Graph history: in that approach, during a merge (or rebase) one need to recompute the history significance of all the commits that come from the other branch. The advantage of that approach is that branches have a proper history.

  • The current approach adopted by copernic, is to have a single branch history, with stash of changes like git stash does. Additions and deletions are associated with None as timestamp, that make them invisible to the rest of the operations. To create a vnstore(n) you need a nstore(n+2) with an item representing whether the tuple is alive? and an item that is the UUID of the commit that is possibly stashed. metadata, the commit information (parent, date, message, uid,… and timestamp) is stored in another vstore(3). When a commit is made part of the history aka. applied to history, the associated timestamp in metadata is replaced with a VersionStamp. That could be all of it. Since I want fast queries of latest version snapshot I have another nstore(n) that is the snapshot of the latest version, that is during a commit, the operations described in the vnstore stash will be re-applied to the snapshot. Given that, copernic use vnstore(3) hence one nstore(3) for the latest version snapshot, one nstore(3) for history metadata and another nstore(5) for the (uid, key, value) + (alive?, changeid).

The important thing is that the “apply a change” operation should be fast: swap None with a VersionStamp and apply the changes to the snapshot (which can be slow if there is lot of changes).