rilevamento ciclo con ricorsiva factoring subquery
https://stackoverflow.com/questions/1731889
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Oracle SQL può fare query gerarchiche dal v2, usando il loro proprietario CONNECT BY sintassi. Nella loro ultima release 11g 2, hanno aggiunto ricorsivo factoring subquery, noto anche come il ricorsiva con clausola. Questo è lo standard ANSI, e se ho capito bene, questo è stato implementato da altri fornitori di RDBMS pure.
Se si confronta il connect-by con l'ricorsiva con, ho notato una differenza nel set di risultati in un rilevamento ciclo. La connessione con i risultati sono più intuitivo per me, quindi mi chiedo se l'implementazione di Oracle contiene un bug, o se questo è un comportamento ANSI e previsto di serie. Quindi la mia domanda è se è possibile controllare il ricorsiva con query utilizzando altri database come MySQL, DB2, SQL Server e altri. A condizione che tali banche dati supportano l'ricorsiva con clausola di certo.
Ecco come funziona su Oracle 11.2.0.1.0
SQL> select *
2 from t
3 /
ID PARENT_ID
---------- ----------
1 2
2 1
2 rows selected.
La query utilizzando CONNECT BY sintassi:
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.
Il che sembra intuitivo da me. Tuttavia, utilizzando la nuova sintassi ANSI restituisce più una riga:
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.
Questo è lo script è possibile utilizzare per controllare:
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;
Soluzione
Da documentazione sul CONNECT_BY_ISCYCLE :
I rendimenti
CONNECT_BY_ISCYCLEpseudocolonna1se la riga corrente ha un figlio, che è anche il suo antenato
e che in CYCLE :
Una riga viene considerata per formare un ciclo se una delle righe antenato ha gli stessi valori per le colonne ciclo.
Nel tuo esempio, fila 2 ha un figlio che è anche il suo predecessore, ma la sua id non è stato ancora restituito.
In altre parole, CONNECT_BY_ISCYCLE controlla il bambini (che sono ancora essere restituiti), mentre CYCLE controlla il riga corrente (che è già restituito).
CONNECT BY si basa fila, mentre CTE ricorsive di sono impostati-based.
Si noti che la documentazione di Oracle su CYCLE menziona un "fila degli antenati". Tuttavia, in generale, non esiste il concetto di "fila antenato" in un CTE ricorsivo. E 'un'operazione basata fisso che può produrre risultati completamente dall'albero. In generale, la parte di ancoraggio e la parte ricorsiva può anche utilizzare le diverse tabelle.
Dal CTE ricorsiva di di solito usato per costruire gli alberi di gerarchia, Oracle ha deciso di aggiungere un controllo ciclo. Ma a causa del modo set-based le CTE ricorsive di operare, è generalmente impossibile dire sarà il passo successivo generare un ciclo o meno, perché senza una chiara definizione della condizione ciclo "riga antenato" non può essere definita né.
Per eseguire il passaggio "successivo", l'intero "di" set deve essere disponibile, ma per generare ogni riga del set corrente (che include la colonna ciclo) abbiamo solo bisogno di avere i risultati del "next" operazione.
Non è un problema se il set corrente consiste sempre in una singola riga (come in CONNECT BY), ma è un problema se l'operazione ricorsiva definita su un suo insieme.
Non guardare in Oracle 11 ancora, ma SQL Server implementa ricorsive CTE di semplicemente nascondere un CONNECT BY dietro di loro, che richiede ponendo numerose restrizioni (ognuno dei quali in modo efficace vietare tutte le operazioni basate su set).
L'implementazione di PostgreSQL, d'altra parte, è davvero basata su set: si può fare qualsiasi operazione con la parte di ancoraggio nella parte ricorsiva. Essa non ha alcun mezzo per rilevare cicli, però, perché i cicli non sono definiti in primo luogo.
Come si è accennato prima, MySQL non implementa CTE è affatto (non implementa HASH JOIN di o MERGE JOINs così, solo i cicli annidati, in modo da non essere sorpreso molto).
Per ironia della sorte, ho ricevuto oggi una lettera su questo tema, che mi occuperò nel mio blog.
Aggiornamento:
CTE ricorsivi di in SQL Server non sono altro che CONNECT BY sotto mentite spoglie. Si veda questo articolo nel mio blog per i dettagli scioccanti:
Altri suggerimenti
PostgreSQL supporti con stile query gerarchiche, ma non ha alcun rilevamento ciclo automatico. Questo significa che è necessario scrivere il proprio e il numero di righe restituite dipende dal modo in cui si specificano le condizioni unirsi nella parte ricorsiva della query.
Entrambi gli esempi utilizzano un array se gli ID (chiamati all_ids) per rilevare loop:
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
Per quanto ne sappia:
- MySql non supporta ricorsiva del CTE
- SQL Sever non supporta ciclo rilevamento in ricorsiva di CTE
MySQL Server versione 5.0.45 non piaceva with:
ERRORE 1064 (42000): Hai un errore nella sintassi SQL; controlla il manuale che corrisponde alla versione del server MySQL per il diritto sintassi da utilizzare vicino 'con TR (id, parent_id) come (select id, parent_id da t dove id = 1 union tutto l at line 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;
Credo che sia meglio questa condizione d.slave = ANY(all_ids)
I risultati del connettersi potrebbe non essere sempre intuitivo.
Di seguito query dimostrano diversi approcci per individuare i cicli a partire id = 3 per il grafico sopra l'immagine.
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.
Il nodo con id = 3 ha due genitori in modo Oracle attraversa due cicli in questo esempio.
(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)
e
(5, 3) -> (3, 4) -> (4, 5)
Edge (5, 3) manca dal risultato della prima query e primo ciclo. Allo stesso tempo bordo (5, 3) appare nel risultato del terzo query e secondo ciclo due volte.
Perché così? È possibile controllare descrizione della logica di rilevamento ciclo nella risposta fornita da Quassnoi. In parole povere significa che
(1) da collegare rileva un ciclo se ID bambino per riga corrente è parte ID ha visitato finora
(2) rec con rileva un ciclo se ID per riga corrente fa parte di ID visitato finora
Risultato della seconda query sembra la più naturale, anche se non v'è ulteriore and prior id_parent is not null predicato. In questo caso
(3) rileva un ciclo se ID per riga corrente fa parte di parent ID visitato finora
Tutte queste condizioni sono implementate in colonne CNT1, CNT2, CNT3 in seguito query.
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 il filtro decommentare da CNT1 / CNT2 / CNT3 e rimuovere "ciclo impostato ciclo id per 1 default 0", quindi query risultato di ritorno, corrispondente query di cui sopra. In altre parole, si può evitare cycle clause e implementare la logica di rilevamento ciclo a trovare più intuitivo .
Ulteriori dettagli sulle gerarchie che attraversano e la rilevazione del ciclo possono essere trovati nel libro Oracle SQL Revealed .
