title: Design pattern for directed acyclic graphs in MongoDB
body: <h3>The problem</h3>
  
  <p>As usual the problem is to display a <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph">directed acyclic graph</a> in a database. The choices for a Database I had were a relational database like <em>mysql</em> or <em>mongodb</em>. I chose mongoDb because DAGs in relational databases are <a href="http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o">a mess</a> but if there is a trick I just didn't find please tell me.</p>
  
  <p>The goal is to map a DAG in one or multiple MongoDB Documents. Because we have multiple children <strong>and</strong> parents <em>SubDocuments</em> where no possibility. I came across multiple design patterns but am not sure which one is the best to go with.</p>
  
  <hr>
  
  <h3>Tree-structure with Ancestors Array</h3>
  
  <p>The Ancestors Array is <a href="http://docs.mongodb.org/manual/tutorial/model-tree-structures-with-ancestors-array/">suggested by the mongoDB docs</a>. And is quite easy to understand. As I understand it my document would look like this:</p>
  
  <pre><code>{
      "_id" : "root",
      "ancestors" : [ null ],
      "left": 1
  }
  {
      "_id" : "child1",
      "ancestors" : [ "root" ],
      "left": 2
  }
  {
      "_id" : "child2",
      "ancestors" : [ "root", "child1" ],
      "left": 1
  }
  </code></pre>
  
  <p>This allows me to <code>find</code> all children of an element like this:</p>
  
  <pre><code>db.Tree.find({ancestors: 'root'}).sort({left: -1})
  </code></pre>
  
  <p>and all parents like this:</p>
  
  <pre><code>db.Tree.findOne({_id: 'child1'}).ancestors
  </code></pre>
  
  <h3>DBRefs instead of Strings</h3>
  
  <p>My second approach would be to replace the <strong>string-keys</strong> with  <code>DBRef</code>s. But except for longer <em>database records</em> I don't see many advantages over the <strong>ancestors array</strong>.</p>
  
  <h3>String-based array with <code>children</code> and <code>parents</code></h3>
  
  <p>The last idea is to store not only the <code>children</code> of each document but it's <code>parents</code> 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 <em>relations</em> 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.</p>
  
  <hr>
  
  <h3>My Questions</h3>
  
  <ul>
  <li>Is MongoDb the right choice over a relational database for this purpose?</li>
  <li>Are there any up-/downsides of any of my pattern I missed?</li>
  <li>Which pattern would you suggest and why? Do you maybe have experience with one of them?</li>
  </ul>