#
The Complexity of Querying Indefinite Data about Linearly Ordered Domains

## R. van der Meyden

In applications dealing with ordered domains, the available data is
frequently indefinite. While the domain is actually linearly ordered,
only some of 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.
We show that in this context queries are intractable even under the
data complexity measure, but identify a number of PTIME sub-problems.
Data complexity in the case of monadic predicates is one of these
PTIME cases, but for disjunctive queries the proof is
non-constructive, using well-quasi-order techniques. We also show
that the query problem we study is equivalent to the problem of
containment of conjunctive relational database queries containing
inequalities. One of our results implies that the latter is
Pi^p_2 complete, solving an open problem of Klug [JACM, 1988].

To appear in *Journal of Computer and Systems Science *

postscript (189K)