Introduction

Ontology-based data access (OBDA) is an increasingly popular approach for enabling uniform access to multiple data sources with diverging schemas [5,15,22]. In OBDA, an ontology provides a unifying conceptual model for the data sources, which is linked to each source by mappings assigning views over the data to ontology predicates. Users access the data by means of queries formulated using the vocabulary of the ontology; query answering amounts to computing the certain answers to the query over the union of ontology and the materialisation of the views defined by the mappings. The formalism of choice for representing ontologies in OBDA is usually the lightweight description logic DL-Lite R [6], which underpins OWL 2 QL [19]. DL-Lite R was designed to ensure that conjunctive queries (CQs) against the ontology are first-order rewritable-that is, they can be reformulated as relational database queries over the sources [6].

There is, however, an important mismatch between standard database query languages, such as SQL, and OBDA: the former work under bag semantics, but the latter is usually set-based. This becomes apparent when evaluating queries with aggregate functions, where the multiplicities of tuples are important [1]. Motivated by the need to support database-style aggregate queries in OBDA systems and inspired by the semantics of aggregates over DL-Lite R of [14], a bag version of DL-Lite R was recently proposed by Nikolaou et al. [20,21], where duplicates in the views defined by the mappings are retained. The most common reasoning tasks of ontology satisfiability and query answering in this new DL, called DL-Lite b R , generalise the counterpart problems defined under the traditional set semantics. This generalisation does not come for free though as it raises the data complexity of query answering from AC 0 to coNP-hard, and this holds already for the core fragment DL-Lite b core of DL-Lite b R . To regain tractability, Nikolaou et al. [20,21] studied restrictions on CQs and showed that query answering for the class of so-called rooted CQs [4] becomes again tractable in data complexity. This result was obtained by showing that rooted CQs are rewritable to BCALC, a logical counterpart of the relational algebra for bags BALG 1 [10,17], whose evaluation problem is in TC 0 in data complexity [16].

Building on the work of Nikolaou et al. [20,21], in this paper we consider the logic DL-Lite b F -that is, the extension of DL-Lite b core with functionality axioms. Such axioms comprise a desirable feature in description logics and OBDA since they are able to deliver various modelling scenarios encountered in information systems that require the expression of key and identification constraints [7,8,18,23]. We propose two alternative semantics for DL-Lite b F , both of which generalise the standard set-based semantics, and which differ from each other in the way they handle functionality axioms. Our first semantics, called SQL semantics, interprets functionality axioms following the semantics of primary keys in SQL; in particular, for each first component in the interpretation of a functional role there exists exactly one second component, and, moreover, the multiplicity of this relation between the components is exactly one. By contrast, our second semantics, called multiplicity-respectful (MR) semantics, enforces only the first requirement, while the multiplicity may be arbitrary.

We study how the two semantics relate to the set-based semantics of DL-Lite F and to each other in terms of the standard reasoning tasks of satisfiability checking and query answering. On the one hand, we show that under the MR semantics both problems generalise the corresponding ones under set semantics. Under the SQL semantics, on the other hand, the notion of satisfiability becomes stronger than under set semantics, while query answering for satisfiable ontologies again generalises set semantics. We further investigate whether the class of rooted CQs is rewritable to BCALC under our two semantics. For the SQL semantics, we obtain positive results, which imply that query answering is feasible in TC 0 . For the MR semantics, however, we obtain negative results (LogSpace-hardness in data complexity) even for the class of instance queries, which are the simplest queries encountered in OBDA. To address this, we identify a class of TBoxes, called functionally weakly acyclic, for which rooted CQs become rewritable to BCALC, and thus query answering is feasible in TC 0 . The rest of the paper is organised as follows. Section 2 introduces the relevant background. Section 3 defines the SQL and MR semantics as extensions of the bag semantics proposed in [20,21] accounting for functionality axioms, and relates the new semantics to the set semantics and to each other. Section 4 then studies the query answering problem for the bag semantics, establishing the rewritability results. Last, Section 5 concludes the paper. Acknowledgements Research supported by the SIRIUS Centre for Scalable Data Access and the EPSRC projects DBOnto, MaSI 3 , and ED 3 .

