Design pattern for directed acyclic graphs in MongoDB

Question

The problem

As usual the problem is to display a directed acyclic graph in a database. The choices for a Database I had were a relational database like mysql or mongodb. I chose mongoDb because DAGs in relational databases are a mess but if there is a trick I just didn't find please tell me.

The goal is to map a DAG in one or multiple MongoDB Documents. Because we have multiple children and parents SubDocuments where no possibility. I came across multiple design patterns but am not sure which one is the best to go with.

---

Tree-structure with Ancestors Array

The Ancestors Array is suggested by the mongoDB docs. And is quite easy to understand. As I understand it my document would look like this:

{
    "_id" : "root",
    "ancestors" : [ null ],
    "left": 1
}
{
    "_id" : "child1",
    "ancestors" : [ "root" ],
    "left": 2
}
{
    "_id" : "child2",
    "ancestors" : [ "root", "child1" ],
    "left": 1
}

This allows me to find all children of an element like this:

db.Tree.find({ancestors: 'root'}).sort({left: -1})

and all parents like this:

db.Tree.findOne({_id: 'child1'}).ancestors

DBRefs instead of Strings

My second approach would be to replace the string-keys with DBRefs. But except for longer database records I don't see many advantages over the ancestors array.

String-based array with children and parents

The last idea is to store not only the children of each document but it's parents as well. This would give me all the features I want. The downside is the massive overhead of information I would create by storing all relations two times. Further on I am worried by the amount of administration there is. E.g. if a document gets deleted I have to check all others for a reference in multiple fields.

---

My Questions

• Is MongoDb the right choice over a relational database for this purpose?
• Are there any up-/downsides of any of my pattern I missed?
• Which pattern would you suggest and why? Do you maybe have experience with one of them?

Answer 1

Why don't you use a graph database? Check ArangoDB, you can use documents like MongoDB and also graphs. MongoDB is a great database, but not for storing graph oriented documents. ArangoDB does.

https://www.arangodb.com/