data modeling - alternatives to NULL foreign key?

Question

I am currently working on a browser game. There is a map, each play has at least one village. Each spot on the map is either empty OR used by a village.

I have a map table with a list of all position in the map (empty and non empty spots).

My map table:

CREATE TABLE map (
 id serial NOT NULL,
 x_pos integer NOT NULL,
 y_pos integer NOT NULL,
 PRIMARY KEY (id),
 FOREIGN KEY (crop_type) REFERENCES. crop_types(id),
 UNIQUE (x_pos, y_pos)
);

my villages table:

CREATE TABLE villages (
 id serial NOT NULL,
 name VARCHAR(256) NOT NULL,
 population INT4 NOT NULL,
 owner_id INT NOT NULL,
 position_id INT NOT NULL,
 PRIMARY KEY (id),
 FOREIGN KEY (owner_id) REFERENCES users(id),
 FOREIGN KEY (position_id) REFERENCES map(id)
);

So each village has a position BUT not every position has a village on it. Right now, I am not sure what would be the proper way to be able to find a location is empty or not:

• empty: all the map.ids - villages.position_id = every empty spots
• non-empty: villages.position_id

Example:

map

id	x_pos	y_pos
1	34	55
2	10	15
3	08	89
4	65	12

villages

id	name	population	position_id
1	london	150	2
2	paris	320	3

Just to be more clear, every new user will have to choose a location to set up his village and of course, I will only give them the option to choose across empty spots.

This is one option that I may implement: add a new column to my map table, a foreign_key called village_id that represent the id column in the villages table. This will be an option FK so the value can be NULL because if a map location is free and does not have a village on it, the village_id will be NULL. My issues with this option:

• A lot of NULLS
• When a spot is going from the empty --> non-empty I have to update the village_id column in my map table.

map

CREATE TABLE map (
 id serial NOT NULL,
 x_pos integer NOT NULL,
 y_pos integer NOT NULL,
 village_id INT, /* new column */
 PRIMARY KEY (id),
 FOREIGN KEY (crop_type) REFERENCES crop_types(id),
 FOREIGN KEY (village_id) REFERENCES villages(id), /* new column details */ 
 UNIQUE (x_pos, y_pos)
);

id	x_pos	y_pos	village_id
1	34	55	NULL (empty)
2	10	15	1 (london)
3	08	89	2 (paris)
4	65	12	NULL (empty)

Is this an appropriate option?

In the game process, a lot of queries will be "what are the current available spots available to set up my new village"

Answer 1

In my opinion, it doesn't really matter. If the foreign key is on villages (and pointing to map), it will be efficient enough to find all the spots on the map without a village, as long as there is an index on villages.position_id:

select
 m.*
from
 map as m
where
 not exists(select from villages as v where v.position_id = m.id)
;

Since each spot on the map can be used only once, you can make villages.position_id UNIQUE, which will take care of the index you need for decent performance:

CREATE TABLE villages (
 id serial NOT NULL,
 name VARCHAR(256) NOT NULL,
 population INT4 NOT NULL,
 owner_id INT NOT NULL,
 position_id INT NOT NULL UNIQUE, -- Added UNIQUE
 PRIMARY KEY (id),
 FOREIGN KEY (owner_id) REFERENCES users(id),
 FOREIGN KEY (position_id) REFERENCES map(id)
);