Thread: Correct implementation of 1:n relationship with n>0?

It hit me today that a 1:n relationship can't be implemented just by a
single foreign key constraint if n>0. I must have been sleeping very
deeply not to notice this.

E.g. if there is a table "list" and another table "list_item" and the
relationship can be described as "every list has at least one
list_item" (and every list_item can only be part of one list, but
this is trivial).

A "correct" solution would require (at least?):

1. A foreign key pointing from each list_item to its list

2. Another foreign key pointing from each list to one of its list_item.
But this must be a list_item that itself points to the same list, so
just a simple foreign key constraint doesn't do it.

3. When a list has more than one list_item, and you want to delete the
list_item that its list points to, you have to "re-point" the foreign
key constraint on the list first. Do I need to use stored proceures
then for all insert, update, delete actions?

(4. Anything else that I've not seen?)

Is there a "straight" (and tested) solution for this in PostgreSQL, that
someone has already implemented and that can be re-used?

No, I definitely don't want to get into programming PL/PgSQL myself.
especially if the solution has to warrant data integrity under all
circumstances. Such as concurrent update, insert, delete etc.

TIA,

Sincerely,

Wolfgang

On ��� 30 ��� 2013 16:39:05 Wolfgang Keller wrote:
> It hit me today that a 1:n relationship can't be implemented just by a
> single foreign key constraint if n>0. I must have been sleeping very
> deeply not to notice this.
>
> E.g. if there is a table "list" and another table "list_item" and the
> relationship can be described as "every list has at least one
> list_item" (and every list_item can only be part of one list, but
> this is trivial).
>
> A "correct" solution would require (at least?):
>
> 1. A foreign key pointing from each list_item to its list
>
> 2. Another foreign key pointing from each list to one of its list_item.
> But this must be a list_item that itself points to the same list, so
> just a simple foreign key constraint doesn't do it.
>
> 3. When a list has more than one list_item, and you want to delete the
> list_item that its list points to, you have to "re-point" the foreign
> key constraint on the list first. Do I need to use stored proceures
> then for all insert, update, delete actions?
>
> (4. Anything else that I've not seen?)
>
> Is there a "straight" (and tested) solution for this in PostgreSQL, that
> someone has already implemented and that can be re-used?
>
> No, I definitely don't want to get into programming PL/PgSQL myself.
> especially if the solution has to warrant data integrity under all
> circumstances. Such as concurrent update, insert, delete etc.
>

I think your best bet is a trigger.
use RAISE EXCEPTION to indicate an erroneous situation so as to
make the transaction abort. (there is nothing wrong in getting your hands
dirty with pl/pgsql btw)

> TIA,
>
> Sincerely,
>
> Wolfgang
>
>
>
-
Achilleas Mantzios
IT DEV
IT DEPT
Dynacom Tankers Mgmt

Hi,

Can you explain what you are trying to achieve because it's not clear...

There are 2 types of relationships which might be used in your case:

1) unidirectional relationship from list_item to list through foreign
key on list
2) bidirectional relationship implemented through join table which
contains references between both tables

These are pretty standard  generic techniques applied many times and
don't require any "programming"

Thanks,
Anton

On Apr 30, 2013, at 16:39, Wolfgang Keller <feliphil@gmx.net> wrote:

