Incremental maintenance of mapping constraints in peer-to-peer database systems

We are interested in the problem of managing mapping constraints in Peer-to-Peer (P2P) data-sharing systems. The Hyperion project has explored mapping tables as value constraints on the exchange of information among peers and developed an efficient algorithm inferring new mapping tables from existing ones. However, this (holistic) algorithm does not consider the dynamic setting of P2P systems, where mapping tables are continuously revised/added/deleted.; This thesis presents a hypergraph model for mapping tables and an incremental algorithm handling the dynamic characteristics of P2P systems in maintaining the consistency of mapping tables. Experimental results demonstrate the efficiency of the incremental algorithm over its "compute-from-scratch" counterpart. Our work also addresses the data provenance problem in the sense that "why" and "where" questions can be answered about derived mappings.