The Local Relational Model: Model and Proof Theory

In this paper we identify desirable data management mechanisms for peer-to-peer (hereafter P2P) computing. In particular, we note that 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 databases associated with peers. Instead, one needs a data model which views the space of data that is being managed within the P2P network as an open collection of possibly overlapping and inconsistent databases (assumed to be relational.) Accordingly, the paper proposes the Local Relational Model and offers a formal semantics for database coordination between peer databases. Specifically, the paper proposes a model- and a proof-theoretic semantics for coordination formulas and proves soundness and completeness. The main result of the paper 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 multi-context system. This work extends earlier work by Giunchiglia and Ghidini on Local Model Semantics