Recap
In the first post of this series, I walked through the basic ideas of what constitutes a graph, and in the second post I discussed a particular kind of graph called a directed acyclical graph (DAG), providing a handful of examples from the world of data engineering along with an attempt to disambiguate – and expand – the meaning of what a DAG is.
To briefly recap the important points discussed so far:
- A graph consists of one or more nodes.
- Nodes are related to other nodes via one or more edges.
- Nodes that that can reach themselves again (by traversing the graph in a single direction) indicate the graph has a cycle.
- A given edge can be directed or undirected.
- Any set of nodes that can’t reach other sets of nodes are a subgraph.
- Nodes and edges can have attributes, including numerical attributes (usually called weights in formal graph theory), that are often leveraged when executing more advanced graph algorithms/analytics.
- Graphs for which all edges are directed, and which have no cycles, are referred to as directed acyclical graphs (DAGs).
In the following post, we’re going to further constrain the definition of a DAG to arrive at the definition of a hierarchy and then discuss some of the associated nuances, i.e. when it comes to modelling and consuming hierarchical data, including a few additional attributes that “fall out” from the definition of a hierarchy (that aren’t particularly relevant to more generic graph structures).
Hierarchies
In order to flesh out what constitutes a hierarchy, recall from the first post in this series that it’s common to refer to a pair of nodes that are related by a directed edge as either “parent/child” nodes or “predecessor/successor” nodes. For simplicity, we’ll stick with “parent/child” for the rest of this discussion.
Now, as you may have noticed, we didn’t really incorporate this vernacular in our discussion of DAGs. Why? Well, the family analogy (parent/child) breaks down rather quickly when your realise that it’s possible, and actually quite common, for a “child” node to have many “parent” nodes (which doesn’t jibe with our intuition about parents and children). So, if anything, DAGs should probably discussed with the terms “predecessor” and “successor” nodes.
When it comes to hierarchies, the parent/child analogy becomes more useful. The distinguishing characteristic for a hierarchy, compared to a DAG, is that a node only ever has one — and only one — parent node. (Conversely, a given parent node can have multiple child nodes.)
(Note: there are edge cases where a node can potentially have more than one parent, but such cases are the exceptions, and they need to handled on a case-by-case basis. Perhaps in a future post I’ll spend time discussing these cases in more detail, but for our purposes, and in light of the expected cardinality of dimensional modelling (i.e. many-to-one from fact table to dimension tables), we’re going to move forward with the expectation that any/all hierarchies should always respect this relationship, i.e. a child node only ever having a single parent node.)
Now, the parent/child analogy is still a bit limited. Obviously in real life, children have only two biological parents (and clearly can have multiple step parents, adopted parents, etc.), whereas with our analogy, we’re restricting a child node to only one parent node, but otherwise you get the point.
Also, as an FYI, a more formal term for this data structure from computer science would be a “tree” which indicates a similar analogy where any given branch stems from a single other branch (or trunk).
(This analogy will play an important role later in our discussion.)
Here’s a basic illustration of a hierarchy:
Example hierarchy of… alphabet soup?
As you can see, it’s still very much a graph with:
- seven nodes
- six edges (directed)
- no cycles
- each node only has a single parent
So far so good.
I mentioned earlier that even though hierarchies have more constraints, i.e. they’re more limited in what they can represent compared to generic graphs, they nonetheless yield additional attributes. What do I mean by that?
Consider the following two points.
Firstly, because I have:
- a single starting point (i.e. the very first parent node),
- only directed edges,
- no cycles,
a hierarchy therefore allows me to measure the “distance” of any node in the hierarchy by how many edges away from the starting node (or “root node” as we’ll later call it) it is. This measurement is typically referred to as which level a particular node is on (analogous to measuring how high up in a building you are by what level you’re on. And much like the British/American confusion around which floor constitutes the “first” floor, you’ll also have to decide whether you index your root node at level 0 or 1).
(Side tangent: you can, of course, measure the number of edges between any two nodes in a generic graph, but unlike with hierarchies, there’s not a single value for level per node but rather N-1 such values, i.e. since you can measure the number of edges between a given node and all other nodes in the same subgraph. Storing such information for all nodes introduce exponential storage requirements, i.e. O(n²), and offers very little technical or business value. Hence level is a fairly meaningless attribute in the context of generic graphs or DAGs.)
Secondly, because you can now refer to multiple “sibling” nodes under a single parent, you can describe the sort order of each sibling node. In other words, you define a particular sort order for all the related sibling nodes under a particular parent node. (This is another example of an attribute that is meaningful for hierarchies, but really doesn’t make much sense in the context of a generic graph or DAG.)
A classic example of this are the various lines in a financial statement such as a profit-and-loss statement:
Financial reports are a very common use case in the world of BI, and it’s clearly extremely important to ensure that your reports display the various lines of your report in the correct order, defined by the sort order of each node in your financial statement hierarchy. (Note in the image above how this sort order is defined at each level.)
Real quick, this sort order attribute doesn’t have a canonical name in the world of BI as such. But for a variety of reasons, my preference is “ordinal position”, so we’ll stick with that for now.
(Also, for folks new to hierarchies, you might find it a worthwhile exercise to analyse the financial statement structure above as a hierarchy: How many nodes does it have? How many edges? How many levels? How many child nodes per parent? How might you actually model this data in a relational format? We’ll come back to this in a bit…)
Two more points I’d like to make, as we work towards a generic/reusable data model for hierarchies:
- This should be obvious, but there are many different types of hierarchies, such as (in an enterprise context): profit centre hierarchies, cost centre hierarchies, WBS structure hierarchies, cost element hierarchies, financial statement hierarchies, and the list goes on.
- A particular hierarchy type might have multiple hierarchy instances. For example, a time dimension is actually a hierarchy, and almost all large enterprises care about tracking metrics along both the calendar year as well as the fiscal year, each of which is its own hierarchy. (We’ll circle back to time dimension hierarchies here in a bit.)
And lastly, let me introduce a bit more vernacular specific to hierarchies:
- A given hierarchy has one (and only one) root node, which is the only node that has children but no parents.
- Any nodes that have parent and child nodes are called intermediate or inner nodes.
- Any nodes that have parent but no child nodes themselves are called leaf nodes.
A colorful alphabet soup hierarchy. Very academic.
(If you like to consider edges cases, keep in mind you could technically have a hierarchy of a single node, which would mean it’s simultaneously all three types. It’s also technically possible to have a leaf node at level 2, which would mean that particular “branch” of the hierarchy has no inner nodes.)
As you can see, the world of data warehousing and BI has managed to mix metaphors by using terminology from the idea of a tree data structure (with things like roots, leaves and branches), and mixing it up with the family analogy (i.e. parents, children, sibling nodes, etc.) of hierarchies.
How fun and entirely not confusing at all.
Anyways.
I’d say we’re ready for our generic hierarchy data model. Rather than write the SQL, I’m just going to provide a poor man’s data dictionary, especially given that your naming conventions (and probably also data types) may well differ.
Basic data dictionary for a hierarchy table.
And just to finish up the example from earlier, here’s what that data might look like (primary key fields highlighted in green):
Sample hierarchy.
It’s worth taking a moment to talk through this a bit.
- First of all, I’d suggest playing with some sample data, and sorting by the different columns, to familiarise yourself even more with this data model. For example, you could sort by NODE_TYPE to quickly find all the INNER nodes and LEAF nodes. You could sort by LEVEL and then ORDINAL_POSITION to “read” the hierarchy as you would with its visualised equivalent, i.e. top-to-bottom, left-to-right.
- Note that root nodes are defined as those records for which PARENT_NODE is NULL. This is a commonly accepted convention, especially for query languages that can parse parent-child hierarchies natively (such as MDX, which we’ll come back to), so I’d highly suggest adopting it (especially if you’re modeling in a strictly OLAP context), but there’s clearly no “formal” reason, i.e. from relational theory or anything else, that requires this.
- If this were a data model for a generic graph or even a DAG, we would have to include PARENT_NODE as part of the primary key, since a node could have more than one parent (er, predecessor). However, since hierarchy nodes only have a single parent node, we don’t need to do this, and in fact, we don’t want to do this (as, from a data quality perspective, it would let us insert records with multiple parent records, which breaks the definition set forth previously for hierarchies, and could lead to incorrect results in our BI queries by inflating metrics when joining hierarchies to fact tables due to M:N join cardinality instead of M:1).
- Be aware that the child nodes in a hierarchy are often just referred to as “nodes”, whereas parent nodes are always referred to as parent nodes.
- ORDINAL_POSITION might be a bit confusing at first glance, because again, it only defines the sort order for a given node compared to its immediate siblings (again, consider the financial statement hierarchy structure that we glanced at earlier. Revenue has to always come before Expenses at the top level, but underneath revenue, it’s important that its constituent child records are also displayed in the right order according to accounting expectations, i.e. “License” coming before “Support”). Now, sorting data only requires that sequential values are larger than previous values, so you could technically use a typical sequence for this column, i.e. each record in the table increasing by 1, which would give us 1, 2, 3… up to 7. But that kind of implies that all of the records are somehow related to each other when it comes to sorting (which they’re not — sort order only makes sense amongst sibling nodes), and if you casually glance at the data, you could get the impression that some records are missing (i.e. if the first node among a set of siblings starts with the value 7 for example).
- Speaking of sorting hierarchy records — in many cases, such as with GL Account hierarchies, the sort order is defined by the business in a dedicated column, and almost always used in any reporting. However, in other cases, a sort order doesn’t really matter. Think of a typical org chart. If you were looking at expenses charged per department (or employee), you often don’t really care about sort order of the hierarchy, as long as the data is grouped properly (i.e. you can see all of the employees per department, all departments per division, etc.). And lastly, you often only care about the alphanumeric sort order, such as with your time dimension. We’ll get to the time dimension shortly, but it’s absolute a hierarchy in the strict definition, and you’re almost always going to sort your days by their intrinsic value (assuming you have your days modeled properly, i.e. don’t forget your padded zeroes for any columns you use for sorting! Otherwise the value 11 might come before the value 2.)
- Ok, very last comment about sorting… you obviously could have more than one sort column for some reason, and you could also join your nodes to some other master data table, let’s say, which might include yet other columns that you’d want to sort on for some reason…
Before I forget to mention, you might hear this structure referred to as an “adjacency list”, which is another technical term from graph theory. Technically, an adjacency list maps a single node to *all* of its adjacent nodes, so in the case of hierarchies, a single row would show a parent node mappes to *all* of its children nodes (in an array, for example). In practice though, folks often refer to the parent/child data model above as an adjacency list, even though each child node gets its own row. Just FYI.
In Summary
We’ve now gone through graphs, DAGs, and hierarchies, and we’ve walked through a basic, scalable data model for parent-child hierarchies and discussed some of the nuances of this model.
In the next post, we’ll review a few more considerations when it comes to data modeling, such as:
- Discuss data quality implications of hierarchies.
- Disambiguate some confusion around terms like “parent/child”
- Discuss two major patterns for consuming hierarchies, i.e. schema-on-read compared to schema-on-write.
- The reason hierarchies are so prevalent in BI in terms of how human cognition goes about processing information.
