Thread: Index to enforce non-overlapping ranges?

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?

----
James Robinson
Socialserve.com

James Robinson <jlrobins@socialserve.com> writes:
>     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?

Nope, sorry.  Unique indexes enforce non-equality, but there's no way
to pretend that "overlaps" is an equality condition (hint: it's not
transitive).

I don't say that it'd be impossible to construct an index type that
could do this, but you won't get there with the pieces we have.
        regards, tom lane

jlrobins@socialserve.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.