{'fraction_non_alphanumeric': 0.05179214098923766, 'fraction_numerical': 0.014568427593706577, 'mean_word_length': 3.4261593704637483, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 82, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics

We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems), and ontology-mediated queries (OMQs) based on expressive description logics and unions of conjunctive queries. Containment in MMSNP was known to be decidable due to a result by Feder and Vardi, but its exact complexity has remained open. We prove 2NEXPTIME-completeness and extend this result to monadic disjunctive Datalog and to OMQs.


Introduction
In knowledge representation with ontologies, data centric applications have become a significant subject of research. In such applications, ontologies are used to address incompleteness and heterogeneity of the data, and for enriching it with background knowledge (Calvanese et al. 2009). This trend has given rise to the notion of an ontology-mediated query (OMQ) which combines a database query with an ontology, often formulated in a description logic (DL). From a data centric viewpoint, an OMQ can be viewed as a normal database query that happens to consist of two components (the ontology and the actual query). It is thus natural to study OMQs in the same way as other query languages, aiming to understand e.g. their expressive power and the complexity of fundamental reasoning tasks such as query containment. In this paper, we concentrate on the latter.
Containment of OMQs was first studied in (Levy and Rousset 1996;Calvanese, De Giacomo, and Lenzerini 1998) and more recently in (Calvanese, Ortiz, and Simkus 2011;Bienvenu et al. 2014;Bienvenu, Lutz, and Wolter 2012). To appreciate the usefulness of this reasoning task, it is important to recall that real-world ontologies can be very large and tend to change frequently. As a user of OMQs, one might thus want to know whether the ontology used in an OMQ can be replaced with a potentially much smaller module extracted from a large ontology or with a newly released version of the ontology, without compromising query answers. This requires to decide equivalence of OMQs, which can be done by answering two containment questions. Containment can also serve as a central reasoning service when optimizing OMQs in static analysis (Bienvenu, Lutz, and Wolter 2012).
In the most general form of OMQ containment, the two OMQs can involve different ontologies and the data schema (ABox signature, in DL terms) can be restricted to a subset of the signature of the ontologies. While results for this form of containment have been obtained for inexpressive DLs such as those of the DL-Lite and EL families (Bienvenu, Lutz, and Wolter 2012), containment of OMQs based on expressive DLs turned out to be a technically challenging problem. A step forward has been made in (Bienvenu et al. 2014) where it was observed that there is a close relationship between three groups of formalisms: (i) OMQs based on expressive DLs, (ii) monadic disjunctive Datalog (MDDLog) programs, and (iii) constraint satisfaction problems (CSPs) as well as their logical generalization MMSNP. These observations have given rise to first complexity results for containment of OMQs based on expressive DLs, namely NEXPTIME-completeness for several cases where the actual query is an atomic query of the form A(x), with A a monadic relation.
In this paper, we study containment in MDDLog, MM-SNP, and OMQs that are based on expressive DLs, conjunctive queries (CQ), and unions thereof (UCQs). A relevant result is due to Feder and Vardi (1998) who show that containment of MMSNP sentences is decidable and that this gives rise to decidability results for CSPs such as whether the complement of a CSP is definable in monadic Datalog. As shown in (Bienvenu et al. 2014), the complement of MM-SNP is equivalent to Boolean MDDLog programs and to Boolean OMQs with UCQs as the actual query. While these results can be used to infer decidability of containment in the mentioned query languages, they do not immediately yield tight complexity bounds. In particular, Feder and Vardi describe their algorithm for containment in MMSNP only on a very high level of abstraction, do not analyze its complexity, and do not attempt to provide lower bounds. Also a subsequent study of MMSNP containment and related problems did not clarify the precise complexity (Madelaine 2010). Other issues to be addressed are that MMSNP containment corresponds only to the containment of Boolean queries and that the translation of OMQs into MMSNP involves a double exponential blowup.
Our main contribution is to show that all of the mentioned containment problems are 2NEXPTIME-complete. In particular, this is the case for MDDLog, MMSNP, OMQs whose ontology is formulated in a DL between ALC and SHI and where the actual queries are UCQs, and OMQs whose ontology is formulated in a DL between ALCI and SHI and where the actual queries are CQs. This closes open problems from (Madelaine 2010) about MMSNP containment and from (Bienvenu, Lutz, and Wolter 2012) about OMQ containment. In addition, clarifying the complexity of MDDLog containment is interesting from the perspective of database theory, where Datalog containment has received a lot of attention. While being undecidable in general (Shmueli 1993), containment is known to be decidable for monadic Datalog (Cosmadakis et al. 1988) and is in fact 2EXPTIME-complete (Benedikt, Bourhis, and Senellart 2012). Here, we show that adding disjunction increases the complexity to 2NEXPTIME. We refer to (Bourhis, Krötzsch, and Rudolph 2015) for another recent work that generalizes monadic Datalog containment, in an orthogonal direction. It is interesting to note that all these previous works rely on the existence of witness instances for non-containment which have a tree-like shape. In MDDLog containment, such witnesses are not guaranteed to exist which results in significant technical challenges.
This paper is structured as follows. We first concentrate on MDDLog containment, establishing that containment of a Boolean MDDLog program in a Boolean conjunctive query (CQ) is 2NEXPTIME-hard and that containment in Boolean MDDLog is in 2NEXPTIME. We then generalize the upper bound to programs that are non-Boolean and admit constant symbols. The lower bound uses a reduction of a tiling problem and borrows queries from (Björklund, Martens, and Schwentick 2008). For the upper bound, we essentially follow the arguments of Feder and Vardi (1998), but provide full details of all involved constructions and carefully analyze the involved blowups. It turns out that an MDDLog containment question Π 1 ⊆ Π 2 can be decided non-deterministically in time single exponential in the size of Π 1 and double exponential in the size of Π 2 . Together with some straightforward observations, this also settles the complexity of MMSNP containment. We additionally observe that FO-and Datalog-rewritability of MDDLog programs and (the complements of) MMSNP sentences is 2NEXPTIME-hard.
We then consider containment between OMQs, starting with the observation that the 2NEXPTIME lower bound for MDDLog also yields that containment of an OMQ in a CQ is 2NEXPTIME-hard when ontologies are formulated in ALC and UCQs are used as queries. The same is true for the containment of an OMQ in an OMQ, even when their ontologies are identical. We then establish a matching upper bound by translating OMQs to MDDLog and applying our results for MDDLog containment. It is interesting that the complexity is double exponential only in the size of the actual query (which tends to be very small) and only single exponential in the size of the ontology. We finally establish another 2NEX-PTIME lower bound which applies to containment of OMQs whose ontologies are formulated in ALCI and whose actual queries are CQs (instead of UCQs as in the first lower bound). This requires a different reduction strategy which borrows queries from (Lutz 2008).
Due to space limitations, we defer proof details to the appendix, available at http://www.informatik.unibremen.de/tdki/research/papers.html.

Preliminaries
A schema is a finite collection S = (S 1 , . . . , S k ) of relation symbols with associated non-negative arity. An S-fact is an expression of the form S(a 1 , . . . , a n ) where S ∈ S is an n-ary relation symbol, and a 1 , . . . , a n are elements of some fixed, countably infinite set const of constants. An S-instance I is a finite set of S-facts. The active domain adom(I) of I is the set of all constants that occur in the facts in I.
An S-query is semantically defined as a mapping q that associates with every S-instance I a set of answers q(I) ⊆ adom(I) n , where n ≥ 0 is the arity of q. If n = 0, then we say that q is Boolean and we write I |= q if () ∈ q(I).
We now introduce some concrete query languages. A conjunctive query (CQ) takes the form ∃y ϕ(x, y) where ϕ is a conjunction of relational atoms and x, y denote tuples of variables. The variables in x are called answer variables. Semantically, ∃y ϕ(x, y) denotes the query q(I) = {(a 1 , . . . , a n ) ∈ adom(I) n | I |= ϕ[a 1 , . . . , a n ]}.
A union of conjunctive queries (UCQ) is a disjunction of CQs with the same free variables. We now define disjunctive Datalog programs, see also (Eiter, Gottlob, and Mannila 1997). A disjunctive Datalog rule ρ has the form where n > 0 and m ≥ 0. 1 We refer to S 1 (x 1 ) ∨ · · · ∨ S m (x m ) as the head of ρ, and to R 1 (y 1 ) ∧ · · · ∧ R n (y n ) as the body. Every variable that occurs in the head of a rule ρ is required to also occur in the body of ρ. A disjunctive Datalog (DDLog) program Π is a finite set of disjunctive Datalog rules with a selected goal relation goal that does not occur in rule bodies and appears only in non-disjunctive goal rules goal(x) ← R 1 (x 1 ) ∧ · · · ∧ R n (x n ). The arity of Π is the arity of the goal relation. Relation symbols that occur in the head of at least one rule of Π are intensional (IDB) relations, and all remaining relation symbols in Π are extensional (EDB) relations. Note that, by definition, goal is an IDB relation. A DDLog program is called monadic or an MDDLog program if all its IDB relations except goal have arity at most one.
An S-instance, with S the set of all (IDB and EDB) relations in Π, is a model of Π if it satisfies all rules in Π. We use Mod(Π) to denote the set of all models of Π. Semantically, a DDLog program Π of arity n defines the following query over the schema S E that consists of the EDB relations of Π: for every S E -instance I, Π(I) = {a ∈ adom(I) n | goal(a) ∈ J for all J ∈ Mod(Π) with I ⊆ J}.
Let Π 1 , Π 2 be DDLog programs over the same EDB schema S E and of the same arity. We say that Π 1 is contained in Π 2 , written Π 1 ⊆ Π 2 , if for every S E -instance I, we have Π 1 (I) ⊆ Π 2 (I). Example 1. Consider the following MDDLog program Π 1 over EDB schema S E = {A, B, r}: Let Π 2 consist of the single rule goal(x) ← B(x). Then Π 1 ⊆ Π 2 is witnessed, for example, by the S E -instance I = {r(a, a), A(a)}. It is interesting to note that there is no tree-shaped S E -instance that can serve as a witness although all rule bodies in Π 1 and Π 2 are tree-shaped. In fact, a tree-shaped instance does not admit any answers to Π 1 because we can alternate A 1 and A 2 with the levels of the tree, avoiding to make goal true anywhere.
An MMSNP sentence over schema S E has the form ∃X 1 · · · ∃X n ∀x 1 · · · ∀x m ϕ with X 1 , . . . , X n monadic second-order variables, x 1 , . . . , x m first-order variables, and ϕ a conjunction of formulas of the form where each α i takes the form X i (x j ) or R(x) with R ∈ S E , and each β i takes the form X i (x j ). This presentation is syntactically different from, but semantically equivalent to the original definition from (Feder and Vardi 1998), which does not use the implication symbol and instead restricts the allowed polarities of atoms. An MMSNP sentence ϕ can serve as a Boolean query in the obvious way, that is, I |= ϕ whenever ϕ evaluates to true on the instance I. The containment problem in MMSNP coincides with logical implication. See (Bodirsky, Chen, and Feder 2012; Bodirsky and Dalmau 2013) for more information on MM-SNP.
It was shown in (Bienvenu et al. 2014) that the complement of an MMSNP sentence can be translated into an equivalent Boolean MDDLog program in polynomial time and vice versa. The involved complementation is irrelevant for the purposes of deciding containment since for any two Boolean queries q 1 , q 2 , we have q 1 ⊆ q 2 if and only if ¬q 1 ⊇ ¬q 2 . Consequently, any upper bound for containment in MDDLog also applies to MMSNP and so does any lower bound for containment between Boolean MDDLog programs. Example 2. Let S E = {r}, r binary. The complement of the MMSNP formula ∃R∃G∃B∀x∀y ψ over S E with ψ the conjunction of

