The chase procedure is considered as one of the most fundamental algorithmic tools in database theory. It has been successfully applied to different database problems such as data exchange, and query answering and containment under constraints, to name a few. One of the central problems regarding the chase procedure is all-instance termination, that is, given a set of tuple-generating dependencies (TGDs) (a.k.a. existential rules), decide whether the chase under that set terminates, for every input database. It is well-known that this problem is undecidable, no matter which version of the chase we consider. The crucial question that comes up is whether existing restricted classes of TGDs, proposed in different contexts such as ontological reasoning, make the above problem decidable. In this work, we focus our attention on the oblivious and the semi-oblivious versions of the chase procedure, and we give a positive answer for classes of TGDs that are based on the notion of guardedness.
The chase procedure (or simply chase) is considered as one of the most fundamental algorithmic tools in databases — it accepts as input a database D and a set Σ of constraints and, if it terminates (which is not guaranteed), its result is a finite instance DΣ that enjoys two crucial properties: 1. DΣ is a model of D and Σ, i.e., it contains D and satisfies the constraints of Σ; and 2. DΣ is universal, i.e., it can be homomorphically embedded into every other model of D and Σ.
In other words, the chase is an algorithmic tool for computing universal models of D and Σ, which can be conceived as representatives of all the other models of D and Σ. This is precisely the reason for the ubiquity of the chase in database theory. Indeed, many key database problems can be solved by simply exhibiting a universal model.
A central class of constraints, which can be treated by the chase procedure and is of special interest for this work, are the well-known tuple-generating dependencies (TGDs) (a.k.a. existential rules) of the form ∀X∀Y(φ(X, Y) → ∃Z(ψ(Y, Z))), where φ and ψ are conjunctions of atoms. Given a database D and a set Σ of TGDs, the chase adds new atoms to D (possibly involving nulls) until the final result satisfies Σ. Example 1. Consider the database D = {person(Bob)}, and the TGD ∀X(person(X) → ∃Y hasFather (X, Y ) ∧ person(Y )), which asserts that each person has a father who is also a person. The database atom triggers the TGD, and the chase will add in D the atoms hasFather (Bob, z1) and person(z1) in order to satisfy it, where z1 is a (labeled) null representing some unknown value. However, the new atom person(z1) triggers again the TGD, and the chase is forced to add the atoms hasFather (z1, z2), person(z2), where z2 is a new null. The result of the chase is the instance {person(Bob), hasFather (Bob, z1)} ∪ ∪ {person(zi), hasFather (zi, zi+1)}, i>0 where z1, z2, . . . are nulls.
As shown by the above example, the chase procedure may run forever, even for
extremely simple databases and constraints. In the light of this fact, there has been a long
line of research on identifying syntactic properties on TGDs such that, for every input
database, the termination of the chase is guaranteed; see, e.g., [
Although the chase termination problem is undecidable in general, the proof given
in [
We focus on the (semi-)oblivious versions of the chase, and we show that the
problem of deciding the termination of the chase for guarded TGDs is decidable, and we
establish precise complexity results. Surprisingly, the present work is to our knowledge
the first one that establishes positive results for the (semi-)oblivious chase termination
problem. For more details, we refer the reader to [
The TGD chase procedure (or simply chase) takes as input an instance I and a set Σ of
TGDs, and constructs a universal model of I and Σ. The chase works on I by applying
the so-called trigger for a set of TGDs on I. The trigger for a set Σ of TGDs on an
instance I is a pair (σ, h), where σ = φ → ψ ∈ Σ and h is a homomorphism that
maps φ to I. An application of (σ, h) to I returns J = I ∪ h′(ψ), where h′ ⊇ h maps
each existentially quantified variable in ψ to a new null value. Such a trigger application
is written I⟨σ, h⟩J . The choice of the type of the next trigger to be applied is crucial
since it gives rise to different versions of the chase procedure. In this work, we focus
our attention on the oblivious [
A finite sequence I0, I1, . . . , In, where n > 0, is said to be a terminating oblivious chase sequence of I0 w.r.t. a set Σ of TGDs if: (i) for each 0 6 i < n, there exists a trigger (σ, h) for Σ on Ii such that Ii⟨σ, h⟩Ii+1; (ii) for each 0 6 i < j < n, assuming that Ii⟨σi, hi⟩Ii+1 and Ij ⟨σj , hj ⟩Ij+1, σi = σj = σ implies hi ̸= hj , i.e., hi and hj are different homomorphisms; and (iii) there is no trigger (σ, h) for Σ on In such that (σ, h) ̸∈ {(σi, hi)}06i6n−1. In this case, the result of the chase is the (finite) instance In. An infinite sequence I0, I1, . . . of instances is said to be a non-terminating oblivious chase sequence of I0 w.r.t. Σ if: (i) for each i > 0, there exists a trigger (σ, h) for Σ on Ii such that Ii⟨σ, h⟩Ii+1; (ii) for each i, j > 0 such that i ̸= j, assuming that Ii⟨σi, hi⟩Ii+1 and Ij ⟨σj , hj ⟩Ij+1, σi = σj = σ implies hi ̸= hj ; and (iii) for each i > 0, and for every trigger (σ, h) for Σ on Ii, there exists j > i such that Ij ⟨σ, h⟩Ij+1; this is known as the fairness condition, and guarantees that all the triggers eventually will be applied. The result of the chase is defined as the infinite instance ∪i>0Ii.
The semi-oblivious chase is a refined version of the oblivious chase, which avoids the application of some superfluous triggers. Roughly speaking, given a TGD σ of the form φ → ψ, for the semi-oblivious chase, two homomorphisms h and g that agree on the universally quantified variables of σ occurring in ψ are indistinguishable.
Henceforth, we write o-chase and so-chase for oblivious and semi-oblivious chase, respectively. A ⋆-chase sequence, where ⋆ ∈ {o, so}, may be infinite.
Example 2. Let D = {p(a, b)}, and Σ = {∀X∀Y (p(X, Y ) → ∃Z(p(Y, Z)))}. There exists only one ⋆-chase sequence of D w.r.t. Σ, where ⋆ ∈ {o, so}, which is non-terminating, i.e., I0, I1, . . . with
I0 = {p(a, b)}
I1 = {p(a, b), p(b, z1)}
Ii = Ii−1 ∪ {p(zi−1, zi)}, for i > 2, where z1, z2, . . . are nulls of N.
For a set of TGDs, a key question is whether all or some ⋆-chase sequences are terminating on all databases. Before formalizing the above decision problems, let us recall the following key classes of TGDs:
CT⋆∀ = {Σ | ∀D, all ⋆ -chase sequences of D w.r.t. Σ are terminating} CT⋆∃ = {Σ | ∀D, there exists a terminating ⋆ -chase sequence of D w.r.t. Σ}. The decision problems tackled in this work are as follows: for q ∈ {∀, ∃}: q-SEQUENCE ⋆-CHASE TERMINATION:
Instance: A set Σ of TGDs.
Question: Does Σ ∈ CTq⋆?
We recall that CTo∀ = CTo∃ ⊂ CTs∀o = CTs∃o [
We focus on the class of guarded TGDs [
By exploiting syntactic conditions that ensure the termination of each (semi-)oblivious
chase sequence on all databases, we syntactically characterize the classes (CT⋆ ∩ SL)
and (CT⋆∩L), where ⋆ ∈ {o, so}. We rely on weak-acyclicity [
In simple words, the above theorem states that, given a set Σ ∈ SL: Σ ∈ CTo iff Σ is richly-acyclic, and Σ ∈ CTso iff Σ is weakly-acyclic. This result is established by showing that a dangerous cycle in the extended dependency graph (resp., dependency graph) necessarily gives rise to a non-terminating o-chase (resp., so-chase) sequence.
Let us now focus on (non-simple) linear TGDs. It is possible to show, by exhibiting a counterexample, that a dangerous cycle does not necessarily correspond to an infinite chase derivation. Thus, rich- and weak-acyclicity are not powerful enough for syntactically characterize the fragment of linear TGDs that guarantees the termination of the oblivious and semi-oblivious chase, respectively. Interestingly, it is possible to extend rich- and weak-acyclicity, focussing on linear TGDs, in such a way that the above key property holds. The obtained formalisms are dubbed critical-rich-acyclicity and critical-weak-acyclicity, and the corresponding classes are denoted as LCriticalRA and LCriticalWA, respectively. We show that: Theorem 2. (CTo ∩ L) = LCriticalRA and (CTso ∩ L) = LCriticalWA.
The above syntactic characterizations, apart from being interesting in their own right, allow us to obtain optimal upper bounds for the ⋆-chase termination problem for (S)L — we simply need to analyze the complexity of deciding whether a set of (simple) linear TGDs enjoys the above acyclicity-based conditions, which can be formulated as a reachability problem on a graph. In particular, we obtain the following results: Theorem 3. Consider a set Σ of TGDs. The problem of deciding whether Σ ∈ CT⋆, where ⋆ ∈ {o, so}, is 1. NL-complete, even for unary and binary predicates, if Σ ∈ SL; and 2. PSPACE-complete, and NL-complete for predicates of bounded arity, if Σ ∈ L.
For the hardness results, a generic technique, called the looping operator, is proposed, which allows us to obtain lower bounds for the chase termination problem in a uniform way. In fact, the goal of the looping operator is to provide a generic reduction from propositional atom entailment to the complement of chase termination. 3.2
We proceed to investigate the (semi-)oblivious chase termination problem for guarded TGDs. Although there is no way (at least no obvious one) to syntactically characterize the classes (CT⋆ ∩ G), where ⋆ ∈ {o, so}, via rich- and weak-acyclicity, as we did for (simple) linear TGDs, it is possible to show that the problem of recognizing the above classes is decidable. For technical reasons, we focus on standard databases, that is, databases that have two constants, let say 0 and 1, that are available via the unary predicates 0(·) and 1(·), respectively. In particular, we show the following: Theorem 4. Consider a set Σ ∈ G. The problem of deciding whether Σ ∈ CT⋆, where ⋆ ∈ {o, so}, focussing on standard databases, is 2EXPTIME-complete, and EXPTIMEcomplete for predicates of bounded arity.
The upper bounds are obtained by exhibiting an alternating algorithm that runs in exponential space, in general, and in polynomial space in case of predicates of bounded arity. The lower bounds are obtained by reductions from the acceptance problem of alternating exponential (resp., polynomial) space clocked Turing machines, i.e., Turing machines equipped with a counter. These reductions are obtained by modifying significantly existing reductions for the problem of propositional atom entailment under guarded TGDs, and then exploiting the looping operator mentioned above. The fact that the database is standard, is crucial for establishing the above lower bounds; the upper bounds hold even for non-standard databases. Our next step is to perform similar analysis focussing on the restricted version of the chase. We already have some preliminary positive results. In particular, if we focus on single-head linear TGDs, where each predicate appears in the head of at most one TGD, then we can syntactically characterize, via a careful extension of weak-acyclicity, the fragment that guarantees the termination of the restricted chase, and obtain a polynomial time upper bound. We are currently working towards the full settlement of the problem. Acknowledgements. M. Calautti was supported by the European Commission, European Social Fund and Region Calabria. G. Gottlob was supported by the EPSRC Programme Grant EP/M025268/ “VADA: Value Added Data Systems – Principles and Architecture”, and the Grant ERC-POC-2014 Nr. 641222 “ExtraLytics: Big Data for Real Estate”. A. Pieris was supported by the Austrian Science Fund (FWF), projects P25207-N23 and Y698, and Vienna Science and Technology Fund (WWTF), project ICT12-015.