Как получить конечную и начальную точку всех линий иерархического дерева?

Question

У меня есть база данных SQLite с набором различных иерархических деревьев (аналогично изображению ниже), где я хочу получить только начальную и конечную точки каждой линии дерева. В blue - идентификаторы дерева (называемые ws_id), в green - требуемые начальная и конечная точки и в red нежелательные объекты между начальной и конечной точками.

Вот пример данных с той же структурой, что и иерархическое дерево выше, и структура данных, аналогичная моей:

CREATE TABLE feat_link
(ws_id integer, source_node varchar(10), target_node varchar(10));
ALTER TABLE feat_link ADD PRIMARY KEY (ws_id);
INSERT INTO feat_link
VALUES ('b', '1', '36');
INSERT INTO feat_link
VALUES ('b', '1', '17');
INSERT INTO feat_link
VALUES ('b', '36', '21');   
INSERT INTO feat_link
VALUES ('b', '2', '20');
INSERT INTO feat_link
VALUES ('b', '3', '37');  
INSERT INTO feat_link
VALUES ('b', '37', '24');  

Как видите, значение source_node совпадает только со следующим значением target_node, а не с конечным узлом линии дерева. То, что мне нужно, - это сопоставление (я думаю, рекурсивный запрос), которое сначала распознает, какие source_nodes действительно являются началом дерева (внимание, например, B не ожидается), а какой является последней точкой этой строки. Другие столбцы значений не имеют значения.

Вот мой ожидаемый результат:

До сих пор мы пробовали рекурсивные запросы. Вот пример, предполагающий, что моя таблица данных выше называется "feat_link":

WITH RECURSIVE target(x) AS (
  SELECT (select 1 from feat_link)
  UNION ALL 
  SELECT feat_link.target_node
  FROM feat_link, target
  WHERE feat_link.source_node=target.x 
    AND feat_link.source_node IS NOT NULL 
    and feat_link.ws_id = 'B'
) 
select distinct x from target;

У вас есть идеи, как улучшить код или даже лучшую идею? Мы только иногда получаем возврат, и результаты, кажется, не всегда верны.

Answer 1

Сначала перечислим все возможные строки (нужные и нежелательные) стандартным образом:

WITH RECURSIVE lines(ws_id, source_node, target_node) AS (
  -- start with all nodes that have no link to their start
  SELECT ws_id, source_node, target_node
  FROM feat_link
  WHERE (ws_id, source_node) NOT IN (SELECT ws_id, target_node
                                     FROM feat_link)

  UNION ALL

  SELECT l.ws_id, l.source_node, f.target_node
  FROM feat_link f
  JOIN lines l ON (f.ws_id, f.source_node) = (l.ws_id, l.target_node)
)
...

Затем отфильтруйте все строки, которые являются частью более длинной строки, то есть имеют ссылку на конец:

...
SELECT *
FROM lines
WHERE (ws_id, target_node) NOT IN (SELECT ws_id, source_node
                                   FROM feat_link);