MDDLog and MMSNP: Lower Bounds
The first main aim of this paper is to establish the following result. Point 3 closes an open problem from (Madelaine 2010).
Theorem 3. The following containment problems are 2NEXPTIME-complete: 1. of an MDDLog program in a CQ; 2. of an MDDLog program in an MDDLog program; 3. of two MMSNP sentences.
We prove the lower bounds by reduction of a tiling problem. It suffices to show that containment between a Boolean MDDLog program and a Boolean CQ is 2NEXPTIME-hard. A 2-exp square tiling problem is a triple P = (T, H, V) where • T = {T 1 , . . . , T p }, p ≥ 1, is a finite set of tile types; • H ⊆ T × T is a horizontal matching relation; . It is 2NEXPTIME-hard to decide, given a 2-exp square tiling problem P and an input w to P , whether there is a tiling for P and w.
For the reduction, let P be a 2-exp square tiling problem and w 0 an input to P of length n. We construct a Boolean MDDLog program Π and a Boolean CQ q such that Π ⊆ q iff there is a tiling for P and w 0 . To get a first intuition, assume that instances I have the form of a (potentially partial) 2 2 n × 2 2 n -grid in which the horizontal and vertical positions of grid nodes are identified by binary counters, described in more detail later on. We construct q such that I |= q iff I contains a counting defect, that is, if the counters in I are not properly incremented or assign multiple counter values to the same node. Π is constructed such that on instances I without counting defects, I |= Π iff the partial grid in I does not admit a tiling for P and w 0 . Note that this gives the desired result: if there is no tiling for P and w 0 , then an instance I that represents the full 2 2 n × 2 2 n -grid (without counting defects) shows Π ⊆ q; conversely, if there is a tiling for P and w 0 , then I |= q means that there is no counting defect in I and thus I |= Π.
We now detail the exact form of the grid and the counters. Some of the constants in the input instance serve as grid nodes in the 2 2 n × 2 2 n -grid while other constants serve different purposes described below. To identify the position of a grid node a, we use a binary counter whose value is stored at the 2 m leaves of a binary counting tree with root a and depth m := n + 1. The depth of counting trees is m instead of n because we need to store the horizontal position (first 2 n bits of the counter) as well as the vertical position (second 2 n bits). The binary relation r is used to connect successors. To distinguish left and right successors, every left successor a has an attached left navigation gadget r(a, a 1 ), r(a 1 , a 2 ), jump(a, a 2 ) and every right successor a has an attached right navigation gadget r(a, a 1 ), jump(a, a 1 )-these gadgets will be used in the formulation of the query q later on. If a grid node a 2 represents the right neighbor of grid node a 1 , then there is some node b such that r(a 1 , b), r(b, a 2 ). The node b is called a horizontal step node. Likewise, if a 2 represents the upper neighbor of a 1 , then there must also be some b with r(a 1 , b), r(b, a 2 ) and we call b a vertical step node. In addition, for each grid node a there must be a node c such that r(a, c), r(c, a) and we call c a self step node. We make sure that, just like grid nodes, all three types of step node have an attached counting tree. Figure 1 illustrates the representation of a single grid cell.
We need to make sure that counters are properly incremented when transitioning to right and upper neighbors via step nodes. To achieve this, each counting tree actually stores two counter values via monadic relations B 1 , B 1 (first value) and B 2 , B 2 (second value) at the leaves of the tree, where B i indicates bit value one and B i bit value zero. While the B 1 -value represents the actual position of the node in the grid, the B 2 -value is copied from the B 1 -values of its predecessor nodes (which must be identical). In fact, the query q to be defined later shall guarantee that (Q1) whenever r(a 1 , a 2 ) and a 1 is associated (via a counting tree) with B 1 -value k 1 and a 2 is associated with B 2value k 2 , then k 1 = k 2 ; (Q2) every node is associated (via counting trees) with at most one B 1 -value.
Between neighboring grid and step nodes, counter values are thus copied as described in (Q1) above, but not incremented. Incrementation takes place inside counting trees, as follows: at grid nodes and at self step nodes, the two values are identical; at horizontal (resp. vertical) step nodes, the B 1 -value is obtained from the B 2 -value by incrementing the horizontal part and keeping the vertical part (resp. incrementing the vertical part and keeping the horizontal part). We now construct the program Π. As the EDB schema, we use S E = {r, jump, B 1 , B 2 , B 1 , B 2 } where r and jump are binary and all other relations are monadic. We first define rules which verify that a grid or self step node has a proper counting tree attached to it (in which both counters are identical): We call a constant a of an instance I gactive if it has all required structures attached to serve as a grid node. Such constants are marked by the IDB relation gactive: We also want horizontal and vertical step nodes to be roots of the required counting trees. The difference to the counting trees below grid / self step nodes is that we need to increment the counters. This requires modifying the rules with head relation lev G i above. We only consider horizontal step nodes explicitly as vertical ones are very similar. The relations B 1 , B 1 and B 2 , B 2 give rise to a labeling of the leaf nodes that defines a word over the alphabet Σ = {0, 1} 2 where symbol (i, j) means that the bit encoded via B 1 , B 1 has value i and the bit encoded via B 2 , B 2 has value j. Ensuring that the B 1 -value is obtained by incrementation from the B 2 -value (least significant bit at the left-most leaf) then corresponds to enforcing that the leaf word is from the regular language L = (0, 1) * (1, 0)((0, 0) + (1, 1)) * . To achieve this, we consider the languages L 1 = (0, 1) * , L 2 = L, and L 3 = ((0, 0) + (1, 1)) * . Instead of level relations lev G i , we use relations lev H, i where ∈ {1, 2, 3} indicates that the leaf word of the subtree belongs to the language L : (1,2,2), (2, 3, 2), (3, 3, 3)}. We call a constant of an instance hactive if it is the root of a counting tree that implements incrementation of the horizontal position (left subtree of the root) and does not change the vertical position (right subtree of the root), identified by the IDB relation hactive: We omit the rules for the corresponding IDB relation vactive. Call the fragment of Π that we have constructed up to this point Π tree .
Recall that we want an instance to make Π true if it admits no tiling for P and w. We thus label all g-active nodes with a tile type: It then remains to trigger the goal relation whenever there is a defect in the tiling. Thus add for all The last kind of defect concerns the initial condition. Let w 0 = T i0 · · · T in−1 . It is tedious but not difficult to write rules which ensure that, for all i < n, every g-active element whose B 1 -value represents horizontal position i and vertical position 0 satisfies the monadic IDB relation pos i,0 . We then put for all j < n and all T ∈ T with T = T ij : We now turn to the definition of q; recall that we want it to achieve conditions (Q1) and (Q2) above. Due to the presence of self step nodes and since the counting trees below self step nodes and grid nodes must have identical values for the two counters, it can be verified that (Q1) implies (Q2). Therefore, we only need to achieve (Q1). We use as q a minor variation of a CQ constructed in (Björklund, Martens, and Schwentick 2008) for a similar purpose. We first constuct a UCQ and show in the appendix how to replace it with a CQ, which also involves some minor additions to the program Π tree above. The UCQ q makes essential use of the left and right navigation gadgets in counting trees. It uses a subquery q m (x, y) constructed such that x and y can only be mapped to corresponding leaves in successive counting trees, that is, (i) the roots of the trees are connected by the relation r and (ii) x can be reached from the root of the first tree by following the same sequence of left and right successors that one also needs to follow to reach y from the root of the second tree. To define q m (x, y), we inductively define queries q i (x, y) for all i ≤ m, starting with q 0 (x, y) = r(x 0 , y 0 ) and setting, for 0 < i ≤ m, The r-atom in q 0 corresponds to the move from the root of one counting tree to the root of a successive tree, the atoms r(x i−1 , x i ) and r(y i−1 , y i ) in q i correspond to moving down the i-th step in both trees, and the remaining atoms in q i make sure that both of these steps are to a left successor or to a right successor. We make essential use of the jump relation here, which shortcuts an edge on the path to the root for left successors, but not for right successors. Additional explanation is provided in the appendix. It is now easy to define the desired UCQ that achieves (Q1): Figure 4. Lemma 4. Π ⊆ q iff there is no tiling for P and w 0 .
This finishes the proof of the lower bounds stated in Theorem 3. Before proceeding, we note that the lower bound can be adapted to important rewritability questions. A query is FO-rewritable if there is an equivalent first-order query and (monadic) Datalog-rewritable if there is an equivalent (nondisjunctive) (monadic) Datalog query. FO-Rewritability of a query is desirable since it allows to use conventional SQL database systems for query answering, and likewise for Datalog-rewritability and Datalog engines. For this reason, FO-and Datalog-rewritability have received a lot of attention. For example, they have been studied for OMQs in (Bienvenu et al. 2014) and for CSPs in (Feder and Vardi 1998;Larose, Loten, and Tardif 2007). Monadic Datalog is an interesting target as it constitutes an extremely well-behaved fragment of Datalog. It is open whether the known decidability of FO-and (monadic) Datalog-rewritability generalizes from CSPs to MMSNP. We observe here that these problems are at least 2NEXPTIME-hard. The proof is by a simple modification of the reduction presented above. Theorem 5. For MDDLog programs and the complements of MMSNP sentences, rewritability into FO, into monadic Datalog, and into Datalog are 2NEXPTIME-hard.

