PostgreSQL 14 preview - SQL标准增强, 递归(CTE)图式搜索增加广度优先、深度优先语法, 循环语法 - breadth- or depth-first search orders and detect cycles

digoal 2021-01-02

921

作者

digoal

日期

2021-02-01

背景

PostgreSQL 14 SQL标准增强, 图式搜索增加: 广度优先、深度优先语法, 循环语法 - breadth- or depth-first search orders and detect cycles.

with recursive 支持 SEARCH and CYCLE 语法, 增强了PG在图中的使用.

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=3696a600e2292d43c00949ddf0352e4ebb487e5b

```
SEARCH and CYCLE clauses master github/master
author Peter Eisentraut peter@eisentraut.org
Mon, 1 Feb 2021 12:54:59 +0000 (13:54 +0100)
committer Peter Eisentraut peter@eisentraut.org
Mon, 1 Feb 2021 13:32:51 +0000 (14:32 +0100)
commit 3696a600e2292d43c00949ddf0352e4ebb487e5b
tree 11f19c8c9e5757c44b8da02d0e1f7b41f8ec5f13 tree | snapshot
parent bb513b364b4fe31574574c8d0afbb2255268b321 commit | diff
SEARCH and CYCLE clauses

This adds the SQL standard feature that adds the SEARCH and CYCLE
clauses to recursive queries to be able to do produce breadth- or
depth-first search orders and detect cycles. These clauses can be
rewritten into queries using existing syntax, and that is what this
patch does in the rewriter.

Reviewed-by: Vik Fearing vik@postgresfriends.org
Reviewed-by: Pavel Stehule pavel.stehule@gmail.com
Discussion: https://www.postgresql.org/message-id/flat/db80ceee-6f97-9b4a-8ee8-3ba0c58e5be2@2ndquadrant.com
```

另外需要注意的是， cycly默认已经使用了深度优先，所以如果使用了cycle就不要重复使用深度优先语法了。

The cycle path column is computed in the same way as the depth-first ordering column show in the previous section. A query can have both a SEARCH and a CYCLE clause, but a depth-first search specification and a cycle detection specification would create redundant computations, so it's more efficient to just use the CYCLE clause and order by the path column. If breadth-first ordering is wanted, then specifying both SEARCH and CYCLE can be useful.

https://www.postgresql.org/docs/devel/queries-with.html#QUERIES-WITH-RECURSIVE

```
+ [ SEARCH { BREADTH | DEPTH } FIRST BY column_name [, ...] SET search_seq_col_name ]
+ [ CYCLE column_name [, ...] SET cycle_mark_col_name TO cycle_mark_value DEFAULT cycle_mark_default USING cycle_path_col_name ]

TABLE [ ONLY ] table_name [ * ]

@@ -276,6 +278,48 @@ TABLE [ ONLY ] table_name [ * ]
queries that do not use recursion or forward references.

The optional SEARCH clause computes a search
sequence column that can be used for ordering the results of a
recursive query in either breadth-first or depth-first order. The
supplied column name list specifies the row key that is to be used for
keeping track of visited rows. A column named
search_seq_col_name will be added to the result
column list of the WITH query. This column can be
ordered by in the outer query to achieve the respective ordering. See
for examples.
The optional CYCLE clause is used to detect cycles in
recursive queries. The supplied column name list specifies the row key
that is to be used for keeping track of visited rows. A column named
cycle_mark_col_name will be added to the result
column list of the WITH query. This column will be set
to cycle_mark_value when a cycle has been
detected, else to cycle_mark_default.
Furthermore, processing of the recursive union will stop when a cycle has
been detected. cycle_mark_value and
cycle_mark_default must be constants and they
must be coercible to a common data type, and the data type must have an
inequality operator. (The SQL standard requires that they be character
strings, but PostgreSQL does not require that.) Furthermore, a column
named cycle_path_col_name will be added to the
result column list of the WITH query. This column is
used internally for tracking visited rows. See <xref
linkend="queries-with-cycle"/> for examples.
Both the SEARCH and the CYCLE clause
are only valid for recursive WITH queries. The
with_query must be a UNION
(or UNION ALL) of two SELECT (or
equivalent) commands (no nested UNIONs). If both
clauses are used, the column added by the SEARCH clause
appears before the columns added by the CYCLE clause.
```

