Obtaining Complete Answers from Incomplete Databases.

@inproceedings{DBLP:conf/vldb/Levy96,
  author    = {Alon Y. Levy},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Obtaining Complete Answers from Incomplete Databases},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {402-412},
  ee        = {db/conf/vldb/Levy96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We consider the problem of answering queries from databases that may be incomplete. A database is incomplete if some tuples may be missing from some relations, and only a (perhaps empty) part of each relation is known to be complete. This problem arises in several contexts. For example, systems that provide access to multiple heterogeneous information sources often encounter incomplete sources. As another example, a database undergoing a long transaction is temporarily incomplete. The question we address is to determine whether the answer to a specific given query is complete even when the database is incomplete.

First, we show that the problem of deciding query-completeness is completely characterized as a problem of deciding whether a query is independent of an insertion update. As a result, we obtain several novel algorithms for deciding query-completeness. Second, we show that an important case of the problem of determining independence of queries from updates can be done in polynomial time, whereas the best known algorithms previously are exponential. This is the case in which the updated tuples are described using constraints with built-in order predicates. Finally, we describe an algorithm that determines whether the answer to the query is complete in the *current* state of the database (as opposed to *any* state of the database). The algorithm uses several auxiliary queries to determine completeness.

Copyright © 1996 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

• 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/vldb8997 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

References

[ACHK94]

Yigal Arens, Chin Y. Chee, Chun-Nan Hsu, Craig A. Knoblock: Retrieving and Integrating Data from Multiple Information Sources. Int. J. Cooperative Inf. Syst. 2(2): 127-158(1993) BibTeX

[ASU79a]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX

[ASU79b]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[BCL89]

José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) BibTeX

[CGMH+94]

Sudarshan S. Chawathe, Hector Garcia-Molina, Joachim Hammer, Kelly Ireland, Yannis Papakonstantinou, Jeffrey D. Ullman, Jennifer Widom: The TSIMMIS Project: Integration of Heterogeneous Information Sources. IPSJ 1994: 7-18 BibTeX

[CM77]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[CV92]

Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66 BibTeX

[CV94]

Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116 BibTeX

[EGW94]

Oren Etzioni, Keith Golden, Daniel S. Weld: Tractable Closed World Reasoning with Updates. KR 1994: 178-189 BibTeX

[Elk90]

Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160 BibTeX

[EW94]

Oren Etzioni, Daniel S. Weld: A Softbot-Based Interface to the Internet. Commun. ACM 37(7): 72-76(1994) BibTeX

[Gin87]

...

[JK83]

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. 28(1): 167-189(1984) BibTeX

[Klu88]

Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX

[LMSS95]

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX

[LRO96a]

Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Query-Answering Algorithms for Information Agents. AAAI/IAAI, Vol. 1 1996: 40-47 BibTeX

[LRO96b]

Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262 BibTeX

[LS93]

Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181 BibTeX

[LSK95]

Alon Y. Levy, Divesh Srivastava, Thomas Kirk: Data Model and Query Evaluation in Global Information Systems. J. Intell. Inf. Syst. 5(2): 121-143(1995) BibTeX

[Mot89]

Amihai Motro: Integrity = Validity + Completeness. ACM Trans. Database Syst. 14(4): 480-502(1989) BibTeX

[Sag88]

Yehoshua Sagiv: Optimizing Datalog Programs. Foundations of Deductive Databases and Logic Programming. 1988: 659-698 BibTeX

[Shm93]

Oded Shmueli: Equivalence of DATALOG Queries is Undecidable. J. Log. Program. 15(3): 231-241(1993) BibTeX

[SY81]

Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX

[Ull89]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[vdM92]

Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345 BibTeX

Referenced by

1. Chen Li, Edward Y. Chang: On Answering Queries in the Presence of Limited Access Patterns. ICDT 2001: 219-233
2. Moshe Y. Vardi: Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000: 76-85
3. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: View-Based Query Processing for Regular Path Queries with Inverse. PODS 2000: 58-66
4. Gösta Grahne, Alberto O. Mendelzon: Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999: 332-347
5. Xun Cheng, Guozhu Dong, Tzekwan Lau, Jianwen Su: Data Integration by Describing Sources with Constraint Databases. ICDE 1999: 374-381
6. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)
7. Beng Chin Ooi, Cheng Hian Goh, Kian-Lee Tan: Fast High-Dimensional Data Search in Incomplete Databases. VLDB 1998: 357-367
8. Hector Garcia-Molina, Wilburt Labio, Jun Yang: Expiring Data in a Warehouse. VLDB 1998: 500-511