TOP 1 WITH TIES

Managing Hierarchies in Relational Database Environment is always a challenging task. Over the years many models like Adjacency List Model, Nested Set Model, Nested Interval Model, Path Enumeration Model etc. were proposed and implemented. There are also other popular methods using recursion and user defined function. SQL Server 2005 T-SQL Extensions has special operators for managing recursive queries. Joe CELKO has written a book exclusively on Managing Trees and Hierarchies.

The basic Hierarchical operations in a typical Employee-Manager type of relation, include

1. Add a new Employee
2. Show the whole Hierarchy with levels.
3. Show the superiors of a given employee.
4. Show the subordinates of a given employee.
5. Show the immediate subordinates of a given employee.
6. List all the Leaf Level Employees.
7. Change the manager of an Employee
8. Delete an Employee and all his subordiantes.
9. Delete an Employee.

Here I am trying to propose a simple model which works almost like Path Enumeration model. This model uses a Prime Number table and basic mathematical operations to answer the above questions. Also the Model only uses set based solutions and can be implemented as a self managing system with the help of triggers.

This model works on two basic concepts.

1. There is a unique path to every node in a hierarchy from the root node.
2. The Prime Number that can be a divisor of the Product of a set of Prime Numbers, are only the Prime numbers in the set.

That is, Let product of n prime numbers be Px, then, the factors of Px can only be the Prime Numbers that participated in the multiplication, or the sub products.
So the product cannot be divided by any other Prime Number.

For eg.

P1, P2, P3,...Pn is the list of Prime Numbers.

Let P be the Product.

Then P1 * P2 * P3 * ... * Pn = P

Then the factors of P can be either P1, P2, P3,...Pn Or the sub product of P1, P2, P3,...Pn.


Now let's try to answer the above questions.

The following is the table used in the examples.

CREATE TABLE dbo.EmpHierarchy
(EmpId int PRIMARY KEY,
EmpName VARCHAR(15),
ManagerId int,
HKey bigint UNIQUE,
Path bigint)

GO

The purpose of the first three columns are obvious. The column Hkey is a Unique Prime Number assigned to each employee. The column Path Holds the product of the Hkey values of the current node and nodes above the current node.

The script used for creating and Populating the PrimeNumber table is here.

1. Add a new Employee
For inserting a new node (employee), we will get the least available Prime Number and use it as the Hkey of the node. The Path will be the Product of the Hkey and the Path of the parent node. For the root level entry the path will be the Hkey itself.

Here is the script for the stored procedure dbo.InsertNode

Now lets insert some sample data.

EXEC dbo.InsertNode 1,'Albert', NULL
EXEC dbo.InsertNode 2,'Bert', 1
EXEC dbo.InsertNode 3,'Chuck', 1
EXEC dbo.InsertNode 4,'Dona', 3
EXEC dbo.InsertNode 5,'Eddie', 3
EXEC dbo.InsertNode 6,'Fred', 3

SELECT * FROM EmpHierarchy

Now we have this data in the table.

EmpId	EmpName	ManagerId	HKey	Path
2	Bert	1	3	6
3	Chuck	1	5	10
4	Dona	3	7	70
5	Eddie	3	11	110
6	Fred	3	13	130

2. Show the whole Hierarchy with levels.
The level of a node in a hierarchy depends on the number of levels above it. So the level of a given node can be found by counting the levels above it. Thats the technique used in the stored procedure dbo.PrintHierarchy. The SP also accepts an EmployeeId, to display a partial hierarchy.

EXEC dbo.PrintHierarchy

Here is the output

Hierarchy	Level	Employee	Manager
-	1	Albert	NULL
--	2	Bert	Albert
--	2	Chuck	Albert
---	3	Dona	Chuck
---	3	Eddie	Chuck
---	3	Fred	Chuck

3. Show the superiors of a given employee.
The path of a given employee is the product of the Hkeys of his superiors and his Hkey. As per our rule the path can be divided only by the Prime Numbers participated in it. Based on that finding the superiors logic is failrly easy. You can get the list of the superios of a given employee by

SELECT A.EmpId, A.EmpName
FROM EmpHierarchy A
WHERE [Path of the given Employee] % A.Hkey = 0

I have this Stored Procedure dbo.getSuperiors which accepts an Employee Id and return the list of his superiors.

To get the Superiors of 'Fred', execute

EXEC dbo. getSuperiors 6

Here is the output

EmpId	Employee	Manager
6	Fred	Chuck
3	Chuck	Albert
1	Albert	NULL

4. Show the subordinates of a given employee.
The Hkey of a given employee will be a factor of the Path of all his subordinates and only his subordinates.
So to get the list of the subordinates of an employee, you can run a query like

SELECT A.EmpId, A.EmpName AS Employee
FROM EmpHierarchy A
WHERE A.Path % [HKey of the given Employee] = 0

