Nested Set Model¶
Encode a tree in relational rows with nested traversal bounds so interval comparisons recover ancestry and subtrees.
Core Idea¶
A nested set model stores a rooted, single-parent tree in rows. Each node has a left number assigned when a depth-first traversal enters it and a right number assigned when the traversal leaves it. A descendant's two numbers fall strictly inside its ancestor's pair, so interval comparisons can find ancestors and subtrees.[ref-d385c998befb][ref-bf84e5d7630b]
It is a way to represent and query a tree. A hierarchy can exist without these labels. If the tree changes, its bounds must still match the intended parent relations; the amount of relabeling depends on the numbering scheme.[^ref-d385c998befb]
Scope of Application¶
The method applies to a selected single-parent hierarchy with a valid bound pair for each node. Celko's six-employee OrgChart is a worked relational example. The public GIFT_taxonomy() output documents lft and rgt fields for taxa; Novotný and Wild classify the exposed output as nested set. Those sources do not show GIFT's internal database schema or an executed GIFT interval query.[ref-d385c998befb][ref-bf84e5d7630b][^ref-8190f2d5c29f]
Clarity¶
An interval containment test finds any descendant, not necessarily an immediate child. Distinguishing direct children requires another rule, such as stored depth or the closest enclosing interval. Strict comparisons omit the subtree root; non-strict comparisons include it. A pair of ordered numbers is insufficient unless it actually preserves the chosen tree's ancestry.[^ref-bf84e5d7630b]
Manages Complexity¶
The two bounds replace a level-by-level walk for many subtree questions with ordered comparisons. This can simplify reading a hierarchy, while insertions or moves under conventional contiguous numbering can require other labels to change. Neither every read nor every write has one universal cost.[ref-d385c998befb][ref-bf84e5d7630b]
Abstract Reasoning¶
State the intended parent tree, assign paired traversal bounds, and check that an ancestor encloses each descendant but not an unrelated node. Decide whether the query includes the selected root and whether it asks for all descendants or only direct children. After an edit, compare known parent links with interval containment to detect stale labels.
Knowledge Transfer¶
Employees and taxa can both fill the node role, while reporting and classification provide parent relations. The same bound-pair invariant applies to both examples. Celko's chart is a worked model; GIFT documents a public output. The latter does not prove how the private service stores or updates its taxonomy.[ref-d385c998befb][ref-bf84e5d7630b][^ref-8190f2d5c29f]
This model is a specific Representation: the row bounds preserve selected facts about a target. It presupposes Tree Structure, because the method's ancestry claim needs a rooted unique-parent tree to encode.
Examples¶
In Celko's coherent six-node chart, Chuck has bounds (4,11). Donna (5,6), Eddie (7,8) and Fred (9,10) are inside Chuck's interval; Bert (2,3) is outside it. The rows, bounds and containment test are visible in one example. Celko also prints an inconsistent five-row insert elsewhere, which should not be combined with this complete chart.[^ref-d385c998befb]
The GIFT 1.3.2 reference describes public lft and rgt columns and says a genus's bounds lie inside its family's. The generic interval rule can be applied to those fields, but these sources do not record a GIFT-specific query execution.[ref-8190f2d5c29f][ref-bf84e5d7630b]
Relationships to Other Abstractions¶
Current abstraction Nested Set Model Domain-specific
Parents (2) — more general patterns this builds on
-
Nested Set Model is a kind of Representation Prime
A nested set model is a tree representation whose row-wise traversal bounds preserve ancestry as interval containment.
-
Nested Set Model presupposes Tree Structure Prime
The model presupposes a rooted unique-parent tree because its one-interval-per-node containment claim is defined against that tree.
Hierarchy paths (5) — routes to 5 parentless roots
- Nested Set Model → Representation → Abstraction
- Nested Set Model → Tree Structure → Hierarchy → Network
- Nested Set Model → Tree Structure → Hierarchy → Order → Comparison
- Nested Set Model → Tree Structure → Hierarchy → Order → Relation
- Nested Set Model → Tree Structure → Hierarchy → Order → Set and Membership
Neighborhood in Abstraction Space¶
Nested Set Model sits in a moderately populated region (49th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Tree (Data Structure) — 0.88
- Rope (Data Structure) — 0.86
- Trie — 0.86
- Suffix Tree — 0.86
- Perfect Phylogeny — 0.85
Computed from structural-signature embeddings · 2026-10-17
Not to Be Confused With¶
- Adjacency list: stores direct parent or neighbor links, rather than one nested interval pair per node.
- Euler tour technique: uses repeated traversal occurrences for graph algorithms; it is a different encoding.
- The tree itself: the nested set model is one representation of the chosen hierarchy.
- A multiparent graph: one interval pair for a node does not encode two simultaneous parent paths in the same tree.[^ref-bf84e5d7630b]
References¶
[^ref-d385c998befb]: Joe Celko, Joe Celko's Trees and Hierarchies in SQL for Smarties, 2nd ed., Morgan Kaufmann/Elsevier, 2012, ISBN 978-0-12-387733-8, Chapter 4 printed pp. 49–54 and 83–84, §4.12 printed p. 105, Chapter 5 printed pp. 111–124. Full original author book facsimile at an academic repository: https://digilib.stiestekom.ac.id/assets/dokumen/ebook/feb_B8qAP97hWgUpipqdyUbP5LyV7949c7RfhzGg8TiCmAjSqd4H-nLdQJs_1680769184.pdf . The consulted facsimile is the second edition; its page-50 five-row SQL conflicts with Figure 4.1 and the complete §4.12 case. [^ref-bf84e5d7630b]: Petr Novotný and Jan Wild, “The relational modeling of hierarchical data in biodiversity databases,” Database 2024, baae107, https://doi.org/10.1093/database/baae107 . Full original publisher article: https://academic.oup.com/database/article/doi/10.1093/database/baae107/7817843 . Figure 2, Tables 1–3, Discussion and Limits. The authors inspected public materials from outside providers; their classification does not verify internal schemas. [^ref-8190f2d5c29f]: GIFT package, “GIFT 1.3.2 GIFT_taxonomy: Taxonomy of GIFT,” reference manual for package version 1.3.2, Details and Value, https://search.r-project.org/CRAN/refmans/GIFT/html/GIFT_taxonomy.html . Official package documentation of public output fields; not evidence of internal storage or an executed query.