Trees. They're everywhere in nature. But they're also common in your data. Such as
your company's hierarchy or your family tree. But when you store these
hierarchies in your database it can be hard to tell where each row fits in the tree.
Luckily all you need is a bit of SQL magic to turn your rows into a tree!
It's your dear old grandma's birthday coming up. To celebrate you want
to draw out a family tree for her showing all her children; your parents, aunts, and
uncles; their children you, your siblings, and cousins; their children and so on. To
help with this you've got details of all your family members stored in a database table.
But, run a standard query against this and it's not obvious which
generation each person belongs to and who their parents are. You can get around
this by joining the table to itself. Over and over and over again for each new generation.
But this is a paint to write. And, if you want to redraw your family
tree starting with your great-great-great great-great
great great grandma, you've got to rewrite your SQL query. You can
overcome these problems using hierarchical operators. But before we
dive into the SQL, some terminology.
In the real world a tree starts with roots
and grows out to its leaves. A data tree is the same. The starting points are the
roots, the ends the leaves. Each point in between is a node. And, like a family tree,
the direct ancestor of a node is its parent and it's direct descendants its
children. A root is a node with no parent and a leaf is one with no children.
Back to the SQL!
To write your query you need to know how to identify which rows
in the roots and which columns contain the relationships between parents and
children. Your grandma is the start of the tree. So she's the root. And the
relationship between parents and children is just like in real life; the
mother or father of each person is the parent of that child. Armed with this
information you can now start to write your SQL query in Oracle Database. But
first you need to choose between the proprietary connect my clause. Or the ANSI
compatible recursive with.
In both cases you want to begin with the root, your grandma.
With connect by select her in the start with clause. Using with you'll
have a normal select to get this row. As in real life each person's parent is
their mother or father from the previous generation. So you need to check these
columns against the family member from the previous level. Using Oracle syntax
you can access this with a keyword PRIOR. So in the connect by clause you need to
check in the prior person matches the current mother or father. Recursive with
is more complicated. You need to union all the subquery with the initial query
to fetch your granny. Then join this back to the original family table where
the person from the subquery matches the mother or father.
At this point both methods have built your tree.
But the results look like you've just selected
from the table. It's not obvious which rows are the children, grandchildren, or
great-grandchildren. To show this you need to add in which generation each
person belongs to and indent the rows appropriately. With connect by this is
easy the pseudo-column level shows which position you are in the hierarchy. This
starts at 1 and then increments for each new set of children in the tree.
So granny is at level 1. Your parents, aunts, and uncles level 2.
You, your siblings, and cousins are level 3, and so on. You can then use this to pad
spaces before the names so you can easily see who is in each generation
Recursive with doesn't have a level function built in. But this is easy
enough to do manually.
Just select one as the level in the base query.
Then, in the recursive part, increment the level
and add spaces before the names.
Now it's easy to see which generation each person belongs to.
But the order may be a bit jumbled.
Usually you want to sort siblings from oldest to youngest and show all the
person's children next to them in the tree.
And it's here that recursive with as a big advantage over connect by. You can
specify how you want to walk down a tree. Depth-first or breadth-first.
With depth-first search you start at the root then keep going all the way down until
you hit a leaf. You then go back up until you find a node with a child you've not
visited before. Follow that down until you find the next leaf, and so on. So
you're always going down as far as you can. On the other hand breadth-first
search visits all nodes at the same level before going down to the next. So
it starts with your granny. Then gets all her children; your parents, aunts, and
uncles. Then all their children and so on.
This search type can affect how quickly
the SQL runs or even how the query works. But for now it allows you to
specify how to sort your results. To show eldest children first, immediately
followed by their children you want depth-first search ordered by birth date.
Doing this using recursive with this is easy as sticking this after the subquery.
You also need to define a column showing which order the database visits
the rows. This goes in the set clause. To guarantee you display the rows in
this sequence place this column in your order by.
Sadly connect by doesn't have
an option to specify how you want to search the tree. It displays rows in the
order it accesses them. Adding an order by destroys this sequence.
Luckily order by has a siblings clause which allows you to specify which order
to show rows in the same generation. So to get the same effect order siblings by birth date.
So now you built your family tree showing all your granny's blood
descendants. But real family trees usually include both parents of every
child. Trying to do this adds a lot of complexity to your SQL. For example, if
you try and add grandpa in as a root you build your whole family tree twice,
duplicating everyone else in the family.
This is because in data terms each node
in a tree has at most one parent. But, of course, in real life everyone has two
parents. So a family tree isn't a real tree. It's a directed acyclic graph!
Bear this in mind if you're trying to draw out family trees using SQL. You're
best off following the descendants down one gender, for example the mothers, then
joining the fathers in as appropriate.
So now we built your family tree. But
there's still one important aspect of trees we need to cover off:
Loops!
Unless we discover time travel it's impossible to be your own ancestor. So you can't
have a loop in a family tree. But they are possible in other data structures.
If a loop does exist in your hierarchy, as you walk along it you'll eventually get
stuck in an infinite loop. Luckily the database can detect these
and stop the query. Unluckily it will error out when it does, leaving you with
no results. You can avoid this problem using cycle detection. With connect by
just add the nocycle keyword after connect by and Oracle Database will bail
out if it comes back to the same row. Doing the same using ANSI-style is more
typing, but also as more power!
For example say you've arranged your bricks
in a tree with largest at the top and smallest at the bottom. But you've
accidentally pointed one of the leaves back to another branch in the tree.
There's no loops. But this node has two parents. So as you walk down the tree
you'll reach it twice, meaning you'll get two copies of all these bricks in your
results. Something you want to avoid. You know bricks gets smaller as you go down
the tree. So if you've seen a brick of the same size you've seen on the path so
far you've got a problem. The cycle clause allows you to detect this and stop processing.
To use the cycle clause lists the columns you want to check for
duplicates. Then define a new column with the value to set when the database sees
a repeated value and, a default if it doesn't.
So that was a quick overview of how to build hierarchies using SQL.
There are also a host of functions you can use with connect by to find things like which
rows are the leaves, or the ancestors of a row, and so on. Check the links in the
description for more details on these and how to emulate these functions using
recursive with. Just remember: when building trees watch out for loops and
make sure you define the roots. Otherwise you'll build a new tree for every row in you table!
Thanks for watching!
If you enjoyed this and want to watch more
SQL videos click the links on screen now