A Datalog Rewriting Algorithm for Warded Ontologies

1 Introduction

Ontological reasoning is a fundamental task in Knowledge Representation and Reasoning (KRR) and Artificial Intelligence in general, as it enables the development of intelligent data management systems, where data is enriched with additional knowledge that can be derived by means of an ontology, i.e., a logic-based formalization of the domain of interest. A prominent formalism for encoding ontologies is the one of existential rules, a.k.a. tuple-generating dependencies (TGDs), which allow to encode knowledge by means of implication-like formulas, specifying how new knowledge can be derived from existing knowledge known about the system. In this context, the key task is Ontology-Mediated Query (OMQ) Answering. That is, given a database D, containing known facts about the system, and an OMQ O = (q,Σ), where Σ is a TGD-based ontology, and q a conjunctive query (CQ), OMQ Answering is the task of finding the so-called certain answers to O over the database D. It is well-known that the problem of OMQ Answering is uncomputable, in general (e.g., see [Cal`ı et al., 2013]).

Thus, a long stream of literature has been developed in the last decades, devoted to identify fragments of TGD-based ontologies that guarantee the computability of certain answers. See for example acyclicity-based TGD languages [Fagin et al., 2005; Greco et al., 2011; Spezzano and Greco, 2010; Calautti et al., 2016; Carral et al., 2017; Calautti et al., 2015; Calautti and Pieris, 2021; Calautti et al., 2022], as well as UCQ-rewritable languages [Cal`ı et al., 2012a; Cal`ı et al., 2012b]. More expressive languages are the ones based on the notion of guardedness [Cal`ı et al., 2012a; Baget et al., 2011; Benedikt et al., 2022], and beyond [Cal`ı et al., 2013]. We point out that some of the above works have been influenced by earlier works on Description Logics (DL), e.g., see [Calvanese et al., 2007; Poggi et al., 2008; Artale et al., 2009] for UCQ-rewritable DL ontologies, and [Baader et al., 2005; Lutz and Sabellek, 2022] for guarded-like DL ontologies. We refer to [Baader et al., 2003] for a comprehensive overview.

Despite all the above efforts, each of the above TGDbased languages has at least one of two downsides: they either have limited expressive power (e.g., UCQ-rewritable or guarded-based ones), or they are highly expressive but OMQ Answering becomes computationally challenging. To remedy the above situation, warded TGDs have been introduced in [Gottlob and Pieris, 2015], striking a good balance between expressive power and computational complexity. In particular, warded ontologies are expressive enough to capture the full power of Datalog, meaning they can express important properties of data, such as the transitive closure of graphs, but at the same time keep certain answers computation feasible in polynomial time in data complexity, i.e., w.r.t. the size of the input database. The above complexity result has been first shown in [Gottlob and Pieris, 2015] by means of specialized alternating algorithms, while more recent works have shown that warded ontologies are actually Datalog-rewritable [Berger et al., 2022]. That is, every OMQ O = (q,Σ) with Σ warded can be rewritten to a Datalog query DO such that for every database D, the certain answers of O over D coincide with the answers of DO over D. Although wardedness can be considered as the sweet spot between expressiveness and complexity, we are not aware of any efforts from the literature that exploit such a rich theory to develop practical implementations of OMQ Answering over warded TGDs. One of the main reasons is that the results of [Gottlob and Pieris, 2015; Berger et al., 2022] are mostly theoretical in nature. In particular, the Datalog rewriting algorithm of [Berger et al., 2022], constructs an equivalent Datalog query via a naive brute force search over the (exponentially large) space of so-called proof trees of the OMQ at hand. In fact, the only real-world system we are aware of that supports, to some extent, warded ontologies, is the Vadalog system [Bellomarini et al., 2018; Bellomarini et al., 2022; Bellomarini et al., 2024], which supports a simpler version of OMQ Answering, where the CQ is atomic, and uses a procedure different from the ones of [Gottlob and Pieris, 2015; Berger et al., 2022]. The latter, together with the fact that Vadalog is available only after acquiring a license, severely limits the use of warded TGDs in practice.

Contributions. The goal of our work is to rectify the above state of affairs by providing a new Datalog rewriting algorithm for OMQs over warded ontologies, dubbed WardedRewrite, that is more amenable to practical implementations, supporting OMQs O = (q,Σ), where Σ is a warded TGD-based ontology, and q an arbitrary CQ, thus going beyond the capability of existing systems that support the warded language. We then implement WardedRewrite, and perform an experimental analysis that highlights the applicability of our implementation, and provides key insights on the capability of different off-the-shelf Datalog-based engines in computing certain answers over OMQs with warded ontologies, via the evaluation of the Datalog query obtained using our algorithmWardedRewrite.

The full source code and the benchmark data are available at: https://gitlab.com/mcalautti/warded-rewriting-paper.

2 Preliminaries

We consider the disjoint countably infinite sets C, N, and V of constants, (labeled) nulls, and variables, respectively. We refer to constants, nulls and variables as terms. For an integer n > 0, we write [n] for the set of integers {1, . . . , n}.

Relational Databases. A schema S is a finite set of relation symbols (or predicates) with associated arity. We write R/n to denote that R has arity n > 0; we may also write ar(R) for the integer n. A (predicate) position of S is a pair (R, i), where R/n ∈ S and i ∈ [n], that essentially identifies the i-th argument of R. We write pos(S) for the set of positions of S, that is, the set {(R, i) | R/n ∈ S and i ∈ [n]}. An atom over S is an expression of the form R(¯ t), where R/n ∈ S and ¯ t is an n-tuple of terms. A fact is an atom whose arguments consist only of constants. We write var(R(¯ t)) for the set of variables in ¯ t. The notation var(·) extends naturally to other objects mentioning variables. An instance over S is a (possibly infinite) set of atoms over S with constants and nulls. A database D over S is a finite set of facts, i.e., a finite instance mentioning only constants. The active domain of an instance I, denoted dom(I), is the set of terms occurring in I.

Homomorphisms and Conjunctive Queries. A substitution from a set of terms T to a set of terms T ′ is a function h : T → T ′ . A homomorphism from a set of atoms A to a set of atoms B is a substitution h from the set of terms in A to the set of terms in B such that h is the identity on C, and R(t1, . . . , tn) ∈ A implies h(R(t1, . . . , tn)) = R(h(t1), . . . , h(tn)) ∈ B. For an integer k ≥ 0, a kary conjunctive query (CQ) q over a schema S with output variables ¯x, denoted q(¯x), is an expression of the form Q(¯x) ← ∃¯ y R1(¯x1) ∧ . . . ∧ Rn(¯xn), where, for each i ∈ [n], ¯xi is a tuple of variables, and ¯x, ¯ y form a partition of the set of variables ⋃i∈[n] ¯xi; by abuse of notation, we treat a tuple of variables as a set of variables. Moreover, ¯x is a tuple of k (not necessarily distinct) variables, and Q(¯x) and Ri(¯xi), for i ∈ [n], are atoms with Ri ∈ S, while Q ̸∈ S. For convenience, we may use comma in place of the symbol ∧, and we may omit the existential quantifier. The body (resp., head) of q, denoted body(q) (resp., head(q)) is the set of atoms {R1(¯x1), . . . ,Rn(¯xn)} (resp., the atom Q(¯x)). We use headPred(q) to denote the predicate Q. For an instance I over S, we write q(I) for the answers of q over I, defined as {¯ t ∈ (dom(I) ∩ C)k | ∃ a homomorphism h from body(q) to I with h(¯x) = ¯ t}.

Tuple-Generating Dependencies. A tuple-generating dependency (TGD) σ over a schema S is a (constant-free) expression of the form ∀¯x∀¯ y (ϕ(¯x, ¯ y) → ∃¯ z ψ(¯x, ¯ z)) , where ¯x, ¯ y and ¯ z are tuples of variables of V, and ϕ(¯x, ¯ y) and ψ(¯x, ¯ z) are non-empty conjunctions of atoms over S that only mention variables from ¯x∪ ¯ y and ¯x∪ ¯ z, respectively. We may write σ as ϕ(¯x, ¯ y) → ∃¯ z ψ(¯x, ¯ z), and use comma instead of ∧ for joining atoms. We refer to ϕ(¯x, ¯ y) and ψ(¯x, ¯ z) as the body and head of σ, denoted body(σ) and head(σ), respectively. We say that σ is full if ¯ z is empty, and we say it is single-head if ψ(¯x, ¯ z) contains a single atom. The frontier of the TGD σ, denoted fr(σ), is the set of variables ¯x, i.e., the variables that appear both in the body and the head of σ. We use exvar(σ) and expos(σ) to denote the set of all existential variables of σ, and the set of all positions in which an existential variable of σ occurs. An ontology Σ over a schema S is a finite set of TGDs over S. The schema of an ontology Σ, denoted sch(Σ), is the set of predicates occurring in Σ. Moreover, we assume w.l.o.g. that no two TGDs in Σ share a variable. We use TGD to denote the class of all ontologies.

An instance I satisfies a TGD σ as the one above, written I |= σ, if whenever there exists a homomorphism h from ϕ(¯x, ¯ y) to I, then there is an extension of h that is a homomorphism from ψ(¯x, ¯ z) to I; we may treat a conjunction of atoms as a set of atoms. The instance I satisfies an ontology Σ, written I |= Σ, if I |= σ for each σ ∈ Σ.

Ontology-Mediated Queries. The main task we are interested in this paper is query answering under TGDs. Consider a database D over a schema S and an ontology Σ over S. A model of D and Σ is an instance I over S such that D ⊆ I and such that I |= Σ. We use models(D,Σ) to denote the set of all models of D and Σ. For an integer k ≥ 0, a k-ary ontology-mediated query (OMQ) over a schema S is a pair O = (q, Σ), where q is a k-ary CQ over S, and Σ is an ontology over S. For a database D over S, the certain answers of O over D is the set of tuples ans(O, D) defined as

The Chase Procedure. The chase procedure is an algorithm that can be used to produce a so-called universal model of a database D and ontology Σ, which in turn can be used to provide an alternative definition of certain answers of OMQs. Consider an instance I and an ontology Σ over a schema S. A trigger for Σ on I is a pair (σ, h), where σ ∈ Σ and h is a homomorphism from body(σ) to I. The result of (σ, h), denoted result(σ, h), is the set µ(head(σ)), where µ : var(head(σ)) → C ∪ N is such that µ(x) = h(x) if x ∈ fr(σ), and µ(x) = ⊥xσ,h , with ⊥xσ,h ∈ N, otherwise.

For a database D and an ontology Σ over a schema S, the chase of D w.r.t. Σ is the set chase(D,Σ) of atoms inductively defined as follows. We define chase0 (D,Σ) = D, and for each i > 0, chasei (D,Σ) = chasei-1 (D,Σ) ∪ {result(σ, h) | (σ, h) is a trigger for Σ on chasei-1 (D,Σ)}. Finally, chase(D, Σ) = ⋃i≥0 chasei (D, Σ).

The following is well-known [Grahne and Onet, 2018]:

Theorem 1. For a k-ary OMQ O = (q, Σ) and a database D over a schema S, ans(O,D) = {¯ t ∈ dom(D)k | ¯ t ∈ q(chase(D, Σ))}.

3 Wardedness and Datalog Rewritability

At the high-level, a warded ontology Σ restricts how some of the variables of its TGDs, called "dangerous" variables, are used. We now proceed to formally define the above notions; in what follows, fix an ontology Σ.

Affected Positions. First, we need the notion of affected positions. For a position (R, i) ∈ pos(sch(Σ)), we inductively say that (R, i) is an affected position of Σ as follows: there exists a TGD σ ∈ Σ with (R, i) ∈ expos(σ), or there exists a TGD σ ∈ Σ and a variable x ∈ fr(σ) occurring at (R, i) in the head of σ such that x occurs in body(σ) only at affected positions. We use aff(Σ) to denote the set of all affected positions of Σ, and notaff(Σ) = pos(sch(Σ)) \ aff(Σ) to denote set of all position of Σ that are not affected. Intuitively, when a position (R, i) of Σ is not affected, it is guaranteed that for every database D, every atom of the form R(t1, . . . , tn) ∈ chase(D, Σ) is such that ti is a constant.

Wardedness. Consider a variable x occurring in the body of some TGD σ of Σ. We say that x is harmless if it occurs in body(σ) at some position of notaff(Σ); harmful if it is not harmless, i.e., it occurs in body(σ) only at positions of aff(Σ); dangerous if it is harmful and it is a frontier variable of σ. We say that Σ is warded if for each TGD σ ∈ Σ there exists an atom α ∈ body(σ), called the ward of σ, such that (i) all dangerous variables of σ occur in α, and (ii) each variable in var(α) ∩ var(body(σ) \ {α}) is harmless. We use WARDED to denote the set of all warded ontologies.

Datalog Rewritability and Wardedness. A Datalog program is an ontology Σ containing only full, single-head TGDs, which we also call (Datalog) rules. A k-ary Datalog query is a pair D = (R,Σ), where Σ is a Datalog program, and R/k ∈ sch(Σ). A predicate occurring in Σ is intensional if it occurs in the head of some rule of Σ, otherwise, it is extensional. We use idb(D) and edb(D) to denote the set of all intensional and extensional predicates of D, respectively. For a Datalog query D = (R,Σ), and a database D over edb(D), the answers of D over D is the set D(D) = {¯ t ∈ dom(D)k | R(¯ t) ∈ chase(D,Σ)}. A class C of ontologies is Datalog-rewritable if for every OMQ O = (q,Σ) over a schema S, with Σ ∈ C, there exists a Datalog query DO = (RO,ΣO) with edb(DO) ⊆ S and idb(DO) ∩ S = ∅, called a Datalog rewriting of O, such that for every database D over S, ans(O,D) = DO(D′ ), with D′ = {R(¯ t) ∈ D | R ∈ edb(DO)}. It is known that WARDED is Datalog-rewritable [Berger et al., 2022].

4 ADatalog Rewriting Algorithm forWarded

We present a new algorithm that is able to produce a Datalog rewriting of a given OMQ O = (q, Σ) with Σ ∈ WARDED that is more amenable to be implemented in practice.

At the high-level, given an OMQ O = (q,Σ), with Σ ∈ WARDED, our algorithm exhaustively applies, starting from the query q, one of the following two basic steps to the current query being processed: decomposition and resolution. The decomposition step is in charge of decomposing the query being processed into the smallest possible, independently processable queries. The resolution step is in charge of unfolding the smaller queries using the TGDs of the ontology. The latter step is the same employed by other algorithms from the literature that deal with UCQ-rewritable OMQs. We recall that a union of conjunctive queries (UCQ) is a Datalog query (R, Σ) containing only rules having R as their head predicate, and R does not occur in their body. However, the decomposition step is what distinguishes our algorithm from ones for UCQ-rewritable languages, as it guarantees the construction of a finite Datalog query, when focusing on warded ontologies. We now introduce the basic notions needed to define the above two steps.

Chunk-Based Resolution. Let A and B be non-empty sets of atoms that mention only variables. The sets A and B unify if there is a substitution γ, called unifier for A and B, such that γ(A) = γ(B). A most general unifier (MGU) for A and B, denoted mgu(A,B), is a unifier for A and B such that for each unifier γ for A and B, γ = γ ′ ◦ mgu(A,B), for some substitution γ ′ . It is well-known that if two sets of atoms unify, then there is always a MGU, which is unique (modulo variable renaming). Given a CQ q(¯x) and a set of atoms S ⊆ body(q), we say that a variable y ∈ var(S) is shared in q (w.r.t. S), if y ∈ ¯x or y ∈ var(body(q) \ S). We use shared(q, S) to denote the set of all variables in S that are shared in q w.r.t. S. We can now recall chunk unifiers. 1

Definition 2. Consider a CQ q(¯x) and a TGD σ having no variables in common with q. A chunk unifier of q with σ is a triple (S1, S2, γ), where

• ∅ ⊊ S1 ⊆ body(q) and ∅ ⊊ S2 ⊆ head(σ);
• γ is a unifier for S1 and S2;
• for each x ∈ var(S2) ∩ exvar(σ), and for each variable y ̸= x, γ(x) = γ(y) implies that y occurs in S1 (and thus y ̸∈ var(S2)) and that y ̸∈ shared(q, S1).

We say that a chunk unifier (S1, S2, γ) is most general (MGCU) if γ is an MGU for S1 and S2.

1 Chunk-unifiers, employed in most works related to wardedness, are equivalent to the piece-unifiers from [K¨onig et al., 2015].

In other words, an MGCU faithfully describes how the chase would trigger σ producing a set of atoms to which the atoms in S1 would homomorphically map.

The notion of chunk-based resolution follows naturally.

Definition 3. Consider a CQ q(¯x), with headPred(q) = Q, a TGD σ, and a MGCU M = (S1, S2, γ) of q with σ. The σ-resolvent of q (viaM), denoted by resolvσ,M(q), is the CQ q′ with head(q′ ) = Q(γ(¯x)), and body(q′ ) = γ((body(q) \ S1) ∪ body(σ)).

As we are going to see in Section 4.1, a resolution step exhaustively applies chunk-based resolution on a given CQ.

Query Decomposition. We now move to the notions needed to implement the other step of our algorithm: the decomposition step. We start with the notion of existential-join decomposition, employed for other tasks in [Gottlob et al., 2014].

Definition 4. Consider a CQ q(¯x) with headPred(q) = Q, and an ontology Σ. An existential-join decomposition of q w.r.t. Σ, or simply decomposition, is a set of n > 1 CQs S = {q1(¯x1), . . . , qn(¯xn)} where {body(q1), . . . , body(qn)} is a partition of body(q), headPred(qi) = Qi for i ∈ [n], and for each i ∈ [n]:

1. ¯xi = shared(q, body(qi)), and
2. for every two atoms α, β ∈ body(q), if α ∈ body(qi) and α and β mention a variable y ̸∈ ¯x occurring only in affected positions of body(q), then β ∈ body(qi).

We say that S is optimal if for each i ∈ [n], there is no existential-join decomposition of qi w.r.t. Σ.

The main idea behind an optimal decomposition S = {q1(¯x1), . . . , qn(¯xn)} of a CQ q(¯x) w.r.t. Σ is to factorize the body of q into the smallest subqueries, guaranteeing that the certain answers of (q,Σ) can be retrieved by combining the certain answers of each OMQ (qi, Σ), for i ∈ [n]. In particular, assuming headPred(q) = Q, and headPred(qi) = Qi, for i ∈ [n], the reconciliation rule of S and q is the (full) TGD of the form Q1(¯x1), . . . ,Qn(¯xn) → Q(¯x). In other words, the reconciliation rule of S and q performs the inverse of the decomposition, i.e., it combines the certain answers of each member of S, so to restore the certain answers of the CQ q.

4.1 The AlgorithmWardedRewrite

In the following, for a CQ q(¯x) of the form Q(¯x) ← R1(¯x1), . . . , Rn(¯xn), we use rule(q) to denote the (full) TGD of the form R1(¯x1), . . . ,Rn(¯xn) → Q(¯x). Moreover, for a full TGD σ of the form R1(¯x1), . . . , Rn(¯xn) → Q(¯x), with Q different from each Ri, we use cq(σ) to denote the CQ of the form Q(¯x) ← R1(¯x1), . . . ,Rn(¯xn). Moreover, for a CQ q, we use can(q) to denote the canonical form of q, i.e., the CQ obtained from q where each variable x of q that appears, from left to right in q, as the i-th variable, is replaced with the fresh variable wi. For example, if q is the CQ Q(x, y, y) ← R(y, z, x), S(x, z), then can(q) is the CQ Q(w1,w2,w2) ← R(w2,w3,w1), S(w1,w3). Clearly, two CQs q1 and q2 which are the same, up to variable renaming, are such that can(q1) = can(q2). We extend the above notations to sets in the natural way. Finally, given two CQs q1 and q2, we write q1 ≈ q2 iff can(q1) and can(q2) are the

Input: An OMQ O = (q, Σ) with Σ ∈ WARDED Output: A Datalog rewriting of O 1 Qcurrent := {can(q)}; Qexplored := ∅; Qdec := ∅; R := ∅; 2 while Qcurrent ̸= ∅ do 3 Qnew := ∅; 4 foreach q′ ∈ Qcurrent do 5 if a decomposition of q′ w.r.t. Σ exists then // Decomposition step 6 S := decomposeOptimal(q′ , Σ); 7 ρ := reconciliationRule(q′ , S); 8 foreach q′′ ∈ S do 9 if there is qalt ∈ Qdec with qalt ≈ q′′ then 10 Replace headPred(q′′ ) with headPred(qalt) in body(ρ); 11 else 12 Qdec :=Qdec ∪ {can(q′′ )}; 13 Qnew := Qnew ∪ {can(q′′ )}; 14 R := R ∪ {ρ}; 15 else // Resolution step 16 foreach σ ∈ Σ do 17 foreach MGCU M of q′ with σ do 18 q′′ := resolvσ,M(q′ ); 19 Qnew := Qnew ∪ {can(q′′ )}; 20 R := R ∪ {rule(q′ )}; 21 Qexplored :=Qexplored ∪ {q′ }; 22 Qcurrent :=Qnew \Qexplored; 23 return (headPred(q),R);

same up to head predicate renaming. We now have all the notions we need to present our rewriting algorithm, dubbed WardedRewrite, which we report in Algorithm 1.

Consider an OMQ O = (q, Σ) with Σ ∈ WARDED. The main idea behind the algorithm WardedRewrite is to iteratively apply one of two steps: decomposition and resolution. The set Qcurrent collects the CQs that need to be processed, and it initially contains the (canonical version of) the input query q, while all other structures are initially empty.

For each query in q′ ∈ Qcurrent, the goal is to try first to decompose q′ into smaller subqueries (line 5). If this is possible, then the algorithm constructs the decomposition S of q′ w.r.t. Σ, and the corresponding reconciliation rule ρ (lines 67). Ideally, all queries in S should then be added to the set Qnew for later processing, and ρ added to the set R of rules of the final Datalog rewriting. However, to guarantee termination, the algorithm first checks, for each q′′ ∈ S, whether any previous decomposition step has already produced a query qalt with qalt ≈ q′′ (line 9). If this is the case, there is no need to add q′′ to Qnew, as an identical version has already been processed. Hence, it is enough to replace the occurrence of headPred(q′′ ) in the body of ρ with headPred(qalt) (line 10). If no such a query qalt is found, then the CQ q′′ is really new and its canonical version is added to the set Qnew for later processing, as well as to the set Qdec, in order to remember that q′′ has been produced by a decomposition step (lines 12-13).

Then, the (modified) rule ρ is added to the set R of all rules of the Datalog rewriting (line 14).

If q′ cannot be decomposed, it is instead unfolded by constructing all possible σ-resolvents of q′ , for all TGDs σ ∈ Σ; this is a single resolution step (lines 16-19), which produces a set of new queries that are also added to Qnew for later processing. The (rule version of) q′ is then added to the set of rules R of the final Datalog rewriting (line 20).

After q′ has gone through a decomposition or a resolution step, it is marked as explored in line 21 by adding q′ to the set Qexplored of processed queries. After all queries in Qcurrent have been explored, Qcurrent is updated in line 22 with all new queries in Qnew that have not been explored yet (i.e., that are not in Qexplored), and the process repeats. 2 The algorithm terminates when no new queries (up to variable renaming) have been produced. The final Datalog rewriting is (headPred(q),R) and it is returned in line 23.

We can show the following result.

Theorem 5. For every OMQ O = (q,Σ), with Σ ∈ WARDED, WardedRewrite terminates with input O, and outputs a Datalog rewriting of O.

5 Implementation and Experiments

In this section we discuss how we implemented the algorithm WardedRewrite. Moreover, we present an experimental analysis assessing two aspects: how fast is of our implementation of WardedRewrite to produce the Datalog rewriting, and how efficient existing Datalog-based engines are at evaluating the Datalog query produced by our algorithm.

Implementation

Regarding the implementation, the main challenge is keeping the set of rules R of the final Datalog rewriting as small as possible. This is in order to not hinder the performance of answering the query using off-the-shelf Datalog engines. As an optimization, each time a rule is added to the set R, we consider all predicates Q1, . . . , Qn occurring in the head of some rule of R, and for each i ∈ [n], consider the maximal subset RQi of TGDs with head predicate Qi occurring in R such that (Qi,RQi ) is a UCQ. Then, we minimize each set RQi independently by constructing, for each i ∈ [n], the smallest subset R′Qi of RQi such that (Qi,R′Qi ) and (Qi,RQi ) are equivalent; the latter boils down to checking equivalence between UCQs, which is decidable [Abiteboul et al., 1995].

Experimental Analysis

We now move to our experimental analysis. In particular, our goal is to experimentally evaluate different aspects of our implementation of WardedRewrite. In particular, we are interested to answer two key questions.

Question 1: Given an OMQ O = (q, Σ) with Σ ∈ WARDED as input to our implementation of WardedRewrite, how do key parameters of O affect its running time and scalability?

Answering the above will allow us to provide insights on the practical applicability of our implementation and its limits, as well as providing conclusions on the expected behaviour of the algorithm, depending on the input OMQ.

2 Note that by considering the canonical version of the CQs, performing the set-theoretic difference is enough to exclude from Qnew all queries that have already been considered.

The next natural question is whether the Datalog rewriting produced by our implementation can be actually used for query answering purposes by exploiting existing Datalogbased reasoning systems.

Question 2: Given a database D, an OMQ O = (q, Σ) with Σ ∈ WARDED, and the Datalog rewriting DO produced by WardedRewrite with input O, how efficient existing Datalogbased reasoning engines are in evaluating DO over D?

Towards answering our key experimental questions, we need a way to stress test both our rewriting algorithm WardedRewrite, as well as the Datalog-based reasoning engines we consider. For this, we generate a large pool of synthetic database-OMQ pairs (D, O), which we call scenarios, where O = (q, Σ) and Σ ∈ WARDED, using the IWARDED benchmark generator from [Atzeni et al., 2022]. IWARDED allows to generate scenarios (D,O), with O = (q,Σ) and Σ ∈ WARDED, by considering different parameters. In order to keep our experimental evaluation manageble, we will focus on a few, key parameters that mostly affect either the size of the database, or the main structure of the ontology Σ.

Ontology Parameters. IWARDED generates OMQs (q,Σ), where Σ is warded, and the TGDs have a single head atom and at most two atoms in the body. Moreover, TGDs are generated so to induce multiple sequences of TGDs of the form σ1, . . . , σn, where the atom produced during the construction of the chase by the TGD σi contributes to trigger the TGD σi+1, for each i ∈ [n - 1]. We can control the shape of these sequences by choosing two main parameters.

The average recursion length, denoted avg recursion, specifies the average length of recursive TGD sequences, i.e., sequences of TGDs σ1, . . . , σn in Σ where the TGD σn can further trigger σ1. The length n of the sequence is chosen using a Guassian distribution with avg recursion as the mean, and variance 1.0. The number of left-right-join recursions, denoted num lrj, specifies the number of TGDs that IWARDED will add to Σ that mention two predicates in their body that both belong to a recursive sequence.

Database Parameters. As for the database parameters, we consider the number of facts per predicate, denoted db facts: IWARDED will add db facts random facts to the database D for each predicate of D; the number of predicates of D is chosen automatically by IWARDED so to preserve the values of the ontology-related parameters above.

Query Parameters. There are no parameters we can control regarding the construction of the CQ q. In particular, IWARDED only supports the construction of CQs q of the form Q(¯x) ← R(¯x), i.e., CQs with a single body atom whose tuples are propagated as output of the query; IWARDED automatically adds auxiliary TGDs to Σ so that all the TGD sequences added to Σ "feed" the predicate R with tuples. This guarantees that the certain answers of q are never empty.

Test Scenarios. In generating our scenarios, we consider 21 different values for the number of left-rightjoin recursions num lrj and the average recursion length avg recursion, spanning from 0 to 400 with steps of

20 each. That is, we consider the values in the set {0, 20, 40, . . . , 400} for the above two parameters. We point out that the largest values in this set are quite extreme for an average real-world ontology, and we consider such a large interval in order to strees test our rewriting algorithm, and assess its practical applicability. Regarding the database generation, we consider a fixed value of 100k facts per predicate (db facts). Then, for each combination i, j ∈ {0, 20, 40, . . . , 400}, we generated a scenario, denoted S[i, j], of the form (D,O) with O = (q,Σ), by running IWARDED with input num lrj = i, avg recursion = j, and db facts = 100k, obtaining a total of 441 scenarios.

Experimental Setup. For the experiments, we used an Amazon Elastic Compute Cloud (EC2) instance with an Intel(R) Xeon(TM) Platinum 8000-series @3.6 GHz, 16 GB of RAM, running Amazon Linux 2 LTS Candidate. We implemented the algorithmWardedRewrite in Java 22, and used openJDK 22 for its execution, while the Datalog-based reasoning engines have been executed in their default configuration.

5.1 Evaluating the Rewriting Algorithm

In this section we address our first experimental question. For each of the 441 scenarios S[i, j] = (D, O) with O = (q, Σ) and with i, j ∈ {0, 20, 40, . . . , 400}, we executed our implementation of WardedRewrite with input the OMQ O. For each execution we collected the total running time.

Figure 1 (resp., Figure 2) shows the average running time of our implementation of WardedRewrite, for each value of the parameter num lrj (resp., avg recursion), where the average is computed across all test scenarios having avg recursion (resp., num lrj) in one of 4 intervals, i.e., [0-100], [100-200], [200-300], [300-400].

As we can see from Figure 1, the number of left-rightjoin recursions indeed has an impact on the running time of our implementation of WardedRewrite. We can see that for lower intervals of avg recursion, even the highest value of 400 left-right-join recursions (num lrj) leads to quite fast executions on average; e.g., 5 seconds for the average recursion length interval [0-100], and 33 seconds for [100200]; the highest interval [300-400] leads to some minutes with the higher values of num lrj. The trend is somehow expected, since the deeper TGDs can chain, and the more queries WardedRewrite needs to produce via resolution steps.

However, we can see that the increase in running time is mostly linear as num lrj increases, on average, suggesting that the number of left-right-join recursions does not severely impact the efficiency of our implementation.

Moving to the analysis w.r.t. the parameter avg recursion, we observe steeper trends in Figure 2. The reason is because, assuming we focus on a certain value of the parameter num lrj, at each resolution step, there is a certain chance that a new CQ q′ with two body atoms, both having a recursive predicate, is produced. The number of times this happens is proportional to avg recursion. Hence, the runtime of WardedRewrite increases exponentially w.r.t. avg recursion.

Nonetheless, the above analysis shows that even the most demanding scenarios (e.g., S[400, 400]), which are rather extreme and unlikely to occur in practice, can be solved in the order of some minutes. This is quite encouraging, considering that computing the rewriting is usually done "offline", since this is a database-independent task.

Validation with Other Benchmarks. To place our analysis above in perspective, we also executed our implementation of WardedRewrite on another benchmark of OMQs from the literature that uses warded ontologies from [Atzeni et al., 2022], called structural scenarios. These scenarios were meant to stress test different aspects of a Datalog-based reasoning engine, and we are not aware of other existing benchmarks collecting OMQs whose ontologies are (strictly) warded. Executing WardedRewrite over the OMQs of the structural scenarios revealed that the Datalog rewriting can be constructed very efficiently, with the worst case requiring about 250 ms.

5.2 Impact of the Rewriting on Reasoning

In this section we move to our second experimental question, i.e., how off-the-shelf Datalog-based reasoning engines behave when they evaluate the Datalog query produced by our implementation of WardedRewrite.

Engines. We consider different engines from the literature. In particular, (the parallel version of) Vadalog [Bellomarini et al., 2024],VLog [Urbani et al., 2018], DLV [Adrian et al., 2018] and its extension DLV-E [Leone et al., 2019], as well as InteGraal [Baget et al., 2015]. All the above Datalogbased reasoning engines support the evaluation of standard Datalog queries. They also support OMQ Answering, but to a certain degree. For example, Vadalog supports OMQs over warded ontologies, but only with atomic CQs, using a specialized procedure rather than a Datalog rewriting approach. On the other hand, for example, DLV-E works on OMQs over shy ontologies, uncomparable to warded, and relies on a refined version of the chase, called parsimonious. Nonetheless, all engines above support OMQ Answering when the ontology Σ is such that, for every database D, chase(D,Σ) is finite. Since all our test scenarios turned out to have an ontology with this property, every engine we consider not only is able to evaluate Datalog queries, but it is also able to take directly as input any of our test scenarios S[i, j] = (D,O), with i, j ∈ {0, 20, 40, . . . , 400}, and effectively compute the certain answers ans(O, D).

Answering Question 2. For each Datalog-based reasoning engine E we consider and each pair i, j ∈ {0, 20, 40, . . . , 200}, we asked E to compute the certain answers ans(O,D), and collected the time tcertain required by the engine. Then, we asked E to compute the answers DO(D) of the Datalog rewriting DO of O we previously computed using WardedRewrite in Section 5.1, and collected the time trew required. Note that we only considered the test scenarios with num lrj and avg recursion in the range {0, 20, 40, . . . , 200}, since for higher values most of the engines run out of memory. Moreover, each time an engine was executed, it was given a timeout of 5 minutes.

Then, we measure the efficiency of an engine E over a scenario S[i, j] via the efficiency ratioRE,S[i,j] = trew tcertain . The reason is that our goal is not a comparison of the above engines, but rather asses for each engine, whether the Datalog rewriting produced by our implementation of WardedRewrite can be evaluated efficiently, relative to the capabilities and the limits of the engine itself; RE,S[i,j] < 1 means that it is "relatively" efficient for the engine to evaluate the Datalog query produced by WardedRewrite, while RE,S[i,j] > 1 means it is faster for the engine to evaluate the original OMQ directly.

Figure 3 reports, for each engine E, a violin plot collecting the efficiency ratios RE,S[i,j], for all i, j ∈ {0, 20, 40, . . . , 200}, expressed as a percentage-e.g. 50% corresponds to an efficiency ratio equal to 0.5. In each violin plot, the bottom and the top borders of the inner box denote the first and third quartile; the line inside the box denotes the median efficiency ratio; the area surrounding the box denotes the distribution of all the efficiency ratios.

Regarding DLV, DLV-E, and InteGraal, we can see that most of the efficiency ratios are below 100%, with DLV-E and InteGraal having most of them around 50%. This indicates that the Datalog rewriting produced by our implementation of WardedRewrite can be evaluated efficienty by these systems, and in most cases, the rewriting is even desirable w.r.t. evaluating the original OMQ itself. The main reason for this trend is that all these engines implement certain answering by means of an explicit construction of the chase instance (or a variant of it). This means that when considering the original OMQ O of a test scenario, the presence of existential variables in O forces the engine to introduce a large number of nulls, while constructing the chase, and thus results in a large chase instance. On the other hand, the Datalog rewriting avoids the construction of all such intermediate atoms, reducing the size of the chase instance considerably.

On the opposite side, VLog is not very efficient, in most cases, when evaluating the Datalog rewriting w.r.t. evaluating the original OMQ directly, with almost 75% of the scenarios having an efficiency ratio over 100%, with the worst efficiency ratio around 480%. The reason for this is that, differently from DLV, DLV-E, and InteGraal, VLog is less affected by the size of the chase instance, when evaluating the original OMQ, due to a custom column-based representation of the produced atoms, and thus it does not usually gain much in computing the certain answers via the Datalog rewriting.

Finally, Vadalog is in a middle ground, with roughly 80% of the test scenarios having an efficiency ratio below 50%, while for the remaining 20% of the test scenarios, the Datalog rewriting performs poorly, compared to the original OMQ, with high efficiency ratios up to 830%. This could be due to the fact that for some of the scenarios, when Vadalog evaluates the original OMQ of the scenario, it is able to stop much earlier in the contruction of the chase instance, since it internally constructs only an isomorphim-closed portion of the chase (see [Bellomarini et al., 2018] for more details).

Validation and Scalability Analysis. We employed once again the structural scenarios from [Atzeni et al., 2022] in order to validate our analysis performed above, and indeed the above trends are confirmed also in these scenarios. Moreover, it turned out that for most of the engines, the efficiency ratio even improves (i.e., decreases) as the database size increases.

End-to-end Reasoning. We point out that, besides VLog, for which we have already shown that evaluating the original OMQ is faster than evaluating the Datalog rewriting, in most cases, for all other engines, most of the efficiency ratios (88% on average) that are below 100% remain below 100% even if the time for building the rewriting is taken into account.

6 Conclusion

Our work is a first step in making OMQ Answering under warded ontologies viable in practice, without relying on closed systems, as we have shown that constructing the Datalog rewriting is quite efficient, and most off-the-shelf Datalog-based engines are very capable in evaluating it.

A possible direction for improvement would be parallelizing WardedRewrite by exploiting the fact that all intermediate queries produced by the algorithm can be processed independently from each other, thanks to the optimal decomposition employed by the algorithm.

Ethical Statement

There are no ethical issues.

Acknowledgments

We thank the anonymous referees for their feedback. This work was funded by the European Union - Next Generation EU under the MUR PRIN-PNRR grant P2022KHTX7 "DISTORT", by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT2201, 10.47379/VRG18013, 10.47379/NXT22018], and by the Austrian Science Fund (FWF) 10.55776/COE12. The Vadalog Parallel system as presented here is the intellectual property of Prometheux Limited.