Here is the stored procedure dbo. getSubordinates for doing the same.

Now to get the list of subordiantes of 'Chuck', execute

EXEC dbo. getSubordinates 3

Here is the output

EmpId	Employee	Manager
3	Chuck	Albert
4	Dona	Chuck
5	Eddie	Chuck
6	Fred	Chuck

5. Show the immediate subordinates of a given employee.
The path of the immediate subordiantes of a given employee will be the product of the path of the manager and the HKey of the subordinate.
So one can find the immediate subordinates of a given employee by writing a query like

SELECT EmpId, EmpName
FROM EmpHierarchy
WHERE Path = HKey * [Path of the Given Employee]

For eg, to get All the immediate subordinates of Albert, the query will be

SELECT EmpId, EmpName
FROM EmpHierarchy
WHERE Path = HKey *2 --Path of Albert

Here is the output

EmpId	EmpName
2	Bert
3	Chuck

6. List all the Leaf Level Employees.
Leaf level employees are those who dont have any subordinates. So finding them is a trivial task.
The following query gives you the list of leaf level employees.

SELECT EmpId, EmpName
FROM EmpHierarchy A
WHERE NOT Exists(SELECT 1 FROM EmpHierarchy T
WHERE T.Path % A.Hkey = 0
AND T.Path > A.Path)

And here is the output.

EmpId	EmpName
2	Bert
4	Dona
5	Eddie
6	Fred

7. Change the manager of an Employee
Updating can be of two types, promotion and demotion. When updating an Employees manager, you need to update the rows of the given employee and all his subordinates Path. Also you need to perform some validation to avoid cyclic reference. Here is the stored Procedure dbo.UpdateNode to update a given node.

So now to change Fred's Manager to Bert from Chuck, you can Execute

EXEC dbo.UpdateNode EmployeeId, NewManagerId

EXEC dbo.UpdateNode 6, 2

After the update, the hierarchy will look like

EXEC dbo.PrintHierarchy

Hierarchy	Level	Employee	Manager
-	1	Albert	NULL
--	2	Bert	Albert
--	2	Chuck	Albert
---	3	Dona	Chuck
---	3	Eddie	Chuck
---	3	Fred	Bert

Now, lets try a promotion. Eddie directly reports to Albert instead of Chuck

EXEC dbo.UpdateNode 5, 1

This is how the hierarchy will look like now.

EXEC dbo.PrintHierarchy

Hierarchy	Level	Employee	Manager
-	1	Albert	NULL
--	2	Bert	Albert
--	2	Chuck	Albert
--	2	Eddie	Albert
---	3	Fred	Bert
---	3	Dona	Chuck

Finally lets demote chuck one level down the hierarchy. Instead of reporting to Albert, he will now report to Bert

EXEC dbo.UpdateNode 3, 2

EXEC dbo.PrintHierarchy

Hierarchy	Level	Employee	Manager
-	1	Albert	NULL
--	2	Bert	Albert
--	2	Eddie	Albert
---	3	Fred	Bert
---	3	Chuck	Bert
----	4	Dona	Chuck

8. Delete an Employee and all his subordiantes.
Deleting a subtree is fairly easy. we can use the same logic of finding subordinates and apply that in the where clause.
Here is the stored procedure dbo.deleteSubTree

Now to fire the whole team of Chuck, you can execute

EXEC dbo.deleteSubTree 3 --EmployeeId of chuck

After the deletion, the Hierarchy will look like

EXEC dbo.PrintHierarchy

Hierarchy	Level	Employee	Manager
-	1	Albert	NULL
--	2	Bert	Albert
--	2	Eddie	Albert
---	3	Fred	Bert

9. Delete an Employee.
This can be more tricky, because when you delete an Employee, If he has subordinates, the hierarchy will be broken. So all the subordinates of the deleted employee should report to the Manager of the deleted employee. Here is the Stored Procedure dbo.deleteNode, which takes care of it.

So Now lets try deleting Bert.

EXEC dbo.deleteNode 2

After the deletion, the hierarchy will look like

Hierarchy	Level	Employee	Manager
-	1	Albert	NULL
--	2	Eddie	Albert
--	2	Fred	Albert

And thats it :)

These are the pro's and con's of the model from my point of view.

Pros
1. Use only standard SQL constructs.
2. Use only set based solutions.
3. Can be implemented as self manageable using triggers.
4. Gives better performance because it uses Numeric operations instead of string operations.

Cons
1. For larger Hierarchies, you may encounter out of range errors because the Path value grows in an exponential rate.
Still you can replace the bigint with a larger datatype like numeric and replace the % operator with division operator and overcome the issue.

AS I mentioned earlier, this model is still in its evolving face. So as always, your feedback is highly appreciated.