Conway's Game of Life in SQL, Part 2

I showed my implementation of Conway's Game of Life in SQL to a few people, a co-worker pondered if it could be done without the stored procedure.  I gave it some thought, and came up with an implementation that relies on views. I used views for the simple reason that it made things easier to see and understand.  If a query can be written using views, the it can be written as straight SQL, but the results are generally uglier, messier, and can often be unreadable.  Since I'm using MySQL, I realize how bad views can be when it comes to performance, but since this is a proof of concept, and a toy anyway, I'm not too worried.  I honestly doubt any real-life application would ever require me to implement the Game of Life in SQL!

I started as I had earlier, by defining the table as holding all the live cells for each generation.

create table cell (
  generation int,
  x int, 
  y int,
  primary key (generation, x, y));

Then, I created a view to represent all the candidate position on the grids where we might find live cells on the next generation.  We can only find cells where there are cells for the current generation, and in all 8 neighbour positions of those cells:

create view candidate (generation, x, y) as 
  select generation, x-1, y-1 from cell union
  select generation, x,   y-1 from cell union
  select generation, x+1, y-1 from cell union
  select generation, x-1, y   from cell union
  select generation, x,   y   from cell union
  select generation, x+1, y   from cell union
  select generation, x-1, y+1 from cell union
  select generation, x,   y+1 from cell union
  select generation, x+1, y+1 from cell;

Next, I counted the number of live cells in the 3x3 square around each candidate.  This isn't quite the same as counting the neighbours, since it includes the current cell in the count.  We will need to take that into account in a bit.

create view neighbour_count (generation, x, y, count) as 
  select generation, x, y, 
         (select count(*) 
          from cell 
         where cell.x in (candidate.x-1, candidate.x, candidate.x+1)
           and cell.y in (candidate.y-1, candidate.y, candidate.y+1)
           and not (cell.x = candidate.x and cell.y = candidate.y)
           and cell.generation = candidate.generation)
    from candidate;

From the previous post, the rules of the game can be reduced to: a cell is alive in the next generation if

1. it has 3 neighbours
2. it has 2 neighbours and was alive in the current generation

Let's write this as a truth table:

Live?	Neighbours	Alive in the next generation
yes	less than 2	no
yes	2	YES
yes	3	YES
yes	more than 3	no
no	less than 3	no
no	3	YES
no	more than 3	no

If we count the cell in the neighbour count, we change our truth table:

Live?	# cells in 3x3 square	Alive in the next generation
yes	less than 3	no
yes	3	YES
yes	4	YES
yes	more than 4	no
no	less than 3	no
no	3	YES
no	more than 3	no

A cell will be alive in the next generation if it's alive and the number of live cells in the square is 3 or 4, or if the cell is dead and there are 3 cells in the square.  Let's rewrite the rules... again.

A cell will be alive in the next generation if

1. The 3x3 square has exactly 3 cells
2. The 3x3 square has exactly 4 cells and the current cell is alive.

So, we'll include a cell in the next generation according to these rules.  We can tell if a cell is alive by doing a left outer join on the cell table:

insert into cell (
  select neighbour_count.generation+1, neighbour_count.x, neighbour_count.y 
  from neighbour_count 
         left outer join cell 
              on neighbour_count.generation = cell.generation
             and neighbour_count.x = cell.x
             and neighbour_count.y = cell.y
  where neighbour_count.generation = (select max(generation) from cell)
    and (neighbour_count.count = 3 
         or (neighbour_count.count = 4 and cell.x is not null)));

Repeat the insert statement for each following generation.