foreign key cardinality

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

foreign key cardinality

James K. Lowden
I would like to illustrate a problem with SQLite's foreign key
enforcement policy.  SQLite requires that foreign keys refer to primary
keys.  That rule has no relational foundation, and prevents the use of
foreign keys that are perfectly valid.

I have these tables (non-key columns omitted for brevity):

        Directory ( name primary key )
        File ( name, dname references Directory(name), primary key
(name, dname) ) Program ( name primary key )

Note that a filename is not unique except within a directory.

Now I have authorization tables that constrain what directories and
files a program can access, and in what order.  

        ProgDir (  pname references Program(name),
                        dname references Directory(name),
                  ord,
                        primary key (pname, ord) )

        ProgFile ( pname, pord, fname, ord,
                       primary key (pname, pord, fname),
                       foreign key (pname, pord) references ProgDir
(pname, ord), foreign key (fname) references File(name) ) -- ouch

A program can access a directory and that directory's files.  The file
access order depends on which directory we're referring to, and
requires that the program be permitted to use that directory.

It's not necessary to carry dname in ProgFile; it can be derived from
ProgDir.dname.  But it would be nice to know that the ProgFile.fname
exists in File.name.

If I added Progfile.dname, so that I could declare a foreign key to
File, it would be nice to also add it to the FK declaration referring
to ProgDir:

        foreign key (pname, pord, dname) references ProgDir(pname, ord,
dname)

because that reflects the rule that permission to use a file requires
permission to use the file's directory.

