Library tutorials & articles
Tree structures in ASP.NET and SQL Server
- Introduction
- Storing Trees in SQL Server
- Self-maintaining Trees Using Triggers
- Basic Operations over Trees in SQL Server
- Displaying our Nodes
- Displaying Breadcrumbs
- Previewing Sub-levels
- Populating the TreeNode Children
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
depthfield to simply be the depth of its parent, plus one. If there is no parent (becauseparentIdfield isNULLor invalid), then we treat it as a root node, and simply give a depth of zero. - the
lineagefield 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
depthfield 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
lineagefield, 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).
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 audience ...
Related articles
Related discussion
-
High-Performance .NET Application Development & Architecture
by Manjot Bawa (0 replies)
-
Help me please to know about compression method for .wacv files
by rajitharavindran (0 replies)
-
Need help for web application
by bnitinn (1 replies)
-
how to show the extra data fields due to joins , using typed dataset
by BelaPatil (0 replies)
-
How to check there is a particular record in database or not
by kausar4u (2 replies)
Related podcasts
-
ADO.NET "Astoria" Data Services with Shawn Wildermuth
Scott chats with Shawn Wildermuth, "the ADO Guy," about ADO.NET Data Services, aka "Project Astoria." It's REST for SQL Server. Should you care? What's REST? How does this relate to WCF or ASP.NET?
Events coming up
-
Nov
19
SQLBits V
Newport, United Kingdom
SQLBits is Europe's largest SQL Server conference, and SQLBits V will be the biggest and best yet. On November 19th we are holding a day of pre-conference seminars; on November 20th we have a pay-to-attend day of SQL Server 2008 and R2 content; and on Saturday November 21st we have our usual free community conference.
i think this is missing SP:
hey guys nice article. i have problem adn i think you forgot one Sp: Could not find stored procedure 'dfTreeGetNode'
any help?
Hi James,
I have read your article in developer fusion about Tree structures in asp.net and sql server and I have successfully implemented into some diffuicult task.So,thank you about it...
However,I would like to ask what are the words child,old and parent and how Sql server knows about them?
Thanks in advance,
Kostis.
add this methods to the TreeNode class
public string GetXml
{
get
{
XmlDocument xDoc = new XmlDocument();
XmlElement root = (XmlElement) xDoc.AppendChild(xDoc.CreateElement("node"));
root.SetAttribute("id", this.UniqueID.ToString());
root.SetAttribute("name", this.Name);
foreach (TreeNode tn in this.Children)
{
AppendChildren(root, tn);
}
return xDoc.OuterXml;
}
}
private void AppendChildren(XmlElement root, TreeNode tn)
{
XmlElement node = (XmlElement)root.AppendChild(root.OwnerDocument.CreateElement("node"));
node.SetAttribute("id", tn.UniqueID.ToString());
node.SetAttribute("name", tn.Name);
foreach (TreeNode child in tn.Children)
{
AppendChildren(node, child);
}
}
the xml has all the info i need for the tree control, feel free to change it to your needs
hope this helps
Thanks this article has been a great help, I have one question.
How hard would it be to get the tree from SQL in XML so that you could use ASP.net 2 tree control?
Regards Geraint
There are many ways to represent a tree or hierarchy in SQL. This is called an adjacency list model and it looks like this:
CREATE TABLE OrgChart
(emp CHAR(10) NOT NULL PRIMARY KEY,
boss CHAR(10) DEFAULT NULL REFERENCES OrgChart(emp),
salary DECIMAL(6,2) NOT NULL DEFAULT 100.00);
OrgChart
emp boss salary
===========================
'Albert' NULL 1000.00
'Bert' 'Albert' 900.00
'Chuck' 'Albert' 900.00
'Donna' 'Chuck' 800.00
'Eddie' 'Chuck' 700.00
'Fred' 'Chuck' 600.00
Another way of representing trees is to show them as nested sets.
Since SQL is a set oriented language, this is a better model than the usual adjacency list approach you see in most text books. Let us define a simple OrgChart table like this.
CREATE TABLE OrgChart
(emp CHAR(10) NOT NULL PRIMARY KEY,
lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
CONSTRAINT order_okay CHECK (lft < rgt) );
OrgChart
emp lft rgt
======================
'Albert' 1 12
'Bert' 2 3
'Chuck' 4 11
'Donna' 5 6
'Eddie' 7 8
'Fred' 9 10
The organizational chart would look like this as a directed graph:
Albert (1, 12)
/ \
/ \
Bert (2, 3) Chuck (4, 11)
/ | \
/ | \
/ | \
/ | \
Donna (5, 6) Eddie (7, 8) Fred (9, 10)
The adjacency list table is denormalized in several ways. We are modeling both the Personnel and the organizational chart in one table. But for the sake of saving space, pretend that the names are job titles and that we have another table which describes the Personnel that hold those positions.
Another problem with the adjacency list model is that the boss and employee columns are the same kind of thing (i.e. names of personnel), and therefore should be shown in only one column in a normalized table. To prove that this is not normalized, assume that "Chuck" changes his name to "Charles"; you have to change his name in both columns and several places. The defining characteristic of a normalized table is that you have one fact, one place, one time.
The final problem is that the adjacency list model does not model subordination. Authority flows downhill in a hierarchy, but If I fire Chuck, I disconnect all of his subordinates from Albert. There are situations (i.e. water pipes) where this is true, but that is not the expected situation in this case.
To show a tree as nested sets, replace the nodes with ovals, and then nest subordinate ovals inside each other. The root will be the largest oval and will contain every other node. The leaf nodes will be the innermost ovals with nothing else inside them and the nesting will show the hierarchical relationship. The (lft, rgt) columns (I cannot use the reserved words LEFT and RIGHT in SQL) are what show the nesting. This is like XML, HTML or parentheses.
At this point, the boss column is both redundant and denormalized, so it can be dropped. Also, note that the tree structure can be kept in one table and all the information about a node can be put in a second table and they can be joined on employee number for queries.
To convert the graph into a nested sets model think of a little worm crawling along the tree. The worm starts at the top, the root, makes a complete trip around the tree. When he comes to a node, he puts a number in the cell on the side that he is visiting and increments his counter. Each node will get two numbers, one of the right side and one for the left. Computer Science majors will recognize this as a modified preorder tree traversal algorithm. Finally, drop the unneeded OrgChart.boss column which used to represent the edges of a graph.
This has some predictable results that we can use for building queries. The root is always (left = 1, right = 2 * (SELECT COUNT(*) FROM TreeTable)); leaf nodes always have (left + 1 = right); subtrees are defined by the BETWEEN predicate; etc. Here are two common queries which can be used to build others:
1. An employee and all their Supervisors, no matter how deep the tree.
SELECT O2.*
FROM OrgChart AS O1, OrgChart AS O2
WHERE O1.lft BETWEEN O2.lft AND O2.rgt
AND O1.emp = :myemployee;
2. The employee and all their subordinates. There is a nice symmetry here.
SELECT O1.*
FROM OrgChart AS O1, OrgChart AS O2
WHERE O1.lft BETWEEN O2.lft AND O2.rgt
AND O2.emp = :myemployee;
3. Add a GROUP BY and aggregate functions to these basic queries and you have hierarchical reports. For example, the total salaries which each employee controls:
SELECT O2.emp, SUM(S1.salary)
FROM OrgChart AS O1, OrgChart AS O2,
Salaries AS S1
WHERE O1.lft BETWEEN O2.lft AND O2.rgt
AND O1.emp = S1.emp
GROUP BY O2.emp;
4. To find the level of each emp, so you can print the tree as an indented listing. Technically, you should declare a cursor to go with the ORDER BY clause.
SELECT COUNT(O2.emp) AS indentation, O1.emp
FROM OrgChart AS O1, OrgChart AS O2
WHERE O1.lft BETWEEN O2.lft AND O2.rgt
GROUP BY O1.lft, O1.emp
ORDER BY O1.lft;
5. The nested set model has an implied ordering of siblings which the adjacency list model does not. To insert a new node, G1, under part G. We can insert one node at a time like this:
BEGIN ATOMIC
DECLARE rightmost_spread INTEGER;
SET rightmost_spread -- can be put into the UPDATE
= (SELECT rgt
FROM Frammis
WHERE part = 'G');
UPDATE Frammis
SET lft = CASE WHEN lft > rightmost_spread
THEN lft + 2
ELSE lft END,
rgt = CASE WHEN rgt >= rightmost_spread
THEN rgt + 2
ELSE rgt END
WHERE rgt >= rightmost_spread;
INSERT INTO Frammis (part, lft, rgt)
VALUES ('G1', rightmost_spread, (rightmost_spread + 1));
COMMIT WORK;
END;
The idea is to spread the (lft, rgt) numbers after the youngest child of the parent, G in this case, over by two to make room for the new addition, G1. This procedure will add the new
I know that you're a very well respected author on this area, and I'm still *very* new to this, but I had difficulty with the fact that it was so relatively "hard" to work out things like who a nodes parent is, and what its depth/level was with your solutions.... am I missing something obvious here? Thanks for your time!
Hasn't anyone read a copy of TREES & HIERARCHIES IN SQL? There are sooo many better ways of doing this without any proprietary code.
Why was my post about making the database and code more efficient removed?
good article but wanted to know which of the two ways are more optimized
using xml or the example you have given
''''''''''''''''''''''''''
CREATE PROCEDURE dfTreeGetSubChildren ( @id INT, @depth INT ) AS
SELECT t.* FROM dfTree AS children INNER JOIN dfTree AS actualNode
ON children.lineage LIKE actualNode.lineage + '_%'
WHERE actualNode.id = @id
ORDER BY children.lineage, children.name
'''''''''''''''''''''''''
Since this do order by children.lineage, children.name, and the children.lineage is unique, the children.name order will not run.
Is there a way to overcome this? Example, sort by the start of lineage except the last id /1/3/5 --> /1/3 this way we could sort by this field, cobined with name. But I do not know how to overcome this with T-SQL.
I would appreciate if anyone could help me.
Rgs
Vidar
It's very performant. Feel free to try it with a 10000 node, 10 level deep tree. Works fine.
I'm not sure this is actually much better performance wise...
Yes, the method I suggest requires some overhead when adding to the tree - but SELECTing from the tree is fast. Looking at the recursive function there, with multiple SELECT and DELETE statements... just to retrieve the tree, doesn't look especially nice to me when compared to
SELECT t.* FROM dfTree t ORDER BY t.lineage
...
James:
That was good reading!
Good Job!
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/acdata/ac_8_qd_14_5yk3.asp
No triggers needs, no column needed to track depth...
The problem is fixed. Change the line in the UPDATE trigger that reads
INNER JOIN deleted old ON child.lineage LIKE old.lineage + '%'
to
INNER JOIN inserted old ON child.lineage LIKE old.lineage + '%'
I've updated the download.
Strange. I'll look into that and let you know....
Hello again,
I was playing around with the updating trigger and I uncovered another little problem.
It seems that I need to run the UPDATE statement twice in order to get the trigger to execute properly and update the depth and lineage columns.
I have been playing around with the trigger to see if I could correct this, but haven't come up wiht anything yet.
I guess its not a big deal as it isnt that hard to just run the statement twice, but do you have any ideas on how to get it working in a single pass?
Thanks,
Max
huh... isn't that interesting. Firefox WAS caching the zip I guess. Who knows... but I fired up Internet Explorer and I got the proper version. Thanks for the fixes, everything worked straight off when I fired it up this time. ;-)
I do have a question though. In the original version of the zip file, you used the computed columns. Intuitively it makes sense to not have to comput this each time we touch a row in the DB (as you say in the article), but have you done any tests (or heard anything back from anyone) as to the performance gain by calculating this via the triggers as opposed to the computed column approach.
I'm just interested in any different thinking on the idea. Like I said before I've never really worked with computed columns before and while they don't really strike me as a good idea in general. better to do somehting once the first time, rather than recomputer on each access. I was wondering if you might know of any circumstances where computed columns would be the best approach (besides the obvious storage space considerations).
Again, great article. I have done a bunch of different projects with hierarchies like this, and this article has a lot of good ideas for dealing with this kind of data.
Thanks,
Max
Hi - these problems have been fixed in the new ZIP file I uploaded. Are you sure your browser is not caching the old ZIP file?
Hi, I still have all the same problems with the sample code.
TREEDEMOA:
There is a missing Button for "CreateNodes" on the skin for TreeDemoA.
TREEDEMOD:
Get SQL error for unknown "id" parameter on execution of an SPROC.
I looked into this and the problem is in SqlServerTreeProvider.cs
There are a bunch of places where the SQL Params do not have the @ before the parameter names. so the "id" should be "@id"
After fixing these too, I can get TreeDemoD to run.
SQL SCRIPT:
I get the following error on the execution:
Server: Msg 271, Level 16, State 1, Procedure dfTree_UpdateTrigger, Line 10
Column 'depth' cannot be modified because it is a computed column.
It is not creating the UpdateTrigger. The problem here is that the Computed Column seems to be a late addition to the design and the code that originally updated the "depth" column in the UpdateTrigger has not been removed from the UpdateTrigger (corresponding code WAS removed from the InsertTrigger)
Also, there is a reference in the file to the SPROC dfTreeGetValidParents, but that SPROC is not included in the SQL Script
public ArrayList GetValidParents(int rootID, int uniqueID)
{
return ProcessList("dfTreeGetValidParents",
new SqlParameter("@rootId",rootID),
new SqlParameter("@id",uniqueID));
}
If you could update the Zip package with these changes it be most helpful for others trying the download.
Again, very interesting article, and now I'm going to dive in and see how I can use the ideas and techniques in my projects. javascript:smilie('
smile
Thanks,
Max
Hey,
Apologies! Thanks for pointing that out - I think I've fixed the sample download now - if you could try downloading it again, and let me know how it goes, that would be great
Cheers,
~ James
Hi, very interesting article.
I have run into a number of problems wiht the sample source code though.
1. The SQL Statement will not fully execute. I get the following error:
Server: Msg 271, Level 16, State 1, Procedure dfTree_UpdateTrigger, Line 10
Column 'depth' cannot be modified because it is a computed column.
2. The createNodes button was not on the page for TreeDemoA.
3. when I try to run TreeDemoD I get the following error:
id is not a parameter for procedure dfTreeGetTree.
I don't know if this is due to the SQL statement failing or what.
Any advice on getting the code running properly would be much appreciated.
Thanks,
Max
First of all, great article. I agree with it and would like your feedback in regards to simplifying your approach on the node levels. You use the 'lineage' varchar field to track where a node is in regards to order and depth. Considering you have already created a depth field, and you have a unique node (somewhere in the structure), you have 2 out of the 3 pieces that you need to know where the node is. You are simply missing the placement of the node at its depth. So, why wouldn't you use an int field named NodeOrder instead of the lineage field? This would help the doubling of data, and would be easier to maintain. There are many similar fields in other databases that you could rob code from. Just look for databases that use the 'sortorder' field. By using a sort order index, you can fetch for a particular node, know its unique id, parent id, its depth and at what placement the node will sit. and furthermore, you will know this for each node you retrieve in your select, which will in effect, create the /1/2/6/ . The slash being the depth, and the number being the position and the unique id is in behind the postition number.... in other words (/position(unique_id)/)
What do you think of this?
Regards,
Jay
This thread is for discussions of Tree structures in ASP.NET and SQL Server.