Query answering over a database becomes far more difficult if the extensional knowledge in the database is extended by constraints in an ontology. The reason is that a database plus an ontology may have many different models, hence ontology based query answering has to compute the answers w.r.t. to all models and build their intersection (certain answer semantics). But in some cases-when using a lightweight logic like DL-Lite for the representation of the ontology and a restricted query language like unions of conjunctive queries-query answering w.r.t. an ontology can be reduced to model checking. This is formalized by the notion of FOL (first order logic) rewritability: a given query can be rewritten into a FOL query in which the intensional knowledge of the ontology is captured. Though the rewritten queries may become exponentially bigger than the original queries, there exist optimizations [13]. So, FOL rewritability means a benefit. DL-Lite per se [2] is not sufficient for use in scenarios of geographic information processing, as these demand among others the representation and deduction over spatial concepts. Though there exists related work combining spatial and thematic reasoning [4], [15], [6], it is not aimed at FOL rewritability. Hence, there is still a need for investigating combinations of logics that, on the one hand, are sufficiently expressive to fit the representation's needs in geographical information processing and that, on the other hand, allow for computationally feasible (in particular FOL rewritable) satisfiability checking and query answering.
Continuing previous work [7,8], we investigate combinations of logics in the DL-Lite family with different members of the region connection calculus (RCC) family [9], a well-known family of calculi for qualitative spatial reasoning. The DL-Lite logic we are using as thematic part differs from the known members of the DL-Lite family as it also allows for concept conjunctions on the lefthand side of general inclusion axioms. In previous work [8], we focussed on the FOL rewritability aspects for weak combinations of DL-Lite with RCC8; these combinations are weak in so far as they do not allow for the construction of arbitrary RCC8 constraint networks in the intensional part (TBox) of the ontology. In this paper we focus on strong combinations of DL-Lite with the weaker fragments RCC3 and RCC2, and prove that DL-Lite F ,R (RCC3) does not allow for FOL rewritability of satisfiability checking while the weaker DL-Lite F ,R (RCC2) does.
The paper is structured as follows. Section 2 collects technical details on the region connection calculus and the DL-Lite family of description logics. Weak combinations of DL-Lite with the region connection calculus are described in Sect. 3. In Sect. 4, the last section before the conclusion, we consider strong combinations of DL-Lite with weaker fragments of the region connection calculus.
We recapitulate the main logical notation and concepts used in this paper; the region connection calculus and DL-Lite.
We will consider different fragments of the region connection calculus [9] as potential candidates for the spatial logic to be combined with DL-Lite. Randell and colleagues' axiom system [9] is based on a primitive binary relation C intended to denote a connectedness relation which is specified to be reflexive and symmetric. On the basis of C other binary relations between regions which are called base relations are explained. One set of base relations is the set B RCC8 , which is the main component of the most expressive region connection calculus RCC8. The base relations of B RCC8 and their intended meanings are given as follows: B RCC8 = {DC (disconnected), EC (externally connected), EQ (equal), PO (partially overlapping), NTPP (non-tangential proper part), TPP (tangential proper part), NTPPi (inverse of NTPP), TPPi (inverse of TPP)}. We skip the concrete definitions of the base relations by the connectedness relation C (see, e.g., [11, p. 45]), as we-in contrast to the axiom system of Randell and colleagues-consider the following axiom system schema Ax RCCi , which directly specifies the properties of the base relations in B RCCi .
Definition 1 (Axiom system schema Ax RCCi ). For all i ∈ {2, 3, 5, 8} the axiom set Ax RCCi contains the following axioms:
For i ∈ {3, 5, 8} additionally the axiom ∀xEQ(x, x) (reflexivity of EQ) is contained. For i = 2 one has instead the axiom ∀xO(x, x) (reflexivity of O).
In particular, the axioms state the JEPD-property of the base relations (each pair of regions x, y is related over exactly one base relation) and describe the (weak) composition of two base relations (denoted by ;) according to the composition table for RCCi. With the composition of two base relations, in most cases, only indefinite knowledge of spatial configurations follows. The spatial configuration r 1 (x, z) ∨ • • • ∨ r n (x, z) for base relations r j in B RCCi is also written as {r 1 , . . . , r n }(x, z), and the set {r 1 , . . . , r n } is called a general RCCi relation. Let Rel RCCi be the set of all 2 i general RCCi relations. An RCCi (constraint) network consists of assertions of the form {r 1 , . . . , r n }(x, y).
We mention here the composition table for the low resolution logics RCC2 and RCC3. Their base relations are given by the sets B RCC3 = {DR, EQ, ONE} and B RCC2 = {DR, O}, and their weak compositions are defined as shown in Fig. 1 Note that in the definitions of the base relations (of RCC3 and RCC2) we followed the author of [14]. The base relations of the low resolution calculus of [3] are different from those of RCC2; the authors of [3] consider the two base relations DC and {EC, O}. But as we do not deal with the exact definitions of the base relations referring to the connectedness relation C but with the axiom systems referring to the composition table this difference has no effect-the low resolution calculus of [3] has the same trivial composition table as RCC2. For the composition tables of RCC5 and RCC8 have a look at [12, p. 45].
The family of DL-Lite description logics [2] is an appropriate candidate for the thematic component of the envisioned geo-thematic logic as it offers computationally feasible satisfiability checking and query answering over ontologies and data stored in a relational database. More concretely, satisfiability checking and query answering (for unions of conjunctive queries) are first order logic (FOL) rewritable. In this paper, we will mainly deal with a member of the extended DL-Lite family which we termed DL-Lite F ,R , and which allows functional roles, role hierarchies and role inverses as well as the conjunction of basic concepts on the left-hand side of GCIs (general concept inclusions). The syntax is given in Def. 2. The semantics of this logic is defined in the usual way-but imposing the unique name assumption (UNA).
Definition 2 (DL-Lite F ,R ). Let RN be the set of role symbols and P ∈ RN , CN be a set of concept symbols and A ∈ CN , Const be a set of individual constants and a, b
occurs in a functionality axiom, then R and its inverse do not occur on the right-hand side of a role inclusion axiom R 1 R 2 .
FOL rewritability also holds for the logic DL-Lite F ,R which follows from the corresponding FOL rewritability results for the Datalog extension Datalog ± [1]. We assume that the reader is familiar with the notion of FOL queries, conjunctive queries (CQ) and unions of conjunctive queries (UCQ), their semantics and the notion of certain answers cert(Q, A ∪ T ) of a query w.r.t. to the union of a TBox and an ABox T ∪ A [2]. Let DB(A) be the minimal Herbrand model of A. Checking the satisfiability of ontologies is FOL rewritable iff for all TBoxes T there is a boolean FOL query Q T s.t. for all ABoxes A: the ontology T ∪ A is satisfiable iff DB(A) |= Q T . Answering queries from a subclass C of FOL queries w.r.t. to ontologies is FOL rewritable iff for all TBoxes T and queries
. For DL-Lite, FOL-rewritability can be proved w.r.t. to satisfiability as well as w.r.t. answering UCQs [2, Thm 4.14, Thm 5.15]. A crucial part of the proof for FOL rewritability w.r.t. query answering is the perfect rewriting algorithm [2, Fig. 2]. This algorithm works by using positive inclusion axioms of the form A 1 A 2 as rewriting rules from right to left so that for example an atom A 2 (x) occurring in a CQ would produce a new CQ containing A 1 (x) instead of A 2 (x).
In this section, we recapitulate the results concerning a weak coupling of DL-Lite with the most expressive region connection calculus fragment RCC8, which we introduced in [7, 8], and provide an example for its use(fulness). This will give us the opportunity to introduce further concepts that are necessary to understand the following discussions on stronger couplings of DL-Lite with the weaker region connection calculi RCC2 and RCC3.
The combination paradigm follows that of Lutz and Miličič [6] who combine ALC with the RCC8 and, more generally, with ω-admissible concrete domains [6,Def. 5,p. 7]. The combined logic ALC(RCC8) of [6] is well behaved in so far as testing concept subsumption is decidable. As we aim at FOL rewritability we have to be even more careful in choosing the right combination method.
We use an axiom set T ω with corresponding properties of an ω-admissible domain for coupling with DL-Lite because axioms are more appropriate for rewriting investigations. The axiom sets Ax RCCi will instantiate T ω .
We recapitulate the syntax and the semantics of the constructors of [6] that are used for the coupling of the thematic and the spatial domain. A path U (of length at most 2) is defined as l for a fixed attribute l ("has location") or as R • l, the composition of the role symbol R with l. We abbreviate R • l with R in this paper. The usual notion of an interpretation I in our combined logic is slightly modified by using two separate domains ∆ I and (∆ * ) I . All symbols of the theory T ω are interpreted relative to (∆ * ) I . Let r be an RCC-relation of some RCC-fragment. That is, let be given a set of base relations B RCCi and r = {r 1 , . . .
2 it holds that (e * 1 , e * 2 ) ∈ r I }. Now we can define the following combined geo-thematic logic (where a * , b * stand for constants intended to be interpreted by regions):
A(a), R(a, b), l(a, a * ), r(a * , b * ) *) Restriction: If (funct R) ∈ T , then R and R − do not occur on the righthand side of a role inclusion axiom or in a concept of the form ∃U 1 , U 2 .r.
As satisfiability checking of RCC8 constraint networks is NP-complete, there is only a chance to reach FOL rewritability if we assume within the ABox a constraint network which is consistent and complete, i.e., only base relations are allowed as labels; in this case the ABox is called spatially complete. It seems to us that for cadastral maps or maps containing areas of administration one can assume pretty safely (almost) spatial completeness. The coupling with RCC8 is so weak that FOL rewritability of satisfiability follows.
Proposition 1. Checking the satisfiability of DL − Lite F ,R (RCC8) ontologies that have a spatially complete ABox is FOL rewritable.
The FOL rewritability holds also for query rewriting w.r.t. to a restricted class of treelike queries (termed GCQ + ). The result is achieved by an adapted perfect rewriting algorithm PerfectRef [2, Fig. 13].
Theorem 1. Answering GCQ + -queries w.r.t. DL − Lite F ,R (RCC8) ontologies that have a spatially complete ABox is FOL rewritable. DL-Lite F ,R (RCC8) as well as the logics introduced below are suited for use in scenarios such as that of an engineering bureau planning additional parks in a city [7]. Assume, the bureau has stored geographical data in some database and declares relevant concepts in the TBox: Park+Lake Park; Park4Playing Park; Park+Lake ∃hasLake•l, l.TPP; Park4Playing ∃hasPlAr•l, l.TPP. The ABox A is derived virtually by mappings from geographical data in a database. In particular, assume that {Park+Lake(a), Park4Playing(a)} ⊆ A. According to A, the object a is a park with a lake and a park with a playing area but its spatial extension is not known. Now, the engineering bureau asks for all parks with lakes and playing areas such that the playing area is not contained as island in the lake. This can be formalized by the GCQ + query: Q =Park(x)∧∃hasLake• l, hasPlAr • l.(B RCC8 \ {NTPP})(x). Using the composition entry TPP; TPPi = {DC, EC, PO, TPP, TPPi, EQ} ⊆ B RCC8 \ {NTPP}, the reformulation algorithm produces a UCQ that contains the following CQ: Q = (∃hasLake • l, l.TPP)(x) ∧ (∃l, hasPlAr • l.TPPi)(x). Rewriting ∃l, hasPlAr • l.TPPi to ∃hasPlAr • l, l.TPP in combination with the rewriting rule for A 1 A 2 we get another CQ Q = Park+Lake(x) ∧ Park4Playing(x). Now, Q captures (as desired) the object a.
Another way of reaching FOL rewritability for combinations of DL-Lite with RCC is weakening the expressivity of the spatial component. Hence, one may ask whether a combination with the calculus RCC3 or RCC2 [15], both fragments with weak expressibility, allows for weak FOL rewritability w.r.t. satisfiability checks (and query answering). Their potential use as logics for approximating [5] ontologies in more expressible combined logics like ALC(RCC8) makes the investigation valuable. The logics DL-Lite ,+ F ,R (RCC2) and DL-Lite ,+ F ,R (RCC3) are defined as follows ('+' indicates the strong combination):
then R and R − do not occur on the righthand side of a role inclusion axiom.
For RCC3 the strong combination with DL-Lite F ,R leads to non-FOL rewritability. The reason lies in the fact that testing the satisfiability of RCC3 is not in the complexity class AC 0 as shown by the following lemma.
Lemma 1. Checking satisfiability of RCC3 networks is Logspace hard.
Proof. As is known, the reachability problem in symmetric (undirected) graphs is logspace complete [10]-where graph reachability asks whether for nodes s, t in G there is a path between s and t. By reducing this problem to the satisfiability test for RCC3 networks we will have shown that the latter problem is Logspace hard itself. So let be given a (symmetric) graph G = (V, E) and nodes s, t ∈ V . We define the network N in the following way (see Figure 2): Let V = {v 1 , . . . , v n } be an enumeration of the nodes of G; w.l.o.g. let s = v 1 and t = v n and let B = B RCC3 . Nodes of N are given by V ∪ {a} where a / ∈ V . Labelled edges of N are given by: s{DR}a; t{ONE}a; v i {B}a for all i = 1, n; v i {EQ}v j if E(v i , v j ); v i {B}v j if ¬E(v i , v j ). Now we show that the network N is satisfiable iff s and t are connected in G. Assume that s and t are connected; then there is an EQ-path in N between them, hence s{EQ}t follows. But this contradicts s{DR}a and t{ONE}a. Now assume that s and t are not connected; then there is no path consisting only of EQ-labels between s and t. The graph G consists of at least 2 components, and s, t are in different components. We define a consistent configuration as follows: For all nodes v, v in the component in which s is contained, let v{DR}a and v{EQ}v . For all nodes v, v in the component of t let v{ONE}a and v{EQ}v . For all nodes v, v in the other components let v{DR}a and v{EQ}v . For all nodes v, v which have not a label yet, let v{DR}v . (Two remarks : 1) EQ-edges for edges E(v i , v j ) in G with j > i + 1 are not shown in Fig. 2. 2) We inserted edges labelled B for better illustrations. But these are not needed.)
This lemma immediately entails the fact that satisfiability checking for ontologies over the logic DL-Lite ,+ F ,R (RCC3) is not FOL rewritable. This problem does not vanish if we presuppose that the ABox A is spatially complete-as shown by the following proposition.
F ,R (RCC3) with spatially complete ABoxes is not FOL rewritable.
Proof. We construct a generic TBox T g that allows one to encode any RCC3 constraint network so that checking the consistency of RCC3 constraint networks is reducible to a satisfiability check of this TBox and a spatially complete ABox. Let for every r ∈ Rel RCC3 be given role symbols R 1 r , R 2 r . The generic TBox T g has for every r ∈ Rel RCC3 a concept symbol A r and a corresponding axiom with the content that all instances of A r have paths over the abstract features R 1 resp. R 2 to regions that are r-related.
Now, let N be an arbitrary RCC3 constraint network which has to be tested for relational consistency. Let A N be an ABox such that for every r(a, b) in N three new constants are introduced: x ab , x a , x b .
The construction entails:
If the data complexity of the satisfiability check for DL-Lite ,+ F ,R (RCC3)ontologies were in AC 0 , then the consistency of constraint networks could be tested in AC 0 , too. (Note that T g is a fixed TBox.) But checking the consistency of RCC3 constraint networks is Logspace-hard and AC 0 Logspace.
As a corollary to this proposition we get the assertion that strong combinations of RCC5 and RCC8 into DL-Lite ,+ F ,R (RCC5) and DL-Lite ,+ F ,R (RCC8), respectively-which are defined in the same manner as in Definition 4-do not allow for FOL rewritability of satisfiability checking.
The low resolution calculus RCC2 is quite more inexpressive than RCC3 due to the fact that the composition table does not allow for the propagation But in combination with functionality axioms of the TBox one could have the problem that the ABox may lead to identifications of regions. The identified regions are not allowed to have edges labelled O, DR resp. to the same region. Though this can be tested, the problem arises when a chain of regions is identified by the TBox and the ABox, because we do not know the length of the chain in advance. More formally: In addition to RCC2 constraint-network assertions we allow identity assertions v = w for regions v, w. As we can assume that all nodes in a RCC2 network are connected by an edge labelled O, DR or B RCC2 we use a more intuitive formalism where, for every assertion v = w, the label of the edge between v and w is marked with an =; e.g., an edge between v, w with label DR = stands for DR(v, w) ∧ v = w. We call such a network an =-marked RCC2 network (a RCC = 2 network for short). Let B = B RCC2 in the following. Proposition 4. An RCC = 2 constraint network N is unsatisfiable iff 1. N contains DR(v, v) or DR = (v, v) for some node v; or 2. N contains DR = (v, w); or 3. N contains a cycle in which there is DR(v, w) and in which there is a path from v to w such that every label on the path is B = or O = ; or 4. N contains a cycle in which there is DR(v, w) and in which there is a path from v to w s.t. every label on the path is B = or O = except one which is O.
Proof. Sufficiency of the condition for unsatisfiability is clear. The proof for necessity is done by induction on the number of =-marked labels. So let be given a RCC = network N . We may assume, that the network has for every pair of nodes exactly one labelled edge between; we assume the edges to be undirected as all relations are symmetric.
Base case: Assume that none of the four conditions hold. As there are no marked labels, then N unsatisfiability can occur only, if N contains DR(v, v) for some node v (first condition) or DR(v, w) and O(v, w) (fourth condition). But these cases are excluded by assumption.
Induction step: Let N contain n marked labelled edges and assume that for all networks N with n−1 marked labelled edges unsatisfiability of N implies one of the conditions. Now, assume that for N no one of the four conditions holds. We have to show that N is satisfiable. Take an arbitrary =-marked labelled edge between nodes v, w. The label λ of this edge is either O = or B = . We define a new network N which results as a contraction from N by identifying v and w to the node z. For N we may assume again that it contains for every pair of nodes exactly one labelled edge: If in N we have r 1 (v, k) and r 2 (w, k), then the edge between z and k in N results as r 1 ∩ r 2 and is =-marked iff r 1 or r 2 is marked. Clearly r 1 ∩ r 2 is not empty, as otherwise we would have a contradiction to the fact that N does not fulfill conditions 3 and 4. Clearly N is satisfiable iff N is satisfiable. Assume to the contrary that N is unsatisfiable. Hence, one of the four conditions holds for N : 1) Assume N contains DR(v , v ) or DR = (v , v ) for some node v . If v is not z, then also DR(v , v ) ∈ N resp. DR = (v , v ) ∈ Ncontradicting the fact that N does not fulfill condition 1. Otherwise v = z, but this cannot be the case either, as there are no self-loops DR(v, v), DR = (v, v), DR(w, w), DR = (w, w) in N nor DR(v, w) or DR(v, w). 2) Assume N contains DR = (v , w ). If neither v nor w is z, this contradicts the fact that N does not fulfill the 2. condition. Otherwise v = w = z, leading to a contradiction with the fact that N does not fulfill condition 1. 3) Assume N contains a cycle in which there is DR(v , w ) and there is a path from v to w such that every label on the path is B = or O = . The case that the path does not contain z immediately leads to a contradiction. Otherwise, the path extends to a path in N fulfilling the 3. condition-contradiction. Similarly, if N fulfills condition 4, the verifying path can be extended to a path in N fulfilling condition 4-contradiction.
Proposition 4 shows that adding identity assertions to an RCC2 network may require checking the existence of identity chains of arbitrary length. Hence, in principle it is possible that the functional roles used in DL-Lite ,+ F ,R (RCC2) may lead to identity chains. But as we want to show in the following proposition, this cannot be the case: The identity paths induced by functionalities in DL-Lite ,+ F ,R (RCC2) can have only a maximal length of one.
Proposition 5. Satisfiability checking of ontologies in DL-Lite ,+ F ,R (RCC2) is FOL rewritable.
We give a proof sketch. The idea is to find concepts that are unsatisfiable according to the TBox (this amounts to constructing the negative closure as in the proofs for pure DL-Lite [2, Def. 4.7, p. 292]); these are formulated as boolean queries, and the (finite) disjunctions of these queries is answered over the ABox; e.g., if A 1 ¬A 2 is in the TBox, then the query would contain ∃x(A 1 (x)∧A 2 (x)) as disjunct. The introduction of concepts of the form ∃U 1 , U 2 .r enlarges the potential conflicts of a TBox T with an ABox A. So in addition to the FOL queries that result from the negative closure of the TBox, we have to find queries for the potential conflicts in the four conditions of Proposition 4. The resulting conjunctive queries have further to be fed into a perfect rewriting algorithm like PerfectRef for pure DL-Lite [2] in order to capture the implications of the TBox.
Concerning the first two conditions we have to deal with axioms of the form B ∃l, l.DR. If this axiom occurs in the TBox T , then one has to produce the CQ ∃x.B(x). Similarly, if {B ∃ R, R.DR, (funct R)} ⊆ T , then the CQ ∃x.B(x) has to be added. Also if {B ∃ R1 , R2 .DR, (funct R 1 , funct R 2 )} ⊆ T , then we may get a conflict of the first kind and hence we have to add a CQ ∃x, y[B(x) ∧ R 1 (x, y) ∧ R 2 (x, y)]. Concerning the third and fourth condition we note that this can be only the case if the =-marked paths have maximal length one. Otherwise we already have a contradiction of the ABox with the functionality assertions in the TBox. Hence, one considers only the case of pairs of TBox axioms of the general form A ∃ R1 , R2 .DR and B ∃ R3 , R4 .O with (funct R 1 , R 2 , R 3 , R 4 ). In this case we feed also into the PerfectRef algorithm the CQ ∃x, y, z, w[A(x) ∧ B(y) ∧ R 1 (x, z) ∧ R 3 (y, z) ∧ R 2 (x, w) ∧ R 4 (y, w)].
As recapitulated in this paper, combining DL-Lite with expressive fragments of the region calculus like RCC8 into logics that preserve the property of FOL rewritability is possible if the coupling is weak: Constraints of the RCC8 network contained in the ABox are not transported over to the implicitly constructed constraint network resulting from the constructors of the form ∃U 1 , U 2 .r. In this paper we mainly dealt with strong combinations for weaker calculi like RCC2 or RCC3. As we have shown by a reduction proof, a strong combination with RCC3 destroys the FOL rewritability of satisfiability checking. The reason is that checking the satisfiability of RCC3 networks needs to test for reachability along EQ paths, which can be reproduced by the TBox. For the low resolution calculus RCC2, FOL rewritability of satisfiability checking is provable-though checking the satisfiability of RCC2 networks with additional identity assertions is at least as hard as checking RCC3 networks. We plan to investigate whether DL-Lite ,+ F ,R (RCC2) and DL-Lite F ,R (RCC8) can be used for approximationfollowing the complete but not necessarily correct approximation method of [5]. Moreover we want to check whether DL-Lite ,+ F ,R (RCC2) allows for FOL rewritability of query answering w.r.t. unions of conjunctive queries.