MDDLog and MMSNP: Upper Bounds
The aim of this section is to establish the upper bounds stated in Theorem 3. It suffices to concentrate on MDDLog since the result for MMSNP follows. We first consider only Boolean MDDLog programs and then show how to extend the upper bound to MDDLog programs of any arity.
Our main algorithm is essentially the one described in (Feder and Vardi 1998). Since the constructions are described by Feder and Vardi only on an extremely high level of abstraction and without providing any analysis of the algorithm's running time, we give full details and proofs (in the appendix). The algorithm for deciding Π 1 ⊆ Π 2 proceeds in three steps. First, Π 1 and Π 2 are converted into a simplified form, then containment between the resulting programs Π S 1 and Π S 2 is reduced to a certain emptiness problem, and finally that problem is decided. A technical complication is posed by the fact that the construction of Π S 1 and Π S 2 does not preserve containment in a strict sense. In fact, Π 1 ⊆ Π 2 only implies Π S 1 ⊆ Π S 2 on instances of a certain minimum girth. To address this issue, we have to be careful about the girth in all three steps and can finally resolve the problem in the last step.
We now define the notion of girth. For an n-ary relation symbol S, pos(S) is {1, . . . , n}. A finite structure I has a cycle of length n if it contains distinct facts R 0 (a 0 ), . . . , R n−1 (a n−1 ), a i = a i,1 · · · a i,mi , and there are positions p i , p i ∈ pos(R i ), 0 ≤ i < n such that: The girth of I is the length of the shortest cycle in it and ∞ if I has no cycle (in which case we say that I is a tree).
Throughout the proof, we have to carefully analyze the running time of the algorithm, considering various measures for MDDLog programs. The size of an MDDLog program Π, denoted |Π|, is the number of symbols needed to write Π where relation and variable names are counted as having length one. The rule size of an MDDLog program is the maximum size of a rule in Π. The atom width (resp. variable width) of Π is the maximum number of atoms in any rule body (resp. variables in any rule) in Π.
From Unrestricted to Simple Programs An MDDLog program Π S is simple if it satisfies the following conditions: 1. every rule in Π S comprises at most one EDB atom and this atom contains all variables of the rule body, each variable exactly once; 2. rules without an EDB atom contain at most a single variable.
The conversion to simple form changes the EDB schema and thus the semantics of the involved queries, but it (almost) preserves containment, as detailed by the next theorem. The theorem is implicit in (Feder and Vardi 1998) and our contribution is to analyze the size of the constructed MDDLog programs and to provide detailed proofs. The same applies to the other theorems stated in this section.
Theorem 6. Let Π 1 , Π 2 be Boolean MDDLog programs over EDB schema S E . Then one can construct simple Boolean MDDLog programs Π S 1 , Π S 2 over EDB schema S E such that where w is the atom width of Π 1 ∪ Π 2 . Moreover, if r is the number of rules in Π 1 ∪ Π 2 and s the rule size, then 3. |Π S i | ≤ p(r · 2 s ); 4. the variable width of Π S i is bounded by that of Π i ; 5. |S E | ≤ p(r · 2 s ); where p is a polynomial. The construction takes time polynomial in |Π S 1 ∪ Π S 2 |. A detailed proof of Theorem 6 is given in the appendix. Here, we only sketch the construction, which consists of several steps. We concentrate on a single Boolean MDDLog program Π. In the first step, we extend Π with all rules that can be obtained from a rule in Π by consistently identifying variables. We then split up each rule in Π into multiple rules by introducing fresh IDB relations whenever this is possible. After this second step, we obtain a program which satisfies the following conditions: (i) all rule bodies are biconnected, that is, when any single variable is removed from the body (by deleting all atoms that contain it), then the resulting rule body is still connected; (ii) if R(x, . . . , x) occurs in a rule body with R EDB, then the body contains no other EDB atoms. In the final step, we transform every rule as follows: we replace all EDB atoms in the rule body by a single EDB atom that uses a fresh EDB relation which represents the conjunction of all atoms replaced. Additionally, we need to take care of implications between the new EDB relations, which gives rise to additional rules. The last step of the conversion is the most important one, and it is the reason for why we can only use instances of a certain girth in Point 2 of Theorem 6. Assume, for example, that, before the last step, the program had contained the following rules, where A and r are EDB relations: A new ternary EDB relation R q2 is introduced for the EDB body atoms of the lower rule, where q 2 = r(x 1 , x 2 ) ∧ r(x 2 , x 3 ) ∧ r(x 3 , x 1 ), and a new ternary EDB relation R q1 is introduced for the upper rule, q 1 = A(x 1 ) ∧ q 2 . Then the rules are replaced with Note that q 1 ⊆ q 2 , which results in two copies of the goal rule to be generated. To understand the issues with girth, consider the S E -instance I defined by R q1 (a, a , c ), R q1 (b, b , a ), R q1 (c, c , b ). The goal rules from the simplified program do not apply. But when translating into an S E -instance J in the obvious way, the goal rule of the original program does apply. The intuitive reason is that, when we translate J back to I, we get additional facts R q2 (a , b , c ), R q2 (b , c , a ), R q2 (c , a , b ) that are 'missed' in I. Such effects can only happen on instances whose girth is at most w, such as I.
From Containment to Relativized Emptiness A disjointness constraint is a rule of the form ⊥ ← P 1 (x) ∧ · · · ∧ P n (x) where all relations are of the same arity and at most unary. Let Π be a Boolean MDDLog program over EDB schema S E and D a set of disjointness constraints over S E . We say that Π is semi-simple w.r.t. D if Π is simple when all relations that occur in D are viewed as IDB relations. We say that Π is empty w.r.t. D if for all S E -instances I with I |= D, we have I |= Π. The problem of relativized emptiness is to decide, given a Boolean MDDLog program Π and a set of disjointness constraints D such that Π is semi-simple w.r.t. D, whether Π is empty w.r.t. D. Theorem 7. Let Π 1 , Π 2 be simple Boolean MDDLog programs over EDB schema S E . Then one can construct a Boolean MDDLog program Π over EDB schema S E and a set of disjointness constraints D over S E such that Π is semi-simple w.r.t. D and where v 1 is the variable width of Π 1 and S I,2 is the IDB schema of Π 2 . The construction takes time polynomial in |Π ∪ D|.
Note that, in Point 2 of Theorem 7, girth one instances are excluded.
To prove Theorem 7, let Π 1 , Π 2 be simple Boolean MDDLog programs over EDB schema S E . For i ∈ {1, 2}, let S I,i be the set of IDB relations in Π i with goal relations goal i ∈ S I,i and assume w.l.o.g. that S I,1 ∩ S I,2 = ∅. Set S E := S E ∪ S I,2 ∪ {P | P ∈ S I,2 }. The MDDLog program Π is constructed in two steps. We first add to Π every rule that can be obtained from a rule ρ in Π 1 by extending the rule body with • P (x) or P (x), for every variable x in ρ and every unary P ∈ S I,2 , and • P () or P () for every nullary P ∈ S I,2 ; for P = goal 2 , we always include P () but never P (). In the second step of the construction, we remove from Π every rule ρ whose body being true implies that a rule from Π 2 is violated, that is, there is a rule whose body is the CQ q(x) and with head P 1 (y 1 ) ∨ · · · ∨ P n (y n ) and a variable substitution σ such that 2 • σ(q) is a subset of the body of ρ and The goal relation of Π is goal 1 (). The set of disjointness constraints D then consists of all rules ⊥ ← P (x) ∧ P (x) for each unary P ∈ S I,2 and ⊥ ← P ()∧P () for each nullary 2 Of course, each yi consists of either zero or one variable. P ∈ S I,2 . It is not hard to verify that Π and D satisfy the size bounds from Theorem 7. We show in the appendix that Π satisfies Points 1 and 2 of Theorem 7.
Deciding Relativized Emptiness We now show how to decide emptiness of an MDDLog program Π w.r.t. a set of disjointness constraints D assuming that Π is semi-simple w.r.t. D. Theorem 8. Given a Boolean MDDLog program Π over EDB schema S E and a set of disjointness constraints D over Let Π be a Boolean MDDLog program over EDB schema S E and let D be a set of disjointness constraints over S E such that Π is semi-simple w.r.t. D. To prove Theorem 8, we show how to construct a finite set of S E -instances satisfying D such that Π is empty w.r.t. D if and only if it is empty in the constructed set of instances. Let S D be the set of all EDB relations that occur in D. For i ∈ {0, 1}, an i-type is a set t of i-ary relation symbols from S D such that t does not contain all EDB relations that co-occur in a disjointness rule in D. The 0-type of an instance I is the set θ of all nullary P ∈ S D with P () ∈ I. For each constant a of I, we use t a to denote the 1-type that a has in I, that is, t a contains all unary P ∈ S D with P (a) ∈ I.
We build an S E -instance K θ for each 0-type θ. The elements of K θ are exactly the 1-types and K θ consists of the following facts: • P (t) for each 1-type t and each P ∈ t; • R(t 1 , . . . , t n ) for each relation R ∈ S E \ S D and all 1types t 1 , . . . , t n ; • P () for each nullary P ∈ θ.
Note that, by construction, K θ is an S E -instance that satisfies all constraints in D. Lemma 9. Π is empty w.r.t. D iff K θ |= Π for all 0-types θ.
By Lemma 9, we can decide emptiness of Π by constructing all instances K θ and then checking whether K θ |= Π. The latter is done by guessing an extension K θ of K θ to the IDB relations in Π that does not contain the goal relation, and then verifying by an iteration over all possible homomorphisms from rule bodies in Π to K θ that all rules in Π are satisfied in K θ . Lemma 10. The algorithm for deciding relativized empti- We still have to address the girth restrictions in Theorems 6 and 7, which are not reflected in Theorem 8. In fact, it suffices to observe that relativized emptiness is independent of the girth of witnessing structures. This is made precise by the following result. Lemma 11. For every Boolean MDDLog program Π over EDB schema S E and set of disjointness constraints D over S E such that Π is semi-simple w.r.t. D, the following are equivalent for any g ≥ 0: 1. Π is empty regarding D and 2. Π is empty regarding D and instances of girth exceeding g. The proof of Lemma 11 uses a translation of semi-simple MDDLog programs with disjointness constraints into a constraint satisfaction problem (CSP) and invokes a combinatorial lemma by Feder and Vardi (and, originally, Erdős), to transform instances into instances of high girth while preserving certain homomorphisms.
Deriving Upper Bounds We exploit the results just obtained to derive upper complexity bounds, starting with Boolean MDDLog programs and MMSNP sentences. In the following theorem, note that for deciding Π 1 ⊆ Π 2 , the contribution of Π 2 to the complexity is exponentially larger than that of Π 1 . Theorem 12. Containment between Boolean MDDLog programs and between MMSNP sentences is in 2NEXPTIME. More precisely, for Boolean MDDLog programs Π 1 and Π 2 , it can be decided non-deterministically in time We now extend Theorem 12 to MDDLog programs of unrestricted arity. Since this is easier to do when constants can be used in place of variables in rules, we actually generalize Theorem 12 by allowing both constants in rules and unrestricted arity. For clarity, we speak about MDDLog c programs whenever we allow constants in rules. First, we show how to (Turing) reduce containment between MDDLog c programs of unrestricted arity to containment between Boolean MDDLog c programs. The idea essentially is to replace answer variables with fresh constants.
Let Π 1 , Π 2 be MDDLog c programs of arity k and let C be the set of constants in Π 1 ∪ Π 2 , extended with k fresh constants. We define Boolean MDDLog c programs Π a 1 , Π a 2 for each tuple a over C of arity k. If a = (a 1 , . . . , a k ), then Π a i is obtained from Π i by modifying each goal rule ρ = goal(x) ← q with x = (x 1 , . . . , x k ) as follows: • if there are i, j such that x i = x j and a i = a j , then discard ρ; • otherwise, replace ρ with goal() ← q where q is obtained from q by replacing each x i with a i . In the appendix, we show the following. Lemma 13. Π 1 ⊆ Π 2 iff Π a 1 ⊆ Π a 2 for all a ∈ C k . This provides the desired Turing reduction to the Boolean case, with constants. Note that the size of Π a i is bounded by that of Π i , and likewise for all other relevant measures. The number of required containment tests is bounded by 2 |Π1∪Π2| 2 , a factor that is absorbed by the bounds in Theorem 12.
It remains to reduce containment between Boolean MDDLog c programs to containment between Boolean MDDLog programs. The general idea is to replace constants with fresh monadic EDB relations. Of course, we have to be careful because the extension of these fresh relations in an instance need not be a singleton set. Let Π 1 , Π 2 be Boolean MDDLog c programs over EDB schema S E and let C be the set of constants in Π 1 ∪ Π 2 . The EDB schema S E is obtained by extending S E with a monadic relation R a for each a ∈ C. For i ∈ {1, 2}, the Boolean MDDLog program Π i over EDB schema S E contains all rules that can be obtained from a rule ρ from Π i by choosing a partial function δ that maps the terms (variables and constants) in ρ to the relations in S E \ S E such that each constant a is mapped to R a and then 1. replacing every occurrence of a term t ∈ dom(δ) in the body of ρ with a fresh variable and every occurrence of t in the head of ρ with one of the variables introduced for t in the rule body; 2. adding R a (x) to the rule body whenever some occurrence of a variable x 0 in the original rule has been replaced with x and δ(x 0 ) = R a .
For example, the rule P 1 (y) ∨ P 2 (y) ← r(x, y, y) ∧ s(y, z) in Π i gives rise, among others, to the following rule in Π i : The above rule treats the case where the variable x from the original rule is mapped to the constant a 1 , y to a 2 , and z not to any constant in C. Note that the original variables x and y have been duplicated because R a1 and R a2 need not be singletons while a 1 and a 2 denote a single object. So intuitively, Π i treats its input instance I as if it was the quotient I of I obtained by identifying all a 1 , a 2 with It can be verified that |Π i | ≤ 2 |Π i | 2 and that the rule size of Π i is bounded by twice the rule size of Π i . Because of the latter, the simplification of the programs Π i according to Theorem 6 yields programs whose size is still bounded by 2 p(|Πi|) , as in the proof of Theorem 12, and whose variable width is bounded by twice the variable width of Π i . It is thus easy to check that we obtain the same overall bounds as stated in Theorem 12.

Ontology-Mediated Queries
We now consider containment between ontology-mediated queries based on description logics, which we introduce next.
An ontology-mediated query (OMQ) over a schema S E is a triple (T , S E , q), where T is a TBox formulated in a description logic and q is a query over the schema S E ∪sig(T ), with sig(T ) the set of relation symbols used in T . The TBox can introduce symbols that are not in S E , which allows it to enrich the schema of the query q. As the TBox language, we use the description logic ALC, its extension ALCI with inverse roles, and the further extension SHI of ALCI with transitive roles and role hierarchies. Since all these logics admit only unary and binary relations, we assume that these are the only allowed arities in schemas throughout the section. As the actual query language, we use UCQs and CQs. The OMQ languages that these choices give rise to are denoted with (ALC, UCQ), (ALCI, UCQ), (SHI, UCQ), and so on. In OMQs (T , S E , q) from (SHI, UCQ), we disallow superroles of transitive roles in q; it is known that allowing transitive roles in the query poses serious additional complications, which are outside the scope of this paper, see e.g. (Bienvenu et al. 2010;Gottlob, Pieris, and Tendera 2013). The semantics of an OMQ is given in terms of certain answers. We refer to the appendix for further details and only give an example of an OMQ from (ALC, UCQ). Example 16. Let the OMQ Q = (T , S E , q) be given by the only certain answer to Q is e 1 . Let if for every S E -instance I, the certain answers to Q 1 on I are a subset of the certain answers to Q 2 on I. The query containment problems between OMQs considered in (Bienvenu, Lutz, and Wolter 2012) are closely related to ours, but concern different (weaker) OMQ languages. One difference in setup is that, there, the definition of "contained in" does not refer to all S E -instances I, but only to those that are consistent with both T 1 and T 2 . Our results apply to both notions of consistency. In fact, we show in the appendix that consistent containment between OMQs can be reduced in polynomial time to unrestricted containment as studied in this paper, and in our lower bound we use TBoxes that are consistent w.r.t. all instances. We use |T | and |q| to denote the size of a TBox T and a query q, defined as for MDDLog programs.
We start with the lower bounds. For Point 1 and 2 of Theorem 17, we make use of the lower bound that we have already obtained for MDDLog. It was observed in (Bienvenu et al. 2013;Bienvenu et al. 2014) that both (ALC, UCQ) and (SHI, UCQ) have the same expressive power as MDDLog restricted to unary and binary EDB relations. In fact, every such MDDLog program can be translated into an equivalent OMQ from (ALC, UCQ) in polynomial time. Thus, the lower bounds in Point 1 and 2 of Theorem 17 are a consequence of those in Theorem 3.
The lower bound stated in Point 3 of Theorem 17 is proved by a non-trivial reduction of the 2-exp torus tiling problem. Compared to the reduction that we have used for MDDLog, some major changes are required. In particular, the queries used there do not seem to be suitable for this case, and thus we replace them by a different set of queries originally introduced in (Lutz 2008). Details are in the appendix. It can be shown exactly as in the proof of Theorem 3 in (Bienvenu, Lutz, and Wolter 2012) that, in the lower bounds in Points 2 and 3, we can assume the TBoxes of the two OMQs to be identical.
We note in passing that we again obtain corresponding lower bounds for rewritability.
Theorem 18. In (ALC, UCQ) and (ALCI, CQ), rewritability into FO, into monadic Datalog, and into Datalog is 2NEXPTIME-hard. Now for the upper bounds in Theorem 17. The translation of OMQs into MDDLog programs is more involved than the converse direction, a naive attempt resulting in an MDDLog program with existential quantifiers in the rule heads. We next analyze the blowups involved. The construction used in the proof of the following theorem is a refinement of a construction from (Bienvenu et al. 2013), resulting in improved bounds.
We now use Theorem 19 to derive an upper complexity bound for containment in (SHI, UCQ). While there are double exponential blowups both in Theorem 15 and in Theorem 19, a careful analysis reveals that they do not add up and, overall, still give rise to a 2NEXPTIME upper bound. In contrast to Theorem 12, though, we only get an algorithm whose running time is double exponential in both inputs (T 1 , S E , q 1 ) and (T 2 , S E , q 2 ). However, it is double exponential only in the size of the actual queries q 1 and q 2 while being only single exponential in the size of the TBoxes T 1 and T 2 . This is good news since the size of q 1 and q 2 is typically very small compared to the sizes of T 1 and T 2 . For this reason, it can even be reasonable to assume that the sizes of q 1 and q 2 are constant, in the same way in which the size of the query is assumed to be constant in classical data complexity. Note that, under this assumption, we obtain a NEXPTIME upper bound for containment.

Outlook
There are several interesting questions left open. One is whether decidability of containment in MMSNP generalizes to GMSNP, where IDB relations can have any arity and rules must be frontier-guarded (Bienvenu et al. 2014) or even to frontier-guarded disjunctive TGDs, which are the extension of GMSNP with existential quantification in the rule head (Bourhis, Morak, and Pieris 2013). We remark that an extension of Theorem 19 to frontier-one disjunctive TGDs (where rule body and head share only a single variable) seems not too hard.
Other open problems concern containment between OMQs. In particular, it would be good to know the complexity of containment in (ALC, CQ) which must lie between NEXPTIME and 2NEXPTIME. Note that our first lower bound crucially relies on unions of conjunctive queries to be evailable, and the second one on inverse roles. It is known that adding inverse roles to ALC tends to increase the complexity of querying-related problems (Lutz 2008), so the complexity of containment in (ALC, CQ) might indeed be lower than 2NEXPTIME. It would also be interesting to study containment for OMQs from (ALCI, UCQ) where the actual query is connected and has at least one answer variable. In the case of query answering, such a (practically very relevant) assumption causes the complexity to drop (Lutz 2008). Is this also the case for containment?

