Re: [sqlite] probably recursive?

[E.Pasma]

Cezary H. Noweta wrote:


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;



and


CREATE TABLE xaxis AS SELECT x, COUNT(x) AS n FROM points GROUP BY x;
CREATE TABLE yaxis AS SELECT y, COUNT(y) AS n FROM points GROUP BY y;

For example for two points (1,2); (1,-4)

xaxis(x, n):
1 2

yaxis(y, n):
-4 1
2 1

xaxis <== points(x, y) ==> yaxis:
 1 -4
 1  2

``points(x, y)'' could have (CASCADING) FOREIGN KEY x=>xaxis.x and  
y=>yaxis.y and DELETE TRIGGERs which could adjust counters in  
``*axis'' tables (DELETEing FROM xaxis WHERE x==OLD.x AND n==0 and  
FROM yaxis WHERE y==OLD.y AND n==0; alternatively ``*axis'' could  
have UPDATE TRIGGERs which could DELETE FROM points when ``n''  
column had achieved 0 or less then nX/nY -- triggers must be  
supressed while creating a ``*axis'' table in the latter case).


Then ``iteratively'' (not ``recusively'') DELETE from ``*axis''  
WHERE n < threshold until there are no too small Xs/Ys or tables are  
empty.


(1)
DELETE FROM xaxis WHERE n < nX;
DELETE FROM yaxis WHERE n < nY;

(2)
which fire CASCADE DELETE of relations FROM points

(3)
which fires DELETE TRIGGERs of points

(4)
which adjust referenced xaxis.n and y.axis.n

(4a)
and further DELETE FROM *axis WHERE n == 0

(4b)
and further DELETE FROM *axis WHERE n < nX/nY

(4c)
and further fire UPDATE TRIGGERs of *axis, which in turn further do  
(4a) or (4b).


Cezary, how about this solution with a trigger only on xaxis and on  
yaxis?

AFTER DELETE FROM xaxis:
- update yaxis set n=n-1 where y in (select y from points where x=old.x)
- delete points where x=old.x
- delete yaxis where nNow, with pragma recursive_triggers this might do the whole job if the  
initial deletes(1) are executed. There is a limit on the recursion (/ 
iteration) depth. And this solution requires at most nx+ny iterations,  
where nx is the number of xaxis rows and ny the number of yaxis rows,


On the other hand, if this is not a constest in purely sql  
programming, why not have a programme loop with a single delete, and  
no derived *axis tables. For instance using tclsh:



while 1 {
db eval {
DELETE FROM points
WHERE x IN (
SELECT x FROM points GROUP BY x HAVING COUNT(*)<(SELECT nx FROM  
params)

)
OR y IN (
SELECT y FROM points GROUP BY y HAVING COUNT(*)<(SELECT ny FROM  
params)

)
;
}
if {![db changes]} break
} ;# end loop


E.Pasma
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Cezary H. Noweta]

Hello,

On 2018-05-04 20:02, Roman Fleysher wrote:

For some reason, I did not receive email from Cezary, only comments on it.


About 50% of e-mails from  is 
marked as SPAM by my server for unknown reason. Independently on an author.



But, most importantly, could you elaborate more on how it works. I agree it is 
n-to-n problem. But the solution merges all data into a single cell with all 
pairs, which is counter to relational solution.


Please, do not mind ``a single cell''. This is for the bijective mapping 
STRING <=> TABLE, which is caused by the fact that a recursive CTEs' 
state is a row/record and a whole table must be packed into one row for 
an ``one query'' solution. However, do not do it at home ;) You do not 
need (and should not) do it in an ``one query''. I'm sorry for 
disturbing you.


Ad. solution: AFAIK your tables are created ad hoc and do not exist 
permanently. For each relation ``points'' my solution builds related 
entities (coordinates or Xs/Ys):


CREATE TABLE xaxis AS SELECT x, COUNT(x) AS n FROM points GROUP BY x;
CREATE TABLE yaxis AS SELECT y, COUNT(y) AS n FROM points GROUP BY y;

For example for two points (1,2); (1,-4)

xaxis(x, n):
1 2

yaxis(y, n):
-4 1
 2 1

xaxis <== points(x, y) ==> yaxis:
  1 -4
  1  2

``points(x, y)'' could have (CASCADING) FOREIGN KEY x=>xaxis.x and 
y=>yaxis.y and DELETE TRIGGERs which could adjust counters in ``*axis'' 
tables (DELETEing FROM xaxis WHERE x==OLD.x AND n==0 and FROM yaxis 
WHERE y==OLD.y AND n==0; alternatively ``*axis'' could have UPDATE 
TRIGGERs which could DELETE FROM points when ``n'' column had achieved 0 
or less then nX/nY -- triggers must be supressed while creating a 
``*axis'' table in the latter case).


Then ``iteratively'' (not ``recusively'') DELETE from ``*axis'' WHERE n 
< threshold until there are no too small Xs/Ys or tables are empty.



I ask for details, if possible, because the actual problem  that I have to 
solve is a bit more complicated: I have two of such lists good(x,y) and 
bad(x,y) with a coupling condition that if x is removed from one list, it must 
be removed from the other. This is easy to add for ones who understand how it 
works.


It does complicate nearly nothing. AFAIU good/bad are points on the same 
``image'' (implied by a coupling). Simply, add a column: points(x, y, 
is_good), or add a relational table to have two tables: points_good(x, 
y) and points_bad(x, y) with the same properties as the original 
``points(x, y)'' -- that's all -- nothing more.