Preliminaries

We start by defining DL-Lite F ontologies as well as the notions of query answering and rewriting over such ontologies, all over the usual set semantics [2,6], after which we summarise the bag semantics of queries in databases [10,17,21]. Syntax of DL-Lite F . We fix a vocabulary consisting of countably infinite and pairwise disjoint sets of individuals I (i.e., constants), atomic concepts C (i.e., unary predicates) and atomic roles R (i.e., binary predicates). A role is an atomic role P ∈ R or its inverse P − . A concept is an atomic concept in C or an expression ∃R with R a role. Expressions C 1 C 2 and Disj(C 1 , C 2 ) with C 1 , C 2 concepts are inclusion and disjointness axioms, respectively. An expression (funct R) with R a role is a functionality axiom. A DL-Lite F TBox is a finite set of inclusion, disjointness, and functionality axioms. A concept assertion is A(a) with a ∈ I and A ∈ C, and a role assertion is P (a, b) with a, b ∈ I and P ∈ R. A (set) ABox is a finite set of concept and role assertions. A DL-Lite F ontology is a pair (T , A) with T a DL-Lite F TBox and A an ABox. A DL-Lite core ontology is the same except that functionality axioms are disallowed. Semantics of DL-Lite F . A (set) interpretation I is a pair (∆ I , • I ), where the domain ∆ I is a non-empty set, and the interpretation function • I maps each a ∈ I to a I ∈ ∆ I such that a I = b I for all a, b ∈ I (i.e., as usual for DL-Lite we adopt the UNA-that is, the unique name assumption), each A ∈ C to A I ⊆ ∆ I , and each P ∈ R to P I ⊆ ∆ I × ∆ I . Interpretation function • I extends to non-atomic concepts and roles as follows:

(P − ) I = {(u, u ) | (u , u) ∈ P I }, (∃R) I = {u ∈ ∆ I | ∃u ∈ ∆ I : (u, u ) ∈ R I }. An interpretation I satisfies a DL-Lite F TBox T if C I 1 ⊆ C I 2 for each inclusion axiom C 1 C 2 in T , C I 1 ∩C I 2 = ∅ for each Disj(C 1 , C 2 )

in T , and v 1 = v 2 for each (u, v 1 ), (u, v 2 ) in R I with (funct R) in T . Interpretation I satisfies an ABox A if a I ∈ A I for all A(a) ∈ A and (a I , b I ) ∈ P I for all P (a, b) ∈ A. An interpretation I is a model of an ontology (T , A) if it satisfies T and A. An ontology is satisfiable if it has a model. Checking satisfiability of a DL-Lite F ontology is NLogSpacecomplete in general and in AC 0 if the TBox is fixed [2,6]. Queries over DL-Lite F . A conjunctive query (CQ) q(x) with answer variables x is a formula ∃y. φ(x, y), where x, y are (possibly empty) repetition-free tuples of variables from a set X disjoint from I, C and R, and φ(x, y) is a conjunction of atoms of the form A(t), P (t 1 , t 2 ) or (z = t), where A ∈ C, P ∈ R, z ∈ x ∪ y, and t, t 1 , t 2 ∈ x ∪ y ∪ I. If x is inessential, then we write q instead of q(x). The equality atoms (z = t) in φ(x, y) yield an equivalence relation ∼ on terms x ∪ y ∪ I, and we write t for the equivalence class of a term t. The Gaifman graph of q(x) has a node t for each t ∈ x ∪ y ∪ I in φ, and an edge { t1 , t2 } for each atom in φ over t 1 and t 2 . We assume that all CQs are safe-that is, for each z ∈ x ∪ y, z contains a term mentioned in an atom of φ(x, y) that is not equality. A CQ q(x) is rooted if each connected component of its Gaifman graph has a node with a term in x ∪ I [4]. A union of CQs (UCQ) is a disjunction of CQs with the same answer variables. The certain answers q K to a (U)CQ q(x) over a DL-Lite F ontology K are the set of all tuples a of individuals such that q(a) holds in every model of K. Checking whether a tuple of individuals is in the certain answers to a (U)CQ over a DL-Lite F ontology is an NP-complete problem with AC 0 data complexity (i.e., when the CQ and TBox are fixed) [2,6]. The latter follows from the rewritability of the class of UCQs to itself over DL-Lite F -that is, from the fact that for every UCQ q and DL-Lite F TBox T we can find a UCQ q 1 such that q (T ,A) = q

