The chase procedure, an algorithm proposed 25+ years ago to fix constraint violations in database instances, has been successfully applied in a variety of contexts, such as query optimization and data exchange. Its practicability, however, is limited by the fact that - for an arbitrary set of constraints - it might not terminate; even worse, chase termination is an undecidable problem in general. In response, the database community has proposed sufficient restrictions on top of the constraints that guarantee chase termination on any database instance. In this paper, we propose a sufficient termination condition, called inductive restriction, which strictly generalizes previous conditions, but can be checked as efficiently.
The chase procedure is a fundamental algorithm that has been successfully applied
in a variety of database applications [
The core idea of the chase algorithm is simple: given a set of dependencies (also called
constraints) over a database schema and an instance as input, it fixes constraint
violations in the instance. One problem with the chase, however, is that – given an arbitrary
set of constraints – it might never terminate; even worse, this problem is undecidable in
general, also for a fixed instance [
Remark. An extended version of this paper including full proofs can be found in [
General mathematical notation. For n ∈ N, we denote by [n] the set {1, ..., n}. For a set M , we denote by 2M its powerset.
Databases. We fix three pairwise disjoint infinite sets: the set of constants Δ, the set of labeled nulls Δnull, and the set of variables V . A database schema R is a finite set of relational symbols {R1, ..., Rn}. In the rest of the paper, we assume the database schema and the set of constants and labeled nulls to be fixed. A database instance I is a finite set of R-atoms that contains only elements from Δ ∪ Δnull in its positions. We denote an element of an instance as fact. The domain of I, dom(I), is the set of elements from Δ ∪ Δnull that appear in I.
We use the term position to denote a position in a predicate, e.g. a three-ary predicate R has three positions R1, R2, R3. We say that a variable, labeled null, or constant c appears e.g. in a position R1 if there exists a fact R(c, ...).
Constraints. Let x, y be tuples of variables. We consider two types of database
constraints: tuple generating dependencies (TGDs) and equality generating dependencies
(EGDs). A TGD has the form α := ∀x(φ(x) → ∃yψ(x, y)) such that both φ and ψ
are conjunctions of atomic and equality-free R-atoms, possibly with parameters from
Δ and all variables from x that occur in ψ must also occur in φ. We denote by pos(α)
the set of positions in φ. An EGD has the form α := ∀x(φ(x) → xi = xj ), where
xi, xj occur in φ and φ is a non-empty conjunction of equality-free R-atoms, possibly
with parameters from Δ. We denote by pos(α) the set of positions in φ. As a
notational convenience, we will often omit the ∀-quantifier and respective list of universally
quantified variables. For a set of TGDs and EGDs Σ we set pos(Σ) := Sξ∈Σ pos(ξ).
Chase. We assume that the reader is familiar with the chase procedure and give only
a short introduction here, referring the interested reader to [
→ J takes a relational database instance I such that I 2
α(a) and adds tuples (in case of TGDs) or collapses some elements (in case of EGDs)
such that the resulting relational database J is a model of α(a). If J was obtained from
I in that kind, we sometimes also write Ia ⊕ Cα instead of J . A chase sequence is an
exhaustive application of applicable constraints I0 α−0→,a0 I1 α−1→,a1 . . ., where we impose
no strict order on what constraint to apply in case several constraints are applicable. If
this sequence is finite, say Ir being its final element, the chase terminates and its result
I0Σ is defined as Ir. The length of this chase sequence is r. Note that different orders of
application orders may lead to a different chase result. However, as proven in [
In the past, sufficient conditions for constraint sets have been developed that guarantee
chase termination for any instance. One such condition is weak acyclicity [
Safe Restriction. The idea of safe restriction is to keep track of positions where fresh
null values might be created in or copied to. As a basic tool, we borrow the definition
of affected positions from [
Definition 1. [
Akin to the dependency graph in weak acyclicity [
Definition 2. Let Σ be a set of TGDs. We define a directed graph called propagation graph prop(Σ) := (aff(Σ), E) as follows. There are two kinds of edges in E. Add them as follows: for every TGD ∀x(φ(x) → ∃yψ(x, y)) ∈ Σ and for every x in x that occurs in ψ and every occurrence of x in φ in position π1 • if x occurs only in affected positions in φ then, for every occurrence of x in ψ in position π2, add an edge π1 → π2 (if it does not already exist). • if x occurs only in affected positions in φ then, for every existentially quantified variable y and for every occurrence of y in a position π2, add a special edge π1 →∗ π2 (if it does not already exist).
Definition 3. A set Σ of constraints is called safe iff prop(Σ) has no cycles going through a special edge.
Safety is a sufficient termination condition which strictly generalizes weak acyclicity
and is different from stratification [
Definition 4. Let Σ abe given and P ⊆ pos(Σ). For all α, β ∈ Σ, we define α ≺P β iff there are tuples a, b and a database instance I s.t. (i) I 2 α(a), (ii) I |= β(b), (iii) I α→,a J , (iv) J 2 β(b), (v) I contains null values only in positions from P and (vi) there is a null value n ∈ b ∩ Δnull in the head of β(b).
Informally, α ≺P β holds if α might cause β to fire s.t., when null values occur only in positions from P, β copies some null values. We next introduce a notion for affected positions relative to a constraint and a set of positions.
Definition 5. For any set of positions P and a TGD α let aff-cl(α, P ) be the set of positions π from the head of α such that • for every universally quantified variable x in π: x occurs in the body of α only in positions from P or • π contains an existentially quantified variable.
On top of previous definitions we introduce the central tool of restriction systems. Definition 6. A restriction system is a pair (G′(Σ), f ), where G′(Σ) := (Σ, E) is a directed graph and f : Σ → 2pos(Σ) is a function such that • forall TGDs α and forall (α, β) ∈ E: aff-cl(α, f (α)) ∩ pos({β}) ⊆ f (β), • forall EGDs α and forall (α, β) ∈ E: f (α) ∩ pos({β}) ⊆ f (β), and • forall α, β ∈ Σ: α ≺f(α) β =⇒ (α, β) ∈ E.
A restriction system is minimal if it is obtained from ((Σ, ∅),{(α, ∅) | α ∈ Σ}) by a repeated application of the constraints from bullets one to three (until all constraints hold) s.t., in case of the first and second bullet, the image of f (β) is extended only by those positions that are required to satisfy the condition.
Example 1. Let predicate E(x,y) store graph edges and predicate S(x) store some nodes.
The constraints Σ = {α1, α2} with α1 := S(x), E(x,y) → E(y,x) and α2 := S(x),
E(x,y) → ∃z E(y,z), E(z,x) assert that all nodes in S have a cycle of length 1 and 2.
It holds that aff(Σ) = {E1,E2} and it is easy to verify that Σ is neither safe nor
stratified (see Def. 2 in [
As shown in [
Example 2. Constraint set Σ from Example 1 is safely restricted: its minimal restriction system contains no strongly connected components.
As shown in [
Inductive Restriction. We now introduce the novel class of inductively restricted constraints, which generalizes safe restriction but, like the latter, gives polynomial-time termination guarantees. We start with a motivating example.
Example 3. We extend the constraints from Example 1 to Σ′ := Σ ∪{α3}, where α3 := ∃x, yS(x), E(x, y). Then G’(Σ′):=(Σ′,{(α1, α2),(α2,α1),(α3,α1),(α3,α2)}) with f(α1) = f(α2) := {E1,E2,S1} and f(α3) := ∅ is the minimal restriction system. It contains the strongly connected component {α1,α2}, which is not safe. Consequently, Σ′ is not safely restricted.
Intuitively, safe restriction does not apply in the example above because α3 “infects” position S1 in the restriction system. Though, null values cannot be repeatedly created in S1: α3 fires at most once, so it does not affect chase termination. Our novel termination condition recognizes such situations by recursively computing the minimal restriction systems of the strongly connected components. We formalize this computation in Algorithm 1, called part(Σ). Based on this algorithm, we define an improved sufficient termination condition.
Definition 8. Let Σ be a set of constraints. We call Σ inductively restricted iff for all Σ′ ∈ part (Σ) it holds that Σ′ is safe.
As stated in the following lemma, inductive restriction strictly generalizes safe restriction, but does not increase the complexity of the recognition problem. Lemma 1. Let Σ be a set of constraints. • If Σ is safely restricted, then it is inductively restricted. • There is some Σ that is inductively restricted, but not safely restricted. • The recognition problem for inductive restriction is in CONP.
Example 4. Consider Σ′ from Example 3. It is easy to verify that part (Σ′) = ∅ and we conclude that Σ′ is inductively restricted. As argued in Example 3, Σ′ is not safely restricted, which proves the second claim in Lemma 1.
The next theorem gives the main result of this section, showing that inductive restriction guarantees chase termination in polynomial time data complexity. To the best of our knowledge inductive restriction is the most general sufficient termination condition for the chase that has been proposed so far.
Theorem 1. Let Σ be a fixed set of inductively restricted constraints. Then, there exists a polynomial Q ∈ N[X] such that for any database instance I, the length of every chase sequence is bounded by Q(||I||), where ||I|| is the number of distinct values in I. 4
We considered the termination of the chase algorithm. As our main contribution, we
generalized all sufficient data-independent termination conditions that were known so
far. Our results on chase termination directly carry over to applications that rely on the
chase and also to the so-called core-chase presented in [