Re: plpgsql recursion

Greetings!
I have a table like:

node parent
1 2
2 3
3 4

Since i traverse this table with a recursive function, i want to avoid
infinite recursion loop. I have wrote a function to check that a new record
does not create a circular dependency. The function i wrote is as follow:

CREATE OR REPLACE FUNCTION dba_test(INTEGER,INTEGER) RETURNS TEXT AS '
DECLARE
traversing ALIAS FOR $1;
testing ALIAS FOR $2;
t_rec RECORD;
BEGIN
FOR t_rec IN SELECT node,parent FROM dba_test WHERE parent = traversing
LOOP
IF t_rec.node = testing THEN
RETURN ''Circular'';
ELSE
PERFORM dba_test(t_rec.node,testing);
END IF;
END LOOP;
RETURN ''ok'' || testing::text;
END;
' LANGUAGE 'plpgsql';

I would use this function BEFORE inserting the new row. But if i try SELECT
dba_test(4,1); i don't have the result i expect. Can i you give me an hint
where am i wrong?

Thank you!

Stefano Vita Finzi
kluge(at)despammed(dot)com

Stefan,

I just downloaded PostgreSQL and I thought it would be a good learning
experience to figure out your problem. My background is as an Oracle
programmer but I haven't been using PL/SQL for a while.

Anyway, I tested your procedure and I got ok1. I think that you expected
"circular". I am afraid I am stumped as to why you do not get "circular" as
a result.

I was trying to figure out how to debug a plpgsql program. I finally figured
out that I could insert the values of node, and testing at each iteration of
the loop which in this case was the same as each time the module was called
recursively. I got

(3, 1)
(2, 1)
(1, 1) --> At this point t_rec.node should have equaled testing and I would
have expected Circular to be returned. It didn't and I am completely
stumped.

There does seem to be a logical error with what you are doing though, but it
does not change the fact that the code seems to be acting incorrectly.

The reason your code seems to be illogical is that your hierarchy is
4-->3-->2-->1 where 4 is the top parent. Your code seems to be testing to
see whether inserting 4-->1 would cause a problem. That is you are saying
that the following is wrong

4
/ \
3 1
/
2
/
1

It is not checking for a circular relationship. I believe that you should go
down the hierarchy recursively and find that inserting 1-->4 causes a
circular relationship because 4 is ultimately a child of 4. I don't believe
that this is what your code is doing.

Another thing that does not affect your test but seems to be incorrect is
that I expected the row 4-->NULL to be in the table since 4 was at the top
of your hierarchy.

Vincent Hikida,
Member of Technical Staff - Urbana Software, Inc.
"A Personalized Learning Experience"

www.UrbanaSoft.com

----- Original Message -----
From: "Stefano Vita Finzi" <stefano(dot)vita(at)pronesis(dot)it>
To: <pgsql-general(at)postgresql(dot)org>
Sent: Tuesday, May 20, 2003 9:52 AM
Subject: [GENERAL] plpgsql recursion

> Greetings!
> I have a table like:
>
> node parent
> 1 2
> 2 3
> 3 4
>
> Since i traverse this table with a recursive function, i want to avoid
> infinite recursion loop. I have wrote a function to check that a new
record
> does not create a circular dependency. The function i wrote is as follow:
>
> CREATE OR REPLACE FUNCTION dba_test(INTEGER,INTEGER) RETURNS TEXT AS '
> DECLARE
> traversing ALIAS FOR $1;
> testing ALIAS FOR $2;
> t_rec RECORD;
> BEGIN
> FOR t_rec IN SELECT node,parent FROM dba_test WHERE parent =
traversing
> LOOP
> IF t_rec.node = testing THEN
> RETURN ''Circular'';
> ELSE
> PERFORM dba_test(t_rec.node,testing);
> END IF;
> END LOOP;
> RETURN ''ok'' || testing::text;
> END;
> ' LANGUAGE 'plpgsql';
>
> I would use this function BEFORE inserting the new row. But if i try
SELECT
> dba_test(4,1); i don't have the result i expect. Can i you give me an hint
> where am i wrong?
>
> Thank you!
>
> Stefano Vita Finzi
> kluge(at)despammed(dot)com
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 1: subscribe and unsubscribe commands go to majordomo(at)postgresql(dot)org
>

Forget what I said about your code not being logical. It is correct.

What you are saying is that you want to add the fact that 4 is a child of 1.
If you find that 1 is a child of 4 either directly or transitively, then you
have a circular relationship.

Vincent Hikida,
Member of Technical Staff - Urbana Software, Inc.
"A Personalized Learning Experience"

www.UrbanaSoft.com

----- Original Message -----
From: "Vincent Hikida" <vhikida(at)inreach(dot)com>
To: <pgsql-general(at)postgresql(dot)org>
Sent: Saturday, May 24, 2003 7:07 PM
Subject: Re: [GENERAL] plpgsql recursion

