Since my first post on this topic got a lot of attention and traction, I felt it appropriate to expand on the topic a bit, even if it’s been largely covered by other bloggers in the past. I’ve also found it very useful to have a “depth” field, which isn’t canonically part of the model (hence the “++” in the title!), but is quite handy not only for display purposes (while you’re querying & testing the thing), and also for making certain “get” ops easier. Sure, it adds a wee bit more to structural maintenance, but since that’s already the most complicated part of the model anyway, it’s hardly worth a second thought. So let’s dive in!
The big topic last time was this operation of “move a subtree” — of course, sometimes you’re just moving one node, but only if it’s a leaf; otherwise you’re moving a node and all its descendants, so I’ve kept the procedure name
MoveCatSubtree intact. This time we’ll talk about good ol’ CrUD ops – Create, Update, Delete. In my implementation, I chose to handle these with table triggers. Some would argue in favor of stored-procs, and while that would seem “more consistent” with the precedent set, I’d counter with 2 points:
- To be really fool-proof, you’ll need to prevent ungoverned inserts/updates/deletes anyway; you could either do this with
GRANT/DENYpermissions, or triggers. Permissions would be more complex because you’d still need your users to be able to
execthe CrUD procs, so you’d end up using some convoluted security mechanisms that can be tricky to maintain over time.
- With triggers, we can allow the consumers of the data (apps, users) to continue to use “plain-ol’-TSQL” to access and manipulate the data, instead of having to remember stored-proc names and hunt for documentation on them. (The exception being, of course,
MoveCatSubtree, which, honestly, could be integrated into the
inserttrigger, but I’ll leave that as an exercise to the reader!)
Again, yes, we could easily do the same implementations in stored-proc form, and you’re welcome to
fork my GitHub repo if you feel like exploring that.
Let’s outline the steps and draw some pictures.
Insert: Make a hole!
INSERT a node, we want to specify its parent and a name, and let the triggers do the rest! We place it at the right of its siblings-to-be, and update the position values of all nodes to the right so that everything stays kosher. This should sound familiar — it’s essentially that “make a gap” part of the subtree-move op. In terms of depth, we just +1 to the parent’s.
Also, for some reason, our cats reproduce asexually…
Delete: Think of the children!
DELETE a node, we want to “close the gap” left by said deleted node. But what of the children? We don’t want to leave any orphans behind! So we “promote” the children of our deleted node to the level (depth) of their parent, sandwiching them in between the deleted node’s siblings (aka their former aunts/uncles!). This is easier than it sounds.
Fluffy is survived by his children, who are now for some reason his siblings, and are very confused by their sudden increase in age & status.
Update: Rename; everything else is encapsulated.
Finally, we only allow
UPDATEs on the Name, because everything else (position values, depth, parent) is structural, and encapsulated by our tree maintenance logic. Moving a node or subtree?
MoveCatSubtree. Swapping positions with another node?
Depth: Set it once, & encapsulate it!
Depth is pretty simple to add if you’ve already got a tree full of data. We can use a recursive common table expression, or “rCTE“. While normally these are frown-worthy (remember, recursion is not SQL’s strong suite), we’re only using it one time to populate an existing data-set, so we can keep on smiling.
;WITH CatTree AS ( SELECT CatID, ParentID, Name, PLeft, PRight, Depth = 0 FROM nsm.Cat WHERE ParentID IS NULL UNION ALL SELECT cat.CatID, cat.ParentID, cat.Name , cat.PLeft, cat.PRight, Depth = tree.Depth + 1 FROM CatTree tree JOIN nsm.Cat cat ON cat.ParentID = tree.CatID ) UPDATE cat SET cat.Depth = CatTree.Depth FROM CatTree JOIN nsm.Cat cat ON cat.CatID = CatTree.CatID
The last order of business (for now) is to add
Depth support to our
MoveCatSubtree method. As illustrated below, we have to move the subtree “up” or “down” in
Depth depending on its new parent’s position relative to its old position. The details are, of course, in the GitHub repo, but here’s a quick snippet of what that looks like:
NodeNewDepth = /*NodeCurrent*/Depth + (@NewParentDepth - @SubtreeOldDepth) + 1 (where
@SubtreeOldDepth is the depth of the top node of the moving subtree.)
In a future little addendum, I’ll briefly go over the “get” queries and that TDB
SwapCatNode method. For now, enjoy the cats (again)! Thanks or sticking around, I know it’s been a few more weeks than normal.
PS: A big thank-you to the dudes in the CodingBlocks #blogging Slack channel for their encouragement and motivation to get this done! You guys rock. Check out their blogs for some terrific content: http://dotnetcore.gaprogman.com/ , http://www.codeshare.co.uk/ , http://thereactionary.net/ .
I’d like to point future readers at two very informative articles for those interested in deep-diving down the hierarchical rabbit-hole: Aaron Bertrand, and Jeff Moden. There are many more tweaks and enhancements that can be made to the “classical” Nested Set model, which those lucky Devs/DBAs who are in a position to actually [re]implement their hierarchies will want to read about and take advantage of.