(∅,A) 1 for every ABox A [6]. Bags. A bag over a set M is a function Ω : M → N ∞ 0 ,

where N ∞ 0 is the set N 0 of non-negative integers extended with the (positive) infinity ∞. The value Ω(c) is the multiplicity of element c in Ω. A bag Ω is finite if there are finitely many c ∈ M with Ω(c) > 0 and there is no

c with Ω(c) = ∞. The empty bag ∅ over M is the bag such that ∅(c) = 0 for each c ∈ M . A bag Ω 1 over M is a subbag of a bag Ω 2 over M , in symbols Ω 1 ⊆ Ω 2 , if Ω 1 (c) ≤ Ω 2 (c) for each c ∈ M .

Often we will use an alternative syntax for bags: for instance, we will write {| c : 5, d : 3 |} for the bag that assigns 5 to c, 3 to d, and 0 to all other elements. We use the following common operators on bags [10,17]: the intersection ∩, maximal union ∪, arithmetic union , and difference − are the binary operators defined, for bags Ω 1 and Ω 2 over a set M , and for every c ∈ M , as

(Ω 1 ∩ Ω 2 )(c) = min{Ω 1 (c), Ω 2 (c)}, (Ω 1 ∪ Ω 2 )(c) = max{Ω 1 (c), Ω 2 (c)}, (Ω 1 Ω 2 )(c) = Ω 1 (c) + Ω 2 (c), (Ω 1 − Ω 2 )(c) = max{0, Ω 1 (c) − Ω 2 (c)}.

Note that bag difference is well-defined only if Ω 2 (c) is a finite number for each c ∈ M . The unary duplicate elimination operator ε is defined for a bag Ω over M and for each c ∈ M as (ε(Ω))(c) = 1 if Ω(c) > 0 and (ε(Ω))(c) = 0 otherwise. Queries over Bags. Following [21], a BCALC query Φ(x) with (a tuple of) answer variables x is any of the following, for Ψ , Ψ 1 , and Ψ 2 BCALC queries: -S(t), where S ∈ C ∪ R and t is a tuple over x ∪ I mentioning all x; -Ψ 1 (x 1 ) ∧ Ψ 2 (x 2 ), where x = x 1 ∪ x 2 ; -Ψ (x 0 ) ∧ (x = t), where x ∈ x 0 , t ∈ X ∪ I, and x = x 0 ∪ ({t} \ I); -∃y. Ψ (x, y), where y is a tuple of distinct variables from X that are not in x;

-Ψ 1 (x) op Ψ 2 (x)

, where op ∈ {∨, ∨ . , \}; or δ Ψ (x).

In particular, all UCQs are syntactically BCALC queries. BCALC queries are evaluated over bag database instances, which are, in the context of this paper, bag ABoxes-that is, finite bags over the set of concept and role assertions. The bag answers Φ A to a BCALC query Φ(x) over a bag ABox A is the finite bag over I |x| defined inductively by the following equations, for every tuple a over I with |a| = |x|, where ν : x ∪ I → I is the function such that ν(x) = a and ν(a) = a for all a ∈ I:

-Φ A (a) = A(S(ν(t))), if Φ(x) = S(t); -Φ A (a) = Ψ A 1 (ν(x 1 )) × Ψ A 2 (ν(x 2 )), if Φ(x) = Ψ 1 (x 1 ) ∧ Ψ 2 (x 2 ); -Φ A (a) = Ψ A (ν(x 0 )), if Φ(x) = Ψ (x 0 ) ∧ (x = t) and ν(x) = ν(t); -Φ A (a) = 0, if Φ(x) = Ψ (x 0 ) ∧ (x = t) and ν(x) = ν(t); -Φ A (a) = ν : y→I Ψ A (a, ν (y)), if Φ(x) = ∃y. Ψ (x, y); -Φ A (a) = (Ψ A 1 op Ψ A 2 )(a), if Φ(x) = Ψ 1 (x) op Ψ 2 (x)

