Abstract
Recently, there have been several proposals that consider the integration of information and the computation of queries in an open-ended network of distributed peers (Bernstein, Giunchiglia, Kementsietsidis, Mylopulos, Serafini, & Zaihrayen, 2002; Calvanese, De Giacomo, Lenzerini, & Rosati, 2004; Franconi, Kuper, Lopatenko, & Zaihrayeu, 2003) as well as the problem of schema mediation and query optimization in P2P (peerto- peer) environments (Gribble, Halevy, Ives, Rodrig, & Suciu, 2001; Halevy, Ives, Suciu, & Tatarinov, 2003; Madhavan & Halevy, 2003; Tatarinov & Halevy, 2004). Generally, peers can both provide or consume data and the only information a peer participating in a P2P system has is about neighbors, that is, information about the peers that are reachable and can provide data of interest. More specifically, each peer joining a P2P system exhibits a set of mapping rules, in other words, a set of semantic correspondences to a set of peers that are already part of the system (neighbors). Thus, in a P2P system, the entry of a new source, or peer, is extremely simple as it just requires the definition of the mapping rules. By using mapping rules as soon as it enters the system, a peer can participate and access all data available in its neighborhood, and through its neighborhood it becomes accessible to all the other peers in the system.
TopMotivation
The motivation of this work stems from the observation that previously proposed approaches result in not being sound with respect to query answering when some peer is inconsistent.
Example 1. Consider the P2P system depicted in Figure 1 consisting of three peers P1, P2, and P3 where
- •
P3 contains two atoms, r(a) and r(b),
- •
P2 imports data from P3 using the (mapping) rule q(X)r(X) (observe that a special syntax is used for mapping rules). Moreover, imported atoms must satisfy the constraint ← q(X), q(Y), X≠Y stating that the relation q may contain at most one tuple, and
- •
P1 imports data from P2 using the (mapping) rule p(X)q(X). P1 also contains the rules s ← p(X) stating that s is true if the relation p contains at least one tuple, and t ← p(X), p(Y), X≠Y, stating that t is true if the relation p contains at least two distinct tuples.
Key Terms in this Chapter
P2P System: A collection of autonomous nodes providing or requesting data.
Integrity Constraints: Set of constraints that must be satisfied by database instances.
Consistent Database: A database satisfying a set of integrity constraints.
Inconsistent Database: A database violating some integrity constraints.