détection de cycle avec l'affacturage sous-requête récursive
https://stackoverflow.com/questions/1731889
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Oracle SQL peut faire des requêtes hiérarchiques depuis v2, en utilisant leur CONNECT exclusive par la syntaxe. Dans leur dernière version 11g 2, ils ont ajouté l'affacturage sous-requête récursive, également connu sous le récursive avec clause. Ceci est la norme ANSI, et si je comprends bien, celui-ci a été mis en œuvre par d'autres fournisseurs de SGBDR ainsi.
Si l'on compare la connexion par le récursive avec, je remarqué une différence dans le jeu de résultats lors de l'utilisation de détection de cycle. La connexion par les résultats sont plus intuitifs pour moi, alors je me demande si la mise en œuvre d'Oracle contient un bug, ou si cela est un comportement normal ANSI et prévu. Par conséquent, ma question est de savoir si vous pouvez vérifier l'récursive avec l'aide d'autres bases de données requête comme MySQL, DB2, SQL Server et d'autres. À condition que ces bases de données prennent en charge l'récursive avec clause bien sûr.
Voici comment cela fonctionne sur Oracle 11.2.0.1.0
SQL> select *
2 from t
3 /
ID PARENT_ID
---------- ----------
1 2
2 1
2 rows selected.
La requête en utilisant la syntaxe CONNECT BY:
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.
Ce qui semble intuitif pour moi. Cependant, en utilisant la nouvelle syntaxe ANSI retourne une ligne supplémentaire:
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.
Ceci est le script que vous pouvez utiliser pour vérifier:
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;
La solution
De la documentation sur CONNECT_BY_ISCYCLE :
Les rendements
CONNECT_BY_ISCYCLEde1si la Pseudo-ligne actuelle a un enfant qui est aussi son ancêtre
et sur CYCLE :
Une ligne est considéré pour former un cycle si l'une de ses lignes d'ancêtre a les mêmes valeurs pour les colonnes de cycle.
Dans votre exemple, la ligne 2 a un enfant qui est aussi son ancêtre, mais son id n'a pas été retourné encore.
En d'autres termes, CONNECT_BY_ISCYCLE vérifie les enfants (qui sont encore retournés), alors que CYCLE vérifie la ligne actuelle (qui est déjà retourné).
CONNECT BY est basée rangée, tandis que celle des récursifs CTE sont basées sur des ensembles.
Notez que la documentation d'Oracle sur CYCLE mentionne une « ligne ancêtre ». Cependant, en général, il n'y a pas de concept d'une « rangée ancêtre » dans un CTE récursive. Il est une opération à base de jeu qui peut donner des résultats complètement hors de l'arbre. D'une manière générale, la partie d'ancrage et la partie récursive peut même utiliser les différentes tables.
Depuis son récursives de CTE sont habituellement utilisé pour construire des arbres hiérarchie, Oracle a décidé d'ajouter un contrôle de cycle. Mais en raison de la façon ensembliste les CTE récursives de fonctionnement, il est généralement impossible de dire sera l'étape suivante générer un cycle ou non, parce que sans une définition claire de l'état du cycle « de la ligne ancêtre » ne peut pas être défini.
Pour effectuer le « suivant » étape, l'ensemble « courant » jeu doit être disponible, mais pour générer chaque ligne de l'ensemble courant (qui comprend la colonne de cycle), nous avons juste besoin d'avoir les résultats de la « prochaine » opération.
Il est pas un problème si l'ensemble actuel se compose toujours d'une seule rangée (comme dans CONNECT BY), mais il est un problème si l'opération récursive définie sur un ensemble dans son ensemble.
n'a pas examiné Oracle 11 encore, mais SQL Server implémente des années CTE récursives simplement en cachant un CONNECT BY derrière eux, ce qui nécessite de placer de nombreuses restrictions (tous qui interdisent efficacement toutes les opérations à base de set).
La mise en œuvre de PostgreSQL, d'autre part, est basé sur un ensemble vraiment: vous pouvez faire une opération avec la partie d'ancrage dans la partie récursive. Il ne dispose pas de moyens pour détecter les cycles, cependant, parce que les cycles ne sont pas définis en premier lieu.
Comme il a été mentionné précédemment, MySQL ne met pas en œuvre des années CTE du tout (il ne met pas en œuvre et de les HASH JOIN ou MERGE JOINs, seules les boucles imbriquées, alors ne soyez pas surpris beaucoup).
Ironie du sort, j'ai reçu une lettre aujourd'hui sur ce sujet, que je couvrirai dans mon blog.
Mise à jour:
de récursives de CTE dans SQL Server ne sont plus que CONNECT BY déguisé. Voir cet article dans mon blog pour plus de détails choquants:
Autres conseils
PostgreSQL supporte les requêtes hiérarchiques avec style, mais ne dispose pas de détection de cycle automatique. Cela signifie que vous devez écrire votre propre et le nombre de lignes retournées dépend de la manière que vous spécifiez des conditions de jointure dans la partie récursive de la requête.
Les deux exemples utilisent un tableau si les ID (appelés all_ids) pour détecter les boucles:
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
AFAIK:
- MySQL ne supporte pas de CTE récursive
- SQL Sever ne prend pas en charge le cycle détection de CTE récursive
MySQL Server version 5.0.45 n'a pas aimé with:
ERREUR 1064 (42000): Vous avez une erreur dans votre syntaxe SQL; vérifier la manuel qui correspond à votre version du serveur MySQL pour le droit syntaxe à utiliser à côté de « avec tr (id, parent_id) comme (select id, parent_id de t où id = 1 union tout s'à la ligne 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;
Je pense que le mieux est cette d.slave = ANY(all_ids) condition
Les résultats de la connecter par ne peut pas toujours intuitive.
Ci-dessous les requêtes montrent différentes approches pour détecter les cycles commençant par id = 3 pour le graphique sur l'image.
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.
avec nœud id = 3 a deux parents si Oracle parcourt deux cycles dans cet exemple.
(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)
et
(5, 3) -> (3, 4) -> (4, 5)
bord (5, 3) est manquant à partir du résultat de la première requête et le premier cycle. Dans le même bord de temps (5, 3) apparaît dans le résultat de la troisième requête et second cycle à deux reprises.
Pourquoi? Vous pouvez vérifier la description de la logique de détection de cycle dans la réponse fournie par Quassnoi. En anglais, cela signifie simplement que
(1) relier par un cycle détecte si enfant ID de ligne courante fait partie de ID visité jusqu'à présent
(2) avec rec détecte un cycle si ID de ligne courante fait partie des identifiants visité jusqu'à présent
Résultat de la deuxième requête semble le plus naturel bien qu'il y ait and prior id_parent is not null sous-jacente supplémentaire. Dans ce cas,
(3) détecte un cycle si ID de ligne courante fait partie de ID parent visité jusqu'à présent
Toutes ces conditions sont mises en œuvre dans les colonnes CNT1, CNT2, dans CNT3 ci-dessous requête.
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.
Si vous filtre uncomment par CNT1 / cnt2 / CNT3 et de supprimer « cycle de jeu id cycle 1 par défaut 0 » puis requête renverra résultat comme requête correspondante ci-dessus. En d'autres termes vous pouvez éviter cycle clause et mettre en œuvre quelle que soit la logique de détection de cycle, vous trouvez plus intuitive .
Des détails supplémentaires sur les hiérarchies et la détection traversant du cycle se trouvent dans le livre Révélé Oracle SQL .
