Nested set model: Difference between revisions

Revision as of 15:07, 7 December 2017

Revision as of 02:01, 3 February 2018

Line 5:

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

Line 88:

The use case for a dynamic endless database tree hierarchy is rare. The Nested Set model is appropriate where the tree element and one or two attributes are the only data, but is a poor choice when more complex relational data exists for the elements in the tree. Given an arbitrary starting depth for a category of 'Vehicles' and a child of 'Cars' with a child of 'Mercedes', a foreign key table relationship must be established unless the tree table is naively non-normalized. Attributes of a newly created tree item may not share all attributes with a parent, child or even a sibling. If a foreign key table is established for a table of 'Plants' attributes, no integrity is given to the child attribute data of 'Trees' and its child 'Oak'. Therefore, in each case of an item inserted into the tree, a foreign key table of the item's attributes must be created for all but the most trivial of use cases.

If the tree isn't expected to change often, a properly normalized hierarchy of attribute tables can be created in the initial design of a system, leading to simpler, more portable SQL statements; specifically ones that don't require an arbitrary number of runtime, programmatically created or deleted tables for changes to the tree. For more complex systems, hierarchy can be developed through relational models rather than an implicit numeric tree structure. Depth of an item is simply another attribute rather than the basis for an entire DB architecture. As stated in ''SQL Antipatterns'':<ref>{{cite book|last1=Bill|first1=Kerwin|title=SQL Antipatterns|date=2010-06-17|pages=328|url=https://pragprog.com/book/bksqla/sql-antipatterns}}</ref>

<blockquote>Nested Sets is a clever solution – maybe too clever. It also fails to support referential integrity. It’s best used when you need to query a tree more frequently than you need to modify the tree.<ref>{{cite book|last1=Bill|first1=Kerwin|title=SQL Antipatterns|page=44}}</ref></blockquote>