Skip to Main Content

Breadcrumb

more

Connor and Chris don't just spend all day on AskTOM. You can also catch regular content via Connor's blog and Chris's blog. Or if video is more your thing, check out Connor's latest video and Chris's latest video from their Youtube channels. And of course, keep up to date with AskTOM via the official twitter account.

Question and Answer

Tom Kyte

Thanks for the question, Piotr.

Asked: October 19, 2003 - 9:00 pm UTC

Answered by: Tom Kyte - Last updated: July 04, 2016 - 10:27 am UTC

Category: Database - Version: 9.2.0.1.0

Viewed 1000+ times

Whilst you are here, check out some content from the AskTom team: Licensed for Advanced Compression? Don't forget the network

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 we 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>


and you rated our response

  (8 ratings)

Is this answer out of date? If it is, please let us know via a Review

Reviews

Excellent!

October 20, 2003 - 12:31 pm UTC

Reviewer: Piotr Jarmuz from Poznan, Poland

I knew that if this were at all possible you'd find the solution.

Thank you very much!

Another related question

October 23, 2003 - 10:31 am UTC

Reviewer: Piotr Jarmuz from Poznan, Poland

Hello Tom,

Now I had to slightly modify this query like this:

select * from (
select name, min(level), count(*) from tree
start with name in (select name from another_table where SOME_PREDICATE...)
connect by prior pid=id
group by name
having count(*)=(select count(name) from another_table where SOME_PREDICATE...)
order by 2
)
where rownum=1;


Is there a way to eliminate duplication of "almost" identical subqueries:

select name from another_table where SOME_PREDICATE...
select count(name) from another_table where SOME_PREDICATE...

They compute resultset and its length at the same time logically so there should be a away to do it once physically.

Maybe an inline view?

Maybe this is not the best analogy but it has just crossed my mind that it is similar to the way the "C" compilers can optimize division and modulo in integer arithmetics under analogical conditions. I am sure you know what I mean.

Thank you in advance.

Piotr

Tom Kyte

Followup  

October 23, 2003 - 12:58 pm UTC

you could "with"

with Q as ( select name, count(*) over () cnt from another_table ... )
select name, min(level), count(*)
from tree
start with name in ( select name from q )
...
having count(*) = ( select cnt from q where rownum = 1 )

It works

October 23, 2003 - 1:35 pm UTC

Reviewer: Piotr Jarmuz from Poznan, Poland

Thank you very much.

What is this "with clause"? I see it for the first time.
Very cool, anyway.

And the execution plan shows something like:
...
TABLE ACCESS (FULL) OF 'SYS_TEMP_0FD9D6607_5823328' (Cost=2 Card=1 Bytes=15)
...

Is this a temporary materialized view?

Tom Kyte

Followup  

October 23, 2003 - 1:39 pm UTC

it is called subquery factoring, new in 9i.

yes, that is like a temporary mv

Close to perfection

December 02, 2004 - 10:34 am UTC

Reviewer: Vladimir Andreev from Germany

Doh... :-/

Tom, you can forget the new question I posted about an hour ago... The whole time I was thinking in terms of organisational hierarchies and they don't have "ancestors", do they? They have "indirect parents", and a parent org is not necessarily "older" than its children. So I was searching for a "nearest common parent" and not finding this thread. My sincere apologies to the one that couldn't post his/hers question today because of my narrow-mindedness.

Anyway, your solution here is very close to perfection. What is missing is that it still needs the distinct cardinality of the parameter set, which might not be easy (performance-wise) to get, if the parameter is itself the result of a subquery. Any ideas how to overcome that? I'll put my thinking hat on as well, but yours seems to be faster :-)

Thanks for the great site!
Flado

Today is not my day

December 02, 2004 - 10:48 am UTC

Reviewer: Vladimir Andreev from Germany

The minute I post a question, I find it's been answered already. Please ignore my last followup as well.

Just replace
select name, count(*) over () cnt from another_table ...
with
select name, count(distinct name) over () cnt from another_table ...

and I'll have my perfection.

Thanks again and sorry.
Flado

do it for all

June 22, 2016 - 2:28 pm UTC

Reviewer: Pet from Columbus, OH USA

