Query challenge

Is this problem really different from "Hierarchical weighted total" -- hierarchy in this case collapsed to a linearly ordered sequence of dates? We have "part assembly"

grandchild(qty=1000) ----> child(qty=200) -----> parent(qty=500) ---->...

The links are weighed with interest rates, so that amended picture is:

grandchild(qty=1000) --1.05--> child(qty=200) ---1.032--> parent(qty=500) ---->...

The "Hierarchical weighted total" problem is to calculate aggregated qty at the root, and the "connect by" really shines for that kind of queries. Yet, the recursive with gives even more elegant answer.

================= Extract from "SQL Design patterns" ===============

Hierarchical Weighted Total

Before exploring aggregation on graphs, let’s have a quick look to aggregation on trees. Aggregation on trees is much simpler and has a designated name: hierarchical total. A typical query is
"Find combined salary of all the employees under (direct and indirect) supervision of King."
This query, however, has no inherent complexity, and effectively reduces to familiar task of finding a set all node’s descendants.

In graph context, the hierarchical total query is commonly referred to as bill of materials (BOM). Consider bicycle parts assembly

Part SubPart Quantity
Bicycle Wheel 2
Wheel Reflector 2
Bicycle Frame 1
Frame Reflector 2

Parts with the same name are assumed to be identical. They are modeled as nodes in an (acyclic directed) graph. The edges specify the construction flow:
1. Assemble each wheel from the required parts (including reflectors).
2. Assemble frame from the required components (including reflectors).
3. Assemble bicycle from the required parts (including frame and wheels).

Suppose we want to order the total list of parts for bike assembly. How do we calculate each part quantity? Unlike hierarchical total for a tree we can’t just add the quantities, as they multiply along each path.

Figure 6.11: Bicycle assembly graph. The total number of reflector parts should be calculated as the sum of parts aggregated along each path. The path /Bicycle/Wheel/Reflector contributes to 2*2=4 parts: bicycle has 2 wheels, each wheel has 2 reflectors. Likewise, the path /Bicycle/Frame/Reflector contribute to 1*2=2 more parts.

Therefore, there are two levels of aggregation here, multiplication of the quantities along each path, and summation along each alternative path.

----------------- Aggregation on Graphs (soapbox) -----------------
Two levels of aggregation fit naturally into in graphs queries. Consider finding a shortest path between two nodes. First, we add the distances along each path, and then we choose a path with minimal length.

Double aggregation is not something unique to graph queries, however. Consider
"Find the sum of the salaries grouped by department. Select maximum of them."
When expressing such a query in SQL, we accommodate the first sentence as an inner subquery inside the outer query corresponding to the second sentence

select max(salaryExpences) from (
select deptno, sum(sal) salaryExpenses
from Emp
group by dept
)
------------------------(end of soapbox)-------------------------

Hierarchical weighted total query has the same structure. The first level of aggregation where we join edges into paths is analogous to the group by subquery from the salary expense query. Formally, it is a transitive closure, which is enhanced with additional aggregates, or generalized transitive closure.

Figure 6.12: Generalized transitive closure. There are several aggregates naturally associated with each path: the first edge, the last edge, the path length, or any aggregate on the edge weights.

Let’s suggest some hypothetical SQL syntax for generalized transitive closure
select distinct first(Part), last(SubPart), product (Quantity)
from AssemblyEdges
connect by prior Part = later SubPart
Unfamiliar syntax requires clarification:
§ The product is a non-standard aggregate from chapter 4.
§ The first and last refer to the first and last edges in the path, correspondingly. These aggregates are unique to ordered structures such as (directed) graphs.
§ Although we didn’t use it in the example, concatenating edge labels into a string is one more natural aggregation function, which is unique to graphs. The list aggregate function is a standard way to accommodates it.
§ The later keyword is just a syntactic sugar fixing apparent asymmetry caused by the prior keyword.
§ There is no start with clause, which is, in fact, redundant. It is an outer query where we’ll restrict paths to those originated in the ‘Bicycle’ node.

The generalized transitive closure query is enveloped with second level of aggregation, which is accomplished by standard means
select leaf, sum(factoredQuantity) from (
select product(Quantity) factoredQuantity,
first(Part) root, last(SubPart) leaf
from AssemblyEdges
connect by prior Part = later SubPart
) where root = ‘Bicycle’
group by leaf

