=Paper=
{{Paper
|id=Vol-3203/paper6
|storemode=property
|title=Dyadic Existential Rules
|pdfUrl=https://ceur-ws.org/Vol-3203/paper6.pdf
|volume=Vol-3203
|authors=Georg Gottlob,Marco Manna,Cinzia Marte
|dblpUrl=https://dblp.org/rec/conf/datalog/GottlobMM22
}}
==Dyadic Existential Rules==
<pdf width="1500px">https://ceur-ws.org/Vol-3203/paper6.pdf</pdf>
<pre>
Dyadic Existential Rules
Georg Gottlob1,2,† , Marco Manna3,† and Cinzia Marte3,*,†
1
  Department of Computer Science, University of Oxford, United Kingdom
2
  Faculty of Informatics, TU Wien, Austria
3
  Department of Mathematics and Computer Science, University of Calabria, Italy


                                         Abstract
                                         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 different
                                         syntactic conditions imposing the development of different 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.

                                         Keywords
                                         Existential rules, Datalog, ontology-based query answering, tuple-generating dependencies, computa-
                                         tional complexity.




1. Introduction
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 [1] and
Existential Rules (a.k.a. tuple generating dependencies) [2] are the main languages used to
specify ontologies. In particular, the latter are essentially classical datalog rules extended with
existential quantified variables in rule-heads. The presence of existential quantification in the
head of rules, however, makes query answering undecidable in the general case. To overcome
this limitation, in the last two decades, a number of classes of existential rules —based on
both semantic and syntactic conditions— that guarantee the decidability of query answering
have been proposed. Concerning the semantic conditions, we recall finite expansions sets, finite
treewidth sets, finite unification sets, and strongly parsimonious sets [3, 2, 4]. Each of these classes

Datalog 2.0 2022: 4th International Workshop on the Resurgence of Datalog in Academia and Industry, September 05,
2022, Genova - Nervi, Italy
*
  Corresponding author.
†
  These authors contributed equally.
$ georg.gottlob@cs.ox.ac.uk (G. Gottlob); manna@mat.unical.it (M. Manna); marte@mat.unical.it (C. Marte)
 0000-0002-2353-5230 (G. Gottlob); 0000-0003-3323-9328 (M. Manna); 0000-0003-3920-8186 (C. Marte)
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)



                                                                                                          83
Georg Gottlob et al. CEUR Workshop Proceedings                                                83–96


           Main syntactic classes         Data Complexity         Combined Complexity
           Weakly-(Fr)-Guarded [5, 6]      ExpTime-complete           2ExpTime-complete
           (Fr)-Guarded [6]                 PTime-complete            2ExpTime-complete
           Weakly-Acyclic [7]               PTime-complete            2ExpTime-complete
           Jointly-Acyclic [8]              PTime-complete            2ExpTime-complete
           Datalog [9]                      PTime-complete             ExpTime-complete
           Shy, Ward [4, 10]                PTime-complete             ExpTime-complete
           Protected [11]                   PTime-complete             ExpTime-complete
           Sticky-(Join) [12, 13]                AC0                   ExpTime-complete
           Linear, Joinless [14, 15]             AC0                    PSpace-complete
           Inclusion-Dependencies [16]           AC0                    PSpace-complete
Table 1
Computational complexity of query answering over the main concrete classes of existential rules.


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 different syntactic conditions imposes the
development of different 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.


2. Preliminaries
2.1. Basics on Relational Structures
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



                                                 84
Georg Gottlob et al. CEUR Workshop Proceedings                                               83–96


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 .

2.2. Conjunctive Queries
A conjunctive query (CQ) 𝑞 over a schema S is a (first-order) formula of the form

                                       ⟨x⟩ ← ∃ y Φ(x, y),                                       (1)

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 ⟨⟩.

2.3. Tuple-Generating Dependencies
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),                                      (2)

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



                                                 85
Georg Gottlob et al. CEUR Workshop Proceedings                                                 83–96


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 𝜎 ∈ Σ.

2.4. Ontological Query Answering
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.