MDDLog Hardness: Missing Details
We first repeat the details of the construction of a UCQ which achieves (Q1) along with additional information, then prove Lemma 4, and subsequently describe how the UCQ can be replaced by a CQ. Finally, we prove Theorem 5. Since the constructed queries will make use of the counting gadgets in counting trees, we show these gadgets again in Figure 3. There, a is a node in a counting tree, b is its left successor, and c is its right successor.
To define the UCQ that achieves (Q1), set q 0 (x, y) = r(x 0 , y 0 ) and, for 0 < i ≤ m, The idea is that I |= q m [a, b] if a and b are leafs in successive counting trees that are at the same leaf position, that is, (i) the roots of the trees are connected by the relation r and (ii) a can be reached from the root of the first tree by following the same sequence of left and right successors that one also needs to follow to reach b from the root of the second tree. In fact, the r-atom in q 0 corresponds to the move from the root of one counting tree to the root of a successive tree, the atoms r(x i−1 , x i ) and r(y i−1 , y i ) in q i correspond to moving down the i-th step in both trees, and the remaining atoms in q i make sure that both of these steps are to a left successor or to a right successor.
To understand the latter, note that jump is the relation used in the navigation gadgets attached to tree nodes. The variable z i,i+2 can only be mapped to the target of the jump relation in the navigation gadget at x i , and likewise for z i,i+3 and the target of the jump relation in the navigation gadget at y i . Note that there must be a z i,0 from which z i,i+2 can be reached along an r-path of length i + 2 and from which z i,i+3 can be reached along an r-path of length i + 3. If x i and y i are both left successors, then this z i,0 is the root of the first counting tree. If x i and y i are both right successors, then z i,0 is the r-predecessor of the root of the first counting tree, which must exist at all relevant nodes: at grid nodes because of the self step nodes and at horizontal/vertical step nodes because they have a grid node as r-predecessor. If x i is a left successor and y i a right successor or vice versa, then there is no target for z i,0 because this target would have to reach the root of the first counting tree on a path of length one and on a path of length zero, but there is no reflexive loop at the root of counting trees (only a length two loop via self step nodes).
It is now easy to define the desired UCQ: The first CQ in this UCQ is displayed in Figure 4. As required, it evaluates to true on an instance if there are successive counting trees (whose roots have an r-predecessor and) which contain two leafs at the same position that are labeled differently regarding B 1 , B 1 and B 2 , B 2 . This finishes the construction for the case of UCQs. We first establish correctness and then show how to replace the UCQ with a CQ.
Lemma 4. Π ⊆ q iff there is no tiling for P and w 0 .
Proof.(sketch) Assume first that there is no tiling for P and w 0 . Let I be the instance that represents the 2 2 n × 2 2 n -grid with counting trees in the way described above. It can be verified that I |= q. We aim to show that I |= Π and thus I witnesses Π ⊆ q. Assume to the contrary that I |= Π. Then there is an extension J of I that satisfies all rules in Π, but does not contain goal(). In particular, J must contain at least one atom T i (c) for each constant c with gactive(c) ∈ J, thus we can choose a concrete T i (c) for each such c. Since none of the goal rules in Π applies, these chosen atoms must represent a tiling for P and w 0 . We have thus obtained a contradiction to the assumption that no such tiling exists. Now assume that there is a tiling f for P and w 0 . Take an instance I with I |= Π. Assume to the contrary of what is to be shown that I |= q. Then I satisfies Conditions (Q1) and (Q2). Extend I to a new instance J as follows. Since I satisfies (Q2), every g-active constant c in I is associated with a unique counter value, thus with a unique horizontal position x ∈ {0, . . . , 2 2 n − 1} and a unique vertical position y ∈ {0, . . . , 2 2 n − 1}. Include T i (c) ∈ J if f (x, y) = T i and then exhaustively apply all non-disjunctive rules from Π tree . One can verify that J satisfies all rules in Π while making the goal relation false, in contradiction to I |= Π. In particular, satisfaction of (Q1) and the way in which we have added facts T i (c) to J imply that none of the goal rules that check for a tiling defect applies. J To replace the UCQ q by a CQ, we again use a coding trick from (Björklund, Martens, and Schwentick 2008). The basic idea is to replace B 1 , B 1 and B 2 , B 2 with suitable bit gadgets and then to use a construction that is very similar to the one used above for ensuring that we consistenly follow left successors or right successors in corresponding steps of the navigation in the two involved trees. We replace B 1 (x) with the following bit one gadget: where jump 1 is a fresh EDB relation and B 1 (x) with the following bit zero gadget: B 2 and B 2 are replaced with corresponding gadgets in which only jump 1 is replaced with jump 2 . The existence of these bit gadgets needs to be verified in the rules of Π tree that ensure the existence of counting trees. In addition to that, we require one further modification to Π tree : the self step loops of length two at each grid node are replaced with self step nodes of length four. All three intermediate nodes on these loops behave exactly like a self step node before. We then replace the above UCQ by q = ∃x m ∃y m ∃z 0 · · · ∃z m+2 ∃z 1 · · · ∃z m+5 q m (x m , y m ) ∧ jump 1 (x m , z m+2 ) ∧ jump 2 (y m , z m+5 ) ∧ r(z 0 , z 1 ) ∧ · · · ∧ r(z m+1 , z m+2 ) ∧ r(z 0 , z 1 ) ∧ r(z 1 , z 2 ) ∧ · · · ∧ r(z m+4 , z m+5 ) Note that the x m and y m must be leafs in successive counting trees with the same leaf position. Additionally, the variable z m+2 can only be mapped to a target of the jump 1 relation in the bit gadget at x m , and likewise for z m+5 and a target of the jump 2 relation in the bit gadget at y m . There must also be a z 0 from which z m+2 can be reached along an r-path of length m + 2 and from which z m+5 can be reached along an r-path of length m + 5 (thus the difference in lengths is three). If the bit value at x m is zero and the bit value at y m is one, then this z 0 is the root of the first counting tree. If the bit value at x m is one and the bit value at y m is zero, the we can use for z 0 an r-predecessor of the root of the first counting tree. It can be verified that when the bit values at x m and y m are identical, then the possible target for z 0 must have r-paths to the root of the first counting tree of length i and j steps, for some However, since we have extended the length of self loops at grid nodes from two to four, there is no such target. This finishes the construction of the CQ q and establishes the lower bounds stated in Theorem 3.
We now come to the proof of Theorem 5.
Theorem 5. For MDDLog programs and the complements of MMSNP sentences, rewritability into FO, into monadic Datalog, and into Datalog are 2NEXPTIME-hard.
Proof.It suffices to consider Boolean MDDLog programs. First note that, by Rossman's theorem, any such program that is rewritable into FO is rewritable into a UCQ. Consequently, FO-rewritability implies monadic Datalogrewritability implies Datalog-rewritability. Based on this observation, we deal with all three kinds of rewritability in a single proof: we show that from a 2-exp square tiling problem P and an input w 0 to P , we can construct in polynomial time a Boolean MDDLog program Π such that 1. if there is a tiling for P and w 0 , then Π is FO-rewritable; 2. if there is no tiling for P and w 0 , then Π is not Datalogrewritable. Reconsider the reduction of the 2-exp square tiling problem to MDDLog containment given above. Given a 2-exp square tiling problem P and an input w 0 to P , we have shown how to construct a Boolean MDDLog program Π and a Boolean CQ q such that Π ⊆ q iff there is a tiling for P and w 0 . Let S E be the EDB schema of Π and q. To obtain the desired program Π , we modify Π as follows: 1. in every goal rule, change the head to A(x); 2. add goal() ← q, where s is a fresh EDB relation and A, R, G, B are IDB relations. Let S E = S E ∪ {s}. We now show that Π satisfies Points 1 and 2 above. For Point 1, assume that there is a tiling for P and w 0 . Then Π ⊆ q. We claim that q is a rewriting of Π . By construction of Π , I |= q clearly implies I |= Π for all S Einstances I. For the converse, let I |= Π . First assume I |= Π. Then there is an extension J of I to the IDB relations in Π such that the extension of A is empty. Consequently, we must have I |= Π because I |= q and we are done. Now assume I |= Π. Since Π ⊆ q, this implies I |= q as desired.
For Point 2, assume there is no tiling for P and w 0 . Then Π ⊆ q. Given an undirected graph G = (V, E), let the instance I + G be defined as the disjoint union of the instance I 0 which represents the 2 2 n -grid plus counting gadgets and the instance I G that contains the fact s(v 1 , v 2 ) for every Since there is no tiling for P and w 0 , we have I 0 |= Π and thus I + G |= Π. By construction of Π and since Π |= q, this implies that I G |= Π iff G is not 3-colorable. Assume to the contrary of what is to be shown that there is a Datalogrewriting Γ of Π . It is not difficult to modify Γ so that its EDB schema is S E = {s} and on any S E -instance I G representing an undirected graph G, the modified program Γ yields the same result that Γ yields on I + G . We only sketch the idea: for every n-ary IDB relation S of Γ, all sets of positions P = {i 1 , . . . , i k } ⊆ {1, . . . , n}, and all tuples t = (d 1 , . . . , d k ) of elements of I 0 , introduce a fresh n − kary IDB S P,t . Intuitively, S P,t is used to represent facts S(d 1 , . . . , d k ) where every position i j ∈ P is mapped to the element d j (which is not part of the input instance) and every position that is not in P is mapped to an element of the input instance I G . It remains to introduce additional versions of each rule that use the new predicates, in all possible combinations.
We have thus shown that non-3-colorability of graphs can be expressed in Datalog, which is not the case (Afrati et al. 1995). J

