From: Mike Rylander <mrylander@gmail.com>
To: Richard Rowell <richard@bowmansystems.com>
Cc: PostgreSQL SQL <pgsql-sql@postgresql.org>
Subject: Re: Breadth first traversal in PLSQL (How to implement Queue?)
Date: Wed, 15 Dec 2004 21:48:57 -0500
Message-ID: <b918cf3d04121518481a0744ae@mail.gmail.com> (raw)
In-Reply-To: <1103136884.9908.22.camel@richard>
References: <1103136884.9908.22.camel@richard>
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: mrylander@gmail.com, richard@bowmansystems.com
Subject: Re: Breadth first traversal in PLSQL (How to implement Queue?)
In-Reply-To: <b918cf3d04121518481a0744ae@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
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