If you do not want to lose your original data use Simon's solution (most 
effective), i.e. add ``deleted'' column to ``points'' and ``n_shadow'' 
column to ``*axis'' and modify/restore those columns instead of actual 
DELETEing/UPDATEing ``n''; alternatively (most obvious but not so 
effective in case of big sets of data) make copies of tables/databases.


(1)
DELETE FROM xaxis WHERE n < nX;
DELETE FROM yaxis WHERE n < nY;

(2)
which fire CASCADE DELETE of relations FROM points

(3)
which fires DELETE TRIGGERs of points

(4)
which adjust referenced xaxis.n and y.axis.n

(4a)
and further DELETE FROM *axis WHERE n == 0

(4b)
and further DELETE FROM *axis WHERE n < nX/nY

(4c)
and further fire UPDATE TRIGGERs of *axis, which in turn further do (4a) 
or (4b).


I do not want to provide specified DDL statements as they would require 
a bit of testing -- unfortunately I cannot test SQLite now.


-- best regards

Cezary H. Noweta
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Roman Fleysher]

Thank you Cezary and others who commented.

For some reason, I did not receive email from Cezary, only comments on it.

I was under impression that RECURSIVE can not be used in sub-query. I see that 
it can.

But, most importantly, could you elaborate more on how it works. I agree it is 
n-to-n problem. But the solution merges all data into a single cell with all 
pairs, which is counter to relational solution.

I ask for details, if possible, because the actual problem  that I have to 
solve is a bit more complicated: I have two of such lists good(x,y) and 
bad(x,y) with a coupling condition that if x is removed from one list, it must 
be removed from the other. This is easy to add for ones who understand how it 
works. 

Roman


From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf of 
E.Pasma [pasm...@concepts.nl]
Sent: Friday, May 04, 2018 10:35 AM
To: SQLite mailing list
Subject: Re: [sqlite] probably recursive?

Cezary H. Noweta wrote:
>>
>>> At the beginning I would like to agree with that the problem is
>>> iterative rather then recursive one. However
R. Smith wrote:
>
>> LOL, that might be the hackiest query I ever seen, but kudos mate,
>> that's bloody marvellous!

Cezary, thanks for the diverting solution. I've been looking into
solving sudokus along the same lines. A function GROUP_SPLIT as an
inverse of GROUP_CONCAT would be handy here. Below is the query as it
looks when there was such a function, or actually a (function like)
virtual table with column elem. It is exactly half the size.
Nevertheless the fun is to achieve the goal purely in SQL.
Thanks, E Pasma.

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;

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 (
   SELECT
 CAST(elem AS INTEGER) x,
 CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) y
   FROM GROUP_SPLIT (state.points)
 )
 WHERE (x NOT IN (
   SELECT x FROM (
 SELECT
   CAST(elem AS INTEGER) x,
   CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
   FROM GROUP_SPLIT (state.xaxis)
   ) WHERE n < (SELECT nx FROM params)
 )) AND (y NOT IN (
   SELECT y FROM (
 SELECT
   CAST(elem AS INTEGER) y,
   CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
   FROM GROUP_SPLIT (state.yaxis)
   ) 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 (
   SELECT
 CAST(elem AS INTEGER) x
   FROM GROUP_SPLIT (state.points)
 ) GROUP BY x)) ELSE xaxis END,
 CASE clock WHEN 1 THEN
(SELECT GROUP_CONCAT(y || ' ' || n) FROM (SELECT y, COUNT(y) n FROM (
   SELECT
 CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) y
   FROM GROUP_SPLIT (state.points)
 ) GROUP BY y)) ELSE yaxis END,
 CASE clock WHEN 2 THEN
 (SELECT MIN(n) FROM (
   SELECT
 CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
   FROM GROUP_SPLIT (state.xaxis)
 )) ELSE nxmin END,
 CASE clock WHEN 2 THEN
 (SELECT MAX(n) FROM (
   SELECT
 CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
   FROM GROUP_SPLIT (state.xaxis)
 )) ELSE nxmax END,
 CASE clock WHEN 2 THEN
 (SELECT MIN(n) FROM (
   SELECT
 CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
   FROM GROUP_SPLIT (state.yaxis)
 )) ELSE nymin END,
 CASE clock WHEN 2 THEN

Re: [sqlite] probably recursive?

[E.Pasma]

Cezary H. Noweta wrote:


At the beginning I would like to agree with that the problem is  
iterative rather then recursive one. However

R. Smith wrote:


LOL, that might be the hackiest query I ever seen, but kudos mate,  
that's bloody marvellous!


Cezary, thanks for the diverting solution. I've been looking into  
solving sudokus along the same lines. A function GROUP_SPLIT as an  
inverse of GROUP_CONCAT would be handy here. Below is the query as it  
looks when there was such a function, or actually a (function like)  
virtual table with column elem. It is exactly half the size.  
Nevertheless the fun is to achieve the goal purely in SQL.

