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

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

From
Richard Rowell
Date:
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 '
DECLAREparent_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
''InexistentID --> %'', 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
WHEREqueue.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


-- 



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

From
Mike Rylander
Date:
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


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

From
Mike Rylander
Date:
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


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

From
Andrew - Supernews
Date:
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