Allow composite foreign keys to reference a superset of unique constraint columns?

Hey, hackers!

While working with some foreign keys, I noticed some mildly unexpected
behavior. The columns referenced by a unique constraint must naturally
have a unique constraint on them:

CREATE TABLE foo (a integer);
CREATE TABLE bar (x integer REFERENCES foo(a));
> ERROR: there is no unique constraint matching given keys for referenced
table "foo"

But Postgres doesn't allow a foreign key to reference a set of columns
without a unique constraint, even if there a unique constraint on a
subset of those columns (i.e., it doesn't allow referencing a superset
of a unique constraint).

CREATE TABLE foo (a integer PRIMARY KEY, b integer);
CREATE TABLE bar (x integer, y integer, FOREIGN KEY (x, y) REFERENCES
foo(a, b));
> ERROR: there is no unique constraint matching given keys for referenced
table "foo"

It seems to me like there would be nothing wrong in this case to allow this
foreign key constraint to exist. Because there is a unique constraint on foo(a),
foo(a, b) will also be unique. And it doesn't seem like it would be too complex
to implement.

Neither MATCH SIMPLE nor MATCH FULL constraints would have any issues
with this. MATCH PARTIAL may, but, alas, it's not implemented. (I've had
a few ideas about foreign keys, and MATCH PARTIAL seems to always come
up, and I still don't understand what its use case is.)

A real-world use case that uses denormalization could run into this. Imagine a
naive music database that has a list of artists, albums, and songs, where each
album is by one artist and each song is on one album, but we still store a
reference to the artist on each song:

CREATE TABLE artists (id serial PRIMARY KEY, name text);
CREATE TABLE albums (id serial PRIMARY KEY, artist_id REFERENCES
artists(id) name text);
CREATE TABLE songs (
id serial PRIMARY KEY,
artist_id REFERENCES artists(id) ON DELETE CASCADE,
album_id REFERENCES albums(id) ON DELETE CASCADE,
name text,
);

To ensure that artist deletions are fast, we need to create an index on
songs(artist_id) and songs(album_id). But, suppose we wanted to save on index
space, and we never needed to query JUST by album_id. We could then do:

CREATE TABLE songs (
id serial PRIMARY KEY,
artist_id REFERENCES artists(id) ON DELETE CASCADE,
album_id integer,
name text,
FOREIGN KEY (artist_id, album_id) REFERENCES albums(artist_id, id)
ON DELETE CASCADE
);

And then we could have a single index on songs(artist_id, album_id) that would
serve both ON CASCADE DELETE triggers:

-- Delete artist
DELETE FROM songs WHERE artist_id = <artist.id>;
-- Delete artist
DELETE FROM songs
WHERE artist_id = <album.artist_id> AND album_id = <album.id>;

But Postgres wouldn't let us create the composite foreign key described.

It seems like a somewhat useful feature. If people think it would be useful to
implement, I might take a stab at it when I have time.

- Paul