Query Rewriting for DL-Lite with n-ary Concrete Domains

1 Introduction

Ontology-based query answering (OBQA) (see, e.g., [Ortiz, 2013] for an overview) extends query answering in databases in two directions. On the one hand, in OBQA it is not assumed that the available data are complete, and thus facts that are not present are assumed to be unknown rather than false (no closed world assumption [CWA]). On the other hand, an ontology can be used to state background knowledge about the data and to translate between vocabularies (e.g., useroriented versus system-oriented). Nevertheless, if the query and ontology languages are suitably restricted, then OBQA can be reduced to classical query answering in databases.

As the query language, one usually considers (unions of) conjunctive queries ((U)CQs) (i.e., select-project-join queries) in this setting. If the ontology language belongs to the so-called DL-Lite family of Description Logics (DLs) [Calvanese et al., 2007; Artale et al., 2009], then the ontology can often be compiled into the query, which can then be evaluated over the unchanged data using the CWA [Calvanese et al., 2007; 2011]. If this approach is feasible, then one says that the query language is first-order (FO) rewritable w.r.t. the ontology language. FO rewritability implies that OBQA then has the same data complexity as query answering in databases, AC0 . For settings where the data complexity of OBQA is no longer in AC0 (e.g., if the DL EL is used as ontology language), the combined rewriting approach, in which both the query and the data

Marcel Lippmann

TNG Technology Consulting GmbH Unterf¨ohring, Germany marcel.lippmann@tngtech.com

are changed, has turned out to be useful [Lutz et al., 2009; Kontchakov et al., 2011]. In case the data can be rewritten in polynomial time, this yields polynomial data complexity.

Real-world datasets frequently contain concrete data values (such as numbers and strings), and database queries use built-in predicates on these values to formulate restrictions on the tuples to be selected. When adopting concrete data values and built-in predicates for the OBQA setting, it makes sense to employ them not only in the query, but also in the ontology. In ontology languages based on DLs, one then talks about DLs with concrete domains [Baader and Hanschke, 1991; Lutz, 2003]. In addition to concepts and roles (i.e., unary and binary predicates on the abstract domain), such DLs employ attributes (i.e., binary relations between the abstract and the concrete domain) to assign concrete values to individuals, and concrete predicates (corresponding to built-in predicates in databases) to formulate constraints on these values.

Motivated by OBQA applications, several authors have introduced dialects of DL-Lite and CQs with concrete domains [Poggi et al., 2008; Savkovi´c and Calvanese, 2012; Artale et al., 2012]. However, like the standard Web Ontology Language OWL2, 1 these extensions of DL-Lite with concrete domains consider only unary predicates on data values, which can be used to constrain a single value, but cannot require relationships between different values. With unary predicates one can, for example, express that the systolic blood pressure of a patient is >120 and the diastolic blood pressure is >80, but setting the systolic blood pressure into a relationship with the diastolic one requires a binary predicate. In this work, we lift this restriction, i.e., we define an extension of DL-Lite with concrete domains that may have predicates of arbitrary arity, and show that-for concrete domains satisfying certain properties-CQs with built-in predicates from the concrete domain allow for a combined rewriting w.r.t. ontologies formulated in this new language. For example, using an appropriate binary predicate we can then express that the pulse pressure, i.e., the difference between the systolic and the diastolic blood pressure, is 50.

We do not assume that attributes are functional, but our logic can express (local) functionality (e.g., a patient can have only one systolic blood pressure). We also show that concrete domains satisfying our restrictions are closed under disjoint union and product. Using the product of two domains (one for pressure values and one for time), we can compare measurements at different time points; e.g., ask for patients whose systolic blood pressure increased by 20 in 30 seconds.

1 see https://www.w3.org/TR/owl2-overview/

