This discussion is archived
13 Replies Latest reply: Nov 20, 2012 10:29 AM by user12200443 RSS

advanced:   How to traverse a tree representation in PL/SQL (procedure)?

user12200443 Newbie
Currently Being Moderated
I am looking to write a method that will create a collection of records, each of which represents a node in a tree.

TYPE t_all_folders IS TABLE OF get_all_folders%ROWTYPE INDEX BY PLS_INTEGER;
v_all_folders t_all_folders;

so first need help in figuring out what the cursor 'get_all_folders' would look like


---
I have a folder structure represented in a database that is used basically to show visually
(with a front end app) a folder structure (much like a folder structure in a file system).

So each row has an entry in the 'folders' table like do:

table folder:
     column           column
     folder_id          name
     1                    folder1               <= say this is a root folder
     2                    folder2               <= say this is a root folder
     3                    folder3               <= say this is a root folder
     4                    folder1a          <= all below are child folders..
     5                    folder1b
     6                    folder1c
     7                    folder1aa
     8                    folder1ab
                         ...

     There is nothing in this table that indicates a hiearchy.
     
---
The hiearchy is represented by another single table with two columns
(I cannot change this, it is what it is)

There is no left node or right node (not like a tree), just imagine sub folders.

table: parent_child
     column          column
     ------          ------
     parent_id     child_id
          
---
such that visually when the tables are queried and the UI uses a folder icon to
represent each row:

it would look like this:

     folder1                              1
          - folder1a                         2
               -folder1aa                    3
               - folder1ab                    4
          - folder1b                         5
               - folder1ba                    6
               - folder1bb                    7
          - folder1c                         8
     folder2                              9
     folder3                              10

I am attempting to create a query that will add to a collection folder records in the
order above (1..10)