In both cases, I'm stuck.  SQLite requires a FK declaration to match
the referrenced table's PK, else you get a "foreign key mismatch"
error.  (At least, that's my understanding of, "Parent and child keys
must have the same cardinality." If ProgFile has no dname, it can't
have a foreign key to File. If it does have dname, it can't include it
in its reference to ProgDir.  

The relational model doesn't recognize the concept of "primary key",
and the rule that a foreign key must refer to a primary key is not part
of the SQL standard.  The rule is unnecessary, and interferes with
accurate foreign key reference declarations.

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Richard Hipp-3
On 2/27/17, James K. Lowden <[hidden email]> wrote:
> SQLite requires that foreign keys refer to primary
> keys.

No it doesn't.  Where did you get that impression?

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Ben Newberg
The column can be unique as well, correct?

SQLite version 3.17.0 2017-02-13 16:02:40
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> pragma foreign_keys = 1;
sqlite> create table x (a integer primary key, b integer unique, c text);
sqlite> insert into x (a, b, c) values (1, 11, 'a');
sqlite> insert into x (a, b, c) values (2, 22, 'a');
sqlite> insert into x (a, b, c) values (3, 33, 'b');
sqlite> create table y1 (a integer references x(a));
sqlite> insert into y1 values(1);
sqlite> create table y2 (b integer references x(b));
sqlite> insert into y2 values(11);
sqlite> create table y3 (c text references x(c));
sqlite> insert into y3 values('a');
Error: foreign key mismatch - "y3" referencing "x"
sqlite> insert into y3 values('b');
Error: foreign key mismatch - "y3" referencing "x"
sqlite>

On Mon, Feb 27, 2017 at 3:07 PM, Richard Hipp <[hidden email]> wrote:

> On 2/27/17, James K. Lowden <[hidden email]> wrote:
> > SQLite requires that foreign keys refer to primary
> > keys.
>
> No it doesn't.  Where did you get that impression?
>
> --
> D. Richard Hipp
> [hidden email]
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

James K. Lowden
In reply to this post by Richard Hipp-3
On Mon, 27 Feb 2017 16:07:48 -0500
Richard Hipp <[hidden email]> wrote:

> On 2/27/17, James K. Lowden <[hidden email]> wrote:
> > SQLite requires that foreign keys refer to primary
> > keys.
>
> No it doesn't.  Where did you get that impression?

sqlite> create table A(a, b, primary key (a,b));
sqlite> create table C(c references A(a));
sqlite> insert into A values (1,2);
sqlite> insert into C values (1);
Error: foreign key mismatch - "C" referencing "A"
sqlite>

Clearly something about the primary key influences the evaluation of a
referencing foreign key.  Perhaps i should have said "whole primary
key"?  

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Simon Slavin-3

On 28 Feb 2017, at 12:19am, James K. Lowden <[hidden email]> wrote:

> sqlite> create table A(a, b, primary key (a,b));
> sqlite> create table C(c references A(a));

The reference column(s) (the column(s) in the 'parent' table) must be UNIQUE otherwise you may have two rows in that table which both look like they may be the parent.

So you need a UNIQUE index on the reference column(s).  Of course, if they’re the primary key then they already have a UNIQUE index, since the primary key of a table must be unique and SQLite automatically makes an index to enforce that.  So try instead

create table A(a, b, primary key (a,b));
CREATE UNIQUE INDEX A_a ON A (a);
create table C(c references A(a));

A way to have this index automatically created is to put a UNIQUE requirement on that column:

create table A(a, b, primary key (a UNIQUE,b));
create table C(c references A(a));

This is documented in section 3 of

<https://www.sqlite.org/foreignkeys.html>

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Hick Gunter
In reply to this post by James K. Lowden
Your assumption does not correspond with the documentation, see http://sqlite.org/foreignkeys.html :

"The parent key is the column or set of columns in the parent table that the foreign key constraint refers to. This is normally, but not always, the primary key of the parent table. The parent key must be a named column or columns in the parent table, not the rowid."

" If they are not the primary key, then the parent key columns must be collectively subject to a UNIQUE constraint or have a UNIQUE index."

"Cardinality" refers to the number of fields in the constraint. As in "(x,y,z) of child table must match (a,b,c) of parent table" is valid, while "(x,y) of child must match (a) of parent table" is invalid, just like "(x,y) of chid table must match (a,b,c) of parent table".


-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von James K. Lowden
Gesendet: Montag, 27. Februar 2017 21:42
An: [hidden email]
Betreff: [sqlite] foreign key cardinality

I would like to illustrate a problem with SQLite's foreign key enforcement policy.  SQLite requires that foreign keys refer to primary keys.  That rule has no relational foundation, and prevents the use of foreign keys that are perfectly valid.

I have these tables (non-key columns omitted for brevity):

        Directory ( name primary key )
        File ( name, dname references Directory(name), primary key (name, dname) ) Program ( name primary key )

Note that a filename is not unique except within a directory.

Now I have authorization tables that constrain what directories and files a program can access, and in what order.

        ProgDir (  pname references Program(name),
                        dname references Directory(name),
                        ord,
                        primary key (pname, ord) )

        ProgFile ( pname, pord, fname, ord,
                       primary key (pname, pord, fname),
                       foreign key (pname, pord) references ProgDir (pname, ord), foreign key (fname) references File(name) ) -- ouch

A program can access a directory and that directory's files.  The file access order depends on which directory we're referring to, and requires that the program be permitted to use that directory.

It's not necessary to carry dname in ProgFile; it can be derived from ProgDir.dname.  But it would be nice to know that the ProgFile.fname exists in File.name.

If I added Progfile.dname, so that I could declare a foreign key to File, it would be nice to also add it to the FK declaration referring to ProgDir:

        foreign key (pname, pord, dname) references ProgDir(pname, ord,
dname)

because that reflects the rule that permission to use a file requires permission to use the file's directory.

In both cases, I'm stuck.  SQLite requires a FK declaration to match the referrenced table's PK, else you get a "foreign key mismatch"
error.  (At least, that's my understanding of, "Parent and child keys must have the same cardinality." If ProgFile has no dname, it can't have a foreign key to File. If it does have dname, it can't include it in its reference to ProgDir.

The relational model doesn't recognize the concept of "primary key", and the rule that a foreign key must refer to a primary key is not part of the SQL standard.  The rule is unnecessary, and interferes with accurate foreign key reference declarations.

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Hick Gunter
In reply to this post by Simon Slavin-3
If a is already unique, there is no need for b in the primary key...

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Simon Slavin
Gesendet: Dienstag, 28. Februar 2017 01:41
An: SQLite mailing list <[hidden email]>
Betreff: Re: [sqlite] foreign key cardinality


On 28 Feb 2017, at 12:19am, James K. Lowden <[hidden email]> wrote:

> sqlite> create table A(a, b, primary key (a,b)); create table C(c
> sqlite> references A(a));

The reference column(s) (the column(s) in the 'parent' table) must be UNIQUE otherwise you may have two rows in that table which both look like they may be the parent.

So you need a UNIQUE index on the reference column(s).  Of course, if they’re the primary key then they already have a UNIQUE index, since the primary key of a table must be unique and SQLite automatically makes an index to enforce that.  So try instead

create table A(a, b, primary key (a,b)); CREATE UNIQUE INDEX A_a ON A (a); create table C(c references A(a));

A way to have this index automatically created is to put a UNIQUE requirement on that column:

create table A(a, b, primary key (a UNIQUE,b)); create table C(c references A(a));

This is documented in section 3 of

<https://www.sqlite.org/foreignkeys.html>

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

James K. Lowden
In reply to this post by Hick Gunter
On Tue, 28 Feb 2017 08:48:02 +0000
Hick Gunter <[hidden email]> wrote:

> "If they are not the primary key, then the parent key columns must
> be collectively subject to a UNIQUE constraint or have a UNIQUE
> index."

Thank you, Hick.  

I have always thought af a foreign key as an existence test.  Looking
around, I see that other implementations also often require the
referent to be unique.  I'm not convinced that's justified
theoretically, but at the moment I can't check against my usual
resources.  

I now see how to solve the conundrum I faced that motivated my
complaint.  It requires more columns and UNIQUE constraints than I
think are strictly necessary, but it can be made to work.  

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Hick Gunter
Let's assume you have a parent table P (color, shape, style, ...) that is unique on the three named fields.
Let's assume you have a child table C (id, ...,color, shape, ...) that references P(color,shape)

Now insert some rows into P (red,square,none, ...) and (red, square, bold, ...).

And insert some rows into C (1,...,red, square, ...) and (2,...,red, square,...).

Which, if any, of the P rows can you safely delete without losing referential integrity? Assuming ON DELETE CASCADE, when do you delete the rows from C?

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von James K. Lowden
Gesendet: Dienstag, 28. Februar 2017 17:42
An: [hidden email]
Betreff: Re: [sqlite] foreign key cardinality

On Tue, 28 Feb 2017 08:48:02 +0000
Hick Gunter <[hidden email]> wrote:

> "If they are not the primary key, then the parent key columns must be
> collectively subject to a UNIQUE constraint or have a UNIQUE index."

Thank you, Hick.

I have always thought af a foreign key as an existence test.  Looking around, I see that other implementations also often require the referent to be unique.  I'm not convinced that's justified theoretically, but at the moment I can't check against my usual resources.

I now see how to solve the conundrum I faced that motivated my complaint.  It requires more columns and UNIQUE constraints than I think are strictly necessary, but it can be made to work.

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Kees Nuyt
In reply to this post by James K. Lowden
On Tue, 28 Feb 2017 11:42:23 -0500, "James K. Lowden"
<[hidden email]> wrote:

> I have always thought af a foreign key as an existence test.  Looking
> around, I see that other implementations also often require the
> referent to be unique.  I'm not convinced that's justified
> theoretically, but at the moment I can't check against my usual
> resources.  

Here you go:

Information Technology - Database Language SQL
(Proposed revised text of DIS 9075)
(Second Informal Review Draft) ISO/IEC 9075:1992,
Database Language SQL- July 30, 1992
which is pretty close to the final text.

X3H2-92-154/DBL CBR-002  (page 274 or thereabout)

11.8  <referential constraint definition>

Function

Specify a referential constraint.

Format

<referential constraint definition> ::=
     FOREIGN KEY <left paren> <referencing columns> <right paren>
       <references specification>

<references specification> ::=
     REFERENCES <referenced table and columns>
       [ MATCH <match type> ]
       [ <referential triggered action> ]

<match type> ::=
       FULL
     | PARTIAL

<referencing columns> ::=
     <reference column list>

<referenced table and columns> ::=
     <table name> [ <left paren> <reference column list> <right paren> ]

<reference column list> ::= <column name list>

<referential triggered action> ::=
       <update rule> [ <delete rule> ]
     | <delete rule> [ <update rule> ]

<update rule> ::= ON UPDATE <referential action>

<delete rule> ::= ON DELETE <referential action>

<referential action> ::=
       CASCADE
     | SET NULL
     | SET DEFAULT
     | NO ACTION


Syntax Rules

1) Let referencing table be the table identified by the containing
   <table definition> or <alter table statement>. Let referenced
   table be the table identified by the <table name> in the <refer-
   enced table and columns>. Let referencing columns be the column
   or columns identified by the <reference column list> in the
   <referencing columns> and let referencing column be one such
   column.

2) Case:

   a) If the <referenced table and columns> specifies a <reference
     column list>, then the set of column names of that <refer-
     ence column list> shall be equal to the set of column names
     in the unique columns of a unique constraint of the refer-
     enced table. Let referenced columns be the column or columns
     identified by that <reference column list> and let refer-
     enced column be one such column. Each referenced column shall
     identify a column of the referenced table and the same column
     shall not be identified more than once.

   b) If the <referenced table and columns> does not specify a
     <reference column list>, then the table descriptor of the
     referenced table shall include a unique constraint that spec-
     ifies PRIMARY KEY. Let referenced columns be the column or
     columns identified by the unique columns in that unique con-
     straint and let referenced column be one such column. The
     <referenced table and columns> shall be considered to implic-
     itly specify a <reference column list> that is identical to
     that <unique column list>.