In addition to our combined rewriting approach, we also show that the FO rewritability results for the DL-Lite variant with unary concrete predicates in [Savkovi´c and Calvanese, 2012] follow from our results. Basically, we show that (i) concrete domains with unary predicates satisfying the restrictions in [Savkovi´c and Calvanese, 2012] can be turned into ones satisfying our restrictions, and (ii) in the unary case our combined rewriting boils down to an FO rewriting. The results in [Artale et al., 2012] are orthogonal to ours since they are restricted to the unary case, but allow for more expressiveness on the DL side. In contrast to our work and [Savkovi´c and Calvanese, 2012; Artale et al., 2012], in [Poggi et al., 2008] queries do not contain built-in predicates. Finally, in [Hernich et al., 2017] the authors also consider a setting with non-unary concrete domains, but where the data complexity is CO-NP-hard in general. They then investigate for which kinds of queries this complexity goes down to P. In contrast, our goal is to find restrictions that ensure combined rewritability, and thus polynomial data complexity, for all queries. Detailed proofs of our results can be found in [Baader et al., 2017].

2 Concrete Domains

We first introduce the general notion of concrete domains, and then restrict it such that it fits our purpose. A concrete domain D consists of (i) a non-empty set ∆D of values, (ii) a collection of predicates Πi with associated arities mi containing the special unary predicate ⊤D, and (iii) interpretations ΠDi ⊆ (∆D )mi for all predicates, where (⊤D)D =∆D .

Let NV be a set of variables. A D-formula φ is a Boolean combination of D-atoms Π(v1, . . . , vm), where Π is an m-ary predicate and v1, . . . , vm ∈ ∆D ∪ NV. The set of variables in φ is denoted by Var(φ). A D-conjunction (D-disjunction) is a conjunction (disjunction) of D-atoms. The set solV (φ) of solutions for a D-formula φ, where V ⊇ Var(φ), consists of all variable assignments f : V → ∆D satisfying φ in D (using the standard notion of satisfaction in a relational structure). The D-formula φ is satisfiable if solVar(φ)(φ) ̸= ∅, and it implies the D-formula ψ if solV (φ) ⊆ solV (ψ), where V := Var(φ) ∪Var(ψ).

In the DL literature, concrete domains are usually required to satisfy additional properties that are tailored to the reasoning problems under consideration. For example, in order to obtain decidability of standard DL reasoning problems such as subsumption, Baader and Hanschke [1991] require the concrete domain to be decidable, which in our setting means that satisfiability of D-conjunctions and implications between D-conjunctions must be decidable. In the context of concrete domain extensions of EL, this requirement is tightened by Baader et al. [2005] to decidability in polynomial time. However, to obtain polynomiality of subsumption, one additionally needs to require that the concrete domain is convex, i.e., whenever a D-conjunction implies a (non-empty) D-disjunction, then it should also imply one of its disjuncts. The papers [Savkovi´c and Calvanese, 2012; Artale et al., 2012] among other things require D to be unary, which means that all its predicates must be unary.

Our combined rewritability results depend on the concrete domain D to be cr-admissible, i.e., polynomial, convex, and satisfying the following additional properties:

• D has equality: it contains all unary predicates =d with d ∈ ∆D , which are interpreted as {d}, as well as a binary predicate =, interpreted as {(d, d) | d ∈ ∆D }.
• D is functional: for any m-ary predicate Π, d ∈ ∆D , and i, 1 ≤ i ≤ m, the formula Π(v1, . . . , vm) ∧ =d(vi) has at most one solution.
• D is constructive: for all D-conjunctions φ and D-disjunctions ψ with solV (φ) \ solV (ψ) ̸= ∅, an element of this set can be computed in polynomial time.

The following concrete domains are known to be polynomial and convex [Baader et al., 2005]:

• DQ: The set Q of rational numbers with the unary predicates ⊤DQ , =q, and >q (interpreted as {x | x > q}), and binary predicates = and +q (with the interpretation {(x, y) | x = q + y}), for any q ∈ Q.
• DΣ∗: The set Σ∗ of words over an alphabet Σ with the predicates ⊤DΣ∗ , =w, =, and concw (interpreted as {(x, y) | x = w · y}), for any w ∈ Σ∗ .

Both can also be shown to be functional and constructive, and hence cr-admissible. Moreover, we can show that the class of cr-admissible concrete domains is closed under disjoint union and product of concrete domains, which allows us to construct more complex domains without losing the above properties. For example, the product DQ ×DQ can be used to model measurements that are associated with time stamps.

Unary Concrete Domains. The paper [Savkovi´c and Calvanese, 2012] about query answering in DL-Lite with unary concrete domains D imposes the following restriction. 2

