pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedRecursive select
11+ messages / 11 participants
[nested] [flat]
* Recursive select
@ 2001-05-23 09:07 Martin Smetak <minca@no9.cz>
0 siblings, 1 reply; 11+ messages in thread
From: Martin Smetak @ 2001-05-23 09:07 UTC (permalink / raw)
To: pgsql-sql
Hi all!
Anyone know if it's possible to make a recursive select from a table ?
My problem: I got a table of "some categories" which all points to its
parrent one(tree)...shown below. And I want to select all names of
parrent categories of one child, lets say "fast[4]". Now I'm solving that
with
many SQL queries like : "SELECT main_id FROM cat WHERE id=4;"....but I would
like to optimize this.
Anyone can help or point me to a way ??
Thanks a lot,Minca
Table : CAT
ID | Main_id | Name
=========================
1 0 Car
2 1 Crash
3 1 Wash
4 3 Fast
5 1 Second_hand
6 0 House
7 3 Slow
....etc
*(root)[0]
-Car[1]
-Crash[2]
-Wash[3]
-Fast[4]
-Slow[7]
-Second hand[5]
-House[6]
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Recursive select
@ 2001-05-24 03:36 Ron Peterson <ron.peterson@yellowbank.com>
1 sibling, 0 replies; 11+ messages in thread
From: Ron Peterson @ 2001-05-24 03:36 UTC (permalink / raw)
To: Martin Smetak <minca_sql@no9.cz>; +Cc: pgsql-sql
Don't drive yourself crazy ( like me ;). You'll have to write some
procedural code - sorry. I believe IBM's DB/2 supports recursive
queries as defined by SQL3. Oracle provide a couple of non SQL standard
clauses (CONNECT BY, LEVELS) to provide similar funcionality.
-Ron-
GPG and other info at: http://www.yellowbank.com/
Martin Smetak wrote:
>
> Hi all!
>
> Anyone know if it's possible to make a recursive select from a table ?
> My problem: I got a table of "some categories" which all points to its
> parrent one(tree)...shown below. And I want to select all names of
> parrent categories of one child, lets say "fast[4]". Now I'm solving that
> with
> many SQL queries like : "SELECT main_id FROM cat WHERE id=4;"....but I would
> like to optimize this.
>
> Anyone can help or point me to a way ??
>
> Thanks a lot,Minca
>
> Table : CAT
> ID | Main_id | Name
> =========================
> 1 0 Car
> 2 1 Crash
> 3 1 Wash
> 4 3 Fast
> 5 1 Second_hand
> 6 0 House
> 7 3 Slow
> ....etc
>
> *(root)[0]
> -Car[1]
> -Crash[2]
> -Wash[3]
> -Fast[4]
> -Slow[7]
> -Second hand[5]
> -House[6]
>
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Don't 'kill -9' the postmaster
^ permalink raw reply [nested|flat] 11+ messages in thread
* Recursive select
@ 2001-05-24 13:44 Daniel Wickstrom <danw@rtp.ericsson.se>
1 sibling, 0 replies; 11+ messages in thread
From: Daniel Wickstrom @ 2001-05-24 13:44 UTC (permalink / raw)
To: Martin Smetak <minca_sql@no9.cz>; +Cc: pgsql-sql
>>>>> "Martin" == Martin Smetak <minca_sql@no9.cz> writes:
Martin> Hi all! Anyone know if it's possible to make a recursive
Martin> select from a table ? My problem: I got a table of "some
Martin> categories" which all points to its parrent
Martin> one(tree)...shown below. And I want to select all names of
Martin> parrent categories of one child, lets say "fast[4]". Now
Martin> I'm solving that with many SQL queries like : "SELECT
Martin> main_id FROM cat WHERE id=4;"....but I would like to
Martin> optimize this.
Martin> Anyone can help or point me to a way ??
The Openacs project has implemented a couple of different methods for
handling tree queries. Check out these two threads:
http://openacs.org/bboard/q-and-a-fetch-msg.tcl?msg_id=0000eC&topic_id=11&topic=OpenACS
http://openacs.org/bboard/q-and-a-fetch-msg.tcl?msg_id=0000j6&topic_id=12&topic=OpenACS%204%...
Regards,
Dan Wickstrom
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Recursive select
@ 2001-05-28 09:08 Martín Marqués <martin@bugs.unl.edu.ar>
parent: Martin Smetak <minca@no9.cz>
0 siblings, 0 replies; 11+ messages in thread
From: Martín Marqués @ 2001-05-28 09:08 UTC (permalink / raw)
To: Martin Smetak <minca@no9.cz>; +Cc: pgsql-sql
On Mié 23 May 2001 12:07, you wrote:
> Hi all!
>
> Anyone know if it's possible to make a recursive select from a table ?
> My problem: I got a table of "some categories" which all points to its
> parrent one(tree)...shown below. And I want to select all names of
> parrent categories of one child, lets say "fast[4]". Now I'm solving that
> with
> many SQL queries like : "SELECT main_id FROM cat WHERE id=4;"....but I
> would like to optimize this.
>
> Anyone can help or point me to a way ??
Sub-selects maybe?
SELECT main_id FROM cat WHERE id=(SELECT ID FROM cat WHERE name=crash)
Could this be what yo want?
Saludos.... :-)
> Thanks a lot,Minca
>
> Table : CAT
> ID | Main_id | Name
> =========================
> 1 0 Car
> 2 1 Crash
> 3 1 Wash
> 4 3 Fast
> 5 1 Second_hand
> 6 0 House
> 7 3 Slow
> ....etc
>
> *(root)[0]
> -Car[1]
> -Crash[2]
> -Wash[3]
> -Fast[4]
> -Slow[7]
> -Second hand[5]
> -House[6]
--
Cualquiera administra un NT.
Ese es el problema, que cualquiera administre.
-----------------------------------------------------------------
Martin Marques | mmarques@unl.edu.ar
Programador, Administrador | Centro de Telematica
Universidad Nacional
del Litoral
-----------------------------------------------------------------
^ permalink raw reply [nested|flat] 11+ messages in thread
* Recursive select
@ 2001-10-26 06:57 Jason Kwok <jason@newhonest.com>
0 siblings, 3 replies; 11+ messages in thread
From: Jason Kwok @ 2001-10-26 06:57 UTC (permalink / raw)
To: pgsql-sql
I have a table :
MyID parentID
================
5 6
6 7
3 13
7 3
Is there any simple select statement that can get all rows with MyID = 5 and
all its parents?
That means 5's parenet is 6, 6's parent is 7, 7's parent is 3.....
Jason
---
Virus Free
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.286 / Virus Database: 152 - Release Date: 2001/10/9
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Recursive select
@ 2001-10-29 18:57 Esteban Gutierrez Abarzua <esgutier@sauce.chillan.ubiobio.cl>
parent: Jason Kwok <jason@newhonest.com>
2 siblings, 0 replies; 11+ messages in thread
From: Esteban Gutierrez Abarzua @ 2001-10-29 18:57 UTC (permalink / raw)
To: Jason Kwok <jason@newhonest.com>; +Cc: pgsql-sql
On Fri, 26 Oct 2001, Jason Kwok wrote:
> I have a table :
>
> MyID parentID
> ================
> 5 6
> 6 7
> 3 13
> 7 3
>
> Is there any simple select statement that can get all rows with MyID = 5 and
> all its parents?
> That means 5's parenet is 6, 6's parent is 7, 7's parent is 3.....
>
>
> Jason
>
I think that this is not possible.
You may do it using sql embedded or jdbc!
bye.
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Recursive select
@ 2001-10-29 19:44 Greg Sabino Mullane <greg@turnstep.com>
0 siblings, 0 replies; 11+ messages in thread
From: Greg Sabino Mullane @ 2001-10-29 19:44 UTC (permalink / raw)
To: pgsql-sql
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
> Is there any simple select statement that can get all rows
> with MyID = 5 and all its parents?
Simple? No. You can do it directly with SQL if you know how
"deep" you want to recurse. For example, a single level
would be:
SELECT * FROM foo
WHERE myid = 5
OR myid IN
(SELECT parentid FROM foo WHERE myID=5)
while two levels would be:
SELECT * FROM foo
WHERE myid = 5
OR myid IN
(SELECT parentid FROM foo WHERE myID=5)
OR myID in
(SELECT parentID FROM foo WHERE myid in
(SELECT parentID FROM foo WHERE myid=5));
etc. It only gets worse from there. :) For unlimited recursion,
you'll have to have a client slurp all the parent and children
into some sort of lookup table (e.g. a hash) and then loop
through until you've found them all. Here's a small perl example,
assuming you are using DBI, RaiseError is true, and 'myid'
is a unique column:
my $FOO_SQL = "SELECT myid, parentid, 'whateverelse' FROM foo";
my $foo_h = $dbh->prepare($FOO_SQL);
$foo_h->execute();
my %parent;
while(defined($_=$foo_h->fetchrow_arrayref())) {
$parent{$_->[0]}=$_->[1];
}
my %seenit;
my $winner = 5;
{
my $newwinner = $parent{$winner};
last if !defined $newwinner or $seenit{$newwinner}++;
print "Found myid: $winner parentid: $newwinner\n";
$winner = $newwinner;
redo;
}
Doesn't have to perl of course, but it has to be something that
can store variables and perform basic iteration.
Greg Sabino Mullane
greg@turnstep.com
PGP Key: 0x14964AC8 200110291441
-----BEGIN PGP SIGNATURE-----
Comment: http://www.turnstep.com/pgp.html
iQA/AwUBO92xbLybkGcUlkrIEQL4PACgx0IvEybczRwcepxjYwWOhEEEwx0AnRNW
dYx/8hHp36sjWhpXyv+cN3sc
=NvbM
-----END PGP SIGNATURE-----
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Recursive select
@ 2001-10-29 22:09 Keith Gray <keith@heart.com.au>
parent: Jason Kwok <jason@newhonest.com>
2 siblings, 0 replies; 11+ messages in thread
From: Keith Gray @ 2001-10-29 22:09 UTC (permalink / raw)
To: Jason Kwok <jason@newhonest.com>; +Cc: pgsql-sql
Jason Kwok wrote:
>
> I have a table :
>
> MyID parentID
> ================
> 5 6
> 6 7
> 3 13
> 7 3
>
> Is there any simple select statement that can get all rows with MyID = 5 and
> all its parents?
> That means 5's parenet is 6, 6's parent is 7, 7's parent is 3.....
>
I had a similar problem a couple of weeks back.
The only way I could get around it was "programmatically".
This is an iterative (loop) problem.
Because I am writing for several brands/flavours of database
I solved it in VB, but some solutions (for postgres only)
are offered using functions or triggers in PgSQL.
--
Keith Gray
Technical Development Manager
Heart Consulting Services P/L
mailto:keith@heart.com.au
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Recursive select
@ 2001-10-29 22:47 Roberto Mello <rmello@cc.usu.edu>
parent: Jason Kwok <jason@newhonest.com>
2 siblings, 1 reply; 11+ messages in thread
From: Roberto Mello @ 2001-10-29 22:47 UTC (permalink / raw)
To: Jason Kwok <jason@newhonest.com>; +Cc: pgsql-sql
On Fri, Oct 26, 2001 at 02:57:18PM +0800, Jason Kwok wrote:
> I have a table :
>
> MyID parentID
> ================
> 5 6
> 6 7
> 3 13
> 7 3
>
> Is there any simple select statement that can get all rows with MyID = 5 and
> all its parents?
Dan Wickstrom, of the OpenACS.org team, implemented a bunch of PL/pgSQL
functions to do what you're after. It simulates the CONNECT BY behaviour
in Oracle.
OpenACS 4 is GPL'd, so you can look at the source. I need to extract the
relevant sections and post them in the PostgreSQL Cookbook (actually, I
think there are a couple tree functions in there -
http://www.brasileiro.net/postgres/)
-Roberto
--
+----| http://fslc.usu.edu USU Free Software & GNU/Linux Club |------+
Roberto Mello - Computer Science, USU - http://www.brasileiro.net
http://www.sdl.usu.edu - Space Dynamics Lab, Developer
Always forgive your enemies. They hate that!
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Recursive select
@ 2001-11-01 01:14 --CELKO-- <71062.1056@compuserve.com>
parent: Roberto Mello <rmello@cc.usu.edu>
0 siblings, 1 reply; 11+ messages in thread
From: 71062.1056@compuserve.com @ 2001-11-01 01:14 UTC (permalink / raw)
To: pgsql-sql
The usual example of a tree structure in SQL books is called an
adjacency list model and it looks like this:
CREATE TABLE Personnel
(emp CHAR(10) NOT NULL PRIMARY KEY,
boss CHAR(10) DEFAULT NULL REFERENCES Personnel(emp),
salary DECIMAL(6,2) NOT NULL DEFAULT 100.00);
Personnel
emp boss salary
===========================
'Albert' 'NULL' 1000.00
'Bert' 'Albert' 900.00
'Chuck' 'Albert' 900.00
'Donna' 'Chuck' 800.00
'Eddie' 'Chuck' 700.00
'Fred' 'Chuck' 600.00
Another way of representing trees is to show them as nested sets.
Since SQL is a set oriented language, this is a better model than the
usual adjacency list approach you see in most text books. Let us
define a simple Personnel table like this, ignoring the left (lft) and
right (rgt) columns for now. This problem is always given with a
column for the employee and one for his boss in the textbooks. This
table without the lft and rgt columns is called the adjacency list
model, after the graph theory technique of the same name; the pairs of
nodes are adjacent to each other.
CREATE TABLE Personnel
(emp CHAR(10) NOT NULL PRIMARY KEY,
lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
CONSTRAINT order_okay CHECK (lft < rgt) );
Personnel
emp lft rgt
======================
'Albert' 1 12
'Bert' 2 3
'Chuck' 4 11
'Donna' 5 6
'Eddie' 7 8
'Fred' 9 10
The organizational chart would look like this as a directed graph:
Albert (1,12)
/ \
/ \
Bert (2,3) Chuck (4,11)
/ | \
/ | \
/ | \
/ | \
Donna (5,6) Eddie (7,8) Fred (9,10)
The first table is denormalized in several ways. We are modeling both
the personnel and the organizational chart in one table. But for the
sake of saving space, pretend that the names are job titles and that
we have another table which describes the personnel that hold those
positions.
Another problem with the adjacency list model is that the boss and
employee columns are the same kind of thing (i.e. names of personnel),
and therefore should be shown in only one column in a normalized
table. To prove that this is not normalized, assume that "Chuck"
changes his name to "Charles"; you have to change his name in both
columns and several places. The defining characteristic of a
normalized table is that you have one fact, one place, one time.
The final problem is that the adjacency list model does not model
subordination. Authority flows downhill in a hierarchy, but If I fire
Chuck, I disconnect all of his subordinates from Albert. There are
situations (i.e. water pipes) where this is true, but that is not the
expected situation in this case.
To show a tree as nested sets, replace the nodes with ovals, then nest
subordinate ovals inside each other. The root will be the largest
oval and will contain every other node. The leaf nodes will be the
innermost ovals with nothing else inside them and the nesting will
show the hierarchical relationship. The rgt and lft columns (I cannot
use the reserved words LEFT and RIGHT in SQL) are what shows the
nesting.
If that mental model does not work, then imagine a little worm
crawling anti-clockwise along the tree. Every time he gets to the
left or right side of a node, he numbers it. The worm stops when he
gets all the way around the tree and back to the top.
This is a natural way to model a parts explosion, since a final
assembly is made of physically nested assemblies that final break down
into separate parts.
At this point, the boss column is both redundant and denormalized, so
it can be dropped. Also, note that the tree structure can be kept in
one table and all the information about a node can be put in a second
table and they can be joined on employee number for queries.
To convert the graph into a nested sets model think of a little worm
crawling along the tree. The worm starts at the top, the root, makes
a complete trip around the tree. When he comes to a node, he puts a
number in the cell on the side that he is visiting and increments his
counter. Each node will get two numbers, one of the right side and
one for the left. Computer Science majors will recognize this as a
modified preorder tree traversal algorithm. Finally, drop the
unneeded Personnel.boss column which used to represent the edges of a
graph.
This has some predictable results that we can use for building
queries. The root is always (left = 1, right = 2 * (SELECT COUNT(*)
FROM TreeTable)); leaf nodes always have (left + 1 = right); subtrees
are defined by the BETWEEN predicate; etc. Here are two common
queries which can be used to build others:
1. An employee and all their Supervisors, no matter how deep the tree.
SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P1.emp = :myemployee;
2. The employee and all subordinates. There is a nice symmetry here.
SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P2.emp = :myemployee;
3. Add a GROUP BY and aggregate functions to these basic queries and
you have hierarchical reports. For example, the total salaries which
each employee controls:
SELECT P2.emp, SUM(S1.salary)
FROM Personnel AS P1, Personnel AS P2,
Salaries AS S1
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P1.emp = S1.emp
GROUP BY P2.emp;
4. To find the level of each node, so you can print the tree as an
indented listing.
DECLARE Out_Tree CURSOR FOR
SELECT P1.lft, COUNT(P2.emp) AS indentation, P1.emp
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
GROUP BY P1.emp
ORDER BY P1.lft;
5. The nested set model has an implied ordering of siblings which the
adjacency list model does not. To insert a new node as the rightmost
sibling.
BEGIN
DECLARE right_most_sibling INTEGER;
SET right_most_sibling
= (SELECT rgt
FROM Personnel
WHERE emp = :your_boss);
UPDATE Personnel
SET lft = CASE WHEN lft > right_most_sibling
THEN lft + 2
ELSE lft END,
rgt = CASE WHEN rgt >= right_most_sibling
THEN rgt + 2
ELSE rgt END
WHERE rgt >= right_most_sibling;
INSERT INTO Personnel (emp, lft, rgt)
VALUES ('New Guy', right_most_sibling, (right_most_sibling + 1))
END;
6. To convert an adjacency list model into a nested set model, use a
push down stack algorithm. Assume that we have these tables:
-- Tree holds the adjacency model
CREATE TABLE Tree
(emp CHAR(10) NOT NULL,
boss CHAR(10));
INSERT INTO Tree
SELECT emp, boss FROM Personnel;
-- Stack starts empty, will holds the nested set model
CREATE TABLE Stack
(stack_top INTEGER NOT NULL,
emp CHAR(10) NOT NULL,
lft INTEGER,
rgt INTEGER);
BEGIN ATOMIC
DECLARE counter INTEGER;
DECLARE max_counter INTEGER;
DECLARE current_top INTEGER;
SET counter = 2;
SET max_counter = 2 * (SELECT COUNT(*) FROM Tree);
SET current_top = 1;
INSERT INTO Stack
SELECT 1, emp, 1, NULL
FROM Tree
WHERE boss IS NULL;
DELETE FROM Tree
WHERE boss IS NULL;
WHILE counter <= (max_counter - 2)
LOOP IF EXISTS (SELECT *
FROM Stack AS S1, Tree AS T1
WHERE S1.emp = T1.boss
AND S1.stack_top = current_top)
THEN
BEGIN -- push when top has subordinates and set lft value
INSERT INTO Stack
SELECT (current_top + 1), MIN(T1.emp), counter, NULL
FROM Stack AS S1, Tree AS T1
WHERE S1.emp = T1.boss
AND S1.stack_top = current_top;
DELETE FROM Tree
WHERE emp = (SELECT emp
FROM Stack
WHERE stack_top = current_top + 1);
SET counter = counter + 1;
SET current_top = current_top + 1;
END
ELSE
BEGIN -- pop the stack and set rgt value
UPDATE Stack
SET rgt = counter,
stack_top = -stack_top -- pops the stack
WHERE stack_top = current_top
SET counter = counter + 1;
SET current_top = current_top - 1;
END IF;
END LOOP;
END;
This approach will be two to three orders of magnitude faster than the
adjacency list model for subtree and aggregate operations.
For details, see the chapter in my book JOE CELKO'S SQL FOR SMARTIES
(Morgan-Kaufmann, 1999, second edition)
^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Recursive select
@ 2001-11-04 17:03 knut.suebert@web.de
parent: --CELKO-- <71062.1056@compuserve.com>
0 siblings, 0 replies; 11+ messages in thread
From: knut.suebert@web.de @ 2001-11-04 17:03 UTC (permalink / raw)
To: pgsql-sql
--CELKO-- schrieb:
> Another way of representing trees is to show them as nested sets.
Good evening,
that's what I needed!
To limit the result to entries below one node, I'd use something like
SELECT P1.lft, COUNT(P2.emp) AS indentation, P1.emp
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND p1.lft>(SELECT lft FROM personnel WHERE emp='Chuck')
AND p1.rgt<(SELECT rgt FROM personnel WHERE emp='Chuck')
GROUP BY P1.emp, p1.lft ORDER BY P1.lft;
lft | indentation | emp
-----+-------------+------------
5 | 3 | Donna
7 | 3 | Eddie
9 | 3 | Fred
(3 rows)
for emp='Albert' it returns
lft | indentation | emp
-----+-------------+------------
2 | 2 | Bert
4 | 2 | Chuck
5 | 3 | Donna
7 | 3 | Eddie
9 | 3 | Fred
(5 rows)
My question is, how to limit this result to (Albert's indentation)+1?
Thanks,
Knut Sübert
^ permalink raw reply [nested|flat] 11+ messages in thread
end of thread, other threads:[~2001-11-04 17:03 UTC | newest]
Thread overview: 11+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2001-05-23 09:07 Recursive select Martin Smetak <minca@no9.cz>
2001-05-28 09:08 ` Martín Marqués <martin@bugs.unl.edu.ar>
2001-05-24 03:36 ` Ron Peterson <ron.peterson@yellowbank.com>
2001-05-24 13:44 ` Daniel Wickstrom <danw@rtp.ericsson.se>
2001-10-26 06:57 Recursive select Jason Kwok <jason@newhonest.com>
2001-10-29 18:57 ` Esteban Gutierrez Abarzua <esgutier@sauce.chillan.ubiobio.cl>
2001-10-29 22:09 ` Keith Gray <keith@heart.com.au>
2001-10-29 22:47 ` Roberto Mello <rmello@cc.usu.edu>
2001-11-01 01:14 ` --CELKO-- <71062.1056@compuserve.com>
2001-11-04 17:03 ` knut.suebert@web.de
2001-10-29 19:44 Re: Recursive select Greg Sabino Mullane <greg@turnstep.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox