Nested set model: Difference between revisions

Revision as of 21:43, 23 September 2017

Revision as of 15:07, 7 December 2017

Line 3:

==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 directly all desirable operations on hierarchies directly. The Anested hierarchy can be expressed in terms of a parent-child relation – Celko calls this the [[adjacency listset 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 somewherea in the subhierarchy of another element. When the hierarchy is of fixed or bounded depth, the operations are possible, but expensive, duesolution 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]]that problem.{{citation needed|date=November 2011}}

An alternative solution is the expression of the hierarchy as a parent-child relation. Celko called this the [[adjacency list model|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:

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:

* support for a dedicated [[hierarchy data type]], such as in SQL's [[hierarchical query]] facility;