Enhancing Existential Rules by Closed-World Variables

1 Introduction

Existential rules, also known as TGDs or datalog∃ rules, are a fascinating research topic deeply studied not only in artificial intelligence [Baget et al., 2011; Amendola et al., 2017] but also in database theory [Bourhis et al., 2016; Alviano and Pieris, 2015] and logic [B´ar´any et al., 2014]. They are at the core of Datalog± [Cal`ı et al., 2009], an emerging family of ontology languages complementing the expressive power of Description Logics (DLs) [Baader et al., 2003]. Indeed, datalog∃ generalizes the well-known language Datalog [Ceri et al., 1989] with existential quantification in the head. Natively, Datalog is interpreted under a closed-world semantics, while existential rules typically employ the openworld assumption. For example, in classical query answering [Ortiz, 2013] -where a query q is evaluated over a logical theory consisting of a database D paired with an ontology Σ- the presence of existential quantifiers in Σ requires an interpretation domain of D ∪ Σ that extends the closed domain of D with infinitely many extra "anonymous" individuals. Then, each variable of Σ does range over all individuals.

To consciously reason on the properties of "known" (nonanonymous) and arbitrary individuals in different ways, we complement standard variables with closed(-world) variables that range over the individuals of D ∪ Σ only. The resulting language, called datalog∃,H , offers novel modeling capabilities, as it allows to specify properties at both data and conceptual level in a uniform way. Consider, for example, a scenario in which one has to model that "every good has a price" and "a good is auctionable if some reference price can be associated to it". Such desiderata are expressible via the rules ρ1 =good(X) → ∃Y hasPrice(X, Y ) and ρ2 =good(X), hasPrice(X, ̂Y) → auctionable(X), where ̂Y is a closed variable. Given D0 = {good(ferrari250)}, Σ0={ρ1, ρ2}, and the queries q1 =∃X ∃Y hasPrice(X, Y ) and q2=∃X ∃Y hasPrice(X, Y ), auctionable(X). Clearly, q1 is entailed by D0 ∪ Σ0. But q2 is not since M = D0 ∪ {hasPrice(ferrari250 , 10)} is a possible model of D0 ∪ Σ0. Indeed, 10 is not a reference price for ferrari250 but simply one of the infinitely many anonymous individuals not in D0. Therefore rule ρ2 is satisfied in M. Of course, a first natural question now is to wonder whether Σ0 can be expressed via some equivalent datalog∃ ontology.

Existential rules, besides offering good modeling capability, are extremely challenging from a computational viewpoint, as they make query answering undecidable in the general case [Beeri and Vardi, 1984]. To remedy this fact, several syntactic conditions have been proposed in the literature, with some giving rise to the five basic decidable datalog∃ classes: linear [Cal`ı et al., 2012a], weakly-acyclic [Fagin et al., 2005], guarded [Cal`ı et al., 2013], sticky [Cal`ı et al., 2012b], and shy [Leone et al., 2012]. The second natural question now is to wonder whether these conditions can be generalized to preserve decidability of query answering also for datalog∃,H .

Along the paper we give answers to the above questions, starting right here by summarizing the main contributions:

• For each basic datalog∃ class C, we consider a "naive" and a "refined" extension, denoted by CH and CH+, respectively. In naive extension, the syntactic conditions underlying C treat closed variables as standard ones. In the refined one, the syntactic conditions are enforced over standard variables only. Decidability can be easily established. (Section 3.)
• We show that CH preserves the same data and combined complexity of each basic datalog∃ class C. Likewise, this holdswith shyH+ andw-acyclicH+ w.r.t. their standard counterparts. Differently, guardedH+ and stickyH+ exhibit an increase in data complexity, while only linearH+ has an increase in both data and combined complexity. (Section 4.)

• We prove that datalog∃,H is (resp., CH and CH+ are) strictly more expressive than datalog∃ (resp., each basic class C). In particular, going back to our running example, there is no datalog∃ ontology that, independently from the database at hand, behaves as Σ0 w.r.t. both q1 and q2. Also, each CH+ is even strictly more expressive than datalog. (Section 5.1.)
• We show that the well-known Description Logic ELH [Brandt, 2004b] is captured by linearH+, even if we only focus on linearH+ ontologies of arity at most two and with at most two atoms in the body (where the combined complexity of query answering drops to NP as for ELH). Interestingly, linearH+ keeps a lower computational complexity, compared to other datalog∃ classes that can express this DL, namely guarded and its extensions. (Section 5.2.)

2 Existential Rules with Closed Variables

