Have you ever tried to store hierarchies in SQL. That’s easy but, have you ever tried to do some calculation in that hierarchy. That’s bit harder.
Let’s take example situation that I have some hierarchy and some cost that should be allocated in that hierarchy. Let assume that you have an HierarchyItem that could have another item many other HierarchyItems as child of it and many parents also. Then you could have some cost allocated to that hierarchy let’s say DirectCost. You share this according to weight between the HierarchyItem connection say ConnectionShare.
Here is the class diagram of this.
So HierarchyItem cost is sum of direct costs and cost of items child according to share ratios.
Example if have file server and it costs are 1000 euros. Application A file usage is 80GB and Application B file usage is 120GB:
Application A has costs from file server (80 / (80 + 120)) * 1000 euros = 400 euros
Application B has costs from file server (120 / (80 + 120)) * 1000 euros = 600 euros
In this easily solved with recursion as flows (Detailed code in C#):
public float GetCost(string costType)
{
float retval = 0;
//Calculate first all direct costs
foreach(DirectCost directCost in DirectCosts)
{
if(directCost.CostType.Equals(costType))
retval += directCost.Value;
}
//Add all child costs to this
foreach(ConnectionShare child in ChildConnectionShares)
{
retval += child.GetChildCost(costType);
}
return retval;
}
Problem converting this to SQL is that you can’t really do recursion in SQL. So the solution in my case was to simulate the cost in time to time. Simulation is a good solution if you don’t data bee accurate all the time.
So if you think about how you would calculate this by hand. You just would start calculating this from the bottom. First calculate those items that do not have any child’s. After that you would calculate items which child’s has been calculated all ready. And the just iterate the process.
So SQL solution comes from the same idea. First calculate all those items that have no childs and after that calculate those items which child’s has been calculated. Or if I be more precise you can calculate those items where your child count is the same as calculated child count.
So if I would have an tables HierarchyItem, ConnectionShare, DirectCost and HierarchyItemCosts.
HierarchyItem you would all the hierarchy items.
ConnectionShare would include all connections between HierarchyItems
DirectCost Table would include all direct cost related to HierarchyItem.
HierarchyItemCosts would store all the simulated costs.
Let’s assume that we already have some data in there. And go step by step…
1. Find all those items that can be calculated - those items where your child count is the same as calculated child count.
SELECT Parent.ID
FROM HierarchyItem Parent LEFT JOIN ConnectionShare Child
ON Parent.ID = Child.ParentID
LEFT JOIN HierarchyItemCost CalulcatedItems
ON Child.ChildID = CalulcatedItems.HierarchyItemID
GROUP BY Parent.ID
HAVING COUNT(Child.ChildID) = COUNT(CalulcatedItems.HierarchyItemID)
2. Now Select all the items that should be calculated
SELECT HI.ID
FROM HierarchyItem HI
WHERE HI.ID IN (Query from the step 1)
3. Add all CostTypes to calculation
SELECT HI.ID,
TmpCostType. CostType
FROM HierarchyItem HI CROSS JOIN
(SELECT DISTINCT CostType FROM DirectCost) TmpCostType
WHERE HI.ID IN (Query from the step 1)
4. Add the direct cost calculation
SELECT HI.ID,
TmpCostType. CostType,
(SELECT COALESCE(SUM(Value),0)
FROM DirectCost
WHERE HierarchyItemID = HI.ID
AND CostType = TmpCostType.CostType)
FROM HierarchyItem HI CROSS JOIN
(SELECT DISTINCT CostType FROM DirectCost) TmpCostType
WHERE HI.ID IN (Query from the step 1)
5. Add the child costs to calculation and helpper view.
CREATE VIEW HierarchyItemTotalShare AS
SELECT HI.ID,COALESCE(SUM(Share),0)
FROM HierarchyItem HI LEFT JOIN ConnectionShare CS
ON HI.ID = CS.ChildID
GROUP BY HI.ID
SELECT COALESCE(SUM(Child.Value * (Relation.Share/TotalShare.TotalShare) ),0)
FROM HierarchyItemCost Child JOIN ConnectionShare Relation
ON Child.HierarchyItemID = Relation.ChildID
JOIN HierarchyItemTotalShare TotalShare
ON Child.HierarchyItemID = TotalShare.ID
WHERE Relation.ParentID = HI.ID
AND Child.CostType = TmpCostType.CostType
AND TotalShare.TotalShare <> 0
6. The final insert statement that is run until all row’s have been instered.
INSERT INTO HierarchyItemCost (HierarchyItemID,CostType,Value)
SELECT HI.ID,
TmpCostType.CostType,
--Items cost is sum of direct cost +
(SELECT COALESCE(SUM(Value),0) FROM DirectCost WHERE HierarchyItemID = HI.ID AND CostType = TmpCostType.CostType)
+
--Sum of all child cost acording to share
(SELECT COALESCE(SUM(Child.Value * (Relation.Share/TotalShare.TotalShare) ),0)
FROM HierarchyItemCost Child JOIN ConnectionShare Relation
ON Child.HierarchyItemID = Relation.ChildID
JOIN HierarchyItemTotalShare TotalShare
ON Child.HierarchyItemID = TotalShare.ID
WHERE Relation.ParentID = HI.ID AND Child.CostType = TmpCostType.CostType AND TotalShare.TotalShare <> 0)
FROM HierarchyItem HI CROSS JOIN (SELECT DISTINCT CostType FROM DirectCost) TmpCostType
WHERE HI.ID IN
–All those HierarchyItems witch childs has been calculated
(SELECT Parent.ID
FROM HierarchyItem Parent LEFT JOIN ConnectionShare Child
ON Parent.ID = Child.ParentID
LEFT JOIN HierarchyItemCost CalulcatedItems
ON Child.ChildID = CalulcatedItems.HierarchyItemID
GROUP BY Parent.ID
HAVING COUNT(Child.ChildID) = COUNT(CalulcatedItems.HierarchyItemID))
–Only calculate every item once
AND HI.ID NOT IN (SELECT HierarchyItemID FROM HierarchyItemCost)
Voilá!
If you have SqlServer you can test the solution with this script.