2.5. The Chase Procedure
The chase procedure [17] is a tool exploited for reasoning with TGDs. Consider a database 𝐷 and
a set Σ of TGDs. Given an instance 𝐼 ⊇ 𝐷, a trigger for 𝐼 is any pair ⟨𝜎, ℎ⟩, where 𝜎 ∈ Σ is a rule
as in Equation 2 and ℎ is a homomorphism from body(𝜎) to 𝐼. Let 𝐼 ′ = 𝐼 ∪ ℎ′ (head(𝜎)), where
ℎ′ ⊇ ℎ|x maps each 𝑧 ∈ var∃ (𝜎) to a “fresh” null ℎ′ (𝑧) not occurring in 𝐼 such that 𝑧1 ̸= 𝑧2 in
var∃ (𝜎) implies ℎ′ (𝑧1 ) ̸= ℎ′ (𝑧2 ). Such an operation which constructs 𝐼 ′ from 𝐼 is called chase
step and denoted ⟨𝜎, ℎ⟩(𝐼) = 𝐼 ′ . The chase procedure of 𝐷 ∪ Σ is an exhaustive application of
chase steps, starting from 𝐷, which produce a sequence 𝐼0 = 𝐷 ⊂ 𝐼1 ⊂ 𝐼2 ⊂ · · · ⊂ 𝐼𝑚 ⊂ . . .
of instances in such a way that: (𝑖) for each 𝑖 ≥ 0, 𝐼𝑖+1 = ⟨𝜎, ℎ⟩(𝐼𝑖 ) is a chase step obtained via
some trigger ⟨𝜎, ℎ⟩ for 𝐼𝑖 ; (𝑖𝑖) for each 𝑖 ≥ 0, if there exists a trigger ⟨𝜎, ℎ⟩ for 𝐼𝑖 , then there
exists some 𝑗 > 𝑖 such that 𝐼𝑗 = ⟨𝜎, ℎ⟩(𝐼𝑗−1 ) is a chase step; and (𝑖𝑖𝑖) any trigger ⟨𝜎, ℎ⟩ is used
only once. We define chase(𝐷, Σ) = ∪𝑖≥0 𝐼𝑖 . It is well know that chase(𝐷, Σ) is a universal
model of 𝐷 ∪ Σ, that is, for each 𝑀 ∈ mods(𝐷, Σ) there is a homomorphism from chase(𝐷, Σ)
to 𝑀 . Hence, given a BCQ 𝑞 it holds that chase(𝐷, Σ) |= 𝑞 ⇔ 𝐷 ∪ Σ |= 𝑞. Finally, we recall
that chase(𝐷, Σ) can be decomposed into levels [12]: each atom of 𝐷 has level 𝛾 = 0; an atom



                                                 86
Georg Gottlob et al. CEUR Workshop Proceedings                                             83–96


of chase(𝐷, Σ) has level 𝛾 + 1 if, during its generation, the exploited trigger ⟨𝜎, ℎ⟩ maps the
body of 𝜎 via ℎ to atoms whose maximum level is 𝛾. We refer to the part of the chase up to
level 𝛾 as chase𝛾 (𝐷, Σ). Clearly, chase(𝐷, Σ) = ∪𝛾>0 chase𝛾 (𝐷 ∪ Σ).


3. Dyadic Decomposable Sets
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.

3.1. Preliminary Notions
This section fixes the basics that are needed to define dyadic decomposable sets, by providing
a uniform notation for key existing notions: affected/invaded positions and attacked/protect-
ed/harmless/harmful/dangerous variables [4, 6, 18, 19]. Basically, these notions serve to separate
positions in which the chase can introduce only constants from those where nulls might appear.

Definition 1. Consider an ontology Σ and a variable 𝑧 ∈ var∃ (Σ). A position 𝜋 ∈ pos(Σ) is
said to be 𝑧-affected (or invaded by 𝑧) if one of the following two properties holds:
   1. there exists 𝜎 ∈ Σ such that 𝑧 appears in the head of 𝜎 at position 𝜋;
   2. there exist 𝜎 ∈ Σ and 𝑥 ∈ front(𝜎) such that 𝑥 occurs both in head(𝜎) at position 𝜋 and
      in body(𝜎) at 𝑧-affected positions only.
