Zykluserkennung mit rekursiver Unterabfrage Factoring
https://stackoverflow.com/questions/1731889
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Oracle SQL kann hierarchische Abfragen ausführen, da V2 ihre proprietäre Verbindung durch Syntax verwendet. In ihrer jüngsten 11G -Release 2 fügten sie eine rekursive Unterabfrage hinzu, die auch als rekursiv mit Klausel bezeichnet wird. Dies ist der ANSI -Standard, und wenn ich richtig verstehe, wurde dieser auch von anderen RDBMS -Anbietern implementiert.
Beim Vergleich der Connect-by mit dem rekursiven mit, bemerkte ich einen Unterschied im Ergebnissatz bei der Verwendung der Zykluserkennung. Die Verbindung durch Ergebnisse ist für mich intuitiver. Ich frage mich, ob die Implementierung von Oracle einen Fehler enthält oder ob dies Standard -ANSI und erwartete Verhalten ist. Daher ist meine Frage, ob Sie die rekursive Abfrage mit anderen Datenbanken wie MySQL, DB2, SQL Server und anderen überprüfen können. Vorausgesetzt, diese Datenbanken unterstützen die rekursive Klausel natürlich.
So funktioniert es auf Oracle 11.2.0.1.0
SQL> select *
2 from t
3 /
ID PARENT_ID
---------- ----------
1 2
2 1
2 rows selected.
Die Abfrage mithilfe von 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.
Was für mich intuitiv aussieht. Mit der neuen ANSI -Syntax gibt es jedoch eine weitere Zeile zurück:
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.
Dies ist das Skript, mit dem Sie überprüfen können:
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;
Lösung
Aus Dokumentation auf CONNECT_BY_ISCYCLE:
Das
CONNECT_BY_ISCYCLEPseudocolumn kehrt zurück1Wenn die aktuelle Reihe ein Kind hat, das auch ihr Vorfahr ist
Und das an CYCLE:
Es wird angenommen, dass eine Zeile einen Zyklus bildet, wenn eine seiner Vorfahren die gleichen Werte für die Zyklusspalten hat.
In Ihrem Beispiel Zeile 2 Hat ein Kind, das auch sein Vorfahr ist, aber es id wurde noch nicht zurückgegeben.
Mit anderen Worten, CONNECT_BY_ISCYCLE Überprüft Kinder (die noch zurückgegeben werden müssen) und während CYCLE Überprüft Aktuelle Reihe (was bereits zurückgegeben wird).
CONNECT BY ist zeilbasiert, während rekursiv CTE's sind set-basiert.
Beachten Sie, dass die Dokumentation von Oracle auf CYCLE erwähnt eine "Vorfahrreihe". Im Allgemeinen gibt es jedoch kein Konzept einer "Vorfahrreihe" in einem rekursiven CTE. Es handelt sich um eine festgelegte Operation, die Ergebnisse vollständig aus dem Baum liefern kann. Im Allgemeinen kann der Ankerteil und der rekursive Teil sogar die verschiedenen Tabellen verwenden.
Seit rekursiv CTE'S sind normalerweise verwendet, um Hierarchiebäume zu bauen, Oracle beschlossen, eine Zyklusprüfung hinzuzufügen. Aber aufgrund der set-basierten Art und Weise die rekursive Art und Weise CTEIn Betrieb ist es im Allgemeinen unmöglich zu sagen, dass der nächste Schritt einen Zyklus erzeugt oder nicht, da ohne eine klare Definition der Zyklusbedingung "Ancestor Row" auch nicht definiert werden kann.
Um den "nächsten" Schritt auszuführen, muss das gesamte "aktuelle" Set verfügbar sein. Um jedoch jede Zeile des aktuellen Satzes (einschließlich der Zyklusspalte) zu generieren, müssen wir nur die Ergebnisse der "nächsten" Operation haben.
Es ist kein Problem, wenn der aktuelle Satz immer aus einer einzigen Reihe besteht (wie in CONNECT BY), aber es ist ein Problem, wenn die rekursive Operation auf einem Set als Ganzes definiert ist.
Ich habe mich nicht angesehen Oracle 11 doch aber SQL Server implementiert rekursiv CTE's, indem du nur a versteckt hast CONNECT BY Hinter ihnen erfordert, dass zahlreiche Einschränkungen platziert werden (was alle alle set-basierten Vorgänge verbieten).
PostgreSQLDie Implementierung hingegen ist wirklich set-basiert: Sie können jeden Betrieb mit dem Ankerteil im rekursiven Teil ausführen. Es hat jedoch keine Mittel, um Zyklen zu erkennen, da Zyklen überhaupt nicht definiert sind.
Wie bereits erwähnt, MySQL Implementiert nicht CTE'S überhaupt (es wird nicht implementiert HASH JOIN's oder MERGE JOINS auch nur die verschachtelten Loops, also wundern Sie sich nicht viel).
Ironischerweise habe ich heute einen Brief zu diesem Thema erhalten, den ich in meinem Blog behandeln werde.
Aktualisieren:
Rekursiv CTE's in SQL Server sind nicht mehr als CONNECT BY verkleidet. In diesem Artikel in meinem Blog finden Sie schockierende Details:
Andere Tipps
PostgreSQL unterstützt mit hierarchischen Abfragen im Stil, hat jedoch keine automatische Zykluserkennung. Dies bedeutet, dass Sie Ihre eigenen schreiben müssen, und die Anzahl der zurückgegebenen Zeilen hängt von der Art und Weise ab, wie Sie die Verbindungsbedingungen im rekursiven Teil der Abfrage angeben.
Beide Beispiele verwenden ein Array, wenn IDs (genannt All_ids) zum Erkennen von Schleifen:
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
SO VIEL ICH WEISS:
- MySQL unterstützt keine rekursiven CTEs
- SQL Sever unterstützt keine Zykluserkennung bei rekursiven CTEs
MySQL Server Version 5.0.45 mochte nicht with:
Fehler 1064 (42000): Sie haben einen Fehler in Ihrer SQL -Syntax; Überprüfen Sie das Handbuch, das Ihrer MySQL -Serverversion entspricht, damit die richtige Syntax in der Nähe von TR (ID, Eltern_ID) als (SELECT ID, STRUFT_ID VON D WHERE ID = 1 UNION All S 'in Zeile 1 auswählen kann.
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;
Ich denke besser ist dieser Zustand d.slave = ANY(all_ids)
Die Ergebnisse der Verbindung durch sind möglicherweise nicht immer intuitiv.
Nachfolgend Abfragen zeigen unterschiedliche Ansätze zum Erkennen von Zyklen, beginnend mit id = 3 Für die Grafik auf dem Bild.
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.
Knoten mit id = 3 Hat zwei Eltern, so dass Oracle in diesem Beispiel zwei Zyklen durchquert.
(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)
und
(5, 3) -> (3, 4) -> (4, 5)
Edge (5, 3) fehlt im Ergebnis der ersten Abfrage und des ersten Zyklus. Gleichzeitig erscheint der Rand (5, 3) im Ergebnis für die dritte Abfrage und den zweiten Zyklus zweimal.
Warum so? Sie können die Beschreibung der Zykluserkennungslogik in der von Quassnoi bereitgestellten Antwort überprüfen. Im einfachen Englisch bedeutet das, dass das
(1) Verbinden Sie durch Erkennung eines Zyklus, wenn Kinder -ID für die aktuelle Zeile ist Teil der bisher besuchten IDs
(2) Rec mit Erkennung eines Zyklus, wenn ID für die aktuelle Zeile ist Teil der bisher besuchten IDs
Das Ergebnis der zweiten Abfrage sieht am natürlichsten aus, obwohl es ein zusätzliches Prädikat gibt and prior id_parent is not null. In diesem Fall
(3) Es erkennt einen Zyklus, wenn ID für die aktuelle Zeile ist ein Teil von übergeordnete IDsbisher besucht
Alle diese Bedingungen sind in den Spalten CNT1, CNT2, CNT3 in der folgenden Abfrage implementiert.
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.
Wenn Sie mit CNT1/CNT2/CNT3 den Filter für den FILTEN und den Zyklus -ID -Zyklus auf 1 Standard 0 "entfernen, gibt die Abfrage das Ergebnis als entsprechende Abfrage oben zurück. Mit anderen Worten Sie können vermeiden cycle clause und implementieren Sie die Zykluserkennungslogik, die Sie intuitiver finden.
Weitere Details zum Durchqueren von Hierarchien und Zykluserkennung finden Sie im Buch Oracle SQL enthüllte.