, where op is ∪, , or −, and op is ∨, ∨ . , or \, respectively; -

Φ A (a) = ε(Ψ A ) (a), if Φ(x) = δ Ψ (x).

As shown in [21], BCALC is a logical counterpart of the bag relational algebra BALG 1 of [10], with the same expressive power. Evaluation of a fixed BALG 1 (and hence BCALC) query is in TC 0 [16] (i.e., between AC 0 and LogSpace).

DL-Lite F under Bag Semantics

In this section we introduce the bag version DL-Lite b F of the ontology language DL-Lite F with two semantics and study their properties and relationships. Both semantics extend the bag semantics of DL-Lite b core studied in [21] but differ in their interpretation of functionality axioms. F ontologies is based on bag interpretations, which are the same as set interpretations except that concepts and roles are interpreted as bags rather than sets. Note that the extension of the interpretation function to non-atomic concepts and roles is defined in a way that respects the multiplicities: for example, the concept ∃P for an atomic role P is interpreted by a bag interpretation I as the bag projection of P I to its first component, where each occurrence of a pair (u, v) in P I contributes separately to the multiplicity of u in (∃P ) I .

(P − ) I (u, u ) = P I (u , u) and (∃R) I (u) = u ∈∆ I R I (u, u ).

A bag interpretation I is finite if so are ∆ I and S I for each S ∈ C ∪ R.

Note that, same as in the set case, we adopt the UNA by requiring different individuals be interpreted by different domain elements.

We are now ready to present our two semantics of DL-Lite b F . Both semantics extend the semantics of DL-Lite b core considered in [21], but handle the functional axioms differently. Our first SQL semantics follows the semantics of primary keys in SQL: if R is a functional role then for every domain element u of a model there exists at most one element u related to u by R; moreover, the multiplicity of the tuple (u, u ) in R cannot be more than one. Our second MR semantics allows more freedom for functional roles: same as before, only one u may be related to u by a functional role R, but the multiplicity of (u, u ) may be arbitrary.

Definition 3. A bag interpretation I satisfies an inclusion axiom C 1 C 2 if C I 1 ⊆ C I 2 . It satisfies a disjointness axiom Disj(C 1 , C 2 ) if C I 1 ∩ C I 2 = ∅.

It satisfies a functionality axiom (funct R) under SQL semantics (or SQL-satisfies, for short) if u = u and R I (u, u ) = R I (u, u ) = 1 for every u, u , and u in ∆ I such that R I (u, u ) > 0 and R I (u, u ) > 0; it satisfies (funct R) under MR semantics (or MR-satisfies) if the same holds except that the restriction F ontology is X-satisfiable if it has an X-model.

R I (u, u ) = R I (u, u ) = 1 is not imposed.

Since MR-satisfaction is a relaxation of SQL-satisfaction, every SQL-model of a DL-Lite b

F ontology is also an MR-model of this ontology. However, as illustrated by the following example, the opposite does not hold. To conclude this section, we note that each semantics has its advantages and drawbacks. Indeed, on the one hand, SQL semantics is compatible with primary keys in SQL, so a large fragment of DL-Lite b F under this semantics can be easily simulated by a SQL engine. On the other hand, one can show that entailment of axioms under set and bag semantics coincides only for the case of MR models; this means that the adoption of MR semantics does not affect the standard TBox reasoning services implemented in ontology development tools. So neither of the two semantics is clearly preferable to the other.

Queries over DL-Lite b

F

