Dependency Satisfaction in Databases with Incomplete Information.

Gösta Grahne: Dependency Satisfaction in Databases with Incomplete Information. VLDB 1984: 37-45

@inproceedings{DBLP:conf/vldb/Grahne84,
  author    = {G{\"o}sta Grahne},
  editor    = {Umeshwar Dayal and
               Gunter Schlageter and
               Lim Huat Seng},
  title     = {Dependency Satisfaction in Databases with Incomplete Information},
  booktitle = {Tenth International Conference on Very Large Data Bases, August
               27-31, 1984, Singapore, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1984},
  isbn      = {0-934613-16-8},
  pages     = {37-45},
  ee        = {db/conf/vldb/Grahne84.html},
  crossref  = {DBLP:conf/vldb/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Two of the major problems raised by information incompleteness in databases are how to evaluate queries and how to take data dependencies into account. We give a unified solution of these two intermingled problems for the relational model. Formal criteria for the correctness of the relational algebra and dependency satisfaction are presented. We give a correct redefinition of the complete relational algebra and present a method, called a chase, for enforcing a set of functional and full join dependencies on a relation with null-values of type "value exists, but is presently unknown". This novel chase can also be regarded as a generalization of previously known chase methods. The title of the paper reflects the emphasis of its contribution.

Copyright © 1984 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

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/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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/aDVD1 or /dvd

Printed Edition

Umeshwar Dayal, Gunter Schlageter, Lim Huat Seng (Eds.): Tenth International Conference on Very Large Data Bases, August 27-31, 1984, Singapore, Proceedings. Morgan Kaufmann 1984, ISBN 0-934613-16-8
Contents

References

[Abi]: ...
[Bis1]: Joachim Biskup: A Formal Approach to Null Values in Database Relations. Advances in Data Base Theory 1979: 299-341
[Bis2]: Joachim Biskup: A Foundation of Codd's Relational Maybe-Operations. ACM Trans. Database Syst. 8(4): 608-636(1983)
[FUV]: Ronald Fagin, Jeffrey D. Ullman, Moshe Y. Vardi: On the Semantics of Updates in Databases. PODS 1983: 352-365
[Gra1]: ...
[Gra2]: ...
[IL1]: Tomasz Imielinski, Witold Lipski Jr.: On Representing Incomplete Information in a Relational Data Base. VLDB 1981: 388-397
[IL2]: Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984)
[IL3]: Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information and Dependencies in Relational Databases. SIGMOD Conference 1983: 178-184
[Lie]: Y. Edmund Lien: Multivalued Dependencies with Null Values in Relational Data Bases. VLDB 1979: 61-66
[Lip]: ...
[Mai]: David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents
[MMS]: David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979)
[Rei]: Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76
[Sci]: ...
[Ull]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
[Vas1]: Yannis Vassiliou: Null Values in Data Base Management: A Denotational Semantics Approach. SIGMOD Conference 1979: 162-169
[Vas2]: Yannis Vassiliou: Functional Dependencies and Incomplete Information. VLDB 1980: 260-269
[Yp]: Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41(1982)