What kind of backend data structures are needed for implementing a graph DB like this?

[micahscopes]

I'm curious about how the data is indexed. I'm familiar with the hexastore indexing scheme. How do redisgraph/falcor compare with that on a storage level? I know a bunch of people interested in distributed databases built on "prolly trees", which are like this hybrid between hash array mapped tries and b trees. They do well with both ordered streams and diffs, and allow for structured sharing. Anyhow I'm wondering if it's possible to do the sparse matrix queriable graph representation on top of a tree index?

[swilly22]

At the very beginning RedisGraph used a hexastore as its primary data structure for maintaining graph topology, using the Subject, Object, Predicate paradigm (SOP, SPO, OSP, OPS, POS, PSO). But I don't believe this is an optimal way (performance wise) of representing a property graph.

For the past years we're using GraphBLAS sparse matrices to store our graph structure, there are a number of different matrix "classes":

1. Label matrices - For every label Li in the graph Label matrix Li[j,j] is set if node with ID j is associated with label Li
2. Relation matrices - For every relationship-type Ri in the graph Relation matrix Ri[j,k] = x if there's an edge with ID x connecting nodes j to k.
3. THE Adj matrix - captures the entire graph topology but it is relationship-type agnostic.

There are additional matrices in place but maybe we should publish a more detailed post about our internals.

Thinking about distributing a graph, one way to go about this is to try and split the graph's matrices into blocks, say we have an NxN matrix A we could split A into 4 blocks A0, A1, A2, A3 each of size N/2XN/2 and distribute these blocks among multiple machines.

[jasperblues]

I would love to read about internals!

Another topic I'm interested in is how FolkorDB performs with transactional writes, to be used in an OLAP style application. (Eg to power REST or GraphQL graphy APIs).

[gkorland]

FalkorDB is utilizing Redis Transaction API

[micahscopes]

Thank you so much, this is fascinating. I'd love to read more about the additional matrices if you ever find inspiration to write about this stuff more.

[gkorland]

I think @swilly22 has a couple of posts on this topic