MDDLog Upper Bound: Missing Details
From Unrestricted to Simple Programs Theorem 6. Let Π 1 , Π 2 be Boolean MDDLog programs over EDB schema S E . Then one can construct simple Boolean MDDLog programs Π S 1 , Π S 2 over EDB schema S E such that 1.
Moreover, if r is the number of rules in Π 1 ∪ Π 2 and s the rule size, then 3. |Π S i | ≤ p(r · 2 s ); 4. the variable width of Π S i is bounded by that of Π i ; 5. |S E | ≤ p(r · 2 s ); where p is a polynomial. The construction takes time polynomial in |Π S 1 ∪ Π S 2 |. To prove Theorem 6, we first concentrate on a single Boolean MDDLog program Π over EDB schema S E . We first construct from Π an equivalent MDDLog program Π such that the following conditions are satisfied: (i) all rule bodies are biconnected, that is, when any single variable is removed from the body (by deleting all atoms that contain it), then the resulting rule body is still connected; (ii) if R(x, . . . , x) occurs in a rule body with R EDB, then the body contains no other EDB atoms. To construct Π , we first extend Π with all rules that can be obtained from a rule in Π by consistently identifying variables and then exhaustively apply the following rules: • replace every rule p(y) ← q 1 (x 1 ) ∧ q 2 (x 2 ) where x 1 and x 2 share exactly one variable x but both contain also other variables with the rules p 1 (y 1 ) ∨ Q(x) ← q 1 (x 1 ) and p 2 (y 2 ) ← Q(x) ∧ q 2 (x 2 ), where Q is a fresh monadic IDB relation and p i (y i ) is the restriction of p(y) to atoms that are nullary or contain a variable from q i , i ∈ {1, 2}; • replace every rule p(y) ← q 1 (x 1 ) ∧ q 2 (x 2 ) where x 1 and x 2 share no variables and are both non-empty with the rules p 1 (y 1 )∨Q() ← q 1 (x 1 ) and p 2 (y 2 ) ← Q()∧q 2 (x 2 ), where Q() is a fresh nullary IDB relation and the p i (y i ) are as above; • replace every rule p(y) ← R(x, . . . , x) ∧ q(x) where R is an EDB relation and q contains at least one EDB atom and the variable x, with the rules Q(x) ← R(x, . . . , x) and p(y) ← Q(x) ∧ q(x), where Q is a fresh monadic IDB relation.
It is easy to see that the program Π is equivalent to the original program Π. We next construct from Π the desired simplification Π S of Π. The intuition is that in every rule of Π , we replace all EDB atoms in the rule body by a single EDB atom that uses a fresh EDB relation which represents the conjunction of all atoms replaced. We also need to take care of implications between the new EDB relations. In the following, we make the construction precise. For every conjunctive query q(x) and schema S, we use q(x)| S to denote the restriction of q(x) to S-atoms. The EDB schema S E of Π S consists of the relations R q(x)| S E , p(y) ← q(x) a rule in Π ; the arity of R q(x)| S E is the number of variables in q(x) (equivalently: in q(x)| S E ).
Let S I be the IDB schema of Π . The program Π S consists of the following rules: ( * ) whenever p(y) ← q 1 (x 1 ) is a rule in Π , R q2(x2) an EDB relation in S E , and h : x 1 → x 2 an injective homomorphism from q 1 (x 1 ) to q 2 (x 2 ), then Π S contains the rule ) denotes the result of replacing in R q2 (x 2 ) every variable x with y if x = h(y) and every variable that does not occur in the range of h with a fresh variable. The case where q 1 (x 1 ) is identical to q 2 (x 2 ) and h is the identity corresponds to adapting rules in Π to the new EDB signature and the other cases take care of implications between EDB relations, as announced. The last step of the conversion just described is the most important one, and it is the reason for why we can only use instances of a certain girth in Point 2 of Theorem 6. An example illustarting this step and the issue with girth can be found in the main part of the paper. We next analyze the size of the constructed program Π S . Lemma 21. Let r be the number of rules in Π and s the rule size of Π. Then there is a polynomial p such that 1. |Π S | ≤ p(r · 2 s ); 2. the variable width of Π S is bounded by that of Π; 3. |S E | ≤ p(r · 2 s ).
Proof.We start with Point 1. Let r be the number of rules in Π, v the variable width, and w the atom width. Regarding the size of Π S , note that the first (identification) step replaces each rule of Π with at most k! rules, where k is the number of variables in the original rule. After this step, we thus have at most r·v! rules. The subsequent rewriting in the construction of Π splits each rule into at most one rule per atom in the original rule. The number of rules in Π is thus bounded by r · v! · w. The number of rules in Π S is clearly at most quadratic in the number of rules in Π , thus their number is bounded by (r · v! · w) 2 . None of the steps increases the rule size, i.e., the rule size of Π S is bounded by the rule size of Π. This yields the bound stated in Point 1.
Point 2 is very easy to verify by analyzing the construction of Π S .
For Point 3, note that the program Π has the same EDB schema as Π. In the construction of Π S , the number of EDB relations is bounded by the number of rules in Π , thus by r · v! · w. J So far, we have concentrated on a single program. To obtain Theorem 6, we have to jointly simplify that two involved programs Π 1 and Π 2 . This only means that, when constructing Π S i from Π i in the second step of the normalization procedure, then we use the set of EDB relations introduced for both Π 1 and Π 2 instead of only those for Π i . The bounds in Lemma 21 then cleary give rise to those in Theorem 6. It remains to show that the joint simplification Π S 1 , Π S 2 of Π 1 , Π 2 behaves as expected regarding containment.
Proof.It is obvious that the construction of the program Π i from Π i preserves equivalence. We can therefore assume that the programs Π 1 and Π 2 in Lemma 22 are in fact the programs Π 1 and Π 2 . For i ∈ {1, 2}, let S I,i be the IDBschema of Π i (and thus also of Π S i ), and let goal i be the goal relation of Π i .
For Point 1, let I be an S E -instance such that I |= Π 1 and I |= Π 2 . Let J be the S E -instance that consists of all facts R q (a 1 , . . . , a n ) such that I |= q[a 1 , . . . , a n ]. It remains to show that J |= Π S 1 and J |= Π S 2 . For J |= Π S 1 , assume to the contrary of what is to be shown that there is an extension J of J to schema S E ∪S I,1 that satisfies all rules of Π S i and does not contain the goal 1 relation. Let I be the corresponding extension of I, that is, I extends I with the S I,1 -facts from J . It suffices to show that J satisfies all rules in Π 1 to obtain a contradiction against I |= Π 1 . Thus, let p(y) ← q(x) be a rule in Π 1 and let h be a homomorphism from q(x) to I . Then Π S 1 contains the rule p(y) ← R q(x)| S E (x) ∧ q(x)| S I 1 . By construction of J and I , h is also a homomorphism from R q(x)| S E (x) ∧ q(x)| S I 1 to J . Since J satisfies all rules of Π S 1 , one of the disjuncts of p(y) is satisfied under h, as required.
For J |= Π S 2 , let I be an extension of I to S E ∪ S I,2 that satisfies all rules of Π 2 and does not contain the goal 2 relation. Let J be the corresponding extension of J. It suffices to show that J satisfies all rules of Π S 2 . Thus, let p(y) ← q(x) be a rule in Π S 2 and let h be a homomorphism from q(x) to J . Then there is a rule p(y) ← q (x ) in Π 2 , a relation R q (x ) in S E , and an injective homomorphism g from q (x ) to q (x ) such that q(x) = g −1 (R q (x ) (x ))∧ q (x )| S I 2 . By construction of J and J , h is also a homomorphism from q (x ) to I. Since I satisfies p(y) ← q (x ), one of the disjuncts of p(y) is satisfied under h, as required. Now for Point 2. Let I be an S E -instance of girth exceeding w such that I |= Π S 1 and I |= Π S 2 . Let J be the S E -instance that consists of all facts r(a i1 , . . . , a i k ) such that for some fact R q(x1,...,xn) (a 1 , . . . , a n ), we have r(x i1 , . . . , x i k ) ∈ q. We show that J |= Π 1 and J |= Π 2 .
For J |= Π 1 , assume to the contrary of what is to be shown that there is an extension J of J to schema S E ∪S I,1 such that all rules of Π 1 are satisfied and goal 1 / ∈ J . Let I be the corresponding extension of I to S E ∪ S I,1 . It suffices to show that all rules of Π S 1 are satisfied in I to obtain a contradiction against I |= Π S 1 . Thus, let p(y) ← q(x) be a rule in Π S 1 and let h be a homomorphism from q(x) to I . Then there is a rule p(y) ← q (x ) in Π 1 , a relation R q (x ) in S E , and an injective homomorphism g from q (x ) to q (x ) such that q(x) = g −1 (R q (x ) (x )) ∧ q (x )| S I 2 . By construction of J and I , h is also a homomorphism from q (x ) to I. Since J satisfies p(y) ← q (x ), one of the disjuncts of p(y) is satisfied under h, as required.
For J |= Π 2 , let I be an extension of I to S E ∪ S I,2 that satisfies all rules of Π S 2 and does not contain the goal 2 relation. Let J be the corresponding extension of J. It suffices to show that J satisfies all rules of Π 2 . Thus, let p(y) ← q(x) be a rule in Π 2 and let h be a homomorphism from q(x) to J . Let the query q (x ) be obtained from q(x) by identifying all variables that h maps to the same target. For simplicity, let us assume first that q is connected.
Partition the EDB atoms of q (x ) into components as follows: every reflexive atom r(x, . . . , x) forms a component and every maximal biconnected set of non-reflexive atoms forms a component. Let q 1 (x 1 ), . . . , q n (x n ) be the components obtained in this way, enriched with IDB atoms in the following way: if P (x) is in q(x) with P IDB and x occurs in q i (x i ), then q i (x i ) contains P (x). It can be verified that distinct components share at most one variable and that the undirected graph obtained by taking the non-reflexive components as nodes and putting edges between components that share a variable is a tree. For ech tree in the tree, choose a component that is the root to turn the undirected tree into a directed one, allowing us to speak about successors, predecessors, etc. Slightly extend the tree by adding each reflexive component as a leaf below some node that contains the variable in the reflexive component; if there is no such node, the component forms an extra tree.
For every component q i (x i ), Π 2 contains an associated rule. Recall that we assume Π 2 to be the result of the first step of the construction of Π S 2 . If the q i (x i ) is a leaf in the tree, then the associated rule takes the form is the restriction of p(y) to atoms that are nullary or contain a variable from x i , Q i is a fresh unary relation, and x i is the variable that the component shares with the component which is its predecessor in the tree. For non-leafs, the rule body is additionally enriched with atoms Q j (x) where Q j is a fresh IDB introduced for a successor node. For the root node, no fresh IDB relation is introduced.
We now make a bottom-up pass over the tree as follows. Consider the rule p i (y i ) ← q i (x i ) associated with the current node. The homomorphism h from above is also a homomorphism from q i (x i ) to J ; this is clear for leaf nodes and can inductively be verified for inner nodes. Take the corresponding rule ρ in Π S 2 , the one that introduces a new EDB relation for the EDB atoms in q i (x i ). By construction of J , since q i (x i ) is biconnected without reflexive loops or a single reflexive loop and because the girth of I is higher than that of q i (x i ), the h-image of all EDB-atoms in q i (x i ) must have been derived from a single fact in I. There is another rule ρ in Π S 2 in which the EDB-relation in the body of ρ is replaced with the relation from that fact. This rule applies in I and thus one of the atoms from its head is true. If this is an atom from p(x), we are done with the entire proof. If this is a fresh IDB atom, we are done with this tree node and can continue in our bottom-up tree walk. We will be done at the root at latest since the associated rule contains no fresh IDB relation.
This finishes the case where the query q (x ) is connected. the general case, the tree has to be replaced by a forest. There will be exactly one tree in the forest in which the rule associated with the root does not have a fresh IDB relation in the head. For those trees where the root rule has a fresh such relation, we find another tree where that relation occurs in the body of the rule associated with a leaf. This defines an order on the trees, which is acyclic. We process the trees in this order, each single tree essentially as in the connected case. J From Containment to Relativized Emptiness Lemma 23. For any g > 0, Proof.For Point 1, assume Π 1 ⊆ Π 2 . Then there is an S E -instance I such that I |= Π 1 and I |= Π 2 . Let J be an extension of I to signature S E ∪S I,2 such that all rules in Π 2 are satisfied and goal 2 () / ∈ J. Add P (a) to J if P (a) / ∈ J for all unary P ∈ S I,2 and a ∈ adom (J), and add P () to J if P () / ∈ J for all nullary P ∈ S I,2 . Clearly, (the extended) J is over schema S E and satisfies D. To show that Π is non-empty w.r.t. D, it thus remains to argue that J |= Π.
Assume to the contrary that this is not the case. Then there is an extension J of J to signature S E ∪ S I,1 such that all rules of Π are satisfied, but goal 1 () / ∈ J . Since the restriction of J to S E -facts is I, it remains to argue that J satisfies all rules in Π 1 . Let ρp(y) ←= q(x) be such a rule and let h be a homomorphism from q to J . We define an extension q of q as follows: conjunctively add to q all P () ∈ J ∩ S I,2 and all P () ∈ J with P ∈ S I,2 ; moreover, for all variables x in q and all facts P (h(x)) ∈ J with P ∈ S I,2 , conjunctively add the atom P (x) to q, and likewise for facts P (h(x)) and atoms P (x). Since J satisfies all rules in Π 2 , it can be verified that the rule p(y) ← q (x), which is added to Π in the first step of its construction, is not removed in the second step of the construction. Since h is a homomorphism from q to J and J satisfies all rules in Π, J |= p[h(y)] and thus J satifies ρ as required. Now for Point 2. Assume that Π is non-empty w.r.t. D on instances of girth > g, with g > 0. Then there is an S E -instance I of girth > g with I |= Π and I |= D. By construction of Π, this implies that (i) P () ∈ I or P () ∈ I for every nullary P ∈ S I,2 (otherwise no rule of Π would be applicable, implying I |= Π). Moreover, we can assume w.l.o.g. that (ii) every a ∈ adom(I) satisfies P (a) ∈ I or P (a) ∈ I for every unary P ∈ S I,2 ; in fact, it this is not the case, then we can simply replace I with its restriction to those elements a that satisfy the condition (elements which do not can never be involved in rule applications). Let J be the restriction of I to schema S E . By construction of Π and due to Conditions (i) and (ii), I |= Π implies J |= Π 1 . To finish the proof, it would this be sufficient to show that I witnesses J |= Π 2 . This, however, need not be the case: while we know that goal 2 () ∈ I as otherwise no rule of Π would be applicable, it need not be the case that all rules in Π 2 are satisfied in I. We thus show how to first manipulate I such that I |= Π still holds, I does still not contain goal 2 (), and I satisfies all rules in Π 2 . In fact, we exhaustively apply the following.
Assume that there is a rule ρ in Π 2 that is not satisfied in I. Since Π 2 is simple, ρ has the form Q 1 (y 1 ) ∨ · · · ∨ Q (y ) ← A(x) ∧ P 1 (x 1 ) ∧ · · · ∧ P k (x k ) with A EDB and all P i and Q i IDB. Let h be a homomorphism from the rule body to I such that Q i (h(y i )) / ∈ I for 1 ≤ i ≤ . We modify I by removing the fact A(h(x)), resulting in instance I − . Clearly, the application of ρ via h is no longer possible and it remains to show that I − |= Π. Assume that this is not the case, that is, there is an extension J − of I − to schema S E ∪ S I,1 such that goal 1 () / ∈ J − and J − satisfies all rules of Π. Let J be the corresponding extension of I, that is, J and J − differ only in the presence of the fact A(h(x)). We show that J satisfies all rules of Π, contradicting I |= Π. Clearly, we need to consider only rules ρ whose only S E -atom is of the form A(x ) and only homomorphisms h from the body of ρ to J such that h(x ) = h(x). Fix such a ρ and h . Since I and thus also J has girth > 1 and since x contains all variables from the body of ρ , h must be injective. By definition of Π and because of the homomorphism h , we must have • P () ∈ J (resp. P () ∈ J) implies that the body of ρ has a conjunct P () (resp. P ) for every nullary P ∈ S I,2 ; • P (h (x)) ∈ J (resp. P (h (x)) ∈ J) implies that the body of ρ has a conjunct P (x) (resp. P (x)) for unary P ∈ S I,2 and all variables x from x .
Because of the homomorphism h and since Q i (h(y i )) / ∈ I for 1 ≤ i ≤ , the rule ρ ∈ Π 2 and the variable substitution h•h −1 mean that the rule ρ was removed during the second step of the construction of Π, in contradiction to ρ ∈ Π. J
Proof.Clearly, K θ |= Π means that K θ is a witness for Π being non-empty w.r.t. D. Conversely, assume that there is an S E -instance I with I |= D and I |= Π. Let θ be the 0type of I. Then the mapping h defined by setting h(a) = t a for all constants a in I is a homomorphism from I to K θ . It is well-known (and can be proved using a disjunctive version of the chase procedure) that truth of MDDLog queries is preserved under homomorphisms, thus I |= Π implies K θ |= Π. Proof.Let us first analyze the time that it takes to check whether K θ |= Π, for one instance K θ . The number of elements in K θ is bounded by 2 |D| . Note that the interpretation of the relations in S E \ S D is trivial, and thus we do not need to explicitly construct these relations when building K θ . Thus, 2 O(|D|) is a bound on the number of facts in (the constructed part of) K θ and on the time needed to build it. The number of guesses to be taken when constructing K θ is bounded by 2 |D| · |S I | where S I is the IDB schema of Π, thus by 2 |D| · |Π|. For each rule in Π, the number of candidate functions for homomorphisms from the rule body to K θ is bounded by 2 |D|·v and it can be checked in time O(|Π| · (|D| + |S I |)) whether a candidate is a homomorphism. We thus need time O(|Π| 2 ) · 2 O(|D|·v) per rule and time O(|Π| 3 )·2 O(|D|·v) overall to deal with the instance K θ . There are at most 2 |D| many instances K θ , a factor that is absorbed by the bound that we have already computed. J The next lemma is a main ingredient to the proof of Lemma 11. Intuitively, it shows that a semi-simple MDDLog programs with disjointness constraints can be understood as a constraint satisfaction problem (CSP). For two instances I and J, we write I → J if there is a homomorphism from I to J, which is defined in the standard way. Of course, homomorphisms also have to respect nullary relations. In the following, we call a finite instance a template when we use it as a homomorphism target, as in the CSP literature. Lemma 24. For every 0-type θ, there are templates T 0 , . . . , T n in signature S E such that, for every S E -instance I of some 0-type θ ⊆ θ, we have I |= Π iff I → T i for some i ≤ n.
Proof.Just like the construction of the instances K θ , the construction of the templates T 0 , . . . , T n is based on types. However, the types used for this purpose are formed over the schema S = S I ∪ S D instead of over the schema S D , where S I is the IDB schema of Π. To emphasize the difference between the two kinds of types, we from now on call the types introduced above types for S D .
A type for S is a set t ⊆ S that satisfies all rules in Π, that is, if a rule ρ mentions only nullary and unary relations (and thus involves at most a single variable since Π is semi-simple w.r.t. D) and all these relations are in t, then at least one of the relations from the head of ρ is in t. Note that, in contrast to 0-types for S D and 1-types for S D defined before, a type for S contains both unary and nullary relation symbols. The restriction δ of a type t for S to nullary relations is a 0-type for S. There is no need to define 1-types for S. We say that a type t for S is compatible with a 0-type δ for S if δ is the restriction of t to nullary relations.
Let θ be a 0-type for D. To construct the set of templates stipulated in Lemma 24, we define one template T δ for every 0-type δ for S that agrees with θ on relations from S D and does not contain the goal relation. The elements of T δ are the types for S that are compatible with δ and T δ consists of the following facts: 1. all facts R(t 1 , . . . , t n ) such that R ∈ S E \S D is of arity n and there is no rule ρ in Π and variables x 1 , . . . , x n such that the following conditions are satisfied: • R(x 1 , . . . , x n ) occurs in the body of ρ; • if P (x i ) or P () occurs in the body of ρ with P ∈ S, then P ∈ t i ; • for none of the disjuncts P (x i ) in the head of ρ, we have P ∈ t i ; • for none of the disjuncts P () in the head of ρ, we have P ∈ δ; 2. all facts P (t) with P ∈ t ∩ S D ; 3. all facts P () with P ∈ δ ∩ S D .
We have to show that the templates T δ are as required, that is, for every S E -instance I that has some 0-type θ ⊆ θ for S D , we have I |= Π iff I → T δ for some 0-type δ for S. "if". Assume that I is an S E -instance of 0-type θ ⊆ θ for S D and that there is a homomorphism h from I to T δ . Extend I to an S E ∪ S I -instance J by adding P () whenever P () ∈ δ ∩ S I and P (a) whenever P ∈ h(a) ∩ S I . Since the goal relation is not in δ, it is not in J; it thus remains to show that every rule ρ of Π is satisfied in J. First for rules ρ that contain a body atom whose relation is from S E \ S D . Since Π is semi-simple w.r.t. D, the body of ρ consists of one atom R(x 1 , . . . , x n ) with R ∈ S E \ S D plus atoms of the form P (x i ) and P () with P ∈ S. Assume that g is a homomorphism from the body of ρ to J. Then we have R(g(x 1 ), . . . , g(x n )) ∈ T δ . Moreover, 1. when P (x i ) is in the body of ρ and P ∈ S, then P ∈ g(x i ) and 2. when P () is in the body of ρ and P ∈ S, then P ∈ g(x i ) for 1 ≤ i ≤ n.
In fact, Point 1 follows from Point 2 of the construction of T δ when P ∈ S D and from the definition of J when P ∈ S I . Point 2 similarly follows from Point 3 of the construction of T δ . With Points 1 and 2 above, Condition 1 from the construction of T δ yields that the head of ρ contains an atom P (x i ) with P ∈ g(x i ) or P () with P ∈ J. Thus, ρ is satisfied in J. For rules ρ that contain no atom with a relation from S E \ S D , one can first observe that, since Π is semisimple w.r.t. D, there is at most one variable in the rule. We can now argue in a similar way as before that the rule is satisfied in J, using in particular the fact that types for S satisfy the rules in Π. "only if". Assume that I is an S E -instance of 0-type θ ⊆ θ for S D and that I |= Π. Then there is an extension J of I to signature S E ∪ S I that satisfies rules of Π and does not contain the goal relation. For every constant a in I, let t a be the set of all unary relations P ∈ S such that P (a) ∈ J and of all nullary relations P ∈ S such that P () ∈ J. Clearly, t a is a type for S. Set h(a) = t a for all constants a in I. It remains to verify that h is a homomorphism from I to T δ .
First consider facts P (a) ∈ I with P ∈ S D . Then P ∈ t a , thus P ∈ h(a), thus P (a) ∈ T δ by definition of T δ . Now consider facts R(a 1 , . . . , a n ) ∈ I with R ∈ S E \ S D . Assume to the contrary of what is to be shown that R(h(a 1 ), . . . , h(a n )) / ∈ T δ . By definition of T δ , there is a rule ρ of Π and variables x 1 , . . . , x n such that A second important ingredient to the proof of Theorem 11 is the following well-known lemma which is originally due to Erdős and concerns graphs of high girth and high chromatic number and was adapted to the following formulation in (Feder and Vardi 1998). Lemma 25. Let S E be a schema. For every S E -instance I and g, s ≥ 0, there is an S E -instance I such that 1. I → I, 2. I has girth exceeding g, and 3. for every S E -instance J with at most s elements, J → I iff J → I .
Lemma 11. For every Boolean MDDLog program Π over EDB schema S E and set of disjointness constraints D over S E such that Π is semi-simple w.r.t. D, the following are equivalent for any g ≥ 0: 1. Π is empty regarding D and 2. Π is empty regarding D and instances of girth exceeding g. Proof.Clearly, we only need to prove that if Π is non-empty w.r.t. D, then this is witnessed by an instance of girth exceeding g. By Lemma 9, Π being non-empty w.r.t. D implies that K θ |= Π for some 0-type θ. By Lemma 24, we find templates T 0 , . . . , T n in signature S E such that, for every S E -instance I of some 0-type θ ⊆ θ, we have I |= Π iff I → T i for some i ≤ n. Thus K θ → T i for all i ≤ n. By Lemma 25, there is an S E -instance K θ such that K θ → K θ (and thus K θ satisfies the constraints in D and has some 0-type θ ⊆ θ), K θ has girth exceeding h, and for every S E -instance I of size at most s := max{|T 0 |, . . . , |T n |}, we have K θ → I iff K θ → I. The latter implies K θ → T i for all i ≤ n, and thus K θ |= Π as desired. J
Proof.To decide whether Π 1 ⊆ Π 2 , we first jointly simplify Π 1 and Π 2 as per Theorem 6, giving programs Π S 1 and Π S 2 . These programs and Theorem 7 give another program Π and a set of constraints D such that Π is semi-simple w.r.t. Π. We decide whether Π is empty w.r.t. D and return the result. The size and complexity bounds given in Theorems 6, 7, and 8 give the complexity bound stated in Theorem 12. In fact, it can be verified that |Π S i | ≤ 2 p(|Πi|) , |Π| ≤ 2 2 p(|Π 2 |·log|Π 1 |) , and |D| ≤ 2 p(Π2) where p is a polynomial. Moreover, the variable width of Π is bounded by that of Π 1 ∪ Π 2 and it remains to plug these bounds into the time bounds stated in Theorem 8.
It remains to argue that the algorithm is correct. If Π 1 ⊆ Π 2 , then Π S 1 ⊆ Π S 2 , thus Π is non-empty w.r.t. D, thus "no" is returned. Let w be the atom width of Π 1 ∪ Π 2 (with the exception that w = 2 if that atom width is one). If "no" is returned by our algorithm, then Π is non-empty w.r.t. D. By Theorem 11, Π is non-empty w.r.t. D on instances of girth > w.
For the following lemma, let S E be the EDB schema of Π 1 and Π 2 , and let S I,i be the IDB schema of Π i , i ∈ {1, 2}.
Proof.Assume that Π 1 ⊆ Π 2 . Then there is an S E -instance I and a tuple a ⊆ adom(I) k such that a ∈ Π 1 (I) \ Π 2 (I).
Let C Π be the constants which occur in Π 1 ∪ Π 2 , and observe that C Π ⊆ C. We can assume w.l.o.g. that all constants in a are from C; if this is not the case, we can first rename constants in I and a that are from C \ (C Π ∪ a) with fresh constants and then rename constants in I and a that are from a \ C with constants from C \ C Π . By choice of C, there are enough constants of the latter kind. It can now be verified that I |= Π a 1 and I |= Π a 2 . In particular, an extension J of I to schema S E ∪ S I,1 that satisfies all rules in Π a 1 and does not contain the goal relation gives rise to an extension J of I that satisfies all rules in Π a 1 and does not contain goal(a): start with J and then apply all goal rules of Π 1 . By construction of Π a 1 and since goal() / ∈ J , we have goal(a) / ∈ J . Similarly, an extension J of I to schema S E ∪ S I,2 that satisfies all rules in Π 2 and does not contain goal(a) gives rise to an extension J of I that satisfies all rules in Π a 2 and does not contain goal(). Conversely, assume that Π a 1 ⊆ Π a 2 . Then there is an S Einstance I with I |= Π a 1 and I |= Π a 1 . By considering appropriate extensions of I to the schemas S E ∪S I,i , it can be verified in a very similar way as above that a ∈ Π 1 (I) \ Π 2 (I). J Proof.Assume that Π 1 ⊆ Π 2 . Then there is an S E -instance I such that I |= Π 1 and I |= Π 2 . Let J be the S E -instance obtained from I by adding R a (a) whenever a ∈ adom(I) ∩ C. It can be verified that J |= Π 1 and J |= Π 2 . Conversely, assume that Π 1 ⊆ Π 2 . Then there is an S Einstance I such that I |= Π 1 and I |= Π 2 . Let J be the S E -instance which is obtained from I by • dropping all facts that use a relation from S E \ S E and then • taking the quotient according to the following equivalence relation on adom(I): note that this is indeed an equivalence relation because the rules goal() ← R a1 (x) ∧ R a2 (x) in Π 2 (for all distinct a 1 , a 2 ) imply that for any a ∈ adom(I), there is at most It can be verified that J |= Π 1 and J |= Π 2 . J

