An ontology-based data access (OBDA) system is composed of one or more data sources, an ontology that provides a conceptual view of the data, and declarative mappings that relate the data and ontology schemas. In order to debug and optimize such systems, it is important to be able to analyze and compare OBDA specifications. Recent work in this direction compared specifications using classical notions of equivalence and entailment, but an interesting alternative is to consider query-based notions, in which two specifications are deemed equivalent if they give the same answers to the considered query or class of queries for all possible data sources. In this paper, we define such query-based notions of entailment and equivalence of OBDA specifications and investigate the complexity of the resulting analysis tasks when the ontology is formulated in DL-LiteR.
Ontology-based data access (OBDA) [
Due to the recent availability of techniques and systems for query processing in this
setting [
In addition, the OBDA specification plays a major role in query answering, since
the form of the specification may affect the system performance in answering queries:
different, yet semantically equivalent specifications may give rise to very different
execution times for the same query. So, the study of notions of equivalence and formal
comparison of OBDA specifications is also important for optimizing query
processing in OBDA systems. Indeed, some systems already implement forms of optimization
based on transformations of the OBDA specification (an example is [
So far, most of the work in OBDA has focused on query answering, often in a
simplified setting without any mappings. Very little attention has been devoted to the
formal analysis of OBDA specifications. The first approach that explicitly focuses on
the formal analysis of OBDA specifications is [
The majority of work on on OBDA has considered conjunctive queries (CQs) as the query language. Therefore, a first natural choice would be to compare OBDA specifications with respect to the whole class of CQs. We thus define and study a notion of CQentailment between OBDA specifications that formalizes this case. We also consider the important subclass of instance queries (IQs), i.e., queries that ask for the instances of a single concept or role, and analyze the notion of IQ-entailment between specifications. Moreover, in many application contexts only a (small) set of predefined conjunctive queries are of interest for the OBDA user(s): in such cases, it may be more appropriate to tailor the comparison of specifications to a specific set of queries. For this reason, we also study in this paper the notions of single CQ-entailment and single IQ-entailment, which compare specifications with respect to a single CQ or IQ, respectively.
We present a first investigation of the computational complexity of deciding the
above forms of entailment for a pair of OBDA specifications. We study ontologies
specified in DL-LiteR and three different mapping languages (linear, GAV and GLAV). In
all cases, we provide exact complexity bounds for the entailment problem. Our results
are summarized in Figure 1. As shown in the table, the complexity of the entailment
check ranges from NL (non-deterministic logarithmic space) for linear mappings and
IQ-entailment to EXPTIME for CQ-entailment. To obtain these results, we show that
instead of considering all possible data instances, it is sufficient to consider a small
number of databases of a particular form. We also exploit connections to query containment
in the presence of signature restrictions [
We start from four pairwise disjoint countably infinite set of names: the set of concept names NC, the set of role names NR, the set of relation names Nrel, the set of constant names NI (also called individuals).
To introduce OBDA specifications, we first recall the notion of knowledge base (KB) in Description Logics (DLs). A DL KB is a pair hT ; Ai, where: T , called the TBox, is the intensional component of the KB, and is constituted by a finite set of axioms expressing intensional knowledge; and A, called the ABox, is a finite set of atomic concept and role assertions (set of ground facts). We assume that the concept, role and constant names occurring in every TBox and ABox belong to NC, NR and NI, respectively. We denote by sig(T ) and sig(A) the set of concept and role names occurring in T and A, respectively.
Although the definitions of Section 3 are general, in Section 4 we will focus on
the DL DL-LiteR [
B ! A j 9R
C ! B j :B
R ! P j P
S ! R j :R
We now introduce OBDA specifications. As already explained, a mapping
assertion specifies the semantic relationship between elements of a DL ontology, specified
through a TBox, to elements of a database. Such a relationship is specified through
a pair of queries, one over the TBox signature, and the other one over the database
signature. In this paper, we focus on the case where both queries involved in the
mapping assertion are conjunctive queries: such mapping assertions are called GLAV (for
‘global-as-view’) mappings in the literature [
Mappings are formally defined as follows. An atom is an expression r(t) where r is a predicate and t is a tuple of variables and constants. Then, a (GLAV) mapping assertion m is an expression of the form qs(x) ! qo(x), where qs(x) (called the body of m, body (m)) is a conjunction of atoms over predicates from Nrel and constants from NI, qo(x) (called the head of m, head (m)) is a conjunction of atoms using predicates from NC [ NR and constants from NI, and x, called the frontier variables of m, are the variables that appear both in qo and in qs. The arity of m is the number of its frontier variables. When qo(x) has the form p(x) (i.e., qo(x) is a single atom whose arguments are x), we call m a GAV mapping assertion. A linear mapping assertion is a GAV assertion whose body consists of a single atom. A (GLAV) mapping M is a set of mapping assertions. A GAV mapping is a mapping constituted of GAV mapping assertions. A linear mapping is a set of linear mapping assertions. Without loss of generality, we assume that in every mapping M, every pair of distinct mapping assertions uses pairwise disjoint sets of variables.
An OBDA specification is a pair = hT ; Mi, where T is a TBox and M is a mapping. Given a mapping assertion m of arity n and an n-tuple of constants a, we denote by m(a) the assertion obtained from m by replacing the frontier variables with the constants in a.
Given a set of atoms AT , gr (AT ) is the function that returns the set of ground atoms obtained from AT by replacing every variable symbol x with a fresh constant symbol cx. We assume that such constant symbols do not occur elsewhere in the application context of the function gr (i.e., in the TBoxes, mappings and databases involved).
In this paper, a database (instance) is a set of ground atoms using relation names from Nrel and constant names from NI. Given a mapping M and a database instance D, we define the ABox for D and M, denoted as AM;D, as the following ABox: f
2 gr (head (m(a))) j m 2 M and and D j= 9y:body (m(a)) g where we assume that y are the variables occurring in body (m(a)). Given an OBDA specification = hT ; Mi and a database instance D, we define the models of and D, denoted as M ods( ; D) as the set of models of the KB hT ; AM;Di. When such a set is empty, we write hT ; M; Di j= ? (analogously, when a KB hT ; Ai has no models, we write hT ; Ai j= ?).
We are interested in the problem of answering instance queries and conjunctive queries over a pair composed of an OBDA specification and a database. A Boolean conjunctive query (CQ) is an expression of the form 9x( 1 ^ : : : ^ n) where every i is an atom whose arguments are either constants or variables from x. For a non-Boolean CQ q with answer variables v1; : : : ; vk, a tuple of constants a = ha1; : : : ; aki occurring in A is said to be a certain answer for q w.r.t. K just in the case that K j= q(a), where q(a) is the Boolean query obtained from q by replacing each vi by ai. We call instance query (IQ) a CQ consisting of a single atom of the form A(x) or R(x; y), with A concept name, R role name, and x; y distinct free variables. We denote by sig(q) the set of concept and role names occurring in a query q. We use CQ (resp. IQ ) to refer the set of all CQs (resp. IQs) over the DL signature NC [ NR.
Given an OBDA specification = hT ; Mi, a database instance D, and a conjunctive query q, we define the certain answers for q w.r.t. ( ; D) as the tuples of constants from D that are certain answers for q w.r.t. hT ; AM;Di. In particular, for Boolean CQs, we say that q is entailed by ( ; D), denoted by ( ; D) j= q (or hT ; M; Di j= q), if I j= q for every I 2 M ods( ; D). Note that for non-Boolean queries, we only consider tuples of constants from D, in order to avoid including those fresh constants introducing in AM;D by grounding existential variables in mapping heads. 3
We start by recalling the classical notion of entailment between OBDA specifications.
hT2; M2i, written hT1; M1i j=log hT2; M2i if and only the first-order theory T1 [ M1 logically entails the first-order theory T2 [ M2.
We now define the formal notions of query-based entailment between OBDA specifications considered in this paper. First, we introduce a notion of entailment that compares specifications based upon the constraints they impose regarding consistency. Definition 2 (?-entailment). Let q be a query. An OBDA specification hT1; M1i ?entails hT2; M2i, written hT1; M1i j=? hT2; M2i, iff, for every database D, hT2; M2; Di j= ?
)
Next, we define a notion of query entailment between OBDA specifications with respect to a single query. hT1; M1; Di j= ? Definition 3 (Single query entailment). Let q be a query. An OBDA specification hT1; M1i q-entails hT2; M2i, written hT1; M1i j=q hT2; M2i, if and only if hT1; M1i j=? hT2; M2i and for every database D, hT2; M2; Di j= q(a) ) hT1; M1; Di j= q(a) When q is an IQ, we call the entailment relation in the preceding definition single IQentailment, while we call it single CQ-entailment if q is an arbitrary CQ.
We can generalize the previous definition to classes of queries as follows. Definition 4 (Query entailment). Let L be a (possibly infinite) set of queries. An OBDA specification hT1; M1i L-entails hT2; M2i, written hT1; M1i j=L hT2; M2i iff hT1; M1i j=? hT2; M2i and hT1; M1i j=q hT2; M2i for every query q 2 L. When L = IQ, we call the preceding entailment relation IQ-entailment, and for L = CQ, we use the term CQ-entailment.
Note that, for each of the above notions of entailment, a notion of equivalence between OBDA specifications can be immediately derived, corresponding to entailment in both directions (we omit the formal definitions due to space limitations).
The following property immediately follows from the above definitions. Proposition 1. Let hT1; M1i; hT2; M2i be two OBDA specifications, and let L1 be a set of queries. Then, hT1; M1i j=log hT2; M2i implies hT1; M1i j=L1 hT2; M2i. Moreover, if L2 L1, then hT1; M1i j=L1 hT2; M2i implies hT1; M1i j=L2 hT2; M2i.
As a consequence of the above property, we have that logical entailment implies CQ-entailment, and CQ-entailment implies IQ-entailment. The converse implications do not hold, as the following examples demonstrate.
Example 1. We start by illustrating the difference between logical entailment and CQ-entailment. Consider a database containing instances for the relation EXAM(studentName,courseName,grade,date). Then, let 1 = hT1; M1i, where T1 = fStudent v Person; PhDStudent v Studentg
M1 = fEXAM(x; y; z; w) ! Student(x)g and let 2 = hT2; M2i, where T2 = fStudent v Persong and M2 = M1. It is immediate to verify that 2 6j=log 1. However, we have that 2 j=CQ 1. Indeed, 2 j=CQ 1 can be intuitively explained by the fact that the mapping M1 does not retrieve any instances of the concept PhDStudent (and there are no subclasses that can indirectly populate it), so the presence of the inclusion PhDStudent v Student in T1 does not have any effect on query answering; in particular, every CQ that mentions the concept PhDStudent cannot be entailed both under 1 and under 2. Notice also that, if we modify the mapping M1 to map PhDStudent instead of Student (i.e., if M1 were fEXAM(x; y; z; w) ! PhDStudent(x)g), then CQ-entailment between 2 and 1 would no longer hold.
Next, consider 3 = hT3; M3i, where T3 = ; and
M3 = fEXAM(x; y; z; w) ! Student(x); EXAM(x; y; z; w) ! Person(x)g Again, it it immediate to see that 3 6j=log 2, while we have that 3 j=CQ 2. Indeed, 3 j=CQ 2 follows informally from the fact that the mapping M3 is able to “extensionally” simulate the inclusion Student v Person of T2, which is sufficient for 3 to entail every CQ in the same way as 2.
Example 2. We slightly modify the previous example to show the difference between CQ-entailment and IQ-entailment. Consider 1 = hT1; Mi and 2 = hT2; Mi where T1 = fStudent v Person; Student v 9takesCourseg T2 = fStudent v Persong
M = fEXAM(x; y; z; w) ! Student(x)g Type of entailment
Type of mapping logical ? CQ IQ single CQ single IQ
GAV / GLAV linear GAV / GLAV linear linear GAV / GLAV linear / GAV / GLAV linear GAV / GLAV linear / GAV / GLAV
EXPTIME-complete Complexity NP-complete NL-complete NP-complete NL-complete NL-complete NP-complete
2p-complete NL-complete NP-complete Then, it can be easily verified that 2 6j=CQ 1. Indeed, consider the Boolean CQ 9x; y takesCourse(x; y): for every database D, this query is not entailed by the pair ( 2; D), while this is not the case when the specification is 1. On the other hand, we have that 2 j=IQ 1: in particular, for every database D and for every pair of individuals a; b, neither ( 1; D) nor ( 2; D) entails the IQ takesCourse(a; b). Finally, let q be the non-Boolean CQ 9x takesCourse(x; y): then, it can be easily verified that the single CQ-entailment 2 j=q 1 holds; while for the CQ q0 of the form 9y takesCourse(x; y), the single CQ-entailment 2 j=q0 1 does not hold.
In this section, we investigate the computational properties of the different notions of
entailment between OBDA specifications defined in the previous section. For this first
study, we focus on the case in which the TBox is formulated in DL-LiteR [
In what follows, we formally state the different complexity results and provide some ideas about the proofs. We begin by considering the complexity of deciding classical entailment between OBDA specifications.
Theorem 1. Classical logical entailment for OBDA specifications based upon DL-LiteR TBoxes is NP-complete for GAV or GLAV mappings, and NL-complete for linear mappings.
Proof. Let 1 = hT1; M1i, 2 = hT2; M2i. First, it is easy to see that 1 j=log 2 iff
(i) T1 j= T2; and (ii) 1 j=log M2. Property (i) can be decided in NL [
We next consider ?-entailment. Our upper bounds rely on the following result that shows it is sufficient to consider a small number of small databases.
Theorem 2. Let q be a CQ, and let 1 = hT1; M1i and 2 = hT2; M2i be OBDA specifications such that T1; T2 are formulated in DL-LiteR, and M1; M2 are GLAV mappings. Then 1 j=? 2 if and only if hT1; M1; Di j= ? for every database D satisfying the following condition:1 – Condition 1: D is obtained by (i) taking two mapping assertions m1; m2 from M2, (ii) selecting atoms 1 and 2 from head (m1) and head (m2) respectively, (iii) identifying in m1 and m2 some variables from 1 and 2 in such a way that hT ; gr (f 1; 2g)i j= ?, (iv) setting D equal to gr (body (m1) [ body (m2)). Proof. The one direction is immediate from the definitions. For the interesting direction, let us suppose that hT1; M1; Di j= ? for every database D satisfying Condition 1. Let us further suppose that we have hT2; M2; D0i j= ?, where D0 may be any database. We thus have hT2; AM2;D0 i j= ?. It is well known that every minimal inconsistent subset of a DL-LiteR KB contains at most two ABox assertions, so there must exist a subset A0 AM2;D with jA0j 2 such that hT2; A0i j= ?. Let be the conjunction of atoms obtained by taking for each ABox assertion in A0, a mapping assertion that produced it, identifying those variables (and only those variables) needed to produce the ABox assertion(s), and then taking the conjunction of the atoms in the bodies. We observe that by construction D = gr ( ) satisfies Condition 1 and is such that hT1; M1; D i j= ?. By construction, there is a homomorphism of into the original database D0. It follows that hT1; M1; D0i j= ?. tu
Using the preceding result, we can pinpoint the complexity of ?-entailment. Theorem 3. The ?-entailment problem is NP-complete for OBDA specifications based upon DL-LiteR TBoxes and GAV / GLAV mappings, and NL-complete in the case of linear mappings.
Proof. We know from Theorem 2 that 1 j=? 2 iff hT1; M1; Di j= ? for every database D satisfying Condition 1. For the GAV / GLAV case, we guess one such database D and a polynomial-size proof that hT1; M1; Di j= ?. For the linear case, we note that the databases satisfying Condition 1 contain at most 2 tuples each and can be enumerated in logarithmic space. For every such database, we can check using an NL oracle whether hT1; M1; Di j= ?. Since LNL = NL, we obtain an NL procedure. tu
Next we consider entailment with respect to a specific query. We again start by showing it is sufficient to consider a finite number of databases of a particular form. 1 Recall that distinct mapping assertions in a mapping have no common variables. Theorem 4. Let q be a CQ, and let 1 = hT1; M1i and 2 = hT2; M2i be OBDA specifications such that T1; T2 are formulated in DL-LiteR, and M1; M2 are GLAV mappings. Then 1 j=q 2 if and only if 1 j=? 2 and hT2; M2; Di j= q(a) implies hT1; M1; Di j= q(a) for every database D satisfying the following condition: – Condition 2: D is obtained by (i) taking k jqj mapping assertions m1; m2; : : : ; mk from M2, (ii) identifying some of the frontier variables in m1; m2; : : : ; mk, (iii) letting D = gr (body (m1) [ body (m2) [ : : : [ body (mk)). If q is an IQ, then the latter condition can be replaced by: – Condition 3: D is obtained by (i) taking a mapping assertion m from M2 and choosing an atom 2 head (m), (ii) possibly identifying in m the (at most two) frontier variables appearing in , and (iii) letting D = gr (body (m)). Proof. Again the one direction is immediate. To show the non-trivial direction, let us suppose that 1 j=? 2 and that hT2; M2; Di j= q(c) implies hT1; M1; Di j= q(c) for every tuple c and database D satisfying Condition 2 (we return later to the case of IQs). Let us further suppose that we have hT2; M2; D0i j= q(a). The first possibility is that hT2; M2; D0i j= ?, in which case we have hT1; M1; D0i j= ? because of 1 j=? 2. We thus obtain hT1; M1; D0i j= q0(a). The other possibility is that hT2; M2; D0i j= q0(a) and hT2; M2; D0i 6j= ?. If hT1; M1; D0i j= ?, we immediately obtain hT1; M1; D0i j= q0(a). Otherwise, let AM2;D0 be the ABox for M2 and D0. Since hT2; M2; D0i j= q0(a), we have hT2; AM2;D0 i j= q0(a). It is a well-known property of DL-LiteR that there exists a subset A0 AM2;D0 with jA0j jq0j such that hT2; A0i j= q0(a). Let jA0j = k, and let 1; : : : ; k be the ABox assertions in A0. For each i, we choose a mapping assertion mi 2 M2 and a homomorphism hi of body (mi) into D0 such that gr (hi(head (m))) contains i. We also select an atom i 2 head (m) such that gr (h( )) = . Let m0i be obtained from mi by identifying frontier variables y and z if hi(y) = hi(z), and set D0 = gr (body (m01) [ : : : [ body (m0k)). It is easy to see that D0 satisfies Condition 2. Moreover, by construction, the ABox AM2;D0 contains a subset A00 that is isomorphic to A0, and so hT2; M2; D0i j= q0(a0) where a0 is tuple corresponding to a according to this isomorphism. Applying our assumption, we obtain hT1; M1; D0i j= q0(a0). Using the fact that there is a homomorphism of body (m01) [ : : : [ body (m0k) into D0 that is an isomorphism on the frontier variables, we obtain hT1; M1; Di j= q0(a).
Finally, for the case of instance queries, we simply note that we have k = 1, and it is only necessary to identify those variables in the head atom of the mapping that leads to introducing the single ABox assertion of interest. This yields Condition 3.
We pinpoint the complexity of single CQ-entailment, showing it to be Theorem 5. The single CQ-entailment problem is 2p-complete for OBDA specifications based upon DL-LiteR TBoxes and GLAV mappings. The lower bound holds even for linear mapping assertions and when both TBoxes are empty.
Proof. For the upper bound, consider two OBDA specifications 1 = hT1; M1i and 2 = hT2; M2i. From Theorems 2 and 4, we know that 1 6j=q 2 if and only if one of the following holds: tu 2p-complete. – there is a database D satisfying Condition 2 such that hT1; M1; Di 6j= ?; – there is a database D satisfying Condition 2 such that hT2; M2; Di j= q(a), hT2; M2; Di 6j= ?, and hT1; M1; Di 6j= q(a).
The first item can be checked using an NP oracle (by Theorem 3). To check the second item, we remark that the size of databases satisfying Condition 2 cannot exceed max(2; jqj) maxbody, where maxbody is the maximum number of atoms appearing in the body of a mapping assertion in M2. It follows that to show that the second item above is violated, we can guess a database D of size at most max(2; jqj) maxbody together with a tuple of constants a and a polynomial-size proof that hT2; M2; Di j= q(a), and then we can verify using an NP oracle that hT1; M1; Di 6j= q(a). We therefore obtain a 2p procedure for deciding the complement of our problem.
For the lower bound, we utilize a result from [
In what follows, we will show how given T , q1, q2, and as above, we can reduce the problem of testing whether T ; A j= q1 implies T ; A j= q2 for all -ABoxes to the problem of single CQ entailment. We will use for our database instances, and we create two copies 1 = fP 1 j P 2 g and 2 = fP 2 j P 2 g of the signature to be used in the head of mapping assertions. Next, we define sets of mapping assertions copy1( ) and copy2( ) that simply copies all of the predicates in into the corresponding symbol in 1 (resp. 2). Formally, for j 2 f1; 2g, copyj ( ) = fA(x) ! Aj (x) j A 2 \ NCg [ fR(x; y) ! Rj (x; y) j R 2 \ NRg We further define, given a data signature 1 and DL signature populate( 1; 2) of mapping assertions that populates the relations in possible combinations of the constants appearing in tuples over 1: 2, a set 2 using all populate( 1; 2) =fP1(x1; : : : ; xk) ! P2(x01; : : : ; x0`) j P1 2 1; arity(P ) = k; P2 2 2; arity(P ) = `; fx01; : : : ; x0`g fx1; : : : ; xk)g Using copy1( ), copy2( ), populate( ; 1), and populate( ; 2), we construct the following mappings:
M1 = populate( ; 1) [ copy2( )
M2 = copy1( ) [ populate( ; 2) [ fT (x) ! V (x); F (x) ! V (x)g
Observe that both mappings are linear. For the query, we let q10 (resp. q20) be obtained
from q1 (resp. q2) by replacing every predicate P by P 1( resp. P 2). We also rename
variables so that q10 and q20 do not share any variables. We then let q be the CQ obtained
by taking the conjunction of q10 and q20 and existentially quantifying all variables. In the
appendix, we show that h;; M1i j=q h;; M2i iff T ; A j= q1 ) T ; A j= q2 for all
-ABoxes. By combining this with the reduction from [
If we consider IQs instead, the complexity drops to either NP- or NL-complete. Theorem 6. The single IQ-entailment problem is NP-complete for OBDA specifications based upon DL-LiteR TBoxes and either GAV or GLAV mappings. It is NLcomplete if linear mappings are considered.
Proof. We give the arguments for GAV and GLAV mappings (for linear case, see the appendix). For the NP upper bound, consider two OBDA specifications 1 = hT1; M1i and 2 = hT2; M2i, and let q be an IQ. By Theorem 4, 1 j=q 2 if and only if 1 j=? 2 and hT2; M2; Di j= implies hT1; M1; Di j= for all databases D satisfying Condition 3 and for all Boolean IQs obtained by instantiating the variable(s) in q with constant(s) from D.
We already know that it is in NP to test whether 1 j=? 2. For the second property, observe that there are only polynomially many databases satisfying Condition 2, since each corresponds to choosing a mapping assertion m in M2, an atom 2 head (m), and deciding whether or not to identify variables in . For every such database D, we compute (in polynomial time) the set of Boolean IQs obtained by instantiating the IQ q with constants from D for which hT2; M2; gr (head (m))i j= . For every such , we guess a polynomial-size proof that hT1; M1; Di j= . If all of our polynomially many guesses succeed, then the procedure returns yes, and otherwise no. By grouping all of the guesses together, we obtain an NP decision procedure.
The NP lower bound is by reduction from the NP-complete CQ containment problem: given two CQs q1; q2 both having a single answer variable x, we have q1 q2 iff h;; fq2 ! A(x)gi j=A(x) h;; fq1 ! A(x)gi, where A is a concept name that does not appear in either of q1 and q2. tu
Finally, we consider entailment with respect to entire classes of queries. Again, we can show it is sufficient to consider a small number of databases of a particular form. Theorem 7. Let 1 = hT1; M1i and 2 = hT2; M2i be as in Theorem 4. For L 2 fCQ; IQg, 1 j=L 2 if and only if 1 j=? 2 and hT2; M2; Di j= q(a) implies hT1; M1; Di j= q(a) for every q 2 L and every database D that satisfies Condition 3.
We show that testing CQ-entailment is much more difficult than for single CQs.
Both the upper and lower bounds use recent results on KB query inseparability [
Proof. We start with the proof of membership in EXPTIME. Consider OBDA
specifications 1 = hT1; M1i and 2 = hT2; M2i. By Theorem 7, 1 j=CQ 2 if and
only if 1 j=? 2 and hT2; M2; Di j= q(a) implies hT1; M1; Di j= q(a) for
every choice of q(a) and every database D satisfying Condition 3. We know that testing
1 j=? 2 can be done in NP (Theorem 3). To decide whether the second property
holds, we consider each of the (polynomially many) databases satisfying Condition 3.
For every such database D, we generate the two ABoxes AM1;D and AM2;D and the
corresponding KBs K1 = hT1; AM1;Di and K2 = hT2; AM2;Di. We then test whether
it is the case that for every CQ q over sig(K2), K2 j= q(a) implies K1 j= q(a), and we
return no if this is not the case. The preceding check corresponds to the -query
entailment problem for DL-LiteR KBs, which has been recently studied in [
Our lower bound also makes use of the recent work on query inseparability of
DL-LiteR knowledge bases. In [
Our final result shows that IQ-entailment has the same complexity as single IQentailment. The proof proceeds similarly to the proof of Theorem 6.
Theorem 9. IQ-entailment is NP-complete for OBDA specifications based upon DL-LiteR TBoxes and either GAV or GLAV mappings. It is NL-complete if linear mappings are considered. 5
In this paper, we have introduced notions of query-based entailment of OBDA specifications and have analyzed the complexity of checking query-based entailment for different classes of queries and mappings and for TBoxes formulated in DL-LiteR.
The present work constitutes only a first step towards a full analysis of query-based
forms of comparing OBDA specifications, and can be extended in several directions:
– First, it would be interesting to extend the computational analysis of query
entailment to other DLs beyond DL-LiteR. For instance, one interesting question for DLs
with functional or cardinality restrictions concerns the impact of the Unique Name
Assumption on the complexity of (and the techniques for) query entailment.
– Second, other forms of mapping beyond GAV and GLAV could be analyzed. In
particular, we would like to see whether decidability of query entailment is preserved
if we add some restricted form of inequality or negation to the mapping bodies.
– Third, we could introduce a query signature and only test entailment for queries
formulated in the given signature, as has been done for TBox and KB query
inseparability [