Узнайте, является ли узел предком другого узла для дерева, хранящегося в виде списка смежности в sqlite - PullRequest
Новая
       48

Узнайте, является ли узел предком другого узла для дерева, хранящегося в виде списка смежности в sqlite

0 голосов
/ 17 февраля 2020

Вопрос

У меня есть древовидная структура, хранящаяся в виде таблицы смежности (также известной как Наивное дерево) в базе данных SQL. Я sh выясню, является ли node_b предком node_a. Как я могу это сделать?

Детали фона

Таблица, в которой хранятся узлы, определяется, как показано ниже: 

CREATE TABLE Nodes(
      id INTEGER PRIMARY KEY,
      parent INTEGER,     
      -- Other node specific data
      FOREIGN KEY (parent) REFERENCES Nodes(id)
    );

Дерево глубина неизвестна, но в обычных случаях использования ожидается довольно мала.

В дереве нет петель.

Root узлы имеют родительское значение NULL. Может быть несколько root узлов.

Критерии ответа

Я ищу запрос, который выполняется максимально быстро.

Работа уже сделана

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

Примеры

Учитывая следующий набор данных: 

id     parent
1      NULL
2      1
3      NULL
4      1
5      2
  • Запрос должен вернуть True (или 1) для node_a = 1, node_b = 1
  • Запрос должен возвращать True (или 1) для node_a = 2, node_b = 1
  • Запрос должен возвращать True (или 1) для node_a = 5, node_b = 1
  • Запрос должен возвращать True (или 1) для node_a = 5, node_b = 2
  • Запрос должен возвращать False (или 0) для node_a = 2, node_b = 3
  • Запрос должен вернуть False (или 0) для node_a = 2, node_b = 5

1 Ответ

1 голос
/ 17 февраля 2020

Мое решение

Следующий запрос - это решение, которое я использовал (:node_a и :node_b - это заполнители для рассматриваемого узла и его возможного предка): 

WITH RECURSIVE ancestors AS(
  SELECT parent, id=:node_b AS match 
  FROM NODES WHERE id=:node_a
  UNION ALL
  SELECT n.parent, n.id=:id AS match
  FROM Nodes n JOIN ancestors
  ON ancestors.parent=n.id AND NOT ancestors.match
)
SELECT MAX(match) AS is_ancestor FROM ancestors;

Объяснение

Общее табличное выражение используется для генерации запроса, содержащего родителя каждого из предков node_a, и соответствует ли этот предок node_b

Он начинается с самого node_a и проверяет, совпадает ли это с node_b, возвращая строку, состоящую из двух столбцов parent и match - прямого родителя для node_a и логического значения, представляющего, соответствует ли node_a для node_b.

Затем он поднимается вверх через предков node_a путем рекурсивного присоединения к родительскому столбцу, пока один из предков не совпадет с node_b или родительский столбец не станет равным NULL.

Если node_b является предком node_a, тогда одна строка этой таблицы будет содержать значение true для столбца соответствия. Если это не так, тогда столбец соответствия будет содержать значение false для всех строк. Значения true и false представлены как 1 и 0, соответственно, MAX столбца соответствия будет 1 в первом случае и 0 во втором.

Поэтому весь запрос возвращает 1, если node_b является предком node_a и 0 в противном случае.

...