3) The table constraint descriptor describing the <unique con-
   straint definition> whose <unique column list> identifies the
   referenced columns shall indicate that the unique constraint is
   not deferrable.


--
Regards,

Kees Nuyt

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

James K. Lowden
In reply to this post by Hick Gunter
On Tue, 28 Feb 2017 17:13:30 +0000
Hick Gunter <[hidden email]> wrote:

> Let's assume you have a parent table P (color, shape, style, ...)
> that is unique on the three named fields. Let's assume you have a
> child table C (id, ...,color, shape, ...) that references P
> (color,shape)

As far as SQL goes, Kees provided the relevant text, so we know SQLite
conforms to the standard in this regard.  Thank you, Kees.  

To answer your questions, supposing UNIQUE were not required for a
FK referent:

> Which, if any, of the P rows can you safely delete without losing
> referential integrity?

delete from P where not exists (
        select 1 from C where color = P.color and shape = P.shape );

> Assuming ON DELETE CASCADE, when do you delete the rows from C?

delete from C where exists (
        select 1 from P where color = C.color and shape = C.shape
  and /* ... P criteria ... */
);

From a theoretical standpoint, for relations

        P{A,B}
and
        C{C,B} with C{B} referencing P{B}

without loss of information we may add

        B{B}

and constraints

        P{B} references B{B} and C{B} references B{B}

