Modulo Constraints and the Complexity of Typechecking XML Views
The typechecking problem for transformations of relational data into tree data is the following: given a relational-to-XML transformation P, and an XML type d, decide whether for every database instance D the result of the transformation P on D satisfies d. TreeQL programs with projection-free conjunctive queries (see Alon et al. in ACM Trans. Comput. Log. 4(3): 315-354, 2003) are considered as transformations and DTDs with arbitrary regular expressions as XML types. A non-elementary upper bound for the typechecking problem was already given by Alon et al. (ACM Trans. Comput. Log. 4(3): 315-354, 2003) (although in a more general setting, where equality and negation in projection-free conjunctive queries and additional universal integrity constraints are allowed). In this paper we show that the typechecking problem is coNEXPTIME-complete. As an intermediate step we consider the following problem, which can be formulated independently of XML notions. Given a set of triples of the form (phi, k, j), where phi is a projection-free conjunctive query and k, j are natural numbers, decide whether there exists a database D such that, for each triple (phi, k, j) in the set, there exists a natural number alpha, such that there are exactly k + j * alpha tuples satisfying the query phi in D. Our main technical contribution consists of a NEXPTIME algorithm for the last problem.
complexity typechecking xml logic relational databases