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


--
Sent via pgsql-sql mailing list (pgsql-sql@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-sql

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

--
Sent via pgsql-sql mailing list (pgsql-sql@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-sql

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.