Shimon Krokhmal's blog

remember this neat syntax that exists in oracle database for hierarchy selects ?
actually , its pretty simple :

SELECT last_name, employee_id, manager_id, LEVEL
FROM employees
START WITH employee_id = 100
CONNECT BY PRIOR employee_id = manager_id;

ever tried to do the same in sql server ?
well, these kind of syntax just does not exist,
we need to work very hard to create such a feature in our database.

so, what do we have:

• a table that contains entities
• each entity connected to some father entity
• each connection describes a "father - son" relation between the two entities

lets not forget the things we need to relay on , when implementing :

• what will happen when we will delete the father of some sub tree ?
• what should we do when we update/add a record ?
• how will we select the data ?
• algorithm efficiency is crucial, if we will need to wait 5 minutes for the data, it's not worth it

the first (but apparently the worst) idea that came to my mind is recursion
lets look at this table :

we have we that the employee shimon is the "big boss" (because there is no other boss above him),
under shimon we have the employees Gaby and yossi,
and under Gaby, we have another 2 employees : Koby and jack

the recursive solution is to write some stored procedure that will receive the employeeID and return as a data-Table the results
i will not add the code for this solution and surely will not recommend it because it was many problems :

• for each record we received as a descendant ,
  we need to run with the function and get her descendants,
  and so on, until there are no descendants for the node
• we are limited to 32 levels of hierarchy
• the runtime will depend on the row count that is in the table (we will need to run on each of the rows one at the time)
• the run on the node will look like this :
  
  
  

by the way, the most common way that I've seen to select hierarchical structure,
is simply by setting a join between the levels in the select query.
for example :

SELECT TopBoss.Name TopBoss, Boss.Name Boss, Employees.Name Employee
FROM Employees
INNER JOIN Employees AS Boss ON Employees.BossID=Boss.EmployeeID
INNER JOIN Employees TopBoss ON Boss.BossID=TopBoss.EmployeeID

this apply to the selection of three levels

For each level, you'd need to join the table to itself...not an attractive option if you have 5 or more levels ,
you don't know how many levels you will have to select, there is no way can control it!
It would be great if it could join itself as many times as needed. This is called a recursive join, and though some database products support it (Oracle has the CONNECT BY syntax) SQL Server is not one of them.

the other way is based on a thread that i read here about hierarchies,

lets create a table :

CREATE TABLE Tree (
Node int NOT NULL IDENTITY(100, 1),
ParentNode int,
EmployeeID int NOT NULL,
Depth tinyint,
Lineage varchar(255) )

the extra fields that has been added are the "lineage" and the "depth"

• Depth - for saving the current depth of the record in the hierarchy
• Lineage - for saving all the ancestors of the record as a concatenated string

after filling the needed data for relations, the table looks like this :

The next part is to find the root node of the tree, also known as the top-level, etc.
That's the node that has no parent (Null), so we will start there and set the Lineage column as the root:

UPDATE Tree SET Lineage='/', Depth=0 WHERE ParentNode Is Null

Once we did that,
we can then update the rows who are the descendant of the root node:

WHILE EXISTS (SELECT * FROM Tree WHERE Depth Is Null) 
   UPDATE T SET T.depth = P.Depth + 1, 
   T.Lineage = P.Lineage + Ltrim(Str(T.ParentNode,6,0)) + '/' 
   FROM Tree AS T 
   INNER JOIN Tree AS P ON (T.ParentNode=P.Node) 
   WHERE P.Depth>=0 
   AND P.Lineage Is Not Null 
   AND T.Depth Is Null

this loop will run once for each level of the hierarchy (not for each node as the recursion method.)
so, with data representation of 10,000 records with 8 levels of hierarchy,
this code will run only 8 times to populate the needed data of the "lineage" field and the "depth" field, and this "heavy" procedure will happen only once at the setup.
the table should look like this after the given operation :

You'll notice that for each node, the entire lineage back to the root is stored. This means that finding someone's boss, or their boss' boss, doesn't require any self-joins or recursion to create an indented list. In fact, it can be accomplished with a single SELECT.

SELECT Space(T.Depth*2) + E.Name AS Name
FROM Employees E
INNER JOIN Tree T ON E.EmployeeID=T.EmployeeID
ORDER BY T.Lineage + Ltrim(Str(T.Node,6,0))

maintaining the table is really not a big deal if we will use triggers.
think about the new inserted record as the row that has not been filled in the setup process.
so the insert trigger should be :

UPDATE T SET T.depth = P.Depth + 1,
T.Lineage = P.Lineage + Ltrim(Str(T.ParentNode,6,0)) + '/'
FROM Tree AS T
INNER JOIN Tree AS P ON (T.ParentNode=P.Node)
WHERE P.Depth>=0
AND P.Lineage Is Not Null
AND T.Depth Is Null

the update trigger should do pretty much the same : building the 2 extra field all over again.

suggestions and request will be repplied :)