Basics. Let C (constants or individuals) and V (variables) be pairwise disjoint discrete sets of terms. A variable (x, y, ...) is either standard (X, Y, ...) or closed(-world) (̂X, ̂Y, ...). We denote by Vs and Vc, the set of standard and closed variables, respectively. An atom α is a labeled tuple p(t), where p = pred(α) is a predicate symbol, t = t1, ..., tm is a tuple of terms, m = |p| is the arity of p or α, and α[i] = ti. Given a finite domain ∆ ⊂ C of "known" individuals, a ∆-substitution is any map µ : V → C such that ̂X ∈ Vc implies µ(̂X) ∈ ∆. For a set A of atoms, µ(A) is obtained from A by replacing each variable x by µ(x). A database (resp., instance) is any variable-free finite (resp., possibly infinite) set of atoms.

Syntax. A datalog∃,H rule ρ is a logical implication of the form ∀X∀Y (φ(X, Y) → ∃Z ψ(X, Z)) -with X ∪ Y ⊆ V and Z ⊆ Vs- whose body (resp., head) b(ρ) = φ(X,Y) (resp., h(ρ) = ψ(X,Z)) is a conjunction (or set) of atoms, possibly with constants. As usual, the head is nonempty. Universal and existential variables are respectively denoted by UV(ρ) and EV(ρ). The set X is known as the frontier of ρ. If no closed variable is in ρ, then it is also a datalog∃ rule; and if even EV(ρ) = ∅, then it is also a datalog rule. A datalog∃,H ontology Σ is any finite set of datalog∃,H rules. We denote by R(Σ) the set of predicates occurring in Σ. A position p[i] is defined as a predicate p of R(Σ) and its i-th attribute. Let pos(p)={p[1], ..., p[|p|]}. A CH (hybrid conjunctive) query is an expression of the form q(X) = ∃Y φ(X,Y), where φ is as above. In case q contains no closed variable, it is also a C (conjunctive) query. For a "structure" ς over atoms (set, rule, query, ...), if ̂X occurs in ς, then X does not occur in ς. Also, atoms(ς), terms(ς), vars(ς) and std(ς) respectively denote the set of atoms in ς, the set of terms in atoms(ς), the set of variables in atoms(ς), and the structure built from ς by replacing each ̂X with X.

Semantics. Consider a triple 〈D,Σ, q〉 as above, and let ∆ = terms(D,Σ) ∩ C. A model of D ∪ Σ is any instance M ⊇ D such that, for each ρ ∈ Σ and each ∆-substitution µ, µ(b(ρ)) ⊆ M implies µ′ (h(ρ)) ⊆ M for some ∆-substitution µ′ ⊇ µ|X. The answer to q over M is the set ans(q,M) of |X|-tuples t for which there is a ∆-substitution µ such that µ(φ(t,Y)) ⊆ M. The set of all models is denoted by mods(D, Σ). The (certain) answer to q is the set ans(q, D, Σ) = ⋂M∈mods(D,Σ) ans(q,M).

3 Decidability

Hereafter, QEVAL refers to the following decision problem: Given a database D, a datalog∃,H ontology Σ, a CH query q(X) with |X| = n, and a tuple t ∈ Cn , decide whether t ∈ ans(q,D, Σ) holds. In this section, we first introduce the five basic datalog∃ classes ensuring decidability of QEVAL, as well as some of their generalizations that we need in our technical analysis: j-acyclic [Kr¨otzsch and Rudolph, 2011], w-sticky [Cal`ı et al., 2012b], and w-guarded [Cal`ı et al., 2013]. Then, we define hybrid(-world) extensions of the basic classes, and show that decidability is preserved.

3.1 Overview of Some Decidable datalog∃ Classes

Fix a datalog∃ ontology Σ. We assume that different rules of Σ share no variable. A term t occurs in a set A of atoms at position p[i] if there is α ∈ A s.t. pred(α) = p and α[i] = t. Position p[i] is invaded by an existential variable X if there is ρ ∈ Σ s.t.: (1) X occurs in h(ρ) at position p[i]; or (2) some y ∈ UV(ρ) attacked by X (i.e., y occurs in b(ρ) only at positions invaded by X) occurs in h(ρ) at position p[i]. A universal variable is protected if it is attacked by no variable. Linearity. Ontology Σ belongs to linear if, for each ρ ∈ Σ, b(ρ) contains at most one body atom.

