GeoPub: A Multi-Model Database

As part of the openEngiadina project we are researching technology for open and decentralized local knowledge.

Local knowledge comes in a variety of forms and shapes. In order to support this variety we use the RDF data model along with Datalog as a declarative and expressive query laguage (see this previous post).

In this post I'd like to describe the indexing strategies we use that allow efficient querying of local knowledge. In particular, I'd like to highlight how a database can support efficient graph, geo-spatial and full-text search queries at the same time - a multi-modal database. This is an important step towards search and discovery of local knowledge.

Everything described here is implemented in the GeoPub Web application. A demo installation of GeoPub is available here (note that initial loading takes very long).

Without further ado, let's dive into how GeoPub's multi-model database works.

Ordered Key-Value Stores

A very simple form of a database is a key-value store. A key-value store allows values to be persistently stored and accessed with some associated key. Given a key the value can usually be retrieved very efficiently, i.e. in $\mathcal{O}\left(log\left(n\right)\right)$ where $n$ is the number of values stored in the database.

Unfortunately, accessing individual values by their keys is not enough to allow interesting database queries.

Assume we have a database with $n$ key-value pairs $\left(k_i,v_i\right)$ and some function $\mathit{<mi>f</mi>}:V\to \mathbb{<mi>N</mi>}$ that maps values to natural numbers. Now we would like to find all the key-value pairs $\left(k_i,v_i\right)$ such that $\mathit{<mi>f</mi>}\left(v_i\right)=42$.

In a simple key-value store there is no way of efficiently finding the subset of key-value pairs that fulfills such a property. We must iterate over all $n$ key-value pairs in the store and evaluate the function on every value individually.

The number of key-value pairs $c$ that we are interested in is usually much smaller than the number of stored key-value pairs $n$. For example we might be looking for a property that is held by ten entries in a store of millions of entries. In order to be able to query our key-value store efficiently, we really need a way of finding these entries without having to iterate over all entries in the store. Luckily, we don't need to add much to the key-value store. We just need some order.

Order, order!

An ordered key-value store (OKVS) is a persistent storage that allows values to be stored with some associated key. The keys are sorted according to some order and given a range of keys the associated key-value pairs in the range can be accessed efficiently. If there are $c$ key-value pairs in a given range then the complexity of accessing the range is usually $\mathcal{O}\left(log\left(n\right)+c\right)$. We need to find the first entry in the range ($\mathcal{O}\left(log\left(n\right)\right)$) and then iterate over all entries in the range ($\mathcal{O}\left(c\right)$). This is much better than a simple key-value store.

Note that such a range query can not be implemented efficiently in a simple key-value store. Checking if a key is within a range is a property that must be evaluated on every single stored key-value pair (like our function $\mathit{<mi>f</mi>}$).

But how does this help us query more efficiently?

Pre-Computing Properties

Instead of stroring values associated with the original key, we can instead store them associated with $\mathit{<mi>f</mi>}\left(v_i\right)$. The store is now populated with key-values of the form $\left(\mathit{<mi>f</mi>}\left(v_i\right),v_i\right)$.

We can efficiently query for all the values for which $\mathit{<mi>f</mi>}\left(v_i\right)=42$ by querying for the range of keys with $42\le k\le 42$. In fact we can also query for more interesting ranges: For example all values $v_i$ with $13\le \mathit{<mi>f</mi>}\left(v_i\right)\le 21$.

This may seem like a cheap trick, but it is a very powerful way of making values efficiently queryable along some pre-defined properties (in our case the value of the function $\mathit{<mi>f</mi>}$). It is also a very widespread trick. This is what is called an index in database terminology.

The index is a projection of some properties we are interested in to a dimension that can be efficiently queried. In our case the dimension that can be efficiently queried is the intrinsic order of the key-value store. The function $\mathit{<mi>f</mi>}$ is a projection to this dimension. We will see some more concrete examples that will illustrate this idea much better. Don't worry too much about understanding this in the abstract now.

Of course our toy example is overly simplified and has some draw-backs. For one, we have lost the original keys (the $k_i$). We also might want to query along some other property (e.g. a function $\mathit{<mi>g</mi>}$). We will be able to solve both with some tricks.

Tuples as Keys

