Normalizing Incomplete Databases.

@inproceedings{DBLP:conf/pods/Libkin95,
  author    = {Leonid Libkin},
  title     = {Normalizing Incomplete Databases},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {219-230},
  ee        = {http://doi.acm.org/10.1145/212433.220217, db/conf/pods/Libkin95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Databases are often incomplete because of the presence of disjunctive information, due to conflicts, partial knowledge and other reasons. Queries against such databases often ask questions about various possibilities encoded by the stored data, rather than the stored data itself. Normalization, which is a mechanism for asking such queries, was presented in Libkin&Wong, PODS'93; however, it had exponential space complexity.

The main goal of this paper is to develop a general theory of answering queries against incomplete databases with disjunctive information, and use it to design practical algorithms for query evaluation. We define the semantics of such databases and prove normalization theorems for set- and bag-based complex objects. These theorems provide us with programming primitives that one needs in order to obtain the list of all possibilities encoded by a complex object with disjunctions.

We study two ways of making query evaluation faster and more space efficient. Partial normalization allows us to disregard some of the disjunctions if they do not affect a given query. We also design a new normalization algorithm that produces objects represented by an incomplete database one-by-one, rather than all at once. It has linear space complexity and allows us to speed up many classes of queries.

Algorithms presented in this paper have been implemented in existing dbpl. We present experimental results that demonstrate substantial improvement over standard algorithms, both in space and time.

Copyright © 1995 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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[AB88]

Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX

[AH95]

Serge Abiteboul, Gerd G. Hillebrand: Space Usage in Functional Query Languages. ICDT 1995: 439-454 BibTeX

[AKG91]

Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. Theor. Comput. Sci. 78(1): 158-187(1991) BibTeX

[Alb91]

Joseph Albert: Algebraic Properties of Bag Data Types. VLDB 1991: 211-219 BibTeX

[BBN91]

Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 BibTeX

[BBW92]

Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX

[BDW91]

Peter Buneman, Susan B. Davidson, Aaron Watters: A Semantics for Complex Objects and Approximate Answers. J. Comput. Syst. Sci. 43(1): 170-218(1991) BibTeX

[BJO91]

Peter Buneman, Achim Jung, Atsushi Ohori: Using Powerdomains to Generalize Relational Databases. Theor. Comput. Sci. 91(1): 23-55(1991) BibTeX

[DJ90]

...

[Gir87]

...

[GM93]

Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58 BibTeX

[Gun92]

...

[GL94]

Elsa L. Gunter, Leonid Libkin: OR-SML: A Functional Database Programming Language for Disjunctive Information and Its Applications. DEXA 1994: 641-650 BibTeX

[HMT90]

...

[IL84]

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

[INV91a]

Tomasz Imielinski, Shamim A. Naqvi, Kumar V. Vadaparty: Incomplete Objects - A Data Model for Design and Planning Applications. SIGMOD Conference 1991: 288-297 BibTeX

[INV91b]

Tomasz Imielinski, Shamim A. Naqvi, Kumar V. Vadaparty: Querying Design and Planning Databases. DOOD 1991: 524-545 BibTeX

[IMV89]

Tomasz Imielinski, Ron van der Meyden, Kumar V. Vadaparty: Complexity Tailored Design: A New Design Methodology for Databases With Incomplete Information. J. Comput. Syst. Sci. 51(3): 405-432(1995) BibTeX

[Lib91]

Leonid Libkin: A Relational Algebra for Complex Objects Based on Partial Information. MFDBS 1991: 29-43 BibTeX

[Lib92]

...

[Lib95]

Leonid Libkin: Approximation in Databases. ICDT 1995: 411-424 BibTeX

[LW93a]

Leonid Libkin, Limsoon Wong: Semantic Representations and Query Languages for Or-sets. PODS 1993: 37-48 BibTeX

[LW93b]

Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114 BibTeX

[LW94]

Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166 BibTeX

[LMR92]

...

[Rou91]

...

[SP94]

Dan Suciu, Jan Paredaens: Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure. PODS 1994: 201-209 BibTeX

Referenced by

1. Mengchi Liu, Tok Wang Ling: A Data Model for Semistructured Data with Partial and Inconsistent Information. EDBT 2000: 317-331
2. Leonid Libkin: Query Language Primitives for Programming with Incomplete Databases. DBPL 1995: 6