Thread: proposal: operator exclusion constraints with cardinality

proposal: operator exclusion constraints with cardinality

From
Jeff Davis
Date:
I have completed the open issues (that I'm aware of) for operator
exclusion constraints:

http://archives.postgresql.org/message-id/1257101600.27737.159.camel@jdavis

I'd now like to propose an extension to that feature: cardinality
limits.

It could go something like this (syntax still open for discussion, for
illustration only):
 EXCLUSION (room     CHECK WITH =,            attendee CHECK WITH =,            during   CHECK WITH &&)   CARDINALITY
30

To mean that at most 30 attendees can be signed up for the same room at
overlapping times.

I have hacked up a basic prototype just to make sure the semantics can
work reasonably well. I haven't implemented the syntax or catalog
changes yet, but the basic semantics with a hard-coded cardinality seem
to hold up.

Thoughts?

Regards,Jeff Davis



Re: proposal: operator exclusion constraints with cardinality

From
Tom Lane
Date:
Jeff Davis <pgsql@j-davis.com> writes:
> It could go something like this (syntax still open for discussion, for
> illustration only):

>   EXCLUSION (room     CHECK WITH =,
>              attendee CHECK WITH =,
>              during   CHECK WITH &&)
>     CARDINALITY 30

There's an old design principle that says "the only good numbers in
computer science are 0, 1, and N" -- that is, if you need to allow more
than one of something, you should have no hard-wired upper bound on
how many of them you allow.  The reason that meme comes to mind is that
I'm having difficulty seeing applications for this type of constraint.
I can certainly believe that people might like to enforce constraints
like "no more than N people are signed up for class X".  The problem is
that they won't want the *same* N for every class, and that's what this
constraint design seems to require.  What they'll want is N drawn from
some other table entry about the size of the classroom.  If you can't
support that then the design isn't fully baked yet.

(Of course, the reason UNIQUE constraints are good is that they
correspond to the number 1 ;-))
        regards, tom lane


Re: proposal: operator exclusion constraints with cardinality

From
Robert Haas
Date:
On Sun, Nov 1, 2009 at 10:49 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Jeff Davis <pgsql@j-davis.com> writes:
>> It could go something like this (syntax still open for discussion, for
>> illustration only):
>
>>   EXCLUSION (room     CHECK WITH =,
>>              attendee CHECK WITH =,
>>              during   CHECK WITH &&)
>>     CARDINALITY 30
>
> There's an old design principle that says "the only good numbers in
> computer science are 0, 1, and N" -- that is, if you need to allow more
> than one of something, you should have no hard-wired upper bound on
> how many of them you allow.  The reason that meme comes to mind is that
> I'm having difficulty seeing applications for this type of constraint.
> I can certainly believe that people might like to enforce constraints
> like "no more than N people are signed up for class X".  The problem is
> that they won't want the *same* N for every class, and that's what this
> constraint design seems to require.  What they'll want is N drawn from
> some other table entry about the size of the classroom.  If you can't
> support that then the design isn't fully baked yet.
>
> (Of course, the reason UNIQUE constraints are good is that they
> correspond to the number 1 ;-))

Following that thought, in this particular case it seems like you could do:
EXCLUSION (room     CHECK WITH =,             attendee CHECK WITH =,             foobar CHECK WITH =,
during  CHECK WITH &&) 
and then also
CHECK (foobar >= 1 AND foobar <= 30)

I'm a bit baffled by what this constraint is trying to represent,
actually.  I would have thought that the example would be room and
during constrained to a quantity of 30, and the solution would be to
have attendee.  Since you already have attendee as part of the
constraint, I'm a little mystified as to what the quantity of 30 is
supposed to represent, but it any case it seems like you can get the
effect with an extra field - which also allows you to do things like
variable room-sizes (by setting up triggers that arrange to copy the
room size into a column of your scheduling table so that you can then
check that the attendee number is less than the room size).

...Robert


Re: proposal: operator exclusion constraints with cardinality

From
Jeff Davis
Date:
On Sun, 2009-11-01 at 22:49 -0500, Tom Lane wrote:
> you should have no hard-wired upper bound on
> how many of them you allow.

You're right. I saw something that looked easy to implement, but in
practice it wouldn't be very useful.

Regards,Jeff Davis



Re: proposal: operator exclusion constraints with cardinality

From
Jeff Davis
Date:
On Sun, 2009-11-01 at 23:09 -0500, Robert Haas wrote:
> Following that thought, in this particular case it seems like you could do:
> 
>  EXCLUSION (room     CHECK WITH =,
>               attendee CHECK WITH =,
>               foobar CHECK WITH =,
>               during   CHECK WITH &&)
> and then also
> CHECK (foobar >= 1 AND foobar <= 30)

...

>  Since you already have attendee as part of the
> constraint, I'm a little mystified as to what the quantity of 30 is
> supposed to represent,

Yes, that was wrong, attendee shouldn't have been in the constraint.

> but it any case it seems like you can get the
> effect with an extra field 

That's one way to do it, but then you have to assign numbers to all
attendees, which creates a new contention problem.

If using discrete time slots aligned to the hour, for instance, you
could increment a field in the "room" table every time an attendee was
added, and then use a CHECK constraint to limit that field. The fact
that updates follow the chain of concurrent updates makes that work
nicely.

That doesn't seem to work for general overlapping and unaligned time
periods, however.

Regards,Jeff Davis