SQL CHECK constraint to prevent date overlap

In PostgreSQL 8.4 this can only be solved with triggers. The trigger will have to check on insert/update that no conflicting rows exist. Because transaction serializability doesn't implement predicate locking you'll have to do the necessary locking by yourself. To do that SELECT FOR UPDATE the row in the machines table so that no other transaction could be concurrently inserting data that might conflict.

In PostgreSQL 9.0 there will be a better solution to this, called exclusion constraints (somewhat documented under CREATE TABLE). That will let you specify a constraint that date ranges must not overlap. Jeff Davis, the author of that feature has a two part write-up on this: part 1, part 2. Depesz also has some code examples describing the feature.

In the meantime (since version 9.2 if I read the manual correctly) postgreSQL has added support for rangetypes.

With those rangetypes the issue suddenly becomes very simple (example copied from the manual):

CREATE TABLE reservation (
    during tsrange,
    EXCLUDE USING gist (during WITH &&)
);

And that's it. Test (also copied from the manual):

INSERT INTO reservation VALUES
    ('[2010-01-01 11:30, 2010-01-01 15:00)');

INSERT 0 1

INSERT INTO reservation VALUES
    ('[2010-01-01 14:45, 2010-01-01 15:45)');

ERROR: conflicting key value violates exclusion constraint "reservation_during_excl" DETAIL: Key (during)=(["2010-01-01 14:45:00","2010-01-01 15:45:00")) conflicts with existing key (during)=(["2010-01-01 11:30:00","2010-01-01 15:00:00")).