This discussion is archived
1 2 Previous Next 15 Replies Latest reply: Nov 21, 2012 1:10 PM by AlbertoFaenza RSS

advanced:  how to walk up a tree to find root node?

user12200443 Newbie
Currently Being Moderated
advanced: How to walk up a tree?

I have a folder structure represented in the database:

table name:               folders

     column          column          type
     id               name          root|node               <= each entry is either a 'root' or a 'node'
     
     There is no information in this table about hiearchy.
     
There is another table (two columns) that simply link all nodes to the root (or a node to a node).
A node can have a node as a parent. There is no concept of left node or right node, just think about it like
a folder structure (any folder can have files/folders).

table name:               parent_child

     column               column
     parent_id          child_id
     
What I need to do is to write a pl/sql function that will return the root entry given any node

This is simple with one level of nesting:
     
     select * from folders where type='root' and id = (select parent_id from egroup_parent_child where child_id = <node_id>);

     but it does not give me everything I want in the case of nested nodes
     I have a collection of node_ids tha I need to iterate through and get the root id for each (walking up the tree until the root
     entry is found.
     
Visual:
     1     rootFolder1                              
     2          - folder1a                         
     3               -folder1aa                    
     4               - folder1ab                              
     5          - folder1b                         
     6               - folder1ba                    
     7               - folder1bb               so for example given the id of folder1bb (7), how do I get the id of root1 (1)?     
     8          - folder1c                         
     9     rootFolder2                                   
     10     rootFolder3     

---     
sample schema/data (put all in schema2.sql)

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,
     type 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)
-- root1
-- root2
-- root3
-- folder1a
-- folder1b
-- folder1c
-- folder1aa
-- folder1ab
-- folder1ac
-- folder1aaa
-- folder1aba
-- folder1aab
-- folder1abb
-- folder1aac
-- folder1abc

-- Visual hiearchy

-- 1     root1
-- 2      folder1a                         
-- 3          folder1aa          
-- 4               folder1aaa               -- has 3 parents (two are nodes) - root is id=1
-- 5               folder1aab          
-- 6               folder1aac          
-- 7          folder1ab               
-- 8               folder1ab
-- 9               folder1abb
-- 10          folder1ac
-- 11      folder1b
-- 12     folder1c
-- 13 root2
-- 14 root3

--- insert folders
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'root1', 'root');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'root2', 'root');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'root3', 'root');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1a', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1b', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1c', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aa', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1ab', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1ac', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aaa', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aba', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aab', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1abb', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aac', 'node');
insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1abc', 'node');
commit;

--
-- setup hiearchy
insert into parent_child(parent_id, child_id) values (0, (select folder_id from folders where name = 'root1'));
insert into parent_child(parent_id, child_id) values (0, (select folder_id from folders where name = 'root2'));
insert into parent_child(parent_id, child_id) values (0, (select folder_id from folders where name = 'root3'));

