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)

[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)

[ASU79b]

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

[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)

[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

[CM77]

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

[CV92]

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

[CV94]

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

[EGW94]

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

[Elk90]

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

[EW94]

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

[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)

[Klu88]

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

[LMSS95]

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

[LRO96a]

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

[LRO96b]

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

[LS93]

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

[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)

[Mot89]

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

[Sag88]

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

[Shm93]

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

[SY81]

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

[Ull89]

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

[vdM92]

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