Library tutorials & articles
Tree structures in ASP.NET and SQL Server
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 ...
Storing Trees in SQL Server
In order to store our data structure in SQL Server, we're obviously going to need similar properties to that of the TreeNode object. We'll call the table dfTree, and add the fields shown in the diagram below. In addition, the id field's Identity property is also set.
Each row in this table represents a TreeNode object. We use the parentId field to indicate the parent node as the ParentID property does in our TreeNode class - but this will either be NULL (indicating we are at the root of the tree), or be the id of another node in the tree which is our parent.
Ignoring the additional depth and lineage fields for now, it's clearly straightforward to fetch - say a node and all its direct children through a simple LEFT JOIN: (note we need the left join to ensure we get the parent back too)
SELECT p.name AS parentName, c.id AS childId, c.name AS childName FROM dfTree p LEFT JOIN dfTree c ON p.id=c.parentId WHERE p.id=@NODEID
Which could return something like this:
| parentName | childId | childName |
|---|---|---|
| NULL | 1 | ParentNode |
| ParentNode | 2 | ChildA |
| ParentNode | 3 | ChildB |
However, what happens if we want to include all the children of ChildA and ChildB in the resultset too? The number of joins required increase linearly with the depth we want to go to for fetching children. Plus there's no easy way to, say, fetch all subchildren of a node, without caring what their depth is - that would require what would effectively be an infinite inner join. We obviously need another way to select nodes in the tree based on something other than (or in addition to) the parentId field. This is where the depth and lineage fields come in. The depth field represents the number of nodes between the root of the tree, and ourselves (the root has depth 0). The lineage field contains a list of ID's of nodes that we pass through in order to get from the root to the current node, delimited by a '/' character.
So, in order to have a tree like this:
Our table would look something like this:
| id | parentId | name | depth | lineage |
|---|---|---|---|---|
| 1 | NULL | Root Node | 0 | /1/ |
| 2 | 1 | Child A | 1 | /1/2/ |
| 3 | 1 | Child B | 1 | /1/3/ |
| 4 | 1 | Child C | 1 | /1/4/ |
| 5 | 2 | Child D | 2 | /1/2/5/ |
These two fields now make it much easier to fetch specific sets of nodes based on where they are in the tree. For example, all children of the node labelled "Child A" will have a lineage field that starts with "/1/2/". No more inner joins, and a much more elegant way to fetch rows. There is a downside though - although manually entering the depth and lineage fields is straightforward for such a small tree, what happens when we have 100 nodes in the tree? Or we decide we want to move one portion of the tree to somewhere elsewhere in its structure? Suddenly this becomes a much more daunting task!
Fortunately, this isn't a major obstacle - because with a bit of work we can get SQL Server to automatically maintain these fields for us. We essentially have three options here:
- Use a "computed column" so that the depth and lineage are calculated on-the-fly whenever we query the table. For both columns, this would then be a simple matter of defining two functions in SQL Server. One of which would perform a join with the rows parent, and added one to its depth. The other would perform a join with the rows parent, and add its own id plus '/' to the lineage column.
- Alternatively, store these values in two "real" columns, and use another SQL Server feature known as triggers to recalculate these whenever a row is modified. If you haven't come across triggers before, they are essentially stored procedures that are automatically executed when rows in a table are modified as a result of an
UPDATE,INSERTorDELETEquery. - Some combination of the two
I've chosen to implement this with triggers here, on the assumption that we're going to be using SELECT far more than either UPDATE and INSERT - so we don't particularly want to recompute the values each time we perform a query - and we can afford to waste some space storing these two additional columns. This is based solely on my somewhat limited knowledge as to how SQL Server works - so if you know a good reason why I should be using a different method, then please do drop me a line!
Related articles
Related discussion
-
How to check there is a particular record in database or not
by kausar4u (2 replies)
-
Insert_Update Stored Procedure and returning Identity
by ansari.wajid (0 replies)
-
Store files in Sql Server DB
by TimL (5 replies)
-
avoiding 1/1/1900 in SQL SERVER?
by karan_21584 (1 replies)
-
Eliminating "1/1/1900" in datetime fields....
by karan_21584 (8 replies)
Related podcasts
-
Stack Overflow: Podcast #28
This is the twenty-eighth episode of the StackOverflow podcast, where Joel and Jeff discuss Windows Azure, SQL Server 2008 full text search, Bayesian filtering, porn detection, and project management — among other things. Jeff met the inestimable Joey DeVilla aka Accordion Guy...
Related jobs
-
Microsoft .Net Architect
in AMSTERDAM (€50K-€90K per annum) -
Microsoft Dynamics CRM Technical Consultant
in Netherlands (€50K-€90K per annum) -
.net developer
in Rijswijk (€2K-€4K per annum)
Events coming up
-
Mar
23
DevWeek 2009
London, United Kingdom
DevWeek is Europe’s leading independent conference for software developers, database professionals and IT architects, and features expert speakers on a wide range of topics, including .NET Framework 4.0, Silverlight 2, WCF 4.0, Visual Studio 2010, RESTful services, Windows Workflow, ASP.NET AJAX 4.0, SQL Server 2008, LINQ, C# 3, .NET Patterns, Ruby, and more.
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.
Here is how id did it to use with asp:tree:
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
Here is my standard "cut & paste" on the Nested sets model for hierarchies.
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 rightmostspread -- can be put into the UPDATE
= (SELECT rgt
FROM Frammis
WHERE part = 'G');
UPDATE Frammis
SET lft = CASE WHEN lft > rightmostspread
THEN lft + 2
ELSE lft END,
rgt = CASE WHEN rgt >= rightmostspread
THEN rgt + 2
ELSE rgt END
WHERE rgt >= rightmostspread;
INSERT INTO Frammis (part, lft, rgt)
VALUES ('G1', rightmostspread, (rightmostspread + 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
Okay, point taken ... but as far as I'm aware if you moved the code I talk about out of triggers just into stored procs (or whatever), then the SQL is pretty standard stuff?
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!
Yoiu can do your heirarchies & trees in pure declarative SQL without using any proprieary 4GL like PL/SQL, T-SQL, etc.
Unless I've misunderstood you... the point of the lineage field was not to soley indicate its parent, but the entire path up the tree, so we could easily perform queries against this... i'm not sure how easy the same queries would be to perform using the method you describe?
It's still there - you just need to change the drop down on the right hand side to extend the range of old posts that are displayed.
Hi Joe - thanks for posting! What do you mean by "proprietary" code exactly? I know this isn't the same method that you recommend (which I actually didn't come across until after I wrote this article)... but it's all still just SQL stuff....
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
HI. Is there a way to sort the Hierarchies? You used something like this:
''''''''''''''''''''''''''
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!
A much better way of doing this is to use a stack:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/acdata/ac8qd145yk3.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.