Monadic Datalog Containment on Trees

Abstract

We show that the query containment problem for monadic datalog on nite unranked labeled trees can be solved in 2-fold exponential time when (a) considering unordered trees using the axes child and descendant, and when (b) considering ordered trees using the axes rstchild, nextsibling, child, and descendant. When omitting the descendant -axis, we obtain that in both cases the problem is Exptime-complete.

Introduction

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. [ 5 ] and Benedikt et al. [ 2 ] it is known that the QCP for monadic datalog queries on the class of all nite relational structures is 2Exptime-complete. Restricting attention to nite unranked labeled trees, Gottlob and Koch [ 8 ] showed that on ordered trees the QCP for monadic datalog is Exptime-hard and decidable, leaving open the question of a tight bound.

Here we show a matching Exptime upper bound for the QCP for monadic datalog on ordered trees using the axes rstchild, nextsibling, and child. When adding the descendant -axis, we obtain a 2Exptime upper bound. This, in particular, also yields a 2Exptime upper bound for the QCP for monadic datalog on unordered trees using the axes child and descendant, and an Exptime upper bound for unordered trees using only the child -axis. The former result answers a question posed by Abiteboul et al. in [ 1 ]. We complement the latter result by a matching lower bound.

The paper is organised as follows. Section 2 xes the basic notation concerning datalog queries, (unordered and ordered) trees and their representations as logical structures, and summarises basic properties of monadic datalog on trees. Section 3 presents our main results regarding the query containment problem for monadic datalog on trees. Due to space limitations, most technical details had to be deferred to the full version of this paper, available at http://arxiv.org/abs/1404.0606.

Trees and Monadic Datalog (mDatalog)

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 relation 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 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 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 := fchildg:

-labeled trees as u; -structures was considThe representation of unordered ered, e.g., in [ 1 ].

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 := ffc; nsg and

GK := oroot;leaf ;ls: In [ 8 ], Gottlob and Koch represented ordered -labeled trees as GK; -structures.

Datalog. We assume that the reader is familiar with the syntax and semantics of datalog (cf., e.g., [ 6,8 ]). Predicates that occur in the head of some rule of a datalog program P are called intensional, whereas predicates that only occur in the body of rules of P are called extensional. By idb(P) and edb(P) we denote the sets of intensional and extensional predicates of P, resp. We say that P is of schema if edb(P) . We write TP to denote the immediate consequence operator associated with a datalog program P. Recall that TP maps a set C of atomic facts to the set of all atomic facts that are derivable from C by at most one application of the rules of P (see e.g. [ 6,8 ]). The monotonicity of TP implies that for each nite set C, the iterated application of TP to C leads to a xed point, denoted by TP!(C), which is reached after a nite number of iterations.

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. From Gottlob and

Koch [ 8 ] we know that on ordered -labeled trees represented as GK; -structures, monadic datalog can express exactly the same unary queries as monadic secondorder logic | for short, we will say \mDatalog( GK) = MSO( GK) on ordered trees". Since the child and desc relations are de nable in MSO( GK), this implies that mDatalog( GK) = mDatalog( GchKild;desc) on ordered trees.

On the other hand, 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 [ 7 ]). By a similar reasoning one also obtains that on unordered trees, represented as ur;oot;leaf ;desc-structures, monadic datalog is strictly less expressive than monadic second-order logic, and omitting any of the predicates root, leaf further reduces the expressiveness of monadic datalog on unordered trees [ 7 ]. 3

Query Containment for Monadic Datalog on Trees Let be one of the schemas introduced in Section 2 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. The query containment problem (QCP, for short) is de ned as follows:

The QCP for mDatalog( ) on trees

Input: A nite alphabet and

two (unary or Boolean) mDatalog( Question: Is Q1 Q2 ? )-queries Q1 and Q2.

It is not di cult to see that this problem is decidable: the rst step is to observe that monadic datalog can e ectively be embedded into monadic secondorder logic, the second step then applies the well-known result that the monadic second-order theory of nite labeled trees is decidable (cf., e.g., [ 11,4 ]).

Regarding ordered trees represented as GK-structures, in [ 8 ] it was shown that the QCP for unary mDatalog( GK)-queries on trees is Exptime-hard. Our rst main result generalises this to unordered trees represented as u-structures:

