DL-LITER in the Light of Propositional Logic for Decentralized Data Management

1 Introduction

Ontologies are the backbone of the Semantic Web by providing a conceptual view of data and services made available worldwide through the Web. Description logics are the formal foundations of the OWL ontology web language recommended by W3C. They cover a broad spectrum of logical languages for which reasoning is decidable with a computational complexity varying depending on the set of constructors allowed in the language. Answering conjunctive queries over ontologies is a reasoning problem of major interest for the Semantic Web the associated decision problem of which is not reducible to (un)satisfiability checking. The DL-Lite family [Calvanese et al., 2007] has been specially designed for guaranteeing query answering to be polynomial in data complexity. This is achieved by a query reformulation approach which (1) computes the most general conjunctive queries which, together with the axioms in the Tbox, entail the initial query and (2) evaluates each of those query reformulations against the Abox seen as a relational database. Such an approach has the practical interest that it makes possible to use an SQL engine for the second step, thus taking advantage of well-established query optimization strategies supported by standard relational data management systems. The reformulation step is necessary for guaranteeing the completeness of the answers but is a reasoning step independent of the data. A major result in [Calvanese et al., 2007] is that DL-LITER is one of the maximal fragments of the DL-Lite family supporting tractable query answering over large amounts of data. DL-LITER is a M.-C. Rousset LIG: Univ. of Grenoble, CNRS, and INRIA

Marie-Christine.Rousset@imag.fr

