Thread: How to navigate tree without CONNECT BY?
I have a simple table that I'd like to query to pull
out a heirarchy from a tree relationship. What is the
best way to do this without a 'CONNECT BY' clause like
Oracle has?
Example
mytable
+----------+-----------+
| child_id | parent_id |
+----------+-----------+
| 1 | NULL |
| 2 | NULL |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 4 |
| 7 | 4 |
| 8 | 7 |
| 9 | 3 |
| 10 | 9 |
+----------+-----------+
I want to be able to select the child_id, parent_id, and the up-stream
heirarchy level when starting at a given child...
In Oracle you'd use a statement like
SELECT *
FROM account
START WITH child_id = 10
CONNECT BY PRIOR parent_id = child_id;
(* note: may not be exactly correct *)
I was thinking that PL/PGSQL could return a set using a function like
'get_tree_relation(child_id INTEGER)'
Example 1:
SELECT *
FROM get_tree_relation(10)
ORDER BY level ASC;
+----------+-----------+-------+
| child_id | parent_id | level |
+----------+-----------+-------+
| 10 | 9 | 1 |
| 9 | 3 | 2 |
| 3 | 1 | 3 |
| 1 | NULL | 4 |
+----------+-----------+-------+
Example 2:
SELECT *
FROM get_tree_relation(2)
ORDER BY level ASC;
+----------+-----------+-------+
| child_id | parent_id | level |
+----------+-----------+-------+
| 2 | NULL | 1 |
+----------+-----------+-------+
Example 2:
SELECT *
FROM get_tree_relation(11)
ORDER BY level ASC;
+----------+-----------+-------+
| child_id | parent_id | level |
+----------+-----------+-------+
+----------+-----------+-------+
I have a PL/PGSQL function that does this for me with some nested
selects inside a loop, but my NEW problem is that I need to be able
to detect circular loops. For example, if child_id refers to itself
or if a parent_id refers to a child_id that is already in the
heirarchy we don't want to get into an infinite loop. So I modified
my function to use a TEMP table to store the records I had already
seen, but then I had problems with the temp table:
http://archives.postgresql.org/pgsql-bugs/2003-05/msg00084.php
Without having to recompile any database code, can this process be
build using out-of-the-box PostgreSQL features?
There's gotta be an easy way to do this. It's a fairly common
problem, isn't it?
--Dante
D. Dante Lorenso wrote: > I have a simple table that I'd like to query to pull > out a heirarchy from a tree relationship. What is the > best way to do this without a 'CONNECT BY' clause like > Oracle has? See connectby() in contrib/tablefunc. Joe
See http://gppl.terminal.ru/readme.html On Thu, 18 Dec 2003, D. Dante Lorenso wrote: > I have a simple table that I'd like to query to pull > out a heirarchy from a tree relationship. What is the > best way to do this without a 'CONNECT BY' clause like > Oracle has? > > Example > > mytable > +----------+-----------+ > | child_id | parent_id | > +----------+-----------+ > | 1 | NULL | > | 2 | NULL | > | 3 | 1 | > | 4 | 1 | > | 5 | 2 | > | 6 | 4 | > | 7 | 4 | > | 8 | 7 | > | 9 | 3 | > | 10 | 9 | > +----------+-----------+ > > I want to be able to select the child_id, parent_id, and the up-stream > heirarchy level when starting at a given child... > > In Oracle you'd use a statement like > > SELECT * > FROM account > START WITH child_id = 10 > CONNECT BY PRIOR parent_id = child_id; > (* note: may not be exactly correct *) > > I was thinking that PL/PGSQL could return a set using a function like > 'get_tree_relation(child_id INTEGER)' > > Example 1: > > SELECT * > FROM get_tree_relation(10) > ORDER BY level ASC; > > +----------+-----------+-------+ > | child_id | parent_id | level | > +----------+-----------+-------+ > | 10 | 9 | 1 | > | 9 | 3 | 2 | > | 3 | 1 | 3 | > | 1 | NULL | 4 | > +----------+-----------+-------+ > > Example 2: > > SELECT * > FROM get_tree_relation(2) > ORDER BY level ASC; > > +----------+-----------+-------+ > | child_id | parent_id | level | > +----------+-----------+-------+ > | 2 | NULL | 1 | > +----------+-----------+-------+ > > Example 2: > > SELECT * > FROM get_tree_relation(11) > ORDER BY level ASC; > > +----------+-----------+-------+ > | child_id | parent_id | level | > +----------+-----------+-------+ > +----------+-----------+-------+ > > I have a PL/PGSQL function that does this for me with some nested > selects inside a loop, but my NEW problem is that I need to be able > to detect circular loops. For example, if child_id refers to itself > or if a parent_id refers to a child_id that is already in the > heirarchy we don't want to get into an infinite loop. So I modified > my function to use a TEMP table to store the records I had already > seen, but then I had problems with the temp table: > > http://archives.postgresql.org/pgsql-bugs/2003-05/msg00084.php > > Without having to recompile any database code, can this process be > build using out-of-the-box PostgreSQL features? > > There's gotta be an easy way to do this. It's a fairly common > problem, isn't it? > > --Dante > > > > > > ---------------------------(end of broadcast)--------------------------- > TIP 9: the planner will ignore your desire to choose an index scan if your > joining column's datatypes do not match >
Joe Conway wrote: > D. Dante Lorenso wrote: > >> I have a simple table that I'd like to query to pull >> out a heirarchy from a tree relationship. What is the >> best way to do this without a 'CONNECT BY' clause like >> Oracle has? > > > See connectby() in contrib/tablefunc. Yep. That's what I was looking for. Had to upgrade to 7.4 and then install the contrib stuff and import those functions into my database. But, what a pain in the butt. I'd think this functionality would be so important that it'd make it into the main source. Kinda like MD5 did. Thanks again. Dante
Hi D. Dante Lorenso wrote: > I have a simple table that I'd like to query to pull > out a heirarchy from a tree relationship. What is the > best way to do this without a 'CONNECT BY' clause like > Oracle has? use connect_by from contrib. C.
Does anyone now how the algorithm for connect by works? Is it very efficient for large data sets? rg ----- Original Message ----- From: "CoL" <col@mportal.hu> To: <pgsql-general@postgresql.org> Sent: Friday, December 19, 2003 3:17 AM Subject: Re: [GENERAL] How to navigate tree without CONNECT BY? > Hi > > D. Dante Lorenso wrote: > > > I have a simple table that I'd like to query to pull > > out a heirarchy from a tree relationship. What is the > > best way to do this without a 'CONNECT BY' clause like > > Oracle has? > > use connect_by from contrib. > > C. > > ---------------------------(end of broadcast)--------------------------- > TIP 5: Have you checked our extensive FAQ? > > http://www.postgresql.org/docs/faqs/FAQ.html >