#Glossary

Reference for nested-set jargon, acronyms, and package-specific names used throughout the docs. Entries are grouped by topic; the sidebar TOC is alphabetical within each section.

#1. Acronyms

#1.1 BFS — breadth-first search

A tree traversal that visits every node at depth d before any node at depth d + 1 — the queue-based "across, then down" walk. See Tree traversal → BFS for the visit order and the walker's BFS strategy.

#1.2 CDC — change data capture

A pattern where every row-level change in a database (insert / update / delete) is emitted as a stream of events so downstream systems can mirror state without polling. Tools like Debezium and Postgres logical replication are the canonical examples. The package's NestedSetAggregateChanged event applies the same shape to maintained aggregate columns: one event per (row, column) whose stored value moved, carrying oldValue / newValue so a consumer (Redis, Kafka, Reverb, search index) can mirror the rollup without re-querying.

#1.3 CTE — common table expression

A WITH clause that defines a named query reusable within the surrounding statement. The recursive form (WITH RECURSIVE) walks adjacency lists, which is how non-nested-set hierarchies are typically queried. This package avoids recursive CTEs entirely — every ancestor/descendant query is a single BETWEEN thanks to the nested-set encoding.

#1.4 DFS — depth-first search

A tree traversal that follows one branch all the way to a leaf before backtracking and trying the next branch. See Tree traversal → DFS for the pre-order vs post-order distinction.

#1.5 FK — foreign key

A column that references another table's primary key. parent_id is the package's only structural FK — to the same table, making the tree a self-referential one.

#1.6 N+1 queries

The anti-pattern of issuing one query for a list and then one query per row in that list — N + 1 queries total instead of one or two. The nested-set encoding makes ancestors, descendants, and siblings cheap enough that even the unbounded descendants eager-load runs in two queries regardless of the result-set size.

#1.7 ORM — object-relational mapping

A library that maps database rows to in-memory objects. Eloquent is Laravel's ORM, and the entire package is built as a thin extension on top of it.

#1.8 PDO — PHP data objects

PHP's database-abstraction layer; Laravel uses one PDO connection per configured connection. The useReadPdo() switch routes a query through the read-replica PDO when one is configured — relevant for the withFreshAggregates read path.

#1.9 PK — primary key

The unique identifier column on each row. The package accepts integer (bigIncrements) and UUID/ULID primary keys; the choice flows through to parent_id's column type via nestedSet(parentIdType: ...).

#1.10 UDF — user-defined function

A SQL function registered at the connection level. The package installs UDF BIT_OR / BIT_AND / BIT_XOR aggregates on SQLite so the same native-aggregate SQL works on every backend.

#1.11 UUID — universally unique identifier

A 128-bit identifier rendered as xxxxxxxx-xxxx-.... Supported as a primary key shape; the exporters hash UUIDs to a short prefix so Mermaid/DOT identifiers stay valid.

#2. Nested-set model

#2.1 Bounds

The (lft, rgt, depth) triple that describes a row's position in the tree. Wrapped as the immutable NodeBounds value object; obtained via $node->getBounds(). The mutation engine, exporters, and aggregate hooks all pass NodeBounds around rather than loose integers.

#2.2 Containment

The relation A.lft < B.lft AND B.rgt < A.rgt, equivalent to "B is a strict descendant of A". This single predicate, expressible as one BETWEEN, is what makes every tree-shape query in the package O(1) statements instead of recursive.

#2.3 Depth

Distance from the root, stored as a column. The root is depth = 0. Maintained on every mutation, so depth-bounded queries (where('depth', '<=', 2)) are cheap; the walker's WalkFilter::depth() uses relative depth (from the walk root) rather than the absolute column.

#2.4 Forest

A collection of independent trees in one table. An unscoped table holds one forest indexed by parent_id IS NULL roots; a scoped table holds one forest per scope value. The *Forest exporter variants render every tree in every scope.

#2.5 Gap

The 2 × N-wide slot range a subtree of N nodes occupies in the lft/rgt sequence. makeGap($at, $size) opens a fresh $size-wide hole at position $at (shifting later values up); closeGap is the inverse. See the Mutation Engine.

#2.6 Invariant

A property the engine maintains on every mutation — e.g. lft < rgt for every row, lft/rgt unique within a scope, the contiguous-permutation rule. The corruption taxonomy is the list of "an invariant got broken" categories; countErrors() detects them; fixTree() restores them by rebuilding from parent_id.

