SQL to reorder nodes in a hierarchy

Question

I've got a 'task list' database that uses the adjacency list model (see below) so each 'task' can have unlimited sub-tasks. The table has an 'TaskOrder' column so everything renders in the correct order on a treeview.

Is there an SQL statement (MS-SQL 2005) that will select all the child nodes for a specified parent and update the TaskOder column when a sibling is deleted?

Task Table
----------
TaskId
ParentTaskId
TaskOrder
TaskName
--etc--

Any ideas? Thanks.

Answer 1

If you're only using TaskOrder for sorting, it would certainly be simpler to simply leave the holes in TaskOrder, because simply deleting items won't make the sorting incorrect. But then I'm not sure about your application's needs.

Answer 2

Not directly. This is a Topological Sort where you are 'hanging' the child nodes off a parent. If there is no dependency within the children the order that they are executed does not matter. If the children must be executed in a certain order then you do not have enough information to infer this - they would have to have additional levels of hierarchy.

Assuming that the order of children within a parent is irrelevant then a topoligical sort will get you what you want. You won't get this into a single query in most SQL dialects - you will have to write a sproc to do it.

If the order of the children within the node is relevant then you need to maintain the task order within the parent. A query using ParentNodeID, TaskOrder and count (*) will pick out duplicates but unless the system has additional information to order the tasks you will still need manual intervention to select the correct order.

Please add comments if you want me to clarify something.

Answer 3

This looks like a job for ROW_Number.

DECLARE @Tasks TABLE
(
  TaskId int PRIMARY KEY,
  ParentTaskId int,
  TaskOrder int,
  TaskName varchar(30)
)

INSERT INTO @Tasks(TaskId, ParentTaskId, TaskOrder, TaskName)
SELECT 1, null, 1, 'ParentTask'

INSERT INTO @Tasks(TaskId, ParentTaskId, TaskOrder, TaskName)
SELECT 2, 1, 2, 'B'

INSERT INTO @Tasks(TaskId, ParentTaskId, TaskOrder, TaskName)
SELECT 3, 1, 1, 'A'

INSERT INTO @Tasks(TaskId, ParentTaskId, TaskOrder, TaskName)
SELECT 4, 1, 3, 'C'
--Initial
SELECT * FROM @Tasks WHERE ParentTaskId = 1 ORDER BY TaskOrder

DELETE FROM @Tasks WHERE TaskId = 2
--After Delete
SELECT * FROM @Tasks WHERE ParentTaskId = 1 ORDER BY TaskOrder


UPDATE t
SET TaskOrder = NewTaskOrder
FROM @Tasks t
  JOIN
(
SELECT TaskId, ROW_Number() OVER(ORDER BY TaskOrder) as NewTaskOrder
FROM @Tasks
WHERE ParentTaskId = 1
) sub ON t.TaskId = sub.TaskId

--After Update
SELECT * FROM @Tasks WHERE ParentTaskId = 1 ORDER BY TaskOrder

Answer 4

Delete task 88:

UPDATE TaskTable
SET ParentTaskID = (SELECT ParentTaskID AS temp FROM Task_Table t1 WHERE TaskID = 88)
WHERE
TaskID IN (SELECT TaskID task2 FROM TaskTable t2 WHERE ParentTaskID = 88);
Delete FROM TaskTable WHERE TaskID = 88;

Of course, you could eliminate the delete, and just leave the record lying around for future reporting purposes.

CAVEAT: NOT TESTED!!!

Answer 5

Couple of different ways... Since the TaskOrder is scoped by parent id, it's not terribly difficult to gather it. In SQL Server, I'd put a trigger on delete that decrements all the ones 'higher' than the one you deleted, thereby closing the gap (pseudocode follows):

CREATE TRIGGER ON yourtable FOR DELETE
AS
  UPDATE Task
     SET TaskOrder    = TaskOrder - 1
   WHERE ParentTaskId = deleted.ParentTaskId
     AND TaskOrder    > deleted.TaskOrder

If you don't want a trigger, you can capture the parentID and TaskOrder in a query first, delete the row, then execute that same update statement but with literals rather than the trigger.

Or if you want to minimize server round-trips, you could move the to-be-deleted task all the way to the bottom, then move the others up, then do the delete, but that seems overly complicated.