A Generalisation of Entity and Referential Integrity in Relational Databases
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 35, Issue: 2, page 113-127
- ISSN: 0988-3754
Access Full Article
topAbstract
topHow to cite
topLevene, Mark, and Loizou, George. " A Generalisation of Entity and Referential Integrity in Relational Databases." RAIRO - Theoretical Informatics and Applications 35.2 (2010): 113-127. <http://eudml.org/doc/221954>.
@article{Levene2010,
abstract = {
Entity and referential integrity are the most fundamental constraints
that any relational database should satisfy.
We re-examine these fundamental constraints in the
context of incomplete relations, which may have null values of the types
"value exists but is unknown" and "value does not exist" .
We argue that in practice the restrictions that these constraints impose
on the occurrences of null values in relations are too strict.
We justify a generalisation of the said constraints wherein we use key families,
which are collections of attribute sets of a relation schema, rather than keys,
and foreign key families which are collections of pairs of attribute sets
of two relation schemas, rather than foreign keys.
Intuitively, a key family is satisfied in an incomplete relation
if each one of its tuples is uniquely identifiable
on the union of the attribute sets of the key family,
in all possible worlds of the incomplete relation,
and, in addition, is distinguishable from all the other tuples
in the incomplete relation by its nonnull values on some element in the key
family. Our proposal can be viewed as an extension of Thalheim's key set,
which only deals with null values of type "value exists but is unknown" .
The intuition behind the satisfaction of a foreign key family in an incomplete
database is that each pair $(F_i, K_i)$ of attribute sets in the foreign key
family takes the foreign key attribute values over Fi of a tuple
in one incomplete relation referencing the key attribute values over Ki
of a tuple in another incomplete relation.
Such referencing is defined only in the case when the foreign key attribute
values do not have any null values of the type "value does not exist" ;
we insist that the referencing be defined for at least one such pair.
We also investigate some combinatorial properties of key families,
and show that they are comparable to the standard
combinatorial properties of keys.
},
author = {Levene, Mark, Loizou, George},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Incomplete relation; null value; entity and referential integrity; key
family; foreign key family.; relational database},
language = {eng},
month = {3},
number = {2},
pages = {113-127},
publisher = {EDP Sciences},
title = { A Generalisation of Entity and Referential Integrity in Relational Databases},
url = {http://eudml.org/doc/221954},
volume = {35},
year = {2010},
}
TY - JOUR
AU - Levene, Mark
AU - Loizou, George
TI - A Generalisation of Entity and Referential Integrity in Relational Databases
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 2
SP - 113
EP - 127
AB -
Entity and referential integrity are the most fundamental constraints
that any relational database should satisfy.
We re-examine these fundamental constraints in the
context of incomplete relations, which may have null values of the types
"value exists but is unknown" and "value does not exist" .
We argue that in practice the restrictions that these constraints impose
on the occurrences of null values in relations are too strict.
We justify a generalisation of the said constraints wherein we use key families,
which are collections of attribute sets of a relation schema, rather than keys,
and foreign key families which are collections of pairs of attribute sets
of two relation schemas, rather than foreign keys.
Intuitively, a key family is satisfied in an incomplete relation
if each one of its tuples is uniquely identifiable
on the union of the attribute sets of the key family,
in all possible worlds of the incomplete relation,
and, in addition, is distinguishable from all the other tuples
in the incomplete relation by its nonnull values on some element in the key
family. Our proposal can be viewed as an extension of Thalheim's key set,
which only deals with null values of type "value exists but is unknown" .
The intuition behind the satisfaction of a foreign key family in an incomplete
database is that each pair $(F_i, K_i)$ of attribute sets in the foreign key
family takes the foreign key attribute values over Fi of a tuple
in one incomplete relation referencing the key attribute values over Ki
of a tuple in another incomplete relation.
Such referencing is defined only in the case when the foreign key attribute
values do not have any null values of the type "value does not exist" ;
we insist that the referencing be defined for at least one such pair.
We also investigate some combinatorial properties of key families,
and show that they are comparable to the standard
combinatorial properties of keys.
LA - eng
KW - Incomplete relation; null value; entity and referential integrity; key
family; foreign key family.; relational database
UR - http://eudml.org/doc/221954
ER -
References
top- S. Abiteboul, R. Hull and V. Vianu, Foundations of Databases. Addison-Wesley, Reading, MA (1995).
- ANSI/X3/SPARC, Study group on database management systems, interim report. Bull. ACM SIGFIDET 7 (1975).
- E.F. Codd, Extending the database relational model to capture more meaning. ACM Trans. Database Systems4 (1979) 397-434.
- E.F. Codd, The Relational Model for Database Management: Version 2. Addison-Wesley, Reading, MA (1990).
- C.J. Date, Referential integrity, in Relational Database: Selected Writings. Addison-Wesley, Reading, MA (1986) 41-63.
- C.J. Date, Composite keys, in Relational Database Writings 1989-1991. Addison-Wesley, Reading, MA (1992) 467-474.
- J. Demetrovics and V.D. Thi, Relations and minimal keys. Acta Cybernet.8 (1988) 279-285.
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979).
- T. Härder and J. Reinert, Access path support for referential integrity in SQL2. VLDB J.5 (1996) 196-214.
- N. Lerat and W. Lipski Jr., Nonapplicable nulls. Theoret. Comput. Sci.46 (1986) 67-82.
- M. Levene and G. Loizou, Null inclusion dependencies in relational databases. Inform. and Comput.136 (1997) 67-108.
- M. Levene and G. Loizou, A Guided Tour of Relational Databases and Beyond. Springer-Verlag, London (1999).
- C.L. Lucchesi and S.L. Osborn, Candidate keys for relations. J. Comput. System Sci.17 (1978) 270-279.
- D. Maier, The Theory of Relational Databases. Computer Science Press, Rockville, MD (1983).
- B. Thalheim, On semantic issues connected with keys in relational databases permitting null values. J. Inform. Process. Cybernet.25 (1989) 11-20.
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.