(infinitediff) For any D-conjunction φ and D-disjunction ψ, whenever |solV (φ)| > 1 and solV (φ) ⊈ solV (ψ′ ) for every D-atom ψ′ in ψ (where V := Var(φ) ∪ Var(ψ)), then the cardinality of solV (φ) \ solV (ψ) is infinite.

The original definition actually does not include the condition |solV (φ)| > 1. However, it is easily checked that the constructions and results of [Savkovi´c and Calvanese, 2012] remain valid under our weaker version of (infinitediff). In our setting, this modification is useful to accommodate the predicates =d, whose presence would otherwise contradict (infinitediff). To show that our results apply to the setting from [Savkovi´c and Calvanese, 2012], first note that one can add equality predicates to D without destroying (infinitediff).

Lemma 2.1. For any unary concrete domainD satisfying (infinitediff), the concrete domain D′ obtained from D by adding the predicates = and =d (d ∈ ∆D ) still satisfies (infinitediff).

Surprisingly, in our setting (infinitediff) and convexity are equivalent, though they have been introduced for different purposes in [Savkovi´c and Calvanese, 2012] and [Baader et al., 2005], respectively. In general, convexity is a weaker restriction since it does not force non-singleton predicates to be infinite. But in the presence of the predicates =d we can show equivalence. In fact, if solV (φ) \ solV (ψ) is finite, then one can use the predicates =d to construct a counterexample to convexity. In contrast to the previous lemma, this result is not restricted to unary concrete domains.

2 The other restrictions in that paper, (infinite) and (opendomain), are simply special cases with ψ = false and φ = true, respectively.

Lemma 2.2. A concrete domain D containing the predicates =d (d ∈ ∆D ) is convex iff it satisfies (infinitediff).

As a further step towards showing that our results imply the ones in [Savkovi´c and Calvanese, 2012], observe that every unary concrete domain D is trivially functional. We will argue in Section 6 that, for unary concrete domains D, we (i) need decidability only for unary predicates (not for =), and (ii) do not need polynomiality or constructivity of D. In contrast, in the presence of predicates of higher arity, the predicates =d, functionality, and constructivity are essential for our combined rewriting approach (see Section 6).

Convexity is necessary for our rewritability results both in the general and in the unary case. In fact, these results imply polynomial data complexity. If the concrete domain is not convex, then answering conjunctive queries that can refer to concrete domain predicates is CO-NP-hard in the data complexity (and hence neither FO nor combined rewritable, unless P=NP), even in the unary case [Savkovi´c, 2011; Savkovi´c and Calvanese, 2012; Artale et al., 2012].

3 The Ontology Language

For any cr-admissible concrete domain D, we introduce the logic DL-Lite(HF) core (D), a common extension of DL-Lite(HF) core and DL-LiteA [Artale et al., 2009; Poggi et al., 2008].

Syntax. Let NC, NR, NA, and NI denote disjoint sets of concept, role, attribute, and individual names. Roles R and concepts B are defined as

where P ∈ NR, A ∈ NC, U1, . . . ,Um ∈ NA, and Π is an m-ary predicate of D. A TBox (or ontology) is a finite set of inclusions X1 ⊑ X2, disjointness constraints disj(X1,X2), functionality constraints funct(R), and attribute range constraints B ⊑ ∀U1, . . . , Um.Π where X1 and X2 are both either concepts, roles, or attribute names. As usual, role names occurring in functionality constraints are not allowed to occur on the right-hand side of inclusions [Artale et al., 2009]. In contrast to DL-Lite(HF) core , we do not explicitly have role (a)symmetry or (ir)reflexivity axioms here; they can, however, be simulated as described in [Artale et al., 2009].

An ABox is a finite set of concept assertions A(a), role assertions P(a, b), and attribute assertions U(a, d), where a, b ∈ NI and d ∈ ∆D . A knowledge base (KB) K := 〈A, T 〉 consists of a TBox T and an ABox A that uses only the concept, role, and attribute names occurring in T .