Thanks, E Pasma.

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;


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 (
  SELECT
CAST(elem AS INTEGER) x,
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) y
  FROM GROUP_SPLIT (state.points)
)
WHERE (x NOT IN (
  SELECT x FROM (
SELECT
  CAST(elem AS INTEGER) x,
  CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
  FROM GROUP_SPLIT (state.xaxis)
  ) WHERE n < (SELECT nx FROM params)
)) AND (y NOT IN (
  SELECT y FROM (
SELECT
  CAST(elem AS INTEGER) y,
  CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
  FROM GROUP_SPLIT (state.yaxis)
  ) 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 (
  SELECT
CAST(elem AS INTEGER) x
  FROM GROUP_SPLIT (state.points)
) GROUP BY x)) ELSE xaxis END,
CASE clock WHEN 1 THEN
(SELECT GROUP_CONCAT(y || ' ' || n) FROM (SELECT y, COUNT(y) n FROM (
  SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) y
  FROM GROUP_SPLIT (state.points)
) GROUP BY y)) ELSE yaxis END,
CASE clock WHEN 2 THEN
(SELECT MIN(n) FROM (
  SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
  FROM GROUP_SPLIT (state.xaxis)
)) ELSE nxmin END,
CASE clock WHEN 2 THEN
(SELECT MAX(n) FROM (
  SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
  FROM GROUP_SPLIT (state.xaxis)
)) ELSE nxmax END,
CASE clock WHEN 2 THEN
(SELECT MIN(n) FROM (
  SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
  FROM GROUP_SPLIT (state.yaxis)
)) ELSE nymin END,
CASE clock WHEN 2 THEN
(SELECT MAX(n) FROM (
  SELECT
CAST(SUBSTR(elem, INSTR(elem, ' ')) AS INTEGER) n
  FROM GROUP_SPLIT (state.yaxis)
)) 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
;


___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Cezary H. Noweta]

Hello,

On 2018-05-04 03:07, R Smith wrote:

On 2018/05/04 1:54 AM, Cezary H. Noweta wrote:
At the beginning I would like to agree with that the problem is 
iterative rather then recursive one. However


LOL, that might be the hackiest query I ever seen, but kudos mate, 
that's bloody marvellous!


Thank you. ;)

-- best regards

Cezary H. Noweta
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[R Smith]

On 2018/05/04 1:54 AM, Cezary H. Noweta wrote:

Hello,

At the beginning I would like to agree with that the problem is 
iterative rather then recursive one. However


LOL, that might be the hackiest query I ever seen, but kudos mate, 
that's bloody marvellous!


I corrected the table to not have duplicate points, and then added some 
bits to visualize the points, which makes it easier to see what is 
happening - also just for fun :)
(Might have to run it a couple times to get a point-set that actually 
passes)




  -- SQLite version 3.20.1  [ Release: 2017-08-24 ]  on SQLitespeed 
version 2.0.2.4.
  -- 



DROP TABLE IF EXISTS points;

CREATE TABLE points(
  x INT, y INT, PRIMARY KEY (x,y)
);

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
)
INSERT INTO points(x,y)
SELECT DISTINCT x, y FROM cte;


SELECT 'Y_'||y AS 'Points',
   MAX(CASE X WHEN  1 THEN ' * ' ELSE '   ' END) AS X_1,
   MAX(CASE X WHEN  2 THEN ' * ' ELSE '   ' END) AS X_2,
   MAX(CASE X WHEN  3 THEN ' * ' ELSE '   ' END) AS X_3,
   MAX(CASE X WHEN  4 THEN ' * ' ELSE '   ' END) AS X_4,
   MAX(CASE X WHEN  5 THEN ' * ' ELSE '   ' END) AS X_5,
   MAX(CASE X WHEN  6 THEN ' * ' ELSE '   ' END) AS X_6,
   MAX(CASE X WHEN  7 THEN ' * ' ELSE '   ' END) AS X_7,
   MAX(CASE X WHEN  8 THEN ' * ' ELSE '   ' END) AS X_8,
   MAX(CASE X WHEN  9 THEN ' * ' ELSE '   ' END) AS X_9,
   MAX(CASE X WHEN 10 THEN ' * ' ELSE '   ' END) AS X_10
  FROM points
 GROUP BY y
;


  -- Points | X_1 | X_2 | X_3 | X_4 | X_5 | X_6 | X_7 | X_8 | X_9 | X_10
  -- -- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 
  -- Y_1    |  *  | | |  *  |  *  | | | | |  *
  -- Y_2    |  *  |  *  | | | |  *  |  *  |  * | |
  -- Y_3    |  *  | |  *  |  *  |  *  |  *  |  *  | |  *  |
  -- Y_4    |  *  |  *  | |  *  | |  *  |  *  |  * | |
  -- Y_5    |  *  | |  *  | |  *  |  *  |  *  |  * |  *  |
  -- Y_6    | | |  *  |  *  |  *  |  *  | |  * |  *  |  *
  -- Y_7    |  *  |  *  |  *  |  *  |  *  | |  *  |  * | |  *
  -- Y_8    |  *  |  *  | |  *  | |  *  |  *  | |  *  |
  -- Y_9    | |  *  |  *  |  *  |  *  |  *  |  *  |  * |  *  |  *
  -- Y_10   |  *  |  *  | |  *  |  *  |  *  | |  * |  *  |  *

WITH
  params(nx, ny) AS (SELECT 5, 6),
  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

Re: [sqlite] probably recursive?

[Cezary H. Noweta]

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))),

   

Re: [sqlite] probably recursive?

[Roman Fleysher]

nX is a number, the smallest allowed count. There are two conditions,  count of 
dots along horizontal line and count of dots along verticals.



Sent from my T-Mobile 4G LTE Device


 Original message 
From: Barry Smith <smith.bar...@gmail.com>
Date: 5/1/18 7:40 PM (GMT-05:00)
To: SQLite mailing list <sqlite-users@mailinglists.sqlite.org>
Subject: Re: [sqlite] probably recursive?

