9.6 Feature help requested: Inclusion Constraints

I believe Inclusion Constraints will be important for postgres.
Unfortunately, my time has been scarce lately, so without help it may
miss 9.6 as well. If someone is interested in working on this with me to
deliver a good submission in a couple months, please let me know.

The idea is to make a generalized form of foreign keys, just like
exclusion constraints are a generalized form of unique constraints.

=======
Syntax:
=======

(see attachment for more specifics)

INCLUDE [ USING index_method ]
( exclude_element WITH operator [, ... ] )
REFERENCES reftable [ ( refcolumn [, ... ] ) ]
[ MATCH FULL | MATCH PARTIAL | MATCH SIMPLE ]
index_parameters [ WHERE ( predicate ) ]

Notice the WHERE clause, which is missing from FKs.

==========
Example #1
==========

-- e.g. "Super Bowl"
create table event (
event_id int8,
title text,
eduring tstzrange,
exclude using gist (event_id with =, eduring with &&)
);

-- e.g. "Catch on one yard line"
create table event_highlight (
event_id int8,
description text,
hduring tstzrange,
exclude using gist (event_id with =, hduring with &&),
include using gist (event_id with =, hduring with <@)
references event (event_id, eduring)
);

Ensure that the hduring is always contained (<@) in some eduring with
the same event_id.

==========
Example #2
==========

create table asset_ownership (
asset_id INT8,
owner_id INT8,
during tstzrange,
exclude using gist (asset_id with =, during with &&),
include using gist (asset_id with =, during with -|-)
references asset_possession (asset_id, during)
where (not lower_inf(during))
);

Ensure that assets in a business are always in the possession of some
responsible party. Here we require that every possession period is
adjacent (-|-) to some other possession period for the same asset,
unless there is no lower bound.

============
Limitations:
============

I don't see a good way to make cascading updates work, as Peter pointed
out in a previous discussion:

http://www.postgresql.org/message-id/1288113924.22800.4.camel@vanquo.pezone.net

And cascading deletes would be a little strange, as well. I think it's
better to just only support ON UPDATE/DELETE NO ACTION. If someone sees
a use case here that is not too specific, we can always try to add
support for something like that later.

We could support ON UPDATE/DELETE RESTRICT, too, but that can be
accomplished by making it IMMEDIATE (unless I'm missing some subtlety).

===========
Challenges:
===========

I think the biggest technical challenge will be to account for the case
where the a referencing tuple has multiple matches on the referenced
side. This is similar to the challenge of supporting MATCH PARTIAL with
FKs, which is, I assume, why we don't support that yet.

It *seems* solvable, but I haven't looked in detail yet.

Another approach would be to try to enforce the idea that there is only
one match on the referenced side, using an exclusion constraint. I
rejected this approach because:

* Notice in example #1 that the exclusion constraint on the referenced
side uses the overlaps operator (&&), while the inclusion constraint
uses the "contained by" operator (<@). Postgres currently has no way to
know that those two operators have a special relationship that ensures
only one match on the referenced side. I don't even know the name for
that relationship, so asking users to declare such a relationship seems
a little much.
* It seems like it might eliminate some legitimate use cases.
* We could get MATCH PARTIAL support as a result of this work.

================
Work to be done:
================

The rest of the work seems similar in scope to Exclusion Constraints
(0cb65564):
- parse analysis work
- catalog work
- dump/reload support
- compare performance of a trivial inclusion constraint to a FK
- ensure that deadlocks are not too common
- add tests

Any takers?

Regards,
Jeff Davis