In other words traverse the tree depth first going from:
          folder1 -> folder1a -> folder1aa -> folder1ab ->(back out to next level) folder1b -> folder1ba -> folder1bb -> folder1c
          then add folder2 (and traverse down that hiearch if needed)
          and then add folder3 to the colleciton and traverse down that hiearchy if there is one
          and continue adn so on.
          
          The requirement is to have them added to the collection in that order and when I iterate through the collection,
          they would of course need to be pulled out in that order (so use vararray with a counter to iterate through
          after the collection has been created.

After the collection has been created, I have to iterate in that specific order to create records in another table where there is a column that requires an integer value that is the 1... order they come out of the collection
and then have to iterate again and do something else in that order (and then other things - all the while needing in that order).

Edited by: user12200443 on Nov 19, 2012 11:49 AM
  • 1. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,

    You can use CONNECT BY to traverse a tree:
    WITH    joined_data     AS
    (
         SELECT     f.folder_id
         ,     f.name
         ,     pc.parent_id
         FROM     folder          f
         JOIN     parent_child     pc  ON  pc.child_id = f.folder_id
    )
    SELECT     j.*
    ,     ROWNUM          AS r_num     -- if needed
    FROM     joined_data     j
    START WITH     parent_id     IS NULL
    CONNECT BY     parent_id     = PRIOR child_id
    ORDER SIBLINGS BY     name
    ;
    You don't necessarily have to do the join in a separate sub-query. I did it that way above because it's often faster, and, depending on your exact requirements, you may need to do some more manipulation of the data before you traverse the tree.

    You can do this in PL/SQL if you need to copy the data into a data structure. Depending on what you want, you might be able to do it without PL/SQL, and do it more efficently.

     

    I hope this answers your question.
    If not, post a little sample data (CREATE TABLE and INSERT statements, relevant columns only) for all the tables involved, and the results you want from that data.
    If the results you want really are a populated data structure, then post some PL/SQL code to create the empty data structure, and show what you want it to contain when everything is finished, given your sample data. But think carefully about what you really want; you might not need PL/SQL.
    Explain, using specific examples, how you get those results from that data.
    Always say what version of Oracle you're using (e.g. 11.2.0.2.0). This is especially important with CONNECT BY queries, because every version since Oracle 7 has had major improvements in this area.

    See the forum FAQ {message:id=9360002}
  • 2. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    user12200443 Newbie
    Currently Being Moderated
    How do I get the results into an array of records in PL/SQL so I can iterate? I will try the query.
  • 3. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    user12200443 Newbie
    Currently Being Moderated
    I really do need this in a data structure inside PL/SQL. I need to iterate through the list in order at least twice to do some other things (insert rows into another table with data queried from this).
  • 4. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,
    user12200443 wrote:
    How do I get the results into an array of records in PL/SQL so I can iterate?
    Any way you want to. You can handle the results of this query the same way you handle the results of any other query.
    BULK COLLECT is probably the fastest way; a cursor FOR loop might be the simplest.
    I really do need this in a data structure inside PL/SQL. I need to iterate through the list in order at least twice to do some other things (insert rows into another table with data queried from this).
    INSERT can do that; sometimes MERGE is more convient and/or more efficient.
    I'm not saying that there are no good reasons to use PL/SQL; I'm just asking if you have one.

    Edited by: Frank Kulash on Nov 19, 2012 5:56 PM
  • 5. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    user12200443 Newbie
    Currently Being Moderated
    I could not get the query to work on sample tables/data. Any ideas?
  • 6. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,
    user12200443 wrote:
    I could not get the query to work on sample tables/data. Any ideas?
    Nothing that I didn't mention in my first message, and nothing that's not in the forum FAQ {message:id=9360002}
    The query I posted then was my best guess based on the information available, but it was only a guess. Untill you post what i asked for then, there's not much more I can do.
  • 7. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    Justin Cave Oracle ACE
    Currently Being Moderated
    What does that mean?

    Did you get an error? If so, what error? What was the query that you were running that produced the error?

    If you read Frank's reply to the end, there is a request for additional information that would allow us to be more helpful (CREATE TABLE statements, INSERT statements, etc.)

    Justin
  • 8. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    user12200443 Newbie
    Currently Being Moderated
    awesome, thanks for the help.

    put this in 'schema.sql' and run to create a reference schema and data for the example


    drop sequence seq_folders;
    CREATE SEQUENCE seq_folders
    INCREMENT BY 1
    MINVALUE 1
    START WITH 1
    CACHE 1000;

    drop table folders;
    create table folders (
         folder_id number not null,
         name varchar2(20) not null
    );

    drop table parent_child;
    create table parent_child (
         parent_id number not null,
         child_id number not null);

    -- creation order (in order to have parent)
    -- folder1
    -- folder2
    -- folder3
    -- folder1a
    -- folder1b
    -- folder1c
    -- folder1aa
    -- folder1ab
    -- folder1ac
    -- folder1aaa
    -- folder1aba
    -- folder1aab
    -- folder1abb
    -- folder1aac
    -- folder1abc


    -- Visual hiearchy

    -- folder1                              1
    --      folder1a                         2
    --           folder1aa               3
    --                folder1aaa          4
    --                folder1aab          5
    --                folder1aac          6
    --           folder1ab               7
    --                folder1aba          8
    --                folder1abb          9
    --           folder1ac               10
    --      folder1b                         11
    --      folder1c                         12
    -- folder2                              13
    -- folder3                              14

    --- insert folders
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder2');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder3');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1a');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1b');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1c');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1aa');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1ab');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1ac');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1aaa');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1aba');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1aab');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1abb');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1aac');
    insert into folders(folder_id, name) values(seq_folders.nextval, 'folder1abc');
    commit;

    --
    -- setup hiearchy
    insert into parent_child(parent_id, child_id) values (0, (select folder_id from folders where name = 'folder1'));
    insert into parent_child(parent_id, child_id) values (0, (select folder_id from folders where name = 'folder2'));
    insert into parent_child(parent_id, child_id) values (0, (select folder_id from folders where name = 'folder3'));

    -- 1a,1b,1c
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1'), (select folder_id from folders where name = 'folder1a'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1'), (select folder_id from folders where name = 'folder1b'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1'), (select folder_id from folders where name = 'folder1c'));

    -- aa,ab,ac
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1a'), (select folder_id from folders where name = 'folder1aa'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1a'), (select folder_id from folders where name = 'folder1ab'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1a'), (select folder_id from folders where name = 'folder1ac'));

    -- aaa,aba,aab
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1aa'), (select folder_id from folders where name = 'folder1aaa'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1aa'), (select folder_id from folders where name = 'folder1aab'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1aa'), (select folder_id from folders where name = 'folder1aac'));

    -- aba,abb,abc
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1ab'), (select folder_id from folders where name = 'folder1aba'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1ab'), (select folder_id from folders where name = 'folder1abb'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='folder1ab'), (select folder_id from folders where name = 'folder1abc'));

    --
    commit;



    -----
    then run this to get the error message

    WITH joined_data     AS
    (
         SELECT     f.folder_id,     f.name,     pc.parent_id
         FROM     folders     f
         JOIN     parent_child     pc ON pc.child_id = f.folder_id
    )
    SELECT     j.*,     ROWNUM     
    AS r_num
    FROM joined_data     j
    START WITH     parent_id =0
    CONNECT BY     parent_id= PRIOR child_id
    ORDER SIBLINGS BY     name;

    ---
    thanks for the help, hopefully I can find a way to read the rows/record into a data structure (does not have to be a single sql statement - can be anything I can do in PL/SQL.

    Edited by: user12200443 on Nov 19, 2012 5:55 PM
  • 9. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    rp0428 Guru
    Currently Being Moderated
    Please edit that reply and add \
     on the line before and the line after the code to preserve formatting. See the FAQ for other formatting options. Use the 'Preview' tab of your reply to see what it looks like prior to posting it.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
  • 10. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,

    Now that I can test it, I can see I made a mistake.
    In the sub-query, the tables are joined by the condition
    pc.child_id = f.folder_id
    so it doesn't matter if we use child_id or folder_id after that point, since they will always be the same. However, I only included folder_id (and not child_id) in the SELECT clause of joined_data, so only folder_id is visible in the super-query. The one line that references child_id in the main query needs to be changed to reference folder_id instead.

    This is what I should have posted:
    WITH    joined_data      AS
    (
         SELECT  f.folder_id, f.name, pc.parent_id
         FROM      folders       f
         JOIN     parent_child  pc  ON  pc.child_id = f.folder_id
    )
    SELECT   j.*
    ,       ROWNUM          AS r_num
    FROM       joined_data j
    START WITH           parent_id     = 0
    CONNECT BY          parent_id     = PRIOR folder_id     -- CHANGED
    ORDER SIBLINGS BY    name
    ;
    Edited by: Frank Kulash on Nov 19, 2012 8:47 PM
    You might want to indent the name, to reflect the tree structure, so people will find it easier to understand.
    The query below is has changed the name column; the rest of the query is the same as above:
    WITH    joined_data      AS
    (
         SELECT  f.folder_id, f.name, pc.parent_id
         FROM      folders       f
         JOIN     parent_child  pc  ON  pc.child_id = f.folder_id
    )
    SELECT   folder_id
    ,      LPAD ( ' '
               , 2 * (LEVEL - 1)
               ) || name          AS indented_name
    ,      parent_id
    ,       ROWNUM               AS r_num
    FROM       joined_data j
    START WITH           parent_id     = 0
    CONNECT BY          parent_id     = PRIOR folder_id     -- CHANGED
    ORDER SIBLINGS BY    name
    ;
    Output:
    FOLDER                      PARENT
       _ID INDENTED_NAME           _ID      R_NUM
    ------ -------------------- ------ ----------
         1 folder1                   0          1
         4   folder1a                1          2
         7     folder1aa             4          3
        10       folder1aaa          7          4
        12       folder1aab          7          5
        14       folder1aac          7          6
         8     folder1ab             4          7
        11       folder1aba          8          8
        13       folder1abb          8          9
         9       folder1ac           8         10
         9     folder1ac             4         11
         5   folder1b                1         12
         6   folder1c                1         13
         2 folder2                   0         14
         3 folder3                   0         15
    This is what you said you wanted, except for 'folder1ac' which appears 2 times in the output above (and in your INSERT statements), but only 1 time in the desired output you posted. Was there a typo in the sample data? if not, explain what the duplicate folder name means, and why you want the output you do when that happens.

    In most files system, folder and file names don't have to be unique across the whole tree; you just can't have siblings with the exact same name. A lot of guys would base the INSERT statements on unique id numbers, not names, to allow duplicate names.
  • 11. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    user12200443 Newbie
    Currently Being Moderated
    awesome, I think this works, will check through each folder. I need to disect the query to understand what is going on so I can make reuse of the concepts. I appreciate your help.
  • 12. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,
    user12200443 wrote:
    ... I need to disect the query to understand what is going on so I can make reuse of the concepts.
    This page is a nice introduction to CONNECT BY queries.
  • 13. Re: advanced:   How to traverse a tree representation in PL/SQL (procedure)?
    user12200443 Newbie
    Currently Being Moderated
    awesome, will check that out and mark this one as resolved. I have another task to walk up a tree to the root node (new post).

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points