Claire David
email: claire.david@univ-mlv.fr

Amélie Gheerbrant

Leonid Libkin
email: libkin@inf.ed.ac.uk

Wim Martens
email: wim.martens@uni-bayreuth.de

Containment of Pattern-Based Queries over Data Trees

Keywords: H, 2, 3 [Database management]: Languages-Query Languages; F, 2 [Analysis of algorithms and problem complexity]: Algorithms, Theory

published or not. The documents may come

INTRODUCTION

Static analysis of queries and specifications has been actively investigated in the context of XML, not only due to its importance in tasks such as query optimization but also due to a very different nature of the results brought to the fore by the hierarchical structure of XML documents [START_REF] Abiteboul | Reasoning about XML update constraints[END_REF][START_REF] Alon | XML with data values: typechecking revisited[END_REF][START_REF] Arenas | On the complexity of verifying consistency of XML specifications[END_REF][START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF][START_REF] Bojanczyk | Two-variable logic on words with data[END_REF][START_REF] Calvanese | Regular XPath: constraints, query containment and view-based answering for XML documents[END_REF][START_REF] David | Complexity of data tree patterns over XML documents[END_REF][START_REF] Fan | On XML integrity constraints in the presence of DTDs[END_REF][START_REF] Figueira | Satisfiability of downward XPath with data equality tests[END_REF][START_REF] Genevés | A system for the static analysis of XPath[END_REF][START_REF] Libkin | Reasoning about XML with temporal logics and automata[END_REF][START_REF] Maneth | Exact XML type checking in polynomial time[END_REF][START_REF] Neven | On the complexity of XPath containment in the presence of disjunction, DTDs, and variables[END_REF][START_REF] Th | XPath query containment[END_REF]. Typical reasoning problems include consistency of queries or constraints with respect to schema information, typechecking of transformations, security of views, and crucially, query containment, with or without schema information. The latter is the problem we deal with. Starting from the relational case, we know that query containment is often the technical core of many query optimization [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]. In recent years query containment found multiple applications not only in query answering and optimization, but also in data integration, exchange, and provenance among others [START_REF] Green | Containment of conjunctive queries on annotated relations[END_REF][START_REF] Halevy | Answering queries using views: A survey[END_REF][START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF].

Already in the relational case, we know that, by and large, containment is decidable for conjunctive queries and relatives, and undecidable for expressive queries, such as those coming from the full relational algebra. In the XML case, static analysis of queries has been largely restricted to queries in various fragments of XPath [START_REF] Th | XPath query containment[END_REF] and analogs of conjunctive queries [START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF][START_REF] Björklund | Conjunctive query containment over trees[END_REF][START_REF] Gottlob | Conjunctive queries over trees[END_REF], primarily describing the structure of documents. The latter classified the complexity of query containment depending on the list of used axes, providing a seemingly complete picture.

Nonetheless, the picture depicted by [START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF][START_REF] Björklund | Conjunctive query containment over trees[END_REF][START_REF] Gottlob | Conjunctive queries over trees[END_REF] is not as complete as it seems. Firstly, this work basically took relational conjunctive queries on top of XML documents, and considered containment problems for them. Queries like that in a way do not follow tree patterns. An example of such a query is one saying that we have two nodes s and s ′ , so that s ′ is a descendant of s, and we have other nodes s 1 , . . . , s n so that each s i is a descendant of s and an ancestor of s ′ . This says that the s i s appear in some order on the unique path from s and s ′ . But note that the query itself is DAG-shaped rather than tree-shaped (i.e., if we consider its tableau, it is a DAG rather than a tree). Secondly, results in those papers mainly concentrated on navigational features and much less on the data that documents carry. For instance, containment of queries with data values remained practically unexplored (as these papers concentrated on satisfiability).

And yet many applications demand proper XML conjunctive queries which are tree-based and can return data. Such queries are naturally induced by XML patterns which appear in multiple applications including XML data exchange, data integration, and query optimization [START_REF] Amano | XML schema mappings[END_REF][START_REF] Amer-Yahia | Tree pattern query minimization[END_REF][START_REF] Arenas | Relational and XML Data Exchange[END_REF][START_REF] Arenas | XML data exchange: consistency and query answering[END_REF][START_REF] Barceló | XML with incomplete information[END_REF][START_REF] Kimelfeld | Revisiting redundancy and minimization in an XPath fragment[END_REF]. Such patterns are given by grammars or formation rules that naturally induce a tree structure. As a simple example, we can say that a label a is a pattern, and if π 1 , . . . , π n are patterns, then a[π 1 , . . . , π n ] is a pattern. It will be matched by an a-labeled node that has n (not necessarily distinct) children matching π 1 , . . . , π n . Such patterns (and more complex ones including other axes) form the basis for describing XML schema mappings and incompleteness in XML documents. And yet they cannot generate the DAG-like "confluence" behavior explained earlier; because for any two nodes appearing on a descendant path, it is always specified which one appears first. But it is precisely this behavior that is behind many of the complexity results applied to graph-based pattern queries in XML.

So our question is: what are the costs of static analysis problems for proper tree-based pattern queries?

A key feature of the main applications of such patterns is that they are not purely about the structure of documents, but they also collect data. For instance, a pattern a(x)[b(x), c(y)] collects values x and y of data so that a document has an a-node with value x, that in turn has a b-child with the same value x and a c-child with value y. Thus, queries return sets of tuples, rather just a yes/no answer for the existence of a purely structural match. Furthermore, we do not look solely at analogs of conjunctive queries. In the relational case, it is well known that containment of both conjunctive queries and their unions has the same complexity, namely NP-complete [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF][START_REF] Sagiv | Equivalences among relational expressions with the union and difference operators[END_REF], and the complexity of containment of arbitrary Boolean combinations of conjunctive queries moves one level up in the polynomial hierarchy to Π p 2 -complete. So we deal with analogs of such queries too, built from tree-based patterns. Thus, our revised goal is to investigate the containment problems for analogs of conjunctive queries and relatives (unions, Boolean combinations) based on tree-based XML patterns over both structural information and data that XML documents carry.

Overview of the results. As an abstraction of XML documents with data values we use, as is common, data trees. In those trees, each node carries both a label and a data value. This is also sufficient to model XML documents whose nodes may have multiple attributes, simply by creating an extra child of a node for each attribute name.

We start by defining tree patterns upon which our queries are based. The simplest are patterns based on child navigation. An example is the pattern a(x)[b(x), c(y)] that we explained before. Note that variables corresponding to data values are free: we view this pattern as π(x, y), returning all pairs (x, y) such that a match occurs with x and y being the data values witnessing it. We can add horizontal navigation too, for instance we can have a pattern a(x)[b(x) → c(y)], stating that the c-witness is the sibling that follows the bwitness. More generally, we can have transitive closure axes too: for instance a(x)[c(x)]//[b(x) → * c(y)] says that the a-node has a c-child with the same data value and two descendants, with labels b and c and data values x and y, so that they are siblings and the b-node occurs earlier in the sibling order. These types of patterns occur, for instance, in integration and exchange tasks for defining XML schema mappings [START_REF] Amano | XML schema mappings[END_REF][START_REF] Arenas | Relational and XML Data Exchange[END_REF][START_REF] Arenas | XML data exchange: consistency and query answering[END_REF] or in descriptions of XML with incompleteness features [START_REF] Abiteboul | Representing and querying XML with incomplete information[END_REF][START_REF] Barceló | XML with incomplete information[END_REF].

Based on such patterns, we define conjunctive queries (CQs) by closing them under conjunction and existential quantification, i.e., as queries q(x) = ∃ȳ i π i (x, ȳ). We look at unions of conjunctive queries, or UCQs, which are of the form i q i (x), where each q i (x) is a CQ, and their Boolean combinations, or BCCQs, obtained by applying operations q ∩ q ′ , q ∪ q ′ , and qq ′ to CQs.