```
+
+
+ There is built-in syntax to compute a depth- or breadth-first sort column.
+ For example:
+
+
+WITH RECURSIVE search_tree(id, link, data) AS (
+ SELECT t.id, t.link, t.data
+ FROM tree t
+ UNION ALL
+ SELECT t.id, t.link, t.data
+ FROM tree t, search_tree st
+ WHERE t.id = st.link
+) SEARCH DEPTH FIRST BY id SET ordercol
+SELECT * FROM search_tree ORDER BY ordercol;
+
+WITH RECURSIVE search_tree(id, link, data) AS (
+ SELECT t.id, t.link, t.data
+ FROM tree t
+ UNION ALL
+ SELECT t.id, t.link, t.data
+ FROM tree t, search_tree st
+ WHERE t.id = st.link
+) SEARCH BREADTH FIRST BY id SET ordercol
+SELECT * FROM search_tree ORDER BY ordercol;
+
+ This syntax is internally expanded to something similar to the above
+ hand-written forms. The SEARCH clause specifies whether
+ depth- or breadth first search is wanted, the list of columns to track for
+ sorting, and a column name that will contain the result data that can be
+ used for sorting. That column will implicitly be added to the output rows
+ of the CTE.
+

@@ -2305,10 +2338,39 @@ SELECT * FROM search_graph;

There is built-in syntax to simplify cycle detection. The above query can
also be written like this:
+
+WITH RECURSIVE search_graph(id, link, data, depth) AS (
SELECT g.id, g.link, g.data, 1
FROM graph g
UNION ALL
SELECT g.id, g.link, g.data, sg.depth + 1
FROM graph g, search_graph sg
WHERE g.id = sg.link
+) CYCLE id SET is_cycle TO true DEFAULT false USING path
+SELECT * FROM search_graph;
+
and it will be internally rewritten to the above form. The
CYCLE clause specifies first the list of columns to
track for cycle detection, then a column name that will show whether a
cycle has been detected, then two values to use in that column for the yes
and no cases, and finally the name of another column that will track the
path. The cycle and path columns will implicitly be added to the output
rows of the CTE.
The cycle path column is computed in the same way as the depth-first
ordering column show in the previous section.
ordering column show in the previous section. A query can have both a
SEARCH and a CYCLE clause, but a
depth-first search specification and a cycle detection specification would
create redundant computations, so it's more efficient to just use the
CYCLE clause and order by the path column. If
breadth-first ordering is wanted, then specifying both
SEARCH and CYCLE can be useful.

```

例子

