Discussion :

[Kropernic]

Hello,

On m'a posé une colle ce matin. Au départ, je pensais que ça allait être simple mais en fait, en traitant le problème, pas tant que ça...

Dans une table contenant des éléments d'un réseau (conduites de distribution d'eau par exemple), il y a notamment des colonnes IN_FID et OUT_FID qui contiennent les identifiants des éléments auxquels l'élément est connecté.

Voici un exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
WITH A (ID, IN_FID, OUT_FID) AS (  SELECT 1, 1234, 9876   UNION ALL
  SELECT 2, 2345, 8765   UNION ALL
  SELECT 3, 3545, 1234   UNION ALL
  SELECT 4, 6574, 3545 
),
T (ID, IN_FID, OUT_FID, LVL) AS (
  SELECT  ID, IN_FID, OUT_FID, 1
  FROM    A
  WHERE   IN_FID = 1234
  UNION ALL
  SELECT  A.ID, A.IN_FID, A.OUT_FID, T.LVL + 1
  FROM    A 
            INNER JOIN T
				ON  A.IN_FID <> 1234
				AND	A.ID <> T.ID
				AND (
					A.IN_FID = T.IN_FID OR
					A.IN_FID = T.OUT_FID OR
					A.OUT_FID = T.IN_FID OR
					A.OUT_FID = T.OUT_FID
					)
)
 
 
SELECT * FROM T

Particularité aussi, les connexions se font n'importe comment. Ce n'est pas toujours OUT_FID qui pointe vers IN_FID. Ca peut être l'inverse comme ça peut pointer vers la même colonne aussi (ça dépend du sens dans lequel l'utilisateur dessine l'élément du réseau qu'on m'a dit).

Mais avec cette requête, on a bien sûr un cycle. Il faudrait en fait pouvoir exclure une ligne qui a déjà été prise dans T.

Enfin c'est mon analyse du problème. Il y a peut-être moyen de mieux faire.

Perso, je sèche... Auriez-vous une idée ?

[aieeeuuuuu]

Bonjour,

Pour éviter les cycles dans une requête récursive, je ne connais pas d'autres solution que de stocker le "chemin" afin de vérifier à chaque récursion si on n'est pas déjà passé.

donc quelque chose comme ceci par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
WITH A (ID, IN_FID, OUT_FID) AS (  SELECT 1, 1234, 9876   UNION ALL
  SELECT 2, 2345, 8765   UNION ALL
  SELECT 3, 3545, 1234   UNION ALL
  SELECT 4, 6574, 3545 
),
T (ID, IN_FID, OUT_FID, LVL, chemin) AS (
  SELECT  ID, IN_FID, OUT_FID, 1, CAST(CONCAT('[',ID, ']') AS VARCHAR(MAX))
  FROM    A
  WHERE   IN_FID = 1234
  UNION ALL
  SELECT  A.ID, A.IN_FID, A.OUT_FID, T.LVL + 1, CAST(CONCAT(T.chemin,'[',A.ID, ']') AS varchar(max))
  FROM    A 
            INNER JOIN T
				ON  A.IN_FID <> 1234
				AND	A.ID <> T.ID
				AND (
					A.IN_FID = T.IN_FID OR
					A.IN_FID = T.OUT_FID OR
					A.OUT_FID = T.IN_FID OR
					A.OUT_FID = T.OUT_FID
					)
	WHERE t.chemin NOT LIKE CONCAT('%[', A.ID, ']%')
)
 
 
SELECT * FROM T

[Kropernic]

Nice !

Je ne connaissais pas encore l'astuce du "chemin".

Ca fait plaisir de "revoir les mêmes têtes" qu'à l'époque où je fréquentais ce forum plus régulièrement

Un grand merci !

[JeitEmgie]

