Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Assuming a pixel grid with x and y of the size 1000 over 1000. In each iteration\run, using a random number generator, certain cells will be marked as occupied. Those cells will be written in a SQLite database.

In a two dimentional grid, each cell can have up to 8 occupied neighbours. Once an occupied cell sees 8 occupied neighbours i would like to preform some computations.

At the moment i have in my SQLite table three columns (x and y, processed). Only occupied cells are written in to the table (unoccupied cells are not in the table). The processed flag is a boolean flag.

I would like to know after each run, if there exist cells which are occupied, not processed and have 8 occupied neighbours. I am open to changes in the database for doing this query.

share|improve this question

closed as off topic by Max Vernon, dezso, RolandoMySQLDBA, StanleyJohns, Derek Downey Apr 29 '13 at 20:28

Questions on Database Administrators Stack Exchange are expected to relate to database administration within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
You may want to consider that a database may not be the best solution to perform these computations -- why not use an application server, which will scale out much better? (I'm assuming this is a Monte Carlo type simulation where you'll be doing this with a big set of random inputs.) You can store the original with results in the database, but perform all the computations elsewhere. –  Jon Seigel Apr 29 '13 at 14:17

2 Answers 2

up vote 3 down vote accepted

This is a sample matrix. The query should find all the green cells, with value = F (as is TO BE FOUND :) ) ...

enter image description here

SELECT    
   x AS MATRIX_X,    
   y AS MATRIX_Y    
FROM (    
       SELECT    
           a.x    
           ,a.y    
           ,a.processed    
           ,(
                   SELECT
                       COUNT (processed)
                   FROM
                       pixels b
                   WHERE
                               -- Move around the current cell, and check the neighbors
                               -- Movement will be clock wise, starting from top left cell    
                          -- --------------------------------------------------------
                              (b.x = (a.x - 1) AND b.y = (a.y - 1) AND b.processed = 1)
                           OR (b.x = (a.x    ) AND b.y = (a.y - 1) AND b.processed = 1)
                           OR (b.x = (a.x + 1) AND b.y = (a.y - 1) AND b.processed = 1)
                           OR (b.x = (a.x + 1) AND b.y = (a.y    ) AND b.processed = 1)
                           OR (b.x = (a.x + 1) AND b.y = (a.y + 1) AND b.processed = 1)
                           OR (b.x = (a.x    ) AND b.y = (a.y + 1) AND b.processed = 1)
                           OR (b.x = (a.x - 1) AND b.y = (a.y + 1) AND b.processed = 1)
                           OR (b.x = (a.x - 1) AND b.y = (a.y    ) AND b.processed = 1)
           ) AS processed_near
       FROM
           pixels a
       WHERE
           a.processed = 1     -- Current cell has to be processed
   ) q1
 WHERE
    processed_near = 8 -- all 8 neighbors should be processed
ORDER BY
   x ASC,
   y ASC   

enter image description here

share|improve this answer
    
@MTlhai, great answer. Could you explain what is q1? is it the raw table? Could you please add it as well? Thanks –  Eagle Apr 29 '13 at 18:36
    
@Eagle: q1 is like an alias name for the sub-query. The logic is as following: - First count the near processed cells in the subquery (named subquery) - Then extract the relevant rows (processed near cells = 8) from the master query. –  MTIhai Apr 30 '13 at 7:19

You can try something like this (this is for 4 neighbors, you can extend it to 8)

select x,y from pixels p
where (select 1 from pixels where p.x-1 = x and p.y = y) = 1
and (select 1 from pixels where p.x+1 = x and p.y = y) = 1
and (select 1 from pixels where p.x = x and p.y+1 = y) = 1
and (select 1 from pixels where p.x = x and p.y-1 = y) = 1
and processed = 0

The link with the output is here: http://sqlfiddle.com/#!3/dc889/2/0

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.