ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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

ACM SIGMOD Anthology

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

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

Referenced by

  1. Wilfred Ng: Extending Functional Dependencies in Indefinite Sequence Relations. ER 1999: 399-412
  2. 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)
  3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  4. Gösta Grahne: Horn Tables - An Efficient Tool for Handling Incomplete Information in Databases. PODS 1989: 75-82
  5. Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153
  6. Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. SIGMOD Conference 1987: 34-48
  7. Nadine Lerat: Query Processing in Incomplete Logical Databases. ICDT 1986: 260-277
  8. Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12

Copyright © Mon Nov 2 21:18:01 2009 by Michael Ley (ley@uni-trier.de)