Re: Tree Query question

From: Chrysalis <cellis_at_iol.ie>
Date: 1997/11/12
Message-ID: <346A951C.5A55@iol.ie>

rsenn wrote:
>
> I'm trying to work through a tree query in PL*SQL and getting nowhere.
> If you are familiar with the Work Breakdown Structure (WBS) concept,
> then you quickly understand what I'm doing.
>
> Can anybody give me a hand with this? E-mail replies are encouraged,
> even if you also reply to the newsgroup.
>
> Thanks.
>
> Sincerely,
> Randall
>
> Data look something like this.
>
> Job Parent Spent
> 10 NULL 100 -- top level has NULL parent WBS 10
> 20 10 500 -- child 10.20
> 27 20 700 -- grandchild 10.20.27
> 32 27 50 -- great grandchild 10.20.27.32
> 21 20 200 -- a 2nd branch from job 20 10.20.21
>
> There is no limit to the breadth or depth of the tree, although as a
> practical matter I suspect about 10 or 15 levels will be the depth limit
> reached and 20 or 30 will be the practical limit for breadth.
>
> I want to construct a report similar to this, but can't see the coding
> logic to doing it. Can you point me in the right direction?
>
> Job Spent_by_Job_&_Progeny
> 10 1550 -- spent by job 10 and all of its descendents
> 20 1450 -- " 20 "
> 21 200 -- " 21. It has no descendents.
> 27 750 -- " 27 and all of its descendents.
> 32 50 -- " 32. It has no descendents.

The problem is that, while traversing the tree, *for each row* you have to
descend the whole tree from that row in order to calculate the total spend.

It would probably be possible to create a re-entrant procedure to mimic the effect of the Oracle tree-walk feature while summing a column value (or values) during a single pass of the table. However, it may be easier to take the performance hit of defining a simple summation function incorporating one tree walk and then using it in a simple SQL statement containing another tree walk as below.

The following is a listing from the spool file of an actual execution. It works (and gives the same results as you expected!).

SQL>
SQL> create table spend_by_job
  2 (job number
  3 ,parent number
  4 ,spent number
  5 );

Table created.

SQL>
SQL> create or replace function tree_spend (start_job number)

  2     return number is
  3     cursor C is
  4        select sum(spent)
  5        from  spend_by_job
  6        start with job = start_job
  7        connect by prior job = parent;
  8     totspend number;
  9  begin
 10     open C; fetch C into totspend; close C;	-- Note (1)
 11     return totspend;

 12 end tree_spend;
 13 /

Function created.

SQL> set feed off;
SQL> 
SQL> insert into spend_by_job values (10,null,100);
SQL> insert into spend_by_job values (20,10,500);
SQL> insert into spend_by_job values (27,20,700);
SQL> insert into spend_by_job values (32,27,50);
SQL> insert into spend_by_job values (21,20,200);

SQL> select tree_spend(10) from dual	-- Note (2);

TREE_SPEND(10)                                                                  
--------------                                                                  
          1550
                                                                           
SQL> col parent null '  NULL';
SQL> Rem set scan off because of '&' in heading;

SQL> set scan off;
SQL> col ts heading 'Spent_by_Job_&_Progeny'

SQL> select job,parent,tree_spend(job) ts   2 from spend_by_job

  3  start with parent is null	-- Note (3)
  4  connect by prior job = parent	-- Note (4);


   JOB PARENT
Spent_by_Job_&_Progeny                                            
------ ------
----------------------                                            
    10   NULL                  
1550                                            
    20     10                  
1450                                            
    27     20                   
750                                            
    32     27                    
50                                            
    21     20                   
200                                            

SQL>
SQL> spool off;

Notes:
(1) I *always* use an explicit cursor in function/procedure definitions rather than using "select ... into ...". The result is one fetch instead of two per execution of the function.

(2) Of course, you may find "tree_spend" a useful function in its own right.

(3) Try to avoid "start with <column> is null". Use a parent value of, say, -1 in order to use an index (see next note). Of course, you can't do this if you are using referential integrity (non-existent key value).
An alternative is to "start with job = 10", in which case you need an index on (job [,...]).

(4) For large tables, the "downward" tree-query proceeds *very* much faster with an index on (parent,job). (An "upward" query should have an index on (job,parent)).

HTH

-- 
Chrysalis

FABRICATI DIEM, PVNC
('To Protect and to Serve')
Terry Pratchett : "Guards Guards"

Received on Wed Nov 12 1997 - 00:00:00 CST