> It hit me today that a 1:n relationship can't be implemented just by a
> single foreign key constraint if n>0. I must have been sleeping very
> deeply not to notice this.
>
> E.g. if there is a table "list" and another table "list_item" and the
> relationship can be described as "every list has at least one
> list_item" (and every list_item can only be part of one list, but
> this is trivial).
>
> A "correct" solution would require (at least?):
>
> 1. A foreign key pointing from each list_item to its list
>
> 2. Another foreign key pointing from each list to one of its list_item.
> But this must be a list_item that itself points to the same list, so
> just a simple foreign key constraint doesn't do it.
>
> 3. When a list has more than one list_item, and you want to delete the
> list_item that its list points to, you have to "re-point" the foreign
> key constraint on the list first. Do I need to use stored proceures
> then for all insert, update, delete actions?
>
> (4. Anything else that I've not seen?)
>
> Is there a "straight" (and tested) solution for this in PostgreSQL, that
> someone has already implemented and that can be re-used?
>
> No, I definitely don't want to get into programming PL/PgSQL myself.
> especially if the solution has to warrant data integrity under all
> circumstances. Such as concurrent update, insert, delete etc.
>
> TIA,
>
> Sincerely,
>
> Wolfgang
>
>
> --
> Sent via pgsql-sql mailing list (pgsql-sql@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-sql

On 04/30/2013 04:39 PM, Wolfgang Keller wrote:
> It hit me today that a 1:n relationship can't be implemented just by a
> single foreign key constraint if n>0. I must have been sleeping very
> deeply not to notice this.
>
> E.g. if there is a table "list" and another table "list_item" and the
> relationship can be described as "every list has at least one
> list_item" (and every list_item can only be part of one list, but
> this is trivial).
>
> A "correct" solution would require (at least?):
>
> 1. A foreign key pointing from each list_item to its list
>
> 2. Another foreign key pointing from each list to one of its list_item.
> But this must be a list_item that itself points to the same list, so
> just a simple foreign key constraint doesn't do it.
>
> 3. When a list has more than one list_item, and you want to delete the
> list_item that its list points to, you have to "re-point" the foreign
> key constraint on the list first. Do I need to use stored proceures
> then for all insert, update, delete actions?
>
> (4. Anything else that I've not seen?)
>
> Is there a "straight" (and tested) solution for this in PostgreSQL, that
> someone has already implemented and that can be re-used?
>
> No, I definitely don't want to get into programming PL/PgSQL myself.
> especially if the solution has to warrant data integrity under all
> circumstances. Such as concurrent update, insert, delete etc.

Does a solution like the following work for you?  It has some plpgsql,
but you didn't do it yourself.


drop schema if exists one_n cascade;
create schema one_n;
set search_path to 'one_n';

create table lists (id serial primary key, name text);
create table list_items (   id serial primary key,   list_id integer not null       references lists (id)       on
updatecascade on delete cascade,   value text);
 
create index on list_items (list_id);

create or replace function list_cardinality_enforcer()
returns trigger as
$$
declare   __list_id integer;
begin   if tg_table_name = 'lists' then       __list_id := new.id;   elsif tg_table_name = 'list_items' then
__list_id:= old.list_id;   else       raise exception 'This trigger function is only intended for
 
tables lists and list_items';   end if;     /* Take a lock on the list id to handle concurrency */   perform id from
one_n.listswhere id = __list_id for update;
 
   if not exists (select 1 from one_n.list_items li where list_id =
__list_id) then       raise exception 'List with id=% does not have any items', __list_id;   end if;
   return null;
end;
$$
language plpgsql;

create constraint trigger list_cardinality_enforcer
after insert on lists
deferrable initially deferred
for each row execute procedure list_cardinality_enforcer();

create constraint trigger list_cardinality_enforcer
after update or delete on list_items
deferrable initially deferred
for each row execute procedure list_cardinality_enforcer();


My basic tests work, it's possible I've not thought of something.

> It hit me today that a 1:n relationship can't be implemented just by a
> single foreign key constraint if n>0. I must have been sleeping very
> deeply not to notice this.
> 
> E.g. if there is a table "list" and another table "list_item" and the
> relationship can be described as "every list has at least one
> list_item" (and every list_item can only be part of one list, but
> this is trivial).

<duck>

BTW: If every list_item could be part of any number (>0) of lists, you
get a n:m relationship with a join table and then the issue that each
list_item has to belong to at least one list arises as well.

Maybe there should also be a standard solution documented somewhere for
this case, too.

</duck>

Sincerely,

Wolfgang

> (there is nothing wrong in getting your hands dirty with pl/pgsql btw)

The point is that I would have expected that problem to be solved
within the past four decades since relational databases have been
invented. Or at least in the past two decades since PostgreSQL has been
developed.

>;->

After all, this should be really an ultra-classic-standard FAQ item.

I'm definitely not the first database user in the world who needs to
have a 1:n relationship with n>0 and integrity enforced by the
database.

Sincerely,

Wolfgang

> -----Original Message-----
> From: pgsql-sql-owner@postgresql.org [mailto:pgsql-sql-
> owner@postgresql.org] On Behalf Of Wolfgang Keller
> Sent: Tuesday, April 30, 2013 2:19 PM
> To: pgsql-sql@postgresql.org
> Subject: Re: [SQL] Correct implementation of 1:n relationship with n>0?
>
> > It hit me today that a 1:n relationship can't be implemented just by
> a
> > single foreign key constraint if n>0. I must have been sleeping very
> > deeply not to notice this.
> >
> > E.g. if there is a table "list" and another table "list_item" and the
> > relationship can be described as "every list has at least one
> > list_item" (and every list_item can only be part of one list, but
> this
> > is trivial).
>
> <duck>
>
> BTW: If every list_item could be part of any number (>0) of lists, you
> get a n:m relationship with a join table and then the issue that each
> list_item has to belong to at least one list arises as well.
>
> Maybe there should also be a standard solution documented somewhere for
> this case, too.
>
> </duck>
>
> Sincerely,
>
> Wolfgang
>
>
> --
> Sent via pgsql-sql mailing list (pgsql-sql@postgresql.org) To make
> changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-sql