```
+-- SEARCH clause
+create temp table graph0( f int, t int, label text );
+insert into graph0 values
+ (1, 2, 'arc 1 -> 2'),
+ (1, 3, 'arc 1 -> 3'),
+ (2, 3, 'arc 2 -> 3'),
+ (1, 4, 'arc 1 -> 4'),
+ (4, 5, 'arc 4 -> 5');
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union all
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t set seq
+select * from search_graph order by seq;
+ f | t | label | seq
+---+---+------------+-------------------
+ 1 | 2 | arc 1 -> 2 | {"(1,2)"}
+ 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"}
+ 1 | 3 | arc 1 -> 3 | {"(1,3)"}
+ 1 | 4 | arc 1 -> 4 | {"(1,4)"}
+ 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"}
+ 2 | 3 | arc 2 -> 3 | {"(2,3)"}
+ 4 | 5 | arc 4 -> 5 | {"(4,5)"}
+(7 rows)
+
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union distinct
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t set seq
+select * from search_graph order by seq;
+ f | t | label | seq
+---+---+------------+-------------------
+ 1 | 2 | arc 1 -> 2 | {"(1,2)"}
+ 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"}
+ 1 | 3 | arc 1 -> 3 | {"(1,3)"}
+ 1 | 4 | arc 1 -> 4 | {"(1,4)"}
+ 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"}
+ 2 | 3 | arc 2 -> 3 | {"(2,3)"}
+ 4 | 5 | arc 4 -> 5 | {"(4,5)"}
+(7 rows)
+
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union all
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search breadth first by f, t set seq
+select * from search_graph order by seq;
+ f | t | label | seq
+---+---+------------+---------
+ 1 | 2 | arc 1 -> 2 | (0,1,2)
+ 1 | 3 | arc 1 -> 3 | (0,1,3)
+ 1 | 4 | arc 1 -> 4 | (0,1,4)
+ 2 | 3 | arc 2 -> 3 | (0,2,3)
+ 4 | 5 | arc 4 -> 5 | (0,4,5)
+ 2 | 3 | arc 2 -> 3 | (1,2,3)
+ 4 | 5 | arc 4 -> 5 | (1,4,5)
+(7 rows)
+
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union distinct
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search breadth first by f, t set seq
+select * from search_graph order by seq;
+ f | t | label | seq
+---+---+------------+---------
+ 1 | 2 | arc 1 -> 2 | (0,1,2)
+ 1 | 3 | arc 1 -> 3 | (0,1,3)
+ 1 | 4 | arc 1 -> 4 | (0,1,4)
+ 2 | 3 | arc 2 -> 3 | (0,2,3)
+ 4 | 5 | arc 4 -> 5 | (0,4,5)
+ 2 | 3 | arc 2 -> 3 | (1,2,3)
+ 4 | 5 | arc 4 -> 5 | (1,4,5)
+(7 rows)
+
+-- various syntax errors
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union all
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search depth first by foo, tar set seq
+select * from search_graph;
+ERROR: search column "foo" not in WITH query column list
+LINE 7: ) search depth first by foo, tar set seq
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union all
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t set label
+select * from search_graph;
+ERROR: search sequence column name "label" already used in WITH query column list
+LINE 7: ) search depth first by f, t set label
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union all
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t, f set seq
+select * from search_graph;
+ERROR: search column "f" specified more than once
+LINE 7: ) search depth first by f, t, f set seq
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union all
+ select * from graph0 g
+ union all
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t set seq
+select * from search_graph order by seq;
+ERROR: with a SEARCH or CYCLE clause, the left side of the UNION must be a SELECT
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union all
+ (select * from graph0 g
+ union all
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t)
+) search depth first by f, t set seq
+select * from search_graph order by seq;
+ERROR: with a SEARCH or CYCLE clause, the right side of the UNION must be a SELECT
+-- test ruleutils and view expansion
+create temp view v_search as
+with recursive search_graph(f, t, label) as (
+ select * from graph0 g
+ union all
+ select g.
+ from graph0 g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t set seq
+select f, t, label from search_graph;
+select pg_get_viewdef('v_search');
+ pg_get_viewdef
+------------------------------------------------
+ WITH RECURSIVE search_graph(f, t, label) AS (+
+ SELECT g.f, +
+ g.t, +
+ g.label +
+ FROM graph0 g +
+ UNION ALL +
+ SELECT g.f, +
+ g.t, +
+ g.label +
+ FROM graph0 g, +
+ search_graph sg +
+ WHERE (g.f = sg.t) +
+ ) SEARCH DEPTH FIRST BY f, t SET seq +
+ SELECT search_graph.f, +
+ search_graph.t, +
+ search_graph.label +
+ FROM search_graph;
+(1 row)
+
+select * from v_search;
+ f | t | label
+---+---+------------
+ 1 | 2 | arc 1 -> 2
+ 1 | 3 | arc 1 -> 3
+ 2 | 3 | arc 2 -> 3
+ 1 | 4 | arc 1 -> 4
+ 4 | 5 | arc 4 -> 5
+ 2 | 3 | arc 2 -> 3
+ 4 | 5 | arc 4 -> 5
+(7 rows)
+
--
-- test cycle detection
--
@@ -701,6 +885,380 @@ select * from search_graph order by path;
5 | 1 | arc 5 -> 1 | t | {"(5,1)","(1,4)","(4,5)","(5,1)"}
(25 rows)

+-- CYCLE clause
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set is_cycle to true default false using path
+select * from search_graph;
+ f | t | label | is_cycle | path
+---+---+------------+----------+-------------------------------------------
+ 1 | 2 | arc 1 -> 2 | f | {"(1,2)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(1,3)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(2,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(1,4)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(4,5)"}
+ 5 | 1 | arc 5 -> 1 | f | {"(5,1)"}
+ 1 | 2 | arc 1 -> 2 | f | {"(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | f | {"(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | f | {"(4,5)","(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | f | {"(4,5)","(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(5,1)","(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | f | {"(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | f | {"(1,4)","(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | f | {"(1,4)","(4,5)","(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | t | {"(1,4)","(4,5)","(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(4,5)","(5,1)","(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | t | {"(4,5)","(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | t | {"(5,1)","(1,4)","(4,5)","(5,1)"}
+ 2 | 3 | arc 2 -> 3 | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
+(25 rows)
+
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union distinct
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set is_cycle to 'Y' default 'N' using path
+select * from search_graph;
+ f | t | label | is_cycle | path
+---+---+------------+----------+-------------------------------------------
+ 1 | 2 | arc 1 -> 2 | N | {"(1,2)"}
+ 1 | 3 | arc 1 -> 3 | N | {"(1,3)"}
+ 2 | 3 | arc 2 -> 3 | N | {"(2,3)"}
+ 1 | 4 | arc 1 -> 4 | N | {"(1,4)"}
+ 4 | 5 | arc 4 -> 5 | N | {"(4,5)"}
+ 5 | 1 | arc 5 -> 1 | N | {"(5,1)"}
+ 1 | 2 | arc 1 -> 2 | N | {"(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | N | {"(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | N | {"(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | N | {"(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | N | {"(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | N | {"(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | N | {"(4,5)","(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | N | {"(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | N | {"(4,5)","(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | N | {"(5,1)","(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | N | {"(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | N | {"(1,4)","(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | N | {"(1,4)","(4,5)","(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | N | {"(1,4)","(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | Y | {"(1,4)","(4,5)","(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | N | {"(4,5)","(5,1)","(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | Y | {"(4,5)","(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | Y | {"(5,1)","(1,4)","(4,5)","(5,1)"}
+ 2 | 3 | arc 2 -> 3 | N | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
+(25 rows)
+
+-- multiple CTEs
+with recursive
+graph(f, t, label) as (
+ values (1, 2, 'arc 1 -> 2'),
+ (1, 3, 'arc 1 -> 3'),
+ (2, 3, 'arc 2 -> 3'),
+ (1, 4, 'arc 1 -> 4'),
+ (4, 5, 'arc 4 -> 5'),
+ (5, 1, 'arc 5 -> 1')
+),
+search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set is_cycle to true default false using path
+select f, t, label from search_graph;
+ f | t | label
+---+---+------------
+ 1 | 2 | arc 1 -> 2
+ 1 | 3 | arc 1 -> 3
+ 2 | 3 | arc 2 -> 3
+ 1 | 4 | arc 1 -> 4
+ 4 | 5 | arc 4 -> 5
+ 5 | 1 | arc 5 -> 1
+ 2 | 3 | arc 2 -> 3
+ 4 | 5 | arc 4 -> 5
+ 5 | 1 | arc 5 -> 1
+ 1 | 4 | arc 1 -> 4
+ 1 | 3 | arc 1 -> 3
+ 1 | 2 | arc 1 -> 2
+ 5 | 1 | arc 5 -> 1
+ 1 | 4 | arc 1 -> 4
+ 1 | 3 | arc 1 -> 3
+ 1 | 2 | arc 1 -> 2
+ 4 | 5 | arc 4 -> 5
+ 2 | 3 | arc 2 -> 3
+ 1 | 4 | arc 1 -> 4
+ 1 | 3 | arc 1 -> 3
+ 1 | 2 | arc 1 -> 2
+ 4 | 5 | arc 4 -> 5
+ 2 | 3 | arc 2 -> 3
+ 5 | 1 | arc 5 -> 1
+ 2 | 3 | arc 2 -> 3
+(25 rows)
+
+-- star expansion
+with recursive a as (
+ select 1 as b
+ union all
+ select * from a
+) cycle b set c to true default false using p
+select * from a;
+ b | c | p
+---+---+-----------
+ 1 | f | {(1)}
+ 1 | t | {(1),(1)}
+(2 rows)
+
+-- search+cycle
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t set seq
+ cycle f, t set is_cycle to true default false using path
+select * from search_graph;
+ f | t | label | seq | is_cycle | path
+---+---+------------+-------------------------------------------+----------+-------------------------------------------
+ 1 | 2 | arc 1 -> 2 | {"(1,2)"} | f | {"(1,2)"}
+ 1 | 3 | arc 1 -> 3 | {"(1,3)"} | f | {"(1,3)"}
+ 2 | 3 | arc 2 -> 3 | {"(2,3)"} | f | {"(2,3)"}
+ 1 | 4 | arc 1 -> 4 | {"(1,4)"} | f | {"(1,4)"}
+ 4 | 5 | arc 4 -> 5 | {"(4,5)"} | f | {"(4,5)"}
+ 5 | 1 | arc 5 -> 1 | {"(5,1)"} | f | {"(5,1)"}
+ 1 | 2 | arc 1 -> 2 | {"(5,1)","(1,2)"} | f | {"(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | {"(5,1)","(1,3)"} | f | {"(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | {"(5,1)","(1,4)"} | f | {"(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | {"(1,2)","(2,3)"} | f | {"(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | {"(1,4)","(4,5)"} | f | {"(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | {"(4,5)","(5,1)"} | f | {"(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | {"(4,5)","(5,1)","(1,2)"} | f | {"(4,5)","(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | {"(4,5)","(5,1)","(1,3)"} | f | {"(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | {"(4,5)","(5,1)","(1,4)"} | f | {"(4,5)","(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | {"(5,1)","(1,2)","(2,3)"} | f | {"(5,1)","(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | {"(5,1)","(1,4)","(4,5)"} | f | {"(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | {"(1,4)","(4,5)","(5,1)"} | f | {"(1,4)","(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | {"(1,4)","(4,5)","(5,1)","(1,2)"} | f | {"(1,4)","(4,5)","(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,3)"} | f | {"(1,4)","(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | {"(1,4)","(4,5)","(5,1)","(1,4)"} | t | {"(1,4)","(4,5)","(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | {"(4,5)","(5,1)","(1,2)","(2,3)"} | f | {"(4,5)","(5,1)","(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | {"(4,5)","(5,1)","(1,4)","(4,5)"} | t | {"(4,5)","(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | {"(5,1)","(1,4)","(4,5)","(5,1)"} | t | {"(5,1)","(1,4)","(4,5)","(5,1)"}
+ 2 | 3 | arc 2 -> 3 | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"} | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
+(25 rows)
+
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) search breadth first by f, t set seq
+ cycle f, t set is_cycle to true default false using path
+select * from search_graph;
+ f | t | label | seq | is_cycle | path
+---+---+------------+---------+----------+-------------------------------------------
+ 1 | 2 | arc 1 -> 2 | (0,1,2) | f | {"(1,2)"}
+ 1 | 3 | arc 1 -> 3 | (0,1,3) | f | {"(1,3)"}
+ 2 | 3 | arc 2 -> 3 | (0,2,3) | f | {"(2,3)"}
+ 1 | 4 | arc 1 -> 4 | (0,1,4) | f | {"(1,4)"}
+ 4 | 5 | arc 4 -> 5 | (0,4,5) | f | {"(4,5)"}
+ 5 | 1 | arc 5 -> 1 | (0,5,1) | f | {"(5,1)"}
+ 1 | 2 | arc 1 -> 2 | (1,1,2) | f | {"(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | (1,1,3) | f | {"(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | (1,1,4) | f | {"(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | (1,2,3) | f | {"(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | (1,4,5) | f | {"(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | (1,5,1) | f | {"(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | (2,1,2) | f | {"(4,5)","(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | (2,1,3) | f | {"(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | (2,1,4) | f | {"(4,5)","(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | (2,2,3) | f | {"(5,1)","(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | (2,4,5) | f | {"(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | (2,5,1) | f | {"(1,4)","(4,5)","(5,1)"}
+ 1 | 2 | arc 1 -> 2 | (3,1,2) | f | {"(1,4)","(4,5)","(5,1)","(1,2)"}
+ 1 | 3 | arc 1 -> 3 | (3,1,3) | f | {"(1,4)","(4,5)","(5,1)","(1,3)"}
+ 1 | 4 | arc 1 -> 4 | (3,1,4) | t | {"(1,4)","(4,5)","(5,1)","(1,4)"}
+ 2 | 3 | arc 2 -> 3 | (3,2,3) | f | {"(4,5)","(5,1)","(1,2)","(2,3)"}
+ 4 | 5 | arc 4 -> 5 | (3,4,5) | t | {"(4,5)","(5,1)","(1,4)","(4,5)"}
+ 5 | 1 | arc 5 -> 1 | (3,5,1) | t | {"(5,1)","(1,4)","(4,5)","(5,1)"}
+ 2 | 3 | arc 2 -> 3 | (4,2,3) | f | {"(1,4)","(4,5)","(5,1)","(1,2)","(2,3)"}
+(25 rows)
+
+-- various syntax errors
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle foo, tar set is_cycle to true default false using path
+select * from search_graph;
+ERROR: cycle column "foo" not in WITH query column list
+LINE 7: ) cycle foo, tar set is_cycle to true default false using pa...
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set is_cycle to true default 55 using path
+select * from search_graph;
+ERROR: CYCLE types boolean and integer cannot be matched
+LINE 7: ) cycle f, t set is_cycle to true default 55 using path
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set is_cycle to point '(1,1)' default point '(0,0)' using path
+select * from search_graph;
+ERROR: could not identify an equality operator for type point
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set label to true default false using path
+select * from search_graph;
+ERROR: cycle mark column name "label" already used in WITH query column list
+LINE 7: ) cycle f, t set label to true default false using path
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set is_cycle to true default false using label
+select * from search_graph;
+ERROR: cycle path column name "label" already used in WITH query column list
+LINE 7: ) cycle f, t set is_cycle to true default false using label
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set foo to true default false using foo
+select * from search_graph;
+ERROR: cycle mark column name and cycle path column name are the same
+LINE 7: ) cycle f, t set foo to true default false using foo
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t, f set is_cycle to true default false using path
+select * from search_graph;
+ERROR: cycle column "f" specified more than once
+LINE 7: ) cycle f, t, f set is_cycle to true default false using pat...
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t set foo
+ cycle f, t set foo to true default false using path
+select * from search_graph;
+ERROR: search sequence column name and cycle mark column name are the same
+LINE 7: ) search depth first by f, t set foo
+ ^
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.
+ from graph g, search_graph sg
+ where g.f = sg.t
+) search depth first by f, t set foo
+ cycle f, t set is_cycle to true default false using foo
+select * from search_graph;
+ERROR: search_sequence column name and cycle path column name are the same
+LINE 7: ) search depth first by f, t set foo
+ ^
+-- test ruleutils and view expansion
+create temp view v_cycle as
+with recursive search_graph(f, t, label) as (
+ select * from graph g
+ union all
+ select g.*
+ from graph g, search_graph sg
+ where g.f = sg.t
+) cycle f, t set is_cycle to true default false using path
+select f, t, label from search_graph;
+select pg_get_viewdef('v_cycle');
+ pg_get_viewdef
+--------------------------------------------------------------------
+ WITH RECURSIVE search_graph(f, t, label) AS ( +
+ SELECT g.f, +
+ g.t, +
+ g.label +
+ FROM graph g +
+ UNION ALL +
+ SELECT g.f, +
+ g.t, +
+ g.label +
+ FROM graph g, +
+ search_graph sg +
+ WHERE (g.f = sg.t) +
+ ) CYCLE f, t SET is_cycle TO true DEFAULT false USING path+
+ SELECT search_graph.f, +
+ search_graph.t, +
+ search_graph.label +
+ FROM search_graph;
+(1 row)
+
+select * from v_cycle;
+ f | t | label
+---+---+------------
+ 1 | 2 | arc 1 -> 2
+ 1 | 3 | arc 1 -> 3
+ 2 | 3 | arc 2 -> 3
+ 1 | 4 | arc 1 -> 4
+ 4 | 5 | arc 4 -> 5
+ 5 | 1 | arc 5 -> 1
+ 1 | 2 | arc 1 -> 2
+ 1 | 3 | arc 1 -> 3
+ 1 | 4 | arc 1 -> 4
+ 2 | 3 | arc 2 -> 3
+ 4 | 5 | arc 4 -> 5
+ 5 | 1 | arc 5 -> 1
+ 1 | 2 | arc 1 -> 2
+ 1 | 3 | arc 1 -> 3
+ 1 | 4 | arc 1 -> 4
+ 2 | 3 | arc 2 -> 3
+ 4 | 5 | arc 4 -> 5
+ 5 | 1 | arc 5 -> 1
+ 1 | 2 | arc 1 -> 2
+ 1 | 3 | arc 1 -> 3
+ 1 | 4 | arc 1 -> 4
+ 2 | 3 | arc 2 -> 3
+ 4 | 5 | arc 4 -> 5
+ 5 | 1 | arc 5 -> 1
+ 2 | 3 | arc 2 -> 3
+(25 rows)
+
```

文章转载自digoal，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

PostgreSQL 14 preview - SQL标准增强, 递归(CTE)图式搜索增加广度优先、深度优先语法, 循环语法 - breadth- or depth-first search orders and detect cycles

作者

日期

标签

背景

PostgreSQL 许愿链接

9.9元购买3个月阿里云RDS PostgreSQL实例

PostgreSQL 解决方案集合

德哥 / digoal's github - 公益是一辈子的事.

评论