Non-overlapping rectangles constrained to a boundary

I am trying to model placement of parts on a circuit board. Without any meaningful constraints, my basic schema looks like this:

``````create table part (
part_id bigserial primary key,
name text not null,
width double precision not null,
height double precision not null
);
create table board (
board_id bigserial primary key,
width double precision not null,
height double precision not null
);
create table board_part (
board_id bigint not null references board,
part_id bigint not null references part,
position point not null
);
``````

(SQL Fiddle, Visualization)

For `b` and `b2` any `board_part`s, I want to enforce the following constraints:

1. `b` lies on the board:

``````box(b.position, point(b.part.width,b.part.height))
<@ box(point(0,0), point(b.board.width,b.board.height))
``````
2. `b` and `b2` do not overlap if they lie on the same board:

``````b.board_id != b2.board_id or
not (box(b.position, point(b.part.width,b.part.height))
&& box(b2.position, point(b2.part.width,b2.part.height)))
``````

How can I achieve this (without too much data duplication)? Changing the schema is fine.

Here is my best attempt (SQL Fiddle), taking inspiration from Erwin's answer to my previous question. It enforces the constraints I wanted, but has a lot of duplicate data in the `board_part` table. I imagine I could write a function to fill in the `board_width`, `board_height`, `part_width`, and `part_height` fields automatically, but it still feels wrong having so much duplicate data around. Also, keying to the `width`/`height` fields feels like a hack.

I suggest the geometric type `box` and an exclusion constraint (Postgres 9.2+). Should be the perfect solution to your problem. It creates a GiST index implicitly that also supports certain queries.

Combine it with with equality on `board_id` to allow multiple boards in a single table. You'll need the additional module `btree_gist`. Once per database:

``````CREATE EXTENSION btree_gist;
``````

To confine parts to a board add a `CHECK` constraint. You need the confining box of the board in the `board_part` table (redundantly). Could look like this:

``````CREATE TABLE board_part (
board_id bigint NOT NULL REFERENCES board
, board_box box NOT NULL
, part_id bigint NOT NULL REFERENCES part
, part_box box NOT NULL
, EXCLUDE USING gist (board_id WITH =, part_box WITH &&)
, CHECK (part_box <@ board_box)
);
``````

The drawback: you need the dimensions of each part and box in table `board_part` redundantly.

To avoid redundant storage, I like this new idea better: Fake `IMMUTABLE` functions returning the box for an id and build constraints upon these functions. Your tables can make do with just the columns of your original design.

I ran a complete test to verify it works.

Complete schema

Base tables:

``````CREATE TABLE part (
part_id serial PRIMARY KEY
, part text NOT NULL
, wide int NOT NULL
, high int NOT NULL
);

CREATE TABLE board (
board_id serial PRIMARY KEY
, board text NOT NULL
, wide int NOT NULL
, high int NOT NULL
);
``````

`IMMUTABLE` functions:

``````CREATE OR REPLACE FUNCTION f_boardbox(_board_id int)
RETURNS box
LANGUAGE sql IMMUTABLE AS
'SELECT box(point(0,0), point (b.wide, b.high))
FROM   public.board b WHERE board_id = \$1';

CREATE OR REPLACE FUNCTION f_partbox(_part_id int, _wide int, _high int)
RETURNS box
LANGUAGE sql IMMUTABLE AS
'SELECT box(point(\$2,\$3), point(\$2 + p.wide, \$3 + p.high))
FROM   public.part p WHERE part_id = \$1';
``````

Replace `public` with the actual schema of your tables.
In Postgres 9.6 or later add `PARALLEL SAFE`. See:

Main table:

``````CREATE TABLE board_part (
board_id int NOT NULL REFERENCES board
, part_id int NOT NULL REFERENCES part
, wide int NOT NULL
, high int NOT NULL
, EXCLUDE USING gist (board_id WITH =, f_partbox(part_id, wide, high) WITH &&)
, CHECK (f_partbox(part_id, wide, high) <@ f_boardbox(board_id))
);
``````

Of course, if you update dimensions for a `board_id` or `part_id` in use, you partly void the index and / or constraint. You would need to recreate any index or constraint building on the promise that the return value of `IMMUTABLE` function never change. See:

However, you can avoid this expensive operation with triggers to update only affected rows:

Triggers

``````CREATE OR REPLACE FUNCTION f_board_upaft()
RETURNS trigger
LANGUAGE plpgsql AS
\$func\$
BEGIN
UPDATE board_part
SET    board_id = board_id        -- enough to trigger CHECK constraint
WHERE  board_id = NEW.board_id;   -- limit to relevant rows

RETURN NULL;
END
\$func\$;

CREATE TRIGGER board_upaft
AFTER UPDATE OF wide, high ON board  -- limit to relevant columns
FOR EACH ROW EXECUTE PROCEDURE f_board_upaft();

CREATE OR REPLACE FUNCTION f_part_upaft()
RETURNS trigger
LANGUAGE plpgsql AS
\$func\$
BEGIN
UPDATE board_part
SET    part_id = 0
WHERE  part_id = NEW.part_id;

UPDATE board_part
SET    part_id = NEW.part_id
WHERE  part_id = 0;               -- enough to update EXCL. constraint

RETURN NULL;
END
\$func\$;

CREATE TRIGGER part_upaft
AFTER UPDATE OF wide, high ON part
FOR EACH ROW EXECUTE PROCEDURE f_part_upaft();
``````

`part_id = 0` is a special row in table `part` with size 0. Needed for the trigger.

Test data:

``````INSERT INTO board (board, wide, high)
VALUES ('b1010',10,10), ('b2030',20, 30);

INSERT INTO part (part_id, part, wide, high)
VALUES (0,'p0',0,0);          -- special row needed for trigger!

INSERT INTO part (part, wide, high)
VALUES ('p11',1,1), ('p33',3,3);

INSERT INTO board_part (board_id, part_id, wide, high)
VALUES (1,1,3,3)
, (1,1,5,5)   -- no overlap, inside board
, (2,1,3,3);  -- different board, no overlap
``````

Test

These must raise exceptions if the triggers & constraints do their job:

``````UPDATE part SET wide = 6 , high = 6
WHERE  part_id = 1;            -- violates EXCL. & CHECK constraint

UPDATE part SET wide = 3 , high = 3
WHERE  part_id = 1;            -- violates EXCL. constraint

UPDATE board SET wide = 2 , high = 2
WHERE  board_id = 1;            -- violates CHECK constraint
``````

db<>fiddle here
Old sqlfiddle

• That looks pretty similar to what I came up with, apart from the use of `box` instead of scalar width/height. The problem with this approach is how ugly the foreign keys get when you try to enforce that `width(b.part_box) = b.part.width and height(b.part_box) = b.part.height` (I apologize for not making it clear that I wanted to enforce that.) I'll look into your suggestion to use triggers. I'm not very familiar with triggers, so I'll return to this in a day or two when I get the basics down. Thanks for all your help on this! Feb 22, 2014 at 15:05
• @Snowball: I added a new idea to avoid redundant columns. Feb 23, 2014 at 23:08