Tree structures in ASP.NET and SQL Server

Self-maintaining Trees Using Triggers

When we insert a new node, our trigger stored procedure will be automatically executed so we can calculate the depth and lineage columns - and even better, if we change the parentId field of one node, we'll be able to transparently update the depth and lineage fields of that node - and all its children.

When a row is inserted, SQL Server gives the trigger access to a read-only "inserted" table which contains the rows that have been inserted. In our case, when a row is inserted it will have incorrect entries for the depth and lineage fields. In order to provide the correct values, we want

  • the depth field to simply be the depth of its parent, plus one. If there is no parent (because parentId field is NULL or invalid), then we treat it as a root node, and simply give a depth of zero.
  • the lineage field needs to be the lineage of the parent, with the row's ID followed by '/' appended on the end. If there is no parent, then we'll need a '/' in front anyway to maintain the structure.

The trigger implementation of this is fairly straightforward. In order to update the dfTree table, we need to perform a join with the "inserted" table to match the rows we've been told have been updated to "real" rows in the actual table - SQL Server doesn't let you update the inserted table directly. We also need to perform a left outer join based on the parentId in order to try to get the information about the nodes parent - if the parent does not exist, then these columns are null. We use the ISNULL function provided by SQL Server to check whether a parameter is null, and provide a "default" option for when it is.

CREATE TRIGGER dfTree_InsertTrigger ON dfTree
FOR INSERT AS
UPDATE child
    -- set the depth of this "child" to be the
    -- depth of the parent, plus one.
    SET depth = ISNULL(parent.depth + 1,0),
    -- the lineage is simply the lineage of the parent,
    -- plus the child's ID (and appropriate '/' characters
    lineage = ISNULL(parent.lineage,'/') + LTrim(Str(child.id)) + '/'
-- we can't update the "inserted" table directly,
-- so we find the corresponding child in the
-- "real" table
FROM dfTree child INNER JOIN inserted i ON i.id=child.id
-- now, we attempt to find the parent of this
-- "child" - but it might not exist, so these
-- values may well be NULL
LEFT OUTER JOIN dfTree parent ON child.parentId=parent.id

We need to perform some similar calculations for when a row is updated - again, SQL Server gives the trigger access to an "inserted" table which this time contains the original rows.

If the parentId field has changed for one node, we need to recalculate the depth and lineage fields for this node, and all its subchildren.

  • the depth field needs to be updated to represent the new depth. The relative depth between the subchildren and the node that has changed remains the same - we simply need to take into account the depth of the new parent.
  • Similarly for the lineage field, we need to keep the portion of the lineage representing the tree below the node whose parent was changed - and update the lineage before it to that of the new parent.
CREATE TRIGGER dfTree_UpdateTrigger
ON dfTree
FOR UPDATE AS
-- if we've modified the parentId, then we
-- need to do some calculations
IF UPDATE (parentId)
UPDATE child
-- to calculate the correct depth of a node, remember that
--      - old.depth is the depth of its old parent
--      - child.depth is the original depth of the node
--          we're looking at before a parent node moved.
--          note that this is not necessarily old.depth + 1,
--          as we are looking at all depths below the modified
--          node
-- the depth of the node relative to the old parent is
-- (child.depth - old.depth), then we simply add this to the
-- depth of the new parent, plus one.
    SET depth = child.depth - old.depth + ISNULL(parent.depth + 1,0),
    lineage = ISNULL(parent.lineage,'/') + LTrim(Str(old.id)) + '/' +
                  right(child.lineage, len(child.lineage) - len(old.lineage))
-- if the parentId has been changed for some row
-- in the "inserted" table, we need to update the
-- fields in all children of that node, and the
-- node itself                 
FROM dfTree child
INNER JOIN inserted old ON child.lineage LIKE old.lineage + '%'
-- as with the insert trigger, attempt to find the parent
-- of the updated row
LEFT OUTER JOIN dfTree parent ON old.parentId=parent.id

The current implementation performs no checks for cycles in our tree (that is, that the tree contains no nodes that have a parent which is also one of its children).

You might also like...

Comments

About the author

James Crowley

James Crowley United Kingdom

James first started this website when learning Visual Basic back in 1999 whilst studying his GCSEs. The site grew steadily over the years while being run as a hobby - to a regular monthly audien...

Interested in writing for us? Find out more.

Contribute

Why not write for us? Or you could submit an event or a user group in your area. Alternatively just tell us what you think!

Our tools

We've got automatic conversion tools to convert C# to VB.NET, VB.NET to C#. Also you can compress javascript and compress css and generate sql connection strings.

“There are only 3 numbers of interest to a computer scientist: 1, 0 and infinity”