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

The Complexity of Querying Indefinite Data about Linearly Ordered Domains.

Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345
@inproceedings{DBLP:conf/pods/Meyden92,
  author    = {Ron van der Meyden},
  title     = {The Complexity of Querying Indefinite Data about Linearly Ordered
               Domains},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {331-345},
  ee        = {http://doi.acm.org/10.1145/137097.137902, db/conf/pods/Meyden92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In applications dealing with ordered domains, the available data is frequently indefinite. While the domain is actually linearly ordered, only some of all the order relations holding between points in the data are known. Thus, the data provides only a partial order, and query answering involves determining what holds under all the compatible linear orders. In this paper we study the complexity of evaluating queries in logical databases containing such indefinite information. This problem is related to the problem of containment of relational queries containing inequalities. One of our results implies that the latter is Pi2p-complete, solving an open problem. In general, even data complexity is intractable. We identify a number of tractable (PTIME) sub-problems. Data complexity in the case of monadic predicates is one of these PTIME problems, but for disjunctive queries the proof is nonconstructive, using well-quasi-order techniques.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1581 KB]

Journal Version

Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. J. Comput. Syst. Sci. 54(1): 113-135(1997) BibTeX

References

[1]
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
[2]
James F. Allen: Maintaining Knowledge about Temporal Intervals. Commun. ACM 26(11): 832-843(1983) BibTeX
[3]
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) BibTeX
[4]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[5]
Michael R. Fellows, Michael A. Langston: Nonconstructive Advances in Polynomial-Time Complexity. Inf. Process. Lett. 26(3): 155-162(1987) BibTeX
[6]
Michael R. Fellows, Michael A. Langston: Nonconstructive tools for proving polynomial-time decidability. J. ACM 35(3): 727-739(1988) BibTeX
[7]
...
[8]
...
[9]
Joseph Y. Halpern, Yoav Shoham: A Propositional Model Logic of Time Intervals. LICS 1986: 279-292 BibTeX
[10]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
[11]
...
[12]
Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX
[13]
...
[14]
Jean-Louis Lassez: Querying Constraints. PODS 1990: 288-298 BibTeX
[15]
David Maier: The Complexity of Some Problems on Subsequences and Supersequences. J. ACM 25(2): 322-336(1978) BibTeX
[16]
Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 BibTeX
[17]
...
[18]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[19]
...
[20]
Ron van der Meyden: Recursively Indefinite Databases. ICDT 1990: 364-378 BibTeX
[21]
...
[22]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[23]
Moshe Y. Vardi: Querying Logical Databases. J. Comput. Syst. Sci. 33(2): 142-160(1986) BibTeX
[24]
Marc B. Vilain, Henry A. Kautz: Constraint Propagation Algorithms for Temporal Reasoning. AAAI 1986: 377-382 BibTeX

Referenced by

  1. Todd D. Millstein, Alon Y. Levy, Marc Friedman: Query Containment for Data Integration Systems. PODS 2000: 67-75
  2. Sara Cohen, Werner Nutt, Alexander Serebrenik: Rewriting Aggregate Queries Using Views. PODS 1999: 155-166
  3. Werner Nutt, Yehoshua Sagiv, Sara Shurin: Deciding Equivalences Among Aggregate Queries. PODS 1998: 214-223
  4. Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148
  5. Xubo Zhang, Z. Meral Özsoyoglu: Implication and Referential Constraints: A New Formal Reasoning. IEEE Trans. Knowl. Data Eng. 9(6): 894-910(1997)
  6. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
  7. Oscar H. Ibarra, Jianwen Su: On the Containment and Equivalence of Database Queries with Linear Constraints. PODS 1997: 32-43
  8. Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40
  9. Alon Y. Levy: Obtaining Complete Answers from Incomplete Databases. VLDB 1996: 402-412
  10. Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237
  11. Alon Y. Levy, Yehoshua Sagiv: Semantic Query Optimization in Datalog Programs. PODS 1995: 163-173
  12. Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104
  13. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  14. Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. ICDT 1995: 322-337
  15. Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55
  16. Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181
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:34:07 2009