Skip site navigation (1) Skip section navigation (2)

Re: Index to enforce non-overlapping ranges?

From: Chris Browne <cbbrowne(at)acm(dot)org>
To: pgsql-sql(at)postgresql(dot)org
Subject: Re: Index to enforce non-overlapping ranges?
Date: 2008-05-08 14:31:25
Message-ID: 60tzh8hnpe.fsf@dba2.int.libertyrms.com (view raw or flat)
Thread:
Lists: pgsql-sql
jlrobins(at)socialserve(dot)com (James Robinson) writes:
> Academic question here:
>
> 	Given a table with a pair of any sort of line-segment-esqe
> range  delimiter columns, is it possible to build a unique index to
> enforce  non-overlapping ranges? Such as:
>
> 	create table test
> 	(
> 		id int not null primary key,
> 		low_value int not null,
> 		high_value int not null
> 	);
>
> 	Can one build an index to enforce a rule such that no
> (low_value,  high_value) range is identical or overlaps with another
> (low_value,  high_value) range described by the table? And, more
> interestingly,  what about for ranges of dates / timestamps as opposed
> to simple  integers?
>
> 	I can see how a trigger on insert or update could enforce such
> a  constraint [ probe the table for an existing overlapping row, and
> raise exception one exists ], but can such an activity be performed
> with fewer lines using some sort of r-tree index?

Aside: A constraint won't do what you want, because a CHECK constraint
can only reference the columns of the current row.

This is a useful sort of thing to have in a temporal database, where
you might want to add temporal constraints to what was originally a
stateful table which had an ordinary primary key.

Thus, we might start with table:

create table state_of_something (
  id serial primary key,
  att1 text,
  att2 text,
  att3 text
);

and want to make it temporal.  The temporal equivalent (well, *one*
temporal equivalent; there's several ways to treat this) would be:

create table temporal_state_of_something (
  id serial,
  att1 text,
  att2 text,
  att3 text,
  from_date timestamptz,
  to_date timestamptz
);

where the requirement, for any given id value, is for there to be a
series of non-overlapping (from_date,to_date) intervals.

A *vague* approximation that is easy to do is to have a new primary
key:

create table temporal_state_of_something (
  id serial,
  att1 text,
  att2 text,
  att3 text,
  from_date timestamptz,
  to_date timestamptz,
  primary key (id, from_date),
  constraint from_to check (to_date >= from_date)
);

That doesn't prevent there from being overlapping ranges, such as
(id,from_date_to_date) tuples like:

  (151,'2007-01-01','2009-01-01') and (151 '2008-01-01','2008-02-02')

I'm not sure that this is *so* different from a regular foreign key
constraint that it wouldn't be reasonable to handle it via a trigger.
It's certainly a more complex trigger function, but the pattern will
be pretty common.
-- 
output = ("cbbrowne" "@" "linuxfinances.info")
http://linuxdatabases.info/info/linuxdistributions.html
Those who do not learn from history, loop.

In response to

pgsql-sql by date

Next:From: Tom LaneDate: 2008-05-08 14:54:21
Subject: Re: Index to enforce non-overlapping ranges?
Previous:From: James RobinsonDate: 2008-05-08 13:27:52
Subject: Index to enforce non-overlapping ranges?

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group