Ah my bad, I misunderstood the initial condition. nX is a function of X. My 
statements were only true if nX=X. Well, sorry about the noise.

> On 2 May 2018, at 8:20 am, Roman Fleysher <roman.fleys...@einstein.yu.edu> 
> wrote:
>
> Dear Barry,
>
> The statement about the square is not obvious to me. The requirements on 
> counts in x and y are different.
>
> I also imagine answer could be two or several non-overlapping  "rectangles". 
> "Rectangles" will not be densely filled with dots, they might have empty 
> spots either because the points were never on the list or were eliminated.
>
> Roman
>
> 
> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf 
> of Barry Smith [smith.bar...@gmail.com]
> Sent: Tuesday, May 01, 2018 6:12 PM
> To: SQLite mailing list
> Subject: Re: [sqlite] probably recursive?
>
> Well those constraints simplify your problem.
>
> In the resultant dataset, the largest X and Y values will be equal, and the 
> largest X will have and entry for every coordinate from (X, 1) to (X, X). 
> Likewise the largest Y will have an entry for every coordinate from (1, Y) to 
> (Y, Y). Basically you'll have two lines from the axes, drawing a square. All 
> points outside that square will be culled, all points on and inside the 
> square will be kept.
>
> Since you know that, you now have a one dimensional problem to solve. It 
> still seems a little recursive to me, but it should be easier because you 
> only need to find a single number (which you can then plug into a delete 
> statement).
>
> If my statement about the square is not obvious to prove in your head I can 
> try write a proof for that but I'm not much good at proofs.
>
>> On 2 May 2018, at 7:27 am, Roman Fleysher <roman.fleys...@einstein.yu.edu> 
>> wrote:
>>
>> Pairs (x,y) do not repeat.
>>
>> Actual x and y are positive integers, but I do not see how being positive 
>> can be relevant. Integer is important for sorting/comparison.
>>
>>
>> Roman
>>
>> ________
>> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf 
>> of Barry Smith [smith.bar...@gmail.com]
>> Sent: Tuesday, May 01, 2018 5:23 PM
>> To: SQLite mailing list
>> Subject: Re: [sqlite] probably recursive?
>>
>> Is there a uniqueness constraint on your initial data? Can the same 
>> coordinate be listed multiple times?
>>
>> Is there a requirement that X > 0 and Y > 0?
>>
>>>> On 2 May 2018, at 3:35 am, Simon Slavin <slav...@bigfraud.org> wrote:
>>>>
>>>> On 1 May 2018, at 6:28pm, Simon Slavin <slav...@bigfraud.org> wrote:
>>>>
>>>> I just realised that
>>>
>>> That was intended to be personal email.  Apologies, everyone.
>>>
>>> Simon.
>>> ___
>>> sqlite-users mailing list
>>> sqlite-users@mailinglists.sqlite.org
>>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Barry Smith]

Ah my bad, I misunderstood the initial condition. nX is a function of X. My 
statements were only true if nX=X. Well, sorry about the noise.

> On 2 May 2018, at 8:20 am, Roman Fleysher <roman.fleys...@einstein.yu.edu> 
> wrote:
> 
> Dear Barry,
> 
> The statement about the square is not obvious to me. The requirements on 
> counts in x and y are different.
> 
> I also imagine answer could be two or several non-overlapping  "rectangles". 
> "Rectangles" will not be densely filled with dots, they might have empty 
> spots either because the points were never on the list or were eliminated.
> 
> Roman
> 
> 
> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf 
> of Barry Smith [smith.bar...@gmail.com]
> Sent: Tuesday, May 01, 2018 6:12 PM
> To: SQLite mailing list
> Subject: Re: [sqlite] probably recursive?
> 
> Well those constraints simplify your problem.
> 
> In the resultant dataset, the largest X and Y values will be equal, and the 
> largest X will have and entry for every coordinate from (X, 1) to (X, X). 
> Likewise the largest Y will have an entry for every coordinate from (1, Y) to 
> (Y, Y). Basically you'll have two lines from the axes, drawing a square. All 
> points outside that square will be culled, all points on and inside the 
> square will be kept.
> 
> Since you know that, you now have a one dimensional problem to solve. It 
> still seems a little recursive to me, but it should be easier because you 
> only need to find a single number (which you can then plug into a delete 
> statement).
> 
> If my statement about the square is not obvious to prove in your head I can 
> try write a proof for that but I'm not much good at proofs.
> 
>> On 2 May 2018, at 7:27 am, Roman Fleysher <roman.fleys...@einstein.yu.edu> 
>> wrote:
>> 
>> Pairs (x,y) do not repeat.
>> 
>> Actual x and y are positive integers, but I do not see how being positive 
>> can be relevant. Integer is important for sorting/comparison.
>> 
>> 
>> Roman
>> 
>> ________
>> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf 
>> of Barry Smith [smith.bar...@gmail.com]
>> Sent: Tuesday, May 01, 2018 5:23 PM
>> To: SQLite mailing list
>> Subject: Re: [sqlite] probably recursive?
>> 
>> Is there a uniqueness constraint on your initial data? Can the same 
>> coordinate be listed multiple times?
>> 
>> Is there a requirement that X > 0 and Y > 0?
>> 
>>>> On 2 May 2018, at 3:35 am, Simon Slavin <slav...@bigfraud.org> wrote:
>>>> 
>>>> On 1 May 2018, at 6:28pm, Simon Slavin <slav...@bigfraud.org> wrote:
>>>> 
>>>> I just realised that
>>> 
>>> That was intended to be personal email.  Apologies, everyone.
>>> 
>>> Simon.
>>> ___
>>> sqlite-users mailing list
>>> sqlite-users@mailinglists.sqlite.org
>>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Barry Smith]