#2.7 lft and rgt

The two integer columns that encode the nested set. Assigned by a pre-order walk: as you enter a node, stamp lft; as you leave, stamp rgt. Together they form the interval that contains every descendant's interval. The column names are configurable via nestedset.columns.*.

#2.8 Orphan

A row whose parent_id is non-null but points at a missing (or different-scope) row. Detected by countErrors(); not auto-fixable by fixTree() because the right answer is domain-specific — re-parent, promote to root, or delete. See Corruption Reference → orphans.

#2.9 Pre-order numbering

The traversal that assigns lft/rgt integers: visit a node, recurse into its children left-to-right, return. The numbers come out so that each node's interval wraps every descendant's. This is also the natural read order — ORDER BY lft is depth-first display order.

#2.10 Scope

A column (or set of columns) that partitions one table into multiple independent trees. Declared via #[NestedSetScope] or getScopeAttributes(). Each scope's lft sequence restarts at 1; the mutation engine refuses cross-scope writes (ScopeViolationException). See Scoped Trees.

#2.11 Subtree

A node together with all its descendants. In SQL: WHERE lft BETWEEN node.lft AND node.rgt. In PHP: $node->descendants (strict) or $node->descendantsAndSelf (inclusive). The walker operates on subtrees in memory without any further queries.

#3. Tree traversal

#3.1 BFS

Breadth-first search — every node at depth d before any node at depth d + 1. Implemented in SubtreeWalker as a queue-based generator. Honours WalkSignal::SkipSubtree (the children of the skipped node are not enqueued). Use BFS when you need level-by-level visits (rendering a level meter, computing tree width).

#3.2 DFS

Depth-first search — drill into one subtree fully before moving to the next sibling. The walker exposes pre-order and post-order DFS strategies; both use an explicit task stack so deep trees do not blow PHP's call stack.

#3.3 Level

The set of all nodes sharing a depth value. Level 0 is the roots, level 1 the children of roots, and so on. BFS is the "visit level by level" traversal.

#3.4 Post-order

DFS that visits children before their parent. Useful for "fold up" computations: summing weights bottom-up, rendering trees where a parent's display depends on its children. WalkSignal::SkipSubtree is a no-op in post-order — the children have already fired by the time the parent visit runs.

#3.5 Pre-order

DFS that visits a node before descending into its children. The default for every walker and exporter in this package, and the order ORDER BY lft produces from SQL. This is the order humans expect when reading a tree.

#4. Mutations

#4.1 Ancestor chain

The set of ancestors of a node: WHERE lft < node.lft AND rgt > node.rgt. Every aggregate maintenance UPDATE touches exactly this set — that's why the per-mutation cost is "delta UPDATE on the ancestor chain", not "rewrite the whole subtree".

#4.2 Band (move algorithm)

The interval [boundFrom, boundTo] that contains both the moving subtree's old position and the target position during a moveNode. Only rows whose lft/rgt falls inside this band are touched; everything outside is untouched. See the band concept.

#4.3 Bystander (move algorithm)

A row inside the move's band but not part of the moving subtree — the rows the subtree slides past. Bystanders shift by ∓height (negative when the subtree moves forward, positive when backward) to fill or open the slot count the subtree vacates or needs.

#4.4 CASE WHEN UPDATE

The package's signature mutation shape: one SQL UPDATE whose SET clauses are CASE WHEN ... THEN ... ELSE ... expressions, so many rows shift in a single statement with no invariant-violating intermediate state. Used by makeGap, closeGap, moveNode, and the chunked rebuild in fixTree.

#4.5 Gap close

The mirror of "open a gap" — used after a hard delete. closeGap($at, $size) slides every lft/rgt > $at down by $size, reclaiming the deleted subtree's slot range so the 1..2N permutation stays contiguous.

#4.6 Gap open

makeGap($at, $size) shifts every lft/rgt >= $at up by $size, reserving an empty $size-wide slot range at $at. The first step of every insert and every "move into a new parent".

#4.7 Mutation

Any structural change to the tree — appendToNode, prependToNode, insertBefore, insertAfter, moveTo, makeRoot, delete, restore, forceDelete. Each goes through the package's mutation engine, so the structural shift, the row INSERT/UPDATE, and the aggregate hooks share one transaction.

#4.8 Pending operation

A PendingOperation value object set by appendToNode($parent) (and siblings) on the model. The actual SQL doesn't run until save() — the trait's saving listener dispatches the pending action.

