Re: Breadth first traversal in PLSQL (How to implement Queue?)

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 )
WITHOUTOIDS;'';
 

>    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
((SELECTuid 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
LIMIT1;''          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