The Complexity of Querying Indefinite Data about Linearly Ordered Domains
✍ Scribed by Ron van der Meyden
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 969 KB
- Volume
- 54
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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 subproblems. Data complexity in the case of monadic predicates is one of these PTIME cases, but for disjunctive queries the proof is nonconstructive, using wellquasi-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 result implies that the latter is 6 p 2 -complete, solving an open problem of Klug (J. Assoc. Comput. Mach. 35, No. 1 (1988), 146 160). ] 1997 Academic Press IC(z 1 , z 2 , A), IC(z 3 , z 4 , B), z 1 <z 2 <z 3 <z 4 .
Here z 1 } } } z 4 are order constants representing unknown points of time and the object constants A, B refer to agent article no.