Enough theory, what do we do in real world to implement an aggregated weighted total query? Let’s start with Oracle, because the proposed syntax for generalized transitive closure resembles Oracle connect by.

First, we have to be able to refer to the first and the last edges in the path

select connect_by_root(Part) root, SubPart leaf
from AssemblyEdges
connect by prior Part = SubPart

Unlike our fictional syntax, Oracle treats edges in the path asymmetrically. Any column from the AssemblyEdges table is assumed to (implicitly) refer to the last edge. This design dates back to version 7. The connect_by_root function referring to the first edge has been added in version 10. It is remarkable how this, essentially ad-hock design proved to be successful in practice.

Next, Oracle syntax has several more path aggregate functions:
1. level – the length of the path.
2. sys_connect_by_path – which is essentially the list aggregate in our fictitious syntax.
3. connect_by_is_leaf – an indicator if there is no paths which contain the current path as a prefix.
4. connect_by_is_cycle – an indicator if the first edge is adjacent to the last.

Unfortunately, we need an aggregate which is a product of edge weights, and not a string which is a concatenation of weights produced by sys_connect_by_path. You might be tempted to hack a function which accepts a string of the edge weights, parses it, and returns the required aggregate value.

Nah, too easy! Can we solve the problem without coding a function (even a simple one)? Yes we can, although this solution would hardly be more efficient. The critical idea is representing any path in the graph as a concatenation of three paths:

§ a prefix path from the start node to some intermediate node i
§ a path consisting of a single weighted edge (i,j)
§ a postfix path from the node i to the end node

Figure 6.13: A path from node x to node y is a composition of the path from node x to node i, the edge (i, j), and the path from j to y. The edge (i, j) can be positioned anywhere along the path from x to y.
Then, we freeze the path from x to y, while interpreting the edge (i,j) as a variable. All we need to do is aggregating the weights of all those edges.

Let’s assemble the solution piece by piece. First, all the paths in the graphs are expressed as
with TClosure as (
select distinct connect_by_root(Part) x, SubPart y,
sys_connect_by_path('['||Part||','||SubPart||'>',' ') path
from AssemblyEdges
connect by nocycle Part=prior SubPart
union
select Part, Part, '' from AssemblyEdges
union
select SubPart, SubPart, '' from AssemblyEdges
) …
This is essentially reflexive transitive closure relation enhanced with the path column. Paths are strings of concatenated edges; each edge is sugarcoated into '['||Part||','||SubPart||'>', which helps visual perception, but is inessential for the solution.

Next, we join two paths and intermediate edge together, and group by paths
… , PathQuantities as (
select t1.x, t2.y,
t1.p||' ['||e.Part||','||e.SubPart||'>'||t2.p,
product(Quantity) Quantity
from TClosure t1, AssemblyEdges e, TClosure t2
where t1.y = e.Part and e.SubPart = t2.x
group by t1.x, t2.y, t1.p||' ['||e.Part||','||e.SubPart||'>'||t2.p
) …
There we have all the paths with quantities aggregated along them. Let’s group the paths by the first and last node in the path while adding the quantities
select x, y, sum(Quantity)
from PathQuantities
group by x, y
This query is almost final, as it needs only a minor touch: restricting the node x to ‘Bicycle’ and interpreting the y column as a Part in the assembly
select y Part, sum(Quantity)
from PathQuantities
where x = ‘Bicycle’
group by x, y

Let’s move on to recursive SQL solution. It turns out to be quite satisfactory
with TCAssembly as (
select Part, SubPart, Quantity AS factoredQuantity
from AssemblyEdges
where Part = ‘Bicycle’
union all
select te.Part, e.SubPart, e.Quantity * te.factoredQuantity
from TCAssembly te, AssemblyEdges e
where te.SubPart = e.Part
) select SubPart, sum(Quantity) from TCAssembly
group by SubPart

The most important, it accommodated the inner aggregation with non-standard aggregate effortlessly! Second, the cycle detection issue that plagued recursive SQL in the section on transitive closure is not a problem for directed acyclic graphs.