We present a general upper bound showing that containment of BCCQs that use all the axes is in Π p 2 . We show two matching lower bounds: either for BCCQs with the simplest navigation (only child relation), or CQs with all the axes.

In the relational case, CQ containment is tested by tableaux homomorphisms. The Π p 2 -hardness for general CQs precludes the possibility of such a test in general, but we show that with restricted sets of axes it is still possible (in fact we just have to exclude the horizontal → * relation).

We then look at adding features to patterns and queries. First, we add wildcard and show that the Π p 2 -upper bound continues to hold. We also show that, for some classes of queries, the complexity of containment can jump from NPcomplete to Π p 2 -complete if wildcard is added to patterns. Furthermore, we identify a 'safe' case of using wildcard, namely everywhere except at roots of patterns, that preserves homomorphism characterizations of containment.

The next addition we consider is containment under schema information (abstracted as a tree automaton, which capture many schema formalisms for XML). Here we show that the upper bound increases to double-exponential, and a matching lower bound can be shown for CQs with all axes. Finally, we look at adding data-value comparisons to queries, in particular the disequality ( =) comparisons. This addition has a much more dramatic effect on the complexity of containment: it becomes undecidable for BCCQs, and for CQs when both comparisons and schemas are present (even with severe restrictions on available navigation).

Comparison with non-tree pattern queries. As we already mentioned, a number of results exist on CQs based on graphshaped, rather than tree-shaped patterns [START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF][START_REF] Björklund | Conjunctive query containment over trees[END_REF][START_REF] Gottlob | Conjunctive queries over trees[END_REF]. None of those results extend to handle unions and differences of queries (i.e., UCQs and BCCQs) and they handle data values in a very limited way. Below we contrast them with our results.

For CQs that may contain arbitrary graph patterns, the Π p 2 upper bound continues to hold, but hardness requires less: for instance, purely navigational queries with non-tree patterns are already Π p 2 -complete for vertical navigation [START_REF] Björklund | Conjunctive query containment over trees[END_REF] (for tree patterns they stay in NP, as we show). Under schema, containment of CQs jumps to doubly-exponential too [START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF]. With = comparisons, even CQ containment becomes undecidable [START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF].

Those results cover only a part of the landscape that we study here (i.e., CQs, concentrating mainly on pure navigation), and, crucially, under different assumptions on the shape of queries. Such assumptions make most existing proofs inapplicable for us (as they often rely heavily on nontree features, such as the confluence, explained earlier, and the bidirectionality of axes).

Organization. We give key definitions in Section 2. The Π p 2 upper bound for BCCQs is shown in Section 3. In Section 4 we prove two matching lower bounds. In Section 5 we investigate cases when containment can be witnessed by the homomorphism of tableaux. Section 6 studies the effect of adding wildcard to queries. In Section 7 we investigate static analysis under schema constraints. Adding data-value comparison is studied in Section 8. Concluding remarks are given in Section 9. Due to space limitations, proofs are only sketched.

TREES, PATTERNS, AND QUERIES

Unranked trees and data trees. We start with the standard definitions of unranked finite trees which serve as an abstraction of XML documents when one deals with their structural properties. A finite unranked tree domain is a non-empty, prefix-closed finite subset D of N * (words over N) such that s • i ∈ D implies s • j ∈ D for all j < i and s ∈ N * . We refer to elements of finite unranked tree domains as nodes. We assume a countably infinite set L of possible labels that can be used to label tree nodes. An unranked tree is a structure D, ↓, →, λ , where

• D is a finite unranked tree domain, • ↓ is the child relation: s ↓ s • i for s • i ∈ D, • → is the next-sibling relation: s • i → s • (i + 1) for s • (i + 1)
∈ D, and • λ : D → L is the labeling function assigning a label to each node.

We denote the reflexive-transitive closure of ↓ by ↓ * (descendant-or-self), and the reflexive-transitive closure of → by → * (following-sibling-or-self).

Data trees are a standard abstraction of XML documents when one deals with both structural properties and data. Suppose we have a domain D of data values, such as strings, numbers, etc. A data tree is a structure t = D, ↓, →, λ, ρ , where D, ↓, →, λ is an unranked tree, and ρ : D → D assigns each node a data value. In XML documents, nodes may have multiple attributes, but this is easily modeled with data trees. For instance, to model a node with attributes a 1 , . . . , a n having values v 1 , . . . , v n , we pick special labels ℓ 1 , . . . , ℓ n , and create n extra children labeled ℓ 1 , . . . , ℓ n carrying values v 1 , . . . , v n .

Patterns. As already explained, the patterns that we use are naturally tree-shaped. To explain how they are introduced, let us consider the reducts of data trees to the child relation, i.e., structures D, ↓, λ, ρ . Trees of this form can be defined by recursion. That is, a node labeled with a ∈ L and carrying a data value v ∈ D is a data tree, and if t 1 , . . . , t n are trees, we can form a new tree by making them children of a node with label a and data value v.

In patterns we use also variables; the intention for them is to match data values in data trees. Thus, they are essentially partial tree descriptions with variables appearing in place of some data values. We assume a countable infinite set V of variables, disjoint from the domain of values D. So the previous inductive definition gives rise to the definition of the simplest patterns we consider here:

π := a(x)[π, . . . , π] (1)
with a ∈ L and x ∈ V ∪ D. Here the sequence in [. . .] could be empty. In other words, if π 1 , . . . , π n is a sequence of patterns (perhaps empty), a ∈ L and x ∈ V ∪ D, then a(x)[π 1 , . . . , π n ] is a pattern. If x is the list of all the variables used in a pattern π, we write π(x).

We denote patterns from this class by Π(↓). The semantics of π(x) is defined with respect to a data tree t = D, ↓, →, λ, ρ , a node s ∈ D, and a valuation ν : x → D as follows:

(t, s, ν) |= a(x)[π 1 (x 1 ), . . . , π n (x n )] iff • λ(s) = a (the label of s is a); • ρ(s) = ν(x) if x is a variable x if
x is a data value;

• there exist not necessarily distinct children s • i 1 , . . . , s • i n of s so that (t, s • i j , ν) |= π j (x j ) for each j ≤ n (recall that n could be 0, in which case this last item is not needed).

We write (t, ν) |= π(x) if there is a node s so that (t, s, ν) |= π(x) (i.e., a pattern is matched somewhere in the tree). Also if v = ν(x), we write t |= π(v) instead of (t, ν) |= π(x).

A natural extension for these simple patterns is to include both vertical and horizontal navigation. Again the intuition comes from defining data trees as follows: a node labeled with a ∈ L and carrying a data value v ∈ D is a data tree, and if t 1 , . . . , t n are trees, we can form a new tree by making them children of a node with label a and data value v, so that their roots are connected in the order t 1 → t 2 → . . . → t n . This leads to the definition of patterns in the class Π(↓, →):

π := a(x)[π → . . . → π] (2)
with a ∈ L and x ∈ V ∪ D. Again the sequence in [. . .] could be empty. In other words, if π 1 , . . . , π n is a sequence of patterns (perhaps empty), a ∈ L and x ∈ V ∪ D, then a(x)[π 1 → π 2 → . . . → π n ] is a pattern. The last clause in the definition of the semantics of Π(↓) is modified as follows:

• there exists a child s•i of s so that (t, s•i, ν) |= π 1 (x j ), (t, s

• (i + 1), ν) |= π 2 (x 2 ), . . ., (t, s • (i + n -1), ν) |= π n (x n ).
In other words, it is consecutive children that witness the satisfaction of subpatterns.

Patterns in Π(↓) and Π(↓, →) completely specify the structure of a tree (depending on the available axes) and, in particular, only express local properties of trees. We therefore also consider their more expressive versions with transitive closure axes ↓ * (descendant) and → * (following sibling). More precisely, following [START_REF] Amano | XML schema mappings[END_REF][START_REF] Gheerbrant | On the complexity of query answering over incomplete XML documents[END_REF], we define general patterns by the rules:

