Library tutorials & articles
Tree structures in ASP.NET and SQL Server
Introduction
Trees can be an intuitively simply way of organising large amounts of information. We're exposed to them everywhere - from directories in file systems and categories in a web directory to hierarchies in organisations and family trees! Something like XML handles hierarchical data well, but if you've got a database full of data we want to associate with the tree - for example, a table full of articles - splitting our data store between XML and something like SQL Server isn't a particularly elegant option. Unfortunately, relational SQL doesn't make it especially easy to store these structures in such a way that we can perform useful (and efficient) operations over the trees.
This article looks at one way to represent trees in .NET - and how to map them to a table in SQL Server and back again - which should hopefully take the pain out of storing trees and manipulating them from .NET. Our aim will be to create an ASP.NET page that provides some standard "web directory" features including
- Breadcrumbs
- Listing sub-nodes in the current section
- Indicating some of the children of these child nodes
whilst ensuring that we have zero limitations on the number of items in the tree, or its depth.
I've referenced many articles on the subject in order to implement the SQL Server portion of this - in particular, Maintaining Hierarchies and More Trees & Hierarchies in SQL - so many thanks to those authors. I hope this proves to be a useful extension to their discussions, rather than just a rehash of old material! Naturally, any mistakes in the implementation I show here are mine alone - but please do point them out to me.
Representing trees in .NET
To start with, its probably useful to remind ourselves what exactly a tree is (!). Each element in a tree is known as a node - each node has zero or more child nodes, and the one at the top - with no parent - is the root of the tree. .NET doesn't currently have a built-in datatype for representing trees, but it's fairly straightforward to to create our own. We'll simply create a class to represent each "node" in the tree - which will consist of the following.
| Property Name | Data Type | Description |
|---|---|---|
| UniqueID | int | A unique identifier for the node in this tree. As we're looking to store the tree in a relational database, this maps nicely to a primary/identity key, so we'll use an integer here. If we are creating a new TreeNode object that has not yet been associated with a unique identifier, this value will be zero. |
| ParentID | int | Used to identify the parent node of this object by storing the unique id of the parent. A parent ID of zero indicates that the node has no parent (ie it is a root node). |
| Name | string | A text value (not necessarily unique) to be associated with this node. |
| Children | ArrayList<TreeNode> | A collection of TreeNode objects that are children of this node. This will not necessarily contain all children that are in the original tree stored in our relational database - but will be populated appropriately depending on which queries we run. |
The simple class shown below encapsulates this.
[Serializable]
public class TreeNode
{
private int _uniqueID;
private string _name;
private int _parentID;
private int _depth;
private ArrayList _children;
public TreeNode() { }
public TreeNode(string name, int parentID) : this(0,name,parentID,-1)
{
}
public TreeNode(int uniqueID, string name, int parentID, int depth)
{
_uniqueID = uniqueID;
_name = name;
_parentID = parentID;
_depth = depth;
}
/// <summary>
/// Gets or sets the unique ID associated with this category
/// </summary>
/// <remarks>Once a non-zero ID has been set, it may not be modified.</remarks>
public int UniqueID
{
get { return _uniqueID; }
set
{
if (_uniqueID == 0)
_uniqueID = value;
else
throw new Exception("The UniqueID property cannot be modified once it has a non-zero value");
}
}
public int Depth
{
get { return _depth; }
}
/// <summary>
/// Gets or sets the label for this node
/// </summary>
public string Name
{
get { return _name; }
set { _name = value; }
}
/// <summary>
/// The ID of the parent node
/// </summary>
public int ParentID
{
get { return _parentID; }
set { _parentID = value; }
}
/// <summary>
/// Gets the children TreeNode objects for this category
/// </summary>
/// <remarks>In .NET 2.0, this can be modified to use generics, and have type ArrayList<TreeNode></remarks>
public ArrayList Children
{
get { return _children; }
set { _children = value; }
}
}
We're not going to actually use this class to create standalone tree structures along the lines we would if were were adding elements to, say, a TreeView control. The TreeNode's will be used to represent what we have stored in the database as a tree. However, if we want to add a TreeNode to the structure, the request is going to be made directly to the database - and the change will be reflected in a future request on the state of the tree structure. Likewise, if we modify the Name or ParentId of a TreeNode object, we'll need to tell the database that we've made this change.
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.