Ontology-Mediated Queries Distributing over Components

1 Introduction

Ontology-based data access (OBDA) has recently emerged as a promising application of knowledge representation and reasoning technologies in information management systems. The aim of OBDA is to facilitate access to data that is significantly heterogeneous and incomplete. This is achieved via an ontology that provides a unified conceptual view of the data, and makes it accessible via database queries formulated solely in the vocabulary of the ontology. The actual database query and the ontology can be seen as two components of one composite query, called ontology-mediated query [Bienvenu et al., 2014]. OBDA can then be realized as the problem of answering ontology-mediated queries.

A challenging and important topic for declarative database query languages, and in particular (extensions of) Datalog, is coordination-free evaluation. This has its roots in declarative networking [Loo et al., 2009], an approach where distributed computations are programmed using Datalog-based formalisms. In this setting, programs (or queries) are specified over a global schema, and are executed by multiple computing nodes over which the database is distributed. These nodes can perform local computations, and also communicate asynchronously with each other via messages. The model assumes that messages can never be lost but can be arbitrarily delayed. An intrinsic source of inefficiency in such systems are the global barriers raised by the need for synchronization in computing the result of queries. This has motivated a fruitful line of research for isolating classes of queries that can be evaluated in a coordination-free manner [Zinn et al., 2012; Ameloot et al., 2013; 2014; 2015; Alvaro et al., 2014].

It is quite natural to ask wether the results on coordinationfree evaluation for declarative database query languages can be transferred to ontology-mediated queries. Undoubtedly, a positive answer to this question, apart from possible applications to declarative networking, will significantly contribute towards more efficient procedures for OBDA, since it will enable distributed ontology-mediated query evaluation in a coordination-free way. The goal of the present work is to initiate the study of coordination-free evaluation for ontologymediated queries, and give strong indications that the answer to the above challenging question is affirmative.

Distribution Over Components. More concretely, we focus on the question whether the answer to an ontology-mediated query can be computed by parallelizing it over the (maximally connected) components of the database, i.e., whether the query distributes over components. In other words, given an ontology-mediated query Q, the question is whether for every database D the answer to Q over D, denoted Q(D), coincides with S1in Q(Di), where D1↪ ▷ ▷ ▷ ↪Dn are the components of D. In this case, Q(D) can be computed without any communication over a network using a distribution where every computing node is assigned some of the connected components of the database, and every component is assigned to at least one computing node.

The notion of distribution over components has been introduced in [Ameloot et al., 2014], and explicitly considered for Datalog queries in [Ameloot et al., 2015]. It has been shown that connected Datalog, that is, the fragment of Datalog where all rule-bodies are connected, provides an effective syntax for Datalog queries that distribute over components, while the problem of deciding whether a Datalog query distributes over components is undecidable.