Acyclicity. The labeled graph of Σ is G(Σ) = 〈N,A〉, where: (1) N = ∪p∈R(Σ)pos(p); (2) (p[i], r[j], ∀) ∈ A if there are ρ ∈ Σ and X ∈ UV(ρ) s.t. X occurs both in b(ρ) at position p[i] and in h(ρ) at position r[j]; and (3) (p[i], r[j], ∃) ∈ A if there are ρ ∈ Σ, X ∈ UV(ρ) also occurring in h(ρ), and Y ∈ EV(ρ) s.t. both X occurs in b(ρ) at position p[i] and Y occurs in h(ρ) at position r[j]. The existential graph of Σ is G∃(Σ) = 〈N, A〉, where N = ∪ρ∈ΣEV(ρ) and (X, Y ) ∈ A if the rule ρ where Y occurs contains a universal variable attacked by X and occurring in h(ρ). Σ belongs to weakly-acyclic (resp., j-acyclic) if G(Σ) (resp., G∃(Σ)) has no cycle through an ∃-arc (resp., is acyclic).

Guardedness. Σ belongs to guarded if ρ ∈ Σ implies that there is α ∈ b(ρ) s.t. UV(ρ) = vars(α). Also, Σ belongs to w-guarded if, for each ρ ∈ Σ, there is an atom of b(ρ) containing all the attacked variables of ρ.

Stickiness. A variable X of Σ is marked if (1) there is ρ ∈ Σ s.t. X occurs in b(ρ) but not in h(ρ); or (2) there are ρ, ρ′ ∈ Σ s.t. a marked variable occurs in b(ρ) at some position p[i] and X occurs in h(ρ′ ) at position p[i] too. Then, Σ is sticky if, for each ρ ∈ Σ, X occurs multiple times in b(ρ) implies X is not marked. Also, Σ belongs to w-sticky if, for each ρ ∈ Σ, X occurs multiple times in b(ρ) implies X is not marked or X occurs in some position never involved in cycles going through an ∃-arc of G(Σ).

Shyness. Σ belongs to shy if, for each ρ ∈ Σ: (1) X occurs in two different atoms of b(ρ) implies X is protected; and (2) if X and Y occur both in h(ρ) and in two different atoms of b(ρ), then X and Y are not attacked by the same variable.

Proposition 1. The considered classes are pairwise uncomparable, except for: linear ⊂ guarded ⊂ w-guarded, linear ⊂ shy, datalog ⊂ shy, sticky ⊂ w-sticky, and datalog ⊂ w-acyclic ⊂ j-acyclic.

3.2 Decidable Hybrid Extensions

Let B = {linear, w-acyclic, guarded, sticky, shy}. For each C ∈ B, we define the "naive" and "refined" hybrid(-world) extension of C, respectively denoted by CH and CH+. Formally, for each Σ ∈ datalog∃,H , Σ ∈ CH if std(Σ) ∈ C, while Σ ∈ CH+ if thin(Σ) ∈ C, where thin(Σ) is obtained from Σ by replacing each closed variable by some constant and then eliminating every atom containing only constants. For example, g(X, ̂Y), s(̂Y) → r(X) belongs to linearH+ but not to linearH since g(X, c) → r(X) belongs to linear but the rule g(X, Y ), s(Y ) → r(X) does not.

Proposition 2. For each C, C ′ ∈ B, C ⊂ CH ⊂ CH+ holds, as well as C ⊂ C ′ implies both CH ⊂ C ′H and CH+ ⊂ C ′H+.

For the decidability analysis, we reduce QEVAL over datalog∃,H to QEVAL over datalog∃ . To this end, we devise the following algorithm, whose key principle is reminiscent of analogous methods from the literature [Motik et al., 2005]:

Algorithm 1. Reduction A1 from a hybrid triple 〈D, Σ, q〉 † Σ′ ← {p(Xp ) →Γ(Xp ), ¯ p(Xp ) : p ∈ R(Σ)}; ‡ Σ′′ ← {std(b(¯ ρ)), Γ(Vρ ) → std (h( ¯ ρ)), Γ(Cρ ) : ρ ∈ Σ}; q′ ← std(¯ q), Γ(Vq ); return 〈D, Σ′ ∪ Σ′′ , q′ 〉;

Legend. ¯ q (resp., ¯ ρ) is obtained from q (resp., ρ) by replacing each predicate p with ¯ p; Γ(t1, ..., tn) = c(t1), ..., c(tn), for any n > 0;V⋄= {V : ̂V ∈ vars(⋄)}; Cρ=C∩terms(h(ρ)); Xp = X1, ..., X|p|; and {c, ¯ p} ∩ R(Σ) = ∅.

E.g., from q=∃X ∃̂Y r(X, ̂Y) and Σ={r(̂X, Y )→∃Z r(Y,Z)}, we get q′ =∃X ∃Y ¯ r(X, Y ), c(Y ), and Σ′ ={r(X1, X2)→c(X1), c(X2), ¯ r(X1,X2)} and Σ′′ ={¯ r(X, Y ), c(X)→∃Z ¯ r(Y, Z)}. Let us now highlight the key properties of A1.