Ontology-Mediated Queries
Preliminaries We first introduce the relevant OMQ languages and then provide missing proofs.
A ALCI-concept is formed according to the syntax rule C, D : where A ranges over a fixed countably infinite set of concept names and r over a fixed countably infinite set of role names. An ALC-concept is an ALCI-concept in which the constructors ∃r − .C and ∀r − .C are not used. An ALC-TBox (resp. ALCI-TBox) is a finite set of concept inclusions C D, C and D ALC-concepts (resp. ALCI-concepts). A SHI-TBox is a finite set of • concept inclusions C D, C and D SHI-concepts, • role inclusion r s, r and s role names, and • transitivity statements trans(r), r a role name.
DL semantics is given in terms of interpretations. An interpretation takes that form I = (∆ I , · I ) where ∆ I is a nonempty set called the domain and · I is the interpretation function which maps each concept name A to a subset A I ⊆ ∆ I and each role name r to a binary relation r I ⊆ r I × r I . The interpretation functions is extended to concepts in the standard way, for example (∃r.C) I = {d ∈ ∆ I | ∃e ∈ C I : (d, e) ∈ r I } (∃r − .C) I = {d ∈ ∆ I | ∃e ∈ C I : (e, d) ∈ r I }.
We refer to standard references such as (?) for full details. An intepretation is a model of a TBox T if it satisfies all statements in T , that is, • C D ∈ T implies C I ⊆ D I ; • r s ∈ T implies r I ⊆ s I ; • trans(r) ∈ T implies that r I is transitive.
In description logic, data is typically stored in so-called ABoxes. For uniformity with MDDLog, we use instances instead, identifying unary relations with concept names, binary relations with role names, and disallowing relations of any other arity. An interpretation I is a model of an instance I if A(a) ∈ I implies a ∈ A I and r(a, b) ∈ I implies (a, b) ∈ r I . We say that an instance I is consistent with a TBox T if I and T have a joint model. We write T |= r s if every model I of T satisfies r I ⊆ s I .
An ontology-mediated query (OMQ) takes the form Q = (T , S E , q) with T a TBox, S E a set of concept and role names, and q a UCQ. We use (L, Q) to refer to the set of all OMQs whose TBox is formulated in the language L and where the actual queries are from the language Q. For example, (ALC, UCQ) refers to the set of all OMQs that consist of an ALC-TBox and a UCQ. For OMQs (T , q) from (SHI, UCQ), we adopt the following additional restriction: when T contains a transitivity trans(r) and T |= r s, we disallow the use of s in the query q. Let I be an S E -instance and a a tuple of constants from I. We write I |= Q[a] and call a a certain answer to Q on I if for all models I of I and T , we have I |= q[a] (defined in the usual way).
Containment between OMQs is defined in analogy with containment between MDDLog programs: . This is different from the notion of containment considered in (Bienvenu, Lutz, and Wolter 2012), here called consistent containment. We say that Q 1 = (T 1 , S E , q 1 ) is consistently contained in Q 2 = (T 2 , S E , q 2 ), written Q 1 ⊆ c Q 2 , if for every S Einstance I that is consistent with T 1 and T 2 and every tuple a of constants from I, I |= Q 1 [a] implies I |= Q 2 [a]. We observe the following.
Lemma 26. In (SHI, UCQ), consistent containment can be reduced to containment in polynomial time.
Proof.(sketch) Let Q 1 = (T 1 , S E , q 1 ) and Q 2 = (T 2 , S E , q 2 ) be OMQs from (SHI, UCQ). Assume without loss of generality that all concept that occur in T 1 are in negation normal form, that is, negation is only applied to concept names but not to compound concepts. For every concept name A in S E ∪ sig(T 1 ), introduce fresh concept names A and A that do not occur in Q 1 and Q 2 . For every role name r in S E ∪ sig(T 1 ), introduce a fresh role name r . Define the TBox T 2 as the extension of T 2 with the following: • A A for all concept names A in S E ∪ sig(T 1 ); • r r for all role names r in S E ∪ sig(T 1 ); • every concept inclusion, role inclusion, and transitivity statement from T 1 , each concept name A replaced with A , each subconcept ¬A replaced with A , and each role name replaced with r ; • the inclusions A A and A A B for all concept names A in S E ∪ sig(T 1 ), where B is a fresh concept name.
Set q 2 = q 2 ∨ ∃x B(x). It suffices to establish the following claim. The proof is not difficult and left to the reader.
Proof.Let Q = (T , S E , q 0 ) be an OMQ from (SHI, UCQ). We use sub(T ) to denote the set of subconcepts of (concepts occurring in) T . Moreover, let Γ be the set of all tree-shaped conjunctive queries that can be obtained from a CQ in q 0 by first quantifying all answer variables, then identifying variables, and then taking a subquery. Here, a conjunctive query q is tree-shaped if (i) the undirected graph (V, {{x, y} | r(x, y) ∈ q}) is a tree (where V is the set of variables in q), (ii) r 1 (x, y), r 2 (x, y) ∈ q implies r 1 = r 2 , and (iii) r(x, y) ∈ q implies s(y, x) / ∈ q for all s. Every q ∈ Γ can be viewed as a ALCI-concept provided that we additionally choose a root x of the tree. We denote this concept with C q,x . For example, the query ∃x∃y∃z r(x, y) ∧ A(y) ∧ s(x, z) yields the ALCI-concept ∃r.A ∃s. . Let con(q 0 ) be the set of all these concepts C q,x and let S I be the schema that consists of monadic relation symbols P C and P C for each C ∈ sub(T ) ∪ con(q 0 ) and nullary relation symbols P q and P q for each q ∈ Γ. We are going to construct an MDDLog program Π over EDB schema S E and IDB schema S I that is equivalent to Q.
By a diagram, we mean a conjunction δ(x) of atoms over the schema S E ∪ S I . For an interpretation I, we write I |= δ(x) if there is a homomorphism from δ(x) to I, that is, a map h : x → ∆ I such that: 1. A(x) ∈ δ with A ∈ S E implies h(x) ∈ A I ; 2. r(x, y) ∈ δ with r ∈ S E implies (h(x), h(y)) ∈ A I ; 3. P q () ∈ δ implies I |= q and P q () ∈ δ implies I |= q; x a sequence of variables from x, if every homomorphism from δ(x) to some interpretation I is also a homomorphism from q(x ) to I. The MDDLog program Π consists of the following rules: 1. the rule P q () ∨ P q () ← R(x) for each q ∈ Γ, each R ∈ S E , and each R ∈ S E where x = x 1 , . . . , x n , n the arity of R; 2. the rule P C (x) ∨ P C (x) ← R(x) for each C ∈ sub(T ) ∪ con(q 0 ), each R ∈ S E , and each tuple x that can be obtained from x 1 , . . . , x n by replacing a single x i with x (n the arity of R); 3. the rule ⊥ ← δ(x) for each non-realizable diagram δ(x) that contains a single variable x and only atoms of the form P C (x), C ∈ sub(T ) ∪ con(q 0 ); 4. the rule ⊥ ← δ(x) for each non-realizable connected diagram δ(x) that contains at most two variables and at most three atoms; 5. the rule goal(x ) ← δ(x) for each diagram δ(x) that implies q 0 (x), has at most |q 0 | variable occurrences, and uses only relations of the following form: P q , P C with C a concept name that occurs in q 0 , and role names from S E that occur in q 0 .
To understand Π, a good first intuition is that rules of type 1 and 2 guess an interpretation I, rules of type 3 and 4 take care that the independent guesses are consistent with each other, with the facts in I and with the inclusions in the TBox T , and rules of type 5 ensure that Π returns the answers to q 0 in I. However, this description is an oversimplification. Guessing I is not really possible since I might have to contain additional domain elements to satisfy existential quantifiers in T which may be involved in homomorphisms from (a CQ in) q 0 to I, but new elements cannot be introduced by MDDLog rules. Instead of introducing new elements, rules of type 1 and 2 thus only guess the tree-shaped queries that are satisfied by those elements. Tree-shaped queries suffice because SHI has a tree-like model property and since we have disallowed the use of roles in the query that have a transitive subrole. The notion of 'diagram implies query' used in the rules of type 4 takes care that the guessed treeshaped queries are taken into account when looking for homomorphisms from q 0 to the guessed model. A more detailed explanation can be found in the proof of Theorem 1 of (Bienvenu et al. 2013). In fact, the construction used there is identical to the one used here, with two exceptions. First, we use predicates P C and P C for every concept C ∈ sub(T ) ∪ con(q 0 ) while the mentioned proof uses a predicate P t for every subset t ⊆ sub(T ) ∪ con(q 0 ). And second, our versions of Rules 3-5 are formulated more carefully. It can be verified that the correctness proof given in (Bienvenu et al. 2013) is not affected by these modifications. The modifications do make a difference regarding the size of Π, though, which we analyse next.
It is not hard to see that the number of rules of type 1 is bounded by 2 |q| 2 , the number of rules of type 2 is bounded by |T |, the number of rules of type 3 is bounded by 2 2 |q|·log|T | , the number of rules of type 4 is bounded by 2 p(|q|·log|T |) for some polynomial p, and the number of rules of type 5 is bounded by 2 p(|q|) . Consequently, the overall number of rules is bounded by 2 2 p(|q|·log|T |) and so is the size of Π. The bounds on the size of the IDB schema and number of rules in Π stated in Theorem 19 are easily verified. The construction can be carried out in double exponential time since for a given diagram δ(x) and CQ q(x ), with x a sequence of variables from x, it can be decided in 2EXPTIME whether δ(x) implies q(x ). J Theorem 20. Containment between OMQs from (SHI, UCQ) is in 2NEXPTIME. More precisely, for OMQs Q 1 = (T 1 , S E , q 1 ) and Q 2 = (T 2 , S E , q 2 ), it can be decided non-deterministically in time 2 2 p(|q 1 |·|q 2 |·log|T 1 |·log|T 2 |) whether Q 1 ⊆ Q 2 , p a polynomial. Proof.We convert Q 1 and Q 2 into MDDLog programs as per Theorem 19 and then remove the answer variables according to the proof of Theorem 15. Analyzing the latter construction reveals that it produces programs of size r·2s·a s where r is the number of rules of the input program, s is the rule size, and a the arity. Moreover the IDB schema is not changed and rule size at most doubles. The Π 1 , Π 2 obtained by these two first steps thus still satisfy Conditions 1-3 of Theorem 19 except that |q| in the last point has to be replaced by 2|q|.
The joint simplifications Π S 1 and Π S 2 from Theorem 6 then have size |Π S i | ≤ 2 2 p(|q i |·log|T i |) and their variable width is bounded by (the rule size of Π i and thus by) 2|q|. Let us analyze the size of the IDB schema of Π S i . First note that the initial variable identification step can be ignored. In fact, we start with at most 2 2 p(|q i |·log|T i |) rules, each of size at most 2|q i |. Thus variable identification results in a factor of (2|q i |)!, which is absorbed by 2 2 p(|q i |·log|T |) . The other parameters are not changed by variable identification.
When making rules biconnected in the construction of Π S 1 and Π S 2 , we need not worry about rules of type 1-2 and 4-5. The reason is that there are only 2 p(|qi|·log|Ti|) many such rules, each of size at most 2|q i |, and thus the number of additional IDB relations introduced for making them biconnected is also bounded by 2 p(|qi|·log|Ti|) . Rules of type 3, on the other hand, are of a very restricted form, namely ⊥ ← P C1 (x) ∧ · · · ∧ P Cn (x) with C 1 , . . . , C n ∈ sub(T )∪con(q 0 ). These rules are biconnected and thus we are done in the Boolean case. In the non-Boolean case, rules of the above form are manipulated in the second step of the reduction of non-Boolean MDDLog programs to Boolean MDDLog programs. The result are rules of exactly the same shape, but also rules of the form The latter rules have to be split up to be made biconnected. This will result in rules of the form where R a is one of the fresh IDB relations introduced in the mentioned reduction. Clearly, there are only 2 p(|qi|·log|Ti|) many rule bodies of the latter form and thus it suffices to introduce at most the same number of fresh IDB relations Q i . In summary, we have shown that a careful construction of Π S i can ensure that the size of the IDB schema of Π S i is bounded by 2 p(|qi|·log|Ti|) .