Semantics. The semantics is the standard one [Poggi et al., 2008], based on interpretations (∆I , ·I ) that assign distinct elements aI ∈ ∆I to all individual names, sets C I ⊆ ∆I to concepts, binary relations on ∆I to roles, and relations U I ⊆ ∆I × ∆D to attribute names. For example, the interpretation of an attribute restriction ∃U1,U2.Π is a set that contains all e ∈ ∆I for which there are d1, d2 ∈ ∆D with (d1, d2) ∈ ΠD , (e, d1) ∈ U I 1 , and (e, d2) ∈ U I 2 . The semantics of axioms is also standard; e.g., an interpretation satisfies a disjointness constraint disj(X1,X2) if XI 1 ∩XI 2 = ∅. The models of a KB K are those interpretations satisfying all its axioms, and K is consistent if it has a model.

Other DL-Lite Logics. Our logic extends those from [Poggi et al., 2008; Savkovi´c and Calvanese, 2012]. In fact, the missing functionality restrictions on attributes can be expressed using attribute range constraints for binary equality. On top of that, we even allow functional attributes to occur on the righthand sides of inclusions. In contrast to [Artale et al., 2012], we do not support number restriction on roles or attributes. But we can at least simulate conjunctions in inclusions via the concrete domain. For example, B1 ⊓B2 ⊑ B3 can be expressed by B1 ⊑ ∃U1.=d, ⊤ ⊑ ∃U2.⊤D, B2 ⊑ ∀U1, U2.=, and ∃U2.=d ⊑ B3, where U1, U2 are fresh attribute names, and d is a fresh constant.

says that the maximum heart rate for persons aged 60 is 160, and that for any person an alert should be raised when the measured heart rate rises to only 5 below the maximum heart rate. A corresponding ABox contains actual data such as

which implies the assertion Alert(p1), but not Alert(p2).

This example illustrates a prominent advantage of attribute restrictions using predicates of arity greater than 1. Here, they allow us to express an alert by comparing the current measurement with a maximum value. Using unary predicates, one could express hard-coded limits like ∃hr.>180 ⊑ Alert, but not comparisons with an (age-dependent) maximum rate, unless one writes a huge (finite) case distinction.

As in OWL 2 QL, but in contrast to many DL-Lite dialects, we allow qualified attribute restrictions on the left-hand side of inclusions. This is possible without causing undecidability (as in [Baader and Hanschke, 1991; Lutz, 2002]) since they only refer to values for a single abstract domain element.

4 Conjunctive Queries with Built-ins

Let NV be a set of variables, partitioned into object variables NOV and concrete domain variables NCV. A conjunctive query (CQ) φ is of the form (⃗x,⃗v) ← ψ(⃗y, ⃗w), where ⃗x, ⃗y are vectors over NOV, ⃗v, ⃗w are vectors over NCV, the variables ⃗x, ⃗v are included in ⃗y, ⃗w, and ψ(⃗y, ⃗w) is a conjunction of atoms of the forms A(x) (concept atom), R(x, y) (role atom), U(x, v) (attribute atom), x = y (object equality atom), or Π(v1, . . . , vm) (value comparison atom). In addition to variables, atoms may also contain constants from NI and ∆D at appropriate places. The variables in ⃗x, ⃗v are the distinguished variables of φ; all others are nondistinguished. A CQ is called Boolean if ⃗x and ⃗v are empty. We write α ∈ φ to denote that

α is an atom occurring in the CQ φ. The set terms(φ) consists of the elements of NI, ∆D , and NV occurring in φ.

An interpretation I satisfies a Boolean CQ φ (I |= φ) if there is a homomorphism of φ into I, i.e., a function π : terms(φ) → ∆I ∪∆D that maps object variables into ∆I and concrete domain variables into ∆D , preserves the interpretations of individual names and concrete values, and satisfies all atoms of φ w.r.t. ·I and ·D . A KB K entails φ (K |= φ) if every model of K also satisfies φ. A potential answer a to a CQ φ: (⃗x, ⃗v) ← ψ(⃗y, ⃗w) w.r.t. K maps ⃗x to individual names from K and ⃗v to ∆D . A certain answer to φ w.r.t. K is a tuple of the form a(⃗x,⃗v), where a is a potential answer for which K entails a(φ) : () ← ψ(a(⃗y, ⃗w)). The set of certain answers to φ w.r.t. K is denoted by cert(φ, K). Similarly, for an interpretation I, the set ans(φ, I) contains all tuples a(⃗x, ⃗v) where a is a potential answer to φ w.r.t. K such that I |= a(φ).