Lemma 1. A1 ensures ans(q, D, Σ) = ans(q′ , D, Σ′ ∪Σ′′ ), and it behaves as follows: (1) guardedH → guarded; (2) guardedH+ → w-guarded; (3) stickyH+ → w-sticky; (4) w-acyclicH+ → jointly-acyclic; and (5) shyH+ → shy.

Proof Sketch. Via †-rules, each p(t) ∈ D gives rise to a twin atom ¯ p(t), and its constants are collected under the predicate c. Via ‡-rules, each predicate p is renamed in ¯ p, each variable ̂V is replaced by V , and the atom containing V is paired with the atom c(V ). This way, known individuals can be separated from anonymous ones, and c-atoms can mimic the semantics of closed variables. Consider now the range of the reduction; due to space limits, we only consider cases (3) and (4). In case (3), let Σ ∈ stickyH+. Each rules ρ† cannot violate stickiness as no repeated variable appears in b(ρ† ). Now, let X be a variable occurring multiple times in std(b(¯ ρ)), Γ(Vρ ). We distinguish two cases: (i) X was a standard variable in b(ρ). Then, it also occurred multiple times in b(ρ), Hence, by definition of stickyH+, X was not marked in Σ; and by A1 it appears multiple times in std(b(¯ ρ)) only. Hence, X is also not marked in Σ′ ∪ Σ′′ . (ii) X was a closed variable in b(ρ). Then, it appears both in std(b(¯ ρ)) and in Γ(Vρ ). But position c[1] is never involved in cycles going through an ∃-arc of G(Σ′ ∪Σ′′ ). Hence, Σ′ ∪Σ′′ ∈ wsticky. In case (4), let Σ ∈ w-acyclicH+. Note that, given an existential variable X appearing in Σ′ ∪ Σ′′ (and so in Σ), for each i, p[i] and c[1] are not invaded by X. Assume that there is a loop in G∃(Σ′ ∪Σ′′ ). Hence, there is a ‡-rule ρ′ s.t. X ∈ EV(ρ′ ), and Y ∈ UV(ρ′ ) is attacked by X. Now, Y cannot appear in c. Hence, it is a standard variable in b(ρ). Then, Y is attacked by X in Σ. Thus, Σ ̸∈ w-acyclicH+. An induction on the length of the cycle concludes the proof.

The next result follows immediately.

Theorem 3. Let C ∈ B. Then, QEVAL for CH queries over CH and CH+ ontologies is decidable.

4 Computational Complexity

We now study the combined and data complexity of QEVAL over our hybrid extensions. The former is calculated by considering everything as input, while the latter by considering fixed both the query and the ontology. From our analysis,

Theorem 4. All results in Table 1 do hold.

Each entry "C1 x-→ C2" reads as follows: Algorithm x defines a reduction Ax from QEVAL over C1 to QEVAL over C2, according to Lemma x possibly combined with Propositions 1 and 2. In particular, if x ∈ {1, 4}, then Ax works in polynomial-time. Symbol ∨ means that the result admits alternative proofs. Each entry "C1 ⊂ C2" comes from Proposition 2. Each entry "Ax" means that the upper bound is explicitly given by Algorithm x. The rest of the section is the proof of Theorem 4. To complete data complexity upper bounds of all naive extensions, consider the following algorithm:

Algorithm 2. Reduction A2 from a hybrid triple 〈D, Σ, q〉

† Σ′ ← {p(Xp ) →Γ(Xp ), ¯ p(Xp ), p[c|p| ] (Xp ) : p ∈ R(Σ)}; ‡ Σ′′ ← {std(b(ρω ) → h(ρω ), h(¯ ρ), Γ(Cρ )) : ρ ∈ Σ, ω ∈ Ωρ}; q′ ← std(¯ q), Γ(Vq ); return 〈D, Σ′ ∪ Σ′′ , q′ 〉;

Legend. c|p| is the tuple c, ..., c of symbols having length |p|; Ωρ collects all maps of the form ω : vars(ρ) → {c, o} such that ω(x) = o if x ∈ EV(ρ), and ω(x) = c if x ∈ UV(ρ) ∩ Vc (symbols c and o stand for closed and open, respectively); ρω denotes the rule obtained from ρ by replacing each atom of the form p(X) with p[ω(X)](X); and the rest is as in A1.

