In the field of ontology-based query answering, existential rules (a.k.a. tuple-generating dependencies) form an expressive Datalog-based language to specify implicit knowledge. The presence of existential quantification in rule-heads, however, makes the main reasoning tasks undecidable. To overcome this limitation, in the last two decades, a number of classes of existential rules guaranteeing the decidability of query answering have been proposed. Unfortunately, such classes are typically based on diferent syntactic conditions imposing the development of diferent ad hoc reasoners. This paper introduces a novel general condition that allows to define, systematically, from any decidable class of existential rules, a new class called Dyadic- that enjoys the following properties: () it is decidable; () it generalizes ; () it keeps the same data complexity as ; and () it can exploit any reasoner for query answering over . Additionally, the paper proposes a simple and elegant syntactic condition that gives rise to the class Ward+ generalizing the well-known decidable classes Shy and Ward, and being included in Dyadic-Shy.
In ontology-based query answering, a conjunctive query is typically evaluated over a logical
theory consisting of a relational database paired with an ontology. Description Logics [
Data Complexity ExpTime-complete PTime-complete PTime-complete PTime-complete PTime-complete PTime-complete PTime-complete
AC0 AC0 AC0
Combined Complexity 2ExpTime-complete 2ExpTime-complete 2ExpTime-complete 2ExpTime-complete ExpTime-complete ExpTime-complete ExpTime-complete ExpTime-complete PSpace-complete PSpace-complete encompasses a number of concrete classes based on syntactic conditions. Table 1 summarizes them and their computational complexity with respect to query answering. Unfortunately, the fact that such classes are typically based on diferent syntactic conditions imposes the development of diferent ad hoc reasoners.
This paper introduces a novel general condition that allows to define, systematically, from any class of existential rules for which conjunctive query answering is decidable, a new class called Dyadic- that enjoys the following properties: () it is decidable; () it generalizes ; () it keeps the same data complexity as ; and () it can exploit any reasoner for query answering over . The key idea behind this new class is the existence of a dyadic decomposition of an ontology Σ consisting of a pair (ΣHG, Σ ) such that: () ΣHG ∪ Σ is equivalent to Σ with respect to query answering; () Σ ∈ ; and () ΣHG is a set of “head-ground” rules, which intuitively are rules generating only ground atoms when paired with Σ . In analogy with the existing semantic classes, the union of all Dyadic- classes are called dyadic decomposable sets.
Finally, the paper proposes a simple and elegant syntactic condition that gives rise to the concrete class Ward+ generalizing the well-known decidable classes Shy and Ward, and being included in Dyadic-Shy.
Fix three pairwise disjoint lexicographically enumerable infinite sets Δ of constants, Δ of nulls ( , 0, 1, ...), and Δ of variables (, , , and variations thereof). Their union is denoted by Δ and its elements are called terms. For any integer ≥ 0, we may write [] for the set {1, ..., }; in particular, as usual, if = 0, then [] = ∅. An atom is an expression of the form (t), where = pred() is a (relational) predicate, t = 1, ..., is a tuple of terms = arity() = arity( ) ≥ 0 is the arity of both and , and [] denotes the -th term t[] = of , for each ∈ []. In particular, if = 0, then t is the empty tuple and = (). By const() (resp., vars()) we denote the set of constants (resp., variables) occurring in . A fact is an atom that contains only constants. A (relational) schema S is a finite set of predicates, each with its own arity. The set of positions of S, denoted pos(S), is defined as { [] | ∈ S ∧ 1 ≤ ≤ arity( )}, where each [] denotes the -th position of . A (relational) structure over S is any (possibly infinite) set of atoms using only predicates from S. The domain of a structure , denoted dom(), is the set of all the terms occurring in . An instance over S is any structure over S such that dom() ⊆ Δ ∪ Δ . A database over S is any finite instance over S containing only facts. Consider a map : 1 → 2 where 1 ⊆ Δ and 2 ⊆ Δ. Given a set of terms, the restriction of with respect to is the map | = { ↦→ () : ∈ 1 ∩ }. An extension of is any map ′ between terms, denoted by ′ ⊇ , such that ′|1 = . A homomorphism from a structure 1 to a structure 2 is any map ℎ : dom(1) → dom(2) such that both the following hold: () if ∈ Δ ∩ dom(1), then ℎ() = ; and () ℎ(1) = { (ℎ(t)) : (t) ∈ 1} ⊆ 2.
A conjunctive query (CQ) over a schema S is a (first-order) formula of the form ⟨x⟩ ← ∃
y Φ(x, y), where x and y are tuples (often seen as sets) of variables such that x ∩ y = ∅, and Φ(x, y) is a conjunction (often seen as a set) of atoms using only predicates from S. In particular, () dom(Φ) ⊆ x ∪ y ∪ Δ , () ∈ x ∪ y implies that occurs in some atom of Φ, () x are the output variables of , and () y are the existential variables of . To highlight the output variables, we may write (x) instead of . The evaluation of over an instance is the set () of every tuple t of constants admitting a homomorphism ℎt from Φ(x, y) to such that ℎt(x) = t. A Boolean conjunctive query (BCQ) is a CQ with no output variable, namely an expression of the form ⟨⟩ ← ∃ y Φ(y). An instance satisfies a BCQ , denoted |= , if () is nonempty, namely () contains only the empty tuple ⟨⟩.
A tuple-generating dependency (TGD) —also known as (existential) rule— over a schema S is a (first-order) formula of the form
Φ(x, y) → ∃ z Ψ(x, z), where x, y, and z are pairwise disjoint tuples of variables, and both Φ(x, y) and Ψ(x, z) are conjunctions (often seen as a sets) of atoms using only predicates from S. In particular, () Φ (resp., Ψ) contains all and only the variables in x ∪ y (resp., x ∪ z), () constants (but not nulls) may also occur in , () x ∪ y are the universal variables of , () z are the existential variables of denoted by var∃( ), and () x are the frontier variables of denoted by front( ). In particular, if var∃( ) = ∅ and |head( )| = 1, then is called datalog rule. We refer to body( ) = Φ and head( ) = Ψ as the body and head of , respectively. With hp( ) (resp., bp( )) we denote the set of predicates in head( ) (resp., body( )). An ontology Σ is a set of rules. Without loss of generality, we assume that vars( 1) ∩ vars( 2) = ∅, for each pair 1, 2 of rules in Σ. Operators var∃, hp, and bp (defined for rules) naturally extend on ontologies. A class of ontologies is any (typically infinite) set of TGDs fulfilling some syntactic or semantic (1) (2) conditions (see, for example, the classes shown in Table 1, some of which will be formally defined in the subsequent sections). In particular, Datalog is the class of ontologies containing only datalog rules. The schema of Σ, denoted sch(Σ), is the subset of S containing all and only the predicates occurring in Σ, whereas arity(Σ) = max ∈sch(Σ) arity( ). For simplicity of exposition, we write pos(Σ) instead of pos(sch(Σ)). An instance satisfies a rule as in Equation 2, written |= , if the existence of a homomorphism ℎ from Φ to implies the existence of a homomorphism ℎ′ ⊇ ℎ|x from Ψ to . An instance satisfies a set Σ of TGDs, written |= Σ, if |= for each ∈ Σ.
Consider a database and a set Σ of TGDs. A model of and Σ is an instance such that ⊇ and |= Σ. Let mods(, Σ) be the set of all models of and Σ. The certain answers to a CQ w.r.t. and Σ are defined as the set of tuples cert(, , Σ) = ⋂︀∈mods(,Σ) ( ). Accordingly, for any fixed schema S, two ontologies Σ1 and Σ2 over S are said S-equivalent (in symbols Σ1 ≡ S Σ2) if, for each and over S, it holds that cert(, , Σ1) = cert(, , Σ2). The pair and Σ satisfies a BCQ , written ∪ Σ |= , if cert(, , Σ) = ⟨⟩, namely |= for each ∈ mods(, Σ). Fix a class of ontologies. The computational problem studied in this work —called CQAns()— can be schematized as follows: given a database , a set Σ ∈ of TGDs, a CQ (x), and a tuple c ∈ ()|x|, does c ∈ cert(, , Σ) hold? In what follows, we informally say that is decidable whenever CQAns() is decidable. Note that c ∈ cert(, , Σ) if, and only if, ∪ Σ |= (c), where (c) is the BCQ obtained from (x) by replacing, for each ∈ {1, ..., |x|}, every occurrence x[] with c[]. Actually, the former problem is AC0 reducible to the latter. Finally, while considering the computational complexity of CQAns(), we recall the following convention: () combined complexity means that , Σ, , and c are given in input; and () data complexity means that only and c are given in input, whereas Σ and are considered fixed.
The chase procedure [
In this section we introduce a novel general condition that allows to define, from any decidable class of ontologies, a new decidable class called Dyadic- enjoying desirable properties. We start with some preliminary notions. Then, we present the new notion of dyadic decomposition. Finally, we conclude with a computational analysis.
This section fixes the basics that are needed to define dyadic decomposable sets, by providing
a uniform notation for key existing notions: afected/invaded positions and
attacked/protected/harmless/harmful/dangerous variables [
Moreover, a position ∈ pos(Σ) is -afected , where ⊆ var∃(Σ), if: 1. for each ∈ , is -afected; and 2. for each ∈ var∃(Σ), if is -afected, then ∈ .
Note that for every position there exists a unique set such that is -afected. We write aff( ) for this set . Moreover, aff(Σ) = { ∈ pos(Σ) | aff( ) ̸= ∅}, and nonaff(Σ) = pos(Σ) ∖ aff(Σ). We can now categorize the variables occurring in a conjunction of atoms with the following definition.
Definition 2.
∙ if occurs at positions 1, . . . , and ⋂︀
=1 aff( ) = ∅, then is harmless, ∙ if is not harmless, placed = ⋂︀
=1 aff( ), then it is -harmful, ∙ if is -harmful and belongs to front( ), then is -dangerous.
Given a variable that is -dangerous, we write dang() for the set . Hereinafter, the prefix - is omitted when it is not necessary. Consider an ontology Σ. Given a rule ∈ Σ, we denote by dang( ) (resp., harmless( ) and harmful( )) the dangerous (resp., harmless and harmful) variables in . These sets of variables naturally extend to the whole Σ by taking, for each of them, the union over all the rules of Σ.
In order to define the notion of Dyadic TGDs, we now introduce the concept of head-ground set of rules, being roughly “non-recursive” rules in which nulls are neither created nor propagated. Definition 3.
1. Σ′ ∈ Datalog; 2. each head atom of Σ′ contains only harmless variables w.r.t. Σ; 3. hp(Σ′) ∩ bp(Σ′) = ∅; 4. hp(Σ′) ∩ hp(Σ ∖ Σ′) = ∅.
The following example is given to better understand the above definition.
Example 1. Consider the next set of rules: → ∃ 1, 1 (1, 1) → (2, 2) → (3, 3) → ∃ 4(4, 4) → (5, 5) A subset of head ground rule w.r.t. Σ is given by ΣHG = { 2, 3}. In fact, harmless(Σ) is the set {1, 1, 2, 2, 2, 3, 3, 3, 5, 5}; hence, it is easy to check that () 2 and 3 are datalog rules; () the head atoms of 2 and 3 contain only harmless variables; () both predicates that appear in head( 2) and head( 3) do not occur in any body of ΣHG, () nor in the head of rules 1, 4 and 5. To the contrary, rules 1, 4 and 5 could not be in ΣHG, since they violate Properties 2 and 3 of Definition 3. Hence, we observe that the set ΣHG is maximal.
Definition 4. Consider a class of TGDs, and a set Σ of TGDs. Let S = sch(Σ). A pair (ΣHG, Σ) of TGDs is a dyadic decomposition of Σ w.r.t. if: 1. ΣHG ∪ Σ ≡ S Σ; 2. Σ ∈ ; 3. ΣHG is head-ground w.r.t. ΣHG ∪ Σ; and 4. the head atoms of ΣHG do not occur in Σ.
Dyadic- is the class of all sets of TGDs that admit a dyadic decomposition w.r.t. . The union of all Dyadic-, with being any decidable class of TGDs, forms what we call dyadic decomposable sets, which encompass and generalize any other existing decidable class, including those based on semantic conditions.
We now provide an example of a Dyadic-Shy ontology, where Shy [
(4) → 4() (5), (5), (5), (5) → 5() and Σ is:
Note that, in general, without any assumption on the specific class , we do not have any concrete means to construct a dyadic decomposition for an arbitrary Dyadic- ontology. Concerning Dyadic-Shy, however, in Section 4, we define a syntactic subclass —called Ward+— for which a dyadic decomposition is (easily) computable.
To provide an algorithm for computing the answers to a query over a database paired with a set Σ ∈ Dyadic-, we are going to exploit the dyadic decomposition (ΣHG, Σ) of Σ w.r.t. . Our idea is to reduce query answering over Dyadic- to query answering over , the latter being decidable by assumption. To this aim, we first “complete" by adding all the “auxiliary” ground consequences of ∪ ΣHG ∪ Σ, contained in the set ′ = { ∈ chase(, ΣHG ∪ Σ) | pred() ∈ hp(ΣHG)}. (3) Let = ∪ ′ be the result of this completion operation. We point out that ′ actually contains only ground atoms, since the atoms generated during the chase procedure that derive from the head rules of ΣHG cannot contain nulls by definition of head-ground rules. Accordingly, we evaluate the query over ∪ Σ. Therefore, to show that Dyadic- is decidable, it sufices to prove that ′ is computable and also that cert(, , Σ) = cert(, , Σ) holds for any CQ . We start by showing the correctness of our reduction. Algorithm 1: Database Completion w.r.t. a fixed decidable class of TGDs Input: A dyadic decomposition (ΣHG, Σ) of Σ w.r.t.
A database
Output: The completed database 1 := 2 ˜ := ∅ 3 for each rule of the form Φ(x, y) → Aux (x) in ΣHG do 4 := ⟨x⟩ ← Φ(x, y) 5 ˜ = ˜ ∪ {Aux (t) | t ∈ cert(, , Σ)} 6 if ( ∪ ˜ ⊃ ) then 7 := ∪ ˜ 8 go to instruction 2 9 return Lemma 1. Fix a decidable class of TGDs. Consider a database , a set Σ ∈ Dyadic- and a conjunctive query (x). Let (ΣHG, Σ) be a dyadic decomposition of Σ w.r.t. and let = ∪ ′, where ′ = { ∈ chase(, ΣHG ∪ Σ) | pred() ∈ hp(ΣHG)}. Then, it holds that cert(, , Σ) = cert(, , Σ).
Proof. Let S = sch(Σ). Since, by hypothesis, (ΣHG, Σ) is a dyadic decomposition of Σ, by Definition 4, it holds that Σ ≡ S ΣHG ∪ Σ. Hence, by definition of S-equivalence, we have cert(, , Σ) = cert(, , ΣHG ∪ Σ) Fix any arbitrary |x|-ary tuple c of constants. From Equation 4, we immediately get that c ∈ cert(, , Σ) if, and only if, c ∈ cert(, , ΣHG ∪ Σ). Thus, let ′ = (c), we now have ∪ Σ |= ′ ⇔ ∪ ΣHG ∪ Σ |= ′.
To show cert(, , Σ) ⊆ cert(, , Σ), it sufices to prove that ∪ Σ |= ′ implies ∪ Σ |= ′. Assume ∪ Σ |= ′ holds. By Equation 5, we know that ∪ ΣHG ∪ Σ |= ′ holds too. Hence, chase(, ΣHG ∪ Σ) |= ′. Since ′ ⊂ chase(, ΣHG ∪ Σ), it holds that chase( ∪ ′, ΣHG ∪ Σ) |= ′. Since ′ contains all the auxiliary ground consequences of ΣHG, the latter becomes equivalent to chase( ∪ ′, Σ) |= ′. Hence, ∪ ′ ∪ Σ |= ′. Since, by hypothesis, = ∪ ′, we finally get that ∪ Σ |= ′.
To show that cert(, , Σ) ⊇ cert(, , Σ) it sufices to prove that if ∪ Σ |= ′, then ∪ Σ |= ′. Assume that ∪ Σ |= ′, hence chase(, Σ) |= ′. Since Σ ⊆ ΣHG ∪ Σ, it holds that chase(, ΣHG ∪ Σ) |= ′. By hypothesis, ′ ⊆ chase(, ΣHG ∪ Σ); hence chase(, ΣHG ∪ Σ) |= ′, that is ∪ ΣHG ∪ Σ |= ′. Applying Equation 5, it holds that ∪ Σ |= ′, and hence the thesis.
With Lemma 1 in place, we now design Algorithm 1 in order to iteratively construct the set = ∪ ′, with ′ being the set defined by Equation 3. Roughly speaking, the first (4) (5) two instructions are required, respectively, to add to and to initialize a temporary set ˜ used to store ground consequences derived from ΣHG. The rest of the algorithm is an iterative procedure that computes the answers (instruction 5) to the queries constructed from the rules of ΣHG (instruction 4) and completes the initial database (instruction 7) until no more auxiliary ground atoms can be produced (instruction 6). We point out that, in general, ⊆ ′ holds; in particular, ˜ = ′ holds in the last execution of instruction 7 or, equivalently, ˜ when the condition ∪ ˜ ⊃ examined at instruction 6 is false, since all the auxiliary ground atoms have been added to . We now prove that Algorithm 1 always terminates and correctly constructs .
Lemma 2. Fix a decidable class of TGDs. Consider a database and a set Σ of Dyadic- TGDs. Let (ΣHG, Σ) be a dyadic decomposition of Σ, and ′ be the set of ground auxiliary atoms defined as { ∈ chase(, ΣHG ∪ Σ) | pred() ∈ hp(ΣHG)}. Then, Algorithm 1 both terminates and computes ∪ ′.
Proof sketch. We split the proof in two parts.
Termination. To prove the termination of Algorithm 1, it sufices to show that each instruction alone always terminates and that the overall procedure never falls into an infinite loop. First, observe that |′| ≤ | hp(ΣHG)| · , where = |const()| and = max ∈hp(ΣHG) arity( ). Instructions 1, 2, 4, 8 and 9 trivially terminates. Instructions 6 and 7 both terminate, since ˜ ⊆ ′ always holds (see correctness below). Each time instruction 3 is reached, the for-loop simply scans the set ΣHG, which is finite by definition. Concerning instruction 5, it sufices to observe that its termination relies on the termination of CQAns() —which is true by hypothesis— and on the fact that, for each query , to construct the set {Aux (t) | t ∈ cert(, , Σ)}, the problem CQAns() must be solved at most times, being the maximum number of tuples t for which the check t ∈ cert(, , Σ) has to be performed. Since each instruction alone terminates, it remains to analyze the overall procedure. It contains two loops. The first, namely the for-loop at instruction 3, is not problematic; indeed, we shown that it locally terminates. The second one, namely the go to-loop, depends on the evaluation of the if-instruction, which can be executed at most |′| times. Thus, also the go to-loop does the same. Correctness. We now claim that Algorithm 1 correctly completes the database. Let be the output of Algorithm 1. Our claim is that = ∪ ′.
Inclusion 1 ( ∪ ′ ⊆ ). Assume, by contradiction, that ∪ ′ contains some atom that does not belong to . This means that there exists some > 0 such that both ¯ = (( ∪ ′) ∩ chase− 1(, ΣHG ∪ Σ)) ⊆ and (( ∪ ′) ∩ chase (, ΣHG ∪ Σ)) ∖ ̸= ∅ hold. Thus, there exists some ∈ chase (, ΣHG ∪ Σ) whose level is exactly and that does not belong to . Let ⟨, ℎ ⟩ be the trigger used by the chase to generate , where is of the form Φ(x, y) → Aux (x). Clearly, ℎ maps Φ(x, y) to chase− 1(, ΣHG ∪ Σ), and we also have that = Aux (ℎ(x)). Consider now the query = ⟨x⟩ ← Φ(x, y) constructed from by Algorithm 1 at instruction 4. Thus, chase− 1(, ΣHG ∪ Σ) |= (ℎ(x)) holds. Since ¯ ⊆ , we have that chase− 1(, ΣHG ∪ Σ) ⊆ chase(¯, Σ) ⊆ chase(, Σ). Hence, chase(, Σ) |= (ℎ(x)), namely ℎ(x) ∈ cert(, , Σ) and, thus, ∈ , which is a contradiction.
Inclusion 2 ( ⊆ ∪ ′). An argument analogous for the fist inclusion can be provided also for this second case. Here we assume, by contradiction, that contains some atom that does not belong to ∪ ′. Let ℓ be the number of time instruction 7 of Algorithm 1 is executed. Let 0 = and, for each ∈ [ℓ], ˜ denote the specific ˜ appearing at instruction 7 the -th time ˜ it is executed. Let = ˜ ∖ − 1, for each ∈ [ℓ]. It can be shown that there exists a sequence ˜ of chase applications leading to chase(, ΣHG ∪ Σ) such that, for each ∈ [ℓ] and for each atom ∈ , is generated via such a chase sequence at a certain level (in general, diferent from ) being strictly greater than the level of every other atom contained in ˜− 1. This is a contradiction since = ∪ ˜ℓ.
It remains to show that Dyadic- is decidable. We rely on Algorithm 1 together with Lemma 2 and Lemma 1 to state the following: Theorem 1. Let be a decidable class of TGDs. Then, Dyadic- is decidable.
We point out that Algorithm 1 does not depend on the technique exploited for performing query answering over the class ; hence, such external techniques can be used like a “black box”. We can now study the complexity of CQAns() for an arbitrary decidable class . Theorem 2. Consider a decidable class of TGDs. Assume that CQAns() is complete in data complexity for a certain complexity class C. The following are true: 1. If C ⊆ PTime, then CQAns(Dyadic-) is in PTime in data complexity; 2. If C ⊇ PTime, then CQAns(Dyadic-) is in PTimeC in data complexity; 3. If C ⊇ PTime is deterministic, then CQAns(Dyadic-) is C-complete in data complexity. Proof sketch. To prove the memberships of point 1 and 2, we rely on the complexity of Algorithm 1. In particular, let be a database, Σ ∈ an ontology, (ΣHG, Σ) a dyadic decomposition of Σ, and ′ the set defined in Equation 3. Moreover, let = |const()| and = max ∈hp(ΣHG) arity( ). Via Lemma 2, we shown that Algorithm 1 always terminates and it correctly constructs the completed database = ∪ ′. In particular, by neglecting the computational cost of the “trivial” instructions (i.e., 1–4 and 6–9), Algorithm 1 overall calls |ΣHG| · | hp(ΣHG)| · 2 times the problem CQAns(). To reach the claimed bounds, first, we observe that is polynomial in . Moreover, since we are in data complexity, the following parameters are bounded: the maximum arity , the size of both ΣHG and Σ, as well as the size and the number of each query constructed at instruction 4. Hence, Algorithm 1 calls polynomially many times CQAns(). Finally, hardnesses of point 3 follow from the fact that for any deterministic class C ⊇ PTime, we know that PTimeC = C, and from the fact that Dyadic- includes the class .
A similar analysis can be performed in combined complexity. Here, however, we need further
assumptions on: () the size of dyadic decompositions being equivalent to the ontologies of
Dyadic-; and () both the data and combined complexity of the class under consideration.
4. Ward+
We start this section recalling the syntactic condition of the class Ward [
We now formally introduce the syntactic condition that gives rise to the class Ward+ generalizing the well-known decidable classes Shy and Ward, and being included in Dyadic-Shy. Intuitively, the condition can be explained as follows. If is a ward+rule, then body( ) can be partitioned into two sets of atoms, 1 and 2, that share only harmless variables (see Figure 1(a)). Having in mind the notion of wardedness, the set 1 can be seen as a “multi-ward" that contains all the dangerous variables and that, at the same time, satisfies the shyness conditions. The set 2, instead, is any atoms conjunction that can share with 1 only harmless variables. More formally, a set of ward+ TGDs is defined as follows.
Definition 5. A set Σ of TGDs is ward+ if, for each TGD ∈ Σ, there are no dangerous variables in body( ), or there exists a partition {1, 2} of body( ) such that: 1. 1 contains all the dangerous variables 2. vars(1) ∩ vars(2) are harmless variables 3. for every pair of distinct dangerous variable and in diferent atoms, dang() ∩ dang() = ∅ 4. for every pair of distinct atoms , ∈ 1, vars() ∩ vars() are harmless variables. We write Ward+ for the class of all finite ward + sets of TGDs.
Below we propose an example of an ontology that is in Ward+and an example of one that does not belong to Ward+, respectively.
Example 3. Consider the ontology Σ of Example 2. It easy to see that 1, 2, 3 and 4 are
trivially ward+ rules w.r.t. Σ, since they are rules with one single body atom, which cannot
violate any conditions of Definition 5. Let us focus on rule 5. Since dang( 5) = {5, 5},
harmful( 5) = {5} and harmless( 5) = ∅, there exists a partition of body( 5) into two set
1, 2, that satisfies Definition 5, where, 1 = { (5), (5)} and 2 = { (5), (5)}.
Hence, Σ ∈ Ward+.
Example 4. Let Σ be the following set of TGDs:
1 : (1) → ∃ 1 (1)
2 : (2) → ∃ 2, 2 (2, 2, 2)
3 : (3, 3, 3), (3) → (3, 3, 3)
We pay particular attention to rule 3, since as previously explained, rules 1 and 2, that
have only one body atom, do not go against the definition of ward + rule. Here, Condition 4 of
Definition 5 is violated, since there is a join on variable 3 that appears at positions [
Now we show that Ward+ strictly includes both Shy and Ward. According to Definition 5, the class Ward trivially coincides with the class Ward+ if |1| = 1; thus, Ward ⊆ Ward+. On the other hand, if |2| = ∅, we have that Shy ⊆ Ward+, since the “multi-ward" satisfies the shyness conditions. We show that the latter relations are strict inclusions presenting a set of TGDs that belongs to Ward+, but it is not both in Shy and Ward.
Example 5. Let Σ be the ontology introduced in Example 2. It is easy to see that 1, 2, 3 and 4 are both shy and warded rules w.r.t. Σ, since they are rules with one single body atom, which cannot violate any condition of the classes under consideration. However, rule 5 ∈/ Ward, since the dangerous variables 5 and 5 are not contained in a single ward, and 5 ∈/ Shy, since there is a join on the variable 5 that is 2-harmful. Hence, Σ ∈ Ward+(see Example 3), but Σ ̸∈ Shy and Σ ̸∈ Ward.
Accordingly, it follows the next result.
Theorem 3. Ward+ ⊃ Shy ∪ Ward.
To show that Ward+⊂ Dyadic-Shy, we have to prove the existence of a dyadic decomposition (ΣHG, Σ ) for every set Σ of ward+ TGDs. Intuitively, the construction of a dyadic decomposition for a ward+ set of TGDs takes advantage of the structure of a ward+ rule. Indeed, by definition, a ward + rule can be always partitioned into two sets 1 and 2 of atoms, where 1 is a conjunction of atoms that satisfies the shyness conditions, and 2 is any atom conjunction. Roughly speaking, starting from a rule ∈ Ward+, a rule in ΣHG has the same body of , while the head contains a “fresh" atom in which are propagated only harmless variables; this last atom, with the set 1, is used to construct the body of a rule in Σ , while the head contains the same atoms of head( ) (see Example 2). Now, we formally prove the existence of a dyadic decomposition for a ward+ set Σ of TGDs with respect to Shy.
Theorem 4. For every Σ ∈ Ward+, there is a dyadic decomposition (ΣHG, Σ ) of Σ w.r.t. Shy. Proof. Let Σ be a set of ward+ TGDs. To show the existence of a dyadic decomposition (ΣHG, Σ ) of Σ w.r.t. Shy, we propose the following procedure. Consider a ward+ rule : Φ(x, y, z), Ψ(z, u) → ∃ w Ξ(x, w, z), where x, y, z, u are pairwise disjoint, Φ(x, y, z), Ψ(z, u) and Ξ(x, w, z) are conjunctions of atoms such that Φ(x, y, z) = 1 and Ψ(z, u) = 2 (according to Definition 5). Moreover, dang( ) = {x}, harmless( ) = {z} and harmful( ) = {x, u, y}. Let = |head( )|, then we produce + 2 rules ′( ), ′0′( ), . . . , ′′ ( ) such that: where v ⊆ { x, w, z} for each ∈ {1, . . . , }, {1(v1), . . . , (v )} = Ξ(x, w, z) and ′ , ′′ are fresh auxiliary predicates.
Now, we prove that (ΣHG, Σ ) is a dyadic decomposition for any ward+ set of TGDs w.r.t. Shy, where ΣHG = ⋃︁ ′( ) ∈Σ and Σ =
⋃︁ ∈Σ ∧ 0≤ ≤ ′′( ).
According to Definition 4, the pair (ΣHG, Σ ) has to satisfies four properties. Property 4 is trivially fulfilled: head predicates of ΣHG do not occur in Σ, since, by construction, ′ is a fresh auxiliary predicate introduced for each ∈ Σ. Property 3 states that the set ΣHG is head-ground w.r.t. ΣHG ∪ Σ . This is true since, by construction, we have that: for each ∈ Σ, ′( ) is a datalog rule; hp(ΣHG) = {′ : ∈ Σ}, where each ′ is a predicate that does not occur neither in any body of ΣHG nor in any head of Σ (i.e., hp(Σ′) ∩ bp(Σ′) = ∅, and hp(Σ′) ∩ hp(Σ ∖ Σ′) = ∅), and it contains only harmless variable. Now, we have to prove that Property 2 holds, i.e., Σ ∈ Shy. This is ensured by the fact that rule ′0′( ) is made by joining the set 1 of (that has to satisfy the shyness conditions by definition), and the atom ′ , which contains only harmless variables, and hence, cannot violate any of the shyness conditions; moreover, each rule ′′( ), for = 1, . . . , , is linear, and therefore is a shy rule. Finally, Property 1, that is ΣHG ∪ Σ ≡ sch(Σ) Σ, follows by construction.
Finally —by combining Theorem 2, Theorem 4, the fact that CQAns is PTime-complete (resp., ExpTime-complete) for both Shy and Ward in data (resp., combined) complexity, and the fact that Ward+ admits dyidic decompositions of polynomial size— we can state the following result. Theorem 5. The following are true: 1. Ward+⊆ Dyadic-Shy; 2. CQAns is PTime-complete in data complexity over Ward+, Dyadic-Shy and Dyadic-Ward; 3. CQAns is ExpTime-complete in combined complexity over Ward+.
Dyadic decomposable sets form a novel decidable class of TGDs that encompasses and generalizes all the existing (syntactic and semantic) decidable classes of TGDs. In the near feature, it would be interesting to identify more syntactic Dyadic- fragments —such as Ward+with respect to Dyadic-Shy— for which a dyadic decomposition can be easily computed. Moreover, our plan is to implement Algorithm 1 to perform query answering by exploiting existing reasoners.