Thread: unique index for periods

Hello,

I try to create an unique index for a (time)period, and my goal is to
prevent two overlapping periods in a row.

For this I created a type with following command:

CREATE TYPE period AS
   ("first" timestamp with time zone,
    "next" timestamp with time zone);

To use the btree index I added a compare function:

CREATE OR REPLACE FUNCTION period_compare(period, period)
  RETURNS integer AS $BODY$

begin
   raise info 'compare % <=> % = %', $1, $2,
      CASE
         WHEN $1.next <= $2.first THEN -1
         WHEN $2.next <= $1.first THEN 1
         ELSE 0
      END;

   return
      CASE
         WHEN $1.next <= $2.first THEN -1
         WHEN $2.next <= $1.first THEN 1
         ELSE 0
      END;
end

$BODY$ LANGUAGE 'plpgsql' IMMUTABLE STRICT COST 1;

After this I created a operator class:

CREATE OPERATOR CLASS period_overlap
   DEFAULT FOR TYPE period USING btree AS
   FUNCTION 1 period_compare(period, period);

To test everything I use this table:

CREATE TABLE p (
  p period NOT NULL,
  CONSTRAINT p_pkey PRIMARY KEY (p)
);

Now I fill the table with data:

DELETE FROM p;
-- clean up
VACUUM p;

INSERT INTO p VALUES (('-infinity', 'today')::period);
-- this one fails
-- INSERT INTO p VALUES (('-infinity', 'infinity')::period);

DELETE FROM p;
-- the index tree is still there, why?

INSERT INTO p VALUES (('-infinity', 'infinity')::period);
-- intersects with the deleted value, so compare returns 0
-- and the data goes to the left side of the tree

-- this one should fail
INSERT INTO p VALUES (('today', 'infinity')::period);
-- but this one is bigger than the deleted value, goes to
-- the right side of the tree and is not compared to the
-- entry inserted above.

What do I do wrong? Is there another solution to solve my problem?

Thanks,
  Gerhard

In article <20090820065819.GA2598@gheift.kawo1.rwth-aachen.de>,
Gerhard Heift <ml-postgresql-20081012-3518@gheift.de> writes:

> Hello,
> I try to create an unique index for a (time)period, and my goal is to
> prevent two overlapping periods in a row.

> ...

> Is there another solution to solve my problem?

Have a look at http://pgfoundry.org/projects/temporal

Gerhard Heift <ml-postgresql-20081012-3518@gheift.de> writes:
> I try to create an unique index for a (time)period, and my goal is to
> prevent two overlapping periods in a row.

> To use the btree index I added a compare function:

>    return
>       CASE
>          WHEN $1.next <= $2.first THEN -1
>          WHEN $2.next <= $1.first THEN 1
>          ELSE 0
>       END;

This does not work as a btree compare function, because it fails to
satisfy the basic requirements of a total order.  In particular it
doesn't satisfy the transitive law that A=B and B=C must imply A=C.

I don't believe it is possible to use a btree index for this purpose,
because there just isn't a way to express "overlaps" as a total order.
It'd be really nice to have uniqueness support in gist indexes someday
...

            regards, tom lane

On Thu, Aug 20, 2009 at 3:14 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:
> I don't believe it is possible to use a btree index for this purpose,
> because there just isn't a way to express "overlaps" as a total order.

That's true for the general case of indexing ranges but I don't think
that's true for the case where overlaps are illegal. In such a case
you could just, sorting by the start point, compare the previous
entry's end point with your start point and the next entry with your
end point.

However that's not the way unique indexes work in Postgres so
supporting that would require a lot of new abstractions and code, not
just a new opclass.

--
greg
http://mit.edu/~gsstark/resume.pdf

Greg Stark <gsstark@mit.edu> writes:
> On Thu, Aug 20, 2009 at 3:14 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:
>> I don't believe it is possible to use a btree index for this purpose,
>> because there just isn't a way to express "overlaps" as a total order.

> That's true for the general case of indexing ranges but I don't think
> that's true for the case where overlaps are illegal.

Uh, no, the question is not about whether there are expected to be any
overlapping entries in the index.  The point is that "overlaps" simply
does not fit the semantic model of a btree-processable equality
relationship.

> In such a case
> you could just, sorting by the start point, compare the previous
> entry's end point with your start point and the next entry with your
> end point.

Even if you hacked the code to work like that, it'll fail completely for
deferred unique constraints, not to mention deleted entries that haven't
yet been purged from the index.

            regards, tom lane

On Thu, 2009-08-20 at 13:35 +0200, Harald Fuchs wrote:
> Have a look at http://pgfoundry.org/projects/temporal

The temporal project on pgfoundry only provides the time period type,
which is (hopefully) useful, but it does not help with a non-overlapping
constraint.

Please see my other project here:

https://commitfest.postgresql.org/action/patch_view?id=132

I have a working patch already, and I plan to get it cleaned up so that
it can make it into 8.5.

Regards,
    Jeff Davis