Lower Bound
The following result establishes the lower bound in Point 3 of Theorem 17. We state it here even in a slightly stronger form. ELIU denotes the description logic that admits only the concept constructors , , , and ∃ and ELI ⊥ denotes the DL with the constructors , ⊥, , and ∃.
With BAQ, we denote the class of Boolean atomic queries, that is, queries of the form ∃x A(x) with A a concept name.
The overall strategy of the proof is similar to that of our proof of the lower bounds stated in Theorem 3, but the details differ in a number of respects. Instead of reducing 2exp square tiling problem, we now reduce the 2-exp torus tiling problem. The definition is identical except that a tiling f for the latter problem additionally needs to satisfy (f (2 2 n − 1, i), f (0, i)) ∈ H and (f (i, 2 2 n − 1), f (i, u)) ∈ V for all i < 2 2 n . We first implement the reduction using UCQs instead of CQs and then adapt the proof to CQs. In the previous reduction, the role name r was used to connect neighboring grid nodes and nodes in counting trees. In the current reduction, we replace r with the role composition r − ; r where r − denotes the inverse of r and which behaves like a reflexivesymmetric role. We use S as an abbreviation for r − ; r. In particular, ∃S.C stands for ∃r − .∃r.C and ∀S.C stands for ∀r − .∀r.C. Some other details of the reduction are also different than before. Counting trees now have depth m + 2 instead of m, but no branching occurs on the last two levels of the tree. We also have three different versions of counting trees: one which uses the concept names B 1 , B 1 and B 2 , B 2 to store the two counters, one that uses B 3 , B 3 and B 4 , B 4 , and one that uses B 5 , B 5 and B 6 , B 6 . We say that the trees are of type 0, 1, or 2 to distinguish between the different versions. In the grid representation, we cycle through the types: from left to right and bottom to top, every tree of type 0 is succeeded by trees of type 1 which are succeeded by trees of type 2 which are succeeded by trees of type 3. Note that this refers to trees below grid nodes, but also to trees below horizontal and vertical step nodes. All this prepares for the construction of the UCQ later on.
Let P be a 2-exp torus tiling problem and w 0 an input to P of length n. We construct TBoxes T 1 , T 2 and OMQs Q i = (T i , S E , q i ), i ∈ {1, 2}, such that Q 1 ⊆ Q 2 iff there is a tiling for P and w 0 . The schema S E consists of • the EDB symbols r, B i , B i , i ∈ {1, . . . , 6}; • concept names A 0 , . . . , A m−1 and A 0 , . . . , A m−1 to implement a binary counter that identifies the position of each leaf in a counting tree; • concept names L 0 , . . . , L m+2 that identify the levels in counting trees.
We now construct the TBox T 1 . We first define concept inclusions which verify that a grid node has a proper attached counting tree. We start with identifying nodes on level m+2 by the concept name lev G,t m+2 where t ∈ {0, 1, 2} describes the type of the counting tree as explained above. We only give the construction explicitly for lev G,0 m+2 , which implements the two counters using B 1 , B 1 and B 2 , B 2 : m+2 . To make the UCQ work later on, we need that level m + 1-nodes are labeled complementarily regarding the concept names A i , A i , i ≤ m. We thus identify nodes on level m+ 1 as follows: Note that the first two lines may speak about different Ssuccessors. It is thus not clear that they achieve the intended complementary labeling. Moreover, we have not yet made sure that level m + 2-nodes are labeled with only one of A i , A i for each i and with only one B j , B j for each j ∈ {1, 2}. We fix these problem by including the following concept inclusions in T 2 : where i ranges over 0, . . . , m−1 and j over {1, 2}. These inclusions ensure that all relevant successors are labeled identically regarding the relevant concept names: otherwise the instance is inconsistent with T 2 and thus makes Q 2 true, which rules it out as a witness for non-containment.
We next make sure that every level m node has a level m+ 1 node attached and that its labeling is again complementary (in other words, the labeling of the level m node agrees with the labeling of the level m + 2 node below the attached level m + 1 node): We also include the following in T 2 : where i ranges over 0, . . . , m − 1. We next verify the remaining levels of the tree. To make sure that the required successors are present on all levels, we branch on the concept names A i , A i at level i of a counting tree and for all j < i, keep our choice of A j , A j : where i ranges over 0, . . . , m − 1 and j over 0, . . . , i − 1. Again, lines one to three may speak about different successors and we need to make sure that all those successors are labeled identically. This is done by adding the following inclusions to T 2 : where the ranges of i and j are as above. This finishes the verification of the counting tree. We do not use self step nodes in the current reduction, so a grid node is simply the root of a counting tree where both counter values are identical: lev G,0 0 gactive 0 .
The superscript · 0 in gactive 0 indicates that the counting tree of which this node is the root is of type 0. Concept inclusions that set gactive 1 and gactive 2 are defined analogously, replacing B 1 , B 1 and B 2 , B 2 appropriately, as explained above. In a similar way, we can verify the existence of counting trees below horizontal step nodes and vertical step nodes, signalling the existence of such trees by the concept names hactive t and vactive t , t ∈ {0, 1, 2}. In contrary to the counting trees between grid nodes, counting trees below horizontal and vertical step nodes need to properly increment the counters, as in the previous reduction. Details are slightly tedious but straightforward and thus omitted.
We also use T 1 to enforce that all grid nodes are labeled with a tile type. However, as we shall see below we cannot use all nodes labeled with a gactive t -concept as grid nodes, but only those ones that have an S-neighbor which is labeled with hactive t⊕1 or with vactive t⊕1 where ⊕ denotes addition modulo three. 3 We call such nodes g-active and add the following to T 1 : We next add inclusions to T 1 which identify a defect in the tiling and signal this by making the concept name D true: 1. horizontally neighboring tiles match; for all T i , T j ∈ T with (T i , T j ) / ∈ H and t ∈ {0, 1, 2}: T i gactive t ∃S.(hactive t⊕1 ∃S.(gactive t⊕2 T j )) D 2. vertically neighboring tiles match; for all T i , T j ∈ T with (T i , T j ) / ∈ V and t ∈ {0, 1, 2}: 3. The tiling respects the initial condition. Let w 0 = T i0 · · · T in−1 . As in the previous reduction, it is tedious but not difficult to write concept inclusions to be included in T which ensure that, for 0 ≤ i < n, every element that is in gactive t for some t and whose B -value represents horizontal position i and vertical position 0, satisfies the concept name pos i,0 . Here, (t, ) ranges over (0, 1), (1, 3), (2, 5). We then add the following CQ to q 2 for 0 ≤ j < n and all T ∈ T with T = T ij : pos j,0 T D. Note that Points 1 and 2 achieve the desired cycling through the three different types of counting trees: horizontal and vertical neighborships of g-active nodes whose types are not as expected are simply ignored (i.e., not treated as neighborships in the first place). This completes the construction of the TBox T 1 . The query q 1 simply takes the form ∃x D(x), thus Q 1 is true in an instance I iff the (potentially partial) grid in I does not admit a tiling, as desired. The construction of T 2 is also finished at this point. It thus remains to construct q 2 . As in the previous reduction, the purpose of q 2 is to ensure that counter values are copied appropriately to neighboring counting trees and that the two counter values below each grid and step node are unique. We call two counting trees neighboring if their roots are connected by the relation S. Since S is symmetric, we cannot distinguish successor counting trees from predecessor ones. The three different types of counting trees still allow us to achieve the desired copying of counter values. More precisely, we need to ensure that (Q1) the B i -value of a counting tree coincides with the B i+3 -value of neighboring trees, for all i ∈ {1, 2, 3}; (Q2) every g-active node is associated (via counting trees) with at most one B i -value, for each i ∈ {1, . . . , 6}. The counting strategy is illustrated in Figure 5, displaying a horizontal fragment of the grid. Arrows annotated with "=" indicate identical counter values and arrows annotated with "+ h " indicate incrementation of the horizontal component of the counter. A vertical fragment would look identical, except that hactive i is replaced with gactive i and incrementation of the horizontal counter component with incrementation of the vertical component.
Before we start constructing q 2 , we observe that it actually suffices to ensure (Q1) because (Q2) is then guaranteed automatically. The reason is that we are only interested in nodes that are g-active and thus have an S-neighbor which is labeled with hactive t⊕1 or with vactive t⊕1 . Assume for example that a node a is in gactive 0 and has an S-neighbor b which is labeled with hactive 1 . By (Q1), all leaves with a given position in the tree below a must agree regarding their B 1 , B 1 -value with the B 4 , B 4 -value of all leaves with the same position in the tree below b. Since both trees contain at least one leaf for each position, this achieves (Q2) for the B 1 -value. It also achieves (Q2) for the B 2 -value since that value is identical to B 1 -value. Obviously, the other cases are analogous.
The UCQ q 1 for achieving (Q1) includes six CQs. We first construct a query q which is true in an instance I if ( * ) there are two leaves in neighboring counting trees that have the same position and such that one leaf is labeled with B 1 and the other one with B 4 . The other five queries are then minor variations of q. We construct q from component queries p 0 , . . . , p m−1 , which all take the form of the query show on the left-hand side of Figure 6. Note that all edges are S-edges and that the only difference between the component queries is which concept names A i and A i are used. We assemble p 0 , . . . , p m−1 into the desired query q by taking variable disjoint copies of p 0 , . . . , p m−1 and then identifying (i) the x-variables of all components and (ii) the x -variables of all components.
To see why q achieves ( * ), first note that the variables x and x must be mapped to leaves of counting trees because of their L m+2 -label. Call these leaves a and a . Since x is labeled with B 1 and x with B 4 , a and a must be in different trees. Since they are connected to x in the query, both x 0 and x 0 must then be mapped either to a or to its predecessor; likewise, x 2m+4 and x 2m+4 must be mapped either to a or to its predecessor. Because of the labeling of a and a and the predecessors in the counting tree with A i and A i , we are actually even more constrained: exactly one of x 0 and x 0 must be mapped to a, and exactly one of x 2m+4 and x 2m+4 to a . Since the paths between leaves in different trees in the instance have length at least 2m + 5 and q contains paths from x 0 to x 2m+4 and from x 0 to x 2m+4 of length 2m + 4, only the following cases are possible: • x 0 is mapped to a, x 0 to the predecessor of a, x 2m+4 to a , and x 2m+4 to the predecessor of a ; • x 0 is mapped to a, x 0 to the predecessor of a, x 2m+4 to a , and x 2m+4 to the predecessor of a . This gives rise to the two variable identifications in each query p i shown in Figure 6. Note that the first case implies that a and a are both labeled with A i while they are both labeled with A i in the second case. In summary, a and a must thus agree on all concept names A i , A i . Note that with the identification x 0 = x (resp. x 0 = x), there is a path from x to x in the query of length 2m + 5. Thus, a and a are  Figure 7: Additional component for CQ.
in neighboring counting trees. Since a must satisfy B 1 and a must satisfy B 4 due to the labeling of x and x , we have achieved ( * ).
We now show how to replace the UCQ used in the reduction with a CQ. This requires the following changes: 1. every node on level m now has two successors instead of one (while nodes on level m + 1 still have a single successor); in gactive 0 -trees, one of the leafs below the same level m node carries the B 1 ,B 1 -label while the other leaf carries the B 2 ,B 2 -label; the labeling of the two leaves with A i ,A i is identical; similarly for gactive 1 and gactive 2 ; 2. the predecessors of leaf nodes in counting trees receive additional labels: when the leaf node is labeled with B i (resp. B i ), then its predecessor is labeled with B i (resp. B i ) and with B j and B j for all j ∈ {1, . . . , 6} \ {i}; these concept names are added to S E ; 3. the roots of counting trees receive an additional label R 0 or R 1 , alternating with neighboring trees; these concept names are added to S E , too; 4. the query construction is modified.
Points 2 and 3 are important for the CQ to be constructed to work correctly. Point 2 does not make sense without Point 1. Note that Points 1 to 3 can be achieved in a straightforward way by modifying the previous reduction, details are omitted. We thus concentrate on Point 4. The desired CQ q is again constructed from component queries. We use m components as shown in Figure 6, except that the B 1 and B 4labels are dropped. We additionally take the disjoint union with the component (partially) shown in Figure 7 where again x and x are the variables shared with the other components. The dotted edges denote S-paths of length 2m + 4. For readability, we show only some of the paths. The general scheme is that every variable x i,0 has a path to every variable x j,2m+4 unless the two variables are labeled with complementary concept names, that is, with concept names B i and B j such that i ∈ {1, 2, 3} and j = i + 1 or with concept names B i and B j such that i ∈ {1, 2, 3} and j = i + 1.
In the figure, we only show the paths outgoing from x 1,0 . The edges that connect u and u with the dotted paths always end at the middle point of a path, which has distance m + 2 to the x i,0 variable where the path starts and also distance m + 2 to the x j,2m+4 variable where it ends. We have to argue that the CQ q just constructed achieves (Q1). As before, x and x must be mapped to leafs of counting trees because of their L m+2 -label. Call these leaves a 1 and a 2 . All x i,0 must then be mapped to a or its predecessor, and all x i,2m+4 must be mapped to a or its predecessor. In fact, due to the labeling of a and a and their predecessors in their counting tree with the concepts B i , B i , exactly one variable x i,0 from x 0,0 , . . . , x 12,0 is mapped to a while all others are mapped to the predecessor of a; likewise, exactly one of the x j,2m+4 from x 0,2m+4 , . . . , x 12,2m+4 is mapped to a while all others are mapped to the predecessor of a . To achieve (Q1), we have to argue that x i,0 and x j,2m+4 are labeled with complementary concept names, and that a and a are in neighboring computation trees.
Assume to the contrary that x i,0 and x j,2m+4 are not labeled with complementary concept names. Then they are connected in q by a path of length 2m + 4 whose middle point y is connected to the variables u and u . In a homomorphism to the grid with counting trees, there are four possible targets for u and u and for the predecessor y −1 of y on the connecting path and the successor y 1 of y on that path: 1. u, y −1 map to the same constant, and so do u and y; 2. u, y map to the same constant, and so do u and y 1 ; 3. u , y −1 map to the same constant, and so do u and y; 4. u , y map to the same constant, and so do u and y 1 . However, options 1 and 3 are impossible because there would have to be a path of length 2m + 1 from a node labeled R 0 or R 1 to the leaf a. Similarly, options 2 and 4 are impossible because there would have to be a path of length 2m + 1 from a node labeled R 0 or R 1 to the leaf a . Thus, we have shown that x i,0 and x j,2m+4 are labeled with complementary concept names.
This together with the labeling scheme of Figure 5 also means that a and a (to which x i,0 and x j,2m+4 are mapped) are not in the same counting tree. Moreover, they cannot be in counting trees that are further apart than one step because under the assumption that x = x i,0 and x = x j,2m+4 , there is a path of length 2m + 5 in the query from x to x . Note that we can identify u with the 2m + 2nd variable on any such path and u with the 2m + 3rd variable (or vice versa) to admit a match in neighboring counting trees.
An OMQ Q = (T , S E , q) is FO-rewritable iff there is an FO-query that is equivalent to Q. Rewritability into monadic Datalog and into unrestricted Datalog are defined accordingly. Theorem 18. In (ALC, UCQ) and (ALCI, CQ), rewritability into FO, into monadic Datalog, and into Datalog is 2NEXPTIME-hard.
Proof.For (ALC, UCQ), it suffices to note that every MDDLog program with only unary and binary EDB relations can be translated into an equivalent OMQ from (ALC, UCQ) in polynomial time (Bienvenu et al. 2014). Thus, the lower bounds for (ALC, U CQ) are an immediate consequence of Theorem 5.
For (ALCI, CQ), we adapt the above hardness proof for containment, essentially in the same way as in the proof of Theorem 5. Our aim is thus to show that, from a 2-exp torus tiling problem P and an input w 0 to P , we can construct in polynomial time an (ALCI, CQ)-OMQ Q such that 1. if there is a tiling for P and w 0 , then Q is FO-rewritable; 2. if there is no tiling for P and w 0 , then Q is not Datalogrewritable.
We have shown how to construct from a 2-exp torus tiling problem P and an input w 0 to P , two (ALCI, CQ)-OMQs Q 1 , Q 2 such that Q 1 ⊆ Q 2 iff there is a tiling for P and w 0 . Moreover, Q 2 consists only of inclusions of the form C ⊥ with C an ELI-concept (a concept built only from conjuntion and existential restrictions, possibly using inverse roles). As above, let Q i = (T i , S E , q i ) for i ∈ {1, 2}. The desired OMQ Q = (T , S E , q) is constructed by choosing q = q 2 , S E = S E ∪ {s, u}, and choosing for T the union of T 1 and T 2 , extended with the following CIs: 1. ∃u.D R G B (where D is the concept name used in q 1 ); 2. C 1 C 2 C q2 for all distinct C 1 , C 2 ∈ {R, G, B} where C q2 is an (easy to construct) ELI-concept such that C I q2 = ∅ implies I |= q 2 for all interpretations I; 3. C ∃s.C C q2 for all C ∈ {R, G, B}.
We now show that Q satisfies Points 1 and 2 above.
For Point 1, assume that there is a tiling for P and w 0 . Then Q 1 ⊆ Q 2 . We claim that we obtain a UCQ-rewriting ϕ of Q by taking the disjunction of q 2 and of ∃x C(x) for every CI C ⊥ in T 2 . To see this, let I be an S E -instance. Clearly, I |= ϕ implies I |= Q. Conversely, assume that I |= Q. If I |= Q 1 , then there is a model I of I and T 1 such that D I = ∅. Thus the additional CIs from the construction of Q are inactive and I |= Q implies I |= Q 2 , thus I |= ϕ. Now assume I |= Q 1 . Then I |= Q 2 since Q 1 ⊆ Q 2 . Thus, again, I |= ϕ.
For Point 2, assume there is no tiling for P and w 0 . Then Q 1 ⊆ Q 2 . Given an undirected graph G = (V, E), let the instance I + G be defined as the disjoint union of the instance I 0 which represents the 2 2 n -grid plus counting gadgets, the instance I G which contains a fact s(v 1 , v 2 ) for every {v 1 , v 2 } ∈ V , extended with the fact u(v, g) for every v ∈ V and element g of I 0 .
Since there is no tiling for P and w 0 , we have I 0 |= Q 1 and thus I + G |= Q 1 . By construction of Q and since Q 1 ⊆ Q 2 , this implies that I + G |= Q iff G is not 3-colorable. It remains to argue that, consequently, a Datalog-rewriting of Q gives rise to a Datalog-rewriting of non-3-colorability (which doesn't exist). This can be done as in the proof of Theorem 5. J