Невозможно обнаружить циклические данные в базе данных SQLite

Question

Используя SQLite, у меня есть подозрительный случай рекурсивных данных с циклом - другими словами, дочерний узел также является его собственным дедушкой. Симптомом, конечно же, является бесконечный цикл

Я знаю, как Oracle и Postgresql обрабатывают циклические данные; но не нашли никакого способа сделать это с помощью SQLite. Ниже приведен пример данных с циклом. Если вы удалите последнюю «строку» в таблице наборов данных, она будет работать. Как написано, он переходит в бесконечный цикл.

with DataSet as 
(
    select 'A' as node, null as parent union all 
    select 'B' as node, 'A' as parent union all 
    select 'C' as node, 'B' as parent union all 
    select 'D' as node, 'C' as parent union all 
    select 'A' as node, 'D' as parent 
), 
Hierarchy(node, parent, level, path) 
as 
(
    select DataSet.node, 
      DataSet.parent, 
      1 as level, 
      '/' || DataSet.node as path 
    from  DataSet 
    where DataSet.parent is null 

    union all 
    select DataSet.node, 
      DataSet.parent, 
      Hierarchy.level + 1 as level, 
      Hierarchy.path || '/' || DataSet.node as path 
    from Hierarchy 
    join DataSet 
    on  DataSet.parent = Hierarchy.node 
) 
select * 
from  Hierarchy 

order by path 
; 

Answer 1

Без level, вы могли бы использовать UNION игнорировать дубликаты.

В противном случае нет простого способа сравнить «старые» строки.
Вы можете добавить достаточно большой LIMIT, чтобы исключить бесконечный цикл, но не всегда удалять дубликаты.

Answer 2

Чтобы закрыть петлю (каламбур), я наконец-то выяснил метод, который работает. Плюс я даже добавил столбец, чтобы показать строки, где существует циклическое условие. Это решение включает в себя: уровень (глубина), родительский, дочерний, путь (от корня до узла/листа) и нуль или один для обнаружения цикла. Вы можете вставить SQL ниже в sqlite3 строке и он будет отображать:

level parent node  path   cyclic_flag 
------ ------- ------- ------------ ------------ 
0  A  B  /A/B   0 
1  B  C  /A/B/C  0 
2  C  D  /A/B/C/D  0 
3  D  A  /A/B/C/D/A 1 
sqlite> 

Наконец, вот SQL, который показывает метод. Единственная сложная часть - использование подсчета подстрок в пути (следующий узел подсчитывается подстрокой).

с набором данных в качестве
(
выберите «А» в качестве родителя, «B» в качестве союза узла всех
выберите «B» в качестве родителя, «C» в качестве союза узла всех
выберите «C» в качестве родителя , 'D', как узел
объединения всех выберите 'D' в качестве родителя, 'A' как узел
),
иерархии (уровень, родитель, узел, путь, cyclic_flag)
как
(
выберите 0 как уровень,
dataset.parent,
dataset.node,
'/' || dataset.parent || '/' || dataset.node по пути,
0, как cyclic_flag
из набора данных
, где dataset.parent = 'А'

объединение всех
выбрать
hierarchy.level + 1, как уровень,
dataset.parent,
dataset.node,
hierarchy.path || '/' || dataset.node по пути,
случай, когда

(длина (путь || dataset.node) - длина (заменить (путь || dataset.node, dataset.node, '')))/длина (набор данных.узел) = 1
затем 0
еще 1
конца как cyclic_flag
из иерархии
внутреннего соединения набора данных
на dataset.parent = hierarchy.node
где (длина (путь) - длина (заменить (путь , hierarchy.node, '')))/длина (hierarchy.node) )
выберите *
из иерархии

порядке путь
;