patternsqlMinor

Non-overlapping rectangles constrained to a boundary

Submitted by: @import:stackexchange-dba·Mar 10, 2026·

Viewed 0 times

rectanglesnonconstrainedboundaryoverlapping

Problem

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:

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

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

Solution

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



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

Code Snippets

CREATE EXTENSION btree_gist;

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

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

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

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

Context

StackExchange Database Administrators Q#59399, answer score: 5

Revisions (0)

No revisions yet.