Inheriting Values in SQL

Imagine a situation where you have hierarchical data with various values and you wanted to inherit values from ancestors if a given level in the hierarchy had null values. So if a level had a null value, it could inherit that missing value from the parent and if the parent didn’t have a value, the grandparent etc. etc. updwards until we reach the root. How would you do it?  Well in this article I’ll explore a few approaches.

Firstly let’s create a sample table of hierarchical data with a number, string and date field, with some levels missing data.

-- Create a table to test inheritance with

create table data as 
with the_data (id, parent_id, numval, strval, dateval) as (
  select 0, to_number(null), 2   , 'A'  , to_date(null)     from dual union all
  select 1, 0              , null, 'B'  , null              from dual union all
  select 2, 1              , 1   , null , date '1985-05-22' from dual union all
  select 3, 2              , null, null , date '1992-08-07' from dual union all
  select 4, 3              , 10  , 'C'  , null              from dual
)
select * from the_data; 

Now I’ll write a treewalk starting from the root node (parent_id is null) to the leaf nodes, I’ll include the path of the recursion, to show the family relationships.

select d.*, sys_connect_by_path(id, '/') path
from data d
start with parent_id is null
connect by parent_id = prior id;

         ID  PARENT_ID     NUMVAL STRVAL DATEVAL   PATH                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
----------- ---------- ---------- ------ --------- ----------------
          0                     2 A                /0                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              
          1          0            B                /0/1                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
          2          1          1        22-MAY-85 /0/1/2                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          
          3          2                   07-AUG-92 /0/1/2/3                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
          4          3         10 C                /0/1/2/3/4                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      

5 rows selected.

We can see

  • ID = 1, 3 don’t have a NUMVAL
  • ID = 2, 3 don’t have a STRVAL
  • ID = 0, 1, 4 don’t have a DATEVAL

So applying our desired inheritance rules, we want a solution which gives us this…

         ID  PARENT_ID     NUMVAL STRVAL DATEVAL  
----------- ---------- ---------- ------ ---------
          0                     2 A               
          1          0          2 B               
          2          1          1 B      22-MAY-85
          3          2          1 B      07-AUG-92
          4          3         10 C      07-AUG-92

So, for example,

  • ID = 1, would inherit its parent’s NUMVAL value, because its own value was null.
  • ID = 3 would inherit its grandparent’s STRVAL value, because neither itself or its parent has a value.

Using sys_connect_by_path

Well we could use sys_connect_by_path to build a list of values in the hierarchy and then just take the last one. sys_connect_by_path is a function specific to treewalks which delimiter appends information from each level.  This is how we generated the path in the query above.  Let’s have a look at what I mean.

with treewalk as (
  select d.*, sys_connect_by_path(id, '/') path,
         rtrim(sys_connect_by_path(numval,  '/'), '/') numvalpath,
         rtrim(sys_connect_by_path(strval,  '/'), '/') strvalpath,
         rtrim(sys_connect_by_path(to_char(dateval, 'ddmmyyyy'), '/'), '/') datevalpath       
  from data d
  start with parent_id is null
  connect by parent_id = prior id
)
select *
from treewalk;

         ID  PARENT_ID     NUMVAL STRVAL DATEVAL   PATH            NUMVALPATH      STRVALPATH      DATEVALPATH              
----------- ---------- ---------- ------ --------- --------------- --------------- --------------- -------------------------
          0                     2 A                /0              /2              /A                                       
          1          0            B                /0/1            /2              /A/B                                     
          2          1          1        22-MAY-85 /0/1/2          /2//1           /A/B            ///22051985              
          3          2                   07-AUG-92 /0/1/2/3        /2//1           /A/B            ///22051985/07081992     
          4          3         10 C                /0/1/2/3/4      /2//1//10       /A/B///C        ///22051985/07081992     

5 rows selected.

From the paths, we’d just need to take the last value after the delimiter (/) to get the inherited value and then convert the result back to the type it was originally (because sys_connect_by_path works  on strings).

Like this…

with treewalk as (
  select d.*, sys_connect_by_path(id, '/') path,
         rtrim(sys_connect_by_path(numval,  '/'), '/') numvalpath, -- Remove last '/'
         rtrim(sys_connect_by_path(strval,  '/'), '/') strvalpath,
         rtrim(sys_connect_by_path(to_char(dateval, 'ddmmyyyy'), '/'), '/') datevalpath       
  from data d
  start with parent_id is null
  connect by parent_id = prior id
)
select id, parent_id, 
       to_number(substr(numvalpath, instr(numvalpath, '/', -1) + 1)) numval,
       substr(strvalpath, instr(strvalpath, '/', -1) + 1) strval,
       to_date(substr(datevalpath, instr(datevalpath, '/', -1) + 1), 'ddmmyyyy') dateval
