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