In you initial email, what is n? Some real number between zero and one?

> On 2 May 2018, at 8:37 am, Abroży Nieprzełoży 
> <abrozynieprzelozy314...@gmail.com> wrote:
> 
> I think Barry mean that you can represent the (x,y) pair as a single
> number like (max(X)-min(X))*(Y-min(Y))+X-min(X) or so, but I don't see
> how it would be helpful.
> 
> 2018-05-02 0:20 GMT+02:00, Roman Fleysher:
>> Dear Barry,
>> 
>> The statement about the square is not obvious to me. The requirements on
>> counts in x and y are different.
>> 
>> I also imagine answer could be two or several non-overlapping  "rectangles".
>> "Rectangles" will not be densely filled with dots, they might have empty
>> spots either because the points were never on the list or were eliminated.
>> 
>> Roman
>> 
>> 
>> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf
>> of Barry Smith [smith.bar...@gmail.com]
>> Sent: Tuesday, May 01, 2018 6:12 PM
>> To: SQLite mailing list
>> Subject: Re: [sqlite] probably recursive?
>> 
>> Well those constraints simplify your problem.
>> 
>> In the resultant dataset, the largest X and Y values will be equal, and the
>> largest X will have and entry for every coordinate from (X, 1) to (X, X).
>> Likewise the largest Y will have an entry for every coordinate from (1, Y)
>> to (Y, Y). Basically you'll have two lines from the axes, drawing a square.
>> All points outside that square will be culled, all points on and inside the
>> square will be kept.
>> 
>> Since you know that, you now have a one dimensional problem to solve. It
>> still seems a little recursive to me, but it should be easier because you
>> only need to find a single number (which you can then plug into a delete
>> statement).
>> 
>> If my statement about the square is not obvious to prove in your head I can
>> try write a proof for that but I'm not much good at proofs.
>> 
>>> On 2 May 2018, at 7:27 am, Roman Fleysher
>>> wrote:
>>> 
>>> Pairs (x,y) do not repeat.
>>> 
>>> Actual x and y are positive integers, but I do not see how being positive
>>> can be relevant. Integer is important for sorting/comparison.
>>> 
>>> 
>>> Roman
>>> 
>>> 
>>> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on
>>> behalf of Barry Smith [smith.bar...@gmail.com]
>>> Sent: Tuesday, May 01, 2018 5:23 PM
>>> To: SQLite mailing list
>>> Subject: Re: [sqlite] probably recursive?
>>> 
>>> Is there a uniqueness constraint on your initial data? Can the same
>>> coordinate be listed multiple times?
>>> 
>>> Is there a requirement that X > 0 and Y > 0?
>>> 
>>>>> On 2 May 2018, at 3:35 am, Simon Slavin  wrote:
>>>>> 
>>>>> On 1 May 2018, at 6:28pm, Simon Slavin  wrote:
>>>>> 
>>>>> I just realised that
>>>> 
>>>> That was intended to be personal email.  Apologies, everyone.
>>>> 
>>>> Simon.
>>>> ___
>>>> sqlite-users mailing list
>>>> sqlite-users@mailinglists.sqlite.org
>>>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>>> ___
>>> sqlite-users mailing list
>>> sqlite-users@mailinglists.sqlite.org
>>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>>> ___
>>> sqlite-users mailing list
>>> sqlite-users@mailinglists.sqlite.org
>>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> 
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Abroży Nieprzełoży]

I think Barry mean that you can represent the (x,y) pair as a single
number like (max(X)-min(X))*(Y-min(Y))+X-min(X) or so, but I don't see
how it would be helpful.

2018-05-02 0:20 GMT+02:00, Roman Fleysher:
> Dear Barry,
>
> The statement about the square is not obvious to me. The requirements on
> counts in x and y are different.
>
> I also imagine answer could be two or several non-overlapping  "rectangles".
> "Rectangles" will not be densely filled with dots, they might have empty
> spots either because the points were never on the list or were eliminated.
>
> Roman
>
> 
> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf
> of Barry Smith [smith.bar...@gmail.com]
> Sent: Tuesday, May 01, 2018 6:12 PM
> To: SQLite mailing list
> Subject: Re: [sqlite] probably recursive?
>
> Well those constraints simplify your problem.
>
> In the resultant dataset, the largest X and Y values will be equal, and the
> largest X will have and entry for every coordinate from (X, 1) to (X, X).
> Likewise the largest Y will have an entry for every coordinate from (1, Y)
> to (Y, Y). Basically you'll have two lines from the axes, drawing a square.
> All points outside that square will be culled, all points on and inside the
> square will be kept.
>
> Since you know that, you now have a one dimensional problem to solve. It
> still seems a little recursive to me, but it should be easier because you
> only need to find a single number (which you can then plug into a delete
> statement).
>
> If my statement about the square is not obvious to prove in your head I can
> try write a proof for that but I'm not much good at proofs.
>
>> On 2 May 2018, at 7:27 am, Roman Fleysher
>> wrote:
>>
>> Pairs (x,y) do not repeat.
>>
>> Actual x and y are positive integers, but I do not see how being positive
>> can be relevant. Integer is important for sorting/comparison.
>>
>>
>> Roman
>>
>> 
>> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on
>> behalf of Barry Smith [smith.bar...@gmail.com]
>> Sent: Tuesday, May 01, 2018 5:23 PM
>> To: SQLite mailing list
>> Subject: Re: [sqlite] probably recursive?
>>
>> Is there a uniqueness constraint on your initial data? Can the same
>> coordinate be listed multiple times?
>>
>> Is there a requirement that X > 0 and Y > 0?
>>
>>>> On 2 May 2018, at 3:35 am, Simon Slavin  wrote:
>>>>
>>>> On 1 May 2018, at 6:28pm, Simon Slavin  wrote:
>>>>
>>>> I just realised that
>>>
>>> That was intended to be personal email.  Apologies, everyone.
>>>
>>> Simon.
>>> ___
>>> sqlite-users mailing list
>>> sqlite-users@mailinglists.sqlite.org
>>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Roman Fleysher]

