ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Obtaining Complete Answers from Incomplete Databases.

Alon Y. Levy: Obtaining Complete Answers from Incomplete Databases. VLDB 1996: 402-412
@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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ASU79b]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CM77]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CV92]
Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CV94]
Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EGW94]
Oren Etzioni, Keith Golden, Daniel S. Weld: Tractable Closed World Reasoning with Updates. KR 1994: 178-189 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Elk90]
Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EW94]
Oren Etzioni, Daniel S. Weld: A Softbot-Based Interface to the Internet. Commun. ACM 37(7): 72-76(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Klu88]
Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMSS95]
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LRO96a]
Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Query-Answering Algorithms for Information Agents. AAAI/IAAI, Vol. 1 1996: 40-47 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LRO96b]
Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LS93]
Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mot89]
Amihai Motro: Integrity = Validity + Completeness. ACM Trans. Database Syst. 14(4): 480-502(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sag88]
Yehoshua Sagiv: Optimizing Datalog Programs. Foundations of Deductive Databases and Logic Programming. 1988: 659-698 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shm93]
Oded Shmueli: Equivalence of DATALOG Queries is Undecidable. J. Log. Program. 15(3): 231-241(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SY81]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[vdM92]
Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:22:55 2010 by Michael Ley (ley@uni-trier.de)