Hello,
At the beginning I would like to agree with that the problem is
iterative rather then recursive one. However,
On 2018-05-01 14:15, R Smith wrote:
That depends on what you mean by "Could this be achieved in SQLite?".
There is no query (in any SQL engine) that can depend on a sub-query
that is itself dependent on the outcome of the main query. This is what
makes recursion beautiful, but then there is also no CTE (or other query
in any SQL engine) that can recurse over multiple states of data (i.e.
query data in one single query to reflect results from both before and
after a delete in the source table), nor can a CTE be updated or deleted
from, its data must persist atomically (with some exceptions when using
non-deterministic functions, like random).
These are not so much "inabilities" of SQL engines, but more due to
explicit SQL and set-algebra rules.
So this is not possible in a single query.
This is possible in a single query, though not directly. CTE are very
flexible. CTE can be used to write your own DBMS, which is able to store
tables and make a recursive DELETE. Then: (1) copy ``points'' table to
SQL-one-query-written DBMS; (2) do a recursive DELETE; (3) output a
final table to a proper DBMS -- SQLite.
As Simon has written, the problem can be presented as an image
processing problem. Further, image is a 2D Cartesian product of X/Y
coordinates with points being relations between Xs and Ys -- a classic
relational problem. So, at the beginning, my solution tries to produce
two tables: xaxis/yaxis from a n-to-n relation ``points''. Each
``*axis'' table contains id (coordinate) of a row/column and a number of
points lying on it. Next, let's remove rows/columns having a number of
points less then given values until all remaining rows/columns (even if
0, at the border case) have enough points. Parameters (nX, nY) are
passed by ``params'' CTE:
Let's generate 100 random points:
CREATE TABLE points AS WITH cte(x,y,n) AS (SELECT (random() % 10 + 10) %
10 + 1, (random() % 10 + 10) % 10 + 1, 1 UNION ALL SELECT (random() % 10
+ 10) % 10 + 1, (random() % 10 + 10) % 10 + 1, n + 1 FROM cte WHERE n <
100) SELECT x, y FROM cte;
The preceding statement creates table ``points(x, y)'' containing 100
points with coordinates <1;10> -- points can be repeated -- it does not
matter.
Now, let's SELECT x, y FROM points WHERE nX = 6 AND nY = 8:
======
WITH
params(nx, ny) AS (SELECT 6, 8),
main(elem, rest) AS (
SELECT NULL, (
WITH
state(clock, points, xaxis, yaxis, nxmin, nxmax, nymin, nymax) AS (
SELECT
0,
(SELECT GROUP_CONCAT(x || ' ' || y) FROM points),
(SELECT GROUP_CONCAT(x || ' ' || n) FROM (SELECT x,
COUNT(x) n FROM points GROUP BY x)),
(SELECT GROUP_CONCAT(y || ' ' || n) FROM (SELECT y,
COUNT(y) n FROM points GROUP BY y)),
(SELECT MIN(n) FROM (SELECT x, COUNT(x) n FROM points GROUP
BY x)),
(SELECT MAX(n) FROM (SELECT x, COUNT(x) n FROM points GROUP
BY x)),
(SELECT MIN(n) FROM (SELECT y, COUNT(y) n FROM points GROUP
BY y)),
(SELECT MAX(n) FROM (SELECT y, COUNT(y) n FROM points GROUP
BY y))
UNION ALL
SELECT
(clock + 1) % 3,
CASE clock WHEN 0 THEN
(SELECT GROUP_CONCAT(x || ' ' || y) FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.points
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','), 0)
- 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(elem AS INTEGER) x,
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) y
FROM cte WHERE elem IS NOT NULL
)
WHERE (x NOT IN (
SELECT x FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.xaxis
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','),
0) - 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(elem AS INTEGER) x,
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
FROM cte WHERE elem IS NOT NULL
) WHERE n < (SELECT nx FROM params)
)) AND (y NOT IN (
SELECT y FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.yaxis
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','),
0) - 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(elem AS INTEGER) y,
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
FROM cte WHERE elem IS NOT NULL
) WHERE n < (SELECT ny FROM params)
))) ELSE points END,
CASE clock WHEN 1 THEN
(SELECT GROUP_CONCAT(x || ' ' || n) FROM (SELECT x,
COUNT(x) n FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.points
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','), 0)
- 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(elem AS INTEGER) x
FROM cte WHERE elem IS NOT NULL
) GROUP BY x)) ELSE xaxis END,
CASE clock WHEN 1 THEN
(SELECT GROUP_CONCAT(y || ' ' || n) FROM (SELECT y,
COUNT(y) n FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.points
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','), 0)
- 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) y
FROM cte WHERE elem IS NOT NULL
) GROUP BY y)) ELSE yaxis END,
CASE clock WHEN 2 THEN
(SELECT MIN(n) FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.xaxis
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','), 0)
- 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
FROM cte WHERE elem IS NOT NULL
)) ELSE nxmin END,
CASE clock WHEN 2 THEN
(SELECT MAX(n) FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.xaxis
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','), 0)
- 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
FROM cte WHERE elem IS NOT NULL
)) ELSE nxmax END,
CASE clock WHEN 2 THEN
(SELECT MIN(n) FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.yaxis
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','), 0)
- 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
FROM cte WHERE elem IS NOT NULL
)) ELSE nymin END,
CASE clock WHEN 2 THEN
(SELECT MAX(n) FROM (
WITH
cte(elem, rest) AS (
SELECT NULL, state.yaxis
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','), 0)
- 1, LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM cte
WHERE rest IS NOT NULL
)
SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
FROM cte WHERE elem IS NOT NULL
)) ELSE nymax END
FROM state
WHERE (SELECT nx FROM params) BETWEEN nxmin + 1 AND nxmax OR
(SELECT ny FROM params) BETWEEN nymin + 1 AND nymax
) SELECT points FROM state WHERE nxmin >= (SELECT nx FROM
params) AND nymin >= (SELECT ny FROM params)
)
UNION ALL
SELECT
SUBSTR(rest, 1, IFNULL(NULLIF(INSTR(rest, ','), 0) - 1,
LENGTH(rest))),
SUBSTR(rest, NULLIF(INSTR(rest, ','), 0) + 1)
FROM main
WHERE rest IS NOT NULL
)
SELECT
CAST(elem AS INTEGER) x,
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) y
FROM main WHERE elem IS NOT NULL;
======
If you have received an empty set then you will have to decrease nX/nY,
append more points or generate new ``points'' table.
... just for fun.
-- best regards
Cezary H. Noweta
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