-- 1a,1b,1c
insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='root1'), (select folder_id from folders where name = 'folder1a'));
insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='root1'), (select folder_id from folders where name = 'folder1b'));
insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='root1'), (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;

Edited by: user12200443 on Nov 21, 2012 8:30 AM
  • 1. Re: advanced:  how to walk up a tree to find root node?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,

    Thanks for posting the CREATE TABLE and INSERT statements.
    Don't forget to post the exact output you want from that sample data. For example, is this what you want?
    `FOLDER_ID NAME                 TYPE                       ROOT
    ---------- -------------------- -------------------- ----------
             1 root1                root                          1
             4 folder1a             node                          1
             7 folder1aa            node                          1
            10 folder1aaa           node                          1
            12 folder1aab           node                          1
            14 folder1aac           node                          1
             8 folder1ab            node                          1
            11 folder1aba           node                          1
            13 folder1abb           node                          1
            15 folder1abc           node                          1
             9 folder1ac            node                          1
             5 folder1b             node                          1
             6 folder1c             node                          1
             2 root2                root                          2
             3 root3                root                          3
    If so, here's one way to get it:
    SELECT     f.*
    ,     CONNECT_BY_ROOT pc.child_id     AS root
    FROM     folders          f
    JOIN     parent_child     pc  ON  pc.child_id     = f.folder_id
    START WITH     pc.parent_id     = 0
    CONNECT BY     pc.parent_id     = PRIOR pc.child_id
    ;
    Note that this is walking down the tree; we are finding the roots (in the START WITH clause), and then finding their descendants, but remembering where we started, so we can display it on each row. A Top-Down query like this is the most efficient way to get the output shown above. There are times when you want to do a Bottom-Up query, where you find the ancestors of nodes. This is typically done by reversing which column in the CONNECT BY clause gets the PRIOR operator. So if a top-down query uses:
    CONNECT BY     pc.parent_id     = PRIOR pc.child_id
    then a bottom-up query on the same table will probably use:
    CONNECT BY     PRIOR pc.parent_id     = pc.child_id
    Edited by: Frank Kulash on Nov 20, 2012 1:50 PM
    Added discussion of bottom-up queries
  • 2. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    Thanks, I will give this a try. The reason I want to get the leaf nodes (walk from bottom up) is that I have to delete the leaf nodes first before the parents because of integrity constraint violations. I have to delete the entry in the 'parent_child' table and then delete the node/folder itself.
  • 3. Re: advanced:  how to walk up a tree to find root node?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,
    user12200443 wrote:
    Thanks, I will give this a try. The reason I want to get the leaf nodes (walk from bottom up) is that I have to delete the leaf nodes first before the parents because of integrity constraint violations. I have to delete the entry in the 'parent_child' table and then delete the node/folder itself.
    If you change the constraint to "ON DELETE CASCADE", then all you have to do is DELETE the parent, and all the descendants will be DELETEd automatically.
    Failing that, you should still do the CONNECT BY from the top down. You can reverse the order of the result set afterwards.
    WITH     connect_by_results     AS
    (
         SELECT     f.*
         ,     CONNECT_BY_ROOT pc.child_id     AS root
         ,     ROWNUM                    AS r_num
         FROM     folders          f
         JOIN     parent_child     pc  ON  pc.child_id     = f.folder_id
         START WITH     pc.parent_id     = 0
         CONNECT BY     pc.parent_id     = PRIOR pc.child_id
    )
    SELECT       *
    FROM       connect_by_results
    ORDER BY  r_num          DESC
    ;
  • 4. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    I am not sure that I will be able to get this to work.

    I need to pass an ID to the select statement that is the top most level id of the node from whence to traverse down (or up as would be the case).

    I have a list of the root nodes that are orphaned and need to iterate through this list and put all nodes into a collection from bottom to top, then iterate through this list and delete in order. Not sure if this is possible to pass the starting / parent_id to the select statement?
  • 5. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    The decendents I do not think would be deleted automatically in this case.

    The table that joins a child to a parent is : table: parent_child with two id's. These are foreign keys into the folder table. If I find a top level node that is orphaned (no parent but should have one), I can delete cascade that node, but a delete cascade will not traverse the table 'parent_child' recursively deleting all children. I think delete cascade only works on a row and all tables that have a foreign key pointing to it but would not traverse the tree.
  • 6. Re: advanced:  how to walk up a tree to find root node?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,
    user12200443 wrote:
    I am not sure that I will be able to get this to work.

    I need to pass an ID to the select statement that is the top most level id of the node from whence to traverse down (or up as would be the case).
    That's what the START WITH clause does.
    I have a list of the root nodes that are orphaned and need to iterate through this list and put all nodes into a collection from bottom to top, then iterate through this list and delete in order. Not sure if this is possible to pass the starting / parent_id to the select statement?
    Sure. Unless you have a really old version of Oracle, you can use a sub-query in the START WITH clause.
    ... I think delete cascade only works on a row and all tables that have a foreign key pointing to it but would not traverse the tree.
    Why do you think that?
  • 7. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    OK, will try to give it a go. I have the id that it should start with but cannot use the 'root' alias because that is the ID that I want to pass in.
    A better explanation of what I am trying to do is here: Re: advanced: (tree / node deletion) How to delete from leaf node to parent in (which is not a dupe of this issue - with this issue, I have the top level node that should have a parent / it is orphaned / I have a list of these for which I want to iterate and delete all children if possible).

    thanks for your help.
  • 8. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    a delete cascade, in my understanding will delete children rows in tables that have a foreign key pointing to a parent. I have three rows in a parent table that are orphaned (they should have a parent but do not). These three rows that represent a node have many many children (tens of thousands of children rows nested deeply). What I am attempting to do is recursively get all children ids of these top level orphaned rows (iterating through a list) and delete each/every child node from there. I did not think delete cascade had functionality to traverse a tree represented in a database : table name: parent_child with a parent_id and a child_id.

    Edited by: user12200443 on Nov 21, 2012 11:15 AM
  • 9. Re: advanced:  how to walk up a tree to find root node?
    Frank Kulash Guru
    Currently Being Moderated
    Hi,
    user12200443 wrote:
    a delete cascade, in my understanding will delete children tables that have a foreign key pointing to a parent.
    No, ON DELETE CASCADE deletes rows, not tables. Even if all the rows from a table are deleted, the table remains.

    By the way, it's conventional to use DELETE only with respect to rows, not tables. You can DELETE rows, but you DROP tables.
  • 10. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    yes, I understand that it deletes rows not tables, need to look through and see what I said that led to that. Basically what I am trying to do is that I have a collection (array) of ids which represent top level nodes, I need to iterate through that list and plug each id into a statement that will delete from that node all the way down. I had thought of simply building a list of leaf nodes from bottom to top, then iterating through that list deleting every one so as not to violate an integrity constraint of a table joining parent to child.
  • 11. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    OK, I updated my previous comment for clarification (understood delete cascade deletes rows).
  • 12. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    The original tables/sample data did not thoroughly explain the problem, here it is (not inserting the row that links a node to children - the sql statement at the end will who the orphaned folder - I have that ID and want to pass that to a SQL statement. Running the same sql statement after cleanup will show 0 rows - thanks for your help.

    ---
    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,
         type varchar2(20) not null
    );

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


    -- Visual hiearchy

    --     1 root1                                        -- this node exists in the 'folders' table
    -- 2 folder1a                              -- this node exists in the folders table, but no link to root1, so delete (from here down)     
    -- 3 folder1aa          
    -- 4 folder1aaa
    -- 5 folder1aab          
    -- 6 folder1aac          
    -- 7 folder1ab
    -- 8 folder1aba
    -- 9 folder1abb          
    -- 10 folder1abc          
    -- 11 folder1b                    -- has a link in parent_child to root1 so remains
    -- 12 folder1c                    -- has a link to root1 in parent_child to root1 so remains

    -- after all is said and done (nodes deleted) root1 remains with only two children (folder1b & folder1c : folder1a & down are deleted)

    -- I need a mechanism to pass the id of 'folder1a' to a method or use as a variable in a sql statement that delets from there down.
    --- I have a collection of ids to iterate through (each time passing the id to a method that will use the id as a variable in the sql statement).:1

    --- insert folders
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'root1', 'root');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1a', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1b', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1c', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aa', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1ab', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aaa', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aab', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aac', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1aba', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1abb', 'node');
    insert into folders(folder_id, name, type) values(seq_folders.nextval, 'folder1abc', 'node');
    commit;

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

    -- 1a,1b,1c
    -- the missing link: do not run this insert - this is the linkage this is missing that I want to demonstrate: insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='root1'), (select folder_id from folders where name = 'folder1a'));

    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='root1'), (select folder_id from folders where name = 'folder1b'));
    insert into parent_child(parent_id, child_id) values ((select folder_id from folders where name ='root1'), (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'));

    -- 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'));

    --

    -- after passing the id of 'folder1a' (orphaned) to a method,
    -- after creation, only 'folder1a' id would appear
    select * from folders where folder_id not in (select child_id from parent_child);

    -- after cleanup, rerunning this statement would not show anything.
    commit;
  • 13. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    so basically with the new example, what I am explaining is that I need to start with a node that has no parent, hence I cannot get the last statement to work because I need to start with an ID that should have an entry in the parent_child table but does not. I need to delete all its children ( I have the id ) but when I run the query nothing is returned.

    ---

    ---
  • 14. Re: advanced:  how to walk up a tree to find root node?
    user12200443 Newbie
    Currently Being Moderated
    So I think that is the query that I am looking for, I am attempting to put the query into a cursor (where I can pass the folder_id) but am not having much success:

    -- *************************************************************************************
    CURSOR fetch_all_orphans(p_folder_id in number) IS
    WITH     connect_by_results     AS
    (SELECT     f.*
    ,     CONNECT_BY_ROOT pc.child_id     AS root
    ,     ROWNUM AS r_num
    FROM     folder f
    JOIN     parent_child     pc ON pc.child_id     = f.group_id
    START WITH     pc.parent_id     = p_folder_id
    CONNECT BY     pc.parent_id     = PRIOR pc.child_id)
    SELECT *
    FROM connect_by_results
    ORDER BY r_num DESC;

    TYPE t_all_orphan_locations IS TABLE OF fetch_all_orphans%ROWTYPE INDEX BY PLS_INTEGER;
    v_all_orphans t_all_orphan_locations;


    When I run, I get a prompt to enter something. Is the above an approach for putting the query into a cursor? I need to fetch into the data structure.

    -- iterate through orphaned root folders, fetching all children recursively
    PROCEDURE fetchAllOrphans
    i NUMBER := 1;
    IS
    BEGIN
    LOOP
    EXIT WHEN i > v_root_orphans.COUNT;
    dbms_output.put_line('processing: ' || v_root_orphans(i).name);
    OPEN fetch_all_orphans(v_root_orphans(i).folder_id); -- previously built/queried
    FETCH fetch_all_orphans BULK COLLECT INTO v_all_orphans;
    dbms_output.put_line('all_orphan_count = [' || v_all_orphans.COUNT || ']');
    --- I will do something with v_all_orphans here
    CLOSE fetch_all_orphans;
    i := i + 1;
    END LOOP;
    END fetchAllOrphans;

    When I run in a PL/SQL package, I surprisingly get:


    -> Enter value for delete:

    Edited by: user12200443 on Nov 21, 2012 12:26 PM
1 2 Previous Next

Legend

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