We next define the answers q I to a CQ q(x) over a bag interpretation I as the bag of tuples of individuals such that each valid embedding λ of the atoms in q into I contributes separately to the multiplicity of the tuple λ(x) in q I , and where the contribution of each specific λ is the product of the multiplicities of the images of the query atoms under λ in I. This may be seen as usual CQ answering under bag semantics over relational databases when the interpretation is seen as a bag database instance [9]. In fact, it can be easily observed that q as a BCALC query evaluated over this bag database instance gives exactly q I . Definition 4. Let q(x) = ∃y. φ(x, y) be a CQ and I = (∆ I , • I ) be a bag interpretation. The bag answers q I to q over I are the bag over tuples of individuals from I of size |x| such that, for every such tuple a,

q I (a) = λ∈Λ S(t) in φ(x,y) S I (λ(t)),

where Λ is the set of all valuations λ : x ∪ y ∪ I → ∆ I such that λ(x) = a I , λ(a) = a I for each a ∈ I, and λ(z) = λ(t) for each z = t in φ(x, y).

Note that conjunction φ(x, y) in a CQ may contain repeated atoms, and hence can be seen as a bag of atoms; while repeated atoms are redundant in the set case, they are essential in the bag setting [9,12], and thus in the definition of q I (a) each occurrence of a query atom S(t) is treated separately in the product.

The following definition of certain answers, which captures open-world query answering [14], is a natural extension of certain answers for DL-Lite F to bags. For DL-Lite b core , this definition coincides with the one in [21] for both semantics.

Definition 5. For X being SQL or MR, the X-bag certain answers q K X to a CQ q over a DL-Lite b F ontology K are the bag

I |= X K q I .

Note that in this definition we assume that the intersection of zero bags (which is relevant when K is not X-satisfiable) assigns ∞ to all tuples over I.

The (data complexity version of the) decision problem corresponding to computing the X-bag certain answers to a CQ q over an ontology with a DL-Lite F TBox T , for X being SQL or MR, is defined as follows, assuming that all numbers in the input are represented in unary.

BagCert X [q, T ]

Input: ABox A, tuple a of individuals from I, and k ∈ N ∞ 0 . Question: Is q (T ,A) X (a) ≥ k?

Besides the complexity of query answering, an important related property of any description logic is query rewritability: since TBoxes are much more stable than ABoxes in practice, it is desirable to be able to rewrite a query and a TBox into another query so that the answers to the original query over each satisfiable ontology with this TBox are the same as the answers to the rewriting over the ABox alone. The rewriting may be in a richer query language than the language of the original query, provided we have an efficient query engine for the target language; it is important, however, that the rewriting does not depend on the ABox. In our setting, the source language is CQs and the target language is BCALC, which can be easily translated to SQL. Definition 6. For X being SQL or MR, a BCALC query Φ is an X-rewriting of a CQ q with respect to a DL-Lite F TBox T if q (T ,A) X = Φ A for every bag ABox A with (T , A) X-satisfiable. A class Q of CQs is X-rewritable to a class Q of BCALC queries over a sublanguage L of DL-Lite F if, for every CQ in Q and TBox in L, there is an X-rewriting of the CQ with respect to the TBox in Q .

Since evaluation of fixed BCALC queries is in TC 0 [16], rewritability to BCALC implies TC 0 data complexity of query answering, provided rewritings are effectively constructible. BagCert X [q, T ] is coNP-hard even for DL-Lite b core ontologies (for both X) [21], which precludes efficient query answering and BCALC rewritability (under the usual complexity-theoretic assumptions). However, rewritability and TC 0 data complexity of query answering are regained for the class of rooted CQs, which are common in practice. The main goal of this paper is to understand to what extent these positive results transfer to DL-Lite b F . We next establish some basic properties of the proposed bag semantics and relate them to the standard set semantics. The following theorem states that satisfiability and query answering under the set semantics and MR semantics are essentially equivalent when multiplicities are ignored, while SQL semantics is in a sense stronger as only one direction of the statements holds.

