1

I am trying to model a simple tree structure in my database. I have a TreeNode table with the following columns:

Id (int), Name (string), ParentId (int, nullable), ChildPosition (int)

ParentId is a FK to a parent TreeNode, and ChildPosition is the TreeNode's position relative to its siblings:

- Parent
-- Child 1 (ChildPosition = 0)
-- Child 2 (ChildPosition = 1)
-- Child 3 (ChildPosition = 2)

I'd like to place a composite unique constraint/index on the Parent + ChildPosition columns, because I don't want any two TreeNodes to have the same ChildPosition under a particular Parent. Simple, right?

But I have a problem. In my UI, users can drag 'n' drop children into different positions, effectively changing their ordering (ChildPosition) on-the-fly. This can affect multiple TreeNodes. For example, if I drag Child 3 to be before Child 1, the ChildPosition of all three nodes should be updated:

- Parent
-- Child 3 (ChildPosition = 0)
-- Child 1 (ChildPosition = 1)
-- Child 2 (ChildPosition = 2)

However, my unique constraint doesn't seem to like this. It generates the following error:

Cannot insert duplicate key row in object 'dbo.TreeNode' with unique index 'IX_TreeNode'.

I think it's because I am trying to swap the ChildPosition of multiple records at the same time in one transaction, and the unique constraint doesn't recognize it. So how do I solve this?

I am doing this via Linq to Sql, if that is of any relevance.

EDIT: I should also mention that I've got a check constraint on the ChildPosition column to prevent negative numbers, and I'd like to keep it if possible. :)

XåpplI'-I0llwlg'I -
  • 21,649
  • 28
  • 102
  • 151
  • Update record A to an unused ID. Update record B to record A's old ID. Update record A to record B's old ID. – Andomar Jan 06 '14 at 14:53
  • 1
    Do not swap. Renumber the ChildPositions after every change, and only save after you've renumbered all of them. – Roy Dictus Jan 06 '14 at 14:53
  • @RoyDictus: SQL Server will throw an error before you "save" (commit) – Andomar Jan 06 '14 at 14:56
  • You could use a temp table. When the user submits the data, populate the temp table with what was submitted. You could try to update from the temp table, but I'm not sure that would succeed. But you could delete and replace the records. – Dan Bracuk Jan 06 '14 at 15:05
  • @RoyDictus The only thing I don't like about that is that, over time, the ChildPositions would increase ever higher. In theory, they could exceed the maximum int value if enough drag 'n' drops occur. – XåpplI'-I0llwlg'I - Jan 06 '14 at 15:09
  • 1
    I am going to be in the minority here, but I saw drop the SQL constraint and enforce it in code. Presuming of course that there is only one edit UI. – Brian P Jan 06 '14 at 15:10
  • Second @Brian P's comment. You're already handling the renumbering in code and the constraint is just getting in your way. – simon at rcl Jan 06 '14 at 15:29
  • Assuming that you are inserting / updating the records in the database, if you don't want to change any constraints, then delete the changed records and insert them, that should resolve your current issue. – Consult Yarla Jan 06 '14 at 15:31
  • Moving *one* child to a different position and renumbering required other rows is quite easy - but do you need to support moving multiple children at the same time? – Damien_The_Unbeliever Jan 06 '14 at 15:38
  • Care to register on [tex.se] where you have an [old unconnected question](http://tex.stackexchange.com/q/36500/5764)? – Werner Mar 24 '14 at 18:39

1 Answers1

0

So long as you only need to move one node at a time, something like this should work:

declare @ParentID int
declare @FromPosition int
declare @ToPosition int
select @ParentID = 1, @FromPosition = 2, @ToPosition = 0

update TreeNode set ChildPosition =
    CASE WHEN ChildPosition = @FromPosition THEN @ToPosition
         WHEN @FromPosition > @ToPosition THEN ChildPosition + 1
         ELSE ChildPosition -1
    END
where
    ParentID = @ParentID and
    (
        ChildPosition between @FromPosition and @ToPosition or
        ChildPosition between @ToPosition and @FromPosition
    )

This works because a single UPDATE statement can affect multiple rows, and the UNIQUE constraint is only checked on the eventual result of that statement.

This bit looks a little funky:

    (
        ChildPosition between @FromPosition and @ToPosition or
        ChildPosition between @ToPosition and @FromPosition
    )

But that's because between will always return false if you give it the higher of two values in the first position, and alternate formulations (to avoid the apparent redundancy) tend to be uglier.

Another alternative you might want to consider is using floats to represent the positions rather than ints. Most of the time, you can place a child between any two other children (say at positions 4 and 5) by taking the average of their positions (4.5), and you don't have to do any other renumbering. Occasionally, this doesn't work (once you're down to the limits of what can be represented by a float), but you just need to do a quick renumbering exercise to make space for it to work again.

Damien_The_Unbeliever
  • 234,701
  • 27
  • 340
  • 448