=Paper=
{{Paper
|id=Vol-2037/paper31
|storemode=property
|title=Querying Finite or Arbitrary Models? No matter! Existential Rules May Rely on Both Once Again (Discussion Paper)
|pdfUrl=https://ceur-ws.org/Vol-2037/paper_31.pdf
|volume=Vol-2037
|authors=Giovanni Amendola,Nicola Leone,Marco Manna
|dblpUrl=https://dblp.org/rec/conf/sebd/AmendolaLM17
}}
==Querying Finite or Arbitrary Models? No matter! Existential Rules May Rely on Both Once Again (Discussion Paper)==
https://ceur-ws.org/Vol-2037/paper_31.pdf
Querying finite or arbitrary models? No matter!
Existential rules may rely on both once again?
(discussion paper)
Giovanni Amendola1 , Nicola Leone2 , and Marco Manna2
1 School of Informatics, University of Edinburgh, UK
gamendol@exseed.ed.ac.uk
2 DeMaCS, University of Calabria, Italy
{leone,manna}@mat.unical.it
Abstract. Ontology-based query answering asks whether a Boolean query is
satisfied by all models of a logical theory consisting of an extensional database
paired with an ontology. The introduction of existential rules (i.e., Datalog rules
extended with existential quantifiers in rule-heads) as a means to specify the on-
tology gave birth to Datalog+/-, a framework that has received increasing atten-
tion in the last decade, with focus also on decidability and finite controllability
to support effective reasoning. Five basic decidable fragments have been singled
out: linear, weakly-acyclic, guarded, sticky, and shy. For all these fragments, ex-
cept shy, the important property of finite controllability has been proved, ensuring
that a query is satisfied by all models of the theory iff it is satisfied by all its finite
models. In this paper we complete the picture by showing that finite controlla-
bility holds also for shy ontologies. The demonstration is based on a number of
technical tools which could be used for similar purposes and are valuable per se.
1 Introduction
The problem of answering a Boolean query q against a logical theory consisting of
an extensional database D paired with an ontology Σ is attracting the increasing at-
tention of scientists in various fields of Computer Science, ranging from Artificial In-
telligence [12, 17] to Database Theory [19, 5] and Logic [4, 20]. This problem, called
ontology-based query answering (OBQA) [8], is usually stated as D ∪ Σ |= q, and it is
equivalent to checking whether q is satisfied by all models of D ∪ Σ according to the
standard approach of first-order logics, yielding an open world semantics.
Description Logics [2] and Datalog± [7] have been recognized as the two main
families of formal knowledge representation languages to specify Σ , while union of
(Boolean) conjunctive queries, U(B)CQs for short, is the most common and studied
formalism to express q. For both these families, OBQA is generally undecidable (see,
[22] and [6], respectively). Hence, a number of syntactic decidable fragments of the
above ontological languages have been singled out. However, decidability alone is not
? The paper has been partially supported by the MISE under project “PIUCultura – Paradigmi
Innovativi per l’Utilizzo della Cultura” (n. F/020016/01-02/X27), and under project “Smarter
Solutions in the Big Data World (S2BDW)”.
guarded shy weakly-acyclic sticky
linear datalog joinless
inclusion-dependencies
Fig. 1. Taxonomy of the basic Datalog± classes.
the only desideratum. For example, a good balance between computational complexity
and expressive power is, without any doubt, of high importance too. But there is another
property that is turning out to be as interesting as challenging to prove: it goes under
the name of finite controllability [23]. An ontological fragment F is said to be finitely
controllable if, for each triple hD, Σ , qi with Σ ∈ F, it holds that D ∪ Σ 6|= q implies
that there exists a finite model M of D ∪ Σ such that M 6|= q. This is usually stated as
D ∪ Σ |= q if, and only if, D ∪ Σ |=fin q (where |=fin stands for entailment under finite
models), as the “only if” direction is always trivially true. And there are contexts, like
in databases [23, 4], in which reasoning with respect to finite models is preferred.
In this paper we focus on the Datalog± family, which has been introduced with the
aim of “closing the gap between the Semantic Web and databases” [9] to provide the
Web of Data with scalable formalisms that can benefit from existing database technolo-
gies. In fact, Datalog± generalizes two well-known subfamilies of Description Log-
ics called EL and DL-Lite, which collect the basic tractable languages for OBQA in
the context of the Semantic Web and databases. In particular, we consider ontologies
where Σ is a set of existential rules, each of which is a first-order formula ρ of the form
∀X∀Y(φ (X, Y) → ∃Zp(X, Z)), where the body φ (X, Y) of ρ is a conjunction of atoms,
and the head p(X, Z) of ρ is a single atom.
The main decidable Datalog± fragments rely on the following five syntactic prop-
erties: weak-acyclicity [15], guardedness [6], linearity [9], stickiness [10], and shy-
ness [21]. And these properties underlie the basic classes of existential rules called
weakly-acyclic, guarded, linear, sticky, and shy, respectively. Several variants and com-
binations of these classes have been defined and studied too [11, 13, 18], as well as
semantic properties subsuming the syntactic ones [3, 21].
The five basic classes above are pairwise uncomparable, except for linear which is
strictly contained in both guarded and shy, as depicted in Figure 1. Interestingly, both
weakly-acyclic and shy strictly contain datalog —the well-known class collecting sets
of rules of the form ∀X∀Y(φ (X, Y) → p(X)), where existential quantification has been
dropped. Moreover, sticky strictly contains joinless —the class collecting sets of rules
where each body contains no repeated variable. The latter, introduced by Gogacz and
Marcinkowski [16] to prove that sticky is finitely controllable, plays a central role also
in this paper. Finally, both linear and joinless strictly contain inclusion-dependencies —
the well-known class of relational database dependencies collecting sets of rules with
one single body atom and no repeated variable.
Under arbitrary models, OBQA can be reduced to the problem of answering q over
a universal (or canonical) model U that can be homomorphically embedded into every
other model (both finite and infinite) of D ∪ Σ . Therefore, D ∪ Σ |= q if, and only if,
U |= q. A way to compute a universal model is to employ the so called chase procedure.
Starting from D, the chase “repairs” violations of rules by repeatedly adding new atoms
—introducing fresh values, called nulls, whenever required by an existential variable—
until a fixed-point satisfying all rules is reached. In the classical setting, the chase is
therefore sound and complete. But when finite model reasoning ( |=fin ) is required, then
the chase is generally uncomplete, unless ontologies are finitely controllable. Hence,
proving this property is of utmost importance, especially in contexts where finite model
reasoning is relevant, like for databases [23, 4].
Finite controllability of weakly-acyclic comes for free since every ontology here
admits a finite universal model, computed by a variant of the chase procedure which
goes under the name of restricted chase [15]. Conversely, the proof of this property for
the subsequent three classes has been a very different matter. Complex, yet intriguing,
constructions have been devised for linear [23, 4], guarded [4], and more recently for
sticky [16]. To complete the picture, we have addressed the same problem for shy and
get the following positive result, which is the main contribution of the paper.
Theorem 1. Under shy ontologies, D ∪ Σ |= q if, and only if, D ∪ Σ |=fin q.
For the proof, we design (in Section 3) and exploit (in Section 4) three key technical
tools that we consider rather general and that we believe can be useful in the future for
similar, or even more general, purposes. In particular, the first (canonical rewriting) and
the third one (well-supported finite models) are applicable to every set of existential
rules, besides shy ontologies. Finally, we exploit the fact that joinless sets of existential
rules are finitely controllable [16]. (Full constructions and proofs are reported in [1].)
2 Ontology-Based Query Answering
Basics. Let C, N and V denote pairwise disjoint discrete sets of constants, nulls and
variables, respectively. An element t of T = C ∪ N ∪ V is called term. An atom is a
labeled tuple p(t1 , . . . ,tm ), where p is a predicate symbol, m is the arity, and t1 , . . . ,tm are
terms. An atom is simple if it contains no repeated term. We also consider propositional
atoms, which are simple atoms of arity 0 written without brackets. Given two sets A
and B of atoms, a homomorphism from A to B is a mapping h : T → T such that c ∈ C
implies h(c) = c, and also p(t1 , . . . ,tm ) ∈ A implies p(h(t1 ), . . . , h(tm )) ∈ B. As usual,
h(A) = {p(h(t1 ), . . . , h(tm )) : p(t1 , . . . ,tm ) ∈ A} ⊆ B. An instance I is a discrete set of
atoms where each term is either a constant or a null.
Syntax. A database D is a finite null-free instance. An (existential) rule ρ is a first-
order formula ∀X∀Y(φ (X, Y) → ∃Zp(X, Z)), where body(ρ) = φ (X, Y) is a conjunc-
tion of atoms, and head(ρ) = p(X, Z) is an atom. Constants may occur in ρ. If Z = 0, /
then ρ is datalog rule. An ontology Σ is a set of rules. A union of Boolean conjunctive
query (UBCQ) q is a first-order expression of the form ∃Y1 ψ1 (Y1 ) ∨ . . . ∨ ∃Yk ψk (Yk ),
where each ψ j (Y j ) is a conjunction of atoms. Constants may occur also in q. In case
k = 1, then q is called Boolean conjunctive query, or BCQ for short.
Semantics. Consider a triple hD, Σ , qi as above. An instance I satisfies a rule ρ ∈ Σ ,
denoted by I |= ρ, if whenever there is a homomorphism h from body(ρ) to I, then there
is a homomorphism h0 ⊇ h|X from {head(ρ)} to I. Moreover, I satisfies Σ , denoted by
I |= Σ , if I satisfies each rule of Σ . The models of D ∪Σ , denoted by mods(D, Σ ), consist
of the set {I : I ⊇ D and I |= Σ }. An instance I satisfies q, written I |= q, if there is a
homomorphism from some ψ j (Y j ) to I. Also, q is true over D ∪ Σ , written D ∪ Σ |= q,
if each model of D ∪ Σ satisfies q.
The chase. We recall the notion of chase [14]. Consider a logical theory hD, Σ i
as above. A rule ρ ∈ Σ is applicable to an instance I if there is a homomorphism h
from body(ρ) to I. Let I 0 = I ∪ h0 (head(ρ)), where h0 ⊇ h|X is a homomorphism from
head(ρ) to I 0 such that, for each Z ∈ Z, h0 (Z) is a different fresh null not occurring
in I. We will write hρ, hi(I) = I 0 . Indeed, it defines a single chase step. The chase
procedure of D ∪ Σ is a sequence I0 = D ⊂ I1 ⊂ I2 ⊂ . . . ⊂ Im ⊂ . . . of instances obtained
by applying exhaustively the rules of Σ in a fair fashion such that, for each i > 0,
Ii = hρ, hi(Ii−1 ), for some rule ρ and homomorphism h from body(ρ) to Ii−1 . We define
chase(D, Σ ) = ∪i≥0 Ii . It is well-known that chase(D, Σ ) is a universal model of D ∪ Σ .
In fact, for each M ∈ mods(D, Σ ), there is a homomorphism from chase(D, Σ ) to M.
Hence, given a UBCQ q, it holds that chase(D, Σ ) |= q if and only if D ∪ Σ |= q [15].
Shy ontologies. Consider a chase step hρ, hi(I) = I 0 employed in the construction
of chase(D, Σ ). If Σ is shy, then its underlying properties [21] guarantee that: (1) if X
occurs in two different atoms of body(ρ), then h(X) ∈ C; and (2) if X and Y occur both
in head(ρ) and in two different atoms of body(ρ), then h(X) = h(Y ) implies h(X) ∈ C.
Finite controllability. The finite models of a theory D ∪ Σ , denoted by fmods(D, Σ ),
are defined as the set of instances {I ∈ mods(D, Σ ) : |I| ∈ N}, each of finite size. An
ontological fragment F is said to be finitely controllable if, for each database D, for
each ontology Σ of F, and for each UBCQ q, it holds that D ∪ Σ 6|= q implies that there
exists a finite model M of D ∪ Σ such that M 6|= q. This is formally stated as D ∪ Σ |= q
if and only if D ∪ Σ |=fin q, or equivalently chase(D, Σ ) |= q if and only if D ∪ Σ |=fin q.
3 Technical Tools
3.1 Canonical Rewriting
From a triple hD, Σ , qi we build the triple hDc , Σ c , qc i enjoying the following properties:
(1) Dc is propositional database; (2) Σ c are constant-free rules containing only simple
atoms; (3) qc is a constant-free UBCQ containing only simple atoms; (4) chase(Dc , Σ c )
is a constant-free instance containing only simple atoms; (5) there is a “semantic” bi-
jection between chase(D, Σ ) and chase(Dc , Σ c ). By exploiting the above five properties
we are able to state the following result.
Theorem 2. D ∪ Σ |= q if, and only if, Dc ∪ Σ c |= qc .
Let us now shed some light on our construction. To this aim, consider the ontology
Σ = {person(X) → ∃Y fatherOf (Y, X); fatherOf (X,Y ) → person(X)}, and the database
D = {person(tim), person(john), fatherOf (tim, john)}. Let p, f , c1 and c2 be shorthands
of person, fatherOf , tim and john, respectively. Hence, chase(D, Σ ) is D ∪ {p(ni )}i>0 ∪
{ f (n1 , c1 ), f (n2 , c2 )} ∪ { f (ni+2 , ni ), f (ni+3 , ni+1 )}i>0 . From D we construct the propo-
sitional database Dc = {p[c1 ] , p[c2 ] , f[c1 ,c2 ] } obtained by encoding in the predicates the
tuples of D. Then, from Σ we construct Σ c collecting the following rules:
p[c1 ] → ∃Y f[1,c1 ] (Y ) f[c1 ,c1 ] → p[c1 ] f[c1 ,1] (Y ) → p[c1 ] f[1,1] (X) → p[1] (X)
p[c2 ] → ∃Y f[1,c2 ] (Y ) f[c1 ,c2 ] → p[c1 ] f[c2 ,1] (Y ) → p[c2 ] f[1,2] (X,Y ) → p[1] (X)
p[1] (X) → ∃Y f[1,2] (Y, X) f[c2 ,c1 ] → p[c2 ] f[1,c1 ] (X) → p[1] (X)
f[c2 ,c2 ] → p[c2 ] f[1,c2 ] (X) → p[1] (X)
The predicates here encode tuples of terms consisting of database constants (c1 and c2 )
and placeholders of nulls (1 and 2). Consider the first rule ρ : p(X) → ∃Y f (Y, X) applied
by the chase over D ∪ Σ , and h = {X 7→ c1 ,Y 7→ n1 } be its associated homomorphism.
Hence, h(body(ρ)) = p(c1 ) and h(head(ρ)) = f (n1 , c1 ). Such an application is mimed
by the sister rule ρ c : p[c1 ] → ∃Y f[1,c1 ] (Y ). By exploiting the same homomorphism we
obtain h(body(ρ c )) = p[c1 ] and h(head(ρ c )) = f[1,c1 ] (n1 ). Actually, the encoded tuple
[c1 ] in p[c1 ] says that the original twin atom p(c1 ) is unary and its unique term is exactly
c1 . Moreover, the encoded tuple [1, c1 ] in f[1,c1 ] (n1 ) says that the original twin atom
f (n1 , c1 ) is binary, that its first term is a null, and that its second term is exactly the
constant c1 . Since from predicate f[1,c1 ] we only know that the first term is a null, it
must be unary to keep the specific null value.
In the above construction, red rules are those applied by the chase on Dc ∪ Σ c .
For example, rule f[1,c1 ] (X) → p[1] (X) mimics f (X,Y ) → p(X) when X is mapped
to a null and Y to c1 ; and rule f[1,2] (X,Y ) → p[1] (X) mimics f (X,Y ) → p(X) when
X and Y are mapped to different nulls. Hence, chase(Dc , Σ c ) = Dc ∪ {p[1] (ni )}i>0 ∪
{ f[1,c1 ] (n1 ), f[1,c2 ] (n2 )} ∪ { f[1,2] (ni+2 , ni ), f[1,2] (ni+3 , ni+1 )}i>0 . As a result, the rewrit-
ing separates the interaction between the database constants propagated body-to-head
via universal variables and the nulls introduced to satisfy existential variables. Also,
since the predicates encode the “shapes” of the twin atoms —namely f[1,2] (X,Y ) means
different nulls while f[1,1] (X) the same null— repeated variables are encoded too.
By following the same approach, we can rewrite also the query. Consider the BCQ
q = ∃X∃Y r(X,Y ) ∧ s(Y, c1 ). Assume D contains only the c
constant c1 . Therefore, q
is the UBCQ r[c1 ,c1 ] ∧ s[c1 ,c1 ] ∨ ∃Y r[c1 ,1] (Y ) ∧ s[1,c1 ] (Y ) ∨ ∃Xr[1,c1 ] (X) ∧ s[c1 ,c1 ] ∨
∃Y r[1,1] (Y ) ∧ s[1,c1 ] (Y ) ∨ ∃X∃Y r[1,2] (X,Y ) ∧ s[1,c1 ] (Y ) .
3.2 Active and Harmless Rules in Shy
Consider a pair hD, Σ i and the associated pair hDc , Σ c i in canonical form. The final
goal of this section is to syntactically identify (and discard) rules of Σ c that are never
applied by the chase. But to be effective here, we need to exploit the key properties
of Σ . So, in the rest of this section, let us assume that Σ ∈ shy. First, we observe that
the canonical rewriting of a shy ontology is indeed shy. Second, we partition Σ c in two
sets, denoted by Σac and Σhc , collecting active and harmless rules, respectively, enjoying
the following properties: (1) Σhc are the rules of Σ c with at least a variable occurring in
more than one body atom; (2) Σac = Σ c \ Σhc is a joinless (and still shy) ontology; and (3)
chase(Dc , Σ c ) = chase(Dc , Σac ). By exploiting the above three properties we are able to
state the following result.
Theorem 3. For each Σ ∈ shy, it holds that Dc ∪ Σ c |= qc if, and only if, Dc ∪ Σac |= qc .
Also in this case, instead of proving formally the above theorem, we provide some
insights regarding the way how we partition Σ c . From the database D = {p(c)} and
the shy ontology Σ = {p(X) → ∃Y f (Y, X); f (X,Y ), p(X) → p(Y )} we first construct
Dc = {p[c] } and Σ c collecting the following rules
p[c] → ∃Y f[1,c] (Y ) f[1,c] (X), p[1] (X) → p[c]
p[1] (X) → ∃Y f[1,2] (Y, X) f[1,1] (X), p[1] (X) → p[1] (X)
f[c,c] , p[c] → p[c] f[1,2] (X,Y ), p[1] (X) → p[1] (Y )
f[c,1] (Y ), p[c] → p[1] (Y )
Again, red rules are those applied by the chase on Dc ∪ Σ c . Now we observe that there
is no way to trigger the rules in the second column: although the chase does produce an
atom f (t, ni ) for some term t and null ni , it never produces any atom p(ni ). This fact is
detected by the syntactic conditions underlying shy, which actually consider variable X
as “protected” in f (X,Y ), p(X) → p(Y ). Hence, Σac contains only the joinless rules in
the first column, while Σhc contains the remaining “join-rules” in the second column.
3.3 Well-Supported Finite Models
Inspired by the notion of well-supported interpretations introduced in the context of
general logic programming, we define the notion of well-supported finite models of a
pair hD, Σ i, denoted by wsfmods(D, Σ ), which enjoy the following properties: (1) for
each M ∈ fmods(D, Σ ), there exists a well-supported finite model M 0 ⊆ M; (2) each
minimal finite model of D ∪ Σ is a well-supported finite model. Assuming that the sym-
bol |=wsf refers to the satisfiability of the query under the well-supported finite models
only, by exploiting the above two properties we are able to state the following result.
Theorem 4. D ∪ Σ |=fin q, if and only, if D ∪ Σ |=wsf q.
Unfortunately, in this case, we cannot avoid defining formally this notion. A finite
instance I is called well-supported w.r.t. D∪Σ if there exists an ordering (α1 , . . . , αm ) of
its atoms such that, for each j ∈ {1, . . . , m}, at least one of the following two conditions
is satisfied: (i) α j is a database atom of D; or (ii) there exist a rule ρ of Σ and a
homomorphism h from the atoms of ρ to {α1 , . . . , α j } such that h(head(ρ)) = {α j }
and h(body(ρ)) ⊆ {α1 , . . . , α j−1 }.
Interestingly, although each finite model of an ontological theory contains a well-
supported finite model of the theory, the reverse inclusion does not hold, as shown in
the following example. Consider the father-person ontology Σ given in Section 3.1.
M = D ∪ { f (c1 , c1 ), f (c2 , c1 )} is a well-supported finite model of D ∪ Σ . Indeed, for
instance, (p(c1 ), p(c2 ), f (c1 , c2 ), f (c1 , c1 ), f (c2 , c1 )) is a well-supported ordering of M.
However, M \ { f (c2 , c1 )} is a model of D ∪ Σ . Therefore, M is not a minimal model.
4 Finite Controllability of Shy Ontologies
With our technical tools in place, we are now able to prove our main technical result.
Theorem 5. For each Σ ∈ shy, it holds that D∪Σ |=fin q if, and only if, Dc ∪Σac |=wsf qc .
Th. 1
D ∪ Σ |= q D ∪ Σ |=fin q
Th. 2 Th. 5
Dc ∪ Σ c |= qc Dc ∪ Σac |=wsf qc
Th. 3 Th. 4
Gogacz and Marcinkowski [16]
Dc ∪ Σac |= qc Dc ∪ Σac |=fin qc
Fig. 2. Chain of implications for the proof of Theorem 1.
For our purposes, the “only if” direction is the most important one. Consider an ar-
bitrary model M c ∈ wsfmods(Dc , Σac ). Let decode(M c ) be the instance obtained from M c
by decoding its atoms. For example, if p[1,c,1] (ni ) ∈ M c , then p(ni , c, ni ) ∈ decode(M c ).
It suffices to prove that there exist M ∈ fmods(D, Σ ) and a homomorphism h0 s.t. h0 (M) ⊆
decode(M c ). Indeed, by hypothesis, there exists a homomorphism h s.t. h(q) ⊆ M, and
so (h0 ◦ h)(q) ⊆ decode(M c ). Then, the result follows by the fact that (h0 ◦ h)(qc ) ⊆ M c .
The difficulty here is that decode(M c ) could not be a model of D ∪ Σ . Consider
the database D = {s(c)} and the shy ontology Σ = {s(X) → ∃Y p(Y ); s(X) → ∃Y r(Y );
p(X), r(X) → g(X)}. The canonical rewriting is Dc = {s[c] } and Σ c as follows:
s[c] → ∃Y p[1] (Y ) s[c] → ∃Y r[1] (Y ) p[c] , r[c] → g[c]
s[1] (X) → ∃Y p[1] (Y ) s[1] (X) → ∃Y r[1] (Y ) p[1] (X), r[1] (X) → g[1] (X)
One can verify that M c = {s[c] , p[1] (n1 ), r[1] (n1 )} is a (minimal) well-supported finite
model of Dc ∪ Σac since Σac is obtained from Σ c by discarding the last harmless rule.
However, decode(M c ) = {s(c), p(n1 ), r(n1 )} is not a model of D ∪ Σ because the third
rule is not satisfied. The idea now is to show how to construct from decode(M c ) a model
M ∈ fmods(D, Σ ) that can be homomorphically mapped to decode(M c ). Intuitively, we
identify the starting points in which existentially quantified variables of Σac have been
satisfied and rename the introduced terms using the so-called propagation ordering. In
the example above, consider the ordering (s(c), p(n1 ), r(n1 )) of decode(M c ), replace n1
in p(n1 ) by hn1 , 2, 2i (null n1 introduced in the second atom in the second position),
and replace n1 in r(n1 ) by hn1 , 3, 2i (null n1 introduced in the third atom in the second
position). Then, since M c is well-supported, we propagate (if needed) these new terms
according the supporting ordering. In our case, M = {s(c), p(hn1 , 2, 2i), r(hn1 , 3, 2i)} is
now a finite model of D ∪ Σ that can be mapped to decode(M c ).
Finally, to prove Theorem 1, we can now combine the trivial “only if” implication
with the dashed chain of intermediate results given in Figure 2.
5 Conclusion
At this point, also thanks to the results shown in this paper, we know that every basic
decidable Datalog± class is finitely controllable. However, the problem remains open
for extensions and combinations of these classes [11, 13, 18]. For example, it is open
whether finite controllability holds for the following classes: (i) sticky-join, general-
izing sticky and linear; (ii) tame, generalizing sticky and guarded; and (iii) weakly-
sticky-join, generalizing sticky-join, weakly-acyclic and shy. We believe that the tech-
niques developed in this paper can be exploited to give an answer to these questions.
References
1. Amendola, G., Leone, N., Manna, M.: Finite model reasoning over existential rules. Fourth-
coming (2017)
2. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The
Description Logic Handbook: Theory, Implementation, and Applications. CUP (2003)
3. Baget, J., Leclère, M., Mugnier, M., Salvat, E.: Extending decidable cases for rules with
existential variables. In: In Proc. of IJCAI’09. pp. 677–682 (2009)
4. Bárány, V., Gottlob, G., Otto, M.: Querying the guarded fragment. Logical Methods in Com-
puter Science 10(2) (2014)
5. Bourhis, P., Manna, M., Morak, M., Pieris, A.: Guarded-based disjunctive tuple-generating
dependencies. ACM TODS 41(4), 27:1–27:45 (2016)
6. Calı̀, A., Gottlob, G., Kifer, M.: Taming the infinite chase: Query answering under expressive
relational constraints. J. Artif. Intell. Res. (JAIR) 48, 115–174 (2013)
7. Calı̀, A., Gottlob, G., Lukasiewicz, T.: Datalog± : a unified approach to ontologies and in-
tegrity constraints. In: In Proc. of ICDT’09. pp. 14–30 (2009)
8. Calı̀, A., Gottlob, G., Lukasiewicz, T.: Tractable query answering over ontologies with
datalog+/-. In: In Proc. of DL’09 (2009)
9. Calı̀, A., Gottlob, G., Lukasiewicz, T.: A general datalog-based framework for tractable query
answering over ontologies. J. Web Sem. 14, 57–83 (2012)
10. Calı̀, A., Gottlob, G., Pieris, A.: Advanced processing for ontological queries. PVLDB 3(1),
554–565 (2010)
11. Calı̀, A., Gottlob, G., Pieris, A.: Towards more expressive ontology languages: The query
answering problem. AIJ 193, 87–128 (2012)
12. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of
query answering in description logics. AIJ 195, 335–360 (2013)
13. Civili, C., Rosati, R.: A broad class of first-order rewritable tuple-generating dependencies.
In: In Proc. of Datalog 2.0. pp. 68–80 (2012)
14. Deutsch, A., Nash, A., Remmel, J.B.: The chase revisited. In: In Proc. of PODS’08. pp.
149–158 (2008)
15. Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answer-
ing. TCS 336(1), 89–124 (2005)
16. Gogacz, T., Marcinkowski, J.: Converging to the chase - A tool for finite controllability. In:
In Proc. of LICS’13. pp. 540–549 (2013)
17. Gottlob, G., Kikot, S., Kontchakov, R., Podolskii, V.V., Schwentick, T., Zakharyaschev, M.:
The price of query rewriting in ontology-based data access. AIJ 213, 42–59 (2014)
18. Gottlob, G., Manna, M., Pieris, A.: Combining decidability paradigms for existential rules.
TPLP 13(4-5), 877–892 (2013)
19. Gottlob, G., Orsi, G., Pieris, A.: Query rewriting and optimization for ontological databases.
ACM TODS 39(3), 25:1–25:46 (2014)
20. Gottlob, G., Pieris, A., Tendera, L.: Querying the guarded fragment with transitivity. In: In
Proc. of ICALP’13. pp. 287–298 (2013)
21. Leone, N., Manna, M., Terracina, G., Veltri, P.: Efficiently computable Datalog∃ programs.
In: In Proc. of KR’12 (2012)
22. Rosati, R.: The limits of querying ontologies. In: In Proc. of ICDT’07. pp. 164–178 (2007)
23. Rosati, R.: On the finite controllability of conjunctive query answering in databases under
open-world assumption. JCSS 77(3), 572–594 (2011)