DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:references;
	b=kNdeNpuAeEOBz8++CTtB/mUV0vBI9//wjLDVzLpPtgyBFZZqVMK9VbmdBOw6Gym615Ts0bxyN5Ginj72HFgqZ9CdWu6ZZgEkfoEgbwyZPiI4XwfvXd0Ruf1un41t5AHcbmRu2gtlCfTVY3cPOVeHJjqMVCdTh+HdMQ1b6nOV/1I=
Message-ID: <b918cf3d04121518481a0744ae@mail.gmail.com>
Date: Wed, 15 Dec 2004 21:48:57 -0500
From: Mike Rylander <mrylander@gmail.com>
Reply-To: Mike Rylander <mrylander@gmail.com>
To: Richard Rowell <richard@bowmansystems.com>
Subject: Re: Breadth first traversal in PLSQL (How to implement Queue?)
Cc: PostgreSQL SQL <pgsql-sql@postgresql.org>
In-Reply-To: <1103136884.9908.22.camel@richard>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
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