In their AMW'14-paper, Frochaux, Grohe, and Schweikardt showed that the query containment problem for monadic datalog on nite unranked labeled trees is Exptime-complete when (a) considering unordered trees using the child -axis, and when (b) considering ordered trees using the axes rstchild, nextsibling, and child. Furthermore, when allowing to use also the descendant -axis, the query containment problem was shown to be solvable in 2-fold exponential time, but it remained open to determine the problem's exact complexity in presence of the descendant-axis. The present paper closes this gap by showing that, in the presence of the descendant-axis, the problem is 2Exptime-hard.
The query containment problem (QCP) is a fundamental problem that has been
studied for various query languages. Datalog is a standard tool for expressing
queries with recursion. From Cosmadakis et al. [
Restricting attention to nite unranked labeled trees, Gottlob and Koch [
For the case where queries are allowed to also use the descendant -axis, [
The present paper closes the gap by proving a matching 2Exptime lower
bound (both, for ordered and for unordered trees). This gives a conclusive answer
to a question posed by Abiteboul et al. in [
The remainder of the paper is organised as follows. Section 2 xes the basic notation. Section 3 presents a 2Exptime lower bound for the QCP on ordered trees using the axes rstchild, nextsibling, root, leaf, lastsibling, child, descendant. Section 4 is devoted to the 2Exptime lower bound for the QCP on unordered trees using only the axes child and descendant. We conclude in Section 5.
Due to space limitations, many proof details had to be deferred to the paper's full version. 2
Throughout this paper, will always denote a nite non-empty alphabet. By N we denote the set of non-negative integers, and we let N>1 := N n f0g.
Relational Structures. As usual, a schema consists of a nite number of relation symbols R, each of a xed arity ar(R) 2 N>1. A -structure A consists of a nite non-empty set A called the domain of A, and a relation RA Aar(R) for each relation symbol R 2 . It will often be convenient to identify A with the set of atomic facts of A, i.e., the set atoms(A) consisting of all facts R(a1; : : : ; aar(R)) for all relation symbols R 2 and all tuples (a1; : : : ; aar(R)) 2 RA.
If is a schema and ` is a list of relation symbols, we write ` to denote the extension of the schema by the symbols in `. Furthermore, denotes the extension of by new unary relation symbols label , for all 2 .
Unordered Trees. An unordered -labeled tree T = (V T ; T ; ET ) consists of a nite non-empty set V T of nodes, a function T : V T ! assigning to each node v of T a label (v) 2 , and a set ET V T V T of directed edges such that the directed graph (V T ; ET ) is a rooted tree where edges are directed from the root towards the leaves. We represent such a tree T as a relational structure of domain V T with unary and binary relations: For each label 2 , label (x) expresses that x is a node with label ; child(x; y) expresses that y is a child of node x; root(x) expresses that x is the tree's root node; leaf (x) expresses that x is a leaf; and desc(x; y) expresses that y is a descendant of x (i.e., y is a child or a grandchild or . . . of x). We denote this relational structure representing T by Su(T ), but when no confusion arises we simply write T instead of Su(T ).
The queries we consider for unordered trees are allowed to make use of at least the predicates label and child. We x the schema u := f child g:
Ordered Trees. An ordered -labeled tree T = (V T ; T ; ET ; orderT ) has the same components as an unordered -labeled tree and, in addition, orderT xes for each node u of T a strict linear order of all the children of u in T .
To represent such a tree as a relational structure, we use the same domain and the same predicates as for unordered -labeled trees, along with three further predicates fc (\ rst-child"), ns (\next-sibling"), and ls (\last sibling"), where fc(x; y) expresses that y is the rst child of node x (w.r.t. the linear order of the children of x induced by orderT ); ns(x; y) expresses that y is the right sibling of x (i.e., x and y have the same parent p, and y is the immediate successor of x in the linear order of p's children given by orderT ); and ls(x) expresses that x is the rightmost sibling (w.r.t. the linear order of the children of x's parent given by orderT ). We denote this relational structure representing T by So(T ), but when no confusion arises we simply write T instead of So(T ).
The queries we consider for ordered trees are allowed to make use of at
least the predicates label , fc, and ns. We x the schemas o := f fc; ns g
and GK := oroot;leaf ;ls. In [
Datalog. We assume that the reader is familiar with the syntax and
semantics of datalog (cf., e.g., [
Monadic datalog queries. A datalog program belongs to monadic datalog (mDatalog, for short), if all its intensional predicates have arity 1.
A unary monadic datalog query of schema is a tuple Q = (P; P ) where P is a monadic datalog program of schema and P is an intensional predicate of P. P and P are called the program and the query predicate of Q. When evaluated in a nite -structure A that represents a labeled tree T , the query Q results in the unary relation Q(T ) := fa 2 A : P (a) 2 TP!(atoms(A)) g.
The Boolean monadic datalog query QBool speci ed by Q = (P; P ) is the Boolean query with QBool(T ) = yes i the tree's root node belongs to Q(T ).
The size jjQjj of a monadic datalog query Q is the length of Q = (P; P ) viewed as a string over a suitable alphabet.
Expressive power of monadic datalog on trees. On ordered -labeled
trees represented as GK; -structures, monadic datalog can express exactly the
same unary queries as monadic second-order logic [
Using the monotonicity of the immediate consequence operator, one obtains
that removing any of the predicates root; leaf ; ls from GK strictly decreases the
expressive power of mDatalog on ordered trees (see [
The Query Containment Problem (QCP). Let be one of the schemas
used for representing (ordered or unordered) -labeled trees as relational
structures. For two unary queries Q1 and Q2 of schema we write Q1 Q2 to
indicate that for every -labeled tree T we have Q1(T ) Q2(T ). Similarly, if
Q1 and Q2 are Boolean queries of schema , we write Q1 Q2 to indicate that
for every -labeled tree T , if Q1(T ) = yes then also Q2(T ) = yes. We write
Q1 6 Q2 to indicate that Q1 Q2 does not hold. For a schema , the query
containment problem (QCP) for mDatalog( ) on nite labeled trees receives as
input a nite alphabet and two (unary or Boolean) mDatalog( )-queries Q1
and Q2, and the task is to decide whether Q1 Q2. From [
Theorem 2 The QCP for Boolean mDatalog( GchKild;desc) on
dered trees is 2Exptime-hard.
nite labeled
orThe proof is by a reduction based on a 2Exptime-hardness result of Bjorklund,
Martens, and Schwentick [
A run of A on T is accepting, if T 's root note v is labeled with an accepting state of A, i.e., (v) 2 F . A nite ordered -labeled tree T is accepted by A, if there exists an accepting run of A on T . We write L(A) to denote the language of A, i.e., the set of all nite ordered -labeled trees that are accepted by A.
To present an NTA A = ( ; S; ; F ) as an input for an algorithm, the stringlanguages L that occur in the right-hand side of rules in are speci ed by NFAs AL = ( L; QL; L; qL; FL), whose input alphabet is L := S, and where QL is a nite set of states, L (QL L QL) is a transition relation, qL 2 QL is the initial state, and FL QL is the set of accepting states of AL. The size of AL is jjALjj := jQLj + j Lj, and the size of A is the sum of j j, jSj, j j, and jjALjj, for all L 2 strL(A), where strL(A) is the set of all string-languages L that occur in the right-hand side of a rule in .
In [
Theorem 3 (Bjorklund et al. [
Our proof of Theorem 2 is via a polynomial-time reduction from the problem validity of Boolean CQ(child; desc) w.r.t. a tree automaton to the QCP for Boolean mDatalog( GchKild;desc) on nite labeled ordered trees.
Let QCQ be a Boolean CQ(child; desc)-query, and let A be an NTA with input alphabet . We translate QCQ into an equivalent mDatalog( ud;esc)-query Q0CQ = (P; P ): If QCQ is of the form Ans() R1(u1); : : : ; R`(u`) for relational atoms R1(u1); : : : ; R`(u`), we choose an arbitrary variable x that occurs in at least one of these atoms, we use a new unary idb-predicate P , and we let P be the program consisting of the two rules P (x) R1(u1); : : : ; R`(u`) and P (x) child(x; y); P (y).
Then, for every ordered -labeled tree T we have Q0CQ;Bool(T ) = yes i QCQ(T ) = yes. The following Lemma 4 constructs, in time polynomial in the size of A, an mDatalog( GchKil;d )-query QA which is equivalent to A, i.e., for every ordered -labeled tree T we have QA;Bool(T ) = yes i T 2 L(A).
Note that QCQ is valid w.r.t. A if, and only if, QA;Bool Q0CQ;Bool. Thus, we obtain the desired polynomial-time reduction, showing that the QCP for Boolean mDatalog( GchKild;desc) on nite ordered -labeled trees inherits the 2Exptimehardness from the problem \validity of Boolean CQ(child; desc) w.r.t. a tree automaton". All that remains to nish the proof of Theorem 2 is to prove the following Lemma 4.
Lemma 4 For every NTA A = ( ; S; ; F ) there is an mDatalog( GchKil;d )-query Q = (P; P ), such that for every nite ordered -labeled tree T we have QBool(T ) = yes i T 2 L(A). Furthermore, Q is constructible from A in time polynomial in the size of A.
Proof. We construct a monadic datalog program P which, for every node v of T , computes information on all states that A can assume at node v, i.e., all states s 2 S for which there is a run of A on the subtree of T rooted at v, such that (v) = s. To this end, for every state s 2 S, we will use an idb-predicate s. The query QBool will accept an input tree T if there is an accepting state s 2 F such that s(rootT ) 2 TP!(T ), where rootT denotes the root of T . The program P is constructed in such a way that it performs a generalised version of the well-known powerset construction.
Recall that the transition rules of A are of the form (s; ) ! L, where s 2 S, 2 , and L is a regular string-language over S, speci ed by an NFA AL = ( L; QL; L; qL; FL) with L = S and L (QL L QL). W.l.o.g., we assume that the state sets of all the NFAs are mutually disjoint, and disjoint with S.
To emulate the standard powerset construction of the NFA AL, we use an idb-predicate q for every state q 2 QL, and an extra idb-predicate AccL. If u1; : : : ; un are the children of a node v in an input tree T , the NFA AL processes the strings over alphabet S that are of the form s1 sn, where si is a state that A can assume at node ui (for every i 2 f1; : : : ; ng). We start by letting PL := ; and then add to PL the following rules: For the initial state qL of AL, consider all s 2 S and q 2 QL such that (qL; s; q) 2 L, and add to PL the rule q(x) fc(y; x); s(x) : Afterwards, for every transition (q; s; q0) 2 L, add to PL the rule q0(x0)
q(x); ns(x; x0); s(x0) : Finally, for every accepting state q 2 FL of AL, add to PL the rule
AccL(x) ls(x); q(x) : Clearly, the program PL can be constructed in time polynomial in jjALjj.
Now, we are ready to construct the monadic datalog program P that simulates the NTA A. We start by letting P be the disjoint union of the programs PL, for all L 2 strL(A). The computation of A on an input tree T starts in the leaves of T . Thus, to initiate the simulation of A, we consider every rule (s; ) ! L in , where " 2 L.1 For each such rule, we add to P the rule s(x)
label (x); leaf (x) : Note that for each L 2 strL(A), the program PL ensures that every last sibling un of a node v will be marked by AccL(un) i the states of A assigned to un and its siblings form a string in L. To transfer this information from the last sibling to its parent node, we add to P the rule childAccL (y)
child(y; x); ls(x); AccL(x) ; where childAccL is a new idb-predicate, for every L 2 strL(A).
Afterwards, we consider every rule (s; ) ! L in , and add to P the rule s(x) childAccL (x); label (x) : Finally, to test if A accepts an input tree T , we add rules to test whether T 's root is assigned an accepting state of A. To this end, we consider every accepting state s 2 F of A and add to P the rule
P (x) root(x); s(x) : This nishes the construction of the program P and the query Q = (P; P ). Clearly, P is a monadic datalog program of schema GchKil;d , and Q can be constructed in time polynomial in jjAjj. It is not di cult, but somewhat tedious, to 1 Note that \" 2 L ?" can be checked by simply checking whether qL 2 FL. verify that, as intended by the construction, indeed for every nite ordered labeled tree T we have QBool(T ) = yes if, and only if, there exists an accepting run of the NTA A on T . This completes the proof of Lemma 4. tu 4
Our next aim is to transfer the statement of Theorem 2 to unordered trees. Precisely, we will show the following.
Theorem 5 The QCP for Boolean mDatalog( udesc) on nite labeled unordered trees is 2Exptime-hard.
For proving Theorem 5, we cannot directly build on Bjorklund et al.'s Theorem 3, since their NTAs explicitly refer to ordered trees.
By constructing suitable reductions, we can show that proving Theorem 5 boils down to proving the following Theorem 6, which deals with the emptiness problem on trees over a ranked alphabet.
For the remainder of this section, 0 will denote a ranked nite alphabet. I.e., 0 is a nite set of symbols, and each symbol 2 0 is equipped with a xed arity ar( ) 2 N. An unordered ranked 0-labeled tree is an unordered 0-labeled tree where each node labeled with symbol 2 0 has exactly ar( ) children. For a Boolean mDatalog( ud;es0c)-query Q, we say that Q is unsatis able by unordered ranked trees (in symbols: Q = ?) if for every nite unordered ranked 0-labeled tree T we have Q(T ) = ;. The emptiness problem for Boolean mDatalog( ud;es0c) on nite unordered ranked 0-labeled trees receives as input a Boolean mDatalog( ud;es0c)-query Q, and the task is to decide whether Q = ?. The main technical step needed for proving Theorem 5 is to prove the following. Theorem 6 There is a ranked nite alphabet 0, such that the emptiness problem for Boolean mDatalog( ud;es0c) on nite unordered ranked 0-labeled trees is 2Exptime-hard.
For the proof of Theorem 6, we can build on the approach used by Bjorklund
et al. for proving Theorem 3: As in [
An alternating Turing machine (ATM) is a nondeterministic Turing machine A = (Q; ; ; ; q0) whose state space Q is partitioned into universal states Q8, existential states Q9, an accepting state qa, and a rejecting state qr. The ATM's tape cells are numbered 0,1,2,. . . . A con guration of A is a nite string of the form w1qw2 with w1; w2 2 and q 2 Q, representing the situation where the ATM's tape contains the word w1w2, followed by blanks, the ATM's current state is q, and the head is positioned at the rst letter of w2. A con guration w1qw2 is a halting (universal, existential, resp.) con guration if q 2 fqa; qrg (q 2 Q8, q 2 Q9, resp.). W.l.o.g., no halting con guration has a successor con guration, and every halting con guration is of the form qw. A computation tree TA of the ATM A on input w 2 is a tree labeled with con gurations of A, such that the root of TA is labeled by q0w, and for each node v of TA labeled by w1qw2, { if q 2 Q9, then u has exactly one child, and this child is labeled with a successor con guration of w1qw2, { if q 2 Q8, then u has a child v for every successor con guration w10q0w20, and v is labeled by w10q0w20, { if q 2 fqa; qrg, then u is a leaf of TA.
A computation tree is accepting if all its branches are nite and all its leaves are labeled by con gurations with state qa. The language L(A) of A is de ned as the set of all words w 2 , for which there exists an accepting computation tree of A on w. W.l.o.g., we will assume that the ATM is normalized, i.e., every nonhalting con guration has precisely two successor con gurations, each universal step only a ects the state of the machine, and the machine always alternates between universal and existential states.
The proof of Theorem 6 proceeds by a reduction from the word problem for exponential-space bounded ATMs A. The reduction itself will be done from an ATM with empty input word. To this end, we construct, in the canonical way, for the given exponential-space bounded ATM A and the given word w 2 an ATM Aw that works in space exponential in the size of w and accepts the empty word if, and only if, A accepts w. Since A is exponential-space bounded, the non-blank portion of the ATM's tape during a computation of Aw will never be longer that 2n, where n is polynomial in the size jwj of the original input.
The crucial point of the reduction is to nd an encoding of computation trees
of Aw on empty input, which can be veri ed by a mDatalog( ud;es0c)-query that
can be constructed in time polynomial in the size of Aw. For this, it is necessary
to nd a smart encoding of the tape inscription of length 2n. This encoding shall
allow to compare the content of every tape cell with the same tape cell of the
successor con guration. To achieve this, we adapt the encoding of Bjorklund et
al. [
We choose a xed ranked nite alphabet 0 which, among other symbols, contains a 0-ary symbol ?, unary symbols r; p; m; 0; 1, binary symbols CTleft; CTright, and 3-ary symbols CT8 and s. Consider a computation tree TAw of a 9normal9ized ATM Aw = (Q; ; ; ; q0), see Figure 1.
We x an arbitrary order on the children of nodes in TAw , such that every universal node has a left child and a right child. The encoding T := enc(TAw ) is the ranked 0-labeled unordered tree obtained from TAw by replacing every node v labeled w1qw2 with a 0-labeled ranked tree enc(tv), as follows: { if v is universal, then the root of enc(tv) is labeled with CT8, { if v is existential, and v is the root of TAw or v is the left child of a universal node, then the root of enc(tv) is labeled with CTl9eft, { if v is existential, and v is the right child of a universal node, then the root of enc(tv) is labeled with CTright,
9
CT8 r
CTright 9
CT8
{ exactly one child of the root of enc(tv) is labeled by r (this will be the root of the subtree that encodes the con guration at v), and { for each child u of v in TAw , enc(tv) has a subtree enc(tu), which is the encoded subtree of TAw obtained by the replacement of u.
The subtree r rooted at the r-labeled child of the root of enc(tv), encodes the
con guration c := w1qw2 represented by node v in TAw . Since A is
exponentialspace bounded, the tape inscription of c has length 6 2n. For representing c,
we use a full binary ordered tree of height n. The path from the root to a leaf
speci es the address of the tape cell represented by the leaf, and the leaf carries
information on the tape cell's inscription and, in case that the tape cell is the
current head position, also information on the current state; all this information
is encoded by a suitable tape cell gadget that is attached to the \leaf". The
number k of possible tape cell inscriptions (enriched with information on the
current state) is polynomial in jjAwjj. The nodes of the \full binary tree" are
called skeleton nodes and are labeled s. To ensure that the desired query Q can
be constructed in polynomial time, we attach to each skeleton node a navigation
gadget [
Given an ATM A and a word w 2 , we construct in polynomial time an mDatalog( ud;es0c)-query Q = (P; Ans) such that QBool 6= ? i there is an accepting computation tree for Aw on ", i.e., w 2 L(A). The query Q consists of two parts, one to verify that the structure of the input tree represents an encoded computation tree, and the other to verify consistency with the ATM's transition relation. Details can be found in the paper's full version. The particular choice of the navigation gadgets ensures that Q can be constructed in time polynomial sleaf i m 0 1 0 ? k in the size of A and w. The only point where we make essential use of the descpredicate is during the comparison of the cells by using the navigation gadgets. 5
Along with the upper bound provided by Theorem 1, and since udesc ochild;desc, Theorem 5 implies the following corollary, which summarizes our main results. Corollary 7 The QCP is 2Exptime-complete for Boolean mDatalog( udesc) on nite labeled unordered trees, and for Boolean mDatalog( ochild;desc) on nite labeled ordered trees.
By applying standard reductions, the 2Exptime-completeness results of Corollary 7 carry over from the QCP to the equivalence problem. When restricting attention to ranked trees over a ranked nite alphabet, the 2Exptimecompleteness results also carry over to the emptiness problem. For unranked labeled trees, the emptiness problem for mDatalog( ochild;desc) is in 2Exptime, but we currently do not have a matching 2Exptime-hardness result.
An overview of the currently known results is given in Table 1; for further
information and detailed proofs we refer to [
Table 1. Complexity of monadic datalog on nite labeled trees; N froot; leaf g and M froot; leaf ; ls; childg; \c" (\h") means \complete" (\hard").
N u
M o uN[fdescg
oM[fchild;descg Exptime-c Exptime-h & in 2Exptime 2Exptime-c child;desc GK Emptiness Equivalence Exptime-c Containment Exptime-c 2Exptime-c 2Exptime-c