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 ...
- 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
Basic Operations over Trees in SQL Server
Now that we've got a self-maintaining structure in SQL Server for storing our tree structure, we can start creating our SQL Server/C# implementation. I'm going to be lazy and simply set the connection string as a constant in our class - but you can easily choose to load it from a configuration file or whatever suits you.
public class SqlServerTreeProvider
{
const string connectionString = "server=localhost;uid=someUser;pwd=somePassword;database=dfTreeDemo";
...
}
To start with, we're going to get the boring stuff out of the way - adding, updating and deleting nodes.
Adding nodes
In order to add a node, we simply insert a new row into the table, specifying the values of the name and parentId columns. The insert trigger we specified earlier will automatically calculate values for the depth and lineage fields.
CREATE PROCEDURE dfTreeAddNode
(
@name VARCHAR(50),
@parentId INT
)
AS
IF @parentId=0 SET @parentId=NULL
INSERT INTO dfTree (name,parentId) VALUES (@name,@parentId)
RETURN scope_identity()
Note that our stored procedure uses the scope_identity() function in order to return the identifier of the row we create. (If you're used to using @@identity in these situations - you should probably be using scope_identity instead - take a look here.)
In our SqlServerTreeProvider class, we just need some simple plumbing to expose this operation:
public int AddNode(TreeNode treeNode)
{
// automatically dispose of the SqlConnection object
// when we're done
using (SqlConnection sqlConn = new SqlConnection(connectionString) )
{
// execute the dfTreeAddNode procedure
SqlCommand sqlComm = new SqlCommand("dfTreeAddNode",sqlConn);
sqlComm.CommandType = CommandType.StoredProcedure;
sqlComm.Parameters.Add("@name",SqlDbType.VarChar,50).Value = treeNode.Name;
sqlComm.Parameters.Add("@parentId",SqlDbType.Int).Value = treeNode.ParentID;
sqlComm.Parameters.Add("@RETURN_VALUE", SqlDbType.Int).Direction = ParameterDirection.ReturnValue;
sqlConn.Open();
sqlComm.ExecuteNonQuery();
return (int)sqlComm.Parameters["@RETURN_VALUE"].Value;
}
}
Note that we take the returned value from the stored procedure in order to populate the UniqueID field of the TreeNode object we were passed.
Updating nodes
Updating nodes are equally simple, and again our triggers will automatically adjust the lineage and depth fields if the parentId column has changed.
CREATE PROCEDURE dfTreeUpdateNode
(
@id INT,
@name VARCHAR(50),
@parentId INT
)
AS
UPDATE dfTree SET name=@name,parentId=@parentId WHERE id=@id
And again, a very straightforward implementation for our provider class.
public void UpdateNode(TreeNode treeNode)
{
using (SqlConnection sqlConn = new SqlConnection(connectionString) )
{
// execute the dfTreeUpdateNode stored procedure
SqlCommand sqlComm = new SqlCommand("dfTreeUpdateNode",sqlConn);
sqlComm.CommandType = CommandType.StoredProcedure;
sqlComm.Parameters.Add("@id",SqlDbType.Int).Value = treeNode.UniqueID;
sqlComm.Parameters.Add("@parentId",SqlDbType.Int).Value = treeNode.ParentID;
sqlComm.Parameters.Add("@name",SqlDbType.VarChar,20).Value = treeNode.Name;
sqlConn.Open();
sqlComm.ExecuteNonQuery();
}
}
Deleting nodes
Our implementation of removing nodes from the tree gives us the first hint of how we might use the lineage field to perform operations over the tree in our table. When we delete a node, we also want to remove all subchildren, otherwise we'll end up creating orphan nodes (which have no valid parents). These subchildren include not only direct children of the node we are deleting, but children of its children, and so on.
As you'll remember, the lineage field contains the id's of the nodes in the path from the root node to whichever node we're looking at, delimited by '/'. As an example, say we want to remove a node with id 5, which has a lineage field set to "/1/2/5/". Any children of this node will have a lineage field that starts with that string. Therefore, in order to delete the node along with all its children, all we need to do is remove all rows from the table that have a lineage field starting with "/1/2/5/". In order to do this, we can use the LIKE operator, which allows us to specify the % wildcard character which matches zero or more characters:
DELETE FROM dfTree WHERE lineage LIKE '/1/2/5/%'
Once we've figured this out, it's a simple matter to implement the DeleteNode procedure:
CREATE PROCEDURE dfTreeDeleteNode ( @id INT ) AS
DELETE FROM dfTree
WHERE lineage LIKE (SELECT lineage
FROM dfTree
WHERE id = @id) + '%'
And again, the standard plumbing in our provider class:
public void RemoveNode(int uniqueID)
{
using (SqlConnection sqlConn = new SqlConnection(connectionString) )
{
// execute the dfTreeDeleteNode stored procedure
SqlCommand sqlComm = new SqlCommand("dfTreeDeleteNode",sqlConn);
sqlComm.CommandType = CommandType.StoredProcedure;
sqlComm.Parameters.Add("@id",SqlDbType.Int).Value = uniqueID;
sqlConn.Open();
sqlComm.ExecuteNonQuery();
}
}
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.