Re: Nested Coalescing possible in SQL?

Thanks Lennart. I think your third suggestion might do the trick. If you have a chance to answer I'm curious:

1. Why do you think storing the path (suggestion #2) is not an option? Or if it is option, why is it a bad idea compared to storing a separate ancestor relation? (aside from the usual normal form reasoning)
2. How would you structure the query if you stored the path (suggestion #2).

Thanks!

• Jeff

lennart_at_kommunicera.umea.se (Lennart Jonsson) wrote in message news:<6dae7e65.0406022337.338870_at_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 - 21:37:10 CDT