Detecção de ciclo com fatoração de subconsência recursiva
https://stackoverflow.com/questions/1731889
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
O Oracle SQL pode fazer consultas hierárquicas desde a V2, usando sua conexão proprietária por sintaxe. Em sua mais recente versão 11g, eles adicionaram fatoração de subconsência recursiva, também conhecida como cláusula recursiva com. Esse é o padrão ANSI e, se eu entender corretamente, este também foi implementado por outros fornecedores de RDBMS.
Ao comparar a conexão com o recursivo, notei uma diferença no conjunto de resultados ao usar a detecção do ciclo. O Connect by Results é mais intuitivo para mim, por isso estou me perguntando se a implementação da Oracle contém um bug, ou se isso é o ANSI padrão e o comportamento esperado. Portanto, minha pergunta é se você pode verificar o recursivo com consulta usando outros bancos de dados como MySQL, DB2, SQL Server e outros. Desde que esses bancos de dados apoiem o recursivo com cláusula, é claro.
Aqui está como funciona no Oracle 11.2.0.1.0
SQL> select *
2 from t
3 /
ID PARENT_ID
---------- ----------
1 2
2 1
2 rows selected.
A consulta usando Connect by Syntax:
SQL> select id
2 , parent_id
3 , connect_by_iscycle
4 from t
5 connect by nocycle parent_id = prior id
6 start with id = 1
7 /
ID PARENT_ID CONNECT_BY_ISCYCLE
---------- ---------- ------------------
1 2 0
2 1 1
2 rows selected.
O que me parece intuitivo. No entanto, usando a nova sintaxe ANSI, ele retorna mais uma linha:
SQL> with tr (id,parent_id) as
2 ( select id
3 , parent_id
4 from t
5 where id = 1
6 union all
7 select t.id
8 , t.parent_id
9 from t
10 join tr on t.parent_id = tr.id
11 ) cycle id set is_cycle to '1' default '0'
12 select id
13 , parent_id
14 , is_cycle
15 from tr
16 /
ID PARENT_ID I
---------- ---------- -
1 2 0
2 1 0
1 2 1
3 rows selected.
Este é o script que você pode usar para verificar:
create table t
( id number
, parent_id number
);
insert into t values (1, 2);
insert into t values (2, 1);
commit;
with tr (id,parent_id) as
( select id
, parent_id
from t
where id = 1
union all
select t.id
, t.parent_id
from t
join tr on t.parent_id = tr.id
) cycle id set is_cycle to '1' default '0'
select id
, parent_id
, is_cycle
from tr;
Solução
Da documentação sobre CONNECT_BY_ISCYCLE:
o
CONNECT_BY_ISCYCLEPseudocolumn Returns1Se a linha atual tiver um filho que também é seu ancestral
e isso em CYCLE:
É considerado uma linha para formar um ciclo se uma de suas linhas ancestrais tiver os mesmos valores para as colunas do ciclo.
No seu exemplo, Row 2 tem um filho que também é seu ancestral, mas seu id ainda não foi devolvido.
Em outras palavras, CONNECT_BY_ISCYCLE verifica o crianças (que ainda não foram devolvidos), enquanto CYCLE verifica o linha atual (que já está devolvido).
CONNECT BY é baseado em linha, embora recursivo CTESão baseados em conjuntos.
Observe que a documentação do Oracle sobre CYCLE menciona uma "fila de ancestral". No entanto, de um modo geral, não há conceito de "fila ancestral" em um recursivo CTE. É uma operação baseada em conjunto que pode produzir resultados completamente fora da árvore. De um modo geral, a parte da âncora e a parte recursiva podem até usar as diferentes tabelas.
Desde recursivo CTEsão usualmente usado para construir árvores de hierarquia, Oracle decidiu adicionar uma verificação de ciclo. Mas devido à maneira baseada em conjunto, o recursivo CTEOpera, geralmente é impossível dizer que a próxima etapa gerará um ciclo ou não, porque sem uma definição clara da condição do ciclo "ancestral da linha" também não pode ser definida.
Para executar a etapa "Next", todo o conjunto "atual" precisa estar disponível, mas para gerar cada linha do conjunto atual (que inclui a coluna do ciclo), precisamos apenas ter os resultados da operação "a próxima".
Não é um problema se o conjunto atual sempre consistir em uma única linha (como em CONNECT BY), mas é um problema se a operação recursiva definida em um conjunto como um todo.
Não olhou para Oracle 11 No entanto, mas SQL Server implementos recursivos CTEestá apenas escondendo um CONNECT BY Atrás deles, o que requer a colocação de inúmeras restrições (todas efetivamente proibirem todas as operações baseadas em conjuntos).
PostgreSQLA implementação, por outro lado, é realmente baseada em conjuntos: você pode fazer qualquer operação com a parte âncora na parte recursiva. No entanto, não tem meios para detectar ciclos, porque os ciclos não são definidos em primeiro lugar.
Como foi mencionado antes, MySQL não implementa CTESi (não implementa HASH JOIN's ou MERGE JOINS também, apenas os loops aninhados, então não se surpreenda muito).
Ironicamente, recebi uma carta hoje sobre esse assunto, que abordarei no meu blog.
Atualizar:
Recursivo CTE'pecado SQL Server não são mais do que CONNECT BY disfarçado. Veja este artigo no meu blog para obter detalhes chocantes:
Outras dicas
O PostgreSQL suporta com consultas hierárquicas de estilo, mas não possui nenhuma detecção de ciclo automático. Isso significa que você precisa escrever o seu próprio e o número de linhas retornadas depende da maneira como você especifica as condições de junção na parte recursiva da consulta.
Ambos os exemplos usam uma matriz se os IDs (chamados all_ids) para detectar loops:
WITH recursive tr (id, parent_id, all_ids, cycle) AS (
SELECT id, parent_id, ARRAY[id], false
FROM t
WHERE id = 1
UNION ALL
SELECT t.id, t.parent_id, all_ids || t.id, t.id = ANY(all_ids)
FROM t
JOIN tr ON t.parent_id = tr.id AND NOT cycle)
SELECT id, parent_id, cycle
FROM tr;
id | parent_id | cycle
----+-----------+-------
1 | 2 | f
2 | 1 | f
1 | 2 | t
WITH recursive tr (id, parent_id, all_ids, cycle) AS (
SELECT id, parent_id, ARRAY[id], false
FROM t
WHERE id = 1
UNION ALL
SELECT t.id, t.parent_id, all_ids || t.id, (EXISTS(SELECT 1 FROM t AS x WHERE x.id = t.parent_id))
FROM t
JOIN tr ON t.parent_id = tr.id
WHERE NOT t.id = ANY(all_ids))
SELECT id, parent_id, cycle
FROM tr;
id | parent_id | cycle
----+-----------+-------
1 | 2 | f
2 | 1 | t
ATÉ ONDE SEI:
- O MySQL não suporta CTE recursivo
- O SQL sever não suporta a detecção do ciclo em CTE recursivo
MySQL Server versão 5.0.45 não gostou with:
Erro 1064 (42000): você tem um erro na sua sintaxe SQL; Verifique o manual que corresponde à sua versão do MySQL Server para obter a sintaxe correta para usar próximo 'com tr (id, parent_id) como (selecione id, parent_id de t where i id = 1 union all s' na linha 1.
WITH RECURSIVE s (master, slave, all_ids, cycle) AS
(
SELECT master, slave, ARRAY[master], false FROM binding WHERE master=3477
UNION ALL
SELECT d.master, d.slave, all_ids || d.master, d.slave = ANY(all_ids)
FROM
binding AS d
JOIN
s
ON (d.master = s.slave)
WHERE NOT d.master = ANY(all_ids)
)
SELECT *
FROM s;
Eu acho melhor essa condição d.slave = ANY(all_ids)
Os resultados da conexão nem sempre podem ser intuitivos.
As perguntas abaixo demonstram diferentes abordagens para detectar ciclos começando com id = 3 para o gráfico na imagem.
create table graph (id, id_parent) as
(select 2, 1 from dual
union all select 3, 1 from dual
union all select 4, 3 from dual
union all select 5, 4 from dual
union all select 3, 5 from dual)
SQL> select level lvl, graph.*, connect_by_iscycle cycle
2 from graph
3 start with id = 3
4 connect by nocycle prior id = id_parent;
LVL ID ID_PARENT CYCLE
---------- ---------- ---------- ----------
1 3 1 0
2 4 3 0
3 5 4 1
1 3 5 0
2 4 3 0
3 5 4 1
6 rows selected.
SQL> select level lvl, graph.*, connect_by_iscycle cycle
2 from graph
3 start with id = 3
4 connect by nocycle prior id = id_parent
5 and prior id_parent is not null;
LVL ID ID_PARENT CYCLE
---------- ---------- ---------- ----------
1 3 1 0
2 4 3 0
3 5 4 0
4 3 5 1
1 3 5 0
2 4 3 0
3 5 4 1
7 rows selected.
SQL> with t(id, id_parent) as
2 (select *
3 from graph
4 where id = 3
5 union all
6 select g.id, g.id_parent
7 from t
8 join graph g
9 on t.id = g.id_parent)
10 search depth first by id set ord
11 cycle id set cycle to 1 default 0
12 select * from t;
ID ID_PARENT ORD C
---------- ---------- ---------- -
3 1 1 0
4 3 2 0
5 4 3 0
3 5 4 1
3 5 5 0
4 3 6 0
5 4 7 0
3 5 8 1
8 rows selected.
Nó com id = 3 tem dois pais para que o Oracle atravessa dois ciclos neste exemplo.
(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)
e
(5, 3) -> (3, 4) -> (4, 5)
Edge (5, 3) está ausente no resultado da primeira consulta e do primeiro ciclo. Ao mesmo tempo, a borda (5, 3) aparece no resultado da terceira consulta e do segundo ciclo duas vezes.
Por quê então? Você pode verificar a descrição da lógica de detecção do ciclo na resposta fornecida pelo Quassnoi. Em inglês simples, significa que
(1) Conecte -se detecta um ciclo se Id de criança para a linha atual faz parte dos IDs visitados até agora
(2) Rec com detecta um ciclo se ID da linha atual faz parte dos IDs visitados até agora
O resultado da segunda consulta parece mais natural, embora exista um predicado adicional and prior id_parent is not null. Nesse caso
(3) detecta um ciclo se ID da linha atual é parte de IDs dos paisvisitado até agora
Todas essas condições são implementadas nas colunas CNT1, CNT2, CNT3 na consulta abaixo.
SQL> with t(id, id_parent, path_id, path_id_parent, cnt1, cnt2, cnt3) as
2 (select g.*,
3 cast('->' || g.id as varchar2(4000)),
4 cast('->' || g.id_parent as varchar2(4000)),
5 0,
6 0,
7 0
8 from graph g
9 where id = 3
10 union all
11 select g.id,
12 g.id_parent,
13 t.path_id || '->' || g.id,
14 t.path_id_parent || '->' || g.id_parent,
15 regexp_count(t.path_id || '->', '->' ||
16 (select id from graph c where c.id_parent = g.id) || '->'),
17 regexp_count(t.path_id || '->', '->' || g.id || '->'),
18 regexp_count(t.path_id_parent || '->', '->' || g.id || '->')
19 from t
20 join graph g
21 on t.id = g.id_parent
22 -- and t.cnt1 = 0
23 -- and t.cnt2 = 0
24 -- and t.cnt3 = 0
25 )
26 search depth first by id set ord
27 cycle id set cycle to 1 default 0
28 select * from t;
ID ID_PARENT PATH_ID PATH_ID_PARENT CNT1 CNT2 CNT3 ORD C
---------- ---------- --------------- --------------- ---- ---- ---- ---------- -
3 1 ->3 ->1 0 0 0 1 0
4 3 ->3->4 ->1->3 0 0 0 2 0
5 4 ->3->4->5 ->1->3->4 1 0 0 3 0
3 5 ->3->4->5->3 ->1->3->4->5 1 1 1 4 1
3 5 ->3 ->5 0 0 0 5 0
4 3 ->3->4 ->5->3 0 0 0 6 0
5 4 ->3->4->5 ->5->3->4 1 0 1 7 0
3 5 ->3->4->5->3 ->5->3->4->5 1 1 1 8 1
8 rows selected.
Se você o filtro de descomposição por CNT1/CNT2/CNT3 e remova "Ciclo de identificação do ciclo para 1 padrão 0", então a consulta retornará o resultado como consulta correspondente acima. Em outras palavras você pode evitar cycle clause e implementar qualquer lógica de detecção de ciclo que você achar mais intuitivo.
Detalhes adicionais sobre percorrer hierarquias e detecção de ciclo podem ser encontrados no livro Oracle SQL revelou.