Autre méthode pour détecter un cycle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
with data as (    select 1 as parent_id, 2 as child_id from dual
    union all
    select 2 as parent_id, 3 as child_id from dual
    union all
    select 3 as parent_id, 4 as child_id from dual
    union all
    select 3 as parent_id, 9 as child_id from dual
    union all
    select 4 as parent_id, 5 as child_id from dual
    union all
    select 5 as parent_id, 6 as child_id from dual
    union all
    select 6 as parent_id, 7 as child_id from dual
    union all
    select 7 as parent_id, 8 as child_id from dual
    union all
    select 8 as parent_id, 1 as child_id from dual
),
cte(lvl, pid, cid, gcid, is_cycle) as (
    select 1 as lvl, d.parent_id, d.child_id, cd.child_id as gcid, 0 as is_cycle from data d
        join data cd on cd.parent_id = d.child_id
        where d.parent_id = 1
    union all
    select lvl+1, cd.parent_id, cd.child_id, cccd.child_id, case when cd.child_id = cccd.child_id then 1 else 0 end
    from cte c
        join data cd on c.cid = cd.parent_id
        join data ccd on c.gcid = ccd.parent_id
        join data cccd on ccd.child_id = cccd.parent_id
    where c.cid <> c.gcid
)
select * from cte ;

LVL	PID	CID	GCID	IS_CYCLE
1	1	2	3	0
2	2	3	5	0
3	3	9	7	0
3	3	4	7	0
4	4	5	1	0
5	5	6	3	0
6	6	7	5	0
7	7	8	7	0
8	8	1	1	1

(méthode de D. Knuth pour détecter les cycles dans une liste chaînée)

[escartefigue]

Nice !

Je ne connaissais pas encore l'astuce du "chemin".

Ca fait plaisir de "revoir les mêmes têtes" qu'à l'époque où je fréquentais ce forum plus régulièrement

Un grand merci !

Ce plaisir aurait du être plus démonstratif en attribuant un vote positif à la réponse fournie, surtout quand celle-ci est pertinente
Ah la la cette ingratitude...

[SQLpro]

Ce plaisir aurait du être plus démonstratif en attribuant un vote positif à la réponse fournie, surtout quand celle-ci est pertinente
Ah la la cette ingratitude...

Notre ami Kropernic, que j'ai bien connu à Bruxelles est Belge ! Peut être ceci explique cela !!!

[aieeeuuuuu]

(méthode de D. Knuth pour détecter les cycles dans une liste chaînée)

Je pense qu'il y a une erreur d'implémentation de la méthode en question (il n'y pas de recherche de longueur de cycle)

Si vous supprimez la dernière ligne 8-->1 (plus de cycle), le résultat est faux
Il est faux également si vous modifiez la même ligne pour reprendre en "milieu de chemin" (par exemple 8-->5)

Il y a aussi probablement un erreur avec la requête que j'ai proposée : le choix des crochets est assez malheureux, car interprété par le LIKE comme caractère d'échappement.
Il faudrait soit utiliser autre chose (comme des parenthèses par exemple), soit spécifier un autre caractère d’échappement pour le like ( LIKE ... ESCAPE '\').

[JeitEmgie]

Non, mais j’aurais dû être plus clair sur le but de ce query qui n’est que de détecter la présence d’un cycle, et non de remplacer le query original.

Normalement on met la condition du CASE dans un WHERE sur le CTE, et pas de résultat == pas de cycle.
J’ai ajouté des champs inutiles dans le CTE pour illustrer comment fonctionne la technique originale de D. Knuth qui consiste à se balader avec la « petite-fille » (gcid == grand-child id) en montrant tous les résultats en cas de cycle.
C’était juste une illustration d’une technique venant d’un raisonnement « procédural » en termes purement relationnels par opposition à « l’astuce » de la recherche dans une string contenant le chemin parcouru.

[Kropernic]

Je repasse voir l'implémentation de la détection de cycle et je vois qu'on parle de moi^^

Ce plaisir aurait du être plus démonstratif en attribuant un vote positif à la réponse fournie, surtout quand celle-ci est pertinente
Ah la la cette ingratitude...

C'est en effet un oubli et c'est corrigé.

Notre ami Kropernic, que j'ai bien connu à Bruxelles est Belge ! Peut être ceci explique cela !!!