Нахождение всех достижимых узлов с использованием SQL

Question

Предположим, что таблица с двумя столбцами: From и To. Пример:

From To
1    2
2    3
2    4
4    5

Я хотел бы знать, как наиболее эффективно найти все узлы, которые достижимы из узла, используя SQL-запрос. Пример: для 1 он возвращает 2,3,4 и 5. Можно использовать несколько запросов, объединенных предложениями UNION, но это ограничит количество уровней, которые могут быть достигнуты. Возможно, другая структура данных сделает проблему более понятной, но это то, что доступно.

Я использую Firebird, но мне хотелось бы иметь решение, которое использует только стандартный SQL.

Answer 1

Вы можете использовать рекурсивное общее табличное выражение , если вы используете большинство брендов баз данных - за исключением MySQL и SQLite и некоторых других малоизвестных (извините, я считаю Firebird неясным). Этот синтаксис является стандартом ANSI SQL, но Firebird пока не поддерживает его.

Исправление: Firebird 2.1 поддерживает рекурсивные CTE, как комментирует @Hugues Van Landeghem.

В противном случае см. Мою презентацию Модели для иерархических данных с SQL для нескольких различных подходов.

Например, вы можете хранить дополнительные строки для каждого пути в вашем дереве, а не только для непосредственных родительских / дочерних путей. Я называю этот дизайн Закрытие стола .

From To   Length
1    1    0
1    2    1
1    3    2
1    4    2
1    5    3
2    2    0
2    3    1
2    4    1
3    3    0
4    4    0
4    5    1
5    5    0

Теперь вы можете запросить SELECT * FROM MyTable WHERE From = 1 и получить всех потомков этого узла.

PS: я бы не стал называть столбец From, потому что это зарезервированное слово SQL.

Answer 2

К сожалению, нет хорошего общего решения для этого, которое будет работать во всех ситуациях во всех базах данных.

Я рекомендую вам взглянуть на эти ресурсы для решения MySQL:

• Управление иерархическими данными в MySQL
• Модели для иерархических данных - презентация Билла Карвина, в которой обсуждается эта тема, демонстрируются различные решения и сравнивается модель списка смежности, которую вы используете, с другими альтернативными моделями.

Для PostgreSQL и SQL Server вы должны взглянуть на рекурсивные CTE .

Если вы используете Oracle, вам следует взглянуть на CONNECT BY , который является проприетарным расширением SQL, что значительно упрощает работу с древовидными структурами.

Answer 3

При использовании стандартного SQL единственным способом сохранить дерево с приемлемой производительностью чтения является использование хака, такого как перечисление пути. Обратите внимание, что это очень тяжело при записи.

ID   PATH
1    1
2    1;2
3    1;2;3
4    1;2;4


SELECT * FROM tree WHERE path LIKE '%2;%'