Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Basic answer

I suggest to use the geometric type box and combine that with an exclusion constraint (Postgres 9.2+). Should be the perfect solution to your problem. The GiST index this is implemented with (automatically) also supports certain queries.

Combine it with with equality on board_id to hold 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 AS
'SELECT box(point(0,0), point (b.wide, b.high))
 FROM public.board b WHERE board_id = $1'
LANGUAGE sql IMMUTABLE; 

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

Replace public with the actual schema of your tables.

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. More explanation for the technique in this related answer on SO:
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 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$ LANGUAGE plpgsql;

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 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$
  LANGUAGE plpgsql;

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

Its not possible to install extensions on SQLfiddle, so simplified exclusion constraint without btree_gist: SQLfiddle to play with.

share|improve this answer
    
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! –  Snowball Feb 22 at 15:05
    
@Snowball: I added a new idea to avoid redundant columns. –  Erwin Brandstetter Feb 23 at 23:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.