Preventing infinite recursion

[tshad]

I have a table that I am using a CTE to get the parent/child records a
category. The problem is that a user could put in a record that would cause
infinite recursion and I am trying to find out if there is a good way to
prevent that?

For example:

Parent Child
5 29
29 5

Using a cte to do recursion I would get a recursion error.

If you start at the 1st record, you would get the parent as 5 and then look
for the record that that had the parent = 29 (the child) which would get
you the 2nd row. You would then look for the record that had the parent - 5
(the child) and you would then get the 1st record and this would happen over
and over.

Two questions:

1) Is there way to get the CTE to tell you which record causes the
recursion???

2) Is there an easy way to prevent a user from putting in a record where
there was a record in the database with with the Parent = Childand the Child
= Parent? Some type of constraint. I know this can be done
programmatically but I want to prevent someone from accidently adding a
record manually that would cause the problem.

Thanks,

Tom

[Philipp Post]

I guess best would be to clean up the data so there are no cycles
anymore.

Otherwise there is OPTION (MAXRECURSION n) to tell the CTE to quit
after n recursions.

brgds

Philipp Post

[Tom]

This is a non trivial problem. A long time ago when I worked on IBM's
DL/I there was a product called IBM System/370 Low-Level Code
Continuity Check documented in SH20-9046-3. A few years ago I was able
to order this document and implemented it with SQL, DL/I is
hierarchical not relational. My solution uses two tables instead of a
self referencing table. For updates to large structures it takes quite
a bit of resources. I have used it several times and have a generic
version I would be happy to share with you if you are interested.
tom.g...@charter.net

[--CELKO--]

[tshad]

I understand both of those.

And the data is clean (at the moment). I am trying to make sure that no one
can accidently add a new record manually that would cause the problem.

I have an AddCategory function that checks to see that the reverse record is
not there before adding in the record - but that doesn't prevent someone
from adding the record manually incorrectly. You then wouldn't see the
problem until later. Then it would be more difficult to find.

In your maxrecursion, it doesn't tell you what records cause the recursion
problem.

Thanks,

Tom

"Philipp Post" <post.p...@googlemail.com> wrote in message
news:2f5171e5-3289-4740...@y11g2000yqm.googlegroups.com...

[--CELKO--]

>> I have a table that I am using a CTE to get the parent/child records [sic:rows] a category.  The problem is that a user could put in a record [sic:row] that would cause infinite recursion and I am trying to find out if there is a good way to prevent that? <<

No. This is one of the problems with the Adjacency list model. You
wind up using procedural code to follow paths and check for cycles.
Oh, and look for orphans; those are subtrees that have no path back to
the root.

This is one of many reasons I tell people to use Nested Sets, where it
is easy to prevent cycles and orphans with declarative code.

As a minimum, you should add a CHECK (parent_node <> child_node) to
the DDL. As quick check, you can use the formula (number of edges)+1 =
(number of nodes). If the graph is a tree then this is true but the
converse does not hold.

[tshad]

Sure.

But my problem is not how it works (as it works fine) my problem is in using
some type of constraint that would prevent a bad record from entering the
table.

I could use a trigger, I suppose to do the check there.

Thanks,

Tom

[Erland Sommarskog]

tshad (t...@dslextreme.com) writes:
> 1) Is there way to get the CTE to tell you which record causes the
> recursion???

No.

> 2) Is there an easy way to prevent a user from putting in a record where
> there was a record in the database with with the Parent = Childand the
> Child = Parent? Some type of constraint. I know this can be done
> programmatically but I want to prevent someone from accidently adding a
> record manually that would cause the problem.

You would need a trigger. A brutal way would be to run a query for the
inserted rows to get their parents, and one to get their children. Then
use BEGIN TRY to trap the MAXRECURSION error to replace it with a more
meaningful message.

Another idea is to store a materialsed path of the ID, and then
compare aginst this before you store. You can't store 5 as a child
to 4, if 4 has 5 in its path.

