<p>What are the ways that you use to model and retrieve hierarchical info in a database? </p>

[{'answer_id': 38804, 'author': 'Josh', 'author_id': 3166, 'author_profile': 'https://Stackoverflow.com/users/3166', 'pm_score': 4, 'selected': False, 'text': "<p>What's the best way to represent a hierachy in a SQL database?  A generic, portable technique?</p>\n\n<p>Let's assume the hierachy is mostly read, but isn't completely static.  Let's say it's a family tree.</p>\n\n<p>Here's how not to do it:</p>\n\n<pre><code>create table person (\nperson_id integer autoincrement primary key,\nname      varchar(255) not null,\ndob       date,\nmother    integer,\nfather    integer\n);\n</code></pre>\n\n<p>And inserting data like this:  </p>\n\n<pre><code>person_id   name      dob       mother father  \n1           Pops      1900/1/1   null   null  \n2           Grandma   1903/2/4   null   null  \n3           Dad       1925/4/2   2      1  \n4           Uncle Kev 1927/3/3   2      1\n5           Cuz Dave  1953/7/8   null   4\n6           Billy     1954/8/1   null   3\n</code></pre>\n\n<p>Instead, split your nodes and your relationships into two tables.</p>\n\n<pre><code>create table person (\nperson_id integer autoincrement primary key,\nname      varchar(255) not null,\ndob       date\n);\n\ncreate table ancestor (\nancestor_id   integer,\ndescendant_id integer,\ndistance      integer\n);\n</code></pre>\n\n<p>Data is created like this:</p>\n\n<pre><code>person_id   name      dob       \n1           Pops      1900/1/1  \n2           Grandma   1903/2/4   \n3           Dad       1925/4/2   \n4           Uncle Kev 1927/3/3\n5           Cuz Dave  1953/7/8   \n6           Billy     1954/8/1   \n\nancestor_id  descendant_id  distance\n1            1              0\n2            2              0\n3            3              0\n4            4              0\n5            5              0\n6            6              0\n1            3              1\n2            3              1\n1            4              1\n2            4              1\n1            5              2\n2            5              2\n4            5              1\n1            6              2\n2            6              2\n3            6              1\n</code></pre>\n\n<p>you can now run arbitary queries that don't involve joining the table back on itself, which would happen if you have the heirachy relationship in the same row as the node.</p>\n\n<p>Who has grandparents?</p>\n\n<pre><code>select * from person where person_id in \n    (select descendant_id from ancestor where distance=2);\n</code></pre>\n\n<p>All your descendants:</p>\n\n<pre><code>select * from person where person_id in \n    (select descendant_id from ancestor \n    where ancestor_id=1 and distance&gt;0);\n</code></pre>\n\n<p>Who are uncles? </p>\n\n<pre><code>select decendant_id uncle from ancestor \n    where distance=1 and ancestor_id in \n    (select ancestor_id from ancestor \n        where distance=2 and not exists\n        (select ancestor_id from ancestor \n        where distance=1 and ancestor_id=uncle)\n    )\n</code></pre>\n\n<p>You avoid all the problems of joining a table to itself via subqueries, a common limitation is 16 subsuqeries.</p>\n\n<p>Trouble is, maintaining the ancestor table is kind of hard - best done with a stored procedure.</p>\n"}, {'answer_id': 38806, 'author': 'Matt Hamilton', 'author_id': 615, 'author_profile': 'https://Stackoverflow.com/users/615', 'pm_score': 2, 'selected': False, 'text': '<p>FYI: SQL Server 2008 introduces a new <a href="http://msdn.microsoft.com/en-us/library/bb677290.aspx" rel="nofollow noreferrer">HierarchyID</a> data type for this sort of situation. Gives you control over where in the "tree" your row sits, horizontally as well as vertically.</p>\n'}, {'answer_id': 38807, 'author': 'Mark Harrison', 'author_id': 116, 'author_profile': 'https://Stackoverflow.com/users/116', 'pm_score': 2, 'selected': False, 'text': '<p><strong>Oracle: SELECT ... START WITH ... CONNECT BY</strong></p>\n\n<p>Oracle has an extension to SELECT that allows easy tree-based retrieval.  Perhaps SQL Server has some similar extension?</p>\n\n<p>This query will traverse a table where the nesting relationship is stored in <strong>parent</strong> and <strong>child</strong> columns.</p>\n\n<pre><code>select * from my_table\n    start with parent = :TOP\n    connect by prior child = parent;\n</code></pre>\n\n<p><a href="http://www.adp-gmbh.ch/ora/sql/connect_by.html" rel="nofollow noreferrer">http://www.adp-gmbh.ch/ora/sql/connect_by.html</a></p>\n'}, {'answer_id': 38808, 'author': 'NakedBrunch', 'author_id': 3742, 'author_profile': 'https://Stackoverflow.com/users/3742', 'pm_score': 0, 'selected': False, 'text': '<p>If you\'re using SQL Server 2005 then <a href="https://web.archive.org/web/20210927200924/http://www.4guysfromrolla.com/webtech/071906-1.shtml" rel="nofollow noreferrer">this link</a> explains how to retrieve hierarchical data.</p>\n\n<p>Common Table Expressions (CTEs) can be your friends once you get comfortable using them.</p>\n'}, {'answer_id': 38869, 'author': 'NakedBrunch', 'author_id': 3742, 'author_profile': 'https://Stackoverflow.com/users/3742', 'pm_score': 3, 'selected': False, 'text': '<p>I\'ve got to disagree with Josh.  What happens if you\'re using a huge hierarchical structure like a company organization.  People can join/leave the company, change reporting lines, etc... Maintaining the "distance" would be a big problem and you would have to maintain two tables of data.</p>\n\n<p>This query (SQL Server 2005 and above) would let you see the complete line of any person AND calculates their place in the hierarchy and it only requires a single table of user information.  It can be modified to find any child relationship.</p>\n\n<pre><code>--Create table of dummy data\ncreate table #person (\npersonID integer IDENTITY(1,1) NOT NULL,\nname      varchar(255) not null,\ndob       date,\nfather    integer\n);\n\nINSERT INTO #person(name,dob,father)Values(\'Pops\',\'1900/1/1\',NULL);  \nINSERT INTO #person(name,dob,father)Values(\'Grandma\',\'1903/2/4\',null);\nINSERT INTO #person(name,dob,father)Values(\'Dad\',\'1925/4/2\',1);\nINSERT INTO #person(name,dob,father)Values(\'Uncle Kev\',\'1927/3/3\',1);\nINSERT INTO #person(name,dob,father)Values(\'Cuz Dave\',\'1953/7/8\',4);\nINSERT INTO #person(name,dob,father)Values(\'Billy\',\'1954/8/1\',3);\n\nDECLARE @OldestPerson INT; \nSET @OldestPerson = 1; -- Set this value to the ID of the oldest person in the family\n\nWITH PersonHierarchy (personID,Name,dob,father, HierarchyLevel) AS\n(\n   SELECT\n      personID\n      ,Name\n      ,dob\n      ,father,\n      1 as HierarchyLevel\n   FROM #person\n   WHERE personID = @OldestPerson\n\n   UNION ALL\n\n   SELECT\n    e.personID,\n      e.Name,\n      e.dob,\n      e.father,\n      eh.HierarchyLevel + 1 AS HierarchyLevel\n   FROM #person e\n      INNER JOIN PersonHierarchy eh ON\n         e.father = eh.personID\n)\n\nSELECT *\nFROM PersonHierarchy\nORDER BY HierarchyLevel, father;\n\nDROP TABLE #person;\n</code></pre>\n'}, {'answer_id': 38945, 'author': 'Telcontar', 'author_id': 518, 'author_profile': 'https://Stackoverflow.com/users/518', 'pm_score': 2, 'selected': False, 'text': '<p>I prefer a mix of the techinques used by Josh and Mark Harrison:</p>\n\n<p>Two tables, one with the data of the Person and other with the hierarchichal info (person_id, parent_id [, mother_id]) if the PK of this table is person_id, you have a simple tree with only one parent by node (which makes sense in this case, but not in other cases like accounting accounts)</p>\n\n<p>This hiarchy table can be transversed by recursive procedures or if your DB supports it by sentences like SELECT... BY PRIOR (Oracle).</p>\n\n<p>Other posibility is if you know the max deep of the hierarchy data you want to mantain is use a single table with a set of columns per level of hierarchy</p>\n'}, {'answer_id': 48298, 'author': 'andy47', 'author_id': 2661, 'author_profile': 'https://Stackoverflow.com/users/2661', 'pm_score': 5, 'selected': True, 'text': '<p>The definitive pieces on this subject have been written by Joe Celko, and he has worked a number of them into a book called Joe Celko\'s Trees and Hierarchies in SQL for Smarties.</p>\n\n<p>He favours a technique called directed graphs. An introduction to his work on this subject can be found <a href="http://web.archive.org/web/20081102031702/http://www.intelligententerprise.com/001020/celko.jhtml" rel="nofollow noreferrer">here</a></p>\n'}, {'answer_id': 99939, 'author': 'markus', 'author_id': 11995, 'author_profile': 'https://Stackoverflow.com/users/11995', 'pm_score': 5, 'selected': False, 'text': '<p>I like the Modified Preorder Tree Traversal Algorithm. This technique makes it very easy to query the tree.</p>\n\n<p>But here is a list of links about the topic which I copied from the Zend Framework (PHP) contributors webpage (posted there by Posted by Laurent Melmoux at Jun 05, 2007 15:52).</p>\n\n<p>Many of the links are language agnostic:</p>\n\n<p>There is 2 main representations and algorithms to represent hierarchical structures with databases :</p>\n\n<ul>\n<li>nested set also known as modified preorder tree traversal algorithm</li>\n<li>adjacency list model</li>\n</ul>\n\n<p>It\'s well explained here:</p>\n\n<ul>\n<li><a href="http://www.sitepoint.com/article/hierarchical-data-database" rel="noreferrer">http://www.sitepoint.com/article/hierarchical-data-database</a></li>\n<li><a href="http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/" rel="noreferrer">Managing Hierarchical Data in MySQL</a></li>\n<li><a href="http://evolt.org/node/4047/" rel="noreferrer">http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html</a></li>\n</ul>\n\n<p>Here are some more links that I\'ve collected:</p>\n\n<ul>\n<li><a href="http://en.wikipedia.org/wiki/Tree_%28data_structure%29" rel="noreferrer">http://en.wikipedia.org/wiki/Tree_%28data_structure%29</a></li>\n<li><a href="http://en.wikipedia.org/wiki/Category:Trees_%28structure%29" rel="noreferrer">http://en.wikipedia.org/wiki/Category:Trees_%28structure%29</a></li>\n</ul>\n\n<p>adjacency list model</p>\n\n<ul>\n<li><a href="http://www.sqlteam.com/item.asp?ItemID=8866" rel="noreferrer">http://www.sqlteam.com/item.asp?ItemID=8866</a></li>\n</ul>\n\n<p>nested set</p>\n\n<ul>\n<li><a href="http://www.sqlsummit.com/AdjacencyList.htm" rel="noreferrer">http://www.sqlsummit.com/AdjacencyList.htm</a></li>\n<li><a href="http://www.edutech.ch/contribution/nstrees/index.php" rel="noreferrer">http://www.edutech.ch/contribution/nstrees/index.php</a></li>\n<li><a href="http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/" rel="noreferrer">http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/</a></li>\n<li><a href="http://www.dbmsmag.com/9604d06.html" rel="noreferrer">http://www.dbmsmag.com/9604d06.html</a></li>\n<li><a href="http://en.wikipedia.org/wiki/Tree_traversal" rel="noreferrer">http://en.wikipedia.org/wiki/Tree_traversal</a></li>\n<li><a href="http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html" rel="noreferrer">http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html</a> (applet java montrant le fonctionnement )</li>\n</ul>\n\n<p>Graphes</p>\n\n<ul>\n<li><a href="http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html" rel="noreferrer">http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html</a></li>\n</ul>\n\n<p>Classes :</p>\n\n<p>Nested Sets DB Tree Adodb</p>\n\n<ul>\n<li><a href="http://www.phpclasses.org/browse/package/2547.html" rel="noreferrer">http://www.phpclasses.org/browse/package/2547.html</a></li>\n</ul>\n\n<p>Visitation Model ADOdb</p>\n\n<ul>\n<li><a href="http://www.phpclasses.org/browse/package/2919.html" rel="noreferrer">http://www.phpclasses.org/browse/package/2919.html</a></li>\n</ul>\n\n<p>PEAR::DB_NestedSet</p>\n\n<ul>\n<li><a href="http://pear.php.net/package/DB_NestedSet" rel="noreferrer">http://pear.php.net/package/DB_NestedSet</a></li>\n<li>utilisation : <a href="https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html" rel="noreferrer">https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html</a></li>\n</ul>\n\n<p>PEAR::Tree</p>\n\n<ul>\n<li><a href="http://pear.php.net/package/Tree/download/0.3.0/" rel="noreferrer">http://pear.php.net/package/Tree/download/0.3.0/</a></li>\n<li><a href="http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html" rel="noreferrer">http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html</a></li>\n</ul>\n\n<p>nstrees</p>\n\n<ul>\n<li><a href="http://www.edutech.ch/contribution/nstrees/index.php" rel="noreferrer">http://www.edutech.ch/contribution/nstrees/index.php</a></li>\n</ul>\n'}, {'answer_id': 314104, 'author': 'Markus Plesser', 'author_id': 40251, 'author_profile': 'https://Stackoverflow.com/users/40251', 'pm_score': 1, 'selected': False, 'text': '<p>We had the same issue when we implemented a tree component for <a href="http://www.flexive.org/" rel="nofollow noreferrer" title="[fleXive]">[fleXive]</a> and used the nested set tree model approach mentioned by tharkun from the <a href="http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/" rel="nofollow noreferrer" title="Managing Hierarchical Data in MySQL">MySQL</a> docs.</p>\n\n<p>In addition to speed things (dramatically) up we used a <em>spreaded</em> approach which simply means we used the maximum Long value for the top level right bounds which allows us to insert and move nodes without recalculating all left and right values. Values for left and right are calculated by dividing the range for a node by 3 und use the <em>inner</em> third as bounds for the new node.</p>\n\n<p>A java code example can be seen <a href="http://source.flexive.org/browse/~raw,r=798/fleXive/trunk/src/framework/java/com/flexive/core/storage/genericSQL/GenericTreeStorageSpreaded.java" rel="nofollow noreferrer">here</a>. </p>\n'}]
['https://Stackoverflow.com/questions/38801', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/2027/']