pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedBreadth first traversal in PLSQL (How to implement Queue?)
4+ messages / 3 participants
[nested] [flat]
* Breadth first traversal in PLSQL (How to implement Queue?)
@ 2004-12-15 18:54 Richard Rowell <richard@bowmansystems.com>
0 siblings, 2 replies; 4+ messages in thread
From: Richard Rowell @ 2004-12-15 18:54 UTC (permalink / raw)
To: pgsql-sql
I have a table with a unary (recursive) relationship that represents a
hierarchy. With the gracious help of Mike Rylander I was able to port a
TSQL function that would traverse "up" the hierarchy to PL/SQL. Now I
need help porting the "down" the hierarchy function.
As implemented in TSQL I utilized a simple breadth first tree traversal.
I'm not sure how to replicate this in PL/SQL as I haven't figured out
how to implement the queue required for the breadth first algorithm. My
queue is declared "queue SETOF INTEGER" and I'm able to "SELECT INTO"
this variable. However when I try to delete the "current" value, I get
a syntax error. If I comment the delete out, I also get an error when I
try to fetch the "next" value from the front of the queue.
Below is the function, followed by the psql output:
CREATE OR REPLACE FUNCTION svp_getchildproviderids (INTEGER)
RETURNS SETOF INTEGER
AS '
DECLARE
parent_provider ALIAS FOR $1;
cid INTEGER;
queue SETOF INTEGER;
BEGIN
SELECT INTO cid count(*) FROM providers WHERE uid =parent_provider;
IF cid = 0 THEN
RAISE EXCEPTION ''Inexistent ID --> %'', parent_provider;
RETURN;
END IF;
cid := parent_provider;
LOOP
EXIT WHEN cid IS NULL;
RETURN NEXT cid;
SELECT INTO queue uid FROM providers WHERE parent_id = cid;
DELETE FROM queue WHERE queue.queue = cid;
SELECT INTO cid * FROM queue LIMIT 1;
END LOOP;
RETURN;
END;' LANGUAGE 'plpgsql';
sp_demo_505=# select * from svp_getchildproviderids(1);
ERROR: syntax error at or near "$1" at character 14
CONTEXT: PL/pgSQL function "svp_getchildproviderids" line 16 at SQL
statement
--
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Breadth first traversal in PLSQL (How to implement Queue?)
@ 2004-12-16 02:48 Mike Rylander <mrylander@gmail.com>
parent: Richard Rowell <richard@bowmansystems.com>
1 sibling, 1 reply; 4+ messages in thread
From: Mike Rylander @ 2004-12-16 02:48 UTC (permalink / raw)
To: Richard Rowell <richard@bowmansystems.com>; +Cc: pgsql-sql
On Wed, 15 Dec 2004 12:54:44 -0600, Richard Rowell
<richard@bowmansystems.com> wrote:
> I have a table with a unary (recursive) relationship that represents a
> hierarchy. With the gracious help of Mike Rylander I was able to port a
> TSQL function that would traverse "up" the hierarchy to PL/SQL. Now I
> need help porting the "down" the hierarchy function.
Glad I could help!
>
> As implemented in TSQL I utilized a simple breadth first tree traversal.
> I'm not sure how to replicate this in PL/SQL as I haven't figured out
> how to implement the queue required for the breadth first algorithm. My
> queue is declared "queue SETOF INTEGER" and I'm able to "SELECT INTO"
> this variable. However when I try to delete the "current" value, I get
> a syntax error. If I comment the delete out, I also get an error when I
> try to fetch the "next" value from the front of the queue.
>
You probably want to use a temp table to hold the queue. Edits inline below.
> Below is the function, followed by the psql output:
>
> CREATE OR REPLACE FUNCTION svp_getchildproviderids (INTEGER)
> RETURNS SETOF INTEGER
> AS '
> DECLARE
> parent_provider ALIAS FOR $1;
> cid INTEGER;
-- Comment out the next line...
-- queue SETOF INTEGER;
> BEGIN
-- We need to use execute to create the queue, otherwise
-- the OID will be cached and the next invocation will cause
-- an exception.
EXECUTE ''CREATE TEMP TABLE cid_queue
(id SERIAL, cid INTEGER ) WITHOUT OIDS;'';
> SELECT INTO cid count(*) FROM providers WHERE uid =parent_provider;
> IF cid = 0 THEN
> RAISE EXCEPTION ''Inexistent ID --> %'', parent_provider;
> RETURN;
> END IF;
> cid := parent_provider;
> LOOP
> EXIT WHEN cid IS NULL;
> RETURN NEXT cid;
-- Put the CID into the queue
EXECUTE ''INSERT INTO cid_queue VALUES
((SELECT uid FROM providers WHERE
parent_id = '' ||
quote_literal( cid ) || ''));'';
-- We'll use EXECUTE to delete the current cid from the queue
EXECUTE ''DELETE FROM cid_queue WHERE cid = '' ||
quote_literal( cid ) || '';'';
-- And a short loop to grab the next one
FOR cid IN EXECUTE ''SELECT cid FROM cid_queue ORDER BY id LIMIT 1;''
END LOOP;
> END LOOP;
> RETURN;
> END;' LANGUAGE 'plpgsql';
Let me know if that works. As before, it's untested, so YMMV... :)
--
Mike Rylander
mrylander@gmail.com
GPLS -- PINES Development
Database Developer
http://open-ils.org
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Breadth first traversal in PLSQL (How to implement Queue?)
@ 2004-12-16 03:23 Mike Rylander <mrylander@gmail.com>
parent: Mike Rylander <mrylander@gmail.com>
0 siblings, 0 replies; 4+ messages in thread
From: Mike Rylander @ 2004-12-16 03:23 UTC (permalink / raw)
To: Richard Rowell <richard@bowmansystems.com>; +Cc: pgsql-sql
Arg! One more change below
On Wed, 15 Dec 2004 21:48:57 -0500, Mike Rylander <mrylander@gmail.com> wrote:
> On Wed, 15 Dec 2004 12:54:44 -0600, Richard Rowell
> <richard@bowmansystems.com> wrote:
> > I have a table with a unary (recursive) relationship that represents a
> > hierarchy. With the gracious help of Mike Rylander I was able to port a
> > TSQL function that would traverse "up" the hierarchy to PL/SQL. Now I
> > need help porting the "down" the hierarchy function.
>
> Glad I could help!
>
> >
> > As implemented in TSQL I utilized a simple breadth first tree traversal.
> > I'm not sure how to replicate this in PL/SQL as I haven't figured out
> > how to implement the queue required for the breadth first algorithm. My
> > queue is declared "queue SETOF INTEGER" and I'm able to "SELECT INTO"
> > this variable. However when I try to delete the "current" value, I get
> > a syntax error. If I comment the delete out, I also get an error when I
> > try to fetch the "next" value from the front of the queue.
> >
>
> You probably want to use a temp table to hold the queue. Edits inline below.
>
> > Below is the function, followed by the psql output:
> >
> > CREATE OR REPLACE FUNCTION svp_getchildproviderids (INTEGER)
> > RETURNS SETOF INTEGER
> > AS '
> > DECLARE
> > parent_provider ALIAS FOR $1;
> > cid INTEGER;
>
> -- Comment out the next line...
> -- queue SETOF INTEGER;
>
> > BEGIN
>
> -- We need to use execute to create the queue, otherwise
> -- the OID will be cached and the next invocation will cause
> -- an exception.
> EXECUTE ''CREATE TEMP TABLE cid_queue
> (id SERIAL, cid INTEGER ) WITHOUT OIDS;'';
>
> > SELECT INTO cid count(*) FROM providers WHERE uid =parent_provider;
> > IF cid = 0 THEN
> > RAISE EXCEPTION ''Inexistent ID --> %'', parent_provider;
> > RETURN;
> > END IF;
> > cid := parent_provider;
> > LOOP
> > EXIT WHEN cid IS NULL;
> > RETURN NEXT cid;
>
> -- Put the CID into the queue
> EXECUTE ''INSERT INTO cid_queue VALUES
> ((SELECT uid FROM providers WHERE
> parent_id = '' ||
> quote_literal( cid ) || ''));'';
>
> -- We'll use EXECUTE to delete the current cid from the queue
> EXECUTE ''DELETE FROM cid_queue WHERE cid = '' ||
> quote_literal( cid ) || '';'';
>
> -- And a short loop to grab the next one
> FOR cid IN EXECUTE ''SELECT cid FROM cid_queue ORDER BY id LIMIT 1;''
> END LOOP;
>
> > END LOOP;
-- We need to drop the temp table, since this will probably be called
-- more than once in a transaction.
EXECUTE ''DROP TABLE cid_queue;'';
> > RETURN;
> > END;' LANGUAGE 'plpgsql';
>
> Let me know if that works. As before, it's untested, so YMMV... :)
>
> --
> Mike Rylander
> mrylander@gmail.com
> GPLS -- PINES Development
> Database Developer
> http://open-ils.org
>
--
Mike Rylander
mrylander@gmail.com
GPLS -- PINES Development
Database Developer
http://open-ils.org
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Breadth first traversal in PLSQL (How to implement Queue?)
@ 2004-12-16 03:37 Andrew - Supernews <andrew+nonews@supernews.com>
parent: Richard Rowell <richard@bowmansystems.com>
1 sibling, 0 replies; 4+ messages in thread
From: Andrew - Supernews @ 2004-12-16 03:37 UTC (permalink / raw)
To: pgsql-sql
On 2004-12-15, Richard Rowell <richard@bowmansystems.com> wrote:
> I have a table with a unary (recursive) relationship that represents a
> hierarchy. With the gracious help of Mike Rylander I was able to port a
> TSQL function that would traverse "up" the hierarchy to PL/SQL. Now I
> need help porting the "down" the hierarchy function.
Have you looked at contrib/tablefunc's connectby() function?
--
Andrew, Supernews
http://www.supernews.com - individual and corporate NNTP services
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2004-12-16 03:37 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2004-12-15 18:54 Breadth first traversal in PLSQL (How to implement Queue?) Richard Rowell <richard@bowmansystems.com>
2004-12-16 02:48 ` Mike Rylander <mrylander@gmail.com>
2004-12-16 03:23 ` Mike Rylander <mrylander@gmail.com>
2004-12-16 03:37 ` Andrew - Supernews <andrew+nonews@supernews.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