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 have a database table AB which tracks the association of A and B over time:

create table AB columns (
   ARef ...,  -- FK of A
   BRef ...,  -- FK of B
   Since as Timestamp,
   Until as Timestamp,
   SomeAttrib1 ...,
   SomeAttrib2 ...
);

I would like to declare a unique key such that the same A and B can only be associated together once during the same interval.

What strategies might I use for expressing such a constraint? Clearly, just doing a PK on ARef,BRef,Since,Until will not suffice - that would only prevent duplicates of the exact same interval. I need to consider how a row's interval overlaps or does not overlaps with the intervals of other rows in the table.

Parameters to consider:

  • I am using SQL Server 2012, but I'm also interested to know what facilities are available in other RDBMS's.
  • Although I realise that keeping this 'history' or 'time dimension' could be considered an 'analytical' use of a database, I'm not wanting a solution that uses a 'dimension' or 'cube' ... this is an ordinary transactional database for an application which needs to assign different attributes to associations which occur at different times.
  • I'm not heavily committed to the timestamps ... happy to consider 'interval' datatypes if they would help.
share|improve this question
    
Postgres' exclusion constraints were created for specifically that reason: de.slideshare.net/pgconf/not-just-unique-exclusion-constraints –  a_horse_with_no_name Jan 11 at 13:03

2 Answers 2

I was thinking because this was a calculation it'd have to be a trigger but in doing some googling there are better options.

