I have a simple table here which shows a list of devices and each device can have a parent device except for the top item which has a <NULL> value for the ParentID column.
Using SQL 2005 CTE (Common Table Expression) to render this full hierarchy we could use a simple query such as this:
What this CTE is doing is allowing us to run a hierarchical query.
We first off find the root of our tree, which in this case is referenced by a NULL value in the ParentID column.
SELECT ParentID, ID,0, [DeviceType], cast(DeviceType as nvarchar(1024))
FROM DeviceType
WHERE ParentID IS null
This technically returns the same details as row #1 in the above graphic.
What the UNION ALL does is executes a query with a join against the CTE virtual table.
So we technically are sort of doing this:
Create Virtual Table with the following fields:
- ParentID
- ID,
- Level,
- DevieType,
- Sort
This line inserts one row into the virtual table, the ID in this case will be 1 because that was the ID in our DeviceType table of the record with the ParentID of Null.
SELECT ParentID, ID,0, [DeviceType], cast(DeviceType as nvarchar(1024))
FROM DeviceType
WHERE ParentID IS null
Now we run the following query on the virtual table until every row is processed in the virtual table.
Note: This select is really like an insert into the virtual table. each row returned in the select is appended to our virtual table.
SELECT dt.ParentID, dt.ID, level+1, dt.DeviceType, cast(Sort + '|'+dt.Devicetype as nvarchar(1024))
FROM DeviceType dt INNER JOIN hierarchy h ON dt.ParentID = h.ID
So the first time it is run we see that h.ID would be equal to 1 which was the ID of the record with ParentID of Null. If there was any records matching this select statement they are added to the virtual table and this continues until all of the virtual table rows have been processed.
At the end of it we have a Virtual table that we can then do what we want with such as join it to another table or just return the data, in our case we run this sql statement.
select ID, ParentID, DeviceType, LEVEL, Sort
from Hierarchy
order by sort
But what happens if I have an record and want to find the parent hierarchy for it?
The following query will allow us to return the parent hierarchy for the item Virtual Server Hosts which has an ID of 10.
Note: There are problems with the results of this query!
Can you see the problem with the results?
We have correctly returned the parents starting from the Virtual Server Hosts and walked up the tree until we get to the root node. But if you look at the Level field it is not actually containing the correct value as the Virtual Server Hosts fields should be at level 3 and not at level 0.
Why is this?
Well we can't determine at what level the Virtual Server Hosts is at when we start creating the virtual table so we just hard code it to 0.
The problem also is that if you wanted to render this out to say a web browser using the following hierarchy we would have to navigate through our records backwards.
How to fix this!
What we can do in this case is run a second CTE joined to the first CTE because each CTE is just like a virtual table. When the first CTE has completed processing we are basically left with a table with records in it like below.
Our second CTE now just references the records in the first CTE as if it was a standard table.
As you can see in the query in the above graphic our second CTE starts by looking for a record which has the ParentID being set to NULL.
This will return our real parent as the first record to be inserted into our second virtual table.
Now we run the following query on the second virtual table until every row is processed in the virtual table. Like the first virtual table, the select appends records to our virtual table and these records get processed until all records have been processed.
SELECT h.ParentID, h.ID, hr.LEVEL+1, h.DeviceType, cast(hr.Sort + '|'+h.sort as nvarchar(1024))
FROM Hierarchy h INNER JOIN HierarchyReverse hr ON h.ParentID = hr.ID
We have changed the join in the second CTE to join from the ParentID --> ItemID, which is the opposite of the first CTE which joined the ItemID --> ParentID. This allows us to navigate down the tree instead of up the tree.
Confusing? hopefully not....
What we end up with is this:
Now you may be wondering what this Sort column is and why we have it at all?
The reason is that we need to have something that is sortable, using the DeviceType is not since it would corrupt our hierarchy by giving us A-Z, the same goes for level, 0-9
What we do is we create a field that contains the hierarchy so far and then add the DeviceType to the end of it. This makes a sortable field that will not corrupt our hierarchy but give us A-Z sorting within each level of the hierarchy.
Notice the problem with this?
Well I have made a decision that all of my hierarchies of DeviceType will not exceed 1024 characters by casting the values with the statement : NVARCHAR(1024)
Well we could use a NVARCHAR(MAX) and the problem is resolved, but this is dependant on your knowledge of the application.
Hopefully this has shown you and me how the CTE's work while they are running - well it looks like that to me and it makes me understand it a bit easier as they can be hard to picture sometimes.