π := a(x)[µ, . . . , µ]//[µ, . . . , µ] µ := π ; . . . ; π (3)
Here a, x and π are as before, and µ stands for a sequence, i.e., a forest such that the roots of its trees are sequential siblings in a tree, and each ; is either → or → * .

The class of such patterns is denoted by Π(⇓, ⇒), with ⇓ we use both types of downward navigation (↓ and ↓ * ) and ⇒ meaning that we use both types of horizontal navigation (→ and → * ). The semantics is extended as follows.

• (t, s, ν) |= π 1 ; . . . ; π m if there is a sequence s = s 1 , . . . , s m of nodes so that (t, s i , ν) |= π i for each i ≤ m and s i → s i+1 whenever the ith ; is →, and

s i → * s i+1 whenever the ith ; is → * . • (t, s, ν) |= a(x)[µ 1 , . . . , µ n ]//[µ ′ 1 , . . . , µ ′ k ]
if the satisfaction of a(x) in node s is as before, and there exist n not necessarily distinct children s 1 , . . . , s n of s such that (t, s i , ν) |= µ i for each i ≤ n, and there exist

k not necessarily distinct descendants s ′ 1 , . . . , s ′ k of s such that (t, s ′ i , ν) |= µ ′ i for each i ≤ k.
Notice that the semantics of patterns allows different µ i to be mapped into the same nodes in a tree.

Finally, we consider a class Π(⇓) of patterns which is a restriction of the most general patterns to downward navigation only. These are defined by the grammar

π := a(x)[π, . . . , π]//[π, . . . , π] (4)
where each of the sequences of patterns can be empty. That is, a pattern a(x

)[π 1 , . . . , π n ]//[π ′ 1 , . . . , π ′ k ]
is witnessed in an a-labeled node assigning its data value to x if it has n children (not necessarily distinct) witnessing π 1 , . . . , π n and k descendants (again not necessarily distinct) witnessing π ′ 1 , . . . , π ′ k .

Shorthands. We shall be using standard shorthand notations: a(x)/π stands for a(x)[π], while a(x)//π denotes a(x)//[π], and a(x)/π//π ′ stands for a(x

)[π]//[π ′ ].
Conjunctive queries, their unions, and Boolean combinations. Pattern-based conjunctive XML queries are obtained by closing patterns by conjunction and existential quantification. Since we have different classes of patterns Π(σ), for σ being ↓, or ↓, →, or ⇓, or ⇓, ⇒, we have different classes of conjunctive queries denoted by CQ(σ). More precisely, CQ(σ) queries are of the form:

q(x) = ∃ȳ n i=1 π i (z i ) (5)
where each π i is a Π(σ) pattern, and each zi is contained in x, ȳ. The semantics is standard:

(t, ν) |= q(x) if there is an extension ν ′ of valuation ν to variables ȳ such that (t, ν ′ ) |= π i (z i ) for every i ≤ n.
As is standard, we also write

t |= q(v) if (t, ν) |= q(x) with ν(x) = v.
Of course conjunctive queries are closed under conjunction. Standard ways of enriching their power include considering unions of conjunctive queries (or UCQs, which, in the relational case, capture the positive fragment of relational algebra) and more generally, Boolean combinations of conjunctive queries (or BCCQs, which, while possessing some form of negation, still retain many nice properties that relational algebra as a whole loses).

Formally, a query from UCQ(σ) is of the form q(x) = q 1 (x) ∪ . . . ∪ q m (x), where each q i (x) is a CQ(σ) query. It returns the union of answers to the q i 's, i.e., (t, ν) |= q(x) iff (t, ν) |= q i (x) for some i ≤ m.

Queries in the class BCCQ are obtained as follows: take some queries q 1 (x), . . . , q m (x) from CQ(σ) and consider a Boolean combination of them, i.e., close them under operations q ∩ q ′ , q ∪ q ′ , and qq ′ . The semantics is extended naturally, with those interpreted as intersection, union, and set difference, respectively.

The answer to a query q(x), from any of the above classes, on a data tree t is defined as q(t) = {ν(x) | (t, ν) |= q(x)}. Note that our definitions of query classes ensure that q(t) is always finite.

Containment.

The main problem we study here is the containment problem. Given two queries q(x), q ′ (x ′ ) with tuples of free variables of the same length, we write q ⊆ q ′ iff q(t) ⊆ q ′ (t) for every data tree t. So the problem we look at is the following.

PROBLEM: CQ

⊆ (σ) INPUT: queries q(x), q ′ (x ′ ) in CQ(σ); QUESTION: is q ⊆ q ′ ?
If instead of queries in CQ(σ) we use queries in UCQ(σ), we refer to the problem UCQ ⊆ (σ) and, if we use queries from BCCQ(σ), we refer to the problem BCCQ ⊆ (σ).

In the relational case, these problems are among the basic problems of database theory. The complexity of CQ ⊆ and UCQ ⊆ over relational databases is NP-complete [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF][START_REF] Sagiv | Equivalences among relational expressions with the union and difference operators[END_REF] (under the representation of UCQs that we use here), and the complexity of BCCQ ⊆ is Π p 2 -complete [START_REF] Sagiv | Equivalences among relational expressions with the union and difference operators[END_REF].

AN UPPER BOUND

A priori, there is no upper bound that is immediate for the containment problem. In fact, in the presence of negation (even a limited form of it) combined with XML hierarchical structure, some reasoning problems can become undecidable (see, e.g., [START_REF] Fan | On XML integrity constraints in the presence of DTDs[END_REF][START_REF] Amano | XML schema mappings[END_REF]). In the relational case, we know that containment for BCCQs is Π p 2 -complete, but this does not imply the same bounds for XML pattern-based queries, especially those that might use transitive closure axes → * and ↓ * . Nevertheless, we can show that for all such queries, the containment problem remains not only decidable, but the upper bound on its complexity continues to match that for the simplest relational queries. In fact we show the following.

THEOREM 3.1. The problem BCCQ ⊆ (⇓, ⇒) is decid- able in Π p 2 .
In other words, for each of the classes of queries -CQ, UCQ, BCCQ-and for each of the classes of patterns seen so far, the containment problem is in Π p 2 , as all of these problems are subsumed by the containment problem of BCCQs with Π(⇓, ⇒)-patterns.

Proof sketch. Checking whether q 1 ⊆ q 2 is the same as checking q 1 -q 2 = ∅, so it will suffice to give a Σ p 2 algorithm for checking if a BCCQ q returns a nonempty result on some data tree. We assume that q is a Boolean combination of CQs q 1 , . . . , q m . For the sketch we assume they are Boolean (free variables do not change anything). To check satisfiability it suffices to guess an assignment χ : {1, . . . , m} → {0, 1} so that for

q ′ = {q i | χ(i) = 1} and q ′′ = {q j | χ(j) = 0}
we have a tree t such that q ′ (t) is true and q ′′ (t) is false. Note that q ′ is a CQ, and q ′′ is a UCQ. The idea of the proof is to turn this into a certain answer problem in XML data exchange [START_REF] Arenas | XML data exchange: consistency and query answering[END_REF]. We let schemas of XML documents be arbitrary and the mapping consist of a single rule _ → q ′ , forcing the patterns of q ′ in every target tree. Then we check whether the certain answer to q ′′ is false: this happens iff there is a tree satisfying q ′ and the negation of q ′′ . The latter requires two steps in the proof. One is a modification of the proof of the CONP data complexity of certain answers in [START_REF] Arenas | XML data exchange: consistency and query answering[END_REF]. The problem is that the latter proof produces a witnessing tree whose size is exponential in q ′′ , which is too large for our purposes. So we show how to encode the exponential witness by a data structure whose size is polynomial in q ′ , q ′′ and which allows checking for satisfiability of UCQs. The second step is making sure that all the guesses are combined in the right order to yield a Σ p 2 algorithm. 2