Wolfgang,

If it is n:m relationship, than appearance of the LIST in list_item table :

(list_id int not null,
item_id int not null,
constraint PK_list_item Primary Key (list_id, item_id),
constraint FK_ItemList_List Foreign Key (list_id) references List (list_id) on delete cascaded on update restrict,
constraint FK_ItemList_Item Foreign Key (item_id) references Item (item_id) on delete cascaded on update restrict)

means that this LIST has at least one ITEM assigned to it.
Same goes for the ITEM: if it is assigned to at least one List it should appear in this "cross table".

It is application responsibility to populate this table, when Items assigned to Lists.
It is database responsibility (through declarative foreign keys) to make sure that Lists and Items used in "cross
table"have corresponding records in "parent" tables. 
Using triggers (which is SQL extension implemented differently in every DBMS) database also can support such feature,
as:"when last Item removed from the List - drop now "empty" List.  Which I don't consider a good idea - what if you'll
needthis list in the future? Why re-create it? 

As for your original problem with 1:n relationship, n should be starting from 0 for the case when new List is created
andthere is no Items to assign to this new List, yet.  In this case, FK on Items table referencing List table makes
surethat every Item references existing (valid) List. 

Regards,
Igor Neyman

Hi,

Can you explain what you are trying to achieve because it's not clear...

There are 2 types of relationships which might be used in your case:

1) unidirectional relationship from list_item to list through foreign
key on list
2) bidirectional relationship implemented through join table which
contains references between both tables

These are pretty standard  generic techniques applied many times and
don't require any "programming"

Thanks,
Anton

On Apr 30, 2013, at 16:39, Wolfgang Keller <feliphil@gmx.net> wrote:

> It hit me today that a 1:n relationship can't be implemented just by a
> single foreign key constraint if n>0. I must have been sleeping very
> deeply not to notice this.
>
> E.g. if there is a table "list" and another table "list_item" and the
> relationship can be described as "every list has at least one
> list_item" (and every list_item can only be part of one list, but
> this is trivial).
>
> A "correct" solution would require (at least?):
>
> 1. A foreign key pointing from each list_item to its list
>
> 2. Another foreign key pointing from each list to one of its list_item.
> But this must be a list_item that itself points to the same list, so
> just a simple foreign key constraint doesn't do it.
>
> 3. When a list has more than one list_item, and you want to delete the
> list_item that its list points to, you have to "re-point" the foreign
> key constraint on the list first. Do I need to use stored proceures
> then for all insert, update, delete actions?
>
> (4. Anything else that I've not seen?)
>
> Is there a "straight" (and tested) solution for this in PostgreSQL, that
> someone has already implemented and that can be re-used?
>
> No, I definitely don't want to get into programming PL/PgSQL myself.
> especially if the solution has to warrant data integrity under all
> circumstances. Such as concurrent update, insert, delete etc.
>
> TIA,
>
> Sincerely,
>
> Wolfgang
>
>
> --
> Sent via pgsql-sql mailing list (pgsql-sql@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-sql

On ��� 30 ��� 2013 20:25:42 Wolfgang Keller wrote:
> > (there is nothing wrong in getting your hands dirty with pl/pgsql btw)
>
> The point is that I would have expected that problem to be solved
> within the past four decades since relational databases have been
> invented. Or at least in the past two decades since PostgreSQL has been
> developed.
>

Then what about n>1, n>2, n>k where k an arbitrarily large positive integer?
isn't it the same problem class actually?

Is there any serious database vendor who provides out of the box support for 1:n, n>0 ?
Or is it an "unusual" user requirement in the first place.
Ever thought why not so many people have asked for this?

Anyway, IMHO, the need for more programming/programmers increases with the years,
engineering becomes more complex, you can't expect serious contgrol in anything without
getting under the hood.

> >;->
>
> After all, this should be really an ultra-classic-standard FAQ item.
>
> I'm definitely not the first database user in the world who needs to
> have a 1:n relationship with n>0 and integrity enforced by the
> database.
>
> Sincerely,
>
> Wolfgang
>
>
>
-
Achilleas Mantzios
IT DEV
IT DEPT

On Ôñé 30 Áðñ 2013 20:25:42 Wolfgang Keller wrote:
> > (there is nothing wrong in getting your hands dirty with pl/pgsql btw)
>
> The point is that I would have expected that problem to be solved
> within the past four decades since relational databases have been
> invented. Or at least in the past two decades since PostgreSQL has been
> developed.
>

Then what about n>1, n>2, n>k where k an arbitrarily large positive integer?
isn't it the same problem class actually?

Is there any serious database vendor who provides out of the box support for 1:n, n>0 ?
Or is it an "unusual" user requirement in the first place.
Ever thought why not so many people have asked for this?

Anyway, IMHO, the need for more programming/programmers increases with the years,
engineering becomes more complex, you can't expect serious contgrol in anything without
getting under the hood.

> >;->
>
> After all, this should be really an ultra-classic-standard FAQ item.
>
> I'm definitely not the first database user in the world who needs to
> have a 1:n relationship with n>0 and integrity enforced by the
> database.
>
> Sincerely,
>
> Wolfgang
>
>
>
-
Achilleas Mantzios
IT DEV
IT DEPT
Dynacom Tankers Mgmt

> > The point is that I would have expected that problem to be solved
> > within the past four decades since relational databases have been
> > invented. Or at least in the past two decades since PostgreSQL has
> > been developed.
> 
> Then what about n>1, n>2, n>k where k an arbitrarily large positive
> integer? isn't it the same problem class actually?

Not quite.

In conceptual modeling, relationships between entities aren't directed.
And there's no reason to not have a "not null" constraint on any of the
two sides of a one-to-many (or many-to-many) relationship from the
conceptual point of view.

The way relationships are implemented in physical database schemas, by
foreign key constraints, just makes it non-trivial to implement such a
"not null" constraint on the "wrong" end of a one-to-many relationship.
But this a technical issue with the implementation of databases at the
physical level, not a conceptual issue.

> Is there any serious database vendor who provides out of the box
> support for 1:n, n>0 ? Or is it an "unusual" user requirement in the
> first place.

It definitely is not, since conceptual diagrams I have seen are full of
such relationships. They're just never correctly implemented at the
physical level.

> Ever thought why not so many people have asked for this?

Having quite some professional experience in companies, I don't doubt
for a second that the very only reason is simply total absence of care
for scientific correctness of database at the level of the physical
implementation.
Sincerely,

Wolfgang