Dear Barry,

The statement about the square is not obvious to me. The requirements on counts 
in x and y are different.

I also imagine answer could be two or several non-overlapping  "rectangles". 
"Rectangles" will not be densely filled with dots, they might have empty spots 
either because the points were never on the list or were eliminated.

Roman


From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf of 
Barry Smith [smith.bar...@gmail.com]
Sent: Tuesday, May 01, 2018 6:12 PM
To: SQLite mailing list
Subject: Re: [sqlite] probably recursive?

Well those constraints simplify your problem.

In the resultant dataset, the largest X and Y values will be equal, and the 
largest X will have and entry for every coordinate from (X, 1) to (X, X). 
Likewise the largest Y will have an entry for every coordinate from (1, Y) to 
(Y, Y). Basically you'll have two lines from the axes, drawing a square. All 
points outside that square will be culled, all points on and inside the square 
will be kept.

Since you know that, you now have a one dimensional problem to solve. It still 
seems a little recursive to me, but it should be easier because you only need 
to find a single number (which you can then plug into a delete statement).

If my statement about the square is not obvious to prove in your head I can try 
write a proof for that but I'm not much good at proofs.

> On 2 May 2018, at 7:27 am, Roman Fleysher <roman.fleys...@einstein.yu.edu> 
> wrote:
>
> Pairs (x,y) do not repeat.
>
> Actual x and y are positive integers, but I do not see how being positive can 
> be relevant. Integer is important for sorting/comparison.
>
>
> Roman
>
> 
> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf 
> of Barry Smith [smith.bar...@gmail.com]
> Sent: Tuesday, May 01, 2018 5:23 PM
> To: SQLite mailing list
> Subject: Re: [sqlite] probably recursive?
>
> Is there a uniqueness constraint on your initial data? Can the same 
> coordinate be listed multiple times?
>
> Is there a requirement that X > 0 and Y > 0?
>
>>> On 2 May 2018, at 3:35 am, Simon Slavin <slav...@bigfraud.org> wrote:
>>>
>>> On 1 May 2018, at 6:28pm, Simon Slavin <slav...@bigfraud.org> wrote:
>>>
>>> I just realised that
>>
>> That was intended to be personal email.  Apologies, everyone.
>>
>> Simon.
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Barry Smith]

Well those constraints simplify your problem.

In the resultant dataset, the largest X and Y values will be equal, and the 
largest X will have and entry for every coordinate from (X, 1) to (X, X). 
Likewise the largest Y will have an entry for every coordinate from (1, Y) to 
(Y, Y). Basically you'll have two lines from the axes, drawing a square. All 
points outside that square will be culled, all points on and inside the square 
will be kept.

Since you know that, you now have a one dimensional problem to solve. It still 
seems a little recursive to me, but it should be easier because you only need 
to find a single number (which you can then plug into a delete statement).

If my statement about the square is not obvious to prove in your head I can try 
write a proof for that but I'm not much good at proofs.

> On 2 May 2018, at 7:27 am, Roman Fleysher <roman.fleys...@einstein.yu.edu> 
> wrote:
> 
> Pairs (x,y) do not repeat.
> 
> Actual x and y are positive integers, but I do not see how being positive can 
> be relevant. Integer is important for sorting/comparison.
> 
> 
> Roman
> 
> 
> From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf 
> of Barry Smith [smith.bar...@gmail.com]
> Sent: Tuesday, May 01, 2018 5:23 PM
> To: SQLite mailing list
> Subject: Re: [sqlite] probably recursive?
> 
> Is there a uniqueness constraint on your initial data? Can the same 
> coordinate be listed multiple times?
> 
> Is there a requirement that X > 0 and Y > 0?
> 
>>> On 2 May 2018, at 3:35 am, Simon Slavin <slav...@bigfraud.org> wrote:
>>> 
>>> On 1 May 2018, at 6:28pm, Simon Slavin <slav...@bigfraud.org> wrote:
>>> 
>>> I just realised that
>> 
>> That was intended to be personal email.  Apologies, everyone.
>> 
>> Simon.
>> ___
>> sqlite-users mailing list
>> sqlite-users@mailinglists.sqlite.org
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Roman Fleysher]

Pairs (x,y) do not repeat.

Actual x and y are positive integers, but I do not see how being positive can 
be relevant. Integer is important for sorting/comparison.


Roman


From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf of 
Barry Smith [smith.bar...@gmail.com]
Sent: Tuesday, May 01, 2018 5:23 PM
To: SQLite mailing list
Subject: Re: [sqlite] probably recursive?

Is there a uniqueness constraint on your initial data? Can the same coordinate 
be listed multiple times?

