Skip to content

Commit 3fb6765

Browse files
peterepetere
committed
Adjust cycle detection examples and tests
Adjust the existing cycle detection example and test queries to put the cycle column before the path column. This is mainly because the SQL-standard CYCLE clause puts them in that order, and so if we added that feature that would make the sequence of examples more consistent and easier to follow. Discussion: https://www.postgresql.org/message-id/c5603982-0088-7f14-0caa-fdcd0c837b57@2ndquadrant.com
1 parent 88ea7a1 commit 3fb6765

File tree

3 files changed

+83
-83
lines changed

3 files changed

+83
-83
lines changed

‎doc/src/sgml/queries.sgml

+13-13
Original file line numberDiff line numberDiff line change
@@ -2144,20 +2144,20 @@ SELECT * FROM search_graph;
21442144
<literal>UNION ALL</literal> to <literal>UNION</literal> would not eliminate the looping.
21452145
Instead we need to recognize whether we have reached the same row again
21462146
while following a particular path of links. We add two columns
2147-
<structfield>path</structfield> and <structfield>cycle</structfield> to the loop-prone query:
2147+
<structfield>is_cycle</structfield> and <structfield>path</structfield> to the loop-prone query:
21482148

21492149
<programlisting>
2150-
WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
2150+
WITH RECURSIVE search_graph(id, link, data, depth, is_cycle, path) AS (
21512151
SELECT g.id, g.link, g.data, 1,
2152-
ARRAY[g.id],
2153-
false
2152+
false,
2153+
ARRAY[g.id]
21542154
FROM graph g
21552155
UNION ALL
21562156
SELECT g.id, g.link, g.data, sg.depth + 1,
2157-
path || g.id,
2158-
g.id = ANY(path)
2157+
g.id = ANY(path),
2158+
path || g.id
21592159
FROM graph g, search_graph sg
2160-
WHERE g.id = sg.link AND NOT cycle
2160+
WHERE g.id = sg.link AND NOT is_cycle
21612161
)
21622162
SELECT * FROM search_graph;
21632163
</programlisting>
@@ -2172,17 +2172,17 @@ SELECT * FROM search_graph;
21722172
compare fields <structfield>f1</structfield> and <structfield>f2</structfield>:
21732173

21742174
<programlisting>
2175-
WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
2175+
WITH RECURSIVE search_graph(id, link, data, depth, is_cycle, path) AS (
21762176
SELECT g.id, g.link, g.data, 1,
2177-
ARRAY[ROW(g.f1, g.f2)],
2178-
false
2177+
false,
2178+
ARRAY[ROW(g.f1, g.f2)]
21792179
FROM graph g
21802180
UNION ALL
21812181
SELECT g.id, g.link, g.data, sg.depth + 1,
2182-
path || ROW(g.f1, g.f2),
2183-
ROW(g.f1, g.f2) = ANY(path)
2182+
ROW(g.f1, g.f2) = ANY(path),
2183+
path || ROW(g.f1, g.f2)
21842184
FROM graph g, search_graph sg
2185-
WHERE g.id = sg.link AND NOT cycle
2185+
WHERE g.id = sg.link AND NOT is_cycle
21862186
)
21872187
SELECT * FROM search_graph;
21882188
</programlisting>

‎src/test/regress/expected/with.out