Adam Machanics "Expert SQL 2005 Development" on Apress has a good
chapter on hierarchical structures, and he covers both materialised
path and nested sets.

--
Erland Sommarskog, SQL Server MVP, esq...@sommarskog.se

Links for SQL Server Books Online:
SQL 2008: http://msdn.microsoft.com/en-us/sqlserver/cc514207.aspx
SQL 2005: http://msdn.microsoft.com/en-us/sqlserver/bb895970.aspx
SQL 2000: http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx

[tshad]

Erland Sommarskog wrote:
> tshad (t...@dslextreme.com) writes:
>> 1) Is there way to get the CTE to tell you which record causes the
>> recursion???
>
> No.
>

Then if I had the following table:

CREATE TABLE [dbo].[TestCat](
[TestCatID] [int] NOT NULL,
[CatID] [int] NOT NULL,
[SubCatID] [int] NOT NULL,
[Required] [bit] NOT NULL
) ON [PRIMARY]

INSERT testcat(TestCatID,CatID,SubCatID,Required)
VALUES (8,15,29,1)
INSERT testcat(TestCatID,CatID,SubCatID,Required)
VALUES (11,29,25,1)
INSERT testcat(TestCatID,CatID,SubCatID,Required)
VALUES (16,15,30,1)
INSERT testcat(TestCatID,CatID,SubCatID,Required)
VALUES (17,25,80,1)
INSERT testcat(TestCatID,CatID,SubCatID,Required)
VALUES (18,80,20,1)
INSERT testcat(TestCatID,CatID,SubCatID,Required)
VALUES (21,30,10,1)
INSERT testcat(TestCatID,CatID,SubCatID,Required)
VALUES (23,20,80,1)

The rows that cause the infinite recursion are TestCatID = 18 and 23. They
have the Cat and SubCat reversed.

How would I do a select statement that would return any rows that have this?

That way, if someone does accidently put a bad record in, I can quickly find
them.

Thanks,

Tom

[Erland Sommarskog]

tshad (t...@dslextreme.com) writes:
> The rows that cause the infinite recursion are TestCatID = 18 and 23. They
> have the Cat and SubCat reversed.
>
> How would I do a select statement that would return any rows that have
> this?

This query works for your example, but it requires further testing.
The idea is that we build a materialised path, and if we come to an ID
that already is in the path, we are going around in circles. We still
recurse one level beyond that, to be able to pick all data about the
incorrect relation. Whence the condition on CTE.stillgood = 0.

The CTE works from bottom to top; normally you traverse hierarchies from
top to bottom. But I could see no top nodes in the example, and if we
are validating a tree for correctness, it may be incorrect to assume that
there is one at all.

[--CELKO--]

>> Then if I had the following table: <<

I know this is a skeleton, but could you learn ISO-11179 rules for
data elements? An attribute can be a category or an identifier, but
never both. This is fundamental.

CREATE TABLE FoobarTestCategories
(test_cat INTEGER NOT NULL,
sub_test_cat INTEGER NOT NULL,
sub2_test_cat INTEGER NOT NULL,
PRIMARY KEY (test_cat, sub_test_cat, sub2_test_cat),
required_flg BIT DEFAULT 0 NOT NULL);

The Standard syntax looks like this; there is no need to do all this
extra typing to speak dialect.

INSERT INTO FoobarTestCategories
VALUES (8, 15, 29, 1),
(11, 29, 25, 1),
(16, 15, 30, 1),
(17, 25, 80, 1),
(18, 80, 20, 1),
(21, 30, 10, 1),
(23, 20, 80, 1);

>> The rows that cause the infinite recursion are test_cat IN (18, 23). They have the sub_cat and sub2_cat reversed. <<

The problem is the design. When you have a fixed depth hierarchy, you
should learn from Melville Dewey, as in the Dewey Decimal
Classification in the library. Put the category system (or is it a
classification? Do you know the differences?)into one encoding that
has a fixed format that can be checked with a regular expression.