LOWER BOUNDS FOR CONTAIN-MENT

Now that we know that all the containment problems are in Π p 2 , it is natural to ask when we have matching lower bounds. Note that in all the variations of containment problems, we have two parameters: the class of queries (going from the simplest, CQs, to UCQs, and to BCCQs), and the set of axes (again, starting with the simplest, just ↓, and then going to more complex ↓, →, as well as ⇓ and ⇓, ⇒).

What we show in this section is that each of the combination simplest/hardest leads to Π p 2 -hardness. That is, the containment problem with the simplest of axes, just ↓, is Π p 2 -complete if we allow Boolean combinations of queries. If we have just CQs, the containment becomes Π p 2 -complete when we have all the axes, i.e. ↓, ↓ * , →, and → * .

Note that the first result on the surface is rather similar to Π p 2 -completeness of containment of relational BCCQs [START_REF] Sagiv | Equivalences among relational expressions with the union and difference operators[END_REF]. Indeed, the standard representation of relations in XML only needs the ↓ axis, and shallow documents. However, the result does not follow from the results in [START_REF] Sagiv | Equivalences among relational expressions with the union and difference operators[END_REF], as we demand containment over all XML documents, not only those that properly represent relational databases of a given schema. In particular, if we have two relational BCCQs q and q ′ , and their natural XML codings as BCCQ(↓) queries q XML and q ′ XML , then q XML ⊆ q ′ XML implies q ⊆ q ′ (as each relational database can be coded as an XML tree), but under the same coding q ⊆ q ′ need not imply q XML ⊆ q ′ XML . Even though we cannot use results on [START_REF] Sagiv | Equivalences among relational expressions with the union and difference operators[END_REF], we can modify reductions to apply to all XML documents and obtain the following.

THEOREM 4.1. The problem BCCQ ⊆ (↓) is Π p 2 - complete.
Next, we move to the other extreme case: CQs with all the axes. Of course relational containment of CQs is NPcomplete, so to get hardness for a larger class, one has to use, in an essential way, the hierarchical structure of XML. In fact we provide a rather elaborate reduction showing that the navigational abilities of all the axes are sufficient to increase the complexity even of conjunctive query containment.

THEOREM 4.2. The problem CQ

⊆ (⇓, ⇒) is Π p 2 - complete.
Proof sketch. The upper bound was shown in the previous section. To show hardness, we proceed by reduction from ∀∃3CNF. Given such a formula ϕ := ∀p 1 . . . ∀p l ∃r 1 . . . ∃r m i (ℓ i1 ∨ ℓ i2 ∨ ℓ i3 ), where the ℓ ij s could be positive or negative literals, we associate with it two Boolean queries q, q ′ ∈ CQ(⇓, ⇒) such that ϕ is true if and only if q ⊆ q ′ . We construct q and q ′ so that for every possible valuation v of the p i s, two conditions hold. First, there exists a tree t v satisfying q which encodes v. Second, such a tree t v satisfies q ′ iff there is a valuation v + extending v to the r i s and for which ϕ evaluates to true. The key idea behind the construction is encoding possible valuations for quantified variables, and we explain it now. The encoding of the CNF formula itself is standard.

In order to encode every possible valuation of the p i s using one single query q, we associate a variable x i to each p i and then take full advantage of navigational features to model assignments. Specifically, we use a tree pattern V (2)/[Val(0) → Val(1), Val(x 1 ), . . . , Val(x l )]. Its root has l + 2 children, among which the ordering is specified for two (Val(0) → Val( 1)). The remaining l children carry the x i s, but note that their exact positions as children of the V (2) node are not specified. This is illustrated below:

V (2) Val(0) -→ Val(1) Val(x 1 ) . . . Val(x l )
Now on every complete tree t witnessing this pattern via some homomorphism h, the image of every x i will either be on the left, or on the right of 0, i.e., either

t |= V (2)[Val(h(x i )) → * Val(0)], or t |= V (2)[Val(0) → * Val(h(x i ))].
This allows us to associate a valuation v of the p i s to any tree satisfying this pattern by letting v(p i ) be false if the image of x i occurs on the left of Val(0), and by letting v(p i ) be true otherwise. The rest of the encoding consists of the standard encoding of a CNF formula, and ensuring, for q ′ , that the extended valuation makes that formula true.

2

Remark Note that letting one omit a complete specification of the sibling ordering has the effect of encoding 2 n possible valuations with n different nodes. This is similar to the effect of using "confluence" features in [START_REF] Björklund | Conjunctive query containment over trees[END_REF]. In both cases, such a concise encoding of exponentially many valuations led to Π p 2 lower bounds.

CONTAINMENT VIA HOMOMOR-PHISMS

A classical result of relational database theory says that containment of relational CQs is NP-complete and containment is witnessed by the existence of a homomorphism of tableaux: if T i is the tableau of a query q i , for i = 1, 2, then q 1 ⊆ q 2 iff there is a homomorphism from T 2 to T 1 [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]. However, the results of the previous section indicate that such a characterization of containment via homomorphisms cannot be extended to all classes of CQs we consider here. Indeed, testing for the existence of a homomorphism is a classical NP-complete problem and we saw in Theorem 4.2 that containment of CQ(⇓, ⇒) queries is Π p 2 -complete. So the question is: for what types of queries, if any, can we characterize containments via homomorphisms of their tableaux? And even before answering this question, we need to ask: what are the tableaux of XML-based CQs? Since tableaux for relational queries are essentially incomplete databases (more precisely, naïve tables with a distinguished row of variables), it is natural to define tableaux of XML CQs as incomplete XML trees. Indeed, patterns forming a query are essentially incompletely specified trees, so we can view each query as an incomplete tree (more precisely, a forest). The theory of incompleteness of XML has been developed [START_REF] Abiteboul | Representing and querying XML with incomplete information[END_REF][START_REF] Barceló | XML with incomplete information[END_REF] and thus we can borrow a notion of an incomplete tree.

Incomplete trees and homomorphism. An incomplete tree is defined as a structure t = (N, V, ↓, ↓ * , →, → * , λ, ρ), where

• N and V are disjoint finite sets of the nodes of t and its data values, respectively; we assume that V ⊂ D ∪ V, i.e., values could be either data values or variables; • all of ↓, ↓ * , →, → * are binary relations on N ; • λ is a partial function from N to L; and • ρ is a function from N to V .

Note that in an incomplete tree, the relations ↓, ↓ * , →, → * may be interpreted arbitrarily. In particular, some incomplete trees cannot be extended to a complete tree. The issue is discussed in details in [START_REF] Barceló | XML with incomplete information[END_REF]. The labeling function is partial, reflecting the fact that labels of some nodes may not be known. The data assigning function ρ is not partial since some data values could be variables, just like in patterns.

Given two incomplete trees

t = N, V, ↓, ↓ * , →, → * , λ, ρ and t ′ = N ′ , V ′ , ↓, ↓ * , →, → * , λ ′ , ρ ′ , a homomorphism from t to t ′ is a map h : N ∪ V → N ′ ∪ V ′ such that: • h(N ) ⊆ N ′ and h(V ) ⊆ V ′ ; • if wRw ′ in t, with w, w ′ ∈ N and R one of the rela- tions ↓, ↓ * , →, → * , then h(w)Rh(w ′ ) in t ′ ; • if λ(w) is defined in t, then λ ′ (h(w)) = λ(w);
• h is the identity on elements of D; and • h(ρ(w)) = ρ ′ (h(w)) for all w ∈ N .

Note that each tree can be viewed as an incomplete tree (with the natural interpretations of the binary relations) and thus it makes sense to speak of a homomorphism from an incomplete tree to a complete tree.

Our plan is now as follows. We show how to associate, to a CQ q, an incomplete tree t q . If q is a Boolean query, then t |= q iff there is a homomorphism from t q into t. If q has free variables x, then t |= q(v) iff there is a homomorphism from t q(x) to t that sends x to v.