But, having added B, we have not added any information.  We have
merely added another relation that is the projection of P{B}.  

It is *usually* true that B will have other attributes, in which case
of course a B table would be needed to hold them.  Maybe that, or
practical considerations, or both, motivated the SQL rule.  

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

J Decker
On Tue, Feb 28, 2017 at 1:41 PM, James K. Lowden <[hidden email]>
wrote:

> On Tue, 28 Feb 2017 17:13:30 +0000
> Hick Gunter <[hidden email]> wrote:
>
> > Let's assume you have a parent table P (color, shape, style, ...)
> > that is unique on the three named fields. Let's assume you have a
> > child table C (id, ...,color, shape, ...) that references P
> > (color,shape)
>
> As far as SQL goes, Kees provided the relevant text, so we know SQLite
> conforms to the standard in this regard.  Thank you, Kees.
>
> To answer your questions, supposing UNIQUE were not required for a
> FK referent:
>
> > Which, if any, of the P rows can you safely delete without losing
> > referential integrity?
>

Then how would you properly find the children?  Or find any information
about their parent, the child would have to in turn be deleted.

foreign keys are as good as pointers.  If the parent structure pointing at
a child is no longer, how is the child valid for anything other than
garbage collection?

If the unique; (memory address) key contains multiple parts, then you have
to reference all aprts.  If there was a part that was itself unique then
you wouldn't really need the second part; otherwise you do in order to
differentiate (1,1) from (1,2)

