Joe Celko's Trees and Hierarchies in SQL for Smarties

Joe Celko's Trees and Hierarchies in SQL for Smarties

The Morgan Kaufmann Series in Data Management Systems
2004, Pages 45-99
Joe Celko's Trees and Hierarchies in SQL for Smarties

Chapter 4 - Nested Set Model of Hierarchies

https://doi.org/10.1016/B978-155860920-4/50005-2Get rights and content

Publisher Summary

Trees are often drawn as boxes-and-arrows charts that tend to fix the mental image of a tree into a graph structure. Another way of representing trees is to show them as nested sets. The chapter highlights this approach. To show a tree as nested sets, replace the boxes with ovals and then nest subordinate ovals inside their parents. Containment represents subordination. The root will be the largest oval and will contain every other node. The leaf nodes will be the innermost ovals, with nothing else inside them, and the nesting will show the hierarchical relationship. This is a natural way to model a parts explosion because a final assembly is made of physically nested assemblies that finally break down into separate parts. This approach is used to model a tree with nested sets with number pairs that always contain the pairs of their subordinates so that a child node is within the bounds of its parent. The chapter uses this approach of representation of a tree graph to present techniques to perform operations, such as finding root and leaf nodes, finding subtrees, finding levels and paths in a tree, finding the height of a tree, deleting nodes and subtrees, closing gaps in the tree, using summary functions on trees, and inserting and updating trees. The chapter also provides techniques to convert nested sets into adjacent list models, and compare nodes and structures of these models. All of these techniques are explained using simple SQL codes maintaining an organizational chart table to represent the hierarchy and people of a sample organization.

References (0)

Cited by (0)

View full text