You Asked
Hello Tom,
I could finally ask you a question...
I have a table like this:
create table tree(name varchar2(30), id number, pid number, primary key(id), foreign key(pid) references tree(id));
with sample data:
insert into tree values ('A',1,null);
insert into tree values ('B',2,1);
insert into tree values ('C',3,1);
insert into tree values ('D',4,2);
insert into tree values ('E',5,2);
insert into tree values ('F',6,3);
insert into tree values ('G',7,3);
insert into tree values ('H',8,3);
insert into tree values ('I',9,6);
insert into tree values ('J',10,6);
insert into tree values ('K',11,8);
insert into tree values ('L',12,10);
Is it possible to write a single SQL query to answer the following question?
Given the arbitrary set of nodes return their Youngest Common Ancestor YCA. You can take for granted that the table contains correct trees (no loops) and that the input node set belongs to exactly one tree.
e.g.
i) (D,E) -> B
ii) (I,L) -> F
iii) (L,G,K) -> C
iv) (K,D) -> A
I wrote a PL/SQL code (using connect by clause, bulk collecting full paths upwards from node to root and finding common ancestor procedurally in a loop) for this but I wonder if it is possible to write this in a single SQL query? Quite a challenge (at least for me). I cannot find a way to do this unless I could create dynamically number of queries glued with intersects and sprinkled with connect by, order by, inline views... etc.
For instance for iii) it would look like:
select name from (
select name, rownum r from (
select name from (
select name,level l from tree
start with name='L'
connect by prior pid=id
order by l desc
)
intersect
select name from (
select name,level l from tree
start with name='G'
connect by prior pid=id
order by l desc
)
intersect
select name from (
select name,level l from tree
start with name='K'
connect by prior pid=id
order by l desc
)
) order by r desc
) where rownum=1
And of course I would normally use bind variables and dbms_sql package...
But that is not an acceptable solution... too expensive (naive algorithm) and too easy ;-)
Thank you in advance,
Regards,
Piotr
and Tom said...
ops$tkyte@ORA920> select *
2 from (
3 select name, min(level), count(*)
4 from t
5 start with name in ( 'D', 'E' )
6 connect by prior pid = id
7 group by name
8 having count(*) = 2
9 order by 2
10 )
11 where rownum = 1
12 /
NAME MIN(LEVEL) COUNT(*)
---------- ---------- ----------
B 2 2
ops$tkyte@ORA920> select *
2 from (
3 select name, min(level), count(*)
4 from t
5 start with name in ( 'I', 'L' )
6 connect by prior pid = id
7 group by name
8 having count(*) = 2
9 order by 2
10 )
11 where rownum = 1
12 /
NAME MIN(LEVEL) COUNT(*)
---------- ---------- ----------
F 2 2
ops$tkyte@ORA920> select *
2 from (
3 select name, min(level), count(*)
4 from t
5 start with name in ( 'L', 'G', 'K' )
6 connect by prior pid = id
7 group by name
8 having count(*) = 3
9 order by 2
10 )
11 where rownum = 1
12 /
NAME MIN(LEVEL) COUNT(*)
---------- ---------- ----------
C 2 3
ops$tkyte@ORA920> select *
2 from (
3 select name, min(level), count(*)
4 from t
5 start with name in ( 'K', 'D' )
6 connect by prior pid = id
7 group by name
8 having count(*) = 2
9 order by 2
10 )
11 where rownum = 1
12 /
NAME MIN(LEVEL) COUNT(*)
---------- ---------- ----------
A 3 2
ops$tkyte@ORA920>
Rating
(8 ratings)
Is this answer out of date? If it is, please let us know via a Comment