Most existing ordered key-value stores require keys (and values) to be byte sequences and the intrinsic order in which keys are sorted is the lexicographic byte order. That is b00 < b01 and b0 < b00.

We can use other types such as bools, integers, strings or compound types for keys as long as we can encode them to bytes. The only thing we must ensure is that the encoding preserves the order between keys.

We will mostly be using tuples as keys. For example a key could be $\left(1,2,3\right)$ or $\left(''Lorem\; Ipsum'',true,32\right)$. We use lexicographic order on tuples, e.g. $\left(1\right)<\left(1,2\right)<\left(1,5\right)<\left(42\right)<\left(''strings\; are\; ordered\; higher\; than\; ints'',52\right)$.

The fact that an order preserving encoding to byte sequences exists for tuples (and the types we use in tuples) is left as an exercise for the reader. Hint: For tuples try a concatenation of type-length-value encoded elements (e.g. CBOR).

Another basic type that will be useful is symbols. We will use symbols such as rdf or spo in key tuples, e.g.: $\left(<mi>rdf</mi>,<mi>spo</mi>,1,42,98\right)$.

Using symbols allows us to create named sub-spaces that can be queried efficiently. For example we can efficiently query for all keys in the $\left(<mi>rdf</mi>,<mi>spo</mi>\right)$ space that start with the values 1 to 12 by querying for the range of keys with $\left(<mi>rdf</mi>,<mi>spo</mi>,1\right)\le k\le \left(<mi>rdf</mi>,<mi>spo</mi>,12\right)$. This would return keys such as $\left(<mi>rdf</mi>,<mi>spo</mi>,1,42,98\right)$, $\left(<mi>rdf</mi>,<mi>spo</mi>,1,59,2\right)$ or $\left(<mi>rdf</mi>,<mi>spo</mi>,7,8,5\right)$ (if present in the store).

Indexing

We are now ready to improve on our initial solutions for efficiently querying values applied to the function $\mathit{<mi>f</mi>}$.

To recap: we have a bunch of key-value pairs $\left(k_i,v_i\right)$, a function $\mathit{<mi>f</mi>}:V\to \mathbb{<mi>N</mi>}$ that maps values to natural numbers and we would like to find key-value pairs for which the applied function takes on some values.

For every key-value pair $\left(k_i,v_i\right)$ that we store, we also store an additional entry with key $\left(<mi>f</mi>,\mathit{<mi>f</mi>}\left(v_i\right)\right)$ and value $k_i$.

In order to efficiently query along the property defined by the function $\mathit{<mi>f</mi>}$ we query for all keys in the range $\left(<mi>f</mi>,\mathrm{lower-bound}\right)\le k\le \left(<mi>f</mi>,\mathrm{upper-bound}\right)$. The values returned by this query are the original keys $k_i$. We can use them to retrieve the associated values $v_i$.

The additional entries $\left(<mi>f</mi>,\mathit{<mi>f</mi>}\left(v_i\right)\right)$ are index entries that point to the original key (also called the primary key). Unlike our initial solution we have not lost any information and can easily add additional indexes for other properties.

This is the basic idea towards building your own custom indices and multi-model databases. We will see examples and variations of this idea when looking at concrete examples below.

Implementation Notes

Ordered-key value stores such as LMDB or LevelDB expose an API as described above and the ideas illustrated above can be implemented pretty directly. In GeoPub we use the web-native database IndexedDB, which provides a slightly different and more high-level API. Nevertheless, the OKVS ideas can be applied and we will give some hints on how while discussing the examples. For a deep-dive check out the GeoPub source-code.

Indexing Strategies

Enough of the abstract. Let's look at some concrete examples of properties and dimensions on which we would like to be able to efficiently query.

RDF Triples

For the openEngiadina project we use the RDF data model to support the various types of data (see this previous post for an introduction to RDF).

In a nutshell: In RDF data is represented as a directed and labeled graph. Nodes are either IRIs (internationalized URIs) or literal values and directed edges are labeled with an URI. The atomic elements in RDF are triples: two nodes and the directed edge between them. Or in RDF parlance: A subject node that is connected with a directed edge, that is labeled with a predicate, to an object node.

We will use the notation $\left(s,p,o\right)$ for triples, where $s$ is the subject, $p$ the predicate and $o$ the object. A value that may appear in the subject, predicate or object position of a triple is called a term.

