I have looked through a few SQL hierarchy tutorials, but none of them made much sense for my application. Perhaps I am just not understanding them correctly. I'm writing a C# ASP.NET application and I would like to create a tree view hierarchy from SQL data.
This is how the hierarchy would work:
SQL TABLE ID | Location ID | Name _______| __________ |_____________ 1331 | 1331 | House 1321 | 1331 | Room 2141 | 1321 | Bed 1251 | 2231 | Gym
If the ID and Location ID are the same, this would determine the top Parent. Any Children of that Parent would have the same Location ID as the Parent. Any Grandchildren of that Child would have a Location ID equal to the ID of the Child, and so on.
For the above example:
- House
-- Room
--- Bed
Any help or direction to easy to follow tutorials would be greatly appreciated.
EDIT:
Code I have so far, but it only gets the Parent and Children, no GrandChildren. I can't seem to figure out how to get it to recursively get all of the nodes.
using System;
using System.Data;
using System.Collections.Generic;
using System.Web;
using System.Web.UI;
using System.Web.UI.WebControls;
using System.Configuration;
using System.Data.SqlClient;
namespace TreeViewProject
{
public partial class _Default : System.Web.UI.Page
{
protected void Page_Load(object sender, EventArgs e)
{
PopulateTree(SampleTreeView);
}
public void PopulateTree(Control ctl)
{
// Data Connection
SqlConnection connection = new SqlConnection(ConfigurationManager.ConnectionStrings["AssetWhereConnectionString1"].ConnectionString);
connection.Open();
// SQL Commands
string getLocations = "SELECT ID, LocationID, Name FROM dbo.Locations";
SqlDataAdapter adapter = new SqlDataAdapter(getLocations, connection);
DataTable locations = new DataTable();
// Fill Data Table with SQL Locations Table
adapter.Fill(locations);
// Setup a row index
DataRow[] myRows;
myRows = locations.Select();
// Create an instance of the tree
TreeView t1 = new TreeView();
// Assign the tree to the control
t1 = (TreeView)ctl;
// Clear any exisiting nodes
t1.Nodes.Clear();
// BUILD THE TREE!
for (int p = 0; p < myRows.Length; p++)
{
// Get Parent Node
if ((Guid)myRows[p]["ID"] == (Guid)myRows[p]["LocationID"])
{
// Create Parent Node
TreeNode parentNode = new TreeNode();
parentNode.Text = (string)myRows[p]["Name"];
t1.Nodes.Add(parentNode);
// Get Child Node
for (int c = 0; c < myRows.Length; c++)
{
if ((Guid)myRows[p]["LocationID"] == (Guid)myRows[c]["LocationID"]
&& (Guid)myRows[p]["LocationID"] != (Guid)myRows[c]["ID"] /* Exclude Parent */)
{
// Create Child Node
TreeNode childNode = new TreeNode();
childNode.Text = (string)myRows[c]["Name"];
parentNode.ChildNodes.Add(childNode);
}
}
}
}
// ALL DONE BUILDING!
// Close the Data Connection
connection.Close();
}
}
}
Here is a snippit from the actual SQL table: Locations
ID LocationID Name ____________________________________ ____________________________________ ______________ DEAF3FFF-FD33-4ECF-910B-1B07DF192074 48700BC6-D422-4B26-B123-31A7CB704B97 Drop F 48700BC6-D422-4B26-B123-31A7CB704B97 7EBDF61C-3425-46DB-A4D5-686E91FD0832 Olway 06B49351-6D18-4595-8228-356253CF45FF 6E8C65AC-CB22-42DA-89EB-D81C5ED0BBD0 Drop E 5 E98BC1F6-4BAE-4022-86A5-43BBEE2BA6CD DEAF3FFF-FD33-4ECF-910B-1B07DF192074 Drop F 6 F6A2CF99-F708-4C61-8154-4C04A38ADDC6 7EBDF61C-3425-46DB-A4D5-686E91FD0832 Pree 0EC89A67-D74A-4A3B-8E03-4E7AAAFEBE51 6E8C65AC-CB22-42DA-89EB-D81C5ED0BBD0 Drop E 4 35540B7A-62F9-487F-B65B-4EA5F42AD88A 48700BC6-D422-4B26-B123-31A7CB704B97 Olway Breakdown 5000AB9D-EB95-48E3-B5C0-547F5DA06FC6 6E8C65AC-CB22-42DA-89EB-D81C5ED0BBD0 Out 1 53CDD540-19BC-4BC2-8612-5C0663B7FDA5 6E8C65AC-CB22-42DA-89EB-D81C5ED0BBD0 Drop E 3 7EBDF61C-3425-46DB-A4D5-686E91FD0821 B46C7305-18B1-4499-9E1C-7B6FDE786CD6 TEST 1 7EBDF61C-3425-46DB-A4D5-686E91FD0832 7EBDF61C-3425-46DB-A4D5-686E91FD0832 HMN
Thanks.
Answer
You are looking for a recursive query using a common table expression, or CTE for short. A detailed write-up for this in SQL Server 2008 can be found on MSDN.
In general, they have a structure similar to the following:
WITH cte_name ( column_name [,...n] )
AS (
–- Anchor
CTE_query_definition
UNION ALL
–- Recursive portion
CTE_query_definition
)
-- Statement using the CTE
SELECT * FROM cte_name
When this executes, SQL Server will do something similar to the following (paraphrased into simpler language from the MSDN):
- Split the CTE expression into anchor and recursive members.
- Run the anchor, creating the first result set.
- Run the recursive portion, with the prior step as an input.
- Repeat step 3 until an empty set is returned.
- Return the result set. This is a UNION ALL of the anchor and all recursive steps.
For this specific example, try something like this:
With hierarchy (id, [location id], name, depth)
As (
-- selects the "root" level items.
Select ID, [LocationID], Name, 1 As depth
From dbo.Locations
Where ID = [LocationID]
Union All
-- selects the descendant items.
Select child.id, child.[LocationID], child.name,
parent.depth + 1 As depth
From dbo.Locations As child
Inner Join hierarchy As parent
On child.[LocationID] = parent.ID
Where child.ID != parent.[Location ID])
-- invokes the above expression.
Select *
From hierarchy
Given your example data, you should get something like this:
ID | Location ID | Name | Depth
_______| __________ |______ | _____
1331 | 1331 | House | 1
1321 | 1331 | Room | 2
2141 | 1321 | Bed | 3
Note that "Gym" is excluded. Based on your sample data, it's ID does not match its [Location ID], so it would not be a root-level item. It's location ID, 2231, does not appear in the list of valid parent IDs.
Edit 1:
You've asked about getting this into a C# data structure. There are many, many different ways to represent a hierarchy in C#. Here is one example, chosen for its simplicity. A real code sample would no doubt be more extensive.
The first step is to define what each node in the hierarchy looks like. Besides containing properties for each datum in the node, I've included Parent and Children properties, plus methods to Add a child and to Get a child. The Get method will search the node's entire descendant axis, not just the node's own children.
public class LocationNode {
public LocationNode Parent { get; set; }
public List<LocationNode> Children = new List<LocationNode>();
public int ID { get; set; }
public int LocationID { get; set; }
public string Name { get; set; }
public void Add(LocationNode child) {
child.Parent = this;
this.Children.Add(child);
}
public LocationNode Get(int id) {
LocationNode result;
foreach (LocationNode child in this.Children) {
if (child.ID == id) {
return child;
}
result = child.Get(id);
if (result != null) {
return result;
}
}
return null;
}
}
Now you'll want to populate your tree. You have a problem here: it's difficult to populate a tree in the wrong order. Before you add a child node, you really need a reference to the parent node. If you have to do it out of order, you can mitigate the problem by making two passes (one to create all the nodes, then another to create the tree). However, in this case, that is unnecessay.
If you take the SQL query I provided above and order by the depth column, you can be mathematically certain that you will never encounter a child node before you encounter its parent node. Therefore, you can do this in one pass.
You will still need a node to serve as the "root" of your tree. You get to decide whether this will be "House" (from your example), or whether it is a fictional placeholder node that you create just for this purpose. I suggest the later.
So, to the code! Again, this is optimized for simplicity and readability. There are some performance issues that you may want to address in production code (for instance, it is not really necessary to constantly look up the "parent" node). I've avoided these optimizations here because they increase complexity.
// Create the root of the tree.
LocationNode root = new LocationNode();
using (SqlCommand cmd = new SqlCommand()) {
cmd.Connection = conn; // your connection object, not shown here.
cmd.CommandText = "The above query, ordered by [Depth] ascending";
cmd.CommandType = CommandType.Text;
using (SqlDataReader rs = cmd.ExecuteReader()) {
while (rs.Read()) {
int id = rs.GetInt32(0); // ID column
var parent = root.Get(id) ?? root;
parent.Add(new LocationNode {
ID = id,
LocationID = rs.GetInt32(1),
Name = rs.GetString(2)
});
}
}
}
Ta-da! The root LocationNode now contains your entire hierarchy. By the way, I haven't actually executed this code, so please let me know if you spot any glaring issues.
Edit 2
To fix your sample code, make these changes:
Remove this line:
// Create an instance of the tree
TreeView t1 = new TreeView();
This line is not actually an issue, but it should be removed. Your comments here are inaccurate; you are not really assigning a tree to the control. Instead, you are creating a new TreeView, assigning it to t1, then immediately assigning a different object to t1. The TreeView that you create is lost as soon as the next line executes.
Fix your SQL statement
// SQL Commands
string getLocations = "SELECT ID, LocationID, Name FROM dbo.Locations";
Replace this SQL statement with the SQL statement that I suggested earlier, with an ORDER BY clause. Read my previous edit that explains why the "depth" is important: you really do want to add the nodes in a particular order. You cannot add a child node until you have the parent node.
Optionally, I think you don't need the overhead of an SqlDataAdapter and DataTable here. The DataReader solution I originally suggested is simpler, easier to work with, and more effecient in terms of resources.
Also, most C# SQL objects implement IDisposable, so you will want to make sure you are using them correctly. If something implements IDisposable, be sure you wrap it in using statements (see my prior C# code sample).
Fix your tree-building loop
You're only getting the parent and child nodes because you have a loop for the parents and an inner loop for the children. As you must already know, you aren't getting the grandchildren because you have no code that adds them.
You could add an inner-inner loop to get the grandchildren, but clearly you're asking for help because you've realized that doing so will only lead to madness. What would happen if you then wanted the great-grandchildren? An inner-inner-inner loop? This technique is not viable.
You have probably thought of recursion here. This is a perfect place for it, and if you are dealing with tree-like structures, it's going to come up eventually. Now that you've edited your question, it's clear that your problem has little, if anything, to do with SQL. Your real problem is with recursion. Somebody may eventually come along and devise a recursive solution for this. That would be a perfectly valid, and possibly preferable approach.
However, my answer has already covered the recursive part--it has simply moved it into the SQL layer. Therefore, I'll keep my previous code around, as I feel it is a suitable generic answer to the question. For your specific situation, you'll need to make a few more modifications.
First, you won't need the LocationNode class that I suggested. You are using TreeNode instead, and that will work fine.
Secondly, the TreeView.FindNode is similar to the LocationNode.Get method that I suggested, except that FindNode requires the complete path to the node. To use FindNode, you must modify the SQL to give you this information.
Therefore, your entire PopulateTree function should look like this:
public void PopulateTree(TreeView t1) {
// Clear any exisiting nodes
t1.Nodes.Clear();
using (SqlConnection connection = new SqlConnection()) {
connection.ConnectionString = "((replace this string))";
connection.Open();
string getLocations = @"
With hierarchy (id, [location id], name, depth, [path])
As (
Select ID, [LocationID], Name, 1 As depth,
Cast(Null as varChar(max)) As [path]
From dbo.Locations
Where ID = [LocationID]
Union All
Select child.id, child.[LocationID], child.name,
parent.depth + 1 As depth,
IsNull(
parent.[path] + '/' + Cast(parent.id As varChar(max)),
Cast(parent.id As varChar(max))
) As [path]
From dbo.Locations As child
Inner Join hierarchy As parent
On child.[LocationID] = parent.ID
Where child.ID != parent.[Location ID])
Select *
From hierarchy
Order By [depth] Asc";
using (SqlCommand cmd = new SqlCommand(getLocations, connection)) {
cmd.CommandType = CommandType.Text;
using (SqlDataReader rs = cmd.ExecuteReader()) {
while (rs.Read()) {
// I guess you actually have GUIDs here, huh?
int id = rs.GetInt32(0);
int locationID = rs.GetInt32(1);
TreeNode node = new TreeNode();
node.Text = rs.GetString(2);
node.Value = id.ToString();
if (id == locationID) {
t1.Nodes.Add(node);
} else {
t1.FindNode(rs.GetString(4)).ChildNodes.Add(node);
}
}
}
}
}
}
Please let me know if you find any additional errors!