perhaps what you intend is to use a graph database, where a single 'child'
might be referred to from mulitple parents (links) ; but then your model
should be something more self recursive like...
(pseudoSQL)
create table inode( iNode char PRIMARY KEY, moreColumns char,  )
create table inodeLinks( someInode char, someOtherInode char, FK(someinode
references inode.iNode), FK(someOtheriNode references inode.iNode) )

create table inodeFileData( iNode char , fileDataIfAny char,  )
create table inodeNameData( iNode char, theNameOfThisPoint char,  )
create table inodeFileData( iNode char, attributes char,  )

Such that any directory might also contain some data, but any file can
contain other files since each thing is named separatly from it's key.




Instead of having the file records themselves having their directory, why
not just make a separate table
( directory char , hasFiles char );

CTE queries can make this even tolerable for linear queries
--------------------
Sorry I wandered into an alternative solution instead of the other
representation...
in .NET you have DataSet, whichi contains DataTables, and between DTs are
Relation(s).  When you fill a dataset with all properly keyed things, the
row in one table (files).getChildRows( "filesInDirectory" ) (returns more
rows)

And it's really a direct reference, it doesn't have to go additionally
search through the index in the child table to get to the rows by looking
up a key, it just points to it.  Much like working with a graph, your
master records just point at the children, and you never have to search for
anything...



> delete from P where not exists (
>         select 1 from C where color = P.color and shape = P.shape );
>
> > Assuming ON DELETE CASCADE, when do you delete the rows from C?
>
> delete from C where exists (
>         select 1 from P where color = C.color and shape = C.shape
>         and /* ... P criteria ... */
> );
>
> From a theoretical standpoint, for relations
>
>         P{A,B}
> and
>         C{C,B} with C{B} referencing P{B}
>
> without loss of information we may add
>
>         B{B}
>
> and constraints
>
>         P{B} references B{B} and C{B} references B{B}
>
> But, having added B, we have not added any information.  We have
> merely added another relation that is the projection of P{B}.
>
> It is *usually* true that B will have other attributes, in which case
> of course a B table would be needed to hold them.  Maybe that, or
> practical considerations, or both, motivated the SQL rule.
>
> --jkl
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

J Decker
On Tue, Feb 28, 2017 at 6:01 PM, J Decker <[hidden email]> wrote:

>
>
> On Tue, Feb 28, 2017 at 1:41 PM, James K. Lowden <[hidden email]
> > wrote:
>
>> On Tue, 28 Feb 2017 17:13:30 +0000
>> Hick Gunter <[hidden email]> wrote:
>>
>> > Let's assume you have a parent table P (color, shape, style, ...)
>> > that is unique on the three named fields. Let's assume you have a
>> > child table C (id, ...,color, shape, ...) that references P
>> > (color,shape)
>>
>> As far as SQL goes, Kees provided the relevant text, so we know SQLite
>> conforms to the standard in this regard.  Thank you, Kees.
>>
>> To answer your questions, supposing UNIQUE were not required for a
>> FK referent:
>>
>> > Which, if any, of the P rows can you safely delete without losing
>> > referential integrity?
>>
>
> Then how would you properly find the children?  Or find any information
> about their parent, the child would have to in turn be deleted.
>
> foreign keys are as good as pointers.  If the parent structure pointing at
> a child is no longer, how is the child valid for anything other than
> garbage collection?
>
> okay but I guess that's what on delete SETNULL is for... so you can keep
the child as a special 'NULL' record for later searching just by file....


