Ontology-based data access (OBDA) is a popular approach for integrating and querying multiple data sources by means of an ontology, which is usually expressed in a description logic (DL) of DL-Lite family. The conventional semantics of OBDA and DLs is set-based|that is, duplicates are disregarded. This disagrees with the standard database bag (multiset) semantics, which is especially important for the correct evaluation of aggregate queries. In this article, we study two variants of the bag semantics for query answering over DL-LiteF , extending basic DL-Litecore with functional roles. For our rst semantics, which follows the semantics of primary keys in SQL, conjunctive query (CQ) answering is coNP-hard in data complexity in general, but it is in TC0 for the restricted class of rooted CQs; such CQs are also rewritable to the bag relational algebra. For our second semantics, the results are the same except that TC0 membership and rewritability hold only for the restricted class of ontologies identi ed by a new notion of functional weak acyclicity.
Ontology-based data access (OBDA) is an increasingly popular approach for
enabling uniform access to multiple data sources with diverging schemas [
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 [
Building on the work of Nikolaou et al. [
We study how the two semantics relate to the set-based semantics of DL-LiteF and to each other in terms of the standard reasoning tasks of satis ability 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 satis ability becomes stronger than under set semantics, while query answering for satis able 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 TC0. 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 TC0.
The rest of the paper is organised as follows. Section 2 introduces the
relevant background. Section 3 de nes the SQL and MR semantics as extensions
of the bag semantics proposed in [
Acknowledgements Research supported by the SIRIUS Centre for Scalable Data Access and the EPSRC projects DBOnto, MaSI3, and ED3. 2
We start by de ning DL-LiteF ontologies as well as the notions of query
answering and rewriting over such ontologies, all over the usual set semantics [
Semantics of DL-LiteF . 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 2 I to aI 2 I such that aI 6= bI for all a; b 2 I (i.e., as usual for DL-Lite we adopt the UNA|that is, the unique name assumption), each A 2 C to AI I , and each P 2 R to P I I I . Interpretation function I extends to non-atomic concepts and roles as follows: (P )I = f(u; u0) j (u0; u) 2 P I g; (9R)I = fu 2 I j 9u0 2
I : (u; u0) 2 RI g:
An interpretation I satis es a DL-LiteF TBox T if C1I C2I for each inclusion
axiom C1 v C2 in T , C1I \C2I = ; for each Disj(C1; C2) in T , and v1 = v2 for each
(u; v1), (u; v2) in RI with (funct R) in T . Interpretation I satis es an ABox A if
aI 2 AI for all A(a) 2 A and (aI ; bI ) 2 P I for all P (a; b) 2 A. An interpretation
I is a model of an ontology (T ; A) if it satis es T and A. An ontology is satis able
if it has a model. Checking satis ability of a DL-LiteF ontology is
NLogSpacecomplete in general and in AC0 if the TBox is xed [
Queries over DL-LiteF . A conjunctive query (CQ ) q(x) with answer variables
x is a formula 9y: (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 (t1; t2) or (z = t), where A 2 C, P 2 R, z 2 x [ y,
and t; t1; t2 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 2 x [ y [ I in , and an edge ft~1; t~2g for each atom
in over t1 and t2. We assume that all CQs are safe|that is, for each z 2 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 [
Bags. A bag over a set M is a function : M ! N01, where N01 is the set N0
of non-negative integers extended with the (positive) in nity 1. The value (c)
is the multiplicity of element c in . A bag is nite if there are nitely many
c 2 M with (c) > 0 and there is no c with (c) = 1. The empty bag ; over M
is the bag such that ;(c) = 0 for each c 2 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 2 M . Often we
will use an alternative syntax for bags: for instance, we will write fj c : 5; d : 3 jg
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 [
2)(c) = maxf 1(c); 2(c)g;
2)(c) =
1(c) +
2(c);
( 1
2)(c) = maxf0; 1(c)
2(c)g:
Note that bag di erence is well-de ned only if 2(c) is a nite number for each
c 2 M . The unary duplicate elimination operator " is de ned for a bag over
M and for each c 2 M as ("( ))(c) = 1 if (c) > 0 and ("( ))(c) = 0 otherwise.
Queries over Bags. Following [
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, nite 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 nite bag over Ijxj de ned inductively by the following equations, for every tuple a over I with jaj = jxj, where : x [ I ! I is the function such that (x) = a and (a) = a for all a 2 I: { A(a) = A(S( (t))), if (x) = S(t); { A(a) = 1A( (x1)) 2A( (x2)), if (x) = 1(x1) ^ 2(x2); { A(a) = A( (x0)), if (x) = (x0) ^ (x = t) and (x) = (t); { A(a) = 0, if (x) = (x0) ^ (x = t) and (x) 6= (t); { A(a) = P 0: y!I A(a; 0(y)), if (x) = 9y: (x; y); { A(a) = ( 1A op 2A)(a), if (x) = 1(x) op0 2(x), where op is [, ], or , and op0 is _, _: , or n, respectively; { A(a) = "( A) (a), if (x) = (x).
As shown in [
In this section we introduce the bag version DL-LitebF of the ontology language
DL-LiteF with two semantics and study their properties and relationships. Both
semantics extend the bag semantics of DL-Litecbore studied in [
Syntactically, DL-LitebF is the same as DL-LiteF except that assertions in ABoxes may have arbitrary nite multiplicities|that is, bag ABoxes are considered instead of set ABoxes. Note that syntactically DL-LitebF is a conservative extension of DL-LiteF , since each set ABox can be seen as a bag ABox with assertion multiplicities 0 and 1.
De nition 1. A DL-LitebF ontology is a pair (T ; A) of a DL-LiteF TBox T and a bag ABox A. A DL-Litecbore ontology is the same except that T is DL-Litecore.
The semantics of DL-LitebF 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 de ned in a way that respects the multiplicities: for example, the concept 9P for an atomic role P is interpreted by a bag interpretation I as the bag projection of P I to its rst component, where each occurrence of a pair (u; v) in P I contributes separately to the multiplicity of u in (9P )I .
De nition 2. A bag interpretation I is a pair ( I ; I ) where the domain I is a non-empty set, and the interpretation function I maps each a 2 I to an element aI 2 I such that aI 6= bI for all a; b 2 I, each A 2 C to a bag AI over I , and each P 2 R to a bag P I over I I . Interpretation function I extends to non-atomic concepts and roles as follows, for all P 2 R, R a role, and u; u0 2 I : (P )I (u; u0) = P I (u0; u) and (9R)I (u) = X
A bag interpretation I is nite if so are
I and SI for each S 2 C [ R.
Note that, same as in the set case, we adopt the UNA by requiring di erent individuals be interpreted by di erent domain elements.
We are now ready to present our two semantics of DL-LitebF . Both semantics
extend the semantics of DL-Litecbore considered in [
For X being SQL or MR, a bag interpretation I X-satis es a DL-LiteF TBox T , written I j=X T , if it (X-)satis es every axiom in T . A bag interpretation I = ( I ; I ) satis es a bag ABox A, written I j= A, if A(A(a)) AI (aI ) and A(P (a; b)) P I (aI ; bI ) for each concept assertion A(a) and role assertion P (a; b), respectively. A bag interpretation I is an X-model of a DL-LitebF ontology (T ; A), written I j=X (T ; A), if I j=X T and I j= A. A DL-LitebF ontology is X-satis able if it has an X-model.
Since MR-satisfaction is a relaxation of SQL-satisfaction, every SQL-model of a DL-LitebF ontology is also an MR-model of this ontology. However, as illustrated by the following example, the opposite does not hold.
Example 1. Consider an online store that employs atomic roles hasItem and placedBy for recording the items ordered by customers in a purchase. Then, a sample DL-LitebF ontology recording an order is Kex = (Tex; Aex) with TBox Tex = f9hasItem v 9placedBy; (funct placedBy)g and ABox Aex = fj hasItem(o; i1) : 1; hasItem(o; i2) : 1; placedBy(o; c) : 1 jg. Let Iex be the bag interpretation interpreting individuals by themselves and roles as hasItemIex = fj (o; i1) : 1; (o; i2) : 1 jg, placedByIex = fj (o; c) : 2 jg. It is immediate to see that Iex is an MR-model of Kex but not a SQL-model.
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-LitebF 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 a ect the standard TBox reasoning services implemented in ontology development tools. So neither of the two semantics is clearly preferable to the other.
We next de ne the answers qI 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 qI ,
and where the contribution of each speci c 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 [
X
Y 2
S(t) in (x;y)
SI ( (t)); where is the set of all valuations : x [ y [ I ! I such that (x) = aI , (a) = aI for each a 2 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 [
The following de nition of certain answers, which captures open-world query
answering [
Note that in this de nition we assume that the intersection of zero bags (which is relevant when K is not X-satis able) assigns 1 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-LiteF TBox T , for X being SQL or MR, is de ned as follows, assuming that all numbers in the input are represented in unary.
BagCertX [q; T ] Input: ABox A, tuple a of individuals from I, and k 2 N01.
Question: Is qX(T ;A)(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 satis able 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 e cient 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.
De nition 6. For X being SQL or MR, a BCALC query is an X-rewriting of a CQ q with respect to a DL-LiteF TBox T if qX(T ;A) = A for every bag ABox A with (T ; A) X-satis able. A class Q of CQs is X-rewritable to a class Q0 of BCALC queries over a sublanguage L of DL-LiteF if, for every CQ in Q and TBox in L, there is an X-rewriting of the CQ with respect to the TBox in Q0.
Since evaluation of xed BCALC queries is in TC0 [
We next establish some basic properties of the proposed bag semantics and relate them to the standard set semantics. The following theorem states that satis ability 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-LiteF TBox T and every bag ABox A (recall that " is the duplicate elimination operator): 1. if (T ; A) is SQL-satis able then (T ; "(A)) is satis able; and 2. for every tuple a over I, if a 2 q(T ;"(A)) then qS(TQ;LA)(a) 1, and the converse holds whenever (T ; A) is SQL-satis able.
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-LitebF ontology Kex of Example 1 is not SQL-satis able but (Tex; "(Aex)) is satis able.
Statement 1 for MR semantics implies that we can check MR-satis ability of DL-LitebF ontologies using standard techniques for DL-LiteF under the set semantics; in particular, we can do it in AC0 for xed TBoxes. The following proposition says that for SQL semantics the problem is not much more di cult. Proposition 1. The problem of checking whether a DL-LitebF ontology is SQLsatis able is in TC0 when the TBox is xed.
Finally, note that, since every SQL-model of a DL-LitebF ontology is also its MR-model, qMKR qSKQL for every CQ q and DL-LitebF ontology K; it is not di cult to see that the inclusion may be strict even if K is SQL-satis able.
F
We next study rewritability of rooted CQs to BCALC over DL-LitebF under
our two semantics (recall that the class of all CQs are not rewritable even over
DL-Litecbore [
SQL Semantics The key ingredient for rewritability and tractability of query answering in many description logics is the existence of a universal model.
De nition 7. For X being SQL or MR, an X-model I of a DL-LitebF ontology K is X-universal for a class of CQs Q if qXK = qI for every q 2 Q.
In the set case, it is well-known that if the ontology is satis able, then the
socalled canonical interpretation, which can be constructed by the chase procedure,
is always a universal model for all CQs [
Proposition 2. Every SQL-satis able DL-LitebF ontology has a SQL-universal model for rooted CQs.
Having this result at hand, we can reuse the rewriting of rooted CQs over
DL-Litecbore introduced in [
Since the proof of rewritability in [
MR Semantics Since evaluation of BCALC queries is in TC0, the following theorem says that even very simple rooted CQs (in particular, instance queries) are unlikely to be MR-rewritable to BCALC.
Theorem 2. There is a CQ of the form A(a) with A 2 C and a 2 I, and a DL-LiteF TBox T such that problem BagCertMR[A(a); T ] is LogSpace-hard.
Next we introduce a restriction on TBoxes which guarantees MR-rewritability. De nition 8. The functional dependency graph GT of a DL-LiteF T is the directed graph that has all the concepts appearing in T as nodes, a usual edge (C1; C2) for each C1 v C2 in T , and a special edge (C1; 9R ) for each C1 v 9R with (funct R) in T , where, for P 2 R, R is P if R is P . TBox T is functionally weakly acyclic if GT has no cycle with a special edge. The f-depth dT of such a TBox T is the maximum number of special edges along a path in GT .
We will need the following technical notions. As in [
cclT [u; I](C) = maxfC0I (u) j T j= C0 v Cg: The union I [ J of two bag interpretations I = ( I ; I ) and J = ( J ; J ) such that aI = aJ for all a 2 I is the bag interpretation ( I [ J ; I[J ) with aI[J = aI for all a 2 I and SI[J = SI [SJ for all S 2 C[R. Given a bag ABox A, we denote by IA the standard interpretation of A that is de ned as follows:
IA = I, aIA = a for each a 2 I, and SIA (a) = A(S(a)) for each S 2 C [ R and tuple of individuals a. The closure L(K) of a DL-LitebF ontology K = (T ; A) is the union Si 0 Li(K) of bag interpretations Li(K) = ( Li(K); Li(K)) with
Li(K) = I such that L0(K) = IA and, for each i 1, Li(K) extends Li 1(K) so that aLi(K) = a for all a 2 I, and, for all A 2 C, P 2 R and a; b; c; c0 2 I, ALi(K)(a) = cclT [a; Li 1(K)](A); if P Li 1(K)(a; b) = 0; P Li(K)(a; b) =
(0; `R(c; c0) =
maxf`P (a; b); `P (b; a)g; otherwise, where (cclT [c; Li 1(K)](9R); if (funct R) is in T ;
RLi 1(K)(c; c0); otherwise: In fact, if TBox is functionally weakly acyclic then the closure can be computed in a nite number of steps that does not depend on the ABox.
Proposition 3. For every DL-LitebF ontology K = (T ; A) with a functionally weakly acyclic TBox T we have L(K) = SdT +1 i i=0 L (K).
We use the closure in the following de nition of MR-canonical interpretations. Note the di erence in handling functional and non-functional roles when creating anonymous elements, resulting in a most general possible interpretation. De nition 9. The MR-canonical bag interpretation CMR(K) of a DL-LitebF ontology K = (T ; A) is the union Si 0 CMiR(K) of bag interpretations CMiR(K) with CM0R(K) = L(K) and, for each i 1, CMiR(K) obtained from CMiR1(K) as follows:
CMiR(K) extends
CMiR1(K) by - a fresh anonymous element wu;R for each u 2
with (funct R) 2 T , cclT [u; CMiR1(K)](9R) > 0, and (9R)CMiR1(K)(u) = 0, - fresh anonymous elements wu1;R; : : : ; wu;R for each u 2 CMiR1(K) and each CMiR1(K) and each role R role R with (funct R) 62 T and = cclT [u; CMiR1(K)](9R) { aCMiR(K) = a for all a 2 I, and, for all A 2 C, P 2 R, and u, v in (9R)CMiR1(K)(u);
CMiR(K), ACMiR(K)(u) = (cclT [u; CMiR1(K)](A); if u 2 0; otherwise;
CMiR1(K);
CMiR1(K) and u = wv;P ; j j if v = wu;P or u = wv;P ;
As the following theorem says, the MR-canonical bag interpretation is an MR-universal model, as desired.
Theorem 3. The MR-canonical bag interpretation CMR(K) of an MR-satisable DL-LitebF ontology K = (T ; A) with T functionally weakly acyclic is an MR-universal model for the class of rooted CQs.
By adapting and extending the techniques in [
Hence, under the restrictions, query answering is indeed feasible in TC0. Corollary 3. Problem BagCertMR[q; T ] is in TC0 for every rooted CQ q and functionally weakly acyclic DL-LiteF TBox T . 5
In this paper, we studied two bag semantics for functionality axioms: our rst
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-Litecore of [