Theorem 1

The QCP for Boolean mDatalog( u) on unordered trees is Exptime-hard.

Our proof proceeds via a reduction from the Exptime-complete two person corridor tiling (TPCT) problem [ 3 ]: For a given instance I of the TPCTproblem we construct (in polynomial time) an alphabet and two Boolean mDatalog( u; )-queries Q1, Q2 which enforce that any tree T witnessing that Q1 6 Q2, contains an encoding of a winning strategy for the rst player of the TPCT-game associated with I. Using Theorem 1 along with a method of [ 8 ] for replacing the child-predicate by means of the predicates fc; ns, we can transfer the hardness result to ordered trees represented by o-structures:

Corollary 2

The QCP for Boolean mDatalog( o) on ordered trees is Exptime-hard.

Our second main result provides a matching Exptime upper bound for the QCP on ordered trees, even in the presence of all predicates in GchKild:

Theorem 3

The QCP for unary mDatalog( GchKild) on ordered trees belongs to Exptime. Proof (sketch). Consider a schema GchKild;desc. By using the automatatheoretic approach [ 5 ], a canonical method for deciding the QCP for unary mDatalog( ) proceeds as follows: (1) Transform the input queries Q1 and Q2 into Boolean queries Q01 and Q02 on binary trees, such that Q1 Q2 i Q01 Q02. (2) Construct tree automata Ayes and Ano such that Ayes (resp. A2no) accepts 1 2 1 exactly those trees T with Q01(T ) = yes (resp. Q02(T ) = no). (3) Construct the product automaton B of Ayes and A2no, such that B accepts 1 exactly those trees that are accepted by Ayes and by A2no. Afterwards, check 1 if the tree language recognised by B is empty. Note that this is the case if, and only if, Q1 Q2.

Using time polynomial in the size of Q1 and Q2, Step (1) can be achieved in a standard way by appropriately extending the labelling alphabet .

For Step (3), if Ayes and Ano are nondeterministic bottom-up tree automata, 1 2 the construction of B takes time polynomial in the sizes of Ayes and A2no, and the 1 emptiness test can be done in time polynomial in the size of B (see e.g. [ 4 ]).

The rst idea for tackling Step (2) is to use a standard translation of Boolean monadic datalog queries into monadic second-order (MSO) sentences: It is not di cult to see (cf., e.g. [ 8 ]) that any Boolean mDatalog( )-query Q can be translated in polynomial time into an equivalent MSO-sentence 'Q of the form 8X1 8Xn 9z1 9z` Wm j=1 j where n is the number of intensional predicates of Q's monadic datalog program P, ` and m are linear in the size of Q, and each j is a conjunction of at most b atoms or negated atoms, where b is linear in the maximum number of atoms occurring in the body of a rule of P. Applying the standard method for translating MSO-sentences into tree automata (cf., e.g., [ 11 ]), we can translate the sentence :'Q into a nondeterministic bottom-up tree-automaton Ano that accepts a tree T i Q(T ) = no. This automaton has 2(m0 cb0 ) states, where m0 and b0 are linear in m and b, resp., and c is a constant not depending on Q or ; and Ano can be constructed in time polynomial in j j 2n+`+m0 cb0 .

Using the subset construction, one obtains an automaton Ayes which accepts a tree T i Q(T ) = yes; and this automaton has 22(m0 cb0 ) states.

Note that, a priori, b0 might be linearly related to the size of Q. Thus, the approach described so far leads to a 3-fold exponential algorithm that solves the QCP for unary mDatalog( )-queries.

In case that does not contain the desc-predicate, we obtain a 2-fold exponential algorithm as follows: At the end of Step (1) we rewrite Q01 and Q02 into queries that do not contain the child-predicate , and we transform both queries into tree marking normal form (TMNF), i.e., a normal form in which bodies of rules consist of at most two atoms, at least one of which is unary. From [ 8 ] we obtain that these transformations can be done in time polynomial in the size of Q01 and Q02. Note that for TMNF-queries, the parameters b and b0 are constant (i.e., they do not depend on the query), and thus the above description shows that for TMNF-queries the automaton Ano can be constructed in 1-fold 2 exponential time, and Ayes can be constructed in 2-fold exponential time.