> If the unique; (memory address) key contains multiple parts, then you have
> to reference all aprts.  If there was a part that was itself unique then
> you wouldn't really need the second part; otherwise you do in order to
> differentiate (1,1) from (1,2)
>
> perhaps what you intend is to use a graph database, where a single 'child'
> might be referred to from mulitple parents (links) ; but then your model
> should be something more self recursive like...
> (pseudoSQL)
> create table inode( iNode char PRIMARY KEY, moreColumns char,  )
> create table inodeLinks( someInode char, someOtherInode char, FK(someinode
> references inode.iNode), FK(someOtheriNode references inode.iNode) )
>
> create table inodeFileData( iNode char , fileDataIfAny char,  )
> create table inodeNameData( iNode char, theNameOfThisPoint char,  )
> create table inodeFileData( iNode char, attributes char,  )
>
> Such that any directory might also contain some data, but any file can
> contain other files since each thing is named separatly from it's key.
>
>
>
>
> Instead of having the file records themselves having their directory, why
> not just make a separate table
> ( directory char , hasFiles char );
>
> CTE queries can make this even tolerable for linear queries
> --------------------
> Sorry I wandered into an alternative solution instead of the other
> representation...
> in .NET you have DataSet, whichi contains DataTables, and between DTs are
> Relation(s).  When you fill a dataset with all properly keyed things, the
> row in one table (files).getChildRows( "filesInDirectory" ) (returns more
> rows)
>
> And it's really a direct reference, it doesn't have to go additionally
> search through the index in the child table to get to the rows by looking
> up a key, it just points to it.  Much like working with a graph, your
> master records just point at the children, and you never have to search for
> anything...
>
>
>
>> delete from P where not exists (
>>         select 1 from C where color = P.color and shape = P.shape );
>>
>> > Assuming ON DELETE CASCADE, when do you delete the rows from C?
>>
>> delete from C where exists (
>>         select 1 from P where color = C.color and shape = C.shape
>>         and /* ... P criteria ... */
>> );
>>
>> From a theoretical standpoint, for relations
>>
>>         P{A,B}
>> and
>>         C{C,B} with C{B} referencing P{B}
>>
>> without loss of information we may add
>>
>>         B{B}
>>
>> and constraints
>>
>>         P{B} references B{B} and C{B} references B{B}
>>
>> But, having added B, we have not added any information.  We have
>> merely added another relation that is the projection of P{B}.
>>
>> It is *usually* true that B will have other attributes, in which case
>> of course a B table would be needed to hold them.  Maybe that, or
>> practical considerations, or both, motivated the SQL rule.
>>
>> --jkl
>> _______________________________________________
>> sqlite-users mailing list
>> [hidden email]
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>>
>
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Keith Medcalf
In reply to this post by James K. Lowden

> > Let's assume you have a parent table P (color, shape, style, ...)
> > that is unique on the three named fields. Let's assume you have a
> > child table C (id, ...,color, shape, ...) that references P
> > (color,shape)
>
> As far as SQL goes, Kees provided the relevant text, so we know SQLite
> conforms to the standard in this regard.  Thank you, Kees.
>
> To answer your questions, supposing UNIQUE were not required for a
> FK referent:
>
> > Which, if any, of the P rows can you safely delete without losing
> > referential integrity?
>
> delete from P where not exists (
> select 1 from C where color = P.color and shape = P.shape );
>
> > Assuming ON DELETE CASCADE, when do you delete the rows from C?
>
> delete from C where exists (
> select 1 from P where color = C.color and shape = C.shape
>   and /* ... P criteria ... */
> );
>
> From a theoretical standpoint, for relations
>
> P{A,B}
> and
> C{C,B} with C{B} referencing P{B}
>
> without loss of information we may add
>
> B{B}
>
> and constraints
>
> P{B} references B{B} and C{B} references B{B}
>
> But, having added B, we have not added any information.  We have
> merely added another relation that is the projection of P{B}.
>
> It is *usually* true that B will have other attributes, in which case
> of course a B table would be needed to hold them.  Maybe that, or
> practical considerations, or both, motivated the SQL rule.

