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\mathcal{D}
the result of the transformation
P on
D\mathcal{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 (
φ,
k,
j), where
φ is a projection-free conjunctive query and
k,
j are natural numbers, decide whether there exists a database
D\mathcal{D}
such that, for each triple (
φ,
k,
j) in the set, there exists a natural number
α, such that there are exactly
k+
j*
α tuples satisfying the query
φ in
D\mathcal{D}
. Our main technical contribution consists of a NEXPTIME algorithm for the last problem.
Keywords Complexity - Logic - Relational databases - Typechecking - XML
Partially supported by Polish Ministry of Science and Higher Education research project N206 022 31/3660, 2006/2009.
This paper is an extended version of 20, where the coNEXPTIME upper bound was shown.