1

Finally, the key idea to obtain a 1-fold exponential algorithm solving the QCP is to use a di erent construction for the automaton Ayes, which does not 1 use the detour via an MSO-formula but, instead, takes a detour via a two-way alternating tree automaton (2ATA): We show that a Boolean TMNF-query can be translated, in polynomial time, into a 2ATA A^1yes that accepts a tree T i Q1(T ) = yes. It is known that, within 1-fold exponential time, a 2ATA can be transformed into an equivalent nondeterministic bottom-up tree automaton (this was claimed already in [ 5 ]; detailed proofs of more general results can be found in [ 12,10 ]). In summary, this leads to a 1-fold exponential algorithm for solving the QCP for mDatalog( GchKild) on ordered trees. tu Since uroot;leaf

GchKild, Theorem 3 immediately implies: Corollary 4 The QCP for unary mDatalog( uroot;leaf ) on unordered trees belongs to Exptime.

It remains open if the Exptime-membership results of Theorem 3 and Corollary 4 can be generalised to queries that also use the descendant predicate desc. However, the rst approach described in the proof of Theorem 3 yields a 3-fold exponential algorithm. We can improve this by using methods and results from [ 8 ] and [ 9 ] to eliminate the desc-predicate at the expense of an exponential blowup of the query size. Afterwards, we apply the algorithms provided by Theorem 3 and Corollary 4. This leads to the following: Theorem 5 The QCP for unary mDatalog( uroot;leaf ;desc) on unordered trees and for unary mDatalog( GchKild;desc) on ordered trees can be solved in 2-fold exponential time.

Open Question. It remains open to close the gap between the Exptime lower and the 2Exptime upper bound for the case where the descendant -axis is involved.

Acknowledgment. The rst author would like to thank Mariano Zelke for countless inspiring discussions and helpful hints on and o the topic.

References

1. S. Abiteboul , P. Bourhis , A. Muscholl , and Z. Wu . Recursive queries on trees and data trees . In Proc. ICDT'13 , pages 93 { 104 , 2013 .

2. M. Benedikt , P. Bourhis , and P. Senellart . Monadic datalog containment . In Proc. ICALP'12 , pages 79 { 91 , 2012 .

3. B. S. Chlebus . Domino-tiling games . J. Comput. Syst. Sci. , 32 ( 3 ): 374 { 392 , 1986 .

4. H. Comon , M. Dauchet , R. Gilleron , C. Loding, F. Jacquemard , D. Lugiez , S. Tison , and M. Tommasi . Tree automata techniques and applications . Available at http: //www.grappa. univ-lille3.fr/tata , 2008 . release November, 18th 2008 .

5. S. Cosmadakis , H. Gaifman , P. Kanellakis , and M. Vardi . Decidable optimization problems for database logic programs . In Proc. STOC'88 , pages 477 { 490 , 1988 .

6. E. Dantsin , T. Eiter , G. Gottlob, and A. Voronkov . Complexity and expressive power of logic programming . ACM Comput. Surv. , 33 ( 3 ): 374 { 425 , 2001 .

7. A. Frochaux and N. Schweikardt . A note on monadic datalog on unranked trees . Technical Report , available at CoRR, abs/1310.1316, 2013 .

8. G. Gottlob and C. Koch . Monadic datalog and the expressive power of languages for web information extraction . J. ACM , 51 ( 1 ): 74 { 113 , 2004 .

9. G. Gottlob , C. Koch , and K. Schulz . Conjunctive queries over trees . J. ACM , 53 ( 2 ): 238 { 272 , 2006 .

10. S. Maneth , S. Friese , and H. Seidl . Type-Checking Tree Walking Transducers . In D. D'Souza and P. Shankar, editors, Modern applications of automata theory , volume 2 of IISc Research Monographs. World Scienti c, 2010 .

11. W. Thomas. Languages, automata, and logic . In Handbook of Formal Languages , volume 3 , pages 389 { 455 . Springer-Verlag, 1997 .

12. M. Vardi . Reasoning about the past with two-way automata . In Proc. ICALP'98 , pages 628 { 641 , 1998 .