Everyone who studies data structures and algorithms would come across
tree data structure and related algorithms at some point or the other.
The tree traversal algorithms provide the ability to do bottom-up
aggregation, top-down propagation, breadth first, depth first processing
and so on. While SQL provides a standard to process recursive data using
WITH RECURSIVE CTE clause, doing any complex analysis on recursive
SQL is like using assembly language to build a web page.
As much as SQL Frames is a fan of
SQL, this is one of the use cases
where it has to breakaway from the limitations of it.
Recursive relational data
Data modeling always involves identifying relationships among data. Most of the time the relationships are between two different tables but occasionally they happen to be in the same table. Such relations are self-referencing. A common example is the employee-manager relationship where a manager is also an employee and hence the employee table would have two records one for the manager and one for the employee and the employee record also has a foreign key pointing to the employee record of the manager.
Recursive data analytics
Let's consider the requirement of computing the payroll expenses of a manager for that person and anyone reporting directly or indirectly to that person. This is a tree-traversal bottom-up aggregation problem starting with that person as the root of the tree.
In a tree-traversal, there is an implicit stack that keeps track of the nodes that have been visited so far and hence when performing the bottom-up aggregation each intermediate node is accessed twice, once to traverse down and once to aggregate bottom-up. Note that it is possible to maintain an accumulator while traversing down and not do bottom up aggregating. However, if the totals have to be computed for each of the intermediate nodes, then the bottom-up aggregation is the only way.
When processing data using
WITH RECURSIVE CTE expression, each row is visited
only once. As a result, doing bottom-up aggregation requires using two
WITH RECURSIVE CTEs
as described in this
stackoverflow answer (which btw seem to work for fixed depth trees). One to identify
all the nodes from within a given root and another to do the rollup. This makes
the queries both complex and slow.
Flattening recursive data
One technique to deal with recursive hierarchies is to flatten the tree-path (root to the node) for each record. For example, a management hierarchy with at most 7 levels deep will have to maintain 7 columns (mgr1, mgr2, ...) and materialize the path information in these columns for each row.
It may be likely possible to compute this in one go and materialize the entire tree by inserting into a new table with corresponding paths materialized but only if the number of levels is assumed to be fixed. But if the levels can be dynamic and no way to know upfront, then the only way I can think of is to do it procedurally.
Flattening in SQL Frames
Today I am happy to announce that SQL Frames has added a new
df.wrangle.flatten API to
create the flattened columns when computing a DataFrame. The hierarchy can have variable depths.
See the documentation for more details.
SQL Frames provides integrated UI to the various types of DataFrames. The flattened recursive
data can then be put together into hierarchical format using the grouping levels based on the
flattened columns acting as the groups. The
df.hdf().fh() API can be used to creating the
grouping columns dynamically based on the max depth of the tree in the source data.
SQL Frames continues to solve real world hard enterprise problems so your analytics can be elevated to the next level. Reach out to me to learn how SQL Frames can help with your interactive visualization needs.