8000 Adjust cycle detection examples and tests · postgrespro/postgres@3fb6765 · GitHub
[go: up one dir, main page]
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
  • doc/src/sgml
  • src/test/regress
    • expected
      • < 8000 div style="grid-area:spacer;display:flex">
        with.out
  • sql

    • 3 files changed

    +83
    -83
    lines changed

    ‎doc/src/sgml/queries.sgml

    Lines changed: 13 additions & 13 deletions
    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

    Lines changed: 62 additions & 62 deletions
    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

    Lines changed: 8 additions & 8 deletions
    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)
    0