4.6 Implementing General Hierarchies

4.6.1 Problem

You want to implement a project-tracking system based on a general hierarchy, and you want to run some basic, single-level hierarchical queries against that hierarchy.

4.6.2 Solution

Use the general parent/child model described earlier in the project-tracking example in Section 4.1 as the basis for the project-tracking system. In this model, a project is composed of subprojects or tasks, tasks may be broken into subtasks, and subtasks may themselves be broken up into subtasks. There is no limit to the level of nesting that may occur, and it all occurs within one database table named Projects. Conceptually, a project is simply the highest-level task. The Projects table is defined as follows:

CREATE TABLE Projects(
   Name VARCHAR(20),
   Cost INTEGER,
   Parent INTEGER,
   VertexId INTEGER,
   Primary key(VertexId)
)

With this solution in mind, let's look at a few problems that are common to hierarchical structures, such as the one used here to define projects:

List all leaf nodes
List all nodes that are not leaf nodes
Find the most expensive vertices
List the immediate children of a node
Find the root

The next few sections present SQL Server solutions to each of these problems.

4.6.2.1 List all leaf nodes

Leaf nodes are nodes without children. The subquery in the following SELECT statement checks each node to see if any other nodes claim it as a parent. If none do, then that node is a leaf node:

SELECT Name FROM Projects p 
WHERE NOT EXISTS(
   SELECT * FROM Projects 
   WHERE Parent=p.VertexId)

The result of executing this query is a list of all subprojects (or tasks if you prefer) that have no children:

Name                 
-------------------- 
Interviews
Drafts
Consolidations
Presentation
UI Design
Correctness Testing
Database
UI Implementation
Coding
Initial Testing
Final Adjustments
Production Testing

4.6.2.2 List all nodes that are not leaf nodes

To list all nodes that are not leaf nodes — in other words, all nodes that have children — begin with the same query used to list leaf nodes and just convert the NOT EXISTS into an EXISTS:

SELECT Name FROM Projects p 
WHERE EXISTS(
   SELECT * FROM Projects 
   WHERE Parent=p.VertexId)

This query lists all nodes with children:

Name                 
-------------------- 
New SW
Specifications
Final Document
Prototype
Calculating
Development
Beta Testing

4.6.2.3 Find the most expensive vertices

Each task in the project has a cost associated with it. Each task is also a vertex. To find the N most expensive tasks, simply query the table, order the results by cost, and use the TOP operator to limit the results to the top N rows. For example:

SELECT TOP 5 Name, Cost 
FROM Projects 
ORDER BY cost DESC

Name                 Cost        
-------------------- ----------- 
Inital testing       40
Beta testing         40
Development          30
Coding               20
Production testing   20

This is a good example of a case where it is more productive to issue straight SQL queries, rather than attempt to navigate the hierarchy.

4.6.2.4 Find the immediate children of a node

Given a particular node, you can write a query to return that node's immediate children. The following query, for example, returns the subprojects of the project named Specifications:

SELECT Name FROM Projects 
WHERE Parent=(
   SELECT VertexId FROM Projects 
   WHERE Name='Specifications' )

Name                 
-------------------- 
Interviews
Drafts
Consolidations
Final document

Only immediate children are returned. The parent record for each of the four records shown here is the record for the "Specifications" task. These records may, themselves, have children, but those children won't show up in the results for this query.

4.6.2.5 Find the root

The root is the vertex with no parents. The query to return it is simple, because all you need is to return the one node with no parent pointer. For example:

SELECT Name FROM Projects WHERE Parent=0

Name                 
-------------------- 
New SW

In our example, we use a value of zero to indicate that a node does not have a parent. You could just as easily use a NULL to indicate the same thing, in which case you would specify Parent IS NULL as your WHERE clause condition.

4.6.3 Discussion

As you can see, these queries work on a single level where, at most, they refer to one level above (to parents) or below (to children). For these types of queries, you don't need any additional algorithms or data structures to retrieve information. The queries are pretty straightforward, and you just have to remember the definition of your hierarchy and its elements to write them.