CODEWITHSUNDEEP
mysqlsqlsqlite
izrik
izrik

Reputation: 954

SQL - How to sort rows relative to each other?

I have a table of tasks to be performed. Each task can have one dependency, represented by a column, dep. The column forms a FK with the id column of the same table. The column is nullable, so a task could have no dependency. I want to be able to sort a list of tasks such that a task will always appear after another task that it depends on.

So, with an example like this: 

id | name | dep
----------------
1  | A    | NULL
2  | B    | 1
3  | C    | 1
4  | D    | 2

Valid orderings would be A,B,C,D, A,C,B,D, and A,C,D,B. This is technically a partial ordering. The position of B relative to C is unimportant. What matters is that 'A' comes before both 'B' and 'C', and 'B' comes before 'D'.

If I were doing something like this in C#, I would probabl create a class that implements the IComparator<T> interface, and return 1 or -1 depending on the object's relationship to each other. But it seems that SQL's ORDER BY clause doesn't allow something like that.

In standard SQL, how can I sort rows relative to each other, based on a FK relationship?

UPDATE: I'm using Flask-SQLAlchemy (Flask-SQLAlchemy==2.1 and SQLAlchemy==0.9.9) to connect to the database. For testing I'm using an in-memory sqlite db (version 3.19.3), and in production I use MySQL 5.6.

I had hoped to avoid CTE's, because I'm unfamiliar with them, and because my version of MySQL doesn't support them.

My DDL would look something like this (MySQL dialect):

CREATE TABLE `task` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) NOT NULL,
  `dep` int(11) DEFAULT NULL,
  PRIMARY KEY (`id),
  CONSTRAINT `task_ibfk_1` FOREIGN KEY (`dep`) REFERENCES `task` (`id`)
);

My original plan was to sort the tasks like so:

SELECT name FROM task JOIN task AS t2 ON (t2.id = task.dep) ORDER BY (???);

But I suspect that isn't possible.

Upvotes: 2

Views: 571

Answers (1)

Cᴏʀʏ
Cᴏʀʏ

Reputation: 107586

EDIT: This was written for Microsoft SQL Server, which may not be transferrable to the DBMS OP is using. I'll leave it here for reference.

While we're waiting for you to update with which DBMS you're using, I'll toss this into the ring. It uses a recursive CTE as the commenters have pointed out to establish the level (ultimately our sort order) each task lives at based on the relationship to its parent. I altered your input data a little to show that is correctly sorts, since yours is already in the ideal order.

WITH Test(id, name, dep) AS
(
    SELECT 1, 'A', NULL UNION
    SELECT 2, 'B', 4 UNION
    SELECT 3, 'C', 2 UNION
    SELECT 4, 'D', 1 
)
, RecursiveCTE AS
(
  SELECT id, name, dep, 0 AS level
  FROM Test
  WHERE dep IS NULL
  UNION ALL
  SELECT i.id, i.name, i.dep, level + i.id
  FROM Test i
  INNER JOIN RecursiveCTE c ON c.id = i.dep
)
SELECT id, name, dep
FROM RecursiveCTE
ORDER BY level;

Output:

id name dep
-- ---- ----
1  A    NULL
4  D    1
2  B    4
3  C    2

Upvotes: 1

Related Questions