Incomplete Information and Dependencies in Relational Databases.

@inproceedings{DBLP:conf/sigmod/ImielinskiL83,
  author    = {Tomasz Imielinski and
               Witold Lipski Jr.},
  editor    = {David J. DeWitt and
               Georges Gardarin},
  title     = {Incomplete Information and Dependencies in Relational Databases},
  booktitle = {SIGMOD'83, Proceedings of Annual Meeting, San Jose, California,
               May 23-26, 1983},
  publisher = {ACM Press},
  year      = {1983},
  pages     = {178-184},
  ee        = {http://doi.acm.org/10.1145/582192.582222, db/conf/sigmod/ImielinskiL83.html},
  crossref  = {DBLP:conf/sigmod/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

An incomplete information relational database combines two types of information about the real world modeled by the database: (a) the information represented by tables with null values ("value not known") allowed as entries, and (b) the data dependencies, which are known to be satisfied in the real world. We view the well known chase procedure as a process which transforms type (b) information into an "equivalent" type (a) form. Assuming that the data dependencies are arbitrary implicational dependencies, we show that this transformation is not quite equivalent, but the corruption of information introduced cannot be discovered if the query language uses the operations of projection, positive selection (i.e. no negation in selection condition), union, natural join and renaming of attributes. This result can be interpreted also as the new important property of chase.

The influence of so-called view dependencies on the table with null values is also examined.

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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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/smod7592 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/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[BV]

Catriel Beeri, Moshe Y. Vardi: Formal Systems for Tuple and Equality Generating Dependencies. SIAM J. Comput. 13(1): 76-98(1984) BibTeX

[GMN]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX

[I]

...

[IL1]

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

[IL2]

Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX

[IL3]

Tomasz Imielinski, Witold Lipski Jr.: Inverting Relational Expressions - A Uniform and Natural Technique for Various Database Problems. PODS 1983: 305-311 BibTeX

[K]

Robert A. Kowalski: Logic for Data Description. Logic and Data Bases 1977: 77-103 BibTeX

[KP]

Anthony C. Klug, Rod Price: Determining View Dependencies Using Tableaux. ACM Trans. Database Syst. 7(3): 361-380(1982) BibTeX

[MMS]

David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX

[Ull]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[V]

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

Referenced by

1. 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)
2. 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)
3. Ken-Chih Liu, Rajshekhar Sunderraman: A Generalized Relational Model for Indefinite and Maybe Information. IEEE Trans. Knowl. Data Eng. 3(1): 65-77(1991)
4. Ken-Chih Liu, Rajshekhar Sunderraman: On Representing Indefinite and Maybe Information in Relational Databases: A Generalization. ICDE 1990: 495-502
5. Gösta Grahne: Horn Tables - An Efficient Tool for Handling Incomplete Information in Databases. PODS 1989: 75-82
6. Ken-Chih Liu, Rajshekhar Sunderraman: On Representing Indefinite and Maybe Information in Relational Databases. ICDE 1988: 250-257
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
9. Gösta Grahne: Dependency Satisfaction in Databases with Incomplete Information. VLDB 1984: 37-45
10. Witold Lipski Jr.: On Relational Algebra with Marked Nulls. PODS 1984: 201-203
11. Arthur M. Keller, Marianne Winslett: Approaches for Updating Databases With Incomplete Information and Nulls. ICDE 1984: 332-340
12. Tomasz Imielinski, Witold Lipski Jr.: Inverting Relational Expressions - A Uniform and Natural Technique for Various Database Problems. PODS 1983: 305-311