Is there a requirement that X > 0 and Y > 0?

> On 2 May 2018, at 3:35 am, Simon Slavin <slav...@bigfraud.org> wrote:
>
>> On 1 May 2018, at 6:28pm, Simon Slavin <slav...@bigfraud.org> wrote:
>>
>> I just realised that
>
> That was intended to be personal email.  Apologies, everyone.
>
> Simon.
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Barry Smith]

Is there a uniqueness constraint on your initial data? Can the same coordinate 
be listed multiple times?

Is there a requirement that X > 0 and Y > 0?

> On 2 May 2018, at 3:35 am, Simon Slavin  wrote:
> 
>> On 1 May 2018, at 6:28pm, Simon Slavin  wrote:
>> 
>> I just realised that
> 
> That was intended to be personal email.  Apologies, everyone.
> 
> Simon.
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Simon Slavin]

On 1 May 2018, at 6:28pm, Simon Slavin  wrote:

> I just realised that

That was intended to be personal email.  Apologies, everyone.

Simon.
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Simon Slavin]

On 1 May 2018, at 1:45am, Roman Fleysher  wrote:

> If x=10 has less than nX dots, all dots with x=10 are deleted. Because of 
> deletion, y=3 which previously had more than nY dots no longer passes the 
> threshold and thus y=3 must be deleted too. This could cause deletion of some 
> other x, etc. At the end, number of dots on all vertical lines must be more 
> than nX and number of dots on all horizontal lines must be more than nY.

I just realised that this is an image-processing problem, and could be 
completed ridiculously quickly by defining a filter in a GPU language.  If you 
have access to people working in image recognition, you might usefully consult 
them about how big a dataset they could support, or just show them the problem 
in general.

I would prototype it using a JavaScript canvas.  Once the initial data is 
written to the canvas you can use API calls to see what colour a pixel is, so 
the whole thing could be completed without needing further access to the SQLite 
table.  I would bet that any up-to-date browser could solve the problem in 
JavaScript fast enough for still images.  Applying it to successive frames of a 
moving image might be a different matter.

Not helpful for a SQLite solution, I'm afraid.

Simon.
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Roman Fleysher]

Agree. Thank you.

Roman


From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf of 
Simon Slavin [slav...@bigfraud.org]
Sent: Tuesday, May 01, 2018 12:50 PM
To: SQLite mailing list
Subject: Re: [sqlite] probably recursive?

On 1 May 2018, at 5:34pm, Roman Fleysher <roman.fleys...@einstein.yu.edu> wrote:

> With recursive route, I am thinking I need to build deleteList(x,y).

Rather than actually delete rows, if you can, insert a new column in the table 
of all points.  It starts with every row set to TRUE.  When you decide a row 
doesn't count the value gets set to FALSE.

This will be faster than doing the processing and file handling involved in 
deleting rows.

Simon.
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Simon Slavin]

On 1 May 2018, at 5:34pm, Roman Fleysher  wrote:

> With recursive route, I am thinking I need to build deleteList(x,y).

Rather than actually delete rows, if you can, insert a new column in the table 
of all points.  It starts with every row set to TRUE.  When you decide a row 
doesn't count the value gets set to FALSE.

This will be faster than doing the processing and file handling involved in 
deleting rows.

Simon.
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Roman Fleysher]

With recursive route, I am thinking I need to build deleteList(x,y). But I can 
not come up with a way to use deleteList only once in the FROM after UNION and 
not in subqueries , as required by WITH RECURSIVE. Assuming pairsTable(x,y) is 
the input table: 

WITH RECURSIVE deleteList(x, y) AS 
( SELECT NULL, NULL
  UNION
  SELECT x, y FROM pairsTable 
  WHERE x IN (SELECT x FROM (SELECT x, y FROM pairsTable 
   EXCEPT 
   SELECT x, y FROM 
deleteList WHERE x IS NOT NULL)
   GROUP BY x HAVING count(x) < 25)
)
SELECT x, y FROM deleteList;



Roman



From: sqlite-users [sqlite-users-boun...@mailinglists.sqlite.org] on behalf of 
David Raymond [david.raym...@tomtom.com]
Sent: Tuesday, May 01, 2018 10:27 AM
To: SQLite mailing list
Subject: Re: [sqlite] probably recursive?

My initial thought on this would be recursive on delete triggers. You're 
limited then to SQLITE_MAX_TRIGGER_DEPTH (defaults to 1,000) though, so really 
big cascades wouldn't fully complete. You can raise the limit, but 
mathematically speaking there's still going to be a limit then.

Will have to think about the recursive CTE route later.

-Original Message-
From: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org] On 
Behalf Of R Smith
Sent: Tuesday, May 01, 2018 8:16 AM
To: sqlite-users@mailinglists.sqlite.org
Subject: Re: [sqlite] probably recursive?

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.

You can of course "achieve" it using any SQL engine by constructing a
temporary table, and then repeatedly run a DELETE query for all x values
where COUNT(y) is less than nY, then DELETE all y values where COUNT(x)
< nX, rinse, repeat until  both SELECT y HAVING COUNT(x) < nX and SELECT
x HAVING COUNT(y) < nY aggregate queries return empty sets - but this
would be painfully slow next to a simple software algorithm that
prunes/resolves a 2-dimensional array - exponentially worse so for
larger grid sizes.