from treewalk

         ID  PARENT_ID     NUMVAL STRVAL    DATEVAL
----------- ---------- ---------- --------- ----------
          0                     2 A                   
          1          0          2 B                   
          2          1          1 B         22-MAY-85 
          3          2          1 B         07-AUG-92 
          4          3         10 C         07-AUG-92 

5 rows selected.

Note : instr(numvalpath, ‘/’, -1) means find position of last ‘/ ‘ in string

Ok, we got the correct result but it’s a bit clunky isn’t it?  Especially the string slicing and type conversion.  There’s also some limitations with sys_connect_by_path in that it only supports paths up to 4000 bytes in length, that could be problematic if we had large hierarchies or long strings at certain levels. There has to be a better way of doing it whilst avoiding those aspects.

Recursive Subquery Factoring

We’ve established that inheritance is a recursive operation, so although Oracle can provide this with connect by, we can also do the same with recursive subquery factoring (RSF), which is a more powerful / flexible approach.

Here’s a comparison of the two approaches in Oracle :

  • Connect By – this is Oracle’s implementation.  Much more intuitive, easy to write, depth first traversal, no real state (effective memory register) between recursive cycles other than “prior” or using sys_connect_by_path.
  • Recursive Subquery Factoring (RSF) – this approach is part of the SQL standard, supports depth or breadth first traversal, state exists between recursive cycles.

One point always worth remembering is Recursive Subquery Factoring can do everything Connect By does, but NOT vice versa.

I won’t go into details of RSF and their construct as it’s outside of the scope of this article, and there are scores of articles already out there, but let’s write a RSF which does inheritance and see how it compares to the sys_connect_by_path approach

with treewalk (id, parent_id, numval, strval, dateval) as (
  select id, parent_id, numval, strval, dateval
  from  data d
  where parent_id is null  -- Anchor block
  union all
  select  d.id, d.parent_id,
          nvl(d.numval , t.numval ),
          nvl(d.strval , t.strval ),
          nvl(d.dateval, t.dateval)
  from treewalk t
  join data d on t.id = d.parent_id -- Recursive block
)
select *
from treewalk

         ID  PARENT_ID     NUMVAL STRVAL    DATEVAL
----------- ---------- ---------- --------- ----------
          0                     2 A                   
          1          0          2 B                   
          2          1          1 B         22-MAY-85 
          3          2          1 B         07-AUG-92 
          4          3         10 C         07-AUG-92 

5 rows selected.

So the RSF recursively treewalks from root to leaf and during the recursive block it applies the next level’s value if one exists, otherwise uses the value that it has kept track of during the recursion. That’s what nvl(d.dateval, t.dateval) is doing.

How great is that?! No string slicing, no data type conversions and all the messy stuff. The fact RSF is able to keep track of “state” has really helped us to solve the problem in an elegant way.

Where Did My Inherited Value Originate From?

Well finally, wouldn’t it be great to also know which id was the source of a particular inherited value? Well that should be quite simple. If a level’s value is null, we use the id we kept track of during recursion, otherwise we use the current level’s id.

with treewalk (id, parent_id, numval, strval, dateval, numval_src, strval_src, dateval_src) as (
  select id, parent_id, numval, strval, dateval, id, id, id
  from  data d
  where parent_id is null
  union all
  select  d.id, d.parent_id,
          nvl(d.numval , t.numval ),
          nvl(d.strval , t.strval ),
          nvl(d.dateval, t.dateval),
          nvl2(d.numval , d.id, t.numval_src ),
          nvl2(d.strval , d.id, t.strval_src ),
          nvl2(d.dateval, d.id, t.dateval_src)
  from treewalk t
  join data d on t.id = d.parent_id
)
select *
from treewalk

         ID  PARENT_ID     NUMVAL STRVAL DATEVAL   NUMVAL_SRC STRVAL_SRC DATEVAL_SRC
----------- ---------- ---------- ------ --------- ---------- ---------- -----------
          0                     2 A                         0          0           0
          1          0          2 B                         0          1           0
          2          1          1 B      22-MAY-85          2          1           2
          3          2          1 B      07-AUG-92          2          1           3
          4          3         10 C      07-AUG-92          4          4           3

5 rows selected.

How cool is that?

I’ve used nvl2 for brevity,  it’s is a bit like nvl, but allows you to define what to use if the first expression is null or not null. So that nvl2(exp1, exp2, exp3) =>

case when exp1 is not null then
  expr2
else
  expr3
end

Anyway, we’re now able to write queries to inherit values and tell you where the value was inherited from.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s