#5. Aggregates

#5.1 Ad-hoc fresh aggregate

A correlated-subquery aggregate computed on read, with no stored column and no maintenance. Declared inline via withFreshAggregates(['alias' => Aggregate::sum(...)]). Useful for one-off reports and drift audits. See Reading Values.

#5.2 Aggregate column

A column on the model whose value is a rolled-up function (SUM/COUNT/AVG/MIN/MAX/...) of every descendant row's source. Declared with #[NestedSetAggregate] and maintained automatically on every mutation. See Aggregates Overview.

#5.3 Chain recompute

A maintenance strategy that re-derives an aggregate by re-scanning the subtree under each affected ancestor — used when no signed delta exists (MIN/MAX after a deleted extremum, BitOr/BitAnd after a delete, collection aggregates). O(depth × subtree-size) per mutation. The opposite of delta maintenance.

#5.4 Companion column

A hidden delta-maintainable column that backs a derived aggregate. AVG is stored as a __sum + __count pair plus the display column rewritten as sum / count. Allocated automatically by the nestedSetAggregate(type: ...) migration macro. See Aggregate Maintenance → Companion columns.

#5.5 Delta maintenance

The cheap path: each ancestor's stored value is updated by a signed delta in one statement (col = col ± Δ). Available for SUM, COUNT, and BitXor (the only delta-maintainable bitwise function — XOR is self-inverse). Constant work per ancestor, regardless of subtree size.

#5.6 Drift

The state where a stored aggregate column disagrees with the value freshly computed from the source. Caused by raw UPDATEs that bypass the trait, Model::unguard() writes, or time-dependent filters (a date window that slides every day). Detected by aggregateErrors(); repaired by fixAggregates(). See Drift & Limitations.

#5.7 Exclusive aggregate

An aggregate that excludes self from its own roll-up — declared with exclusive: true. A leaf reports 0; an interior node reports "every descendant, not me". Routes through chain recompute (no delta path exists), so it costs more than the default inclusive form.

#5.8 Fresh aggregate

A value computed by re-scanning the source at read time rather than reading the stored column. The single-row form is $node->freshAggregate('col'); the collection-level overlay is withFreshAggregates(). Useful for drift detection. Treat the result as read-only — saving a model hydrated via withFreshAggregates() will silently persist the fresh value over the stored one.

#5.9 Listener aggregate

An aggregate whose per-row contribution is a PHP closure rather than a source column. Declared via #[NestedSetAggregateListener] with a class implementing TreeAggregateListener::contribution(Model). SUM/COUNT/MIN/MAX/AVG are supported. See Listener Aggregates.

#5.10 Recompute maintenance

The "SELECT-then-UPDATE" path used by MIN/MAX, raw filters, and collection aggregates — recompute each affected ancestor's value via an inner subtree subquery, then write it back. See Aggregate Maintenance → Recompute maintenance.

#5.11 Source column

The plain column an SQL aggregate is rolled up over: sum: 'articles' rolls up the articles source column. The package watches the source column for change-deltas; updating it triggers ancestor maintenance.

#5.12 SQL aggregate

The default kind — an aggregate computed by SQL over a real source column, declared via #[NestedSetAggregate]. Distinct from listener and ad-hoc fresh aggregates.

#6. Repair

#6.1 Aggregate errors

The per-column drift counts returned by aggregateErrors(). Non-zero means the stored value disagrees with the freshly computed one. Repaired by fixAggregates().

#6.2 countErrors()

The structural diagnostic — runs four scoped queries (invalid_bounds, duplicate_lft, duplicate_rgt, orphans) and returns the counts. Cycles are not detected by countErrors(); see the Diagnostic SQL in the corruption reference.

#6.3 fixAggregates

Recompute every stored aggregate from the source and write back the corrections. Idempotent. See Repairing Aggregates.

#6.4 fixTree

Rebuild lft/rgt/depth from a parent_id walk, then run fixAggregates() against the repaired structure. The recovery anchor for every structural corruption category except cycles. See Tree Repair.

#6.5 Tree corruption

A state where one or more invariants are broken — typically by a write that bypassed the package. The corruption reference enumerates the categories and which are auto-recoverable.

#7. Concurrency

#7.1 Aggregate locking