On 2018/05/01 2:45 AM, Roman Fleysher wrote:
> Dear SQLiters,
>
> I have trouble solving this problem, maybe it is impossible?
>
> I have a table with two columns x and y, both integers. Imagine they are 
> coordinates on X-Y plane, dots. I need to find all x's that have more than nX 
> dots, and all y's that have more than nY dots. Both conditions must be 
> simultaneous in the following sense:
>
> If x=10 has less than nX dots, all dots with x=10 are deleted. Because of 
> deletion, y=3 which previously had more than nY dots no longer passes the 
> threshold and thus y=3 must be deleted too. This could cause deletion of some 
> other x, etc. At the end, number of dots on all vertical lines must be more 
> than nX and number of dots on all horizontal lines must be more than nY.
>
> Could this be achieved with SQLite?
>
> Roman
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[David Raymond]

My initial thought on this would be recursive on delete triggers. You're 
limited then to SQLITE_MAX_TRIGGER_DEPTH (defaults to 1,000) though, so really 
big cascades wouldn't fully complete. You can raise the limit, but 
mathematically speaking there's still going to be a limit then.

Will have to think about the recursive CTE route later.

-Original Message-
From: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org] On 
Behalf Of R Smith
Sent: Tuesday, May 01, 2018 8:16 AM
To: sqlite-users@mailinglists.sqlite.org
Subject: Re: [sqlite] probably recursive?

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.

You can of course "achieve" it using any SQL engine by constructing a 
temporary table, and then repeatedly run a DELETE query for all x values 
where COUNT(y) is less than nY, then DELETE all y values where COUNT(x) 
< nX, rinse, repeat until  both SELECT y HAVING COUNT(x) < nX and SELECT 
x HAVING COUNT(y) < nY aggregate queries return empty sets - but this 
would be painfully slow next to a simple software algorithm that 
prunes/resolves a 2-dimensional array - exponentially worse so for 
larger grid sizes.


On 2018/05/01 2:45 AM, Roman Fleysher wrote:
> Dear SQLiters,
>
> I have trouble solving this problem, maybe it is impossible?
>
> I have a table with two columns x and y, both integers. Imagine they are 
> coordinates on X-Y plane, dots. I need to find all x's that have more than nX 
> dots, and all y's that have more than nY dots. Both conditions must be 
> simultaneous in the following sense:
>
> If x=10 has less than nX dots, all dots with x=10 are deleted. Because of 
> deletion, y=3 which previously had more than nY dots no longer passes the 
> threshold and thus y=3 must be deleted too. This could cause deletion of some 
> other x, etc. At the end, number of dots on all vertical lines must be more 
> than nX and number of dots on all horizontal lines must be more than nY.
>
> Could this be achieved with SQLite?
>
> Roman
> ___
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[R Smith]

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.

You can of course "achieve" it using any SQL engine by constructing a 
temporary table, and then repeatedly run a DELETE query for all x values 
where COUNT(y) is less than nY, then DELETE all y values where COUNT(x) 
< nX, rinse, repeat until  both SELECT y HAVING COUNT(x) < nX and SELECT 
x HAVING COUNT(y) < nY aggregate queries return empty sets - but this 
would be painfully slow next to a simple software algorithm that 
prunes/resolves a 2-dimensional array - exponentially worse so for 
larger grid sizes.



On 2018/05/01 2:45 AM, Roman Fleysher wrote:

Dear SQLiters,

I have trouble solving this problem, maybe it is impossible?

I have a table with two columns x and y, both integers. Imagine they are 
coordinates on X-Y plane, dots. I need to find all x's that have more than nX 
dots, and all y's that have more than nY dots. Both conditions must be 
simultaneous in the following sense:

If x=10 has less than nX dots, all dots with x=10 are deleted. Because of 
deletion, y=3 which previously had more than nY dots no longer passes the 
threshold and thus y=3 must be deleted too. This could cause deletion of some 
other x, etc. At the end, number of dots on all vertical lines must be more 
than nX and number of dots on all horizontal lines must be more than nY.

Could this be achieved with SQLite?

Roman
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] probably recursive?

[Simon Slavin]

On 1 May 2018, at 1:45am, Roman Fleysher  wrote:

> If x=10 has less than nX dots, all dots with x=10 are deleted. Because of 
> deletion, y=3 which previously had more than nY dots no longer passes the 
> threshold and thus y=3 must be deleted too. This could cause deletion of some 
> other x, etc. At the end, number of dots on all vertical lines must be more 
> than nX and number of dots on all horizontal lines must be more than nY.
> 
> Could this be achieved with SQLite?

The continual refining of 'survivors' suggest that you need a WITH RECURSIVE 
construction:



Index both x and y columns in your table.

It may be possible to complete the task purely in SQLite,  I wouldn't choose to 
do it that way but there are people here who delight in crafting complicated 
Recursive Common Table Expressions.

Simon.
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] probably recursive?

[Roman Fleysher]

Dear SQLiters,

I have trouble solving this problem, maybe it is impossible?

I have a table with two columns x and y, both integers. Imagine they are 
coordinates on X-Y plane, dots. I need to find all x's that have more than nX 
dots, and all y's that have more than nY dots. Both conditions must be 
simultaneous in the following sense:

If x=10 has less than nX dots, all dots with x=10 are deleted. Because of 
deletion, y=3 which previously had more than nY dots no longer passes the 
threshold and thus y=3 must be deleted too. This could cause deletion of some 
other x, etc. At the end, number of dots on all vertical lines must be more 
than nX and number of dots on all horizontal lines must be more than nY.

Could this be achieved with SQLite?

Roman
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users