It has always been the case in SQL (and relational databases in general) that Parents must be unique.  It was even the case in Hierarchical databases that Parents of a Set must be unique -- that is, identify a 1:N relationship.  N:M relationship modelling requires a connecting N:M table where the relationships between table A -> C <- B are one parent in A identifies N records in C, each of which identifies one record in B (that is, A -> C is 1:N and B -> C is 1:M with the resulting A <-> B relationship being N:M).  Only Network Model (I forget whether it has to be Network Extended -- it has been a long time since I used one) Hierarchical databases model N:M sets directly.

It has always been a requirement that FK relationships are 1:N mappings, otherwise update anomalies will occur.  If you have a relational database that does not "naturally" have all FK relationships as 1:N, then you have not normalized the data properly (or sufficiently).




_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Hick Gunter
In reply to this post by James K. Lowden
I was not asking for SQL statements but that you think about what you are trying to achieve.

Without a UNIQUE constraint there can be more than one row in the parent table that is the "parent row" of at least one row of the child table. To delete rows from the parent while still satisfying the EXISTS relation, you can delete all rows except the "last one" for each distinct (=UNIQUE) foreign key combination in the child table. This is not a set operation, there is no "last row" in a set. Likewise ON DELETE CASCADE needs tob e triggered when the "last row" for a distinct (=UNIQUE) foreign key combination is deleted from the parent table. Again, there is no "last row" in a set.

Not requiring UNIQUE means that FK enforcement relies on sets exhibiting an order, when they are clearly not allowed to have one by the relational model. Thus UNIQUE is required. (Proof by "reductio ad absurdum")

SQL for non-unique foreign key ON DELETE CASCADE:

-- assumes FK constraints are DEFERRED
BEGIN;
-- get the set of foreign key expressions touched by the delete
CREATE TEMP TABLE TBD_C AS SELECT DISTINCT <FK> FROM P WHERE <delete condition>;
-- remove the rows from parent table
DELETE FROM P WHERE <delete-condition>;
-- remove foreign key expressions still fulfilled by parent table
DELETE FROM TBD_C WHERE EXISTS (SELECT 1 FROM P WHERE <FK-match>);
-- remove "unparented" rows from child table
DELETE FROM C WHERE <FK> IN (SELECT * FROM TBD_C);
--
COMMIT;


-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von James K. Lowden
Gesendet: Dienstag, 28. Februar 2017 22:41
An: [hidden email]
Betreff: Re: [sqlite] foreign key cardinality

On Tue, 28 Feb 2017 17:13:30 +0000
Hick Gunter <[hidden email]> wrote:

> Let's assume you have a parent table P (color, shape, style, ...) that
> is unique on the three named fields. Let's assume you have a child
> table C (id, ...,color, shape, ...) that references P
> (color,shape)

As far as SQL goes, Kees provided the relevant text, so we know SQLite conforms to the standard in this regard.  Thank you, Kees.

To answer your questions, supposing UNIQUE were not required for a FK referent:

> Which, if any, of the P rows can you safely delete without losing
> referential integrity?

delete from P where not exists (
        select 1 from C where color = P.color and shape = P.shape );

> Assuming ON DELETE CASCADE, when do you delete the rows from C?

delete from C where exists (
        select 1 from P where color = C.color and shape = C.shape
        and /* ... P criteria ... */
);

From a theoretical standpoint, for relations

        P{A,B}
and
        C{C,B} with C{B} referencing P{B}

without loss of information we may add

        B{B}

and constraints

        P{B} references B{B} and C{B} references B{B}

But, having added B, we have not added any information.  We have merely added another relation that is the projection of P{B}.

It is *usually* true that B will have other attributes, in which case of course a B table would be needed to hold them.  Maybe that, or practical considerations, or both, motivated the SQL rule.

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

James K. Lowden
On Wed, 1 Mar 2017 07:26:31 +0000
Hick Gunter <[hidden email]> wrote:

> Without a UNIQUE constraint there can be more than one row in the
> parent table that is the "parent row" of at least one row of the
> child table. To delete rows from the parent while still satisfying
> the EXISTS relation, you can delete all rows except the "last one"
> for each distinct (=UNIQUE) foreign key combination in the child
> table. This is not a set operation