Rewritability. A CQ φ is FO rewritable (or, equivalently, UCQ rewritable; see [Bienvenu et al., 2013]) w.r.t. a TBox T if there is a finite set ΦT of CQs such that for every consistent KB K = 〈A, T 〉 we have

where I(A) is the finite interpretation that satisfies exactly the assertions in A. One can view I(A) as a (closed-world) database over which the union of the CQs in ΦT (called a rewriting of φ w.r.t. T ) is evaluated. The CQ φ is combined rewritable w.r.t. T if the above property holds with I(K) instead of I(A), where I(K) is a finite interpretation that is constructed from A and T in polynomial time. Since database queries can be evaluated in AC0 [Abiteboul et al., 1995], FO rewritability yields a data complexity in AC0 , and combined rewritability raises this to P.

Safety. We follow the approach used in databases and assume that concrete domain predicates are built-in predicates of the database system, i.e., their full (possibly infinite) extensions are known [Klug, 1988; Brisaboa et al., 1998; Afrati et al., 2006; Savkovi´c and Calvanese, 2012]. Although this means that the interpretation I(K) is not finite anymore, i.e., not a database, for so-called domain-independent queries it suffices to check satisfiability of D-conjunctions, which is usually implemented by using a dedicated solver, e.g., for integer arithmetic. Domain-independence requires that the answers should not depend on the chosen domain ∆D of available values, but only on the values used in K [Abiteboul et al., 1995]. To ensure this condition in our setting, we restrict ourselves to safe queries, as in [Savkovi´c and Calvanese, 2012; Afrati et al., 2006]. A concrete domain variable v in a CQ φ is safe if it occurs in φ in an atom of the form

1. U(x, v) for some U ∈ NA and object variable x, or
2. =d(v) for some d ∈ ∆D .

The CQ φ is safe if all its concrete domain variables are safe. A variable v that occurs in an atom U(x, v) in φ is bound to x (in φ). Condition b) is not essential for our results, since such variables can be replaced by constants, but it is more convenient for formulating the rewriting in Section 6. Apart from ensuring domain-independence, we can show that safety is a necessary condition for combined rewritability (unless P=NP). In fact, inDL-Lite(HF) core (D{a}∗), non-safeCQs can express that an attribute value starts with letter a. Together with =ε, one can thus simulate truth values by using "empty word" versus "non-empty word", which can then be employed to express the satisfaction of propositional formulas.

Lemma 4.1. In DL-Lite(HF) core (D{a}∗), entailment of (nonsafe) Boolean CQs is CO-NP-hard in data complexity.

5 Canonical Models

Usually, rewritability results are proved using the notion of canonical models of knowledge bases. Given a KB K, a canonical model IK is a model of K with the property that ans(φ, IK) = cert(φ, K) holds for all CQs φ. Unfortunately, such canonical models need not exist, even for unary D.

Example 5.1. Consider the simple DL-Lite(HF) core (DQ) KB K = 〈{A(a)}, {A ⊑ ∃U.>0}〉. A canonical model IK of K must satisfy (aIK, q) ∈ U IK for some q > 0. But then the safe Boolean CQ φq : () ← ∃v.U(a, v) ∧ >q/2 (v) is satisfied in IK, but not entailed by K.

Savkovi´c and Calvanese [2012] try to solve this problem by selecting the "most general" q that does not satisfy any D-atoms except those implied by >0(q). They choose q > 0 such that "for any m predicates Π1, . . . , Πm in DQ such that ( ⋃mi=1 ΠDQ i ) ⊊ (>0)DQ it holds that q /∈ (⋃mi=1 ΠDQ i )" [Savkovi´c and Calvanese, 2012, page 725]. For a given choice of Π1, . . . ,Πm, such a value q must exist due to (infinitediff). However, regardless of the value of q, the CQ φq remains a counterexample. Hence, this construction is incorrect already for the unary predicates >q, q ∈ Q, contrary to the claim in [Savkovi´c and Calvanese, 2012, Example 2].