Theorem 1. The following statements hold for every DL-Lite F TBox T and every bag ABox A (recall that ε is the duplicate elimination operator): 1. if (T , A) is SQL-satisfiable then (T , ε(A)) is satisfiable; and 2. for every tuple a over I, if a ∈ q (T ,ε(A)) then q (T ,A) SQL (a) ≥ 1, and the converse holds whenever (T , A) is SQL-satisfiable. The same holds when MR semantics is considered instead of SQL; moreover, in this case the converses of both statements hold unconditionally.

In fact, the converse direction of statement 1 does not hold for SQL semantics; indeed, the DL-Lite b F ontology K ex of Example 1 is not SQL-satisfiable but (T ex , ε(A ex )) is satisfiable.

Statement 1 for MR semantics implies that we can check MR-satisfiability of DL-Lite b F ontologies using standard techniques for DL-Lite F under the set semantics; in particular, we can do it in AC 0 for fixed TBoxes. The following proposition says that for SQL semantics the problem is not much more difficult.

Proposition 1. The problem of checking whether a DL-Lite b

F ontology is SQLsatisfiable is in TC 0 when the TBox is fixed.

Finally, note that, since every SQL-model of a DL-Lite b F ontology is also its MR-model, q K MR ⊆ q K SQL for every CQ q and DL-Lite b F ontology K; it is not difficult to see that the inclusion may be strict even if K is SQL-satisfiable. F under our two semantics (recall that the class of all CQs are not rewritable even over DL-Lite b core [21]). We first show that for SQL semantics and satisfiable ontologies we can apply the same rewriting as for DL-Lite b core [21], which implies TC 0 data complexity of query answering. However, MR semantics is more complex, because, as we show, even simple rooted CQs (in particular, instance queries) have LogSpace-hard query answering, which precludes rewritability (assuming TC 0 LogSpace). To overcome this, we introduce a new acyclicity condition on TBoxes, for which we show that rewritability is regained.

SQL Semantics

The key ingredient for rewritability and tractability of query answering in many description logics is the existence of a universal model. Definition 7. For X being SQL or MR, an X-model I of a DL-Lite b F ontology K is X-universal for a class of CQs Q if q K X = q I for every q ∈ Q.

In the set case, it is well-known that if the ontology is satisfiable, then the socalled canonical interpretation, which can be constructed by the chase procedure, is always a universal model for all CQs [2,6]. Nikolaou et al. generalised Since the proof of rewritability in [21] is constructive, SQL-satisfiability is in AC 0 , and BCALC evaluation is in TC 0 , rooted CQ answering is also in TC 0 . Corollary 2. Problem BagCert SQL [q, T ] is in TC 0 for every rooted CQ q and DL-Lite F TBox T .

MR Semantics

Since evaluation of BCALC queries is in TC 0 , the following theorem says that even very simple rooted CQs (in particular, instance queries) are unlikely to be MR-rewritable to BCALC. Next we introduce a restriction on TBoxes which guarantees MR-rewritability. Definition 8. The functional dependency graph G T of a DL-Lite F T is the directed graph that has all the concepts appearing in T as nodes, a usual edge (C 1 , C 2 ) for each C 1 C 2 in T , and a special edge (C 1 , ∃R − ) * for each C 1 ∃R with (funct R) in T , where, for P ∈ R, R − is P if R is P − . TBox T is functionally weakly acyclic if G T has no cycle with a special edge. The f-depth d T of such a TBox T is the maximum number of special edges along a path in G T .

We will need the following technical notions. As in [21], the concept closure ccl T [u, I] of an element u ∈ ∆ I in a bag interpretation I = (∆ I , • I ) over a TBox T is the bag of concepts such that, for any concept C,

ccl T [u, I](C) = max{C I 0 (u) | T |= C 0 C}.

The union I ∪ J of two bag interpretations I = (∆ I , • I ) and J = (∆ J , • J ) such that a I = a J for all a ∈ I is the bag interpretation (∆ I ∪ ∆ J , • I∪J ) with a I∪J = a I for all a ∈ I and S I∪J = S I ∪S J for all S ∈ C∪R. Given a bag ABox A, we denote by I A the standard interpretation of A that is defined as follows:

∆ I A = I, a I A =F ontology K = (T , A) is the union i≥0 L i (K) of bag interpretations L i (K) = (∆ L i (K) , • L i (K) ) with ∆ L i (K) = I such that L 0 (K) = I A

and, for each i ≥ 1, L i (K) extends L i−1 (K) so that a L i (K) = a for all a ∈ I, and, for all A ∈ C, P ∈ R and a, b, c, c ∈ I,

A L i (K) (a) = ccl T [a, L i−1 (K)](A), P L i (K) (a, b) = 0, if P L i−1 (K) (a, b) = 0, max{ P (a, b), P − (b, a)}, otherwise, where R (c, c ) = ccl T [c, L i−1 (K)](∃R), if (funct R) is in T , R L i−1 (K) (c, c ), otherwise.

In fact, if TBox is functionally weakly acyclic then the closure can be computed in a finite number of steps that does not depend on the ABox.

Proposition 3. For every DL-Lite b F ontology K = (T , A) with a functionally weakly acyclic TBox T we have L

(K) = d T +1 i=0 L i (K).

We use the closure in the following definition of MR-canonical interpretations. Note the difference in handling functional and non-functional roles when creating anonymous elements, resulting in a most general possible interpretation.

Definition 9. The MR-canonical bag interpretation C MR (K) of a DL-Lite b F on- tology K = (T , A) is the union i≥0 C i MR (K) of bag interpretations C i MR (K) with C 0 MR (K) = L(K) and, for each i ≥ 1, C i MR (K) obtained from C i−1 MR (K) as follows: -∆ C i MR (K) extends ∆ C i−1 MR (K)

by -a fresh anonymous element w u,R for each u ∈ ∆ C i−1 MR (K) and each role R with (funct R) ∈ T , ccl T [u, C i−1 MR (K)](∃R) > 0, and (∃R) C i−1 MR (K) (u) = 0, -fresh anonymous elements w 1 u,R , . . . , w δ u,R for each u ∈ ∆ C i−1 MR (K) and each role R with (funct R) ∈ T and δ = ccl T [u, C i−1 MR (K)](∃R) − (∃R) C i−1 MR (K) (u); -a C i MR (K) = a for all a ∈ I, and, for all A ∈ C, P ∈ R, and u, v in ∆ C i MR (K) ,

A C i MR (K) (u) = ccl T [u, C i−1 MR (K)](A), if u ∈ ∆ C i−1 MR (K) , 0,

otherwise,

P C i MR (K) (u, v) =                P C i−1 MR (K) (u, v), if u, v ∈ ∆ C i−1 MR (K) , ccl T [u, C i−1 MR (K)](∃P ), if u ∈ ∆ C i−1 MR (K) and v = w u,P , ccl T [v, C i−1 MR (K)](∃P − ), if v ∈ ∆ C i−1 MR (K) and u = w v,P − , 1,

if v = w j u,P or u = w j v,P − , 0, otherwise.

As the following theorem says, the MR-canonical bag interpretation is an MR-universal model, as desired. By adapting and extending the techniques in [21], we establish that rooted CQs are MR-rewritable to BCALC over the restricted ontology language. Hence, under the restrictions, query answering is indeed feasible in TC 0 . Corollary 3. Problem BagCert MR [q, T ] is in TC 0 for every rooted CQ q and functionally weakly acyclic DL-Lite F TBox T .

Conclusions

In this paper, we studied two bag semantics for functionality axioms: our first SQL semantics follows the bag semantics of SQL for primary keys, while the second MR semantics is more general and gives more modelling freedom. Combining the semantics with the bag semantics of DL-Lite core of [20,21], we studied the problems of satisfiability, query answering, and rewritability for the resulting logic DL-Lite b F . To the best of our knowledge, this is the first work studying the interaction of functionality and inclusion axioms under a bag semantics. A bag semantics for functional dependencies, which generalises our SQL semantics for functionality axioms, has been studied before in [13]. It would be interesting to see how our work generalises to the case of n-ary predicates. This case has been studied only very recently in the context of data exchange settings [11] and language Datalog ± [3], which, however, do not consider functional dependencies.