+62-62
Original file line numberDiff line numberDiff line change
@@ -579,79 +579,79 @@ insert into graph values
579579
(1, 4, 'arc 1 -> 4'),
580580
(4, 5, 'arc 4 -> 5'),
581581
(5, 1, 'arc 5 -> 1');
582-
with recursive search_graph(f, t, label, path, cycle) as (
583-
select *, array[row(g.f, g.t)], false from graph g
582+
with recursive search_graph(f, t, label, is_cycle, path) as (
583+
select *, false, array[row(g.f, g.t)] from graph g
584584
union all
585-
select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
585+
select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
586586
from graph g, search_graph sg
587-
where g.f = sg.t and not cycle
587+
where g.f = sg.t and not is_cycle
588588
)
589589
select * from search_graph;
590-
f | t | label | path | cycle
591-
---+---+------------+-------------------------------------------+-------
592-
1 | 2 | arc 1 -> 2 | {"(1,2)"} | f
593-
1 | 3 | arc 1 -> 3 | {"(1,3)"} | f
594-
2 | 3 | arc 2 -> 3 | {"(2,3)"} | f
595-
1 | 4 | arc 1 -> 4 | {"(1,4)"} | f
596-
4 | 5 | arc 4 -> 5 | {"(4,5)"} | f
597-
5 | 1 | arc 5 -> 1 | {"(5,1)"} | f
598-
1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"} | f
599-
1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"} | f
600-
1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"} | f
601-
2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} | f
602-
4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} | f
603-
5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"} | f
604-
1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"} | f
605-
1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"} | f
606-
1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"} | f
607-
2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"} | f
608-
4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"} | f
609-
5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"} | f
610-
1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"} | f
611-
1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"} | f
612-
1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"} | t
613-
2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"} | f
614-
4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"} | t
615-
5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t
616-
2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f
590+
f | t | label | is_cycle | path
591+
---+---+------------+----------+-------------------------------------------
592+
1 | 2 | arc 1 -> 2 | f | {"(1,2)"}
593+
1 | 3 | arc 1 -> 3 | f | {"(1,3)"}
594+
2 | 3 | arc 2 -> 3 | f | {"(2,3)"}
595+
1 | 4 | arc 1 -> 4 | f | {"(1,4)"}
596+
4 | 5 | arc 4 -> 5 | f | {"(4,5)"}
597+
5 | 1 | arc 5 -> 1 | f | {"(5,1)"}
598+
1 | 2 | arc 1 -> 2 | f | {"(5,1)","(1,2)"}
599+
1 | 3 | arc 1 -> 3 | f | {"(5,1)","(1,3)"}
600+
1 | 4 | arc 1 -> 4 | f | {"(5,1)","(1,4)"}
601+
2 | 3 | arc 2 -> 3 | f | {"(1,2)","(2,3)"}
602+
4 | 5 | arc 4 -> 5 | f | {"(1,4)","(4,5)"}
603+
5 | 1 | arc 5 -> 1 | f | {"(4,5)","(5,1)"}
604+
1 | 2 | arc 1 -> 2 | f | {"(4,5)","(5,1)","(1,2)"}
605+
1 | 3 | arc 1 -> 3 | f | {"(4,5)","(5,1)","(1,3)"}
606+
1 | 4 | arc 1 -> 4 | f | {"(4,5)","(5,1)","(1,4)"}
607+
2 | 3 | arc 2 -> 3 | f | {"(5,1)","(1,2)","(2,3)"}
608+
4 | 5 | arc 4 -> 5 | f | {"(5,1)","(1,4)","(4,5)"}
609+
5 | 1 | arc 5 -> 1 | f | {"(1,4)","(4,5)","(5,1)"}
610+
1 | 2 | arc 1 -> 2 | f | {"(1,4)","(4,5)","(5,1)","(1,2)"}
611+
1 | 3 | arc 1 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,3)"}
612+
1 | 4 | arc 1 -> 4 | t | {"(1,4)","(4,5)","(5,1)","(1,4)"}
613+
2 | 3 | arc 2 -> 3 | f | {"(4,5)","(5,1)","(1,2)","(2,3)"}
614+
4 | 5 | arc 4 -> 5 | t | {"(4,5)","(5,1)","(1,4)","(4,5)"}
615+
5 | 1 | arc 5 -> 1 | t | {"(5,1)","(1,4)","(4,5)","(5,1)"}
616+
2 | 3 | arc 2 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
617617
(25 rows)
618618