In the above example, it has start with name in ( 'D', 'E' ) in the query. For example, I want to get it for all set of nodes and display their Youngest Common Ancestor YCA, how do I do it. I'm trying to avoid looping through every child nodes. Please let me know
Chris Saxon

Followup  

June 23, 2016 - 7:58 am UTC

I'm not sure what you mean.

Just change the start with clause to include whichever set of nodes you want to find the YCA of. Then modify the having count(*) = :N to be the number of nodes in your set.

If the set is "all nodes", then it's just the root node! (pid is null).

Chris

do it for all

June 23, 2016 - 3:30 pm UTC

Reviewer: pet from Columnbs, OH USA

Here is my query. The code loops through the child_flex_value_low and get the LCA.

SELECT a.*
FROM (SELECT DISTINCT parent_flex_value, lev
FROM (SELECT parent_flex_value, child_flex_value_low,
MIN (LEVEL) OVER (PARTITION BY parent_flex_value)
lev,
COUNT (*) OVER (PARTITION BY parent_flex_value)
cnt
FROM apps.FND_FLEX_VALUE_NORM_HIERARCHY ffvhs
WHERE flex_value_set_id in ( select flex_value_set_id from apps.fnd_flex_value_sets
WHERE flex_value_set_name = 'COMPANY')
START WITH child_flex_value_low IN ('09090', '08787')
CONNECT BY PRIOR parent_flex_value = child_flex_value_low)
WHERE cnt = 2
) a,
apps.fnd_flex_values b
WHERE b.flex_value_set_id in
( select flex_value_set_id from apps.fnd_flex_value_sets
WHERE flex_value_set_name = 'COMPANY')
AND b.flex_value = a.parent_flex_value
AND NVL(b.attribute3, 'z') = 'T'
order by a.lev

I want to avoid the loop. I tried using "With Clause" and it doesn't work, It gives me the error as ORA-00913: too many values

WITH nodes AS (
select '09090' comp , segment1 from gl.gl_Code_combinations gcc where segment2 = '1234567'
)
SELECT a.*
FROM (SELECT DISTINCT child_flex_value_low, parent_flex_value, lev
FROM (SELECT parent_flex_value, child_flex_value_low,
MIN (LEVEL) OVER (PARTITION BY parent_flex_value)
lev,
COUNT (*) OVER (PARTITION BY parent_flex_value)
cnt
FROM apps.FND_FLEX_VALUE_NORM_HIERARCHY ffvhs
WHERE flex_value_set_id in ( select flex_value_set_id from apps.fnd_flex_value_sets
WHERE flex_value_set_name = 'COMPANY')
START WITH child_flex_value_low IN (select comp,segment1 from nodes)
CONNECT BY PRIOR parent_flex_value = child_flex_value_low)
WHERE cnt = 2
) a,
apps.fnd_flex_values b
WHERE b.flex_value_set_id in
( select flex_value_set_id from apps.fnd_flex_value_sets
WHERE flex_value_set_name = 'COMPANY')
AND b.flex_value = a.parent_flex_value
AND NVL(b.attribute3, 'Z') = 'T'
order by a.lev
/
ORA-00913: too many values
00913. 00000 - "too many value

Please help and appreciate your support. Thank you.
Chris Saxon

Followup  

June 24, 2016 - 7:09 am UTC

Your subquery for the start with clause returns two columns:

start with child_flex_value_low in
  ( select comp,segment1 from nodes )


But you're only comparing it to one column! Either you need to remove the column from your subquery or add one to the start with columns:

start with child_flex_value_low in
  ( select comp from nodes )


or

start with (child_flex_value_low, other_col) in
  ( select comp,segment1 from nodes )

do it for all

June 27, 2016 - 1:05 pm UTC

Reviewer: pet from Columns, OH USA

I understand..but if you see my original query, I want to find the common parent for a children pair.

START WITH child_flex_value_low IN ('09090', '08787')

So, I want to avoid the loop and find out for all children pair.

I'm not sure how do I do it. Please let me know.

Thank you


Chris Saxon

Followup  

July 04, 2016 - 10:27 am UTC

Could you clarify what you mean by "avoid the loop"?

There isn't one in your query, so I'm confused! Precisely what is the problem you have?

Chris