To overcome this problem, we weaken the requirements on the canonical model by considering only those CQs that use concrete domain predicates from a fixed, finite set of predicates. This solves the issue in Example 5.1 since there are infinitely many predicates >q/2 , q ∈ Q, and thus not all CQs φq satisfy this restriction. For ease of presentation, we assume in the following that all CQs use only the concrete domain predicates from T . We call such CQs T -restricted. Similarly, we can assume as usual that all other symbols occurring in φ also occur in T . This does not affect the complexity of query answering, but in practice restricts the kind of queries a user can ask over a given KB, which is usually fixed in advance.

Abstract Interpretations. Here we cannot describe our construction in detail, but only explain the general ideas. First, we build an abstract canonical model IK of the KB K, where attributes may use variables as place-holders for actual values, and sets of D-atoms are used to constrain the possible solutions for these variables. This is constructed using chase rules extending the ones in [Calvanese et al., 2007], and is very similar to the universal pre-models in [Hernich et al., 2017]. In this process, the attribute restrictions from the TBox are translated into D-atoms over the variables occurring in IK. For example, if in IK it already holds that (e, v1) ∈ U IK and (e, v2) ∈ V IK, and ⊤ ⊑ ∀U, V.Π occurs in K, then we add the constraint Π(v1, v2) to IK. We denote by I ∗A the initial part of this model, which is constructed by applying the chase rules only to the individual names fromA.

In the next step, we construct a canonical solution fK for all variables in IK, i.e., one that satisfies all constraints, but does not unnecessarily satisfy any of the "relevant" D-atoms (defined similarly to RT ∪ RT ,2 in the next section). As in [Savkovi´c and Calvanese, 2012; Artale et al., 2012], the convexity of D is crucial for this construction, but we also need functionality here (see [Baader et al., 2017] for details). In our combined rewriting approach, the finite interpretation fK(I ∗A), which is obtained from the abstract interpretation I ∗A by replacing all variables by their value under fK, plays the role of I(K) in the definition of combined rewritability.

6 Rewriting CQs with Built-in Predicates

To obtain our rewriting, we extend the approach of [Calvanese et al., 2007; Poggi, 2006; Savkovi´c and Calvanese, 2012]. The idea is to construct the rewriting ΦT of the initial CQ φ w.r.t. the TBox T by iterative application of several operators (called reduce, split, inferT , and inferD). Variants of the two basic operators reduce and inferT have first been used in [Calvanese et al., 2007; Poggi, 2006]. The former tries to unify atoms in CQs, while the latter applies the TBox inclusions as rewrite rules. Intuitively, A ⊑ B ∈ T means that any certain answer to A(x) is also a certain answer to B(x), and hence A(x) is included in the rewriting of B(x). We extend inferT to deal with attribute range restrictions, which behave similarly. A special case of this extension can be found in [Savkovi´c and Calvanese, 2012].

Two new operators deal with concrete domain predicates of higher arity. The operator split can "split" two occurrences of a concrete domain variable into separate variables, as long as they are restricted to the same value by a predicate =d; this is needed for technical reasons (see [Baader et al., 2017]). The operator inferD behaves like inferT , but takes care of implications in the concrete domain instead of the abstract domain.

The Basic Operators. ΦT is the result of iteratively applying

to the initial set {φ}, until we reach a fixed-point. We define

where subst(φ′ ) contains all substitutions of variables by terms from φ′ . The set split(Φ) contains all CQs obtained from any φ′ ∈ Φ with =d(v) ∈ φ′ by replacing one other occurrence of v with a fresh variable v′ and adding the atom =d(v′ ). Before we introduce the infer operators, we want to illustrate them on an example.

Example 6.1. Consider the KB K = 〈A, T 〉 from Example 3.1 and the CQ φ: (x) ← Alert(x) that asks for all patients with alerts. The only certain answer to φ w.r.t. K is p1. To obtain this answer without referring to the TBox T , we have to apply several rewriting steps.

First, inferT applies the inclusion ∃maxHR, hr.+5 ⊑ Alert by replacing Alert(x) by the left-hand side of the axiom:

Note that the existential quantifiers in the inclusion are made explicit by introducing fresh nondistinguished variables v, w.

In DQ, it holds that =160(v) ∧ =155(w) implies +5(v, w). Hence, inferD replaces +5(v,w) by the former two atoms:

This step introduces the predicate =155, which is not present in φ or T . To avoid an infinite rewriting, we obviously have to restrict the implications that can be applied in this way.

Since the maximum heart rate is 160 for all patients that are 60 years old, we can again apply inferT to obtain

Evaluating this query over A yields the expected answer p1. Based on this intuition, we define the operator

inferT (Φ) := {σ(φ′′ ) | φ′ ∈ Φ, φ′ →T φ′′ , σ ∈ subst(φ′′ )}, where the relation φ′ →T φ′′ holds for two safe CQs φ′ , φ′′ if one of the following cases applies:

• There exist an atom X2(⃗x) in φ′ and X1 ⊑ X2 in T such that φ′′ is obtained by replacing X2(⃗x) with X1(⃗x). Here, (∃R)(x) stands for R(x, y), where y is a nondistinguished unique variable, and (∃U1, . . . ,Um.Π)(x) abbreviates the set of atoms {U1(x, v1), . . . , Um(x, vm), Π(v1, . . . , vm)}, where v1, . . . , vm are unique nondistinguished variables. We also allow that X2(⃗x) comprises only a subset of these atoms, as long as it includes at least one attribute atom.
• There exist Π(v1, . . . , vm) in φ′ and B ⊑ ∀U1, . . . , Um.Π in T such that φ′′ is obtained by replacing Π(v1, . . . , vm) with the atoms B(x), U1(x, v1), . . . , Um(x, vm), where x is an object variable of φ′ .

As in previous rewriting algorithms, this operator does not introduce new object variables (except if they occur only once). Concrete Domain Implications. The operator inferD is based on a similar relation →D on safe CQs. A first naive idea would be to define φ′ →D φ′′ as follows:

• There is an atom Π(v1, . . . , vm) in φ′ that is implied by a D-conjunction ψ such that φ′′ is obtained by replacing Π(v1, . . . , vm) by ψ and adding atoms U(x, v) for the fresh variables v in ψ (where U occurs in T and x occurs in φ′ ).

The new attribute atoms ensure safety of the resulting CQ. However, without further restrictions, this operation may yield an unbounded number of new atoms and variables, and hence an "infinite FO rewriting". To avoid this, we introduce a bound on the number of concrete domain variables occurring in CQs: we only allow nT concrete domain variables bound to each object variable x, where nT is the number of occurrences of attribute names on the right-hand side of inclusions in T . This is becuase only such inclusions can cause new values to be created in the canonical model, and hence nT is the maximal number of values relevant for reasoning about the concrete values of a fixed domain element. We further restrict the CQs to the set RT of concrete domain predicates occurring in T , and hence call a CQ bounded if all its value comparison atoms are of the form

• (B1) Π(v1, . . . , vm), where Π ∈ RT and the variables among v1, . . . , vm are bound to at most one object variable x. In the set of all such atoms Π(v1, . . . , vm), there may occur only nT concrete domain variables bound to the same x.

We amend the definitions of inferT and inferD by allowing only bounded CQs (e.g., new atoms U(x, v) do not bind v to two different variables). Note that this restriction may be temporarily violated, as long as it can be restored by an immediate application of a substitution (see the definition of inferT ).

Unfortunately, this is still not enough to obtain the desired rewriting. The reason is that the initial CQ φ itself need not satisfy (B1). In particular, it may contain value comparison atoms whose variables are bound to different object variables. However, due to the functionality of D, such atoms can only be implied by the TBox if all of their variables already satisfy atoms of the form=d(v). It remains to find a finite set of values d that are relevant in these situations. It turns out that it suffices to consider such values d that are implied by some set of atoms of the form (B1). More precisely, we collect in RT ,1 all predicates =d for which =d(v) is implied by a conjunction ψ using only predicates from RT and at most nT variables. Since D is polynomial and constructive, we can, for all such (finitely many) conjunctions ψ, compute a solution for each of their variables v, and check whether this is the only possible solution for v. We obtain RT ,2 by a similar construction, but now allowing all predicates in RT ∪RT ,1 to occur in the conjunctions ψ (see [Baader et al., 2017] for details). We now relax the definition of boundedness by allowing also the following kinds of value comparison atoms:

• (B2) Atoms from φ, possibly after applying reduce or split.
• (B3) Atoms of the form =d(v), where =d ∈ RT ,2.

