How to swap values among records constrained by a

Question

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. :)

Answer 1

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.