Nested set model: Difference between revisions

Revision as of 16:33, 12 October 2016

Revision as of 04:13, 13 October 2016

Line 1:

The '''nested set model''' is a particular technique for representing [[nested set]]s (also known as [[tree (data structure)|tree]]s or [[hierarchy|hierarchies]]) in [[relational database]]s.

The term was apparently introduced by [[Joe Celko]]; others describe the same technique using different terms.<ref>[http://www.infokarta.com/content/relational-taboo-recursive-dimensions-and-topological-ordering-nested-sets Recursive Dimension Hierarchies: The Relational Taboo by Michael Kamfonas originally published at the Relational Journal in 1992]</ref>

<ref>[http://articles.sitepoint.com/article/hierarchical-data-database/2 Storing Hierarchical Data in a Database: ''Modified Pre-order Tree Traversal''], by Gijs van Tulder, at articles.sitepoint.com</ref>

== Motivation ==

The technique is an answer to the problem that the standard [[relational algebra]] and [[relational calculus]], and the [[SQL]] operations based on them, are unable to express all desirable operations on hierarchies directly. A hierarchy can be expressed in terms of a parent-child relation - Celko calls this the [[adjacency list model]] - but if it can have arbitrary depth, this does not allow the expression of operations such as comparing the contents of hierarchies of two elements, or determining whether an element is somewhere in the subhierarchy of another element. When the hierarchy is of fixed or bounded depth, the operations are possible, but expensive, due to the necessity of performing one [[Join (relational_algebrarelational algebra)#Joins_and_joinJoins and join-like_operatorslike operators|relational join]] per level. This is often known as the [[bill of materials]] problem.{{citation needed|date=November 2011}}

Hierarchies may be expressed easily by switching to a [[graph database]]. Alternatively, several resolutions exist for the relational model and are available as a workaround in some [[relational database management system]]s:

Line 119:

</source>

The query will be more complicated when searching for children more than one level deep. To overcome this limitation and simplify [[tree traversal]] an additional column is added to the model to maintain the depth of a node within a tree.

{| class="wikitable sortable"

Line 172:

*[http://pear.php.net/package/DB_NestedSet PHP PEAR Implementation for Nested Sets] - by Daniel Khan

*[http://devmd.com/r/adjacency-list-to-nested-sets-mysql Transform any Adjacency List to Nested Sets using MySQL stored procedures]

{{DEFAULTSORT:Nested Set Model}}

[[Category:Database theory]]