Non-overlapping rectangles constrained to a boundary

Question

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_parts, 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.

Answer 1

Basic answer

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)
);

&& .. "overlaps" operator
<@ .. "contained" operator

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

Advanced answer

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:

• When to mark functions as PARALLEL RESTRICTED vs PARALLEL SAFE?

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:

• Does PostgreSQL support “accent insensitive” collations?

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}