Moreover, a position 𝜋 ∈ pos(Σ) is 𝑆-affected, where 𝑆 ⊆ var∃ (Σ), if:
   1. for each 𝑧 ∈ 𝑆, 𝜋 is 𝑧-affected; and
   2. for each 𝑧 ∈ var∃ (Σ), if 𝜋 is 𝑧-affected, then 𝑧 ∈ 𝑆.

Note that for every position 𝜋 there exists a unique set 𝑆 such that 𝜋 is 𝑆-affected. 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. Given a TGD 𝜎 ∈ Σ and a variable 𝑥 in body(𝜎):

   ∙ 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 Σ.




                                                 87
Georg Gottlob et al. CEUR Workshop Proceedings                                                            83–96


3.2. Dyadic TGDs
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. Consider a set Σ of TGDs. A set Σ′ ⊆ Σ is head-ground w.r.t. Σ if:
   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 , 𝑤1 𝑄(𝑧1 , 𝑤1 )
                        𝜎2 :    𝐶(𝑦2 ), 𝑅(𝑥2 , 𝑧2 )         →    𝑆(𝑦2 , 𝑧2 )
                        𝜎3 : 𝐷(𝑦3 , 𝑧3 ), 𝑅(𝑥3 , 𝑤3 )       →    𝑇 (𝑥3 , 𝑦3 )
                        𝜎4 :              𝑄(𝑥4 , 𝑦4 )       →    ∃ 𝑧4 𝐴(𝑥4 , 𝑧4 )
                        𝜎5 : 𝐴(𝑥5 , 𝑧5 ), 𝐷(𝑦5 , 𝑧5 )       →    𝑄(𝑥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.
   We are now ready to formally introduce the class Dyadic-𝒞.
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] is a known decidable
class. Before that, we recall the syntactic conditions underlying this class. A set Σ of TGDs is
shy if, for each 𝜎 ∈ Σ the following conditions both hold: (𝑖) if a variable 𝑥 occurs in more
than one body atom, then 𝑥 is harmless; (𝑖𝑖) for every pair of distinct dangerous variable 𝑧 and
𝑤 in different atoms, dang(𝑧) ∩ dang(𝑤) = ∅. The class of all shy ontologies is called Shy.



                                                       88
Georg Gottlob et al. CEUR Workshop Proceedings                                                83–96


Example 2. Let consider the following set Σ of TGDs:

                      𝜎1 :                       𝑅(𝑥1 , 𝑦1 )     →    ∃ 𝑧1 𝑇 (𝑧1 )
                      𝜎2 :                       𝑅(𝑥2 , 𝑦2 )     →    ∃ 𝑧2 𝑉 (𝑧2 )
                      𝜎3 :                       𝑆(𝑥3 , 𝑦3 )     →    ∃ 𝑧3 𝑃 (𝑧3 )
                      𝜎4 :                           𝑉 (𝑥4 )     →    𝑄(𝑥4 )
                      𝜎5 : 𝑇 (𝑥5 ), 𝑃 (𝑦5 ), 𝑉 (𝑧5 ), 𝑄(𝑧5 )     →    𝑈 (𝑥5 , 𝑦5 )

where harmless(Σ) = {𝑥1 , 𝑦1 , 𝑥2 , 𝑦2 , 𝑥3 , 𝑦3 }, harmful(Σ) = {𝑥4 , 𝑥5 , 𝑦5 , 𝑧5 }, and dang(Σ) =
{𝑥4 , 𝑥5 , 𝑦5 }. A dyadic decomposition of Σ w.r.t. Shy is given by (ΣHG , Σ𝒮 ), where ΣHG is:

                                              𝑅(𝑥1 , 𝑦1 )   →    𝐴𝑢𝑥1 (𝑥1 , 𝑦1 )
                                              𝑅(𝑥2 , 𝑦2 )   →    𝐴𝑢𝑥2 (𝑥2 , 𝑦2 )
                                              𝑆(𝑥3 , 𝑦3 )   →    𝐴𝑢𝑥3 (𝑥3 , 𝑦3 )
                                                  𝑉 (𝑥4 )   →    𝐴𝑢𝑥4 ()
                        𝑇 (𝑥5 ), 𝑃 (𝑦5 ), 𝑉 (𝑧5 ), 𝑄(𝑧5 )   →    𝐴𝑢𝑥5 ()