In →D , we now allow atoms of the form (B2) to be rewritten into atoms satisfying either (B1) or (B3) (possibly after applying a substitution). Atoms of the form (B3) cannot be rewritten further. This concludes the description of ΦT .

Correctness. We can show that, if the CQ φ is safe, then every CQ in ΦT is safe and bounded, from which we obtain that ΦT is finite. Moreover, this rewriting is correct in the sense that, for any consistent KB K = 〈A, T 〉, we have

where I ∗A is the finite abstract interpretation that can be constructed fromA and T in polynomial time (see Section 5).

In order to obtain an actual combined rewriting, the last step is to replace the abstract interpretation I ∗A by an ordinary finite interpretation, i.e., a database. We use the canonical solution fK described in Section 5 to obtain the desired finite interpretation by instantiating all variables in I ∗A. To construct this solution, we need to solve polynomial-sized Dconjunctions over the predicates in RT ∪ RT ,2 (plus some others) and the constants in A, which is possible in polynomial time since D is polynomial and constructive. Using the resulting finite interpretation fK(I ∗A) as I(K), we can show that ΦT satisfies the definition of combined rewritability.

Theorem 6.2. If D is cr-admissible, safe and T -restricted CQs are combined rewritable w.r.t. DL-Lite(HF) core (D) TBoxes T , and the rewritings are computable.

This shows that the entailment problem for safe Boolean CQs in DL-Lite(HF) core (D) is in P in data complexity. From a practical point of view, this result allows us to combine an offline (polynomial) computation of the database fK(I ∗A) with an on-line rewriting of incoming queries.

So far, we have ignored the side condition that K should be consistent, since query answering over an inconsistent KB is meaningless. As usual, KB consistency can be checked by an off-line test (see [Baader et al., 2017]).

Unary Concrete Domains. We again consider the special case of a unary, decidable concrete domain D satisfying (infinitediff), as in [Savkovi´c and Calvanese, 2012]. Recall from Section 2 that adding the equality predicates does not affect (infinitediff). Since neither T nor φ contain =, for →D it suffices to decide implications that do not contain this predicate; moreover, the unary predicates =d do not affect decidability. Furthermore, (infinitediff) implies convexity, and D is trivially functional. The two remaining properties of cr-admissibility, polynomiality and constructivity, are only needed to construct RT ,2 and the canonical solution fK. In [Baader et al., 2017], we define a weaker notion of boundedness without RT ,2 that suffices for unary concrete domains, and show that one can directly use I(A) instead of fK(I ∗A).

Theorem 6.3. If D is unary, decidable, and satisfies (infinitediff), then safe and T -restricted CQs are FO rewritable w.r.t. DL-Lite(HF) core (D) TBoxes T , and the rewritings are computable.

This extends the results of [Savkovi´c and Calvanese, 2012] to a more expressive ontology language, and adds the missing condition of T -restrictedness.

7 Conclusion

Our combined rewritability result for CQs with built-in predicates over DL-Lite(HF) core (D) ontologies establishes for the first time a polynomial data complexity for query answering w.r.t. ontologies formulated in an ontology language with n-ary concrete domains. These results subsume the ones of [Savkovi´c and Calvanese, 2012] for the case of unary concrete domains, and they are orthogonal to the results in [Hernich et al., 2017]. In the latter work, the data complexity is in general CO-NP, and the authors investigate for which queries this goes down to P. Until now, our focus was on showing rewritability and complexity results. To be useful in practice, the size of the rewriting needs to be reduced, e.g., by investigating whether more concise rewritings [Kontchakov et al., 2010] or alternative target languages [Rosati and Almatelli, 2010] can be employed in our setting. Instead of considering all possible implications in the concrete domain, it may also be possible to realize the operator inferD by a dedicated solving engine for the concrete domain. In addition to considering minor extensions, like allowing for concrete domain variables and predicates in the ABox as in [Lutz, 2002], we will also try to extend the language by local identification constraints (keys) [Calvanese et al., 2008] and functional roles on the right-hand side of inclusions, and investigate whether FO rewritability holds in the general case.

Acknowledgments

This work was supported by DFG in the CRC 912 (HAEC) and the project BA 1122/19-1 (GoAsQ).