Nested set model: Difference between revisions

Revision as of 20:45, 3 July 2019

Latest revision as of 12:00, 27 July 2024

(16 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Technique used in relational databases}}

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

It is based on Nested Intervals, that "are immune to hierarchy reorganization problem, and allow answering ancestor path hierarchical queries algorithmically &mdash; without accessing the stored hierarchy relation".<ref>"Nested Intervals Tree Encoding in SQL", Vadim Tropashko; Oracle Corp. Original at https://web.archive.org/web/20111119165033/http://sigmod.org/publications/sigmod-record/0506/p47-article-tropashko.pdf</ref>

==Motivation==

The standard [[relational algebra]] and [[relational calculus]], and the [[SQL]] operations based on them, are unable to express directly all desirable operations on hierarchies. The nested set model is a solution to that problem.

An alternative solution is the expression of the hierarchy as a parent-child relation. [[Joe Celko]] called this the [[adjacency list model]]. If the hierarchy can have arbitrary depth, the adjacency list model 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 algebra)#Joins and join-like 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 15 ⟶ 18:

When these solutions are not available or not feasible, another approach must be taken.

==The techniqueTechnique==

The nested set model is to number the nodes according to a [https://www.techiedelight.com/arrival-departure-time-vertices-dfs/[tree traversal (DFS arrival and departure of vertices)] ], which visits each node twice, assigning numbers in the order of visiting, and at both visits. This leaves two numbers for each node, which are stored as two attributes. Querying becomes inexpensive: hierarchy membership can be tested by comparing these numbers. Updating requires renumbering and is therefore expensive. Refinements that use [[rational number]]s instead of integers can avoid renumbering, and so are faster to update, although much more complicated.<ref>{{cite arXiv |eprint=0806.3115 | first= Daniel|last = Hazel | title = Using rational numbers to key nested sets| year= 2008| class= cs.DB}}</ref>

==Example==

In a clothing store catalog, clothing may be categorisedcategorized according to the hierarchy given on the left:

[[File:NestedSetModel.svg|thumb|400px|A hierarchy: types of clothing]]

Line 54 ⟶ 57:

==Performance==

Queries using nested sets can be expected to be faster than queries using a [[stored procedure]] to traverse an adjacency list, and so are the faster option for databases which lack native recursive query constructs, such as [[MySQL]] 5.x.<ref>{{Citation

| title= Adjacency list vs. nested sets: MySQL

| author= Quassnoi

Line 82 ⟶ 85:

| url = http://explainextended.com/2009/09/25/adjacency-list-vs-nested-sets-sql-server/

| accessdate = 11 December 2010

}}</ref> [[MySQL]] used to lack recursive query constructs but added such features in version 8.<ref>{{Cite web|title=MySQL :: MySQL 8.0 Reference Manual :: 13.2.15 WITH (Common Table Expressions)|url=https://dev.mysql.com/doc/refman/8.0/en/with.html|access-date=2021-09-01|website=dev.mysql.com}}</ref>

}}</ref>

==Drawbacks==

Line 100 ⟶ 103:

Using the nested set model as described above has some performance limitations during certain tree traversal operations. For example, trying to find the immediate child nodes given a parent node requires pruning the subtree to a specific level as in the following [[SQL]] code example:

<sourcesyntaxhighlight lang="sql">

SELECT Child.Node, Child.Left, Child.Right

FROM Tree as Parent, Tree as Child

Line 110 ⟶ 113:

WHERE Mid.Left BETWEEN Parent.Left AND Parent.Right

AND Child.Left BETWEEN Mid.Left AND Mid.Right

AND Mid.Node NOT IN (Parent.Node AND, Child.Node)

)

AND Parent.Left = 1 -- Given Parent Node Left Index

</syntaxhighlight>

</source>

Or, equivalently:

<sourcesyntaxhighlight lang="sql">

SELECT DISTINCT Child.Node, Child.Left, Child.Right

FROM Tree as Child, Tree as Parent

Line 121 ⟶ 124:

GROUP BY Child.Node, Child.Left, Child.Right

HAVING max(Parent.Left) = 1 -- Subset for those with the given Parent Node as the nearest ancestor

</syntaxhighlight>

</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.

Line 154 ⟶ 157:

In this model, finding the immediate children given a parent node can be accomplished with the following [[SQL]] code:

<sourcesyntaxhighlight lang="sql">

SELECT Child.Node, Child.Left, Child.Right

FROM Tree as Child, Tree as Parent

Line 161 ⟶ 164:

AND Child.Left > Parent.Left

AND Child.Right < Parent.Right

AND Parent.LeftDepth = 1 -- Given Parent Node Left Index

</syntaxhighlight>

</source>

==See also==

* [[TreeAdjacency traversallist]]

* [[Calkin–Wilf tree]]

*[[Tree (data structure)]]

* [[Tree traversal]]

* [[Tree (data structure)]]

==References==