Recursive SQL Question on breaking the infinite loop.

[Pivot_Tables]

Hi,

I have created a recursive SQL Query in DB2 and it works fine until
some point in the tree where the data gets into infinite loop. Below
are some sample data from my relationship table.

Relationship Table
PARENT FIELD CHILD FIELD
AAA BBB
AAA CCC
AAA DDD
BBB EEE
BBB FFF
BBB AAA
CCC GGG
CCC AAA
DDD HHH
DDD AAA
EEE BBB
FFF BBB
GGG CCC
HHH DDD

If you notice the data the all the data are in cycle. That is because
the table has data from top to bottom tree as well as bottom to top
tree. I want to know how I can use the CYCLE Phrase to break the
infinite loop. I only am interested in gathering the data in the one
direction, say from Top Root to Bottom leaf ( I want to construct a
Tree from AAA all the way to GGG/HHH downwards.

Could you someone provide me with some samples or guide me the correct
direction. I reallly appreciate your time in reviewing this question
and responding to the post.

[Serge Rielau]

Pivot_Tables wrote:

I have created a recursive SQL Query in DB2 and it works fine until
some point in the tree where the data gets into infinite loop. Below
are some sample data from my relationship table.

Relationship Table
PARENT FIELD CHILD FIELD
AAA BBB
AAA CCC
AAA DDD
BBB EEE
BBB FFF
BBB AAA
CCC GGG
CCC AAA
DDD HHH
DDD AAA
EEE BBB
FFF BBB
GGG CCC
HHH DDD

If you notice the data the all the data are in cycle. That is because
the table has data from top to bottom tree as well as bottom to top
tree. I want to know how I can use the CYCLE Phrase to break the
infinite loop. I only am interested in gathering the data in the one
direction, say from Top Root to Bottom leaf ( I want to construct a
Tree from AAA all the way to GGG/HHH downwards.

Could you someone provide me with some samples or guide me the correct
direction. I reallly appreciate your time in reviewing this question
and responding to the post.

Which version of DB2? Which platform and which from of recusrion are you
using (WITH UNION ALL vs. CONNECT BY)

Cheers
Serge

--
Serge Rielau
DB2 Solutions Development
IBM Toronto Lab

[Pivot_Tables]

On Aug 9, 12:43*pm, Lennart <[e-mail]:

On Aug 9, 4:17*pm, Pivot_Tables <[e-mail]:

Hi,

I have created arecursive SQLQuery in DB2 and it works fine until
some point in the tree where the data gets into infinite loop. Below
are some sample data from my relationship table.

Relationship Table
PARENT FIELD * * * * * * * * * * *CHILD FIELD
AAA * * * * * * * * * * * * * * * * ** *BBB
AAA * * * * * * * * * * * * * * * * ** *CCC
AAA * * * * * * * * * * * * * * * * ** *DDD
BBB * * * * * * * * * * * * * * * * ** *EEE
BBB * * * * * * * * * * * * * * * * ** *FFF
BBB * * * * * * * * * * * * * * * * ** *AAA
CCC * * * * * * * * * * * * * * * * ** *GGG
CCC * * * * * * * * * * * * * * * * ** *AAA
DDD * * * * * * * * * * * * * * * * ** *HHH
DDD * * * * * * * * * * * * * * * * ** *AAA
EEE * * * * * * * * * * * * * * * * ** *BBB
FFF * * * * * * * * * * * * * * * * ** * BBB
GGG * * * * * * * * * * * * * * * * ** CCC
HHH * * * * * * * * * * * * * * * * ** *DDD

If you notice the data the all the data are in cycle. That is because
the table has data from top to bottom tree as well as bottom to top
tree.

Why? How can you tell whether A is the parent of B or the other way
around and what does it mean if someone deletes the tupel (AAA,BBB)
but leaves the tuple (BBB,AAA)?

[...]

/Lennart- Hide quoted text -

- Show quoted text -

Lenmart,

My application is such that if user creates a relationship like AAA ---

BBB it automatically creates BBB ---AAA relationship if you

looking at the tree bottoms up. I donot know why the application was
created in such a way but I just need to come up with a recursive SQL
where I go in one direction and to be more specific I want the tree
from root node to leaf node means downwards in the tree.

Just to answer a question, if someone deletes AAA,BBB it will
automatically delates BBB,AAA, so I donot worry about the data but I
just want to generate it downwords.

Serge, DB2 version is 9 with fix pack 4. Also, I am using common table
expression (CTE) using WITH phrash using UNION ALL. I thought the
CONNECT BY is for ORACLE. Does it work with DB2 as well. If yes, could
you tell me which one is better?

Thanks for looking into this and responding promptly.

Thanks!

[Lennart]

On Aug 10, 5:37*am, Pivot_Tables <[e-mail]:
[...]

>
Lenmart,

My application is such that if user creates a relationship like AAA ---BBB it automatically creates BBB *---AAA relationship if you

looking at the tree bottoms up. I donot know why the application was
created in such a way but I just need to come up with a recursive SQL
where I go in one direction and to be more specific I want the tree
from root node to leaf node means downwards in the tree.

For starters, how do you determine the root node? Is there some
additional info, for example an implicit ordering relation such that
AAA < CCC? What does your current query look like?

/Lennart

[...]

[Pivot_Tables]

On Aug 10, 2:41*am, Lennart <[e-mail]:

On Aug 10, 5:37*am, Pivot_Tables <[e-mail]:
[...]

Lenmart,

My application is such that if user creates a relationship like AAA ---BBB it automatically creates BBB *---AAA relationship if you

looking at the tree bottoms up. I donot know why the application was
created in such a way but I just need to come up with a recursive SQL
where I go in one direction and to be more specific I want the tree
from root node to leaf node means downwards in the tree.

For starters, how do you determine the root node? Is there some
additional info, for example an implicit ordering relation such that
AAA < CCC? What does your current query look like?

/Lennart

[...]

Lennart,

Yes, I know the root node because the relationship table has a type
field for example, for AAA ---BBB record the relation type is AB and
I know the root node/record start with this type (AB). As I mentioned
earlier, the problem starts when I find the identical row in reverse
direction ( BBB ---AAA with relation type as BA ). Here is how my
query looks like.

WITH topdown_tree ( parent, child ) AS
(
select root.name, root.rel_name
from relationship AS root
where root.rel_typ = 'AB'

UNION ALL

select subroot.name, subroot.rel_name
from topdown_tree AS tt, relationship AS subroot
where tt.child = subroot.name
)
select parent, child
from topdown_tree;

Let me know if you need any other details. I really appreciate your
time and effort looking in to this and responding promptly.

Thanks !!!!!!!!!!

[Tonkuma]

------------------------------ Commands Entered
------------------------------
WITH
/* Test Data */
relationship(parent, child) AS (
SELECT CAST( parent AS VARCHAR(25) )
, CAST( child AS VARCHAR(25) )
FROM (VALUES
('AAA', 'BBB')
,('AAA', 'CCC')
,('AAA', 'DDD')
,('BBB', 'EEE')
,('BBB', 'FFF')
,('BBB', 'AAA')
,('CCC', 'GGG')
,('CCC', 'AAA')
,('DDD', 'HHH')
,('DDD', 'AAA')
,('EEE', 'BBB')
,('FFF', 'BBB')
,('GGG', 'CCC')
,('HHH', 'DDD')
) td(parent, child)
)
/* End of Test Data */
,topdown_tree(k, leaf, path) AS (
SELECT DISTINCT
1
, child
, CAST( parent || ', ' || child AS VARCHAR(30) )
FROM relationship
/*
Start from AAA ---BBB
*/
WHERE parent = 'AAA'
AND child = 'BBB'
/**/
UNION ALL
/**/
SELECT k + 1
, child
, path || ', ' || child
FROM topdown_tree AS tt
, relationship AS subroot
WHERE k < 1000000
AND tt.leaf = subroot.parent
AND LOCATE(subroot.child, tt.path) = 0
)
SELECT path AS "Starting from AAA ---BBB"
FROM topdown_tree
WHERE k
= (SELECT MAX(k)
FROM topdown_tree
)
;
------------------------------------------------------------------------------

Starting from AAA ---BBB
------------------------------
AAA, BBB, EEE
AAA, BBB, FFF

2 record(s) selected.

------------------------------ Commands Entered
------------------------------
WITH
/* Test Data */
relationship(parent, child) AS (
SELECT CAST( parent AS VARCHAR(25) )
, CAST( child AS VARCHAR(25) )
FROM (VALUES
('AAA', 'BBB')
,('AAA', 'CCC')
,('AAA', 'DDD')
,('BBB', 'EEE')
,('BBB', 'FFF')
,('BBB', 'AAA')
,('CCC', 'GGG')
,('CCC', 'AAA')
,('DDD', 'HHH')
,('DDD', 'AAA')
,('EEE', 'BBB')
,('FFF', 'BBB')
,('GGG', 'CCC')
,('HHH', 'DDD')
) td(parent, child)
)
/* End of Test Data */
,topdown_tree(k, leaf, path) AS (
SELECT DISTINCT
1
, child
, CAST( parent || ', ' || child AS VARCHAR(30) )
FROM relationship
/**/
UNION ALL
/**/
SELECT k + 1
, child
, path || ', ' || child
FROM topdown_tree AS tt
, relationship AS subroot
WHERE k < 1000000
AND tt.leaf = subroot.parent
AND LOCATE(subroot.child, tt.path) = 0
)
SELECT path AS "Longest pathes"
FROM topdown_tree
WHERE k
= (SELECT MAX(tm.k)
FROM topdown_tree tm
)
;
------------------------------------------------------------------------------

Longest pathes
------------------------------
EEE, BBB, AAA, CCC, GGG
EEE, BBB, AAA, DDD, HHH
FFF, BBB, AAA, CCC, GGG
FFF, BBB, AAA, DDD, HHH
GGG, CCC, AAA, BBB, EEE
GGG, CCC, AAA, BBB, FFF
GGG, CCC, AAA, DDD, HHH
HHH, DDD, AAA, BBB, EEE
HHH, DDD, AAA, BBB, FFF
HHH, DDD, AAA, CCC, GGG

10 record(s) selected.

[Tonkuma]

Modified slightly to meet your requirements.
------------------------------ Commands Entered
------------------------------
WITH
/* Test Data */
relationship(parent, child, rel_type) AS (
VALUES
('AAA', 'BBB', 'AB')
,('AAA', 'CCC', 'AC')
,('AAA', 'DDD', 'AD')
,('BBB', 'EEE', 'BE')
,('BBB', 'FFF', 'BF')
,('BBB', 'AAA', 'BA')
,('CCC', 'GGG', 'CG')
,('CCC', 'AAA', 'CA')
,('DDD', 'HHH', 'DH')
,('DDD', 'AAA', 'DA')
,('EEE', 'BBB', 'EB')
,('FFF', 'BBB', 'FB')
,('GGG', 'CCC', 'GC')
,('HHH', 'DDD', 'HD')
)
/* End of Test Data */
,topdown_tree(k, leaf, path) AS (
SELECT DISTINCT
1
, child
, CAST( parent || ' ---' || child AS VARCHAR(50) )
FROM relationship
/*
Start from AAA
*/
WHERE parent = 'AAA'
/**/
UNION ALL
/**/
SELECT k + 1
, child
, path || ' ---' || child
FROM topdown_tree AS tt
, relationship AS subroot
WHERE k < 1000000
AND tt.leaf = subroot.parent
AND LOCATE(subroot.child, tt.path) = 0
)
SELECT path AS "Start from AAA"
FROM topdown_tree
;
------------------------------------------------------------------------------

Start from AAA
--------------------------------------------------
AAA ---BBB
AAA ---CCC
AAA ---DDD
AAA ---BBB ---EEE
AAA ---BBB ---FFF
AAA ---CCC ---GGG
AAA ---DDD ---HHH

7 record(s) selected.

[Pivot_Tables]

On Aug 10, 9:58*pm, Tonkuma <[e-mail]:

Modified slightly to meet your requirements.
------------------------------ Commands Entered
------------------------------
WITH
/* Test Data */
*relationship(parent, child, rel_type) AS (
VALUES
* * * *('AAA', 'BBB', 'AB')
* * * ,('AAA', 'CCC', 'AC')
* * * ,('AAA', 'DDD', 'AD')
* * * ,('BBB', 'EEE', 'BE')
* * * ,('BBB', 'FFF', 'BF')
* * * ,('BBB', 'AAA', 'BA')
* * * ,('CCC', 'GGG', 'CG')
* * * ,('CCC', 'AAA', 'CA')
* * * ,('DDD', 'HHH', 'DH')
* * * ,('DDD', 'AAA', 'DA')
* * * ,('EEE', 'BBB', 'EB')
* * * ,('FFF', 'BBB', 'FB')
* * * ,('GGG', 'CCC', 'GC')
* * * ,('HHH', 'DDD', 'HD')
)
/* End of Test Data */
,topdown_tree(k, leaf, path) AS (
SELECT DISTINCT
* * * *1
* * *, child
* * *, CAST( parent || ' ---' || child AS VARCHAR(50) )
* FROM relationship
/*
Start from AAA
*/
*WHERE parent = 'AAA'
/**/
UNION ALL
/**/
SELECT k + 1
* * *, child
* * *, path || ' ---' || child
* FROM topdown_tree AS tt
* * *, relationship AS subroot
*WHERE k < 1000000
* *AND tt.leaf = subroot.parent
* *AND LOCATE(subroot.child, tt.path) = 0
)
SELECT path AS "Start from AAA"
* FROM topdown_tree
;
---------------------------------------------------------------------------*---

Start from AAA
--------------------------------------------------
AAA ---BBB
AAA ---CCC
AAA ---DDD
AAA ---BBB ---EEE
AAA ---BBB ---FFF
AAA ---CCC ---GGG
AAA ---DDD ---HHH

* 7 record(s) selected.

Thanks Tonkuma,

Just a quick question, what is the reason for putting k<1000000
criteria in the recursive query. If the Locate function avoids the
cycle/infinite loop, do you think we need to add the criteria
k<1000000 or not. The reason why I am asking that is because the data
I have is more than sample data I provided and it may go beyond
1000000 limit in the above query. Could you please clarify this.

As always thanks a lot for your time in looking into this.

Appreciated a lot!!!

[Tonkuma]

Just a quick question, what is the reason for putting k<1000000

criteria in the recursive query. If the Locate function avoids the
cycle/infinite loop, do you think we need to add the criteria
k<1000000 or not.

To prevent the following message.
SQL0347W The recursive common table expression
"DB2ADMIN.TOPDOWN_TREE" may contain an infinite loop. SQLSTATE=01605

The reason why I am asking that is because the data
I have is more than sample data I provided and it may go beyond
1000000 limit in the above query. Could you please clarify this.

I can't beleive that the level of your data go beyond 1000000, even if
number of your data would go beyond 1000000.