Basically, A2 avoids Γ(Vρ ) in rule bodies by encoding in predicates those positions where only known individuals may occur. E.g., from q = ∃X ∃̂Y r(X, ̂Y) and Σ={ρ}, where ρ =r(̂X, Y )→∃Z r(Y,Z), we get Ωρ ={ω1, ω2} s.t.: ω1(̂Y)= ω2(̂Y)=c, ω1(Z)=ω2(Z)=o, ω1(Y )=c, ω2(Y )=o. Hence, Σ′ ← {r(X1, X2) → c(X1), c(X2), ¯ r(X1, X2), r[c,c](X1, X2)} Σ′′ ← {r[c,c](X, Y ) → ∃Z r[c,o](Y, Z), ¯ r(Y, Z); r[c,o](X, Y ) → ∃Z r[o,o](Y, Z), ¯ r(Y, Z)} q′ ← ∃X ∃Y ¯ r(X, Y ), c(Y )

By considering any universal model U of D ∪ Σ′ ∪ Σ′′ - i.e., a representative model of any other [Cal`ı et al., 2013]- subscripts guarantee that whenever there is a substitution µ that maps both the body and the head of a ‡-rule ρω to U, then µ(X) ∈ terms(D) iff ω(X) = c. Then,

Lemma 2. A2 ensures ans(q, D, Σ) = ans(q′ , D, Σ′ ∪Σ′′ ). In particular, it behaves as follows: CH → C for each C ∈ B.

Although exponential (each rule ρ admits 2|UV(ρ)∩Vs| different maps), when combined with Lemma 2, reduction A2 gives us the desired bounds. To complete with upper bounds, we design the following algorithm:

Algorithm 3. Alternating decision procedure A3

Input: Hybrid-world triple 〈D, Σ, q〉 where Σ is in normal form ∆ ← terms (D, Σ) ∩ C; / ∗ known ∗ / k ← (1 + |vars(q)|) · maxp∈R(Σ) |p|; I ← {a1, ..., ak} ⊂C such that ∆∩ I = ∅; / ∗ anonymous ∗ / guess a ∆-substitution µ : vars(q) → ∆ ∪ I Q ← µ(atoms(q)) and Iq ← terms(Q) ∩ I for each a ∈ Iq do / ∗ guess atom αa introducing each a ∗ / guess αa ∈ {p(t, a) : p ∈ R(Σ), t ∈ (∆ ∪ I)|p|-1 } † for each α ∈ Q universally do / ∗ prove each atom α ∗ / if α ∈ D then accept else guess ρ ∈ Σ and a ∆-substitution µ : vars(ρ) → {∆∪I} if µ is not compatible with α then reject else Q ← µ(b(ρ)) and goto step †

Legend. Σ is in normal form if, for each ρ ∈ Σ, |h(ρ)| = 1, |EV(ρ)| ≤ 1, and |EV(ρ)| = 1 implies the existential variable is in the last position; µ is not compatible with α if one of the following occurs: µ(h(ρ)) ̸= α; or X ∈ EV(ρ), µ(X) ∈ Iq, and α ̸= αµ(X); or µ maps some non-frontier variable into Iq.

It is a resolution-based algorithm, generally working in alternating polynomial space, hence in exponential time.

Lemma 3. If Σ is stickyH+ or shyH+, thenA3 is correct and it runs in EXPTIME. If Σ ∈ linearH, then A3 runs in PSPACE.

Proof Sketch. A3 proves the query q by exploring a "small" (at most exponential) portion of some universal model of D∪Σ. In case of linear rules, the algorithmworks in nondeterministic polynomial space as step † is universal only once, namely at the very beginning when Q contains the image µ(atoms(q)) of q.

We close the section by providing missing lower bounds:

Algorithm 4. Reduction A4 from a standard triple 〈D, Σ, q〉 Vp ← protectedVars(Σ); Σ′ ← {cls(ρ,Vp) : ρ ∈ Σ}; return 〈D, Σ′ , q〉;

Legend. Vp collects all protected standard universal variables of Σ and cls(ρ,Vp) replaces each variable X ∈ Vp by the closed one ̂X.

Lemma 4. A3 ensures ans(q,D,Σ) = ans(q,D,Σ′ ). In particular, it behaves as follows: 1) datalog → CH+ for each C ∈ B; and 2) w-guarded → guardedH+.

Proof Sketch. Equality of certain answers follows by the fact that protected variables implicitly behave as closed ones.

1. Let Σ ∈ datalog. Then, each variable appearing in Σ is protected. Hence, each rule in Σ′ has closed variables only. Thus, Σ′ belongs to each refined extension, as the syntactic conditions are enforced over standard variables only.
2. Let Σ ∈ w-guarded. Let ρ ∈ Σ, and ρ′ be the corresponding rule in Σ′ . Then, by definition of w-guarded, there is an atom in ρ that covers all the non-protected universal variables appearing in b(ρ). Hence, the corresponding atom in ρ′ covers all the standard universal variables appearing in b(ρ′ ), as each protected variable is replaced by a closed one. Thus, Σ′ ∈ guardedH+.

5 Expressive Power

We now investigate the expressiveness of datalog∃,H . After showing that there are simple hybrid ontologies that cannot be expressed by any datalog∃ one under model equivalence, we consider the classical notion of program expressive power [Arenas et al., 2014], also known as query inseparability, which relies on answer equivalence and turns out to be more appropriate for OBQA purposes. However, also in this case we can show that datalog∃,H is strictly more expressive than datalog∃ . In particular, for both extensions of each basic datalog∃ class, we prove a strict increase in expressiveness. We close the section by showing that linearH+ is strictly more expressive than the Description Logic ELH [Brandt, 2004b].

5.1 datalog∃,H versus datalog∃

Two ontologies Σ1 and Σ2 are model-equivalent (ME), shortly Σ1 ≡ Σ2, if mods(D, Σ1) = mods(D, Σ2), for each database D. Accordingly, a class C2 of ontologies is strictly more expressive (under ME) than C1, denoted by C1 < C2, if (M1) for each Σ1 ∈ C1 there is Σ2 ∈ C2 s.t. Σ1 ≡ Σ2, and (M2) for some Σ2 ∈ C2 there is no Σ1 ∈ C1 s.t. Σ1 ≡ Σ2.

Theorem 5. It holds that: (i) datalog∃ < datalog∃,H , and (ii) both C < CH and C < CH+, for each C ∈ B.

Proof. Consider the ontology Σ = {p(̂X) → r(̂X)}. We proceed by contradiction. Assume Σ admits a model-equivalent datalog∃ ontology Σ′ . Let D∅ = ∅. According to Section 2, M1 = {p(1)} is a model of D∅ ∪ Σ as the interpretation domain of the closed variables is empty. Hence, M1 is a model of D∅ ∪ Σ′ . Let D1 = {p(1)}. In this case, M1 = {p(1)} is not a model of D1 ∪ Σ as r(1) is required. Thus M1 is not a model of D1 ∪ Σ′ . But this is not possible for classical first-order theories. In fact, M1 ⊇ D1. Hence, if M1 is not a model of D1 ∪ Σ′ the only reason is that there exists some rule ρ ∈ Σ′ that is not satisfied. But since M1 ⊇ D∅ also holds, this means that M1 cannot be a model of D∅ ∪ Σ′ as the same rule ρ would be unsatisfied. Hence, (i) follows since datalog∃ ⊂ datalog∃,H , while (ii) holds since, for each C ∈ B, C ⊂ CH ⊂ CH+ by Proposition 2, and Σ ∈ CH.

We now consider a smoother notion of expressiveness. Two ontologies Σ1 and Σ2 are answer-equivalent (AE), shortly Σ1 ∼= Σ2, if ans(q, D, Σ1) = ans(q, D, Σ2), for each database D and for each query q. Hence, if two ontologies are model-equivalent, then they are also answer-equivalent (i.e., Σ1 ≡ Σ2 implies Σ1 ∼= Σ2, for each Σ1 and Σ2). Similarly, a class C2 of ontologies is strictly more expressive (under AE) than C1, denoted by C1 ≺ C2, if (A1) for each Σ1 ∈ C1 there is Σ2 ∈ C2 s.t. Σ1 ∼= Σ2, and (A2) for some Σ2 ∈ C2 there is no Σ1 ∈ C1 s.t. Σ1 ∼= Σ2. Note that, if C1 < C2 (resp., C1 ≺ C2), then condition (A1) (resp., (M2)) is guaranteed.

By Lemma 4, ontology Σ = {p(̂X) → r(̂X)} in the proof of Theorem 5 admits an answer-equivalent datalog∃ ontology. Indeed, it is the output of reduction A3 when it takes the ontology std(Σ) = {p(X) → r(X)} as input. Hence, to prove the next result, we need a stronger argument.

Theorem 6. It holds that: (i) datalog∃ ≺ datalog∃,H , and (ii) C ≺ CH, C ≺ CH+, and also datalog ≺ CH+, for each basic class C ∈ B.

Proof. Consider Σh = {p(̂X) → r(̂X)} ∪ {→ ∃Y p(Y )}. We proceed by contradiction. Assume Σh admits an answerequivalent datalog∃ ontology Σ′h . Let q1 = ∃X p(X), r(X) and Dc = {p(c)}, for each constant c ∈ C. According to Section 2, ans(q1,Dc,Σh) = {〈〉}, and therefore also ans(q1,Dc,Σ′h ) = {〈〉}. Since Σ′ is a standard first-order theory, this means that Dc ∪Σ′h |= q1, and therefore that Σ′h |= {p(c) → q1}, or equivalently mods(Σ′h ) ⊆ mods({p(c) → q1}). Hence, we have that mods(Σ′h ) ⊆ ⋂c∈C mods({p(c) → q1}). But the common models are exactly those of φ1 = ∃Y p(Y ) → q1. Therefore, mods(Σ′h ) ⊆ mods(φ1). Let q2 = ∃Xp(X) and D∅ = ∅. Clearly, ans(q2,D∅,Σh) = {〈〉}, and therefore also ans(q2,D∅,Σ′h ) = 〈〉. But this means that Σ′h |= q2, or equivalently mods(Σ′h ) ⊆ mods(q2). By combining the above results, we have mods(Σ′h ) ⊆ mods(φ1) ∩ mods(q2). But the common models are exactly those of q1. This means that mods(Σ′h ) ⊆ mods(q1), from which we get Σ′h |= q1, implying that ans(q1,D∅,Σ′h ) = {〈〉}. But this is not possible since ans(q1,D∅,Σh) = ∅. Hence, (i) follows since datalog∃ ⊂ datalog∃,H , while (ii) holds since, for each C ∈ B, C ⊂ CH ⊂ CH+ by Proposition 2, and Σh ∈ CH, and since datalog ≺ CH+ holds by Lemma 4.

5.2 linearH+ versus ELH

We now show that linearH+ is strictly more expressive than ELH [Brandt, 2004a; 2004b], even if we focus on linearH+ ontologies with bounded-rules (namely, both arities and number af atoms of each rule are bounded by some integer constant), in which case the combined complexity of QEVAL drops to NP as the complexity of QEVAL for C queries over ELH. (Note that ELH is not expressible in linearH.) In particular, we provide a polynomial time transformation that maps ELH ontologies into answer-equivalent linearH+ ones. This also shows that ELH is no more succinct than linearH+.

In DLs, rules are called inclusions, which in ELH are of the form: C ⊑ D; C ⊓ D ⊑ E; R ⊑ S; C ⊑ ∃R.D; ∃R.D ⊑ C; where C, D, E are concepts, and R, S are roles. According to the semantics of DLs, they are modelequivalent (hence answer-equivalent) to the following existential rules [Baader et al., 2003], respectively: (i) C(X) → D(X); (ii) C(X), D(X) → E(X); (iii) R(X, Y ) → S(X, Y ); (iv) C(X) → ∃Y R(X, Y ),D(Y ) (v) R(X, Y ),D(Y ) → C(X). Only rules of the form (i), (iii), and (iv) are linear.

To obtain a linearH+ ontology answer-equivalent to an ELH one, a possible way is to "close" join variables in the body of non-linear rules, i.e., of the form (ii) and (v). This would preserve soundness, but not necessarily completeness. Hence, to guarantee answer equivalence, one should complement such (hybrid) rules with new linear ones that "bypass" propagations inhibited by closed variables. Formally,

Theorem 7. Under answer-equivalence, linearH+ with bounded-rules is strictly more expressive than ELH. In particular, for each ELH ontology, an equivalent linearH+ one of quadratic size can be constructed in polynomial time.

Proof Sketch. Given an ELH ontology Σ in datalog∃ form, we construct a datalog∃,H ontology Σ′ as follows: (0) Let Σ′ = ∅; (1) Add to Σ′ each rule of Σ of the form (i), (iii) or (iv); (2) For each rule of Σ of the form (ii) (resp., (v)), add to Σ′ the hybrid rule C(̂X),D(̂X) → E(̂X) (resp., R(X, ̂Y), D(̂Y) → C(X)); (3) For each pair (B, A) of unary predicates (i.e., concepts) occurring in Σ, add to Σ′ the standard "bypass" rule B(X) → A(X), provided that Σ logically entails the rule B(X) → A(X), namely whether Σ |= B ⊑ A (B is subsumed by A in Σ) in DLs terminology. By construction, Σ′ is linearH+. Also, the addition of bypass rules makes Σ′ answer-equivalent to Σ (they share the same universal models). This completes our reduction, which works in polynomial time, since it is known that also concept subsumption in ELH can be performed in polynomial time [Brandt, 2004a]. Regarding the size of Σ′ , it suffices to observe that |Σ′ | = |Σ| at the end of step (2), and also that the number of rules added at step (3) are at most quadratic in the number of concepts occurring in Σ. To conclude our proof, we consider the linearH+ ontology Σ = {p(̂X), s(̂Y) → g(̂X, ̂Y)}. It is well-known that Σ cannot be expressed in ELH, as it defines the so-called cross-product, namely p × s ⊑ g.

6 RelatedWork

Interest in reconciling open- and closed-world semantics has a long history [Cadoli et al., 1990]. Since then, different paradigms have been proposed: epistemic and modal operators [Donini et al., 1992; Calvanese et al., 2007], hybrid knowledge bases [Motik et al., 2005; Rosati, 2005; 2006; Eiter et al., 2008; Kr¨otzsch et al., 2008; Motik and Rosati, 2010; Knorr et al., 2011; Libkin and Sirangelo, 2011; Bajraktari et al., 2017], closed predicates [Seylan et al., 2009; Lutz et al., 2013; 2015; Ngo et al., 2016], and nominal schemas [Kr¨otzsch et al., 2011; Kr¨otzsch and Rudolph, 2014].

In case of monotonic Horn DLs, modal operator K behaves as closed variables. Indeed, axiom KC ⊑ D is answer-equivalent to the rule C(̂X) → D(̂X). Hybrid KBs typically combine DLs and rule-based formalisms by enforcing syntactic safety condition, while closed predicates are those whose extensions have to be interpreted as complete. So, they are less related to our framework, although we borrowed from them some useful tool, as said in Section 3. Nominal schemas, instead, represent the proposal which is closest to ours. Intuitively, a nominal variable {z} is represents some arbitrary nominal (i.e., known individual). When occurring in the left-hand side of a concept inclusion, {z} behaves as the closed variable ̂Z. Indeed, axiom ∃hasParent.{z} ⊓ ∃hasParent.∃married.{z} ⊑ C is model-equivalent to hasParent(X, ̂Z), hasParent(X, Y ), married(Y, ̂Z) → C(X). But in DLs, {z} may also be existentially quantified to mimic disjunction among nominals.

Concerning expressiveness, different notions have been also considered in the literature. In [Gottlob et al., 2014], Σ1 and Σ2 are gr-equivalent if ans(q,D,Σ1) = ans(q,D,Σ2), for each database D and query q ∈ G, where G collects ground queries, i.e., all variable-free atoms. Under this notion guarded ≺gr datalog, and datalog∃,H is no more expressive than datalog∃ (the latter obtained via a minor modification of Algorithm 1). Indeed, closed variables do not increase the so-called query expressivity [Rudolph and Thomazo, 2015], defined by fixing a special predicate goal as the only possible ground query. In [Gottlob et al., 2018], (Σ1, q1) and (Σ2, q2) are re-equivalent if ans(q1,D,Σ1) = ans(q2,D,Σ2), for each database D. Then, 〈guarded,C〉 ≺re 〈datalog,G〉 and also 〈sticky, C〉 ⪯re 〈∅, UC〉, where UC is the class of union of conjunctive queries. Differently from program expressive power, however, these notions are more suitable to compare ontology formalisms from a computational viewpoint rather than from a knowledge representation one. Indeed, reequivalence coincides with the so-called query rewritability.

7 FutureWork and Conclusion

In conclusion, closed variables represent a very natural, flexible and effective extension of standard existential rules. In the future, we would like to investigate whether our naive or refined extensions can express other ontology languages, as well as to close a question that has been left (partially) open in Theorems 5 and 6 concerning the expressivity of CH vs. CH+ by varying C. Indeed, so far, what is known is a strict increase in expressivity in the two cases exhibiting a jump in data complexity from AC0 to PTIME, namely when C ∈ {linear, sticky}. Also, it would be reasonable to extend the computational analysis to other known classes. Interestingly, concerning the latter point, while moving to decidable "abstract" (i.e., not recognizable) classes of rules [Baget et al., 2011], such as fes generalizing w-acyclic, we realized that there are ontologies in fesH that are not mapped to fes via Algorithm 1; hence, a separate approach is needed here. Also, one could study the impact of stratified negation in rules and queries, for reasoning even on the anonymity of individuals. As for nominal schemas in DLs, existentially quantified closed variables can be certainly considered to mimic some form of disjunction. Finally, implementing closed variables in some existing datalog∃ system as well as testing performances on real-world ontologies are also tasks in our agenda.

Acknowledgments

The paper has been partially supported by the MISE under project "S2BDW" (n. F/050389/01-03/X32) - "PON I&C 2014-20, and by Regione Calabria under project "DLV Large Scale" (CUP J28C17000220006) - POR Calabria 2014-20.