and Σ𝒮 is:
                                      𝐴𝑢𝑥1 (𝑥1 , 𝑦1 )       →   ∃ 𝑧1 𝑇 (𝑧1 )
                                      𝐴𝑢𝑥2 (𝑥2 , 𝑦2 )       →   ∃ 𝑧2 𝑉 (𝑧2 )
                                      𝐴𝑢𝑥3 (𝑥3 , 𝑦3 )       →   ∃ 𝑧3 𝑃 (𝑧3 )
                                    𝑉 (𝑥4 ), 𝐴𝑢𝑥4 ()        →   𝑄(𝑥4 )
                            𝑇 (𝑥5 ), 𝑃 (𝑦5 ), 𝐴𝑢𝑥5 ()       →   𝑈 (𝑥5 , 𝑦5 )
According to the above decomposition, the considered set Σ is Dyadic-Shy.
  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.

3.3. Decidability and Complexity
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 suffices
to prove that 𝐷′ is computable and also that cert(𝑞, 𝐷, Σ) = cert(𝑞, 𝒟, Σ𝒞 ) holds for any CQ 𝑞.
We start by showing the correctness of our reduction.



                                                   89
Georg Gottlob et al. CEUR Workshop Proceedings                                             83–96


 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 ∪ Σ𝒞 )                             (4)

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 ∪ Σ𝒞 |= 𝑞 ′ .                             (5)

  To show cert(𝑞, 𝐷, Σ) ⊆ cert(𝑞, 𝒟, Σ𝒞 ), it suffices 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 suffices 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



                                                 90
Georg Gottlob et al. CEUR Workshop Proceedings                                                83–96


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 suffices 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 suffices 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 𝐷      ¯ =
        ′          𝑗−1                                    ′         𝑗
