This paper stems from previous works of the same authors in which a declarative semantics for Peer-to-Peer (P2P) systems, de ned in terms of Preferred Weak Models, is proposed. Under this semantics only facts not making the local databases inconsistent can be imported. As in the general case a P2P system may admit many preferred weak models whose computational complexity is prohibitive, the paper looks for a more pragmatic solution. It assigns to a P2P system its Well Founded Model, a partial deterministic model that captures the intuition that if an atom is true in a preferred weak model, but it is false in another one, then it is unde ned in the well founded model.
Di erent works investigate topic related to the integration of information and
the computation of queries in P2P systems [
Familiarity is assumed with deductive database [
De nition 1. P2P System. A peer Pi is a tuple hDi; LPi; MPi; ICii, where (i) Di is a set of facts (local database); (ii) LPi is a set of standard rules; (iii) MPi is a set of mapping rules and (iv) ICi is a set of constraints over predicates de ned by Di, LPi and MPi. A P2P system PS is a set of peers fP1; : : : ; Png. 2 Given a P2P system PS = fP1; : : : ; Png, where Pi = hDi; LPi; MPi; ICii, D; LP; MP and IC denote, respectively, the global sets of ground facts, standard rules, mapping rules and integrity constraints, i.e. D = Si2[1::n] Di, LP = Si2[1::n] LPi, MP = Si2[1::n] MPi and IC = Si2[1::n] ICi. In the rest of this paper, with a little abuse of notation, PS will be also denoted both with the tuple hD; LP; MP; ICi and the set D [ LP [ MP [ IC.
We now review the Preferred Weak Model semantics in [
Given a mapping rule r = H - B, the corresponding standard logic rule H B will be denoted as St(r). Analogously, given a set of mapping rules MP, St(MP) = fSt(r) j r 2 MPg and given a P2P system PS = D [ LP [ MP [ IC, St(PS) = D [ LP [ St(MP) [ IC.
Given an interpretation M , an atom H and a conjunction of atoms B: - valM (H B) = valM (H) valM (B), - valM (H - B) = valM (H) valM (B).
Therefore, if the body is true, the head of a standard rule must be true, whereas the head of a mapping rule could be true. Intuitively, a weak model M is an interpretation that satis es all standard rules, mapping rules and constraints of PS and such that each atom H 2 M [MP] (i.e. each mapping atom) is supported from a mapping rule H - B whose body B is satis ed by M . A preferred weak model is a weak model containing a maximal subset of mapping atoms. De nition 2. (Preferred) Weak Model. Given a P2P system PS = D [ LP [ MP [ IC, an interpretation M is a weak model for PS if fM g = MM(St(PSM )), where PSM is the program obtained from ground(PS) by removing all mapping rules whose head is false w.r.t. M . Given two weak models M and N , M is said to preferable to N , and is denoted as M w N , if M [MP] N [MP]. Moreover, if M w N and N 6w M , then M = N . A weak model M is said to be preferred if there is no weak model N such that N = M . The set of weak models for a P2P system PS will be denoted by WM(PS), whereas the set of preferred weak models will be denoted by PWM(PS). 2 Theorem 1. For every consistent P2P system PS, PWM(PS) 6= ;. Example 2. Consider a P2P system PS in which the peer: P2 contains the facts q(a) and q(b), whereas P1 contains the mapping rule p(X) - q(X) and the constraint p(X); p(Y ); X 6= Y . WM(PS) are: M0 = fq(a); q(b)g, M1 = fq(a); q(b); p(a)g and M2 = fq(a); q(b); p(b)g, whereas PWM(PS) are M1 and M2 as they import maximal sets of atoms from P2. 2
This section presents an alternative characterization of the preferred weak model semantics, that allows to model a P2P system PS with a single logic program Rewt(PS). Let's rstly introduce some preliminaries. Given an atom A = i : p(x), At denotes the atom i : pt(x) and Av denotes the atom i : pv(x). At will be called the testing atom, whereas Av will be called the violating atom. De nition 3. Given a conjunction B = A1; : : : ; Ah; not Ah+1; : : : ; not An; B1; : : : ; Bk; not Bk+1; : : : ; not Bm; (1) where Ai (i 2 [1:: n]) is a mapping atom or a derived atom, Bi (i 2 [1:: m]) is a base atom and is a conjunction of built in atoms, we de ne Bt = At1; : : : ; Ath; not Ath+1; : : : ; not Atn; B1; : : : ; Bk; not Bk+1; : : : ; not Bm; (2) Therefore, given a negation free conjunction B = A1; : : : ; Ah; B1; : : : ; Bk; : : : ; , then Bt = At1; : : : ; Ath; B1; : : : ; Bk; . In the following, the rewriting of a P2P system is reported.
De nition 4. Rewriting of an integrity constraint. Given an integrity constraint i = B (that is of the form (1)) its rewriting is de ned as Rewt(i) = fA1v _ : : : _ Avh Btg. 2 If Bt (of the form (2)), is true, at least one of the violating atoms A1v; : : : ; Avh is true. Therefore, at least one of the atoms A1; : : : ; Ah cannot be inferred. De nition 5. Rewriting of a standard rule. Given a standard rule s = H B, its rewriting is de ned as Rewt(s) = fH B; Ht Bt; A1v_: : :_Avh Bt; Hv g. 2 In order to nd the mapping atoms that, if imported, generate some inconsistencies (i.e. in order to nd their corresponding violating atoms), all possible mapping testing atoms are imported and the derived testing atoms are inferred. In the previous de nition, if Bt is true and the violating atom Hv is true, then the body of the disjunctive rule is true and therefore it can be deduced that at least one of the violating atoms A1v; : : : ; Avh is true (i.e. to avoid such inconsistencies at least one of atoms A1; : : : ; Ah cannot be inferred).
De nition 6. Rewriting of a mapping rule. Given a mapping rule m = H - B, its rewriting is de ned as Rewt(m) = fHt B; H Ht; not Hv g. 2 Intuitively, to check whether a mapping atom H generates some inconsistencies, if imported in its target peer, a testing atom Ht is imported in the same peer. Rather than violating some integrity constraint, it (eventually) generates, by rules obtained from the rewriting of standard rules and integrity constraints, the atom Hv. In this case H, cannot be inferred and inconsistencies are prevented. De nition 7. Rewriting of a P2P system. Given a P2P system PS = DSs[2LLPPRe[wMt(sP), R[eIwCt(,ItCh)en=: RSeiw2tI(CMRPew)t(=i) aSnmd2RMewPtR(PewSt)(=m)D, [RRewe wt(tL(LPP) )=[ Rewt(MP) [ Rewt(IC) 2 De nition 8. Total Stable Model. Given a P2P system PS and a stable model M for Rewt(PS), the interpretation obtained by deleting from M its violating and testing atoms, denoted as T (M ), is a total stable model of PS. The set of total stable models of PS is denoted as T SM(PS). 2 Example 3. Consider the P2P system PS in Ex. 2. From Def. (7) we obtain: Rewt(PS) =fq(a); q(b); pt(X) q(X); p(X) pt(X); not pv(X); pv(X) _ pv(Y ) pt(X); pt(Y ); X 6= Y g The stable models of Rewt(PS) are: M1 = fq(a); q(b); pt(a); pt(b); pv(a); p(b)g; M2 = fq(a); q(b); pt(a); pt(b); p(a); pv(b)g. Then, the total stable models of PS are T SM(PS) = ffq(a); q(b); p(b)g; fq(a); q(b); p(a)gg. 2 Theorem 2. For every P2P system PS, T SM(PS) = PWM(PS). 2 4
A P2P system may admit many preferred weak models whose computational
complexity has been shown to be prohibitive [
De nition 10. Well Founded Semantics. Given an HCF P2P system PS and the well founded model of Reww(PS), say hT; F i, the well founded model semantics of PS is given by hT (T ); T (F )i. 2 Example 4. The rewriting of the HCF P2P system PS in Example 3 is: Reww(PS) =fq(a); q(b); pt(X) q(X); p(X) pt(X); not pv(X); pv(X) pt(X); pt(Y ); X 6= Y; not pv(Y ); pv(Y ) pt(X); pt(Y ); X 6= Y; not pv(X)g The well founded model of Reww(PS) is hfq(a); q(b); pt(a); pt(b)g; ;i and the well founded semantics of PS is given by hfq(a); q(b)g; ;i. The atoms q(a) and q(b) are true, while the atoms p(a) and p(b) are unde ned. 2 Theorem 4. Let PS be a HCF P2P system, then deciding: (i) whether an interpretation M is a preferred weak model of PS is P -time; (ii) whether an atom A is true in some preferred weak model of PS is N P-complete; (iii) whether an atom A is true in every preferred weak model of PS is coN P-complete; (iv) whether an atom A is true in the well founded model of PS is P -time. 2 Reww(PS) allows to compute the well founded semantics of PS in polynomial time. In this section we present a technique allowing to compute the well founded model in a distributed way. The basic idea is that each peer computes its own portion of the \unique logic program", sending to the other peers the result. De nition 11. Let PS= be an HCF P2P system, where Pi = hDi; LPi; MPi; ICii, for i 2 [1::n]. Then, Reww(Pi) = Reww(Di [ LPi [ MPi [ ICi). Previous de nition allows to derive a single normal logic program for each peer. Observe that, Reww(PS) = Si2[1::n] Reww(Pi).
Example 5. The rewritings located on peers P1 and P2 of Ex. 2 are: Reww(P1) = fpt(X) q(X); p(X) pt(X); not pv(X); pv(X) pt(X); pt(Y ); not pv(Y ); X 6= Y ; pv(Y ) pt(X); pt(Y ); not pv(X); X 6= Y g: Reww(P2) = fq(a); q(b)g: 2 The idea is the following: if a peer receives a query, then it will recursively query the peer to which it is connected through mapping rules, before being able to calculate its answer. Formally, a local query submitted by a user to a peer does not di er from a remote query submitted by another peer. Once retrieved the necessary data from neighbor peers, the peer computes its well founded model and evaluates the query (either local or remote) on that model; then if the query is a remote query, the answer is sent to the requesting peer. For the sake of presentation, a partial model reports, using the syntax [T; U ], the sets of true and unde ned atoms, instead of the sets of true and false atoms. Example 6. Consider the P2P system in Example 2. If P1 receives the query p(X), it submits the query p(X) to the peer P2. Once P2 receives the query q(X), it computes its well founded model W2 = [fq(a); q(b)g; ;]. P1 receives the data, populates its local database and computes its well founded model W1 = [fpt(a); pt(b)g; fpv(a); pv(b); p(a); p(b)g] and nally, evaluates the query p(X) over W1. The answer will be [;; fp(a); p(b)g]. Observe that, the peer replies providing two unde ned atoms: p(a) and p(b). 2 Algorithm: ComputeAnsweri input: 1) i : q(X) - a query
2) s - a sender which is a peer Pk (remote query) or null (local query) output: [T; U ] where T (resp. U ) is the set of true (resp. unde ned ) atoms begin while true wait for an input i : q(X) and s; P = Reww(Pi); for each (i : h(X) - j : b(X)) 2 MPi [T; U ] = ComputeAnswerj(j : b(X); Pi);
P = P [ T [ fa not a j a 2 U g; end for [Tw; Uw] = ComputeW ellF oundedM odel(P ); answer = [fi : q(x) j i : q(x) 2 Twg; fi : q(x) j i : q(x) 2 Uwg]; if isN ull(s) then show(answer); else send(answer; Pk); end if end while end We associate to a P2P system, PS, a graph g(PS) whose nodes are the peers of PS and whose edges are the pairs (Pi; Pj) s.t. (i : H - j : B) 2 PS. We say that PS is acyclic if g(PC) is acyclic. In order to guarantee the termination of the computation, from now on we assume that our P2P systems are acyclic. Without loss of generality, we assume that each mapping rule is of the form i : p(X) - j : q(X). The behavior of the peer Pi = hDi; LPi; MPi; ICii within the P2P system can be modeled by the algorithm ComputeAnsweri, running on the peer Pi. It receives in input a query i : q(X) submitted by a sender s which can be another peer or a user. For each mapping rule i : h(X) - j : b(X), the peer Pi queries the peer Pj asking for j : b(X). Pi will receive true and unde ned tuples that will enrich the local knowledge. Observe that, true atoms will be simply inserted into P while for each unde ned atom a, a rule a not a allowing to infer the correct truth value for a (unde ned) in the well founded model, is inserted. Once the local knowledge has been updated, the local well founded model is computed by means of the function ComputeW ellF oundedM odel and the answer for the query is extracted. If the sender is a user then the answer is simply shown, otherwise (if it is a peer) it is sent back to it. A system prototype for query answering in a P2P network based on the proposed semantics has been implemented. The system has been developed using Java.
The communication among peers is performed by using JXTA libraries [