Content deleted Content added
m →See also: add calkin-wilf |
m →Motivation: + wikilink |
||
| (4 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Technique used in relational databases}}
The '''nested set model''' is a 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 — 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.
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:
| |||