Overlapping intervals look like they can be blocked by a particular pattern of constraints (http://sqlblog.com/blogs/alexander_kuznetsov/archive/2009/03/08/storing-intervals-of-time-with-no-overlaps.aspx)

This slideshare walks through 'Exclusion' constraints which are part of PostgreSQL 9.0 and above and also touches on the pitfalls of approaches like triggers (http://www.slideshare.net/pgconf/not-just-unique-exclusion-constraints)

This post titled 'Non-Overlapping Dates Constraint' covers several approaches for Oracle (http://jeffkemponoracle.com/2012/08/30/non-overlapping-dates-constraint/)

My Google search query was 'unique time interval constraint database'

share|improve this answer
    
To summarise, this is a 'cross row' data-integrity constraint which references other rows in the table. The SQL92 standard has an ASSERTION feature to do this and more, but RDBMS's lack support. A correct trigger-based implementation (remember, we are enforcing integrity-constraints) would necessarily need to SERIALIZE the transaction. Despite these challenges, PostgreSQL provides a fast, less-general mechanism only for when rows in the same table 'conflict'. Leaving us with sqlblog.com/blogs/alexander_kuznetsov/archive/2009/03/08/…). –  David Bullock Jan 11 at 14:06
    
@DavidBullock It's a useful reference, but Alexander Kuznetsov's solution requires a different table design. Is it strictly necessary? –  Iain Elder Jan 11 at 16:14
    
@IainElder I'd prefer that SQL Server had a feature like the PostgreSQL 'Exclusion Constraints', but I really do so want the database to enforce data consistency, I'd consider hacking up my model to get it. –  David Bullock Jan 12 at 4:07

Modeling intervals

In SQL Server timestamp is a synonym for rowversion. It gives each row a unique version number. It's more like an identity or a sequence than an instant of time. Are you sure that's the type you want?

SQL Server has no native interval data type. The standard way to model an interval is to use two columns of the same date and time type. The best type for you depends on your precision and time zone requirements.

Sample data

I assume you have sample data like this. For simplicity I've ignored what A and B refer to.

CREATE TABLE AB (
  A INT NOT NULL,
  B INT NOT NULL,
  Since DATE NOT NULL,
  Until DATE NOT NULL,
  SomeAttrib1 INT NOT NULL,
  SomeAttrib2 INT NOT NULL
);

INSERT INTO AB VALUES
  (1, 1, '2014-01-11', '2014-01-18', 1, 2),
  (1, 1, '2014-01-12', '2014-01-17', 3, 4),
  (1, 1, '2014-01-14', '2014-01-21', 5, 6), 
  (1, 1, '2014-01-09', '2014-01-14', 7, 8),
  (2, 2, '2014-01-01', '2014-01-08', 9, 10),
  (2, 2, '2014-01-08', '2014-01-15', 11, 12),
  (2, 2, '2014-01-15', '2014-01-22', 13, 14);

Query to find overlaps

If the database doesn't check for overlaps automatically, you can still check manually using a query.

You can match each row to the others that overlap it with a query like this:

SELECT
  original.A AS A1,
  original.B AS B1,
  original.Since AS Since1,
  original.Until AS Until1,
  overlap.A AS A2,
  overlap.B AS B2,
  overlap.Since AS Since2,
  overlap.Until AS Until2
FROM AB AS original
INNER JOIN AB AS overlap ON (
  -- match same time series
  original.A = overlap.A AND
  original.B = overlap.B AND

  -- overlapping, not just touching
  original.Until > overlap.Since AND
  overlap.Until > original.Since AND

  -- not exact duplicate
  original.Until <> overlap.Until AND
  original.Since <> overlap.Since
);

The query returns all the overlapping pairs of distinct rows.

It's adapted from Branko Dimitrijevic's similar answer on Stack Overflow.

If you consider touching to be a form of overlapping, you can use the 'greater than or equal to' operator instead of the 'greater than' operator in the second set of checks.

The third set of checks excludes the trivial case where each row overlaps exactly with itself, but it also excludes distinct rows that overlap exactly. The easiest way to catch those is to use a unique constraint (see next section).

For the sample data the query produces a result like this:

A1  B1  SINCE1  UNTIL1  A2  B2  SINCE2  UNTIL2
1   1   2014-01-11  2014-01-18  1   1   2014-01-09  2014-01-14
1   1   2014-01-12  2014-01-17  1   1   2014-01-09  2014-01-14
1   1   2014-01-12  2014-01-17  1   1   2014-01-11  2014-01-18
1   1   2014-01-14  2014-01-21  1   1   2014-01-11  2014-01-18
1   1   2014-01-09  2014-01-14  1   1   2014-01-11  2014-01-18
1   1   2014-01-11  2014-01-18  1   1   2014-01-12  2014-01-17
1   1   2014-01-14  2014-01-21  1   1   2014-01-12  2014-01-17
1   1   2014-01-09  2014-01-14  1   1   2014-01-12  2014-01-17
1   1   2014-01-11  2014-01-18  1   1   2014-01-14  2014-01-21
1   1   2014-01-12  2014-01-17  1   1   2014-01-14  2014-01-21

Intervals in the (1, 1) times series overlap in various ways.

There are no rows from the (2, 2) time series because they touch but don't overlap.

Now that you know where the overlaps are, you can remove them.

If you encounter overlaps infrequently and don't mind manual labor, this solution might be good enough.

Of course, it would be easier if you could get the database to avoid overlapping intervals automatically by rejecting conflicting rows.

Automate check with a trigger

A good first step is to add a unique constraint (the primary key you suggested is implicitly a unique constraint).

ALTER TABLE AB ADD CONSTRAINT AB_UniqueIntervals UNIQUE (A, B, Since, Until);

By itself the unique constraint forbids only new duplicates, not overlaps. It's still worth doing because the engine creates an index on the unique columns.

The index will help you to forbid other types of overlap more efficiently, especially if you have lots of non-key attributes in the table.

To check the rest of the conditions, you can use a trigger.

CREATE TRIGGER AB_CanTouchWithoutOverlap
ON AB
AFTER INSERT, UPDATE
AS
...

I leave it as an exercise to adapt the query into a trigger.

The unique index already catches exact duplicates, so you should be able to leave out such checks in the join.

You can use a function, but it's slow

The solution in the linked question uses a scalar function in a check constraint.

This would be very slow compared to a trigger when you insert many rows in bulk.

The trigger can check all the new rows in one go, but the function is called once per inserted row, which makes the engine do a lot more work.

share|improve this answer
    
@IanElder I was using 'Timestamp' in the general sense, and yes, DATETIME would be the realisation of this for SQL Server. The 'problem' with cross-row constraints like this is that the trigger considering whether there are any overlaps needs to consider uncommitted modifications in other transactions, and thus will require some attention to transaction isolation and opportunities for fine-grained explicit locking. (We wouldn't want a table-scan on the whole table holding a lock for every row involved in the SELECT). The links in Kevin's answer are worth reading, esp. the Oracle one. –  David Bullock Jan 12 at 6:33

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.