SQL & PL/SQL

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