Aims and Objectives. As said, this work is concerned about ontology-mediated queries and their distribution over components. We focus on ontology-mediated queries where the database query is a conjunctive query and the ontology is formulated using existential rules (a.k.a. tuple-generating dependencies or Datalog◦ rules). It is widely accepted that existential rules form a natural and convenient way for modeling ontologies. This has led to a flurry of activity for designing ontology languages based on existential rules; see e.g., [Baget et al., 2011; Cal`ı et al., 2012a; 2012b; Thomazo et al., 2012; Leone et al., 2012]. We consider several ontology-mediated query languages, where the ontology is modeled using either arbitrary existential rules (without syntactic restrictions), or one of the basic decidable classes of existential rules, namely guarded, linear, or sticky (more details are given is Section 2), and we perform similar analysis as the one in [Ameloot et al., 2015] for Datalog queries. In particular, we would like to understand whether connectedness is the right notion for characterizing the fragment of the query languages in question that distributes over components, and understand the complexity of checking distribution over components.

Our Results. Our results can be summarized as follows:

I We show that for all the ontology-mediated query languages Q in question, the fragment of Q that distributes over components has the same expressive power as the fragment of Q where both the existential rules and the conjunctive query are connected (Theorem 2). For the language where the ontology is expressed using arbitrary existential rules, similar ideas as the ones in [Ameloot et al., 2015] for Datalog queries can be applied. However, the situation changes once we focus on the languages based on guarded, linear, or sticky existential rules, since these languages are not powerful enough to express transitivity axioms, which can be used to compute the connected components of the input database.

I The problem of deciding distribution over components is undecidable for all the ontology-mediated query languages that capture Datalog; implicit in [Ameloot et al., 2015]. Interestingly, we show that for the languages based on guarded, linear, or sticky existential rules, the problem is decidable (Theorems 15, 16 and 18). 1 Furthermore, for the languages based on linear and sticky rules, we obtain precise complexity results that range from⇧P2 up to coNEXPTIME.

I It turned out that our techniques and results have interesting consequences to ontology-mediated query languages based on Description Logics (Corollary 8, and Theorem 19), and to central database query languages, i.e., (unions of) conjunctive queries, and non-recursive Datalog queries (Corollary 11, and Theorems 20 and 21).

2 Preliminaries

Instances and Queries. Let C, N, and V be pairwise disjoint countably infinite sets of constants, (labeled) nulls and (regular) variables (used in queries and dependencies), respectively. A schema S is a finite set of relation symbols (or predicates) with associated arity. We write R◁n to denote that R has arity n. A term is either a constant, null or variable. An atom over S is an expression R(¯ t), where R is a relation symbol in S of arity n > 0 and ¯ t is an n-tuple of terms. A fact is an atom whose arguments consist only of constants. An instance over S is a (possibly infinite) set of atoms over S that contain constants and nulls, while a database over S is a finite set of facts over S. The active domain of an instance I, denoted adom(I), is the set of all terms occurring in I.

1 For guarded-based queries, this holds under the assumption that the conjunctive query is answer-guarded, i.e., it has an atom that contains all the answer variables.

A query over S is a mapping q that maps every database D over S to a set of answers q(D) ✓ adom(D)n , where n ≥ 0 is the arity of q. If n = 0, then q is a Boolean query, and we write q(D) = 1 if () 2 q(D), and q(D) = 0 otherwise.

The usual way of specifying queries is by means of (fragments of) first-order logic. A conjunctive query (CQ) q over S is a conjunction of atoms of the form 9¯ y φ(¯x↪ ¯ y), where ¯x [ ¯ y are variables of V, that uses only predicates from S. The free variables of a CQ are called answer variables. The evaluation of CQs over instances is defined in terms of homomorphisms; we assume the reader is familiar with the standard notion of homomorphism. Let I be an instance over S. The evaluation of q over I, denoted q(I), is the set of all tuples h(¯x) of constants such that h is a homomorphism from q to I. Each schema S and CQ q = 9¯ y φ(x1↪ ▷ ▷ ▷ ↪ xn↪ ¯ y) give rise to the nary query qφ↪S defined by setting, for every database D over S, qφ↪S(D) = ¶¯ c 2 adom(D)n ♣ ¯ c 2 q(D)♦. Let CQ be the class of all queries definable by some CQ. Analogously, we define UCQ as the class of all queries definable by some union of conjunctive queries (UCQ), that is, a disjunction of CQs with the same answer variables.

Two queries q1 and q2 over S are equivalent, written q1 ⌘ q2, if, for every database D over S, q1(D) = q2(D). A query language Q2 is at least as expressive as query language Q1, written Q1 ⪯ Q2, if, for every q1 2 Q1 over schema S, there is q2 2 Q2 over S such that q1 ⌘ q2. Q1 and Q2 have the same expressive power, written Q1 = Q2, if Q1 ⪯ Q2 ⪯ Q1.

Tgds for Specifying Ontologies. An ontology language is a fragment of first-order logic. Here, we focus on languages that are based on tuple-generating dependencies. A tuplegenerating dependency (tgd) is a first-order sentence of the form 8¯x8¯ y(φ(¯x↪ ¯ y) ! 9¯ z (¯x↪ ¯ z)), where both φ and are conjunctions of atoms without nulls and constants. For simplicity, we write this tgd as φ(¯x↪ ¯ y) ! 9¯ z (¯x↪ ¯ z), and use comma instead of ^ for conjoining atoms. We call φ and the body and head of the tgd, respectively, and write sch(⌃) for the set of predicates occurring in ⌃. An instance I satisfies the above tgd if the following holds: For every homomorphism h such that h(φ(¯x↪ ¯ y)) ✓ I, there is a homomorphism h0 that extends h such that h0 ( (¯x↪ ¯ z)) ✓ I. I satisfies a set ⌃ of tgds, denoted I ♣= ⌃, if I satisfies every tgd in ⌃. Let TGD be the class of all (finite) sets of tgds.

Ontology-Mediated Queries. An ontology-mediated query over S is a triple (S↪ ⌃↪ q), where ⌃ 2 TGD, q 2 CQ, and q is over S [ sch(⌃). We call S the data schema. In general, ontology-mediated queries are defined for arbitrary ontology languages (not only TGD), and arbitrary query languages (not only CQ). In this work, we focus on tgd-based ontology languages and queries definable via CQs. S is explicitly mentioned in the specification of the ontology-mediated query to highlight that it is interpreted as a query over S. The semantics of an ontology-mediated query is given in terms of certain answers. Let (S↪⌃↪ q) be an ontology-mediated query, where n is the arity of q. The certain answers to q w.r.t. a database D over S and ⌃ is the set of tuples certq↪⌃(D) = ¶¯ c 2 adom(D)n ♣ ¯ c 2 q(I)↪ 8I s.t. I ◆ D and I ♣= ⌃♦. Recall that certq↪⌃(D) coincides with the evaluation of q over the canonical instance of D and ⌃ that can be constructed by the chase; see e.g., [Cal`ı et al., 2012b]. The chase adds new atoms to D as dictated by ⌃ until the final result, written chase(D↪⌃), satisfies ⌃. When an existentially quantified variable must be satisfied the chase invents a new null.

