One can use UNION DISTINCT as an easy way of avoiding cycles when traversing a graph with a CTE:
But often one needs to know more than edges, for example
and here DISTINCT no longer works.
SQL Standard specifies that a CTE can have a CYCLE clause as
- <cycle column list> is a subset of columns that the CTE returns
- <cycle mark column> is a new column, generated on the fly, its value for any particular row being <cycle mark value> if there's a cycle and <non-cycle mark value> if there's no cycle
- <path column> is an ARRAY where the path is being accumulated
While in the standard all clauses in the CYCLE are mandatory, we'll relax this grammar to allow only CYCLE <cycle column list>.
This task is about implementing optional CYCLE <cycle column list> clause after the recursive CTE definition.
There is a simple way to implement it by changing CTE's UNION ALL or UNION DISTINCT operator to enforce distinct-ness only over <cycle column list> columns, not over all columns that CTE returns.
The example from above would look like
Note that it doesn't matter whether the CTE uses UNION ALL or UNION DISTINCT anymore. UNION ALL means "all rows, but without cycles", which is exactly what we'll do. And UNION DISTINCT means all rows should be different, which, again, is what will happen — as we'll enforce uniqueness over a subset of columns, complete rows will automatically be all different.