We note that in RDF things and concepts ideally have unique identifiers. Even if they appear in completely different contexts. In other word, the same term can appear in many triples.

{"spo":[6,8,9],"pos":[8,9,6],"osp":[9,6,8]}

Geo-Spatial

There are some limits to what we can query for with the RDF indices presented previously. For example some RDF data might have geo-spatial information attached:

<https://example.com/a-geo-note>
  a as:Note ;
  geo:lat "46.7970040956";
  geo:long "10.2982868244";
  as:content "An ActivityStreams note with a geo position." .

We would like to be able to find such notes efficiently by querying for things in the vicinity of a given point.

Note that we can not do this with the RDF indices as described above. The RDF indices only allow us to search for triples that exactly match some pattern. Finding things in the vicinity can not be formulated as a triple pattern that should be matched. We need a specialized index.

Geo-spatial data is two dimensional and we need to be able to query both dimensions (longitude and latitude) at the same time. There exist specialized data-structures for querying such multi-dimensional data. Examples include Quadtrees, R-Trees or k-d trees. Our ordered key-value store, on the other hand, is queryable only in a single dimension. Can we still make use of our okvs for geo-spatial queries?

Full-Text Search

Another dimension we would like to be able to query is full-text, i.e. given some natural language term we would like to find all entries that contain the term. This is another example of where exact RDF triple pattern matching does not work.

Full-text search is a fuzzy thing. It would be nice if a query for the term "connected" also returns entries that contain the words "connections", "connected" or "connective". This can be done by performing a linguistic normalization called stemming (see the Xapian documentation for a good introduction to the topic).

In order to perform full-text searches we create an index for all RDF literals that have type string (and langString) that maps the linguistic normalized stems appearing in the literal to the literal identifier (as stored in the dictionary).

When given a query we again perform the linguistic normalization on the query to first get a list of query stems. We then use the index to find all literals that contain the stems appearing in the query.

When querying we want to match literals that contain all the query stems (i.e. query result should be a logical and, not a logical or). This is a join over the literal ids. A neat trick (that we stole from this little gist) is to do this join as a merge join. This is an efficient join algorithm that uses the fact that entries are soreted in the okvs.

More Indices

We have looked at three different indexing strategies (RDF, geo-spatial and full-text search) that can be implemented on ordered key-value stores. There are more indices that can be implemented on ordered key-value stores. Examples include temporal indices, pre-computed cryptographic signature verification (see RDF Signify and DMC), revisions (i.e. versioning) and many more!

Conclusion and Outlook

I hope to have illustrated the ideas behind how we have implemented a multi-modal database for openEngiadina that is capable of handling the variety of data that is local knowledge.

The main ingredient to all this has been ordered key-value stores. I find this a very elegant and powerful abstraction. The ideas are practically accessible as robust and well-tested ordered key-value stores exist (e.g. LMDB, LevelDB or SQLite LSM) that can be used to experiment with the ideas. The hard parts of databases (persistence and transactions) are already solved and we can experiment with indices and how to make concrete queries efficient in relative safety.

Ordered key-value stores are a relatively niche subject. Previous work include SRFI-167 and SRFI-168 by Amirouche Boubekki as well as FoundationDB.

This post is a feeble attempt to provide a framework for thinking about ordered key-value stores. I hope to have sparked your interest and invite you to experiment and formulate your thoughts on the topic. Much more thought and work is needed to polish these ideas.

Fin

My fellow openEngiadina developer rustra has been sentenced to 5 years in prison as a victim of political repression in Belarus. Read his last words in court and an interview. Please consider donating to the Anarchist Black Cross Belarus.

Many thanks to the countless people who have helped form these ideas and have provided valuable feedback and ideas. A special thanks goes to Amirouche Boubekki who gave me the courage to pursue these ideas with his work on SRFI-167, SRFI-168 and Babelia.

Thank you, dear reader, for your interest and time. If you have thoughts, comments or questions, please feel free to get in contact! We have an IRC room on Libera (#openEngiadina) or you can contact me directly by mail (pukkamustard [at] posteo [dot] net).

The openEngiadina project is supported by the NLnet Foundation trough the NGI0 Discovery Fund.