Re: How to control order of siblings in a tree walked by "connect by"??
Date: 26 Mar 93 18:12:48 GMT
Message-ID: <1993Mar26.181248.11520_at_qiclab.scn.rain.com>
In article <casivils.732403197_at_node_508ba> casivils_at_lescsse.jsc.nasa.gov (craig sivils) writes:
>In <1993Mar17.001028.14189_at_dlogics.com> brown_at_dlogics.com (Steve Brown) writes:
>
>>I cannot find any reference on how to control the ordering of rows at the
>>same level. An example is a hierarchical parts list where I want to order
>>all parts at the same level alphabetically. The "connect by" seems to use
>>the order of the rows as they were loaded into the table. I didn't
>>think a relational database knew/controlled the order of rows.
>>A recursive c program to do this isn't difficult, but it doesn't return a
>>single, neat, ordered result set and probably would require a cursor per level.
>>I'm probably missing something. Any hints, ideas, or references greatly
>>appreciated.
>You can but you can't. Let me explain, In SQL you can't, but due to the way
>SQL is implemented, you can. You need to correctly index the table so that
>the index used for the connect by will order rows on the same level
>alphabetically. Usually done by indexing the key column first then the
>alphabetical column next. Since Oracle goes down the index to find the rows
>it will retrieve them in alphabetical order. If you wish to dynamically order
>them well......
> Craig
Since you're using Connect-By-Prior, which is an Oracle extension to SQL, perhaps this PL/SQL answer will work for you.
Here is an old e-mail I sent to some people on this topic some years back; I believe it is still valid.
Subject: Q&A: a Sorted Parts Explosion? (Connect By)
Here is an interesting SQL question, together with an even more interesting answer. Thanks to Dominic Delmolino for his answer.
Orginal question..................
Given:
-------------------| MENU_OPTION table | -------------------| opt# number | prnt_opt# number | seq# number |
opt_text char |
-------------------|
Problem:
How do I create a select statement ( or multiple statements if necessary ) that would list the "Connect By" breakdown, but with options at each level sorted by seq#. That is, imagine that this represents a menu structure for an application. I want each menu screen to list the options in the desired order... not in the order in which they reside in the database physically.
I don't want the standard SQL connect-by output:
opt# prnt_opt# seq# lpad(level)||opt_text
---- --------- ---- ---------------------- 1 0 1 Main Option 1 5 1 1 Sub Main Option 1.1 6 1 2 Sub Main Option 1.2 4 0 3 Main Option 3 8 0 2 Main Option 2 2 8 2 Sub Main Option 2.2 9 8 1 Sub Main Option 2.1 10 9 1 SUBSub Main Option 2.1.1 11 9 3 SUBSub Main Option 2.1.3 12 9 2 SUBSub Main Option 2.1.2 13 9 4 SUBSub Main Option 2.1.4 7 8 3 Sub Main Option 2.3
But I DO want:
opt# prnt_opt# seq# lpad(level)||opt_text
---- --------- ---- ---------------------- 1 0 1 Main Option 1 5 1 1 Sub Main Option 1.1 6 1 2 Sub Main Option 1.2 8 0 2 Main Option 2 9 8 1 Sub Main Option 2.1 10 9 1 SUBSub Main Option 2.1.1 12 9 2 SUBSub Main Option 2.1.2 11 9 3 SUBSub Main Option 2.1.3 13 9 4 SUBSub Main Option 2.1.4 2 8 2 Sub Main Option 2.2 7 8 3 Sub Main Option 2.3 4 0 3 Main Option 3
Please help. SQL solutions are desired. PL/SQL solutions are acceptable. Pro*C solutions are last resort but I can handle it if it comes to that.
Answer provided by
Dominic Delmolino
This is a standard tree traversal, visiting parents, and then children in a left to right order. Since CONNECT BY doesn't allow us to specify the order in which to visit the children, we'll have to code the traversal our selves. Normally this is a recursive algorithm. However, it is always possible to code a recursive algorithm in a non-recursive fashion when given access to a data structure that can implement a stack. In our case, we can use a table to simulate a stack:
Using the definition of the MENU_OPTION table given and the following other tables:
MENU_STACK
push# number seq# number opt# number MENU_ORDER opt# number ord number
Here is a PL/SQL procedure to create the menu, with the options listed in order, in a MENU_ORDER table:
declare
Cur_push# number := 0; Cur_ord number := 0; Count_var number := 0; Max_push# number := 0;
Cur_opt# number;
begin
delete from menu_stack;
delete from menu_order;
/* Get all root nodes and initialize counters */ insert into menu_stack
select Cur_push#, seq#, opt# from menu_option where prnt_opt# not in (select opt# from menu_option); select nvl(count(1),0), max(push#) into Count_var, Max_push# from menu_stack;
/* Loop until stack is empty */
while (Count_var > 0) loop
/* Pop node off of stack and insert it into order table */ select opt# into Cur_opt# from menu_stack where push# = Max_push# and seq# = (select min(seq#) from menu_stack where push = Max_push#); delete from menu_stack where opt# = Cur_opt#; Cur_ord := Cur_ord + 1; insert into menu_order (opt#, ord) values (Cur_opt#, Cur_ord); /* Push node's children on to stack */ select nvl(count(1),0) into Count_var from menu_option where prnt_opt# = Cur_opt#; if (Count_var > 0) then Cur_push# := Cur_push# + 1; insert into menu_stack select Cur_push#, seq#, opt# from menu_option where prnt_opt# = Cur_opt#; end if; /* Check to see if stack is empty */ select nvl(count(1),0), max(push#) into Count_var, Max_push# from menu_stack;
end loop;
end;
Dominic Delmolino Office Address: Oracle Staff Consultant 290 Woodcliff Dr. Rochester, New York Fairport, NY 14450 Email: DDelmoli Phone: 716-586-9890 FAX: 716-586-9461
Notes:
- I have not tested this answer; I am assuming it is correct. If you do find an error of any kind in this, please let me know. Thanks.
-- Thomas Cox DoD #1776 '91 CB 750 Nighthawk tcox_at_qiclab.scn.rain.com The Platinum Rule: "Do Unto Others As They Want To Be Done Unto"Received on Fri Mar 26 1993 - 19:12:48 CET