((𝐷 ∪ 𝐷 ) ∩ chase (𝐷, Σ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
                                                                                    ¯ ⊆ 𝒟, we
Algorithm 1 at instruction 4. Thus, chase𝑗−1 (𝐷, ΣHG ∪ Σ𝒞 ) |= 𝑞(ℎ(x)) holds. Since 𝐷
                𝑗−1                           ¯
have that chase (𝐷, Σ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



                                                 91
Georg Gottlob et al. CEUR Workshop Proceedings                                                 83–96


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, different
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 Al-
gorithm 1. In particular, let 𝐷 be a database, Σ ∈ 𝒞 an ontology, (ΣHG , Σ𝒞 ) a dyadic de-
composition 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 [10, 19], useful for
the comprehension of the new class Ward+ that we will introduce below. We point out that



                                                 92
Georg Gottlob et al. CEUR Workshop Proceedings                                             83–96




                             (a)                                      (b)

Figure 1: (a)Structure of a ward+ rule. (b)Syntactical relation among classes.


we state the wardedness condition according to Definition 2; hence, the class Ward presented
here is actually larger than the original one. A set Σ of TGDs is warded if, for each 𝜎 ∈ Σ,
there are no dangerous variables in body(𝜎), or there exists an atom 𝛼 ∈ body(𝜎), called a
ward, such that:(𝑖) all the dangerous variables in body(𝜎) occur in 𝛼, and (𝑖𝑖) each variable of
vars(𝛼) ∩ vars(body(𝜎) ∖ {𝛼}) is harmless. The class of all warded ontologies is called Ward.
   We now formally introduce the syntactic condition that gives rise to the class Ward+ gen-
eralizing 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 different 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+ .



                                                  93
Georg Gottlob et al. CEUR Workshop Proceedings                                             83–96


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 𝑅[2] and
𝑆[1], both 𝑦1 -affected.
  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 decompo-
sition 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:



                                                 94
Georg Gottlob et al. CEUR Workshop Proceedings                                                  83–96


                     𝜌′ (𝜎) : Φ(x, y, z), Ψ(z, u) → 𝐴𝑢𝑥′𝜎 (z)
                     𝜌′′0 (𝜎) : Φ(x, y, z), 𝐴𝑢𝑥′𝜎 (z) → ∃ w 𝐴𝑢𝑥′′𝜎 (x, w, z)
                     𝜌′′1 (𝜎) :      𝐴𝑢𝑥′′𝜎 (x, w, z) → 𝑎1 (v1 )
                            ..
                             .
                   𝜌′′𝑚𝜎 (𝜎) :            𝐴𝑢𝑥′′𝜎 (x, w, z) → 𝑎𝑚𝜎 (v𝑚𝜎 )
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+ .


5. Conclusion
Dyadic decomposable sets form a novel decidable class of TGDs that encompasses and general-
izes 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 re-
spect 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.




                                                      95
Georg Gottlob et al. CEUR Workshop Proceedings                                                83–96


References
 [1] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (Eds.), The
     Description Logic Handbook: Theory, Implementation, and Applications, Cambridge
     University Press, 2003.
 [2] J. Baget, M. Leclère, M. Mugnier, E. Salvat, On rules with existential variables: Walking
     the decidability line, Artif. Intell. 175 (2011) 1620–1654.
 [3] J. Baget, M. Leclère, M. Mugnier, E. Salvat, Extending decidable cases for rules with
     existential variables, in: IJCAI, 2009, pp. 677–682.
 [4] N. Leone, M. Manna, G. Terracina, P. Veltri, Fast query answering over existential rules,
     ACM Trans. Comput. Log. 20 (2019) 12:1–12:48.
 [5] J.-F. Baget, M. Leclère, M.-L. Mugnier, Walking the decidability line for rules with existential
     variables., KR 10 (2010) 466–476.
 [6] A. Calì, G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive
     relational constraints, J. Artif. Intell. Res. 48 (2013) 115–174.
 [7] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: semantics and query answering,
     Theoretical Computer Science 336 (2005) 89–124.
 [8] M. Krötzsch, S. Rudolph, Extending decidable existential rules by joining acyclicity and
     guardedness, in: IJCAI, IJCAI/AAAI, 2011, pp. 963–968.
 [9] S. Ceri, G. Gottlob, L. Tanca, What you always wanted to know about datalog (and never
     dared to ask), IEEE Trans. Knowl. Data Eng. 1 (1989) 146–166.
[10] G. Gottlob, A. Pieris, Beyond SPARQL under OWL 2 QL entailment regime: Rules to the
     rescue, in: IJCAI, AAAI Press, 2015, pp. 2999–3007.
[11] T. Baldazzi, L. Bellomarini, M. Favorito, E. Sallinger, On the relationship between shy and
     warded datalog+/-, CoRR abs/2202.06285 (2022).
[12] A. Calì, G. Gottlob, A. Pieris, Advanced processing for ontological queries, Proceedings of
     the VLDB Endowment 3 (2010) 554–565.
[13] A. Calì, G. Gottlob, A. Pieris, Query answering under non-guarded rules in datalog+/-, in:
     RR, volume 6333 of LNCS, Springer, 2010, pp. 1–17.
[14] A. Calì, G. Gottlob, T. Lukasiewicz, A general datalog-based framework for tractable query
     answering over ontologies, J. Web Semant. 14 (2012) 57–83.
[15] T. Gogacz, J. Marcinkowski, Converging to the chase - A tool for finite controllability,
     volume 83, 2017, pp. 180–206.
[16] D. S. Johnson, A. C. Klug, Testing containment of conjunctive queries under functional
     and inclusion dependencies, J. Comput. Syst. Sci. 28 (1984) 167–189.
[17] A. Deutsch, A. Nash, J. B. Remmel, The chase revisited, in: PODS, ACM, 2008, pp. 149–158.
[18] M. Krötzsch, S. Rudolph, Extending decidable existential rules by joining acyclicity and
     guardedness, in: IJCAI, IJCAI/AAAI, 2011, pp. 963–968.
[19] G. Berger, G. Gottlob, A. Pieris, E. Sallinger, The space-efficient core of vadalog, volume 47,
     2022, pp. 1:1–1:46.




                                                 96

</pre>