Recursive SQL Question on breaking the infinite loop.
Pivot_Tables
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
using (WITH UNION ALL vs. CONNECT BY)
Cheers
Serge
--
Serge Rielau
DB2 Solutions Development
IBM Toronto Lab
Lennart
> 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.
around and what does it mean if someone deletes the tupel (AAA,BBB)
but leaves the tuple (BBB,AAA)?
[...]
/Lennart
Pivot_Tables
> On Aug 9, 4:17 pm, Pivot_Tables <atitbpa...@gmail.com> wrote:
>
>
>
>
>
> > Hi,
>
>
> - 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
[...]
>
> 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
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 !!!!!!!!!!
Serge Rielau
For tree walks I'd prefer CONNECT BY since it comes with path, order and
cycle control.
--CELKO--
How about a whole book? TREES & HIERARCHIES IN SQL. Buy a copy; I
have a house payment coming up.
1) Columns are not fields; rows are not records; tables are not
files. This is a required rant of mine that you have to endure if you
post on any SQL Newsgroup.
One of the many ways they differ is that tables, rows and columns can
have constraints. Those cycles never should have been allowed in the
tree the first place
2) This is why I use the nested sets model instead of the adjacency
list mode and proprietary extensions. The cycle prevention and
single root constraints are easy to write with triggers, create
assertions, full Standard SQL CHECK() clauses or in WITH CHECK OPTIONS
in an updatable view.
Can you fix the design? First mop the floor, then fix the leak. When
the data is clean then move it to a Nested Sets model. It will take
about 1-2 days to make the change in the schema. You will need a VIEW
that converts the Nested Sets into a Adjacency List until you can do
some re-writes.
Depending what you are doing, you will find that you should get about
an order of magnitude improvement in performance in aggregations by
subtrees. While that is nice, you will also find that you finally
have data integrity and the answers are right! Wow!
Pivot_Tables
Serge,
Thanks for your reply, but could you let me know if this infinite loop/
cycle can be broken by using CTE and WITH Phrase. I am not sure
whether we will have the 9.5 in production before this hierarchical
project. I would appreciate if you could direct me on how this can be
achieved using CTE/WITH if that is possible. If it is possible, could
you pass some sample.
Lennart
In general it is a good idea to provide ddl for tables and insert
statements for sample data. Anyhow, since your data looks the way it
does you need to prevent to visit the same node twice. One way to do
this is top record which nodes you have already visited. Assuming your
table and data looks like:
[lelle@53dbd181 pivot_tables]$ cat data.ddl
create table relationship (
name char(3) not null,
child char(3) not null,
rel_typ char(2) not null,
primary key (name, child)
);
insert into relationship (name, child, rel_typ)
values
('XXX','AAA','AB'),
('AAA','BBB','XX'),
('AAA','CCC','XX'),
('AAA','DDD','XX'),
('BBB','EEE','XX'),
('BBB','FFF','XX'),
('BBB','AAA','XX'),
('CCC','GGG','XX'),
('CCC','AAA','XX'),
('DDD','HHH','XX'),
('DDD','AAA','XX'),
('EEE','BBB','XX'),
('FFF','BBB','XX'),
('GGG','CCC','XX'),
('HHH','DDD','XX');
A query like this will probably do:
WITH topdown_tree ( parent, child, path ) AS
(
select root.name, root.child,
',' || cast(root.name as varchar(1000))
from relationship AS root
where root.rel_typ = 'AB'
UNION ALL
select subroot.name, subroot.child,
rtrim(tt.path) || ',' || subroot.name
from topdown_tree AS tt, relationship AS subroot
where tt.child = subroot.name
and locate (',' || subroot.name, rtrim(tt.path)) = 0
)
select parent, child, substr(path,6)
from topdown_tree;
As mentioned before I think it is a bad idea to store the tree twice.
It adds nothing useful and gives you a whole lot of trouble. If
possible, redesign
/Lennart
> Thanks !!!!!!!!!!
Serge Rielau
counter to teh levels of recursion and break it of after a reasonable
amount: say 1000.
If you want to nip teh cycle in the proverbial butt things get a bit
more complex:
http://www.ibm.com/developerworks/db2/library/techarticle/dm-0510rielau/
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.
Pivot_Tables
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
Thanks Guys, Ok just to calrify my table structure and data and
the data I am trying to achieve, here they are.
Relationship Table
PARENT FIELD CHILD FIELD Rel Type
AAA BBB AB <--- AAA is the root node.
AAA CCC AC <--- AAA is the root node.
AAA DDD AD <--- AAA is the root node.
BBB EEE BE
BBB FFF BF
BBB AAA BA <--- This is the reverse row for
Bottom UP and I donot need this
in the output of the query.
CCC GGG CG
CCC AAA CA <--- This is the reverse row for
Bottom UP and I donot need this
in the output of the query.
DDD HHH DH
DDD AAA DA <--- This is the reverse row for
Bottom UP and I donot need this
in the output of the query.
EEE BBB EB <--- This is the reverse row for
Bottom UP and I donot need this
in the output of the query.
FFF BBB FB <--- This is the reverse row for
Bottom UP and I donot need this
in the output of the query.
GGG CCC GC <--- This is the reverse row for
Bottom UP and I donot need this
in the output of the query.
HHH DDD HD <--- This is the reverse row for
Bottom UP and I donot need this
in the output of the query.
Below is the result/output of SQL I am trying to achieve and that
generates the Top Down tree data rows. I am trying to achieve
following result.
PARENT FIELD CHILD FIELD Rel Type
AAA BBB AB <--- This is the root row.
AAA CCC AC <--- This is the also root row.
AAA DDD AD <--- This is the also root row.
BBB EEE BE
BBB FFF BF
CCC GGG CG
DDD HHH DH
7 record(s) selected.
So if I concanate/attach child data to previous parent data at
each pass, I should achieve the below result.
AAA ---> BBB ( This is result from the first select. )
AAA ---> CCC ( This is result from the first select. )
AAA ---> DDD ( This is result from the first select. )
AAA ---> BBB ---> EEE ( Recursion result )
AAA ---> BBB ---> FFF ( Recursion result )
AAA ---> CCC ---> GGG ( Recursion result )
AAA ---> DDD ---> HHH ( Recursion result )
Let me know if this clarifies what I am trying to ask here.
Again as always Thanks a lot!!!
Lennar/Tonkuma,
Could you send me the sample to achieve above data and
avioding the cycle/infinite loop. Also, just to let you
know I trying to get the data starting from my Root Node in
the tree which is AAA.
Sorry for not clarifying exactly my data and result
earlier.
Thanks a lot you guys for looking into this and replying
promptly.
Tonkuma
------------------------------ Commands Entered
------------------------------
WITH
/* Test Data */
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
FROM relationship
/*
Start from AAA
WHERE parent = 'AAA'
UNION ALL
/**/
SELECT k + 1
, child
FROM topdown_tree AS tt
, relationship AS subroot
WHERE k < 1000000
AND tt.leaf = subroot.parent
AND LOCATE(subroot.child, tt.path) = 0
)
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
>
> 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
> 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.
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.
--CELKO--
In the Nested sets model, you have one table of nodes and another
table for tree structure. That follows the rule of data modeling that
we don't put relationships and entities in the same table.
What you can do is create a structure table for each different
relationship type you have and let them reference the same nodes
table. I did this years ago for a show company. They had one
hierarchy for manufacturing reports that was based on materials used
(lather or canvas, stitched or glued, etc.) which was very constant.
Another set of reports was based marketing categories (children's
shoes, women's sport, etc.) and it was changing with the fads.
My favorite example was steel-toed work boots. In the manufacturing
hierarchy, they were one category. But in marketing shoe size was
important. Only two kinds of customers bought these boots -- Goth
girls (small feet, fashion stores) and construction workers (big feet,
work shoe stores).
Splitting the structure from the nodes made queries so much easier.
Pivot_Tables
Thanks Guys for your prompt responses and looking into the question I
asked. I really appreciate your time and effort in sending me the
directions.
Thanks Tonkuma. The sample you sent me helped me alot.
The Application was written and customized with these cyclic data and
the design is not changing so I need to remove the cyclic dependency.
Also, just to let you guys know, DB2 v 9.5 will have the support for
Connect by just like ORACLE. But again the version we are using is not
changing it to 9.5 soon, so i have to use the WITH command and
recursive views.
Thanks all for your support.
Pivot_Tables
>
> - Show quoted text -
Hi Guys,
I got into another issue with this. I want to know if I can break the
repeatation of the same parent child nodes in some other path. Here is
one example of the data I am talking about.
AAA --> BBB --> FFF --> GGG --> HHH
Now the second path refers to one of the node in the above path and it
is currently trying to recurse in the same sub path that was part of
some other path. see the example below.
AAA --> CCC --> DDD --> III --> FFF --> GGG --> HHH
Now, if you notice the III node was refering to FFF and because FFF
has child nodes it copied the same sub tree again. I donot want to
repeat the ( Parent --> Child ) pair if it was already found somewhere
else in some other path.
I tried using the DISTINCT of the Parent --> Child, but its taking too
long for query to return the data. Also, I kept the Locate function so
that it does not go in infinite loop.
Is there a efficient way of retrieving the data without using
DISTINCT. I want to know if I could use the relationship table created
so far as a subquery to not to process the duplicate sub paths.
Could you please guide me in the right direction.
Thanks a lot!!!!!