The Local Relational Model: Model and Proof Theory

In this paper we identify desirable data management mechanisms for peer-to-peer (P2P) computing. P2P networks have to remain open and dynamic, while peers remain autonomous and need only be aware of their immediate acquaintances. In such a setting, we argue that one cannot assume the existence of a global schema for all the peer databases. Instead, one needs a data model which views the space of data being managed within the P2P network as an open collection of possibly overlapping and inconsistent databases. Accordingly, the paper proposes the Local Relational Model and others a formal semantics for coordination between peer databases. Our result generalizes Reiter's characterization of a relational database in terms of a first order theory, by providing a syntactic characterization of a relational space in terms of a multicontext system.