Maybe something like this?

CREATE TABLE FoobarTestCategories
(foobar_test_category CHAR() NOT NULL PRIMARY KEY
CHECK (foobar_test_category LIKE '[0-9][0-9]-[0-9][0-9]-[0-9]
[0-9]'),
foobar_test_description VARCHAR(100) NOT NULL);

Now all your bad design crap problems are gone. Please buy one of my
books and learn the basics. You keep postign things that all you want
is some stinking kludge to get over your unwillingness to do it
right.

[Erland Sommarskog]

--CELKO-- (jcel...@earthlink.net) writes:
> The Standard syntax looks like this; there is no need to do all this
> extra typing to speak dialect.

For crying out loud! What Tom had was perfectly ANSI-compliant. It
is also compliant with SQL 2005. The syntax you suggest works only
with SQL 2008.

(And by chance I happened to visit an Oracle newsgroup where someone
from the DB2 world had posted a question. People were puzzled by his
INSERT statements, which used row constructors, and through he was on
MySQL!)

> The problem is the design. When you have a fixed depth hierarchy, you
> should learn from Melville Dewey, as in the Dewey Decimal
> Classification in the library. Put the category system (or is it a
> classification? Do you know the differences?)into one encoding that
> has a fixed format that can be checked with a regular expression.
>
> Maybe something like this?
>
> CREATE TABLE FoobarTestCategories
> (foobar_test_category CHAR() NOT NULL PRIMARY KEY
> CHECK (foobar_test_category LIKE '[0-9][0-9]-[0-9][0-9]-[0-9]
> [0-9]'),
> foobar_test_description VARCHAR(100) NOT NULL);
>
> Now all your bad design crap problems are gone. Please buy one of my
> books and learn the basics. You keep postign things that all you want
> is some stinking kludge to get over your unwillingness to do it
> right.

What kind of meaningless crap is this? char() is not a data type in
SQL Server. (It may be in your wet dreams, but this is an SQL Server
forum.)

Apart from that, the above seems to be fixed depth, or can you care to
explain how this is to be used.

And why anyone would buy any of your books is beyond me - your behaviour
in this newsgroup is definitly not aimed to boost your sales.

[Tony Rogerson]

> CREATE TABLE FoobarTestCategories
> (test_cat INTEGER NOT NULL,
> sub_test_cat INTEGER NOT NULL,
> sub2_test_cat INTEGER NOT NULL,
> PRIMARY KEY (test_cat, sub_test_cat, sub2_test_cat),
> required_flg BIT DEFAULT 0 NOT NULL);

Why are you breaking 1NF, sub_test_cat and sub2_test_cat are obviously a
repeating group.

That schema also offers no resemblance to the original posters schema.

> INSERT INTO FoobarTestCategories
> VALUES (8, 15, 29, 1),

Why are you not naming columns on the INSERT? This is extremely bad practice
even in a development context.

> Now all your bad design crap problems are gone. Please buy one of my

Lol, no - you've introduced a load of bad design crap problems!

> Please buy one of my
> books and learn the basics. You keep postign things that all you want
> is some stinking kludge to get over your unwillingness to do it
> right.
>

Buy one of your books? Do me a favor, with advice like this and your past
advice given on here, your attitude - don't you think that offers a reason
your book sales have fallen off a cliff!

For the love of god take your tired old brain off to the knackers yard
before you kill somebody with your ailing bad advice!

--ROGGIE--

[Snooperman]

This is a kludge and is slow and difficult to maintain, but it works: use a
check constraint which calls a function to check for circular chains (SQL
Server 2005 and up) - this is a copy of one I used, heavily edited for
security:

CREATE FUNCTION [dbo].[table1_CheckFunction] ()
RETURNS bit
AS
/******************************************************************************/
/*
*/
/* Author. Snooperman. Date written. 20100428.
*/
/*
*/
/* This function returns 1 if it finds a circular chain in table
*/
/* [dbo].[table1], otherwise 0. It is intended for use in a check
*/
/* constraint on that table to ensure that no circular chains are
*/
/* created.
*/
/* To use it, add this constraint to table [dbo].[table1]:
*/
/* ALTER TABLE [dbo].[table1]
*/
/* ADD CONSTRAINT [CK_table1] CHECK
*/
/* ([dbo].[table1_CheckFunction]()=(0))
*/
/*
*/
/* WARNING: BECAUSE THIS FUNCTION IS INTENDED FOR USE WITHIN
*/
/* CONSTRAINT [CK_table1] ON TABLE [dbo].[table1], THERE COULD BE
*/
/* PROBLEMS MODIFYING IT. DROP THE CONSTRAINT, MODIFY THE FUNCTION,
*/
/* THEN REINSTATE THE CONSTRAINT.
*/
/*
*/
/* Tables: [dbo].[table1] (read-only).
*/
/*
*/
/******************************************************************************/
BEGIN
DECLARE @counter int;
WITH [localCTE] ([startofchain], [col1])
AS (SELECT [col1], [col1]
FROM [dbo].[table1]
WHERE ([Parent] IS NULL)
UNION ALL
SELECT c.[startofchain], t.[col1]
FROM [dbo].[table1] t
INNER JOIN [localCTE] c
ON (t.[Parent] = c.[col1]))
SELECT @counter = COUNT(*) FROM [localCTE];
RETURN CASE WHEN ((SELECT COUNT(*) FROM [dbo].[table1]) = @counter)
THEN 0 ELSE 1 END;
END;

--
Snooperman

"tshad" wrote:

> .
>

[tshad]

Actually, the values that are reversed are 80, 20 - The last line is 20,
80.

To see it, you can run:

************************

WITH PrrCTE(CatID,SubCatID, Level, baseCatID, basePreReq )
AS
(
-- Anchor Member
SELECT CatID, SubCatID, 0, SubCatID as baseCatID, CatID as basePreReq
FROM TestCat
WHERE CatID = 15 -- Start original document

UNION ALL

-- Recursive Member
SELECT
e.CatID, e.SubCatID, m.Level+1, m.baseCatID, m.basePreReq
FROM
TestCat AS e
INNER JOIN PrrCTE m ON e.CatID = m.SubCatID
)
-- Using the CTE
SELECT CatID, SubCatID,Level, baseCatID, basePreReq
FROM PrrCTE
Order by baseCatID,Level
*************************************
This will give you an infinite recursion. If you change the 80 to an 81 in
the last row, it will work fine.

Tom

"Erland Sommarskog" <esq...@sommarskog.se> wrote in message
news:Xns9DE27AFCA...@127.0.0.1...

[Erland Sommarskog]

tshad (t...@dslextreme.com) writes:
> Actually, the values that are reversed are 80, 20 - The last line is 20,
> 80.

Sorry, my previous post missed a very important thing - the query!
Better paste it first thing this time:

WITH CTE AS (
SELECT CatID, SubCatID, path = convert(varchar(8000), str(CatID, 4)),
stillgood = 1
FROM testcat
WHERE CatID = 15
UNION ALL
SELECT T.CatID, T.SubCatID, C.path + str(T.CatID, 4),
stillgood =
CASE WHEN C.path LIKE '%' + ltrim(str(T.SubCatID)) + '%'

THEN 0
ELSE 1
END

FROM testcat T
JOIN CTE C ON C.SubCatID = T.CatID
WHERE C.stillgood = 1
)
SELECT *
FROM CTE
WHERE stillgood = 0

I repeat the first paragraph for convenience:

This query works for your example, but it requires further testing.
The idea is that we build a materialised path, and if we come to an ID
that already is in the path, we are going around in circles. We still
recurse one level beyond that, to be able to pick all data about the
incorrect relation. Whence the condition on CTE.stillgood = 0.

I don't repeat the second parapgrah, because I wrote the query
differently this time.