Thread: foreign keys for array/period contains relationships
Currently, foreign keys only work with the = operator (the name might be different, but it needs to behave like equality). I'm thinking there are other scenarios that could be useful, for example with arrays and range types. Example #1: Foreign key side is an array, every member must match some PK. CREATE TABLE pk (a int PRIMARKY KEY, ...); CREATE TABLE fk (x int[] REFERENCES pk (a), ...); Example #2: Foreign key side as a (hypothetical) period type, PK is a timestamp. Every FK period must contain a PK timestamp. CREATE TABLE pk (a timestamp PRIMARY KEY, ...); CREATE TABLE fk (x period/range of timestamp REFERENCES pk (a), ...); Implementing the foreign key side of this merely requires the system to have some knowledge of the required "contains" operator, which it does in the array case, and something can surely be arranged for the range case. The problem is you can't do cascading updates or deletes, but you could do on update/delete restrict, which is still useful. It get's more interesting when the "container" type is the primary key: Example #3: PK is array, FK is element type. FK must be element of some PK array. CREATE TABLE pk (a int[] PRIMARY KEY, ...); CREATE TABLE fk (x int REFERENCES pk (a), ...); Example #4: PK is period, FK is timestamp. FK must be contained in some PK period. CREATE TABLE pk (a period PRIMARY KEY, ...); CREATE TABLE fk (x timestamp REFERENCES pk (a), ...); As above, we can probably arrange the operator knowledge to make these checks. But I think additionally, you'd need an exclusion constraint on the PK side to ensure nonoverlapping arrays/periods so that on update/delete restrict as well as cascading deletes work. Additional interesting examples involve IP network containment using inet/cidr or ip4/ip4r. There, you'd probably need additional syntax to tell the system explicitly which operators to use. Now I originally arrived at this issue via Example #1, but it appeared to me that with the ongoing work on range types, Example #4 would be a very eminent use case. Is this sort of thing feasible? Has anyone done more research into the necessary details?
On Mon, Oct 25, 2010 at 12:11 PM, Peter Eisentraut <peter_e@gmx.net> wrote: > Is this sort of thing feasible? Has anyone done more research into the > necessary details? I think the problems arise when you try to figure out what records you need to lock to prevent someone from deleting the referenced rows before you commit. -- greg
On Mon, Oct 25, 2010 at 3:11 PM, Peter Eisentraut <peter_e@gmx.net> wrote: > Currently, foreign keys only work with the = operator (the name might be > different, but it needs to behave like equality). I'm thinking there > are other scenarios that could be useful, for example with arrays and > range types. > > Example #1: Foreign key side is an array, every member must match some > PK. > > CREATE TABLE pk (a int PRIMARKY KEY, ...); > > CREATE TABLE fk (x int[] REFERENCES pk (a), ...); I've wished for this before when doing app dev with PG. I think it would be pretty neat. The other cases seem potentially useful, too, but especially this one. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
2010/10/25 Robert Haas <robertmhaas@gmail.com>: > On Mon, Oct 25, 2010 at 3:11 PM, Peter Eisentraut <peter_e@gmx.net> wrote: >> Currently, foreign keys only work with the = operator (the name might be >> different, but it needs to behave like equality). I'm thinking there >> are other scenarios that could be useful, for example with arrays and >> range types. >> >> Example #1: Foreign key side is an array, every member must match some >> PK. >> >> CREATE TABLE pk (a int PRIMARKY KEY, ...); >> >> CREATE TABLE fk (x int[] REFERENCES pk (a), ...); What about optimalizations and planning? This is classic sample how don't use a arrays? Regards Pavel > > I've wished for this before when doing app dev with PG. I think it > would be pretty neat. The other cases seem potentially useful, too, > but especially this one. > > -- > Robert Haas > EnterpriseDB: http://www.enterprisedb.com > The Enterprise PostgreSQL Company > > -- > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers >
On Mon, 2010-10-25 at 12:34 -0700, Greg Stark wrote: > On Mon, Oct 25, 2010 at 12:11 PM, Peter Eisentraut <peter_e@gmx.net> wrote: > > Is this sort of thing feasible? Has anyone done more research into the > > necessary details? > > I think the problems arise when you try to figure out what records you > need to lock to prevent someone from deleting the referenced rows > before you commit. I think that's easier when the PK must contain the FK, because then you only need to lock one record. Even when you need to lock multiple records, it seems feasible, and is just an index lookup, right? Do you see a particular problem? Regards,Jeff Davis
On Mon, 2010-10-25 at 22:11 +0300, Peter Eisentraut wrote: > Currently, foreign keys only work with the = operator (the name might be > different, but it needs to behave like equality). I'm thinking there > are other scenarios that could be useful, for example with arrays and > range types. I agree completely. I had not previously considered that arrays could benefit from this idea as well as range types. Mentally, I had already been calling them "foreign range keys" ;) > Implementing the foreign key side of this merely requires the system to > have some knowledge of the required "contains" operator, which it does > in the array case, and something can surely be arranged for the range > case. The problem is you can't do cascading updates or deletes, but you > could do on update/delete restrict, which is still useful. Why can't you do cascading updates/deletes? > Is this sort of thing feasible? Has anyone done more research into the > necessary details? Yes, I think so. #3 and #4 are very feasible. #1 and #2 are, as well, unless I'm missing something. Regards,Jeff Davis
On Mon, Oct 25, 2010 at 5:24 PM, Jeff Davis <pgsql@j-davis.com> wrote: > I think that's easier when the PK must contain the FK, because then you > only need to lock one record. Even when you need to lock multiple > records, it seems feasible, and is just an index lookup, right? Do you > see a particular problem? Well if you lock multiple records then it's not clear what operations you should conflict with. Removing any one of them wouldn't actually invalidate the foreign key reference unless you remove the last one. I always assumed this was why we require the unique constraint at all. Otherwise we could just do a sequential scan and lock all the matching records. but we would be preventing someone from removing those records even though removing just one wouldn't be breaking the constraint. -- greg
On mån, 2010-10-25 at 22:10 +0200, Pavel Stehule wrote: > 2010/10/25 Robert Haas <robertmhaas@gmail.com>: > >> Example #1: Foreign key side is an array, every member must match some > >> PK. > >> > >> CREATE TABLE pk (a int PRIMARKY KEY, ...); > >> > >> CREATE TABLE fk (x int[] REFERENCES pk (a), ...); > > What about optimalizations and planning? Some work will be required to get the respective checking queries to do the right think fast, but it's solvable in principle.
On mån, 2010-10-25 at 17:38 -0700, Jeff Davis wrote: > > Implementing the foreign key side of this merely requires the system > to > > have some knowledge of the required "contains" operator, which it > does > > in the array case, and something can surely be arranged for the > range > > case. The problem is you can't do cascading updates or deletes, but > you > > could do on update/delete restrict, which is still useful. > > Why can't you do cascading updates/deletes? Let's say you have PK 1 2 3 4 5 FK [1,2,3] [3,4,5] [4,4,4] When you delete PK = 3, what do you expect to happen? OK, you might decide to delete the first two rows from the FK table. This might or might not make sense in a particular case, but on delete cascade is an option the user has to choose explicitly. But I don't see what to do about cascading an update when you, say, update PK 1 => 6.
On mån, 2010-10-25 at 17:57 -0700, Greg Stark wrote: > Well if you lock multiple records then it's not clear what operations > you should conflict with. Removing any one of them wouldn't actually > invalidate the foreign key reference unless you remove the last one. > > I always assumed this was why we require the unique constraint at all. I did mention that you would need an exclusion constraint in some of the cases, to get an effect analogous to unique constraints.
On Tue, 2010-10-26 at 20:25 +0300, Peter Eisentraut wrote: > Let's say you have > > PK > > 1 > 2 > 3 > 4 > 5 > > FK > > [1,2,3] > [3,4,5] > [4,4,4] > > When you delete PK = 3, what do you expect to happen? OK, you might > decide to delete the first two rows from the FK table. This might or > might not make sense in a particular case, but on delete cascade is an > option the user has to choose explicitly. That's what I would expect. > But I don't see what to do > about cascading an update when you, say, update PK 1 => 6. Intuitively, I would expect all 1's to be replaced by 6's in all arrays. But I can now see why you would be hesitant to try to support that. Regards,Jeff Davis
On Mon, 2010-10-25 at 17:57 -0700, Greg Stark wrote: > On Mon, Oct 25, 2010 at 5:24 PM, Jeff Davis <pgsql@j-davis.com> wrote: > > I think that's easier when the PK must contain the FK, because then you > > only need to lock one record. Even when you need to lock multiple > > records, it seems feasible, and is just an index lookup, right? Do you > > see a particular problem? > > Well if you lock multiple records then it's not clear what operations > you should conflict with. Removing any one of them wouldn't actually > invalidate the foreign key reference unless you remove the last one. I didn't word my statement clearly. If the PK contains the FK, and you have an Exclusion Constraint on the PK (as Peter suggested), then you only need to lock one record. I think that logic would be pretty much the same as a normal FK. The case where you might need to lock multiple records is when the FK contains the PK (case #1 in Peter's original email). But in that case, you would still have a UNIQUE constraint on the PK (right?) and removing any referenced element should cause a conflict. Case #2 is the strange one, I think. It's not actually just an adaptation of #1. #1 requires that all elements of the array have a corresponding PK value; but #2 just requires that one of them does. Peter, can you clarify case #2? Did you have a use case in mind? Regards,Jeff Davis
On tis, 2010-10-26 at 11:53 -0700, Jeff Davis wrote: > Case #2 is the strange one, I think. It's not actually just an > adaptation of #1. #1 requires that all elements of the array have a > corresponding PK value; but #2 just requires that one of them does. > Peter, can you clarify case #2? Did you have a use case in mind? [ That's the period references timestamp case. ] You're right, it's probably not useful.
On 10/26/10 11:53 AM, Jeff Davis wrote: > Intuitively, I would expect all 1's to be replaced by 6's in all arrays. > But I can now see why you would be hesitant to try to support that. If people want cascading update to work, they shouldn't be denormalizing. -- -- Josh Berkus PostgreSQL Experts Inc. http://www.pgexperts.com
On Mon, Oct 25, 2010 at 15:11, Peter Eisentraut <peter_e@gmx.net> wrote:
There are a large number of use-cases for this type of foreign key with geometry ( PostGIS ) types as well. Point references Area or Line, Area references Area, etc.
Example #4: PK is period, FK is timestamp. FK must be contained in some
PK period.
CREATE TABLE pk (a period PRIMARY KEY, ...);
CREATE TABLE fk (x timestamp REFERENCES pk (a), ...);
As above, we can probably arrange the operator knowledge to make these
checks. But I think additionally, you'd need an exclusion constraint on
the PK side to ensure nonoverlapping arrays/periods so that on
update/delete restrict as well as cascading deletes work.
Additional interesting examples involve IP network containment using
inet/cidr or ip4/ip4r. There, you'd probably need additional syntax to
tell the system explicitly which operators to use.
There are a large number of use-cases for this type of foreign key with geometry ( PostGIS ) types as well. Point references Area or Line, Area references Area, etc.
On Mon, Oct 25, 2010 at 15:11, Peter Eisentraut <peter_e@gmx.net> wrote:Example #4: PK is period, FK is timestamp. FK must be contained in some
PK period.
CREATE TABLE pk (a period PRIMARY KEY, ...);
CREATE TABLE fk (x timestamp REFERENCES pk (a), ...);
As above, we can probably arrange the operator knowledge to make these
checks. But I think additionally, you'd need an exclusion constraint on
the PK side to ensure nonoverlapping arrays/periods so that on
update/delete restrict as well as cascading deletes work.
Additional interesting examples involve IP network containment using
inet/cidr or ip4/ip4r. There, you'd probably need additional syntax to
tell the system explicitly which operators to use.
There are a large number of use-cases for this type of foreign key with geometry ( PostGIS ) types as well. Point references Area or Line, Area references Area, etc.
You may be interested in an experiment I did late last year, where I did a bit of playing around in the system catalogs to create this kind of relationship. Turns out that the RI infrastructure stores the oid of the equality operators it uses in pg_constraint, and after creating a normal foreign key constraint it can be updated to change these operators. Of course, Bad Things can probably happen if you violate assumptions that the RI code depends on. I suspect that the most important one is that a child row must reference exactly one parent row.
For establishing a point-contained-in-box relationship, the parent-eq-parent operator is BOX && BOX and the child-eq-parent operator is POINT <@ BOX. The parent-eq-child operator is BOX @> POINT, which is the commutator of child-eq-parent. Declaring an exclusion constraint on the parent column using the && operator guarantees that the <@ operator can only match a single parent row.
If we're able to teach Postgres about these operator relationships -- that is, && combined with <@ satisfies the restriction that a child row can only reference one parent row -- extending the RI creation code to support this kind of a relationship looks to be fairly straightforward.
(I've attached a small .sql script which demonstrates this for the POINT <@ BOX case.)
-Andrew