The Complexity of Querying Indefinite Data about Linearly Ordered Domains

摘要: In applications dealing with ordered domains, the available data is frequently indefinite. While domain actually linearly ordered, only some of order relations holding between points in are known. Thus, provides a partial order, and query answering involves determining what holds under all compatible linear orders. this paper we study complexity evaluating queries logical databases containing such indefinite information. We show that context intractable even measure, but identify number PTIME subproblems. Data case monadic predicates one these cases, for disjunctive proof nonconstructive, using well-quasi-order techniques. also problem equivalent to containment conjunctive relational database inequalities. One our result implies latter is?p2-complete, solving an open Klug (J. Assoc. Comput. Mach.35, No. 1 (1988), 146?160).