SQL Data Hierarchy

Question

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 1

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):

1. Split the CTE expression into anchor and recursive members.
2. Run the anchor, creating the first result set.
3. Run the recursive portion, with the prior step as an input.
4. Repeat step 3 until an empty set is returned.
5. 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!