We then show that, for some classes σ of axes and queries q, q ′ ∈ CQ(σ), we have q ⊆ q ′ iff there is a homomorphism from the σ-restriction of t q ′ to the σ-restriction of t q .

Incomplete trees of CQs. We now define analogs of tableaux of relational CQs; these will be incomplete trees.

We first define an incomplete tree t π for each pattern π. To carry the inductive construction, we shall need to define both trees t π and t µ for sequences µ. Note that even though we use the name 'incomplete tree', such a structure need not be a tree (due to incompleteness); in fact t µ s will be forest-like. Each incomplete tree t of the form t π or t µ will have a set RT(t) of roots associated with it in such a way that RT(t π ) is always a singleton. The inductive construction is as follows.

• If π = a(x), then t π = {s}, {x}, ↓, ↓ * , →, → * , λ, ρ , where s is a single node, all the binary relations are empty, λ(s) = a and ρ(s

) = x. Furthermore, RT(t π ) = {s}. • Let π = a(x)[µ 1 , . . . , µ n ]//[µ ′ 1 , . . . , µ ′ k ]
. Suppose we already have t µi s and t µ ′ j s defined. Let N i and V i be the sets of nodes and values in t µi s and N ′ j and V ′ j be the sets of nodes and values in t µ ′ j s. By renaming nodes in those incomplete trees, we may assume that all the sets N i s and N ′ j s are disjoint. Then

t π = (N, V, ↓, ↓ * , →, → * , λ, ρ)
where N = {s} ∪ i N i ∪ j N ′ j , with s being a new node, and

V = i V i ∪ j V ′ j .
The binary relations are the unions of those relations in the t µi s and t µ ′ j s. In addition, we put:

-s ↓ s ′ for each s ′ ∈ RT(µ i ), for i ≤ n; and -s ↓ * s ′ for each s ′ ∈ RT(µ ′ j ), for j ≤ k.
The functions λ and ρ are the same as in the t µi s and t µ ′ j s; in addition λ(s) = a and ρ(s) = x. Furthermore, RT(t π ) = {s}.

• Let µ = π 1 ; . . . ; π n . Let t πi be an incomplete tree N i , V i , ↓, ↓ * , →, → * , λ i , ρ i . As before, assume that by renaming nodes, all the N i s are disjoint. Let RT(t πi ) = {s i }.

Then t µ = N, V, ↓, ↓ * , →, → * , λ, ρ , where N = i N i and V = i V i ; the binary relations are unions of those in the t πi s, and in addition we put:

-s i → s i+1 if µ contains π i → π i+1 ; and -s i → * s i+1 if µ contains π i → * π i+1 .
The functions λ and ρ coincide with λ i and ρ i on N i . Moreover, RT(µ) = {s 1 , . . . , s n }.

With a query

q(x) = ∃ ȳ1 . . . ∃ ȳn π 1 (x, ȳ1 ) ∧ . . . ∧ π n (x, ȳn )
we associate an incomplete data tree

t q = (N, V, ↓, ↓ * , →, → * , λ, ρ)
which is the node-disjoint union of all the t πi s; that is, we rename nodes so that their sets are disjoint (but not the values), and take the union of structures t π1 , . . . , t πn .

The incomplete trees t q indeed play the role of tableaux of CQs. Recall that in the relational case, we have D |= q(v) iff there is a homomorphism from the tableau of q(x) to D that sends x to v. The same is true here. The result is very similar to one in [START_REF] Barceló | XML with incomplete information[END_REF], adapted to the definitions given here. PROPOSITION 5.1. Let t be a data tree, and q(x) a query from CQ(⇓, ⇒). Then t |= q(v) iff there is a homomorphism h : t q → t so that h(x) = v.

Containment and homomorphisms.

We already mentioned that a classical result of relational database theory states that relational CQ containment q ⊆ q ′ holds iff the tableau of q ′ can be homomorphically mapped into the tableau of q. Furthermore, an analog of this cannot possibly hold for queries in CQ(⇓, ⇒) unless some complexity classes collapse. Nonetheless, it will work for queries that do not use all the axes. Suppose we have a query q from CQ(↓). Then its incomplete tree t q records no information about ↓ * , →, and → * . So for two such queries q and q ′ , a homomorphism of the ↓reducts of t q and t q ′ (that only keep information about ↓, λ, and ρ) is the same as a homomorphism t q and t q ′ . Hence, even for queries that use reduced sets of axes, e.g., CQ(↓) or CQ(↓, →), we can still meaningfully talk about homomorphisms of their incomplete trees, in place of homomorphisms of reducts of incomplete trees.

We next show that without transitive closure axes, we have an analog of relational containment. THEOREM 5.2. Let q(x) and q ′ (x ′ ) be two queries from either CQ(↓), or CQ(↓, →). Then q ⊆ q ′ iff there is a homomorphism h : t q ′ → t q so that h(x ′ ) = x.

Since testing homomorphism existence is done in NP, and NP-hardness bound for relational CQs trivially applies to CQ(↓) queries, we obtain the following. COROLLARY 5.3. The containment problems for CQ(↓) and CQ(↓, →), i.e., CQ ⊆ (↓) and CQ ⊆ (↓, →), are NPcomplete.

In fact, we prove an even more general result, that shows the applicability of the homomorphism technique to queries in CQ(⇓, →), i.e., queries using all forms of vertical navigation, but only the next-sibling form of horizontal navigation. Formally, they are CQs based on patterns from Π(⇓, →) defined as

π := a(x)[µ, . . . , µ]//[µ, . . . , µ] µ := π → . . . → π (6)
That is, they extend Π(↓, →) patterns by allowing descendants, and prohibiting only → * .

Given a query q ∈ CQ(⇓, →), we define an incomplete tree (t q ) * by replacing the interpretation of ↓ * in t q by the reflexive-transitive closure of the union of ↓ and ↓ * in t q . Then containment can be tested by the existence of homomorphisms between such extended tableaux. As an example, consider queries q ⊆ q ′ , where q = ∃x a(x)//b(x)[c(x)] and q ′ = ∃x a(x)//c(x). While there is no homomorphism from t q ′ to t q , there is one from (t q ′ ) * to (t q ) * . Indeed, in both structures there is a descendant axis going from the a-labeled node to the c-labeled node. THEOREM 5.4. Let q(x) and q ′ (x ′ ) be two queries from CQ(⇓, →). Then q ⊆ q ′ iff there is a homomorphism h : (t q ′ ) * → (t q ) * so that h(x ′ ) = x.

Proof sketch. The right to left direction of the equivalence is immediate. To show the other direction, we assume q ⊆ q ′ and we turn the forest t q into some "canonical" complete tree T such that there is a natural one to one homomorphism h 1 : (t q ) * → T and such that for all w, w ′ ∈ (t q ) * , for all R ∈ {→, ↓, ↓ * }, we have wRw ′ iff h 1 (w)Rh 1 (w ′ ). To this end, we create new nodes labeled with a fresh label ♥ and a fresh data value ♯. One of these nodes becomes the common parent of each of the roots of the tree patterns in t q and thus becomes the root of T . We also define a recursive procedure replacing descendant axis w 1 ↓ * w 2 occurring in t q by child paths w 1 ↓ w 3 ↓ w 2 , where w 3 is one of the new nodes labeled ♥(♯). We proceed in a similar way with sequences of siblings which are given as mere unions. We order them arbitrarily using the next-sibling relation, but we always take care of inserting one of the new ♥(♯)-labeled nodes in between two siblings which were not previously related by a →-arrow. We finally substitute fresh distinct constants for every distinct variable, thus obtaining a complete tree. From q ⊆ q ′ , we then infer that there exists another homomorphism h 2 : t q ′ → T . Relying on the special properties of h 1 , we finally construct the homomorphism h : (t q ′ ) * → (t q ) * from h 1 and h 2 by letting h

(x) = h -1 1 (h 2 (x)). 2
As before, we immediately obtain the following.

