Closure Table: Read and Validate Hierarchy Paths

A closure table stores hierarchy paths so repeated ancestor and descendant reads use ordinary joins. Each stored pair records an ancestor, a descendant and their distance. The useful read path depends on correctly maintained relationships, rather than avoiding maintenance altogether.

Define the closure table and its self-row convention

The node table holds the direct parent relationship. The path table holds every ancestor-descendant pair for this single-parent tree. Each node also has a self row at depth zero. Exclude that row deliberately when a caller wants only other descendants.

A primary key on the pair prevents duplicate pairs. It does not establish that the stored depth matches the parent edges. The example therefore rebuilds expected paths and compares the two sets. A general graph with several routes needs a different depth contract.

The code below needs SQL Server 2012 or later. Run the blocks in order in one query window. They use temporary tables, so nothing stays behind.

CREATE TABLE #Nodes(NodeId int NOT NULL PRIMARY KEY,ParentId int NULL,Label nvarchar(30));
 CREATE TABLE #Path
 (AncestorId int NOT NULL,DescendantId int NOT NULL,Depth int NOT NULL CHECK(Depth>=0),
  PRIMARY KEY(AncestorId,DescendantId));
 CREATE INDEX IX_Path_Descendant ON #Path(DescendantId,AncestorId) INCLUDE(Depth);
 INSERT #Nodes VALUES(1,NULL,N'Root'),(2,1,N'Branch A'),(3,2,N'Leaf A'),(4,1,N'Branch B');
 ;WITH Paths AS
 (SELECT NodeId AS AncestorId,NodeId AS DescendantId,0 AS Depth FROM #Nodes
  UNION ALL
  SELECT p.AncestorId,c.NodeId,p.Depth+1
  FROM Paths AS p JOIN #Nodes AS c ON c.ParentId=p.DescendantId)
 INSERT #Path SELECT AncestorId,DescendantId,Depth FROM Paths OPTION(MAXRECURSION 100);

Read descendants and ancestors without a recursive read

Filter AncestorId to retrieve descendants and join their identifiers to the node table. Filter DescendantId to retrieve ancestors. Descending depth places the root first for a breadcrumb. Include a stable identifier when ordering peers.

SELECT n.NodeId,n.Label,p.Depth
 FROM #Path AS p JOIN #Nodes AS n ON n.NodeId=p.DescendantId
 WHERE p.AncestorId=4 ORDER BY p.Depth,n.NodeId;
 SELECT n.NodeId,n.Label,p.Depth
 FROM #Path AS p JOIN #Nodes AS n ON n.NodeId=p.AncestorId
 WHERE p.DescendantId=3 ORDER BY p.Depth DESC,n.NodeId;

The primary key begins with AncestorId, supporting descendant searches. The reverse index begins with DescendantId, supporting ancestor searches. Their actual benefit depends on row counts and the selected plan. Extra indexes also add write and storage costs.

Insert the child and its paths together

A new leaf needs its own depth-zero row. It also needs a path from every ancestor of its parent, with depth increased by one. The next block runs those inserts in one transaction. Production code also needs a tested protocol for concurrent hierarchy changes.

BEGIN TRANSACTION;
 INSERT #Nodes VALUES(5,4,N'Leaf B');
 INSERT #Path VALUES(5,5,0);
 INSERT #Path SELECT AncestorId,5,Depth+1 FROM #Path WHERE DescendantId=4;
 COMMIT;

The sample starts with four nodes and eight paths. Adding Leaf B beneath Branch B creates three more paths. Its self row, Branch B path and Root path explain those additions. The sample therefore contains eleven stored paths.

Compare closure table paths in both directions

Rebuilding expected paths from the parent edges provides an integrity comparison for an already validated tree. EXCEPT finds expected rows missing from storage. The reverse comparison finds unexpected stored rows. Including Depth detects a wrong distance as well as a missing pair.

;WITH Expected AS
 (SELECT NodeId AS AncestorId,NodeId AS DescendantId,0 AS Depth FROM #Nodes
  UNION ALL
  SELECT p.AncestorId,c.NodeId,p.Depth+1
  FROM Expected AS p JOIN #Nodes AS c ON c.ParentId=p.DescendantId)
 SELECT * INTO #Expected FROM Expected OPTION(MAXRECURSION 100);
 CREATE TABLE #Diff(Direction varchar(20),AncestorId int,DescendantId int,Depth int);
 INSERT #Diff SELECT 'Missing expected',* FROM
 (SELECT * FROM #Expected EXCEPT SELECT * FROM #Path) AS d;
 INSERT #Diff SELECT 'Unexpected stored',* FROM
 (SELECT * FROM #Path EXCEPT SELECT * FROM #Expected) AS d;
 SELECT * FROM #Diff;

That first comparison returns no rows. Now the example deliberately removes one path and changes another depth, then compares again.

DELETE #Path WHERE AncestorId=1 AND DescendantId=3;
 UPDATE #Path SET Depth=99 WHERE AncestorId=1 AND DescendantId=5;
 DELETE #Diff;
 INSERT #Diff SELECT 'Missing expected',* FROM
 (SELECT * FROM #Expected EXCEPT SELECT * FROM #Path) AS d;
 INSERT #Diff SELECT 'Unexpected stored',* FROM
 (SELECT * FROM #Path EXCEPT SELECT * FROM #Expected) AS d;
 SELECT * FROM #Diff ORDER BY Direction,AncestorId,DescendantId;

The comparison reported one missing pair and both representations of the wrong-depth pair. Restoring those two paths leaves no differences. Do not point automatic repairs like this at application data without testing.

INSERT #Path SELECT * FROM #Expected WHERE AncestorId=1 AND DescendantId=3;
 UPDATE #Path SET Depth=2 WHERE AncestorId=1 AND DescendantId=5;
 DELETE #Diff;
 INSERT #Diff SELECT 'Missing expected',* FROM
 (SELECT * FROM #Expected EXCEPT SELECT * FROM #Path) AS d;
 INSERT #Diff SELECT 'Unexpected stored',* FROM
 (SELECT * FROM #Path EXCEPT SELECT * FROM #Expected) AS d;
 SELECT n.NodeId,n.Label,p.Depth
 FROM #Path AS p JOIN #Nodes AS n ON n.NodeId=p.DescendantId
 WHERE p.AncestorId=4 ORDER BY p.Depth,n.NodeId;
 SELECT n.NodeId,n.Label,p.Depth
 FROM #Path AS p JOIN #Nodes AS n ON n.NodeId=p.AncestorId
 WHERE p.DescendantId=3 ORDER BY p.Depth DESC,n.NodeId;
 SELECT (SELECT COUNT(*) FROM #Path) AS PathRows,
        (SELECT COUNT(*) FROM #Diff) AS RestoredDifferences;
 DROP TABLE #Diff,#Expected,#Path,#Nodes;

The last block runs the two read queries again, now that Leaf B exists, and then drops the temporary tables.

Budget closure table storage and structural validation

A deep chain stores many ancestor relationships, while a shallow tree stores fewer per node. Moving a subtree can change many external paths. Preserve internal subtree relationships and reject a destination inside that subtree. Those writes need an atomic, tested procedure.

Validate parent edges for missing parents and cycles before using a rebuild as an integrity reference. The recursive iteration limit can fail a bad rebuild, but it does not fully validate topology. Choose the storage model from actual read, write and move requirements.

Keep the stored paths honest, and the reads stay simple.

A closure table is not a free shortcut, it is a stored copy that must be kept honest.

Published by Pinal Dave on SQLAuthority. More of my work at pinaldave.com.