locked
How to detecting/prevent circular relationships within tabels. RRS feed

  • Question

  • Hello

    I have a table, Category, with among others, a CategoryID and a ParentID column. This allows me to support subcategories.

    I've created a foreign key relationship  from  Category.ParentID to Category.CategoryID.

    What I want to prevent is a category becoming a parent for another category that it is a child of - for example:

        Case 1: CatA -> CatB -> CatA
        Case 2: CatA -> CatB -> CatC -> CatA.


    However, my skills in writing stored procedures are somewhat limited, so I need help writing an "UpdateCategory" stored procedure, that will check for circular nested categories.

    Thanks, Egil.
    Sunday, April 15, 2007 3:39 PM

Answers

  • Here is a possible solution (assuming you are running SQL Server 2005) using a CTE.

    drop table relationshipTest
    go
    create table relationshipTest
    (
        rowId int primary key,
        parentRowId int null
    )
    go
    create trigger relationshipTest_insertUpdate
    on relationshipTest
    after insert,update
    as
    set nocount on
    declare @errorTable table (trouble bit)

            ;WITH relationshipTestCTE(rowId, parentRowId, level,originalRowId)
            AS
            (
                 SELECT rowId, parentRowId, 1 as level, rowId as originalRowId
                 FROM   inserted
                        

                 UNION ALL

                 --gets other levels of tree.  If there is a circular reference, you will always
                 --loop back to yourself.
                 SELECT relationshipTest.rowId, relationshipTest.parentRowId,
                                level + 1 as level, originalRowId
                 FROM   relationshipTest
                            JOIN relationshipTestCTE
                                    on relationshipTest.parentRowId = relationshipTestCTE.rowId
                 where  level <= 100 --stop at max recursion, change max
                                                --recursion to allow deeper tree
            )
            insert into @errorTable
            select  top 1 1
            from    relationshipTestCTE as relationshipTestCTE
                      join relationshipTestCTE  as validate
                            on relationshipTestCTE.level = 1
                               --here we are looking for other rows in the hierarchy, other than the first
                               and validate.level > 1
                               --the same rows shouldn't show up in another level of the tree
                               and validate.rowId  = relationshipTestCTE.originalRowId
                                   --correlates groups, in case of >1 row
                               and validate.originalRowId  = relationshipTestCTE.originalRowId

    if exists(select * from @errorTable)
     begin
        raiserror('Operation would cause illegal circular reference in relationshipTest',16,1)
        rollback transaction
        return
     end
    go

    --Some testing code

    set nocount on
    insert into relationshipTest
    select 1,null
    union all
    select 2,null
    union all
    select 3,2
    union all
    select 4,3
    union all
    select 5,1
    go
    select 'won''t work, would cause 1,8 and 8,1'
    update relationshipTest
    set    parentRowId = 5
    where  rowId = 1

    go
    insert into relationshipTest
    select 6,NULL
    union all
    select 7,6
    union all
    select 8,7
    union all
    select 9,8
    go
    select 'won''t work, would cause 6,9; 7,6; 8,7; 9;8 loop through 9'
    update relationshipTest
    set    parentRowId = 9
    where  rowId = 6
    go


    insert into relationshipTest
    select 16,NULL
    union all
    select 17,NULL
    union all
    select 18,17
    union all
    select 19,18
    go

    select 'will work, so we have 16,19; 17,NULL; 18,17; 19,18'
    update relationshipTest
    set    parentRowId = 19
    where  rowId = 16


    select 'won''t work, would close the loop through 19'
    update relationshipTest
    set    parentRowId = 16
    where  rowId = 17
    go


    select 'won''t work, trying to insert an entire loop in the one statement'
    insert into relationshipTest
    select 21,20
    union all
    select 22,21
    union all
    select 20,22


    Sunday, April 15, 2007 9:42 PM
  • Hi Louis,

    I had the same need to detect any circular reference in one my development projects. I came across your solution--it is excellent by the way--and used it to form the basis of the solution below.

    I found the following solution below to run more efficiently, as it resulted in significantly lower logical reads during query-DML testing. Another advantage is that you don't have to manually set the max depth of the tree, and also don't have to be running SQL 2005.

    I hope this helps somebody.

    Code Below
    -------------------------------------------------------------------------
    drop table rTest
    go
    create table rTest
    (
    rowId int primary key,
    parentRowId int null
    )
    go
    create trigger rTest_insertUpdate
    on rTest
    after insert,update
    as
    set nocount on

    declare @cTable table
    (
    rowId int not null,
    parentRowId int null,
    level int not null,
    originalRowId int not null
    )

    declare @level int
    set @level = 1

    declare @rows_affected int
    set @rows_affected = 1

    --insert "inserted" to serve as root parent
    insert into @cTable
    select rowId, parentRowId, 1, rowId from inserted

    --loop
    while @rows_affected > 0
    begin
    set @level = @level + 1

    --insert immediate children
    insert into @cTable
    select r.rowId, r.parentRowId, @level, originalRowId
    from
    rTest r
    inner join @cTable c
    on r.parentRowId = c.RowId
    and c.level = @level - 1

    set @rows_affected = @@rowcount

    --Check for circular reference
    if exists
    (
    select *
    from
    @cTable base
    inner join @cTable validate
    on base.level = 1
    and validate.level > 1
    and validate.originalRowId = base.originalRowId
    and validate.rowId = base.originalRowId
    )
    begin
    declare @error_message varchar(200)
    set @error_message = 'Operation would cause illegal circular reference in rTest, level = ' + cast(@level as varchar(30))
    raiserror(@error_message,16,1)
    rollback transaction
    return
    end
    end

    GO
    Friday, April 20, 2007 2:49 AM

