On the basis that knowing some more about Graph Theory won’t do me any harm when thinking about operating system behaviour, I am reading about that too right now.

But I found the book’s explanation of a Graph Cartesian Product rather less than full, so here is my attempt to make it a bit clearer.

Say we have graph with vertices and graph with vertices , then our cartesian product graph is with vertices

I am continuing to work my way through A. K. Dewdney‘s New Turing Omnibus – some bits are very familiar and not so interesting, but there are lots of fascinating parts and it is another book I wish I’d read two years ago, before I started the MSc. (Update: you may want to read this).

Anyway, I have just been reading Dewdney’s discussion of how the Mariner probes to Mars used error correction to send back their photographs to Earth. The discussion slightly dates the book – but took me back to my childhood (which doesn’t seem that long ago!) and reading about the probes and what was then thought of as the complex problem of decoding the signals (indeed, Dewdney remarks that specialist hardware had to be used to manage the 16kbs bit stream from the probes).

And where, according to the book is the “cartesian product” of the matrices.

I struggled a bit to work out what a cartesian product of two matrices might be, especially as there seemed to be no definition of such a thing available online. I made a guess (a pretty good one) though and then looked further afield and the standard term for the product appears to “kronecker product” – shown as below (which is pretty much where I was with my guess):

And

And so on… the Mariner probe used which is a 32 x 32 matrix – meaning each possible data signal corresponded to a row (or column) in the matrix – and so that row was sent instead of the data.

The reason this matrix was chosen is because every row, or column, is an orthogonal vector with respect to every other row or column, or, if you like, for the 32 x 32 matrix, each row or column is different in 16 different places from every other row or column.

This means that signals can be wrong in up to 7 different bits and yet it is still relatively simple to pick what the correct signal was meant to be (ie vectors, or rows, have a Hamming distance of 16.)

SELECT K.BATTLE
FROM
(SELECT S.name AS SHIP, B.name AS BATTLE, C.country AS COUNTRY
FROM
Ships S, Classes C, Battles B, Outcomes O
WHERE
S.class = C.class AND O.battle = B.name AND O.ship = S.name) K CROSS JOIN
(SELECT S.name AS SHIP, B.name AS BATTLE, C.country AS COUNTRY
FROM
Ships S, Classes C, Battles B, Outcomes O
WHERE
S.class = C.class AND O.battle = B.name AND O.ship = S.name) J
WHERE K.COUNTRY = J.COUNTRY AND K.BATTLE = J.BATTLE
GROUP BY K.BATTLE
HAVING COUNT(K.BATTLE) >=9

But it’s still not perfect, because it would record a positive answer if a single ship from 9 countries took part in a battle or two ships from three countries (something that certainly took place in the Pacific).

So I cheated and looked for clues – and this works properly:

SELECT K.BATTLE
FROM
(SELECT S.name AS SHIP, B.name AS BATTLE, C.country AS COUNTRY
FROM
Ships S, Classes C, Battles B, Outcomes O
WHERE
S.class = C.class AND O.battle = B.name AND O.ship = S.name) K
GROUP BY K.BATTLE
HAVING COUNT(K.COUNTRY) >=3

This is based on a solution to a similar problem found in Database Management Systems, Third Edition, though, unfortunately, that book prints a solution that is not relational algebra at all, as it relies on the order in which results are returned (relational algebra is a form of set algebra and sets have no order).

(Rename the attributes in TEMP1 – this is the step that is broken in the book)