> Stefan,
>
> I just downloaded PostgreSQL and I thought it would be a good learning
> experience to figure out your problem. My background is as an Oracle
> programmer but I haven't been using PL/SQL for a while.
>
> Anyway, I tested your procedure and I got ok1. I think that you expected
> "circular". I am afraid I am stumped as to why you do not get "circular"
as
> a result.
>
> I was trying to figure out how to debug a plpgsql program. I finally
figured
> out that I could insert the values of node, and testing at each iteration
of
> the loop which in this case was the same as each time the module was
called
> recursively. I got
>
> (3, 1)
> (2, 1)
> (1, 1) --> At this point t_rec.node should have equaled testing and I
would
> have expected Circular to be returned. It didn't and I am completely
> stumped.
>
> There does seem to be a logical error with what you are doing though, but
it
> does not change the fact that the code seems to be acting incorrectly.
>
> The reason your code seems to be illogical is that your hierarchy is
> 4-->3-->2-->1 where 4 is the top parent. Your code seems to be testing to
> see whether inserting 4-->1 would cause a problem. That is you are saying
> that the following is wrong
>
> 4
> / \
> 3 1
> /
> 2
> /
> 1
>
> It is not checking for a circular relationship. I believe that you should
go
> down the hierarchy recursively and find that inserting 1-->4 causes a
> circular relationship because 4 is ultimately a child of 4. I don't
believe
> that this is what your code is doing.
>
> Another thing that does not affect your test but seems to be incorrect is
> that I expected the row 4-->NULL to be in the table since 4 was at the top
> of your hierarchy.
>
> Vincent Hikida,
> Member of Technical Staff - Urbana Software, Inc.
> "A Personalized Learning Experience"
>
> www.UrbanaSoft.com
>
> ----- Original Message -----
> From: "Stefano Vita Finzi" <stefano(dot)vita(at)pronesis(dot)it>
> To: <pgsql-general(at)postgresql(dot)org>
> Sent: Tuesday, May 20, 2003 9:52 AM
> Subject: [GENERAL] plpgsql recursion
>
>
> > Greetings!
> > I have a table like:
> >
> > node parent
> > 1 2
> > 2 3
> > 3 4
> >
> > Since i traverse this table with a recursive function, i want to avoid
> > infinite recursion loop. I have wrote a function to check that a new
> record
> > does not create a circular dependency. The function i wrote is as
follow:
> >
> > CREATE OR REPLACE FUNCTION dba_test(INTEGER,INTEGER) RETURNS TEXT AS '
> > DECLARE
> > traversing ALIAS FOR $1;
> > testing ALIAS FOR $2;
> > t_rec RECORD;
> > BEGIN
> > FOR t_rec IN SELECT node,parent FROM dba_test WHERE parent =
> traversing
> > LOOP
> > IF t_rec.node = testing THEN
> > RETURN ''Circular'';
> > ELSE
> > PERFORM dba_test(t_rec.node,testing);
> > END IF;
> > END LOOP;
> > RETURN ''ok'' || testing::text;
> > END;
> > ' LANGUAGE 'plpgsql';
> >
> > I would use this function BEFORE inserting the new row. But if i try
> SELECT
> > dba_test(4,1); i don't have the result i expect. Can i you give me an
hint
> > where am i wrong?
> >
> > Thank you!
> >
> > Stefano Vita Finzi
> > kluge(at)despammed(dot)com
> >
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 1: subscribe and unsubscribe commands go to majordomo(at)postgresql(dot)org
> >
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 6: Have you searched our list archives?
>
> http://archives.postgresql.org
>

Stefan,

I finally figured it out. After you make the final recursive call, it
returns 'circular'. However it then returns to the function that it was
called from recursively. At that point it immediately completes the loop and
the return is set to ok on up the call structure. The code should be written
as follows:

CREATE OR REPLACE FUNCTION dba_test(INTEGER,INTEGER) RETURNS TEXT AS '
DECLARE
traversing ALIAS FOR $1;
testing ALIAS FOR $2;
t_rec RECORD;
status TEXT;
BEGIN
status := ''ok'';
FOR t_rec IN SELECT node,parent FROM dba_test WHERE parent = traversing
LOOP
IF t_rec.node = testing THEN
status := ''Circular'';
ELSE
SELECT dba_test(t_rec.node,testing) INTO STATUS;
END IF;
END LOOP;
RETURN status;
END;
' LANGUAGE 'plpgsql';

Vincent Hikida,
Member of Technical Staff - Urbana Software, Inc.
"A Personalized Learning Experience"

www.UrbanaSoft.com

----- Original Message -----
From: "Stefano Vita Finzi" <stefano(dot)vita(at)pronesis(dot)it>
To: <pgsql-general(at)postgresql(dot)org>
Sent: Tuesday, May 20, 2003 9:52 AM
Subject: [GENERAL] plpgsql recursion

> Greetings!
> I have a table like:
>
> node parent
> 1 2
> 2 3
> 3 4
>
> Since i traverse this table with a recursive function, i want to avoid
> infinite recursion loop. I have wrote a function to check that a new
record
> does not create a circular dependency. The function i wrote is as follow:
>
> CREATE OR REPLACE FUNCTION dba_test(INTEGER,INTEGER) RETURNS TEXT AS '
> DECLARE
> traversing ALIAS FOR $1;
> testing ALIAS FOR $2;
> t_rec RECORD;
> BEGIN
> FOR t_rec IN SELECT node,parent FROM dba_test WHERE parent =
traversing
> LOOP
> IF t_rec.node = testing THEN
> RETURN ''Circular'';
> ELSE
> PERFORM dba_test(t_rec.node,testing);
> END IF;
> END LOOP;
> RETURN ''ok'' || testing::text;
> END;
> ' LANGUAGE 'plpgsql';
>
> I would use this function BEFORE inserting the new row. But if i try
SELECT
> dba_test(4,1); i don't have the result i expect. Can i you give me an hint
> where am i wrong?
>
> Thank you!
>
> Stefano Vita Finzi
> kluge(at)despammed(dot)com
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 1: subscribe and unsubscribe commands go to majordomo(at)postgresql(dot)org
>