The nestedset.aggregate_locking config flag ('auto' / 'always' / 'never') controlling whether the recompute path takes a FOR UPDATE lock on the ancestor chain before SELECTing. Default 'auto' is right for nearly every app; raise to 'always' if you've observed drift under non-default isolation. See Concurrency → Aggregate locking.

#7.2 Auto-transaction

The wrap that every mutation runs inside by default (config('nestedset.auto_transaction')). Makes a single save() — gap shift, INSERT/UPDATE, aggregate hooks — all-or-nothing. Laravel handles nesting via savepoints, so wrapping in your own outer transaction is safe.

#7.3 FOR UPDATE

A row-level lock taken by SELECT ... FOR UPDATE. Used by the mutation engine on parent/sibling reads to serialise concurrent appenders. PostgreSQL rejects FOR UPDATE on aggregate queries, which is why makeRoot() locks the highest-rgt row instead of max(rgt).

#7.4 Snapshot semantics

The soft-delete model: a trashed subtree freezes its rolled-up aggregates at trash-time, and every subsequent maintenance UPDATE adds WHERE deleted_at IS NULL so trashed ancestors stay frozen. Restore recomputes from live descendants rather than blindly adding back the trash-time total.

#8. Package types

#8.1 HasNestedSet

The contract that every tree model must implement. NodeTrait provides default implementations of every method, so satisfying the interface costs nothing — its job is to give static analysis (Larastan / IDE) a typed surface to resolve getLft(), getBounds(), and the column accessors against.

#8.2 NestedSetAggregate

The PHP attribute that declares an aggregate column on a model: #[NestedSetAggregate(column: 'tickets_total', sum: 'tickets')]. Repeatable. The fluent Aggregate::sum(...)->into(...) factory is the runtime/conditional alternative used from a nestedSetAggregates() method override.

#8.3 NestedSetScope

The PHP attribute that declares a model's scope (partition) column(s): #[NestedSetScope('menu_id')] or #[NestedSetScope(['tenant_id', 'menu_id'])]. See Scoped Trees.

#8.4 NodeBounds

The readonly value object wrapping (lft, rgt, depth). Exposes height(), contains() (the descendant predicate), and depthDelta(). Passed by the mutation engine, aggregate hooks, and exporters — never re-read mid-operation.

#8.5 NodeTrait

The user-facing trait every tree model uses. A composition of nine concerns (HasTreeMutation, HasTreeRelations, HasNodeInspection, HasTreeRepair, HasNestedSetAggregates, HasSoftDeleteTree, HasTreeWalk, HasBulkInsert, HasTreeExport) plus the Eloquent overrides that wire TreeQueryBuilder and TreeBaseQueryBuilder in. See Architecture.

#8.6 PendingOperation

The three-field value object recording a queued mutation: action name ('appendTo', 'prependTo', 'sibling', 'root'), the target neighbour, and a Position enum (Before / After) for sibling inserts. Set by appendToNode() and friends; dispatched on save().

#8.7 TreeAggregateListener

The interface a listener-aggregate class implements. Two methods: contribution(Model $node): int|float|null (the per-row value, null to exclude) and watchColumns(): array (which columns dirty the contribution).

#8.8 TreeExpression

A thin Expression wrapper that lets the package's composed-but-trusted SQL strings bypass Laravel's @template TValue of literal-string constraint. Used everywhere a CASE WHEN or column-to-column predicate is emitted (mutation engine, leaf scope, aggregate SQL).

#8.9 TreeQueryBuilder

The Eloquent builder subclass returned from every NodeTrait model's query(). Adds whereDescendantOf, whereAncestorOf, whereIsRoot, withDepth, defaultOrder, withFreshAggregates, and the positional/ordering helpers. See Query Engine.

#8.10 WalkContext

The readonly value object passed as the visitor's second argument. Carries depth (relative to the walk root), parent, sibling index/count, the derived isFirstSibling/isLastSibling flags, and a lazy pathToRoot(). See Walking Subtrees → The visitor signature.

#8.11 WalkFilter

A static pruning rule combining maxDepth (?int), visitable (?Closure), and includeRoot (bool). Plugs into every walker method and every exporter option object, so the same predicate prunes ASCII output, Mermaid diagrams, and JSON exports identically. See Pruning with WalkFilter.

#8.12 WalkSignal

The two-case enum (SkipSubtree, Stop) a visitor returns to steer the walk. Skip is honoured by pre-order DFS and BFS; ignored by post-order. Returning null (or nothing) continues normally.