COROLLARY 5.5. The problem CQ ⊆ (⇓, →) is NPcomplete.

As mentioned earlier, replacing → by ⇒ and obtaining an analog of Theorem 5.4 is impossible without an unlikely collapse of complexity classes. COROLLARY 5.6. Assume that there is a polynomialtime algorithm that associates with each query q ∈ CQ(⇓, ⇒) an incomplete tree t(q) so that q ⊆ q ′ iff there is a homomorphism t(q ′ ) → t(q). Then NP =CONP. Indeed, since containment of CQ(⇓, ⇒) is Π p 2 -hard and testing homomorphism existence is NP-complete, the existence of such a containment test would imply Π p 2 ⊆ NP from which NP =CONP follows easily.

Polynomial-time cases. Our characterization of containment via homomorphisms immediately shows how to obtain polynomial-time cases of containment. Indeed, since containment is now reduced to the existence of homomorphisms, it is effectively cast as a constraint satisfaction (or conjunctive query evaluation) problem. Thus, we can use multiple known results classifying tractable cases of those and apply them to structures representing incomplete data trees. As all of these are quite routine, we leave the complete treatment to the full version (due to space limitations here), and now give just a couple of examples. One is the containment q ⊆ q ′ for any of the classes CQ(↓), CQ(↓, →), and CQ(⇓, →) if the query q ′ is fixed. The other is containment for the classes CQ(↓) and CQ(↓, →) when q ′ mentions each variable at most once (since in this case containment can be reduced to the combined complexity of evaluating conjunctive queries of fixed treewidth). More results will be provided in the full version.

Extension to unions of CQs.

A classical result in relational theory says that for unions of relational conjunctive queries, q = q 1 ∪ . . . ∪ q m and q ′ = q ′ 1 ∪ . . . ∪ q ′ k , we have q ⊆ q ′ iff for every i ≤ m, there exists j ≤ k so that q i ⊆ q ′ j [START_REF] Sagiv | Equivalences among relational expressions with the union and difference operators[END_REF]. We call this the SY-criterion (for Sagiv/Yannakakis) for containment of UCQs. In particular, the SY-criterion implies that the complexity of containment of relational UCQs remains NP-complete (assuming, of course, that they are represented in the above way, as unions of CQs; for other syntactic representations, in which the union is not the outermost operation, the complexity is Π p 2 -complete [START_REF] Sagiv | Equivalences among relational expressions with the union and difference operators[END_REF]). Note that we have defined XML queries in UCQ(σ) to be syntactically of the form q 1 ∪ . . . ∪ q m , where each q i is a CQ(σ)-query. It turns out that for the classes which permit testing containment by means of homomorphisms between incomplete trees t q , a similar extension to unions continues to be true. PROPOSITION 5.7. Queries in UCQ(↓) and UCQ(↓, →) satisfy the SY-criterion for containment.

This immediately gives us the following. COROLLARY 5.8. The problems UCQ ⊆ (↓) and UCQ ⊆ (↓, →) are NP-complete. Indeed, for queries q = q 1 ∪ . . . ∪ q m and q ′ = q ′ 1 ∪ . . . ∪ q ′ k we simultaneously guess a map f : {1, . . . , m} → {1, . . . , k}, and m maps h i from t q ′ f (i) to t qi for each i ≤ m, and check, in polynomial time, if the h i s satisfy conditions of Theorem 5.2.

THE EFFECT OF WILDCARD

A standard feature of most XML formalisms is the use of wildcard, i.e., a special symbol in place of a label that matches every label in a tree. We normally use _ for wildcard. So patterns can be extended in the following way: instead of a pattern that starts with a(x), we can have a pattern that starts with _(x). It will be witnessed in a node s of a data tree t even if we drop the requirement that labels match. When we deal with classes of patterns Π(σ) extended with wildcard, we write Π(σ, _).

For instance, patterns in Π(↓, _) are given by

π := a(x)[π, . . . , π], a ∈ L ∪ {_}, x ∈ V ∪ D. (7)
The semantics is extended, compared to (1), as follows.

For a data tree t = D, ↓, →, λ, ρ , a node s ∈ D, and a valuation ν : x → D, we have

(t, s, ν) |= a(x)[π 1 (x 1 ), . . . , π n (x n )] iff • λ(s) = a if a ∈ L; • ρ(s) is ν(x) if
x is a variable, and x if x is a constant data value; • there exist not necessarily distinct children s • i 1 , . . . , s • i n of s so that (t, s • i j , ν) |= π j (x j ) for each j ≤ n.

Likewise we define all other classes of patterns extended with wildcard, e.g., Π(↓, →, _) and Π(⇓, ⇒, _), and classes of CQs, UCQs, and BCCQs based on them. For those queries we define the containment problem: for instance, BCCQ ⊆ (⇓, ⇒, _) is the problem of checking containment of BCCQs based on patterns from Π(⇓, ⇒, _).

The question is then whether the use of wildcard increases the cost of testing containment. The first instance of that question is whether we can preserve the Π p 2 upper bound for all containment cases. The answer to this is positive. In fact, our proof of Theorem 3.1 already shows how to handle wildcard.

PROPOSITION 6.1. The problem BCCQ ⊆ (⇓, ⇒, _) is in Π p 2 .
Hence, all other containment problems are in Π p 2 in the presence of wildcard.

What does change, however, is the lower bounds. Recall that we saw in Corollary 5.8 that UCQ ⊆ (↓, →) is in NP. The presence of wildcard makes the complexity jump: adding wildcards to Π(↓, →) patterns makes the complexity of containment of UCQs Π p 2 -hard, rather than being in NP. THEOREM 6.2. The problem

UCQ ⊆ (↓, →, _) is Π p 2 - complete.
Proof sketch. To show hardness, we adapt the lower bound proof of Theorem 4.2 by constructing queries q rigid , q ′ rigid instead of q, q ′ . Recall that the query q was encoding all the possible valuations of the p i s using a special pattern over Π(⇓, ⇒). Additionally we used another pattern in q to encode the clauses in ϕ. We did not describe this pattern in the sketch of Theorem 4.2, but it is enough for the current sketch to note that it can alternatively be represented as a Π(↓, →)-pattern π ϕ . We define q rigid by adding to π ϕ two new nodes as first and second child of its root. These new nodes are respectively labeled Val(0) and Val [START_REF] Abiteboul | Reasoning about XML update constraints[END_REF]. Let π 01 ϕ be the resulting pattern. For every 1 ≤ i ≤ l, we also create a single node pattern labeled Val(x i ) and we form q rigid by existentially quantifying the x i 's and taking the conjunction of these l + 1 patterns. Now we define q ′ rigid as a disjunction whose first member slightly adapts q ′ , while its second member π _ is the disjunction of all Π(↓, →) patterns extending π with one single node labeled with wildcard and with a fresh variable over data values. The key idea is now that if a complete tree t does not satisfy π _ but satisfies q rigid via some homomorphism h, then for every x i , either h(x i ) = 0, or h(x i ) = 1, i.e., t encodes one particular valuation of the p i s.

2

Since wildcard can lead to an increase in complexity of the containment problem, it is natural to ask then when we can match the previously established complexity results in the presence of wildcard. For Π(↓) and Π(↓, →) patterns the answer to this is surprisingly simple: we can allow wildcard everywhere except at the root of the pattern. Recall that in Section 5 we associated with each pattern π an incomplete tree t π with a unique root. The requirement is basically that the label of the root of t π is a ∈ L; other nodes of t π can be labeled either by a ∈ L or by _.

For instance, the following rules define such patterns based on child-only navigation:

π := a(x)[π ′ , . . . , π ′ ] a ∈ L π ′ := a(x)[π ′ , . . . , π ′ ] a ∈ L ∪ {_} (8)
That is, the π ′ s define patterns that can use wildcard, and π is the top-level pattern, whose root label comes from L.