fragment of OWL-DL 1 which extends RDFS 2 with interesting contructors such as inverse roles and disjointness between concepts and between roles. RDFS is the first standard of the W3C concerning the Semantic Web. Its use for associating semantic metadata to web resources is rapidly spreading at a large scale, as shown by the Billion Triple Track of the Semantic Web Challenge (http://challenge.semanticweb.org/).

For scalability and robustness but also for data protection, it is important to investigate a fully decentralized model of the Semantic Web, viewed as a huge peer data management system (PDMS). Each peer may have its own local ontology for describing its data, and interacts with some other peers by establishing mappings with their ontologies. The result is a network of peers with no centralized knowledge and thus no global control on the data and knowledge distributed over the web.

The contribution of this paper is a decentralized data model and associated algorithms for data management in the Semantic Web based on distributed DL-LITER. We revisit the centralized current approach of [Calvanese et al., 2007] for data consistency checking and query answering by reformulation in order to design corresponding decentralized algorithms. We also extend the current work on DL-Lite by providing both a centralized and a decentralized algorithm for rewriting queries using views when queries and views are conjunctive queries over DL-LITER ontologies.

Our approach relies on reducing the above data management problems for DL-LITER into decentralized reasoning in distributed propositional logic, in order to deploy DL-LITER PDMSs on top of the SomeWhere platform. SomeWhere is a propositional P2P inference system for which experiments have demonstrated the scalability [Adjiman et al., 2006].

The paper is organized as follows. In Section 2, we present the distributed DL-LITER data model which is based on bridging distributed DL-LITER ontologieswithmappings. In Section 3, we provide decentralized algorithms for query answering by reformulation and for data consistency checking. In Section 4, we investigate the problem of query rewriting using views in DL-LITER in the centralized and decentralized cases. Finally, we conclude with a short discussion on related work in Section 5.

1 http://www.w3.org/2004/OWL/

2 http://www.w3.org/TR/rdf-schema/

2 Distributed DL-LITER

DL-LITER concepts and roles are of the following form: B →A | ∃R, C →B | ¬B, R→P | P -, E →R | ¬R where A denotes an atomic concept, P an atomic role, and P - the inverse of P. B denotes a basic concept (i.e., an atomic concept A or an unqualified existential quantification on a basic role ∃R) and R a basic role (i.e., an atomic role P or its inverse P -). Finally, C denotes a general concept (i.e., a basic concept or its negation) and E a general role (i.e., a basic role or its negation).

An interpretation I = (ΔI , .I ) consists of a nonempty interpretation domainΔI and an interpretation function .I that assigns a subset of ΔI to each atomic concept, and a binary relation over ΔI to each atomic role. The semantics of non atomic concepts and roles is defined as follows:

An interpretation I is a model of a concept C (resp. a role E) if CI ̸= ∅ (resp. EI ̸= ∅).

DL-LITER knowledge bases. A DL-LITER knowledge base (KB) is made of a Tbox representing a conceptual view of the domain of interest (i.e., an ontology), and either an Abox (a local set of facts) [Calvanese et al., 2007] or view extensions (predefined queries over the Tbox together with their answers) [Calvanese et al., 2008b] for representing the data.

A DL-LITER Tbox is a finite set of inclusion statements of the form B ⊑ C and/or R ⊑ E. General concepts or roles are only allowed on the right hand side of inclusion statements whereas only basic concepts or roles may occur on the left hand side of inclusion statements. Inclusions of the form B1 ⊑ B2 or of the form R1 ⊑ R2 are called positive inclusions (PIs), whereas inclusions of the formB1 ⊑ ¬B2 or of the formR1 ⊑ ¬R2 are called negative inclusions (NIs). An interpretation I = (ΔI , .I ) is a model of an inclusion B ⊑ C (resp. R ⊑ E) if BI ⊆ CI (resp. RI ⊆ EI ). It is a model of a Tbox if it satisfies all of its inclusion statements. A Tbox T logically entails an inclusion statement α, written T |= α, if every model of T is a model of α.

A DL-LITER Abox consists of a finite set of membership assertions on atomic concepts and roles of the form A(a) and P (a, b), stating respectively that a is an instance of A and that the pair of constants (a, b) is an instance of P. The interpretation function of an interpretation I = (ΔI , .I ) is extended to constants by assigning to each constant a a distinct object aI ∈ ΔI (i.e., the so called unique name assumption holds). An interpretation I is a model of the membership assertion A(a) (resp. P(a, b)) if aI ∈ AI (resp., (aI , bI ) ∈ P I ). It is a model of an Abox if it satisfies all of its assertions.

When the extensional knowledge is modeled using view extensions, the KB is of the form 〈T , V, E〉 such that E is a set of facts of the form v(¯ t) where v is a view of V.

Queries and views over a DL-LITER KB. We consider (unions of) conjunctive queries of the form q(¯x) : ∃¯ y conj(¯x, ¯ y) where conj(¯x, ¯ y) is a conjunction of atoms, the variables of which are only the free variables ¯ x and the existential variables ¯ y, and the predicates of which are either atomic concepts or roles of the KB. The arity of a query is the number of its free variables, e.g., 0 for a boolean query.

Given an interpretation I = (ΔI , .I ), the semantics qI of a boolean query q is defined as true if [∃¯ y conj(∅, ¯ y)]I = true, and false otherwise, while the semantics qI of a query q of arity n ≥ 1 is the relation of arity n defined on (ΔI ) as follows: qI = {¯ e ∈ (ΔI )n | [∃¯ y conj(¯ e, ¯ y)]I = true}.

A view v is defined by a query v(¯x) : ∃¯ y conj(¯x, ¯ y), and has an extension E(v) which is a set of facts of the form v(¯ t).

Following the open world assumption, we adopt the sound semantics, i.e., for every interpretation I for each v(¯ t) ∈ E (v), ¯ tI ∈ vI .

A model of a KB K = 〈T , A〉 (resp. K = 〈T , V, E〉) is an interpretation I that is a model of both T and A (resp. of T ,

V and E). A KB K is consistent if it has at least one model. K logically entails a membership assertion β, written K |=

β, if every model of K is a model of β.

(Certain) answers of a query over a DL-LITER KB. For defining the answers of a query over a KB, it is needed to distinguish the case where the extensions of the query predicates are given in an Abox, from the case where they just can be (partially) inferred from extensions of views. In the latter case, they are called the certain answers.

The answer set of a non boolean query q over K = 〈T , A〉 is defined as: ans(q,K) = {¯ t ∈ C n | K |= q(¯ t)} where C is the set of the constants appearing in the KB, and q(¯ t) is the closed formula obtained by replacing in the query definition the free variables in ¯x by the constants in ¯ t.

The certain answer set of a non boolean query q over K = 〈T , V, E〉, is defined as: cert(q, K) = {¯ t ∈ C n | K |= q(¯ t)}. By convention, the (certain) answer set of a boolean query

is {()}, () is the empty tuple, if K |= q(), and ∅ otherwise.

DL-LITER PDMSs ADL-LITER PDMSS is a set of peers {Pi}i=1..n, where the index i models the identifier of the peer Pi (e.g., its IP address). Each peer Pi manages its own DL-LITER KB Ki written in terms of its own vocabulary, i.e., atomic concepts and roles. We will note Ai (resp. Pi) the atomic concept A (resp. the atomic role P) of Pi.

Mappings are here inclusion assertions (PIs and/or NIs) involving concepts and/or roles of two different peers. For simplifying the presentation, we consider that mappings are in both KBs.

From a logical viewpoint, a PDMS S = {Pi}i=1..n is a standard (yet distributed) DL-LITER KB K = ⋃ni=1 Ki, i.e., in contrast with other approaches ([Calvanese et al., 2008a], [Franconi et al., 2004], [Serafini et al., 2005]) we adopt a standard logical semantics for the mappings.

3 Decentralized Query Answering

We first recall the Answer, Consistent, and PerfectRef algorithms of [Calvanese et al., 2007] that are used for answering queries over a DL-LITER KB K = 〈T ,A〉 in the centralized case (Section 3.1). Then we provide their decentralized versions (in Sections 3.3 and 3.4). They are based on the propositional encoding summarized in Section 3.2 and the use of the DeCa algorithm [Adjiman et al., 2006] which is the decentralized algorithm for propositional reasoning implemented in the SomeWhere platform.

3.1 Existing DL-LITER algorithms: reminder

Given a union of conjunctive queries Q over a KB K = 〈T , A〉, Answer (Algorithm 1) first checks whether K is inconsistent (line 1). In that case, it returns all the tuples of the arity of Q that can be generated from the constants occurring in A (line 2). Otherwise, it gets ans(Q,K) by evaluating against A considered as a relational database the union of conjunctive queries obtained by reformulation of Q (line 3).

Algorithm 1: The original Answer algorithm

Answer(Q, K)

Input: a union of conjunctive queries Q and a KB K = 〈T , A〉 Output: ans(Q,K) (1) if not Consistent(K) (2) return Alltup(Q,K)

1. else return (Sqi∈Q PerfectRef(qi, T ))db(A)

Consistent (Algorithm 2) builds a boolean query qunsat that checks that the DL-LITER formulae that must be disjoint, according to the intentional knowledge modeled in T , indeed have disjoint instances in A. qunsat is obtained as the union of the first-order logic (FOL) translations of the NI-closure of T , denoted cln(T ), i.e., the set of all the NIs entailed by T . The FOL translations of NIs are defined by:

δ(B1 ⊑ ¬B2) = ∃x γ1(x) ∧ γ2(x) such that γi(x) = Ai(x) if Bi = Ai γi(x) = ∃yi Pi(x, yi) if Bi = ∃Pi γi(x) = ∃yi Pi(yi, x) if Bi = ∃P - i δ(R1 ⊑ ¬R2) = ∃x, y ρ1(x, y) ∧ ρ2(x, y) such that ρi(x, y) = Pi(x, y) if Ri = Pi ρi(x, y) = Pi(y, x) if Ri = P - i Algorithm 2: The original Consistent algorithm Consistent(K) Input: a KB K = 〈T , A〉 Output: true if K is satisfiable, false otherwise (1) qunsat = ⊥ (i.e., qunsat is false) (2) foreach α ∈ cln(T ) (3) qunsat = qunsat ∨ δ(α) (4) if qdb(A) unsat = ∅ (5) return true

(6) else return false

Finally, PerfectRef (Algorithm 3) reformulates each conjunctive query q in Q by using the PIs in T as rewriting rules. PIs are seen as logical rules that can be applied in backward-chaining to query atoms in order to expand them. More specifically, a PI I is applicable to an atom A(x) of a query if I has A in its right-hand side, and a PI I is applicable to an atom P(x1, x2) of a query if (i) x2 = and the right-hand side of I is ∃P; or (ii) x1 = and the right-hand side of I is ∃P -; or (iii) I is a role inclusion assertion and its right-hand side is either P or P -. Note that denotes here an unbounded existential variable of a query.

The following definition (Definition 32 from [Calvanese et al., 2007]) defines the result gr(g, I) of the (backward) application of the PI I to the atom g, which is the core of PerfectRef (loop (a), lines 5 to 7).

Definition 1 (Backward application of a PI to an atom)

Let I be an inclusion assertion that is applicable to the atom g. Then, gr(g, I) is the atom defined as follows:

- if g = A(x) and I = A1 ⊑ A, then gr(g, I) = A1(x)

• if g = A(x) and I = ∃P ⊑ A, then gr(g, I) = P(x, )

- if g = A(x) and I = ∃P - ⊑ A, then gr(g, I) = P( , x) - if g = P(x, ) and I = A ⊑ ∃P, then gr(g, I) = A(x) - if g = P(x, ) and I = ∃P1 ⊑ ∃P, then gr(g, I) = P1(x, ) - if g = P(x, ) and I = ∃P - 1 ⊑ ∃P, then gr(g, I) = P1( , x) - if g = P( , x) and I = A ⊑ ∃P -, then gr(g, I) = A(x) - if g = P( , x) and I = ∃P1 ⊑ ∃P -, then gr(g, I) = P1(x, ) - if g = P( , x) and I = ∃P - - if g = P(x1, x2) and either I = P1 ⊑ P or I = P - 1 ⊑ P - then gr(g, I) = P1(x1, x2)

1 ⊑ ∃P -, then gr(g, I) = P1( , x) - if g = P(x1, x2) and either I = P1 ⊑ P - or I = P - 1 ⊑ P then gr(g, I) = P1(x2, x1)

The subtle point of PerfectRef is the need of simplifying the produced reformulations (loop (b), lines 8 to 10), so that some PIs that were not applicable to a reformulation become applicable to its simplifications. A simplification amounts to unify two atoms of a reformulation using their most general unifier (using reduce, line 10) and then to switch the possibly new unbounded existential variables to (using τ, line 10).

Algorithm 3: The original PerfectRef algorithm

PerfectRef(q, T )

Input: a conjunctive query q and a Tbox T Output: a union of conjunctive queries (1) PR := {q} (2) repeat (3) PR′ := PR (4) foreach q ∈ PR′ (5) (a) foreach g ∈ q (6) if I is applicable to g (7) PR := PR ∪ {q[g/gr(g, I)]} (8) (b) foreach g1, g2 ∈ q (9) if g1 and g2 unify (10) PR := PR∪ {τ(reduce(q, g1, g2))} (11) until PR′ = PR

3.2 Propositional encoding of a DL-LITER Tbox

The propositional encoding of a DL-LITER Tbox T , denoted Φ(T ), is the formula of propositional logic (PL) that corresponds to the union of the PL encoding of every inclusion assersion I of T : Φ(T ) = ⋃I∈T Φ(I).

The PL encoding of a concept inclusion B ⊑ C, denoted Φ(B ⊑ C) is inductively defined by {Φ(B) ⇒ Φ(C)} where Φ(B) = A when B = A, Φ(B) = P ∃ when B = ∃P, Φ(B) = P ∃- when B = ∃P -, Φ(C) = Φ(B) when C = B, and Φ(C) = ¬Φ(B) when C = ¬B.

The PL encoding of a role inclusion R ⊑ E, denoted Φ(R ⊑ E), is defined as follows:

Φ(P ⊑ Q)={P ⇒ Q, P - ⇒ Q-, P ∃ ⇒ Q∃ , P ∃- ⇒ Q∃- } Φ(P - ⊑ Q)={P - ⇒ Q, P ⇒ Q-, P ∃- ⇒ Q∃, P ∃ ⇒ Q∃- } Φ(P ⊑ Q-)={P ⇒ Q-, P - ⇒ Q, P ∃ ⇒ Q∃- , P ∃- ⇒ Q∃ } Φ(P - ⊑ Q-)={P - ⇒ Q-, P ⇒ Q, P ∃ ⇒ Q∃, P ∃- ⇒ Q∃- } Φ(P ⊑ ¬Q)={P ⇒ ¬Q, P - ⇒ ¬Q-} Φ(P - ⊑ ¬Q)={P - ⇒ ¬Q, P ⇒ ¬Q-} Φ(P ⊑ ¬Q-)={P ⇒ ¬Q-, P - ⇒ ¬Q} Φ(P - ⊑ ¬Q-)={P - ⇒ ¬Q-, P ⇒ ¬Q} Note also that in the following Φ(E) = Φ(R) when E = R, Φ(E) = ¬Φ(R) when E = ¬R, Φ(R) = P when R = P , and Φ(R) = P - when R = P -.

The PL encoding of the distributed Tbox ⋃ni=1 Ti of a DL-LITER PDMS is the distributed propositional theory ⋃ni=1 Φ(Ti) obtained by the encoding of each local Tbox Ti.

DECA is a message-based algorithm implemented in the SomeWhere platform ([Adjiman et al., 2006]) which computes in a decentralized manner the logical consequences of propositional clausal theories distributed in a P2P system. More precisely, by a copy of DECA running locally on each peer and transmitting forth and back messages conveying literals and clauses, DeCAi (li) (denoting DECA running on the peer Pi and triggered with an input literal li of the Pi vocabulary) produces the set of all the proper prime implicates of li w.r.t. the distributed theory ⋃ni=1 Φ(Ti), i.e., the set of prime implicates of {li} ∪ ⋃ni=1 Φ(Ti), which are not implicates of ⋃ni=1 Φ(Ti) alone.

3.3 Decentralized Consistency Checking

Our approach relies on decentralizing the computation of the NI-closure of a distributed Tbox ⋃ni=1 Ti of a DL-LITER PDMS without empty roles (the Tbox does not entail a NI P ⊑ ¬P) by exploiting a property transfer of the propositional encoding (Theorem 1) and then by using DECA. The subtle point is that in a decentralized setting, we have to launch the computation of the NI-closure from each peer and thus possibly start from local PIs and NIs that could lead to the derivation of new NIs by interacting with NIs and PIs of other peers. For doing so, we define (Definition 2) and compute with DECA the NI-closure of a peer w.r.t a PDMS without empty roles.

Theorem 1 (NI-entailment reduced to PL entailment)

The proof is by induction on the number of rules defining the NI-closure (Definition 9 in [Calvanese et al., 2007]) used for producing X ⊑ ¬Y , for the if direction, and on the smallest length of the resolution proof for producing Φ(X) ⇒ Φ(¬Y ) for the converse direction.

Definition 2 (NI-closure of a peer w.r.t. a PDMS) Let T = ⋃ni=1 Ti be the distributed Tbox of a DL-LITER PDMS S = {Pi}i=1..n without empty roles. The NI-closure of Pi w.r.t. S, denoted cln(Pi), is obtained from Φ(T ) using DECA as follows:

• for every PI Z ⊑ Y ∈ Ti such that Z is in the vocabulary of Pi and Y in that of Pj (j may be i), Z ⊑ ¬X ∈ cln(Pi) for any ¬Φ(X) ∈ DeCAj (Φ(Y )).
• for every NI Z ⊑ ¬Y ∈ Ti
• if Z is in the vocabulary of Pi and Y in that of Pj (j may be i), Z ⊑ ¬X ∈ cln(Pi) for any ¬Φ(X) ∈ DeCAj (¬Φ(Y ))
• if Y is in the vocabulary of Pi and Z is in that of Pj (j may be i), X ⊑ ¬Y ∈ cln(Pi) for any ¬Φ(X) ∈ DeCAj (¬Φ(Z)).

The decentralized version of the original Consistent algorithm, denoted Consistenti when running on peer Pi, is simply obtained by replacing foreach α ∈ cln(T ) in Line 2 of Algorithm 2 by foreach α ∈ cln(Pi), and where each conjunctive query of qunsat does not have to be evaluated by Pi against the (unknown) global Abox of the whole PDMS. Indeed, by construction of qunsat, each of its conjunctive queries has two conjuncts, one fromPi and another fromPj (j may be i), the latter providing in its atomic concept or role the identifier j of the peer to contact for the evaluation.

Theorem 2 states the correctness of locally running Consistenti on each peer Pi for global consistency checking of a PDMS without empty roles.

Theorem 2 (Correctness of PDMS consistency checking) Let S = {Pi}i=1..n be a DL-LITER PDMS without empty roles. S is consistent iff Consistenti returns true for every i = 1..n.

The proof relies first on Theorem 1 showing the equivalence between logical entailement from a Tbox of a NI with entailment in PL of the corresponding propositional encoding. Then, both Lemma 12 in [Calvanese et al., 2007] and the completeness of DECA(proved in [Adjiman et al., 2006]) ensure that cln(Pi) defined in Definition 2 contains all the NIs entailed by the PDMS and involving a concept or role in the vocabulary of the peer Pi. Finally, it is easy to see that by running Consistenti for every peer Pi of the PDMS, we obtain all the NIs entailed by the PDMS. Therefore Theorem 15 and Lemma 16 in [Calvanese et al., 2007] ensure that consistency checking can be made by evaluating the union of conjunctive queries in qunsat against the relevant part of the Abox. It is exactly what running Consistenti on all the peers in the PDMS does in a decentralized manner.

3.4 Decentralized Query Reformulation

Our approach relies on the propositional encoding and the use of DECA for decentralizing the backward-closure w.r.t. the PIs of each atom in the query. Definition 3 defines the backward-closure of an atom w.r.t. the PIs as the iteration of the one-step backward application of PIs (Definition 1). Proposition 1 states the termination of this iterative process.

Definition 3 (Backward-closure of an atomw.r.t. PIs) Let PI be a set of PIs, g an atom, and A a set of atoms. We define the backward-closure of g w.r.t. PI as cl gr(g, PI) = ⋃i≥1 cl gri ({g}, PI) where cl gri ({g}, PI) is recursively defined as follows:

• cl gr1 (A, PI) = {gr(g, I) | g ∈ A, I ∈ PI and I is applicable to g}
• cl gri+1 (A, PI) = cl gr1 (cl gri (A, PI), PI)

Proposition 1 (Termination of backward-closure w.r.t. PIs) The backward-closure of an atom w.r.t. a set of PIs is finite, i.e., there exists a constant n such that cl gr(g, PI) = ⋃ni=1 cl gri ({g}, PI).

The proof corresponds to the termination proof of PerfectRef (Lemma 34 in [Calvanese et al., 2007]).

Theorem 3 is the equivalent for the PIs of the transfer property of the propositional encoding for the NIs stated in Theorem 1. Its proof is also by induction (number of one-step applications of a PI and smallest length of resolution proofs).

Theorem 3 (Backward-closure reduced to PL entailment)

Let T be a DL-LITER Tbox the PIs of which form the set PI. Let g, g′ be atoms, and V1, V2 propositional variables. g′ ∈ cl gr(g, PI) iff Φ(T ) ∪ {¬V1} |= ¬V2 where:

- g = A(x), g′ = A′ (x), V1 = A, and V2 = A′ ; - g = A(x), g′ = P(x, ), V1 = A, and V2 = P ∃ ; - g = A(x), g′ = P( , x), V1 = A, and V2 = P ∃- ; - g = P(x, y), g′ = Q(x, y), V1 = P , and V2 = Q; - g = P(x, y), g′ = Q(y, x), V1 = P , and V2 = Q-; - g = P(x, ), g′ = A(x), V1 = P ∃, and V2 = A; - g = P(x, ), g′ =Q(x, ), V1 = P ∃, and V2 =Q∃ ; - g = P(x, ), g′ = Q( , x), V1 = P ∃, and V2 = Q∃- ; - g = P( , x), g′ = A(x), V1 = P ∃- , and V2 = A; - g = P( , x), g′ =Q(x, ), V1 = P ∃- , and V2 = Q∃; - g = P( , x), g′ =Q( , x), V1 = P ∃- , and V2 = Q∃- .

Based on Theorem 3, the decentralized computation of cl gr(g, PI) is straighforward using DECA: if g is built from the vocabulary of the peer Pi, g′ ∈ cl gr(g, PI) iff ¬V2 ∈ DeCAi (¬V1) for the same values of g, g′ , V1, and V2 of the corresponding cases of Theorem 3.

The decentralized version of PerfectRef, denoted PerfectRef i when running on peer Pi, is given in Algorithm 4. For each atom in the query, it computes first (in the decentralized manner explained previously) the set of all of its reformulations, and then it produces a first set of reformulations of the original query by building all the conjunctions between the atomic reformulations (denoted owedgeni=1 cl gr(gi, PI) at Line 5). Those reformulations are then possibly simplified by unifying some of their atoms (Lines 8 to 11), and the reformulation process is iterated on those newly produced reformulations until no simplification is possible (general loop starting on Line 4).

Algorithm 4: The decentralized P erf ectRef algorithm running on the peer Pi of the PDMS S

P erf ectRef i (q)

Input: a conjunctive query q over the Tbox Ti of the peer Pi Output: a union of conjunctive queries over the Tbox T of the PDMS S

(1) PR := {q} (2) PR′ := P R (3) while PR′ ̸= ∅ (4) (a) foreach q′ = g1 ∧ g2 ∧ . . . ∧ gn ∈ PR′ (5) PR′′ = owedgeni=1cl gr(gi, PI) (6) PR′ = ∅ (7) (b) foreach q′′ ∈ PR′′ (8) foreach g′1, g′2 ∈ q′′ (9) if g′1 and g′2 unify (10) PR′ := PR′ ∪ {τ (reduce(q′′ , g′1, g′2))} (11) PR = PR∪ PR′ ∪ PR′′

1. return PR

The following theorem states the correctness of the decentralized reformulation algorithm P erf ectRef i .

Theorem 4 (Correctness of PerfectRef i) Let

T = ⋃ni=1 Ti be a Tbox of a PDMS. Let q be a conjunctive query over Ti. PerfectRef i(q) returns the same set of conjunctive queries as PerfectRef(q, T ).

Its proof results (1) from the observation that the centralized version of PerfectRef i (in which cl gr(gi, PI) is computed by iterating the one-step application of PIs on each atom gi of the query) produces the same results than the original P erf ectRef , and (2) from Theorem 3 and the completeness of DECA, ensuring the decentralized computation of the whole set cl gr(gi, PI).

In contrast with the original Answer algorithm, the global consistency of the PDMS cannot be checked at query time since the queried peer Pi does not know all the peers in the PDMS. However, it can get the identifiers id1, . . . , idk of the peers involved in a reformulation of the query (to contact them) from the identifiers used in the atomic concept and role names involved in that reformulation. Algorithm 5 describes the decentralized Answeri algorithm that checks in a decentralized manner whether ⋃kj=1 (Tidj ∪ Aidj ) is consistent and computes the set of corresponding answers by evaluating each reformulation against the relevant Aboxes.

Algorithm 5: The decentralized Answer algorithm running on the peer Pi of the PDMS S

Answeri (Q)

Input: a union of conjunctive queries Q over the KB Ki = 〈Ti, Ai〉 of Pi

Output: ans(Q, K) where K = 〈T , A〉 is the KB of the PDMS S

1. q = Sq′∈Q PerfectRef i (q′ )
2. if Consistentidj returns true for every peer Pidj involved in q
3. return qdb(Skj=1 Aidj )
4. else return the singleton {⊥}

In that algorithm ⊥ replaces AllTup(Q, K) of the original Answer algorithm.

The interest of Algorithm 5 is to provide well-founded answers, i.e., answers that can be entailed from a consistent subset of the (possibly inconsistent) KB of the PDMS.

4 Query Answering using Views by Rewriting

We provide algorithms for computing the certain answers of a query over a (centralized or decentralized) DL-LITER KB K = 〈T , V, E〉 where E is the extension of views in V that are conjunctive queries over T . For doing so, we make use of the scalable MiniCon [Pottinger and Halevy, 2001] algorithm which produces the maximally-contained conjunctive rewritings of a conjunctive query q using a set V of conjunctive views. A conjunctive rewriting of q is a conjunctive query qv whose body predicates are the head predicates of views in V such that T ∪ V |= ∀¯x (qv(¯x) ⇒ q(¯x)). In that setting ([Halevy, 2001]), the set of certain answers of a query can be obtained by evaluating against the view extensions the (finite) union of its maximally-contained conjunctive rewritings.

Centralized Case First V iewConsistent(K) checks the consistency of the KB It is a variant of the original Consistent algorithm obtained by replacing:

• qunsat = qunsat ∨ δ(α) in Line 3 of Algorithm 2 by qunsat = qunsat ∨ MiniCon(δ(α), V), where MiniCon(δ(α), V) provides the maximally-contained rewritings using V of the FOL translation δ(α) of the NI α,
• qdb(A) unsat in Line(4) of Algorithm 2 by the evaluation against the view extensions: qdb(E) unsat .

Algorithm 6 describes the CertainAnswer algorithm. If the KB is inconsistent, the algorithm returns Alltup(Q, E), the set of all the tuples of the arity of Q generated from the constants in E. Otherwise, it computes (using MiniCon(q′ , V)) the rewritings in terms of the views of the conjunctive queries q′ returned by PerfectRef as the different ways of unfolding the initial query using the PIs of T .

Algorithm 6: The CertainAnswer algorithm

CertainAnswer(Q, K)

Input: a union of conjunctive queries Q and a KB K = 〈T , V, E〉 Output: cert(Q,K)

1. if not V iewConsistent(K)
2. return Alltup(Q, E)
3. else
4. Q′ = Sq∈Q P erf ectRef (q, T )
5. return (Sq′∈Q′ MiniCon(q′ , V))db(E)

Theorem 5 (Correctness of CertainAnswer) Let K = 〈T , V, E〉 be a DL-LITER consistent KB and Q a union of conjunctive queries. cert(Q, K) = CertainAnswer(Q, K).

For one direction, from q′ ∈ PerfectRef(q, T ) and qv ∈ Minicon(q′ , V) we infer: T ∪ V |= ∀¯x(qv(¯x) ⇒ q(¯x)), and thus qv is a conjunctive rewriting of q, the evaluation of which provides certain answers. For the converse direction: if ¯ t is a certain answer, by adapting the notion of witness of a tuple introduced in Lemma 39 of [Calvanese et al., 2007] to E instead of A, we build from the witness of ¯ t a specific conjunctive query qv over view atoms such that ¯ t is in its answer set and we show by induction that this query is a rewriting of a reformulation q′ of q. Since Minicon computes all the maximally-contained rewritings (Theorem 1 in [Pottinger and Halevy, 2001]), qv is contained in one of them, and ¯ t will be returned by Line 5 of Algorithm 6.

Decentralized Case For space limitation, we just sketch the approach: the decentralized versions of V iewConsistent and of CertainAnswer are denoted V iewConsistenti and CertainAnsweri when running on a peer Pi. They are extensions of the decentralized algorithms Consistenti and Answeri presented in the previous section. They use the function fetchV iews(q) where q is a conjunctive query possibly involving the vocabulary of different peers: fetchV iews(q) retrieves from those peers the views a body atom of which can be unified with a body atom of the query.

The V iewConsistenti algorithm extends Consistenti by replacing the evaluation of qunsat against the relevant Aboxes by the evaluation of Qunsat against the relevant view extensions, where Qunsat is obtained from qunsat (which is computed as in Consistenti ) as follows:

The CertainAnsweri algorithm extends Answeri by replacing the evaluation against the relevant Aboxes of the union q of conjunctive queries obtained by reformulation of the initial query (Line 2 in Algorithm 5) by evaluating against the relevant view extensions the following query Q:

5 Conclusion

This papers builds on and extends existing work in data integration ([Calvanese et al., 2007; 2008b] and [Pottinger and Halevy, 2001]). For view-based query answering in DLLITER we provide a centralized and a decentralized algorithm to compute the certain answers based on rewritings. For the decentralized case, our work extends the data model of the SOMEOWL and SOMERDFS PDMSs ([Adjiman et al., 2006; 2007]). We follow the same approach based on limiting the data model allowing to reduce consistency checking and query reformulation to reasoning in propositional logic. It is a way of getting the decidability for query answering in PDMS which is not guaranteed in general ([Halevy et al., 2003]), while adopting a standard logical semantics, in contrast with other works (e.g., ([Calvanese et al., 2008a], [Franconi et al., 2004], [Serafini et al., 2005]). It is also a distinguishing point from the approach in [Bertossi and Bravo, 2007] (based on answer set programs) for defining consistent answers in possibly inconsistent PDMSs.