All replies

  • I'm not sure how that could happen. Follow my thoughs on the issue.

     

    With the single table schema you presented, each record has one, and only one parent. I don't see a way to create a 'circular reference'. For that to happen, it seems like each parent would have to also refer back to its children. (However, it's Sunday, and perhaps my 'critical' thinking cap is still feeling the effects of a late Saturday evening...)

    Code Snippet


    Categoryid ParentID
    ---------- --------
    1          NULL      --No Parent
    2          NULL      --No Parent
    3          1         --Parent=CategoryID: 1
    4          2         --Parent=CategoryID: 2
    5          3         --Parent=CategoryID: 3 -> Parent=CategoryID: 1

     

    If I'm missing something obvious here, let me know.
    Sunday, April 15, 2007 7:28 PM
  • Hi Arnie

    Thanks for replying.I'm probably not using the right word - circular relationships - to describe my problem.

    Let me take your example and show you what my problem is.
    In this example, Category 1 has Category 2 as its parent, and Category 2 has Category 3 as its parent, and Category 3 has Category 1 as its parent - which doesn't make sense, since Category 3 should be ahead of (imagine a linked list) Category 1, not behind it, since Category 1 has Category 2 as it's parent, and Category 2 has Category 3 as its (haha thats one messed up sentence Smile)

    Code Snippet

    Categoryid ParentID
    ---------- --------
    1          2         --Parent=CategoryID: 2
    2          3         --Parent=CategoryID: 3 -> Parent=CategoryID: 1
    3          1         --Parent=CategoryID: 1 -> Parent=CategoryID: 2 -> Parent=CategoryID: 3


    This is another one case - where only two categories have each other as parents (which doesn't make sense obviously).

    Code Snippet

    Categoryid ParentID
    ---------- --------
    1          2         --Parent=CategoryID: 2
    2          1         --Parent=CategoryID: 1


    Regards, Egil.
    Sunday, April 15, 2007 7:48 PM
  • Stay with me a little further.

     

    In my example, I assume that there is a definitive 'root' level. The Parent #1, the one brought forth from immaculate conception. The one that has no parent. I indicated that Categories 1 and 2 had NULL for ParentID.

     

    In your example, you indicate that Parent #1 can be brought forth from some future progeny.

     

    That just can't be. Any design that allows that is 'broken' in my opinion.

     

    Which came first, the chicken or the egg? You have to make a stand for the sake of your model.

    Sunday, April 15, 2007 8:50 PM
  • I agree, I cant assign a parent to the first ever created category, since there are no other categories in existence.

    However, suppose I create a bunch of categories, and decide to update their preferences, and set their parents property to one of the other categories (one category adopting another so to speak Smile), I could run in to that issue I presented above.
    Sunday, April 15, 2007 9:17 PM
  • Here is a possible solution (assuming you are running SQL Server 2005) using a CTE.

    drop table relationshipTest
    go
    create table relationshipTest
    (
        rowId int primary key,
        parentRowId int null
    )
    go
    create trigger relationshipTest_insertUpdate
    on relationshipTest
    after insert,update
    as
    set nocount on
    declare @errorTable table (trouble bit)

            ;WITH relationshipTestCTE(rowId, parentRowId, level,originalRowId)
            AS
            (
                 SELECT rowId, parentRowId, 1 as level, rowId as originalRowId
                 FROM   inserted
                        

                 UNION ALL

                 --gets other levels of tree.  If there is a circular reference, you will always
                 --loop back to yourself.
                 SELECT relationshipTest.rowId, relationshipTest.parentRowId,
                                level + 1 as level, originalRowId
                 FROM   relationshipTest
                            JOIN relationshipTestCTE
                                    on relationshipTest.parentRowId = relationshipTestCTE.rowId
                 where  level <= 100 --stop at max recursion, change max
                                                --recursion to allow deeper tree
            )
            insert into @errorTable
            select  top 1 1
            from    relationshipTestCTE as relationshipTestCTE
                      join relationshipTestCTE  as validate
                            on relationshipTestCTE.level = 1
                               --here we are looking for other rows in the hierarchy, other than the first
                               and validate.level > 1
                               --the same rows shouldn't show up in another level of the tree
                               and validate.rowId  = relationshipTestCTE.originalRowId
                                   --correlates groups, in case of >1 row
                               and validate.originalRowId  = relationshipTestCTE.originalRowId

    if exists(select * from @errorTable)
     begin
        raiserror('Operation would cause illegal circular reference in relationshipTest',16,1)
        rollback transaction
        return
     end
    go

    --Some testing code

    set nocount on
    insert into relationshipTest
    select 1,null
    union all
    select 2,null
    union all
    select 3,2
    union all
    select 4,3
    union all
    select 5,1
    go
    select 'won''t work, would cause 1,8 and 8,1'
    update relationshipTest
    set    parentRowId = 5
    where  rowId = 1

    go
    insert into relationshipTest
    select 6,NULL
    union all
    select 7,6
    union all
    select 8,7
    union all
    select 9,8
    go
    select 'won''t work, would cause 6,9; 7,6; 8,7; 9;8 loop through 9'
    update relationshipTest
    set    parentRowId = 9
    where  rowId = 6
    go


    insert into relationshipTest
    select 16,NULL
    union all
    select 17,NULL
    union all
    select 18,17
    union all
    select 19,18
    go

    select 'will work, so we have 16,19; 17,NULL; 18,17; 19,18'
    update relationshipTest
    set    parentRowId = 19
    where  rowId = 16


    select 'won''t work, would close the loop through 19'
    update relationshipTest
    set    parentRowId = 16
    where  rowId = 17
    go


    select 'won''t work, trying to insert an entire loop in the one statement'
    insert into relationshipTest
    select 21,20
    union all
    select 22,21
    union all
    select 20,22


    Sunday, April 15, 2007 9:42 PM
  • Hi Louis

    Wow, thanks. A few questions:

    I'm unsure if CTE is enabled on the server where my database is being hosted, but I guess I will have to test and see what happens Smile

    I see a lot of SQL that I'm unfamiliar with. I do think I get what's going on (you are recursively building a temporary table, that will hold any circular relationships if any exists), so I won't ask you to explain the code (all though that would be really cool), since it would probably be a few pages of  text Wink

    Another thing. Is my database design even good? It seems like my problem is a somewhat common scenario. Let me ask another way, would you (or anybody else reading this discussion) implement it like I have and then use your trigger solution to keep data integrity?

    Anyways, thanks for the help, regards, Egil.
    Sunday, April 15, 2007 10:14 PM
  • It is a typical scenario, and checking for circular references it pretty typical.  The next time I build a recursive relationship, I will probably put this algorithm to use, as it will work, and should work very fast since it only starts with the rows that were inserted, and works from there.
    Sunday, April 15, 2007 10:45 PM
  • Ok. Thanks a lot, Egil.
    Sunday, April 15, 2007 10:51 PM
  • Very nice solution Louis,

     

    I've spent quite awhile trying work out a CTE method of doing this -but I didn't consider the temp table. -EXCELLENT.

     

    -Arnie

     

    --A day without learning is a day wasted.

    Sunday, April 15, 2007 11:42 PM
  • Hi Louis,

    I had the same need to detect any circular reference in one my development projects. I came across your solution--it is excellent by the way--and used it to form the basis of the solution below.

    I found the following solution below to run more efficiently, as it resulted in significantly lower logical reads during query-DML testing. Another advantage is that you don't have to manually set the max depth of the tree, and also don't have to be running SQL 2005.

    I hope this helps somebody.

    Code Below
    -------------------------------------------------------------------------
    drop table rTest
    go
    create table rTest
    (
    rowId int primary key,
    parentRowId int null
    )
    go
    create trigger rTest_insertUpdate
    on rTest
    after insert,update
    as
    set nocount on

    declare @cTable table
    (
    rowId int not null,
    parentRowId int null,
    level int not null,
    originalRowId int not null
    )

    declare @level int
    set @level = 1

    declare @rows_affected int
    set @rows_affected = 1

    --insert "inserted" to serve as root parent
    insert into @cTable
    select rowId, parentRowId, 1, rowId from inserted

    --loop
    while @rows_affected > 0
    begin
    set @level = @level + 1

    --insert immediate children
    insert into @cTable
    select r.rowId, r.parentRowId, @level, originalRowId
    from
    rTest r
    inner join @cTable c
    on r.parentRowId = c.RowId
    and c.level = @level - 1

    set @rows_affected = @@rowcount

    --Check for circular reference
    if exists
    (
    select *
    from
    @cTable base
    inner join @cTable validate
    on base.level = 1
    and validate.level > 1
    and validate.originalRowId = base.originalRowId
    and validate.rowId = base.originalRowId
    )
    begin
    declare @error_message varchar(200)
    set @error_message = 'Operation would cause illegal circular reference in rTest, level = ' + cast(@level as varchar(30))
    raiserror(@error_message,16,1)
    rollback transaction
    return
    end
    end

    GO
    Friday, April 20, 2007 2:49 AM