When we have this restriction on patterns with wildcard, we write Π(σ, _¬r), where σ, as before, is a set of axes. Likewise we define classes of queries -e.g., CQ(↓, →, _¬r) -and containment problems -e.g., CQ ⊆ (↓, →, _¬r).

Obviously the addition of wildcard preserves lower bounds. We have already seen that containment of BCCQs with wildcard is in Π p 2 , and hence all three versions of BCCQ containment -BCCQ ⊆ (⇓, ⇒), BCCQ ⊆ (⇓, ⇒, _), and BCCQ ⊆ (⇓, ⇒, _¬r) -are Π p 2 -complete. Now we show that the NP bounds established via homomorphisms are also preserved when wildcard is used everywhere except the root. PROPOSITION 6.3. The problems CQ ⊆ (↓, _¬r) and CQ ⊆ (↓, →, _¬r) are NP-complete.

Proof sketch. We adapt the proof of the corresponding result in Section 5. We now turn t Q into a complete tree using a slightly different procedure. We just add to it one new root node labeled ♥(♯) and we decide arbitrarily on a sibling ordering when none is specified. We finally substitute fresh distinct constants for every distinct variable, thus obtaining a complete tree T . The remainder of the proof is almost as before. Whenever the next sibling relation is available, we only need to notice that the homomorphism h 2 : t Q ′ → T cannot map any node in t Q ′ to the root of T . As tree patterns are rooted, this entails that nothing can be said in t Q ′ about the relative sibling orderings of the preimages of the children of the root of T .

2

Note that such a procedure would not work when both unions of siblings and next sibling are allowed. For instance, let q = ∃x, y, z a(x)[a(y), b(z)] and q ′ = ∃x, y, z a(x)[_(y) → _(z)] with a = b. Obviously q ⊆ q ′ , as q forces the tree to have an a-labeled node with at least two children. On the other hand, it is easy to see that there is no homomorphism from t q ′ to t q .

Similarly, the method cannot be applied to queries in CQ(⇓, _¬r). Consider q = ∃x, y a(x)//b(y) and q ′ = ∃x, y, z a(x)/_(z)//b(y) ∧ ∃x, y, z a(x)//_(z)/b(y), with a = b. Again q ⊆ q ′ , as q forces the tree to have an a-labeled node which has at least one child and a b-labeled descendant which has a parent. But here again, it is obvious that there is no homomorphism from t q ′ to (t q ) * .

Observe finally that by allowing wildcard to appear everywhere in patterns we also lose the homomorphism criterion that let us establish the NP upper bound. For instance, let q = ∃x, y a(x) ∧ b(y) , with a = b, and let q ′ = ∃x, y (_(x)/_(y)). Since q forces each tree to have at least two nodes, we have the containment q ⊆ q ′ ; however there is no homomorphism from t q ′ to t q .

As the last result of this section, we show that combining unions of queries even with the restricted use of wildcard can increase the complexity of containment. PROPOSITION 6.4. Containment of UCQs that use downward navigation and wildcard except at the root, i.e., the problem UCQ ⊆ (⇓, _¬r), is Π p 2 -complete.

Proof sketch. We adapt the proof of Theorem 4.2 along the same lines as in the proof of Theorem 6.2. We define queries q ⇓ , q ′ ⇓ as follows. We keep all the ↓ paths patterns which were actually used in q to encode the clauses of ϕ, but we now encode the valuation of the p i 's using a pattern π 1 / . . . /π l where for each 1 ≤ i ≤ l, π i = Val(0)//Val(x i )//Val(1). We can now construct q ′ ⇓ almost as in the proof of Theorem 6.2, except that we replace π _ with a CQ ∃x 1 . . . ∃x 2l+1 Val(0)/_(x 1 )/ . . . /_(x 2l+1 ). 2

THE EFFECT OF SCHEMAS

So far we have not assumed any schema information, such as a DTD or a more general schema description, under which we perform static analysis of queries. However, such assumptions are fairly common, as many XML documents are required to satisfy schema descriptions. Schemas are very well known to affect static analysis of XML. In fact containment of queries can easily behave differently under schemas, even such simple ones as specifying the label of the root of a document. For instance, if q = ∃x, y a(x) ∧ b(y) and q ′ = ∃x, y c(x)/_(y) , then in general q ⊆ q ′ , but if we state that roots must be labeled c, then q ⊆ q ′ . In addition, the presence of schemas is known to affect the complexity of static reasoning tasks, generally by increasing it, sometimes even making it undecidable [START_REF] Arenas | On the complexity of verifying consistency of XML specifications[END_REF][START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF][START_REF] Fan | On XML integrity constraints in the presence of DTDs[END_REF][START_REF] Figueira | Satisfiability of downward XPath with data equality tests[END_REF][START_REF] Gottlob | Conjunctive queries over trees[END_REF][START_REF] Neven | On the complexity of XPath containment in the presence of disjunction, DTDs, and variables[END_REF][START_REF] Th | XPath query containment[END_REF]. The main observation of this section is that under schema information, we preserve decidability of query containment for those classes we have encountered so far, but at the cost of an exponential blow-up.

Abstraction of XML schemas.

There are many formalisms for describing XML schemas (see, e.g., [START_REF] Martens | Simple off the shelf abstractions for XML schema[END_REF] for a survey), but most of them are subsumed by the notion of an unranked tree automaton. To define it, fix a finite alphabet Σ ⊂ L. A non-deterministic unranked tree automaton (NTA) [START_REF] Neven | Automata, logic, and XML[END_REF][START_REF] Thatcher | Characterizing derivation trees of context-free grammars through a generalization of finite automata theory[END_REF] over Σ-labeled trees is a tuple A = (Q, Σ, δ, F ), where Q is a finite set of states, F ⊆ Q is the set of final states, and δ : Q × Σ → 2 (Q * ) is a transition function. We require that the δ(q, a)'s be regular languages over Q for all q ∈ Q and a ∈ Σ. When we deal with complexity results involving automata, we assume that these regular languages are represented by NFAs (or by regular expressions, since those can be converted into NFAs in polynomial time).

A run of A over a tree t with domain D and labeling function λ is a function r A : D → Q such that for each node s with n children s • 0, . . . , s • (n -1), the word

