SQL - Как сортировать строки относительно друг друга?

Question

У меня есть таблица задач, которые нужно выполнить. Каждая задача может иметь одну зависимость, представленную столбцом, dep. Столбец образует FK со столбцом id той же таблицы. Столбец имеет значение NULL, поэтому у задачи не может быть никакой зависимости. Я хочу иметь возможность сортировать список задач таким образом, чтобы задача всегда появлялась после другой задачи, от которой она зависит.

Итак, с примером, подобным этому:

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

Допустимые заказы: A,B,C,D, A,C,B,D и A,C,D,B. Технически это частичный порядок. Положение B относительно C неважно. Важно то, что «A» предшествует как «B», так и «C», а «B» предшествует «D».

Если бы я делал что-то подобное в C #, я бы вероятно создал класс, который реализует интерфейс IComparator<T>, и возвратил бы 1 или -1 в зависимости от отношения объекта друг к другу. Но, похоже, в предложении SQL ORDER BY что-то подобное не допускается.

Как в стандартном SQL можно сортировать строки относительно друг друга на основе отношения FK?

---

UPDATE: Я использую Flask-SQLAlchemy (Flask-SQLAlchemy==2.1 и SQLAlchemy==0.9.9) для подключения к базе данных. Для тестирования я использую sqlite db в памяти (версия 3.19.3), а в производстве я использую MySQL 5.6.

Я надеялся избежать CTE, потому что я не знаком с ними, и потому что моя версия MySQL их не поддерживает.

Мой DDL будет выглядеть примерно так (диалект MySQL):

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`)
);

Мой первоначальный план состоял в том, чтобы сортировать задачи так:

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

Но я подозреваю, что это невозможно.

Answer 1

РЕДАКТИРОВАТЬ : Это было написано для Microsoft SQL Server, который может не передаваться в СУБД, которую использует OP.Я оставлю это здесь для справки.

---

Пока мы ждем, чтобы вы уточнили, какую СУБД вы используете, я добавлю это в кольцо.Он использует рекурсивный CTE, как указали комментаторы, чтобы установить уровень (в конечном счете, наш порядок сортировки), на котором живет каждая задача, на основе отношений с ее родителем.Я немного изменил ваши входные данные, чтобы показать, что они правильно сортируются, поскольку ваши уже в идеальном порядке.

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;

Вывод:

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