Re: Nested Coalescing possible in SQL?

From: Lennart Jonsson <lennart_at_kommunicera.umea.se>
Date: 3 Jun 2004 00:37:23 -0700
Message-ID: <6dae7e65.0406022337.338870@posting.google.com>

jlanfield2003_at_yahoo.com (Jeff Lanfield) wrote in message news:<235c483f.0406021038.13a1b83b_at_posting.google.com>...

[...]

>
> So say the tree is specified like this:
>
> (nodeId int, parentId int, color varchar, phone varchar)
>
> 5, 0,"GREEN", "555-1212"
> 7, 5, NULL, "777-5555"
> 8, 7 NULL, NULL
> 9, 7 "BLUE", NULL
>
>
> That is: node 7 inherits values from 5. Nodes 8,9 inherit values from
> 7. Node 5 is the top level node.
>
> I want to run a query that would give the following result set:
>
> select nodeId, color, phone from ...
>
> 5,"GREEN", "555-1212"
> 7,"GREEN", "777-5555"
> 8,"GREEN", "777-5555"
> 9,"BLUE", "777-5555"
>
> Can such a query be constructed?
>

If you dont have a maximum depth of your tree (and cannot use recursion), then no. The reason is that you cannot express queries like "gimmie the ancestors of x". What you need to do is to inform your system that 5 is an ancestor of 9. There are several ways of doing this. Troels Arvin has a page with links to articles on the subject:

http://troels.arvin.dk/db/rdbms/links/#hierarchical

1. Nested set: google for Celko and nested. There are also variants of this.
2. Store the path in each node. In your case something like:

5,'',"GREEN", "555-1212"
7,'5',"GREEN", "777-5555"
8,'5.7',"GREEN", "777-5555"
9,'5.7',"BLUE",  "777-5555"

In your case I dont think this is an option

3. Store a separate ancestor relation. In your case

create table ancestor (

        nodeid int not null
                references tree,
        ancestorid int not null
                references tree,
        primary key (nodeid, ancestorid)

);

insert into ancestor values (7,5), (8,7), (8,5), (9,7), (9,5);

Main drawback is that you have to maintain this relation as you modifies your tree. I have some notes on how that can be achieved:

http://fungus.teststation.com/~jon/treehandling/TreeHandling.htm

Anyhow, once you have a way of asking for ancestors for a given node, you can do what you want in a single query, namely:   

find the ancestor at the largest depth with property p

Assuming the following ddl

create table tree (

        nodeid int not null primary key,
        parent int not null
                references tree
                on delete restrict

);

create table data (

        nodeid int not null primary key
                references tree
                on delete cascade,
        color varchar(10),
        phone varchar(10)

);

insert into tree values (5,5), (7,5), (8,7), (9,7); insert into data values (5, 'GREEN', '555-1212'), (7, NULL, '777-5555'), (8, NUL
L, NULL), (9, 'BLUE', NULL); create table ancestor (

        nodeid int not null
                references tree,
        ancestorid int not null
                references tree,
        primary key (nodeid, ancestorid)

);

insert into ancestor values (7,5), (8,7), (8,5), (9,7), (9,5);

You could use a query like:

with suspects (nodeid, suspectid, depth) as (

    select

        a.nodeid, a.ancestorid, 
        (select count(1) from ancestor where nodeid = a.ancestorid) as

depth

    from ancestor a, data d
    where a.ancestorid = d.nodeid
      and d.color is not null
    union all
    select

        d.nodeid, d.nodeid, 
        (select count(1) from ancestor where nodeid = d.nodeid) as

depth

    from data d
    where d.color is not null

      and not exists (
          select 1 from ancestor where ancestorid = d.nodeid
      )

)
select s.nodeid, d.color from suspects s, data d where d.nodeid = s.suspectid
  and depth = (select max(depth) from suspects where nodeid = s.nodeid)

NODEID COLOR
----------- ----------

          7 GREEN     
          8 GREEN     
          9 BLUE      

  3 record(s) selected.

As you can see node 5 is missing, but I'll leave that for you ;-)

HTH
/Lennart

> - Jeff
Received on Thu Jun 03 2004 - 02:37:23 CDT