Ontology-Mediated Query Languages. Every query Q = (S↪⌃↪ q) can be semantically interpreted as a query qQ over S by setting qQ(D) = certq↪⌃(D), for every S-database D. 2 Thus, we obtain a new query language, denoted (TGD↪ CQ), defined as the class of queries qQ, where Q is an ontologymediated query. However, (TGD↪ CQ) is undecidable since, given a database D over S, ⌃ 2 TGD, an n-ary query q 2 CQ over S[sch(⌃), and a tuple ¯ c 2 Cn , the problem of deciding if ¯ c 2 certq↪⌃(D) is undecidable [Beeri and Vardi, 1981]. This has led to a flurry of activity for identifying decidable syntactic restrictions. Such a restriction defines a subclass C of tgds, i.e., C ✓ TGD, which in turn gives rise to the decidable query language (C↪ CQ). The two main paradigms for ontological reasoning are guardedness and stickiness:

Guardedness: A tgd is guarded if its body contains an atom, called guard, that contains all the body-variables [Cal`ı et al., 2013]. Let G be the class of sets of guarded tgds. A key subclass of guarded tgds is the class of linear tgds, that is, tgds whose body consists of a single atom [Cal`ı et al., 2012a]. Let L be the class of sets of linear tgds.

Stickiness: The goal of stickiness is to express joins that are not expressible via guarded tgds. The key property underlying this condition is as follows: During the chase, terms that are associated with variables that appear more than once in the body of a tgd (i.e., join variables) are always propagated (or "stick") to the inferred atoms. Due to lack of space we omit the definition that can be found in [Cal`ı et al., 2012b]. Let S be the class of sticky sets of tgds.

Weak Versions: Both G and S have a weak version: Weaklyguarded [Cal`ı et al., 2013] and weakly-sticky [Cal`ı et al., 2012b], respectively. These are highly expressive classes obtained by relaxing guardedness and stickiness so that only those positions that receive nulls during the chase are taken into account. We write WG and WS for the class of weaklyguarded and weakly-sticky sets of tgds, respectively.

We refer to the query languages defined above as ontologymediated query languages.

3 Distribution of Queries and Connectedness

Our goal is to syntactically characterize the expressive power of the fragment of the query languages in question that guarantees distribution over components. Let us recall the notion of distribution over components [Ameloot et al., 2014]. A set of atoms A is connected if for all a↪ b 2 adom(A), there exists a sequence ↵1↪ ▷ ▷ ▷ ↪ ↵n of atoms in A such that a 2 adom(↵1), b 2 adom(↵n), and adom(↵i)\adom(↵i+1) 6= ?, for each i 2 [n- 1]. 3 We call B ✓ A a component of A if

2 For brevity, we use Q both for (S↪ ⌃↪ q) and the mapping qQ.

3 Henceforth, we write [k] for ¶1↪ ▷ ▷ ▷ ↪ k♦.

(i) B is connected, and (ii) for every ↵ 2 A ∩ B, B [ ¶↵♦ is not connected. 4 Let co(A) be the set of components of A.

Definition 1 A query q over S distributes over components if q(D) = SD02co(D) q(D0 ), for every database D over S.

Roughly, the centralized answer to q w.r.t. D is precisely obtained when we parallelize q over the components of D. Let DIST be the class of queries that distribute over components. We proceed to characterize the expressive power of the fragment of (C↪ CQ), where C is one of the classes of tgds introduced above. This is done via connectedness. A tgd is connected if the set of atoms occurring in its body is connected, while a set ⌃ of tgds is called connected if every tgd in ⌃ is connected. Given a class C of tgds, we write conC for the class of all (finite) sets of tgds that are connected and fall in C. Similarly, we write conCQ for the class of all queries definable by some CQ that is connected.

The main result of this section states that every query that is expressible by one of the ontology-mediated query languages Q in question and distributes over components is equivalent to a connected query that falls in Q, and vice versa. Formally:

Notice that guarded and linear tgds are, by definition, connected. This implies that, for C 2 ¶G↪ L♦, the above theorem can be equivalently stated as (C↪ CQ)\DIST = (C↪ conCQ). We present Theorem 2 in this way for the sake of uniformity. Let us now discuss the key ideas underlying Theorem 2.

For the (⌫) direction we show, no matter which ontologymediated query language we consider, that connectedness ensures distribution over components. This is a consequence of the fact that, given a query Q = (S↪ ⌃↪ q) 2 (conC↪ conCQ), for every database D over S with co(D) = ¶D1↪ ▷ ▷ ▷ ↪Dm♦, chase(D↪ ⌃) can be partitioned into ¶I1↪ ▷ ▷ ▷ ↪ Im♦ such that, for each i 2 [m], the atoms of Ii depend only on Di. Thus:

Proposition 3 For each C ✓ TGD, (conC↪ conCQ) ⪯ (C↪ CQ) \ DIST.

We proceed with the (⪯) direction. It turned out that there is no single reduction (at least no obvious one) from queries that distribute over components to connected queries that is generic enough to deal with all the query languages in question. Nevertheless, our languages can be classified into three groups according to certain properties that are useful for our purposes, and then treat each group separately. These groups and the underlying properties are as follows:

• (A) (TGD↪ CQ), (WG↪ CQ) and (WS↪ CQ); these languages are powerful enough to express (a limited form of) transitivity and cartesian products.
• (B) (G↪ CQ), (L↪ CQ); guarded and linear tgds are, by definition, connected.
• (C) (S↪ CQ); UCQ is at least as expressive as (S↪ CQ), and (conS↪ conCQ) is at least as expressive as conUCQ. 5

4 For technical clarity, the notion of component is defined only for sets of atoms that do not contain nullary atoms.

5 We write conUCQ for the class of all queries definable by a union of connected CQs.

We consider each one of the above groups, and show that distribution over components implies (semantic) connectedness.

Group A of Query Languages

Our main technical tool is the so-called connecting operator, based on a construction given in [Ameloot et al., 2015] for showing that distribution over components implies connectedness when we focus on Datalog queries. By applying the connecting operator to a query Q = (S↪ ⌃↪ q) 2 (TGD↪ CQ), we obtain the query Qc = (S↪ c(⌃)↪ c(q)) defined as follows. The set c(⌃) consists of the tgds:

for each R◁n 2 S and i↪ j 2 [n], where con is a new binary

stating that con is symmetric and transitive; con(a↪ b) states that the constants a and b belong to the same component of the input database. In addition, we have the tgd

where v 62 ¶x1↪ ▷ ▷ ▷ ↪ xm♦, that annotates every atom of a certain component of the input database with all the constants in this component. Finally, for each σ 2 ⌃, we add to c(⌃) the connected version of σ obtained by replacing each atom R(¯x) in σ with R? (vσ↪ ¯x), where vσ is a new variable. Analogously, c(q) is defined as the connected version of q. It can be shown that Q 2 DIST implies Q ⌘ Qc . Then:

Proposition 4 For each C ✓ TGD that is closed under connecting, 6 (C↪ CQ) \ DIST ⪯ (conC↪ conCQ).

Interestingly, TGD, WG, and WS are closed under connecting. Hence, Proposition 4 implies that distribution over components implies connectedness for the languages of Group A.

Group B of Query Languages

It is clear that G and L are not closed under connecting, and therefore we need to follow a different approach. To this end, we exploit the fact that guarded and linear tgds are, by definition, connected. In particular, we establish a general result for subclasses of conTGD:

Proposition 5 For each C ✓ conTGD, (C↪ CQ) \ DIST ⪯ (C↪ conCQ).

It is clear that the above result immediately shows that distribution over components implies connectedness for the languages of Group B. We proceed to explain the key ideas underlying Proposition 5. Fix an arbitrary class C ✓ conTGD, and a query Q = (S↪ ⌃↪ q) 2 (C↪ CQ) \ DIST, where q◁n is defined by the CQ 9¯ y φ(¯x↪ ¯ y). Observe that if Q is unsatisfiable, i.e., there is no database D over S such that Q(D) 6= ?, then the claim holds trivially; simply choose an arbitrary unsatisfiable query from (C↪ conTGD). The interesting case is when Q is satisfiable. Let ¶φ1↪ ▷ ▷ ▷ ↪ φk♦ be the components of q. We assume that k ≥ 2 since for k = 1 the claim holds trivially. Our goal is to show that there exists i 2 [k] such that Qi = (S↪ ⌃↪ qi), where qi is the CQ obtained from q by keeping only the component φi, is equivalent to Q. Since Qi 2 (C↪ conCQ) the claim follows. We proceed by distinguishing the two cases where q is either non-Boolean (i.e., n > 0) or Boolean (i.e., n = 0).

6 This means that, for each set ⌃ 2 C, c(⌃) 2 C.

Case 1 - Non-Boolean: Interestingly, we can show that all the answer variables of q occur in a single component. In fact, if an answer variable occurs in more than one component of q, then Q is unsatisfiable, which contradicts the fact that Q is satisfiable; this exploits the fact that ⌃ is connected. Therefore, we can refer to the component q¯x of q that contains the answer variables of q. Notably, the query obtained from Q by replacing q with q¯x is equivalent to Q:

It is clear that Q¯x 2 (C↪ conCQ), and the claim when q is non-Boolean follows by Lemma 6.

Case 2 - Boolean: Let us now consider the Boolean case. Although we cannot refer to the component q¯x of q, we can show that there exists a component that gives rise to a query equivalent to Q. Given a query ˆQ = (ˆS↪ ˆ⌃↪ ˆ q) 2 (C↪ CQ) \ DIST, where ˆ q is Boolean and 1↪ ▷ ▷ ▷ ↪ m are its components, let ˆQi be the query obtained from ˆQ by keeping only the component i of ˆ q, and ˆQ-i the query obtained from ˆQ by removing the component i. We can show that, for each i 2 [m], ˆQi ✓ ˆQ-i or ˆQ-i ✓ ˆQi. 7 Thus, starting from Q, and repeatedly applying this result, we will find an integer i 2 [k] such that Qi ✓ Q-i . It is not difficult to show that Q ⌘ Qi. Thus:

Lemma 7 There exists i 2 [k] such that Q ⌘ Qi, where Qi = (S↪ ⌃↪ qi).

It is clear that the query Qi provided by Lemma 7 belongs to (C↪ conCQ), and the claim when q is Boolean follows.

Description Logics. Before we proceed to the third group of query languages, we would like to briefly discuss an interesting consequence of Proposition 5 to ontology-mediated query languages based on Description Logics (DLs). As for classes of tgds, a DL L gives rise to the query language (L↪ CQ). One of the most prominent and well-studied DLs is EL [Baader, 2003]. It is known that an EL-TBox can be rewritten as a set of guarded tgds [Cal`ı et al., 2012a]. This fact, together with Propositions 3 and 5, allow us to show that:

Group C of Query Languages

S is not closed under connecting, and S 6✓ conTGD. Thus, we need to apply different techniques for establishing the desired result. Our main technical tool is as follows:

Proposition 9 For each C ✓ TGD such that

1. conUCQ ⪯ (conC↪ conCQ),

1. (C↪ CQ) ⪯ UCQ;

it holds that (C↪ CQ) \DIST ⪯ (conC↪ conCQ).

7 As usual, Q1 ✓ Q2 means that for every source database D, Q1(D) ✓ Q2(D).

To establish Proposition 9, it suffices to show the following lemma, which can be done by exploiting similar ideas as the ones developed above for proving Proposition 5:

Lemma 10 UCQ \ DIST ⪯ conUCQ.

Having the above proposition in place, to establish the desired result for (S↪ CQ) it remains to show that (S↪ CQ) ⪯ UCQ and conUCQ ⪯ (conS↪ conCQ). The former is implicit in [Gottlob et al., 2014], where it is shown that evaluation for (S↪ CQ) is UCQ-rewritable. The latter is shown by exploiting the fact that every CQ of the form 9¯ y φ(¯x↪ ¯ y) can be converted into the sticky tgd φ(¯x↪ ¯ y) ! ans(¯x↪ ¯ y); this tgd is sticky since all the body-variables are propagated to the head.

Database Query Languages. We conclude this section by discussing some interesting consequences to central database query languages, in particular CQ, UCQ, and NRDat. 8 First, notice that Proposition 3 can be established for CQ and UCQ. This fact, together with Lemma 10, which holds also for CQ, implies that CQ\DIST (UCQ\DIST) has the same expressive power as conCQ (conUCQ). Regarding NRDat, we can show that the class of tgds that corresponds to non-recursive Datalog programs enjoys the two properties stated in Proposition 9. Hence, Propositions 3 and 9 imply that:

Corollary 11 For each language Q 2 ¶CQ↪ UCQ↪ NRDat♦, Q \ DIST = conQ.

4 Deciding Distribution Over Components

The question that comes up is whether distribution over components for the query languages considered so far can be decided. This problem, dubbed Dist(Q) with Q being a query language, accepts as input a query Q 2 Q, and asks whether Q 2 DIST. Notice that Theorem 2 only says that Dist(Q) is equivalent to the problem of checking whether a query is semantically (not syntactically) connected, and thus it does not provide a decision procedure for our problem.

We start our analysis be recalling a recent negative result: Dist(Dat) is undecidable [Ameloot et al., 2015], where Dat is the class of all queries definable by some Datalog query. Thus, for every C ✓ TGD that captures Datalog programs, we immediately obtain that Dist(C↪ CQ) is undecidable. 9 TGD, WG and WS are such classes, and hence:

Theorem 12 For Q 2 ¶(TGD↪ CQ)↪ (WG↪ CQ)↪ (WS↪ CQ)♦, Dist(Q) is undecidable.

This negative result rules out weakly-guarded and weaklysticky sets of tgds. What about their non-weak versions? Do they ensure the decidability of Dist? This will be the subject of the remainder of this section.

Distribution and Guardedness

We show that our problem is decidable if we focus on the answer-guarded fragment of (G↪ CQ). A CQ q is answerguarded if it includes an atom that contains all the answer variables [B´ar´any et al., 2013]. Let AGCQ be the class of all queries definable by some answer-guarded CQ. Notice that AGCQ is a broad class of queries, which includes all Boolean CQs. Our goal is to show that Dist(G↪ AGCQ) is decidable. Fix a query Q = (S↪ ⌃↪ q) 2 (G↪ AGCQ), where ¶q1↪ ▷ ▷ ▷ ↪ qk♦ are the components of q. Recall that Qi is the query obtained from Q by keeping only the component qi of q. By exploiting Proposition 3, and Lemmas 6 and 7, we can show that:

8 All queries definable by some non-recursive Datalog query.

9 For brevity, we write Dist(C↪ CQ) instead of Dist((C↪ CQ)).

Lemma 13 Q 2 DIST iff one of the following holds:

1. Q is unsatisfiable;
2. There exists i 2 [k] such that Qi 2 (G↪ AGCQ) and Qi ✓ Q.

Checking whether Q is unsatisfiable can be reduced to the containment problem for (G↪ AGCQ). Thus, Lemma 13 provides an algorithm for Dist(G↪ AGCQ) under the assumption that Cont(G↪ AGCQ) is decidable. 10 It remains to show that:

The above result is shown by a reduction to Cont(GDat), where GDat is the class of queries definable by some guarded Datalog query [B´ar´any et al., 2012]. Guarded Datalog requires an atom with an extensional predicate to contain all the variables in the head. Cont(GDat) is in 2EXPTIME as it can be reduced to the satisfiability problem for guarded negation fixed point logic [B´ar´any et al., 2015]. Our reduction exploits a construction given in [B´ar´any et al., 2013] for rewriting a query of Q = (S↪ ⌃↪ q) 2 (G↪ AGCQ) into an equivalent Datalog query QDat = (⇧↪Ans), where each rule of ⇧ has a guard atom (possibly with an intensional predicate) that contains all the head-variables. This construction assumes that q is answer-guarded; this is the reason why we focus on answerguarded queries. From the above discussion, we get that:

Theorem 15 Dist(G↪ AGCQ) is decidable.

The decision procedure underlying Theorem 15 shows that Dist(G↪ AGCQ) is elementary. However, its exact complexity is unknown. Moreover, the decidability of Dist(G↪ CQ), i.e., when the CQ is not answer-guarded, is still open.

Distribution and Linearity

It is easy to verify that the proof of Theorem 15 applies even if we focus on linear tgds; thus, Dist(L↪ AGCQ) is decidable. Interestingly, by exploiting the fact that evaluation for (L↪ CQ) is UCQ-rewritable [Gottlob et al., 2014], we can significantly strengthen the above result. We can show that:

Theorem 16 Dist(L↪ CQ) is PSPACE-complete, and ⇧P2 - complete if the arity of the schema is fixed.

Fix a query Q = (S↪ ⌃↪ q) 2 (L↪ CQ). By applying query rewriting techniques, we can construct Qr 2 UCQ such that Q ⌘ Qr [Gottlob et al., 2014]. Clearly, Q 2 DIST iff Qr 2 DIST. Hence, it would be quite beneficial to first understand the problem Dist(UCQ). One may be tempted to think that a UCQ distributes over components iff each of its disjuncts does. It is easy to show that this is not the case; consider, e.g., the UCQ 9x9y (R(x) ^ S(y)) _ 9x R(x). The reason for this is the fact that some disjuncts that do not distribute over components maybe subsumed by other ones that distribute over components. To formalize this we need an auxiliary notation. For a CQ q(¯x) = 9¯ y (Vni=1 Ri(¯x↪ ¯ y)), let D[q] the database ¶Ri(c(¯x)↪ c(¯ y))♦i2[n] obtained after replacing each variable v in q with a fresh constant c(v). Then:

10 For a query language Q, Cont(Q) accepts as input two queries Q1↪ Q2 2 Q of the same arity, and asks whether Q1 ✓ Q2.

Lemma 17 For Q(¯x) 2 UCQ, Q 2 DIST iff for each q 2 Q, there exists D0 2 co(D[q]) such that c(¯x) 2 Q(D0 ).

Let Q = (S↪⌃↪ q(¯x)) 2 (L↪ CQ), and let Qr(¯x) 2 UCQ be the rewriting obtained by applying the rewriting algorithm in [Gottlob et al., 2014]; recall that Q ⌘ Qr. This algorithm constructs Qr starting from q and exhaustively applying two steps: rewriting and minimization. The rewriting step resolves an atom in the disjunct q0 under consideration using a linear tgd of ⌃, while the minimization step is responsible for unifying some atoms of q0 . Lemma 17 implies that Q 62 DIST iff there exists q0 2 Qr such that, for every D0 2 co(D[q0 ]), c(¯x) 2 Q(D0 ). This suggests the following decision procedure for the complement of Dist(L↪ CQ):

1. Construct a CQ q0 (¯x) 2 Qr by nondeterministically applying rewriting and minimization steps;
2. For each D0 2 co(D), if c(¯x) 2 Q(D0 ), then Reject;
3. Accept.

Each step of the above procedure uses polynomial space. This is shown by exploiting the fact that each q0 2 Qr cannot have more atoms than the original CQ q due to the linearity of tgds, and also the fact that evaluation for (L↪ CQ) is in PSPACE; the latter is implicit in [Johnson and Klug, 1984]. In case the arity of the schema is fixed, q0 can be nondeterministically constructed in polynomial time, while evaluation for (L↪ CQ) is in NP; implicit in [Johnson and Klug, 1984]. Thus, the above procedure gives a ⌃P2 upper bound. Hence, Dist(L↪ CQ) is in PSPACE, and in ⇧P2 if the arity of the schema is fixed.

The lower bounds are established by a reduction from a restricted version of Cont(L↪ CQ). We define RestCont(C↪ CQ) to be the problem of checking Q1 ✓ Q2, where Q1 = (S [ ¶P ♦↪ ⌃↪ q1) and Q2 = (S [ ¶P ♦↪ ⌃↪ q2) with P 62 S being a unary predicate not in ⌃, q1, q2, given: (i) a set ⌃ 2 C of connected tgds, (ii) a Boolean connected CQ q1 with at least one variable vq1 that occurs only in atoms with a predicate of S, and (iii) a Boolean CQ q2 that uses only predicates of S. It holds that Q1 ✓ Q2 iff (S[¶P ♦↪ ⌃↪ q1^P (vq1 )^q2) 2 DIST, which in turn implies that we have a logspace reduction from RestCont(L↪ CQ) to Dist(L↪ CQ). Therefore, to obtain the desired lower bounds for Dist(L↪ CQ), it remains to show that RestCont(L↪ CQ) is PSPACE-hard, and ⇧P2 -hard for fixed arity. The former can be shown by a reduction from query answering under linear tgds, while the latter is implicit in [Bienvenu et al., 2012] (see the proof of Theorem 9). In fact, the ⇧P2 -hardness holds even for tgds of the form P(x) ! R(x).

Distribution and Stickiness

We proceed to show that Dist(S↪ CQ) is decidable, and pinpoint the complexity of the problem:

Theorem 18 Dist(S↪ CQ) is coNEXPTIME-complete, 11 and ⇧P2 -complete if the arity of the schema is fixed.

Evaluation for (S↪ CQ) is UCQ-rewritable [Gottlob et al., 2014]. This allows us to exploit the algorithm devised above for solving the complement of Dist(L↪ CQ). However, since sticky tgds may have more than one atom in their body, the space we need during the execution of the algorithm is not polynomial anymore; actually, we need exponential space. Nevertheless, it can be shown that for (S↪ CQ) this algorithm terminates after exponentially many steps, which implies a NEXPTIME upper bound for the complement of our problem. This exploits the fact that query evaluation for (S↪ CQ) is in EXPTIME [Cal`ı et al., 2012b]. In case the arity of the schema is fixed, the same analysis as for (L↪ CQ) applies, and thus we obtain a ⌃P2 upper bound for the complement of our problem. The fact that evaluation for (S↪ CQ) in case of fixed arity is in NP has been shown in [Lukasiewicz et al., 2015].

11 The lower bound assumes databases with at least two constants.

To show coNEXPTIME-hardness for Dist(S↪ CQ), we first establish the same for Cont(conS↪ conCQ) by giving a reduction from the so-called Exponential Tiling Problem [Johnson, 1990]; for technical reasons, we assume databases with at least two constants. The desired coNEXPTIME-hardness is obtained by reducing Cont(conS↪ conCQ) to Dist(S↪ conCQ). The ⇧P2 -hardness in case the arity of the schema is fixed is obtained in the same way as for (L↪ CQ).

Description Logics and Database Query Languages

Interestingly, by exploiting the ideas developed above for understanding the complexity of Dist, we can show that:

Theorem 19 Dist(EL↪ CQ) is EXPTIME-complete.

For the upper bound, we relax Lemma 13 in order to deal with arbitrary (beyond answer-guarded) CQs, and then use the fact that Cont(EL↪ CQ) is in EXPTIME [Bienvenu et al., 2012]. The lower bound exploits the problem RestCont+ obtained from RestCont dy dropping the third condition in the definition of an instance of RestCont. RestCont+(EL↪ CQ) is known to be EXPTIME-hard [Bienvenu et al., 2012], which is not the case for RestCont(EL↪ CQ).

We conclude with the complexity of Dist when we focus on central database query languages. We show that:

Theorem 20 Dist(CQ) and Dist(UCQ) are NP-complete, even if the arity of the schema is fixed.

By exploiting Lemma 17, we can design a guess-and-check algorithm for Dist(UCQ) that runs in polynomial time; the NP-hardness is shown by reduction from Cont(CQ). Finally, by giving a proof similar to the one for Theorem 18, we show:

Theorem 21 Dist(NRDat) is coNEXPTIME-complete, even if the arity of the schema is fixed. 11

5 Conclusions

Here are some interesting open problems that we are planning to tackle: (i) The complexity of deciding distribution over components for guarded-based queries is still open, (ii) distribution over components in the presence of equality and denial constraints is not well understood, and (iii) we do not know how distribution over components behaves in the case of non-monotonic queries.

Acknowledgements. Austrian Science Fund (FWF), projects P25207-N23, Y698 and W1255-N23, and Vienna Science and Technology Fund (WWTF), project ICT12-015.