How to maintain order when modeling outline in graph database

database-designgraphgraph-dbmsneo4j

(TaskPaper) outlines have a natural hierarchy relationship, so a graph database seems like a great fit. Each item in the outline is a node of the graph that points to its parent and children. I also really like the idea of modeling TaskPaper tags as nodes that any tagged items point to.

However, there is one problem: the order of items is important in an outline, but a simple graph doesn't keep that information. What is the best way to maintain the order of items when an outline is stored as a graph?

The method should be efficient when items are added/removed. New items may be inserted before existing items, so a simple increasing counter/timestamp won't work.

The goal is to store and query a giant outline that can't fit in memory (just the necessary items are streamed to/from the user). Two common ways of querying this outline would be:

  • Linear: get the first n=100 items when everything is "expanded."
  • Breadth first, with depth first traversal of certain items: only get the top level items, fulling expanding a few selected items. (If fully expanding an item would exceed n=100 items, stop expanding.)

Common updates would be:

  • Add/delete a new item somewhere in the hierarchy. Most inserts will probably be appending after the last child of an item. (Basic editing.)
  • Add/delete a new sub-tree (Copy-paste a section of an outline.)

I don't think other database types would be better than a graph database, but I'm open to using other databases (relational, NoSQL, etc).

Best Answer

This is a challenge I have faced multiple times here recently. There are a few ways that I have solved ordering which seems dependent upon the implementation of the graph dbms. Personally, I use Dgraph's Slash GraphQL service. There are some challenges with working with the GraphQL standardized endpoint vs. some database features that are only still available in DQL (Dgraph Query Language extending GraphQL).

Having that said, here are a few ways that I have found to solve such cases:

With a next and previous edge.

This is covered more in detail by MichelDiz on Dgraph's Community post.

DQL has added a @recurse and @normalize directive that helps make the results possible to flatten a deep nest of nest edges. Adding a new one in the hierarchy involves creating a new node with 2 edges to the next and previous nodes and then updating the next edge on the previous node and updating the previous edge on the next node. The query to get a series of edges would look like:

{
  var(func: eq(title, "Series ABC" )){
    G as articles @filter(not has(<~next>)) 
  }
  q(func: uid(G)) @recurse  {
    uid : uid
    title : title
    next @normalize
  }
}

While this is a brilliant answer, it only works from the DQL endpoint or with a custom query and mutations added to the GraphQL endpoint.

With a parent node holding an array of the order.

At the time of writing this, Slash GraphQL list type [...] functions as a set and not like a JSON array. With this in mind, it does not store duplicates nor preserves order. However, GraphQL can support JSON inside of a string type. (Dgraph has a current feature request to support JSON as a new type as well.) With this fact and the ease of JSON manipulation, we can create a structure to store an order of a list of articles.

type Paper {
  id: ID
  articles: [Article]
  title: String! @search(by: [term])
  order: String
}
type Article {
  id: ID
  content: String! @search(by: [fulltext])
  isDone: Boolean @search
}

With this schema and the auto generated queries and mutations, you would be could add a new article and then update the parent paper's order predicate using your favorite client side JSON manipulation language such as javascript to splice the array of ids inserting your new id as needed.

You can also then make a request to get this order predicate and paginate it on the client side splicing it into chunks and then provide those chunks to the queryArticle query to paginate through your page as needed.

Related Question