A Foundation of Codd's Relational Maybe-Operations.

@article{DBLP:journals/tods/Biskup83,
  author    = {Joachim Biskup},
  title     = {A Foundation of Codd's Relational Maybe-Operations},
  journal   = {ACM Trans. Database Syst.},
  volume    = {8},
  number    = {4},
  year      = {1983},
  pages     = {608-636},
  ee        = {http://doi.acm.org/10.1145/319996.320014, db/journals/tods/Biskup83.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Database relations which possibly contain maybe-tuples and null values of type "value at present unknown" are studied. Maybe-tuples and null values are formally interpreted by our notion of representation, which uses classical notions of predicate logic, elaborates Codd's proposal of maybe-tuples, and adopts Reiter's concept of a closed world. Precise notions of information content and redundancy, associated with our notion of representation, are investigated. Extensions of the relational algebra to relations with maybe-tuples and null values are proposed. Our extensions are essentially Codd's, with some modifications. It is proved that these extensions have natural properties which are formally stated as being adequate and restricted.

By the treatment of difference and division, our formal framework can be used even for operations that require "negative information." Finally, extensions of update operations are discussed.

Copyright © 1983 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

...

[2]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX

[3]

Joachim Biskup: A Formal Approach to Null Values in Database Relations. Advances in Data Base Theory 1979: 299-341 BibTeX

[4]

...

[5]

...

[6]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[7]

E. F. Codd: Relational Database: A Practical Foundation for Productivity. Commun. ACM 25(2): 109-117(1982) BibTeX

[8]

Hervé Gallaire, Jack Minker (Eds.): Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977. Advances in Data Base Theory Plemum Press 1978, ISBN 0-306-40060-X
Contents BibTeX

[9]

John Grant: Null Values in a Relational Data Base. Inf. Process. Lett. 6(5): 156-157(1977) BibTeX

[10]

John Grant: Partial Values in a Tabular Database Model. Inf. Process. Lett. 9(2): 97-99(1979) BibTeX

[11]

...

[12]

Tomasz Imielinski, Witold Lipski Jr.: On Representing Incomplete Information in a Relational Data Base. VLDB 1981: 388-397 BibTeX

[13]

...

[14]

Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) BibTeX

[15]

Witold Lipski Jr.: On Databases with Incomplete Information. J. ACM 28(1): 41-70(1981) BibTeX

[16]

Jean-Marie Nicolas, Hervé Gallaire: Data Base: Theory vs. Interpretation. Logic and Data Bases 1977: 33-54 BibTeX

[17]

Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76 BibTeX

[18]

Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX

[19]

Yannis Vassiliou: Null Values in Data Base Management: A Denotational Semantics Approach. SIGMOD Conference 1979: 162-169 BibTeX

[20]

Yannis Vassiliou: Functional Dependencies and Incomplete Information. VLDB 1980: 260-269 BibTeX

[21]

...

Referenced by

1. H. V. Jagadish: The INCINERATE Data Model. ACM Trans. Database Syst. 20(1): 71-110(1995)
2. Fereidoon Sadri: Information Source Tracking Method: Efficiency Issues. IEEE Trans. Knowl. Data Eng. 7(6): 947-954(1995)
3. Jui-Shang Chiu, Arbee L. P. Chen: An Exploration of Relationships Among Exclusive Disjunctive Data. IEEE Trans. Knowl. Data Eng. 7(6): 928-940(1995)
4. Helmut Kaufmann, Moira C. Norrie: Relaxation of Correctness in Database Systems. ADBIS 1995: 90-105
5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
6. Frank Shou-Cheng Tseng, Arbee L. P. Chen, Wei-Pang Yang: Searching a Minimal Semantically-Equivalent Subset of a Set of Partial Values. VLDB J. 2(4): 489-512(1993)
7. Adegbeniga Ola, Gultekin Özsoyoglu: Incomplete Relational Database Models Based on Intervals. IEEE Trans. Knowl. Data Eng. 5(2): 293-308(1993)
8. Shashi K. Gadia, Sunil S. Nair, Yiu-Cheong Poon: Incomplete Information in Relational Temporal Databases. VLDB 1992: 395-406
9. José Alberto Fernández, Jack Minker: Semantics of Disjunctive Deductive Databases. ICDT 1992: 21-50
10. Adegbemiga Ola: Relational Databases with Exclusive Disjunctions. ICDE 1992: 328-336
11. Fereidoon Sadri: Reliability of Answers to Queries in Relational Databases. IEEE Trans. Knowl. Data Eng. 3(2): 245-251(1991)
12. Ken-Chih Liu, Rajshekhar Sunderraman: A Generalized Relational Model for Indefinite and Maybe Information. IEEE Trans. Knowl. Data Eng. 3(1): 65-77(1991)
13. Fereidoon Sadri: Modeling Uncertainty in Databases. ICDE 1991: 122-131
14. Ken-Chih Liu, Lu Zhang: Natural Joins in Relational Databases with Indefinite and Maybe Information. ICDE 1991: 132-139
15. Nong Zhou: Representation and Processing of Uncertain Information in Relational Databases. ER 1991: 371-388
16. Ken-Chih Liu, Rajshekhar Sunderraman: Indefinite and Maybe Information in Relational Databases. ACM Trans. Database Syst. 15(1): 1-39(1990)
17. Ken-Chih Liu, Rajshekhar Sunderraman: On Representing Indefinite and Maybe Information in Relational Databases: A Generalization. ICDE 1990: 495-502
18. Howard M. Dreizen, Shi-Kuo Chang: Imprecise Schema: A Rationale for Relations with Embedded Subrelations. ACM Trans. Database Syst. 14(4): 447-479(1989)
19. Linda G. DeMichiel: Resolving Database Incompatibility: An Approach to Performing Relational Operations over Mismatched Domains. IEEE Trans. Knowl. Data Eng. 1(4): 485-493(1989)
20. Adegbemiga Ola, Gultekin Özsoyoglu: A Family of Incomplete Relational Database Models. VLDB 1989: 23-31
21. Linda G. DeMichiel: Performing Operations over Mismatched Domains. ICDE 1989: 36-45
22. K. V. S. V. N. Raju, Arun K. Majumdar: Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Relational Database Systems. ACM Trans. Database Syst. 13(2): 129-166(1988)
23. Georg Gottlob, Roberto Zicari: Closed World Databases Opened Through Null Values. VLDB 1988: 50-61
24. Ken-Chih Liu, Rajshekhar Sunderraman: On Representing Indefinite and Maybe Information in Relational Databases. ICDE 1988: 250-257
25. Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12
26. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
27. Gösta Grahne: Dependency Satisfaction in Databases with Incomplete Information. VLDB 1984: 37-45
28. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents