Find empty positions in a grid

Question

In a Contents table, items are stored in X,Y coordinates:

Contents
-------
id
parent_id
pos_x
pos_y

Assume the container size is 3 by 3. I'd like to find which positions in a given container are free. So far I've generated a 2D matrix:

SELECT *
FROM 
    (SELECT rownum X FROM dual  CONNECT BY LEVEL <= 3 ) xaxis
INNER JOIN 
    (SELECT rownum Y FROM dual  CONNECT BY LEVEL <=3 ORDER BY 1) yaxis
ON xaxis.X <> yaxis.Y OR xaxis.X = yaxis.Y

Then I attempt to JOIN the queries together, excluding X,Y positions present in Contents:

SELECT X, Y
FROM 
    (SELECT rownum X FROM dual  CONNECT BY LEVEL <= 3 ) xaxis
INNER JOIN 
    (SELECT rownum Y FROM dual  CONNECT BY LEVEL <=3 ORDER BY 1) yaxis
ON xaxis.X <> yaxis.Y OR xaxis.X = yaxis.Y

INNER JOIN (
    SELECT pos_x, pos_y FROM Contents WHERE parent_id = ?) items
ON items.posx <> xaxis.X AND items.posy <> yaxis.Y;

This doesn't treat each pair as unique, and excludes values from all rows if a position is occupied. For example, assuming that (2, 2) is occupied, the above returns:

X   Y
-----
1   1
1   3
3   1
3   3

Essentially I'm trying to get the difference of the two sets. Any help appreciated.

Answer 1

I figured out the answer right before I posted the question, so I thought I'd post it and answer it at the same time. Stating the problem as get the difference of the two sets set me in the right direction.

The answer is the MINUS operator. Replace the final JOIN with MINUS and you get the intended results:

select X, Y
from 
    (select rownum X from dual  CONNECT BY LEVEL <= 3 ) xaxis
inner join 
    (select rownum Y from dual  CONNECT BY LEVEL <=3 order by 1) yaxis
on xaxis.X <> yaxis.Y OR xaxis.X = yaxis.Y

MINUS

select pos_x, pos_y FROM Contents WHERE parent_id = ?;

which returns the intended result (note the lack of (2, 2)):

X   Y
-----
1   1
1   2
1   3
2   1
2   3
3   1
3   2
3   3

Today was a good day

Answer 2

You could do this with an outer join rather than a minus (although you'd have to test both to find out which is more performant for your data!).

If you are only doing it for a single parent_id at a time, you would do:

WITH CONTENTS AS (SELECT 1 parent_id, 2 pos_x, 2 pos_y FROM dual UNION ALL
                  SELECT 2 parent_id, 2 pos_x, 1 pos_y FROM dual)
SELECT xaxis.x,
       yaxis.y
FROM   ((SELECT LEVEL x FROM dual CONNECT BY LEVEL <= 3) xaxis
        CROSS JOIN (SELECT LEVEL y FROM dual CONNECT BY LEVEL <= 3) yaxis)
       LEFT OUTER JOIN CONTENTS c ON c.pos_x = xaxis.x AND c.pos_y = yaxis.y AND c.parent_id = 1
WHERE  c.parent_id IS NULL
ORDER BY x, y;

         X          Y
---------- ----------
         1          1
         1          2
         1          3
         2          1
         2          3
         3          1
         3          2
         3          3

Alternatively, if you want to run it for all parent_ids, you could use a partitioned outer join like so:

WITH CONTENTS AS (SELECT 1 parent_id, 2 pos_x, 2 pos_y FROM dual UNION ALL
                  SELECT 2 parent_id, 2 pos_x, 1 pos_y FROM dual)
SELECT c.parent_id,
       xaxis.x,
       yaxis.y
FROM   ((SELECT LEVEL x FROM dual CONNECT BY LEVEL <= 3) xaxis
        CROSS JOIN (SELECT LEVEL y FROM dual CONNECT BY LEVEL <= 3) yaxis)
       LEFT OUTER JOIN CONTENTS c PARTITION BY (c.parent_id) ON c.pos_x = xaxis.x AND c.pos_y = yaxis.y
WHERE  c.pos_x IS NULL
AND    c.pos_y IS NULL
ORDER BY c.parent_id,
         xaxis.x,
         yaxis.y;

 PARENT_ID          X          Y
---------- ---------- ----------
         1          1          1
         1          1          2
         1          1          3
         1          2          1
         1          2          3
         1          3          1
         1          3          2
         1          3          3
         2          1          1
         2          1          2
         2          1          3
         2          2          2
         2          2          3
         2          3          1
         2          3          2
         2          3          3