r A (s•0) • • • r A (s•(n-1)
) is in the language δ(r A (s), λ(s)). So, for a leaf s labeled a this means that s could be assigned state q iff the empty word ǫ is in δ(q, a). A run is accepting on tree t if the root of t is assigned an accepting state (formally, r A (ǫ) ∈ F . A tree t is accepted by A if there exists an accepting run of A on t. The set of all trees accepted by A is denoted by L(A).

We then define the containment problem under schemas as follows. Let Q be one of the classes CQ, UCQ, or BCCQ, and σ a set of axes. PROBLEM: Q ⊆ (σ) under schemas

INPUT:

queries q(x), q ′ (x ′ ) in Q(σ) and NTA A; QUESTION: is q(t) ⊆ q ′ (t) for every t ∈ L(A)?

A general upper bound. We show that all the versions of Q ⊆ (σ) remain decidable under schemas, but the upper bound is one exponent higher than it was without schemas. THEOREM 7.1. BCCQ ⊆ (⇓, ⇒, _) under schemas is 2EXPTIME-complete.

Proof sketch. The idea is to prove that we can reduce BCCQ ⊆ (⇓, ⇒, _) under schemas to a similar problem over finite alphabets and that we can encode a CQ(⇓, ⇒,_) into an exponential-size unranked tree automaton. The 2EXP-TIME upper bound then follows from tree automata techniques. The lower bound is immediate from Theorem 7.2.

Lower bounds. Since BCCQ ⊆ (⇓, ⇒, _) without the presence of schemas is in Π p 2 (and therefore in single-exponential time), it is natural to ask to whether the jump to doubleexponential time is unavoidable. It turns out that it is, even for conjunctive queries, as we can prove the following.

THEOREM 7.2. CQ ⊆ (⇓, ⇒) under schemas is 2EXPTIME-complete.
Proof sketch. The upper bound is immediate from Theorem 7.1. The lower bound is obtained in two steps. First we show that we can transfer lower bounds for UCQ ⊆ (⇓,⇒) under schemas to lower bounds for CQ ⊆ (⇓, ⇒) under schemas by adapting a technique from [START_REF] Miklau | Containment and equivalence for a fragment of XPath[END_REF]. Then we prove the lower bound for UCQ ⊆ (⇓, ⇒) by a reduction from the acceptance problem for alternating exponential space bounded Turing machines. This is done by adapting the proof of the 2EXPTIME lower bound for query containment from Theorem 6 in [START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF]. Two difficulties arise as that proof used queries with node equalities and wildcards. We handle node equalities by using data value equality constraints in our setting. We show how we can enforce all nodes from a tree to have different data values and then we simulate node equality by data equality. We further provide a modification of the encoding that avoids the use of wildcard. 2

We do not yet have a complete classification of what happens for all of the classes of queries under schemas, but we do have an indication very little is needed to make their complexity considerably higher than in the schema-less scenario. In fact one can use results from [START_REF] Björklund | Validity of tree pattern queries with respect to schema information[END_REF] to prove that even for very simple classes of queries (child relation only; no branching), containment under schemas provably requires exponential time.

THE EFFECT OF DATA VALUE COM-PARISONS

The last feature we are going to consider is data value comparisons, specifically disequalities =. This is a standard addition that has been considered in the study of relational conjunctive queries. In fact it is one of the mildest ways of adding a limited form of negation to positive queries in a way that preserves their nice properties, such as the decidability of static analysis. The other such extension, also considered here, is allowing Boolean combinations of CQs.

The relational case of CQs with = comparisons has been settled in [START_REF] Klug | On conjunctive queries containing inequalities[END_REF][START_REF] Kolaitis | On the complexity of the containment problem for conjunctive queries with built-in predicates[END_REF][START_REF] Van Der Meyden | The complexity of querying indefinite data about linearly ordered domains[END_REF]: the containment problem is Π p 2complete. From this we can derive some hardness results, for instance, containment of CQ(↓) with disequalities under schema is Π p 2 -hard (note that the schema assumption is necessary here to ensure documents code relational databases, as was already explained in Section 4). As for upper bounds, for relational BCCQs, even with disequalities, containment is decidable. In fact it is easily seen that such containment reduces to the complement of satisfiability for the Bernays-Schönfinkel class.

However, relational results do not give us any upper bounds on the containment problem for XML queries. We show in this section that there is a reason for it: such problems are, by and large, undecidable. In fact we show two undecidability results: for XML BCCQs with data comparisons, and even for CQs in the presence of schema information.

Queries with data comparisons. We now formally define classes of queries with = and = data comparisons. Suppose we start with a class Π(σ) of patterns. Then CQs with data comparisons over σ are defined as

q(x) = ∃ȳ n i=1 π i (z i ) ∧ α(x, ȳ) , (9)
where all the π i s are patterns from Π(σ) and α is a conjunction of formulae of the form u = v and u = v, where the variables u and v come from x and ȳ. For instance, q(x) = ∃y (a[b(x), c(y)] ∧ x = y) is such a query.

The class of such queries will be denoted by CQ(σ, ∼) (using the common XML literature notation of ∼ for data value comparisons). We then define the class UCQ(σ, ∼) as unions of queries in CQ(σ, ∼), and BCCQ(σ, ∼) as Boolean combinations of such queries.

Before we present our results, notice that in [START_REF] Barceló | XML with incomplete information[END_REF], the formula α allows explicit equalities. Normally in CQs these can be avoided simply by collapsing two variables. However, in the case of pattern-based queries, we may actually need explicit equalities, at least for UCQs. Consider, for example, a Boolean query q(x, y) = a(x) ∧ a(y). Then this query implies the following UCQ q ′ (x, y) = (x = y) ∨ _/_. Indeed, if q(x, y) is witnessed by two data values that are different, then they must occur in different nodes and hence the _/_ pattern is true.

Containment without schemas. Without schemas, the containment problem for BCCQs behaves drastically differently from the relation case, as we show below. THEOREM 8.1. Containment of BCCQs with data comparisons, i.e., the problem BCCQ ⊆ (⇓, ⇒, _, ∼), is undecidable.

In fact one needs either ↓, ↓ * , → or ↓, →, → * to establish undecidability.

Proof sketch. The proof shows that satisfiability for a BCCQ is undecidable by reduction from Post's Correspondence Problem (PCP). The proof is rather technical. It may be tempting to think that, since BCCQ(⇓, ⇒, _, ∼) can express certain key constraints, one can simulate the node equality tests from [START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF] in our setting by data equalities, and then we can adapt undecidability results from there as well. However, under such a key constraint, it is not clear at all how then the data equalities and inequalities from [START_REF] Björklund | Optimizing conjunctive queries over trees using schema information[END_REF] can be correctly simulated. The reduction from PCP consists of a series of encoding steps that state that (1) all trees satisfying the BCCQ must be string-shaped and of a certain form; and (2) that they somehow encode a PCP solution. The proof can be done in two flavors: either we say that the tree does not branch, in which case we need the negation of the → predicate to express (1) as well as both ↓ and ↓ * for (2). Alternatively, we say that the root has no grandchildren, in which case we need ↓ for (1) and → and → * for (2).

2

Containment with schemas. As in the previous section, for each containment problem of the form Q ⊆ (σ, ∼), with Q being CQ, or UCQ, or BCCQ, we can associate an analogous containment problem under schemas which, in addition, will take as an input a schema, represented as an automaton.

The combination of data value comparisons and schemas has an even more severe effect on the complexity of the containment problem: it becomes undecidable already for CQs using only downward navigation. THEOREM 8.2. The containment problem for CQ(⇓, ∼) queries under schema is undecidable.

Proof sketch. As in the proof of Theorem 7.2, we first notice that we can transfer lower bounds for UCQ ⊆ (⇓, ∼) under schemas to lower bounds for CQ ⊆ (⇓, ∼). After that we prove undecidability for UCQ ⊆ (⇓, ∼) by reduction from the halting problem of two-counter machines.

2

We conclude with the following remark. We noticed earlier that relational results give us Π p 2 -hardness for containment of CQ(↓, ∼) queries under schemas (to enforce relational encoding). While the precise complexity of the problem CQ ⊆ (↓, ∼) remains open (see concluding remarks), we can at least eliminate the need for schemas from the hardness result, i.e., we can prove the following. PROPOSITION 8.3. The problem CQ ⊆ (↓, ∼) is Π p 2 -hard.

CONCLUSION

We have analyzed the containment problem for three classes of queries -CQs, UCQs, and BCCQs -based on various classes of tree patterns (including Π(↓), Π(↓, →), Π(⇓), and Π(⇓, ⇒)), also in the presence of extra features such as wildcard, schemas, and disequality comparisons.

Overall, this gives us 96 cases of possible variations of the containment problem, and our results, although not generating the full set of 96 complexity bounds, have provided answers to the majority of them. Nonetheless, there are a few questions left open, that we would like to address. These concern the cases when we have some of the extra features (wildcard, schemas, inequalities) present.

With wildcard, without any restrictions, we do not yet have the precise complexity of containment for four classes: CQ(↓, _), CQ(↓, →, _), CQ(⇓, _), and UCQ(↓, _). With schemas, we do not yet know whether containment for CQs and UCQs without transitive closure axes is singleexponential or double-exponential. And with disequality comparisons, we do not know if containment without transitive closure axes is decidable. Based on our investigations, all these problems appear to be rather nontrivial. We plan to address them in the future.

Acknowledgment. This work was supported by the FET-Open project FoX (Foundations of XML), grant agreement FP7-ICT-233599, by EPSRC grant G049165, and by DFG grant MA 4938/2-1.