619619
-- ordering by the path column has same effect as SEARCH DEPTH FIRST
620-
with recursive search_graph(f, t, label, path, cycle) as (
621-
select *, array[row(g.f, g.t)], false from graph g
620+
with recursive search_graph(f, t, label, is_cycle, path) as (
621+
select *, false, array[row(g.f, g.t)] from graph g
622622
union all
623-
select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
623+
select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
624624
from graph g, search_graph sg
625-
where g.f = sg.t and not cycle
625+
where g.f = sg.t and not is_cycle
626626
)
627627
select * from search_graph order by path;
628-
f | t | label | path | cycle
629-
---+---+------------+-------------------------------------------+-------
630-
1 | 2 | arc 1 -> 2 | {"(1,2)"} | f
631-
2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} | f
632-
1 | 3 | arc 1 -> 3 | {"(1,3)"} | f
633-
1 | 4 | arc 1 -> 4 | {"(1,4)"} | f
634-
4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} | f
635-
5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"} | f
636-
1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"} | f
637-
2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f
638-
1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"} | f
639-
1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"} | t
640-
2 | 3 | arc 2 -> 3 | {"(2,3)"} | f
641-
4 | 5 | arc 4 -> 5 | {"(4,5)"} | f
642-
5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"} | f
643-
1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"} | f
644-
2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"} | f
645-
1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"} | f
646-
1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"} | f
647-
4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"} | t
648-
5 | 1 | arc 5 -> 1 | {"(5,1)"} | f
649-
1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"} | f
650-
2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"} | f
651-
1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"} | f
652-
1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"} | f
653-
4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"} | f
654-
5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t
628+
f | t | label | is_cycle | path
629+
---+---+------------+----------+-------------------------------------------
630+
1 | 2 | arc 1 -> 2 | f | {"(1,2)"}
631+
2 | 3 | arc 2 -> 3 | f | {"(1,2)","(2,3)"}
632+
1 | 3 | arc 1 -> 3 | f | {"(1,3)"}
633+
1 | 4 | arc 1 -> 4 | f | {"(1,4)"}
634+
4 | 5 | arc 4 -> 5 | f | {"(1,4)","(4,5)"}
635+
5 | 1 | arc 5 -> 1 | f | {"(1,4)","(4,5)","(5,1)"}
636+
1 | 2 | arc 1 -> 2 | f | {"(1,4)","(4,5)","(5,1)","(1,2)"}
637+
2 | 3 | arc 2 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
638+
1 | 3 | arc 1 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,3)"}
639+
1 | 4 | arc 1 -> 4 | t | {"(1,4)","(4,5)","(5,1)","(1,4)"}
640+
2 | 3 | arc 2 -> 3 | f | {"(2,3)"}
641+
4 | 5 | arc 4 -> 5 | f | {"(4,5)"}
642+
5 | 1 | arc 5 -> 1 | f | {"(4,5)","(5,1)"}
643+
1 | 2 | arc 1 -> 2 | f | {"(4,5)","(5,1)","(1,2)"}
644+
2 | 3 | arc 2 -> 3 | f | {"(4,5)","(5,1)","(1,2)","(2,3)"}
645+
1 | 3 | arc 1 -> 3 | f | {"(4,5)","(5,1)","(1,3)"}
646+
1 | 4 | arc 1 -> 4 | f | {"(4,5)","(5,1)","(1,4)"}
647+
4 | 5 | arc 4 -> 5 | t | {"(4,5)","(5,1)","(1,4)","(4,5)"}
648+
5 | 1 | arc 5 -> 1 | f | {"(5,1)"}
649+
1 | 2 | arc 1 -> 2 | f | {"(5,1)","(1,2)"}
650+
2 | 3 | arc 2 -> 3 | f | {"(5,1)","(1,2)","(2,3)"}
651+
1 | 3 | arc 1 -> 3 | f | {"(5,1)","(1,3)"}
652+
1 | 4 | arc 1 -> 4 | f | {"(5,1)","(1,4)"}
653+
4 | 5 | arc 4 -> 5 | f | {"(5,1)","(1,4)","(4,5)"}
654+
5 | 1 | arc 5 -> 1 | t | {"(5,1)","(1,4)","(4,5)","(5,1)"}
655655
(25 rows)
656656

657657
--

‎src/test/regress/sql/with.sql

+8-8
Original file line numberDiff line numberDiff line change
@@ -308,22 +308,22 @@ insert into graph values
308308
(4, 5, 'arc 4 -> 5'),
309309
(5, 1, 'arc 5 -> 1');
310310

311-
with recursive search_graph(f, t, label, path, cycle) as (
312-
select *, array[row(g.f, g.t)], false from graph g
311+
with recursive search_graph(f, t, label, is_cycle, path) as (
312+
select *, false, array[row(g.f, g.t)] from graph g
313313
union all
314-
select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
314+
select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
315315
from graph g, search_graph sg
316-
where g.f = sg.t and not cycle
316+
where g.f = sg.t and not is_cycle
317317
)
318318
select * from search_graph;
319319

320320
-- ordering by the path column has same effect as SEARCH DEPTH FIRST
321-
with recursive search_graph(f, t, label, path, cycle) as (
322-
select *, array[row(g.f, g.t)], false from graph g
321+
with recursive search_graph(f, t, label, is_cycle, path) as (
322+
select *, false, array[row(g.f, g.t)] from graph g
323323
union all
324-
select g.*, path || row(g.f, g.t), row(g.f, g.t) = any(path)
324+
select g.*, row(g.f, g.t) = any(path), path || row(g.f, g.t)
325325
from graph g, search_graph sg
326-
where g.f = sg.t and not cycle
326+
where g.f = sg.t and not is_cycle
327327
)
328328
select * from search_graph order by path;
329329

0 commit comments

Comments
 (0)