ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

On the Representation and Querying of Sets of Possible Worlds.

Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. SIGMOD Conference 1987: 34-48
@inproceedings{DBLP:conf/sigmod/AbiteboulKG87,
  author    = {Serge Abiteboul and
               Paris C. Kanellakis and
               G{\"o}sta Grahne},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {On the Representation and Querying of Sets of Possible Worlds},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {34-48},
  ee        = {http://doi.acm.org/10.1145/38713.38724, db/conf/sigmod/AbiteboulKG87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We represent a set of possible worlds using an incomplete information database. The representation techniques that we study form a hierarchy, which generalizes relations of constants. This hierarchy ranges from the very simple Codd-table, (i. e., a relation of constants and distinct variables called nulls, which stand for values present but unknown), to much more complex mechanisms involving views on conditioned-tables, (i. e., queries on Codd-tables together with conditions). The views we consider are the queries that have polynomial data-complexity on complete information databases. Our conditions are conjunctions of equalities and inequalities.
  1. We provide matching upper and lower bounds on the data-complexity of testing containement, membership, and uniqueness for sets of possible worlds and we fully classify these problems with respect to our representation hierarchy. The most surprising result in this classification is that it is complete in Pi2P, whether a set of possible worlds represented by a Codd-table is a subset of a set of possible worlds represented by a Codd-table with one conjuction of inequalities.
  2. We investigate the data-complexity of querying incomplete information databases. We examine both asking for certain facts and for possible facts. Our approach is algebraic but our bounds also apply to logical databases. We show that asking for a certain fact is coNP-complete, even for a fixed first order query on a Codd-table. We thus strengthen a lower bound of [16], who showed that this holds for a Codd-table with a conjunction of inequalities. For each fixed positive existential query we present a polynomial algorithm solving the bounded possible fact problem of this query on conditioned-tables. We show that our approach is, in a sense, the best possible, by deriving two NP-completeness lower bounds for the bounded possible fact problem when the fixed query contains either negation or recursion.

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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Umeshwar Dayal, Irving L. Traiger (Eds.): Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, California, May 27-29, 1987. ACM Press 1987 BibTeX , SIGMOD Record 16(3)
Contents

Online Edition: ACM Digital Library


References

[1]
Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12 BibTeX
[2]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[3]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[4]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[5]
Stavros S. Cosmadakis: The Complexity of Evaluating Relational Queries. Information and Control 58(1-3): 101-112(1983) BibTeX
[6]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[7]
Gösta Grahne: Dependency Satisfaction in Databases with Incomplete Information. VLDB 1984: 37-45 BibTeX
[8]
Peter Honeyman, Richard E. Ladner, Mihalis Yannakakis: Testing the Universal Instance Assumption. Inf. Process. Lett. 10(1): 14-19(1980) BibTeX
[9]
Tomasz Imielinski: On Algebraic Query Processing in Logical Databases. Advances in Data Base Theory 1982: 285-318 BibTeX
[10]
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX
[11]
Witold Lipski Jr.: On Databases with Incomplete Information. J. ACM 28(1): 41-70(1981) BibTeX
[12]
David Maier, Yehoshua Sagiv, Mihalis Yannakakis: On the Complexity of Testing Implications of Functional and Join Dependencies. J. ACM 28(4): 680-695(1981) BibTeX
[13]
...
[14]
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
[15]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[16]
Moshe Y. Vardi: Querying Logical Databases. PODS 1985: 57-65 BibTeX
[17]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[18]
Carlo Zaniolo: Database Relations with Null Values. PODS 1982: 27-33 BibTeX

Referenced by

  1. Chris Olston, Jennifer Widom: Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data. VLDB 2000: 144-155
  2. Oliver Haase, Andreas Henrich: A Closed Approach to Vague Collections in Partly Inaccessible Distributed Databases. ADBIS 1999: 261-274
  3. Julie Wilks: Querying and Updating Constraint Databases with Incomplete Information. ADBIS 1997: 80-89
  4. Simon Parsons: Current Approaches to Handling Imperfect Information in Data and Knowledge Bases. IEEE Trans. Knowl. Data Eng. 8(3): 353-372(1996)
  5. 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)
  6. Adegbeniga Ola, Gultekin Özsoyoglu: Incomplete Relational Database Models Based on Intervals. IEEE Trans. Knowl. Data Eng. 5(2): 293-308(1993)
  7. Adegbemiga Ola: Relational Databases with Exclusive Disjunctions. ICDE 1992: 328-336
  8. Ken-Chih Liu, Lu Zhang: Natural Joins in Relational Databases with Indefinite and Maybe Information. ICDE 1991: 132-139
  9. Yves Caseau: The LAURE Model for Object-Oriented Logic Databases. DASFAA 1991: 411-420
  10. Adegbemiga Ola, Gultekin Özsoyoglu: A Family of Incomplete Relational Database Models. VLDB 1989: 23-31
  11. Tomasz Imielinski, Kumar V. Vadaparty: Complexity of Query Processing in Databases with OR-Objects. PODS 1989: 51-65
  12. Gösta Grahne: Horn Tables - An Efficient Tool for Handling Incomplete Information in Databases. PODS 1989: 75-82
  13. Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153
  14. Serge Abiteboul: Updates, A New Frontier. ICDT 1988: 1-18
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:48 2009