First, I don't recognize "parent" and "child" as relational concepts.
It's convenient shorthand for us, but we must not let that terminology
contaminate our thinking.  

You seem to think M:N represents some kind of logical challenge that
1:N does not.  Why?  Many databases have a rule similar to "every order
has line items, and every line item has an order".  On deletion of the
last "child", delete the "parent".  It is not the difference between
many and one that matters; it's the difference between any and none.  

In an M:N relationship, cascading delete probably doesn't make sense.
But it wouldn't make more sense represented as three tables instead of
two!  

Please consider my example again:

        P(A,B) and C(C,B) where C(B) references A(B)
        and A(B) is not unique

and

        B(B), P(A,B), and C(C,B)
        where P(B) and C(B) both reference B(B)

In neither case can you define a cascading relationship between P and
C.  Adding B doesn't change that.  It doesn't make the design more
"normalized".  

What it does do is make it more "SQLized"; it allows the use of SQL FK
declarations to enforce that B(B) exists so long as P(B) or C(B) does.  

By requiring a unique referent, though, SQL prevents declaration of the
rule, "for every C(B), there must be a P(B)".  

You might well answer that the relationship should be

        P(A,B) and C(C,A,B) where C(A,B) references A(A,B)

because, otherwise, what B do we mean?  And that's effectively what I
did with the design that motivated my original question.  

But I'm not convinced it's necessary.  In my case, C(A) can be
derived from another relationship; C(B) adds information to that A and
cannot be related to some other A.  The "which B" question can be
answered by a join.  Unambiguously.  I'm schlepping C(A) around only
for SQL reasons, not for any logical one I can see.  

Probably I'm overlooking something, and probably this is not the right
forum.  SQLite adheres to the SQL standard; that's established.  Why
does the standard say what it does?  I'm only saying it's not clear to
me that there's theoretical justification.  

--jkl








_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

James K. Lowden
In reply to this post by Keith Medcalf
On Tue, 28 Feb 2017 19:44:56 -0700
"Keith Medcalf" <[hidden email]> wrote:

> It has always been a requirement that FK relationships are 1:N
> mappings, otherwise update anomalies will occur.  If you have a
> relational database that does not "naturally" have all FK
> relationships as 1:N, then you have not normalized the data properly
> (or sufficiently).

If you say so.  If by definition "sufficient" normalization has all FK
relationships as 1:N, then by definition any design without that
property is not sufficiently normalized.  

I tried with my relations P & C to show relation B is unnecessary.  If
you can show updating such a database would lead to update anomalies
without B defined, I'd be interested to see that.  

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

James K. Lowden
In reply to this post by J Decker
On Tue, 28 Feb 2017 18:01:35 -0800
J Decker <[hidden email]> wrote:

> Then how would you properly find the children?  Or find any
> information about their parent, the child would have to in turn be
> deleted.
>
> foreign keys are as good as pointers.  

That's an interesting way to put it.  One of Codd's first papers
specifically rejected pointers as a database mechanism, and the
relational model relies entirely on values.  That there are no pointers
is by design.  

I accept that SQL foreign keys require a unique referent.  I have to;
it's a fact.  

I'm not convinced that's good or necessary.  I can believe it's
convenient, in the same way that "bag theory" is convenient to avoid
ensuring uniqueness in SQL.  

--jkl
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: foreign key cardinality

Keith Medcalf
In reply to this post by James K. Lowden
On Wednesday, 1 March, 2017 12:21, James K. Lowden <[hidden email]> wrote:

> Probably I'm overlooking something, and probably this is not the right
> forum.  SQLite adheres to the SQL standard; that's established.  Why
> does the standard say what it does?  I'm only saying it's not clear to
> me that there's theoretical justification.

I believe that Codd originally referred to this as the "Domain" requirement.  That is, that a "Parent" specified a domain, and that each "child" (member) must be a part of that domain.  Hence the requirement for the "Domain" (Parent) entries to be unique whilst the Child (Member of domain) entries are not, yet have a referent (foreign key) to the relation specifying the domain.





_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users