Ariel Fuxman
ABSTRACT
In this paper, we introduce and study a framework, called peer data exchange, for sharing and exchanging data between peers. This framework is a special case of a full-fledged peer data management system and a generalization of data exchange between a source schema and a target schema. The motivation behind peer data exchange is to model authority relationships between peers, where a source peer may contribute data to a target peer, specified using source-to-target constraints, and a target peer may use target-to-source constraints to restrict the data it is willing to receive, but cannot modify the data of the source peer.
A fundamental algorithmic problem in this framework is that of deciding the existence of a solution: given a source instance and a target instance for a fixed peer data exchange setting, can the target instance be augmented in such a way that the source instance and the augmented target instance satisfy all constraints of the setting? We investigate the computational complexity of the problem for peer data exchange settings in which the constraints are given by tuple generating dependencies. We show that this problem is always in NP, and that it can be NP-complete even for "acyclic" peer data exchange settings. We also show that the data complexity of the certain answers of target conjunctive queries is in coNP, and that it can be coNP-complete even for "acyclic" peer data exchange settings.
After this, we explore the boundary between tractability and intractability for the problem of deciding the existence of a solution. To this effect, we identify broad syntactic conditions on the constraints between the peers under which testing for solutions is solvable in polynomial time. These syntactic conditions include the important special case of peer data exchange in which the source-to-target constraints are arbitrary tuple generating dependencies, but the target-to-source constraints are local-as-view dependencies. Finally, we show that the syntactic conditions we identified are tight, in the sense that minimal relaxations of them lead to intractability.
- S. Abiteboul and O. M. Duschka. Complexity of answering queries using materialized views. In PODS, pages 254--263, 1998.]] Google Scholar
Digital Library
- M. Arenas, L. Bertossi, and J. Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68--79, 1999.]] Google ScholarDigital Library
- C. Beeri and M. Vardi. A proof procedure for data dependencies. Journal of the ACM, 31(4):718--741, 1984.]] Google ScholarDigital Library
- P. Bernstein, F. Giunchiglia, A. Kementsietsidis, J. Mylopoulos, L. Serafini, and I. Zaihrayeu. Data management for Peer-to-Peer computing: A vision. In WebDB, pages 89--94, 2002.]]Google Scholar
- L. Bertossi and L. Bravo. Query answering in peer-to-peer data exchange systems. In EDBT Workshop on Peer-to-Peer Computing and Databases, 2004.]] Google ScholarDigital Library
- D. Calvanese, G. D. Giacomo, M. Lenzerini, and R. Rosati. Logical foundations of peer-to-peer data integration. In PODS, pages 241--251, 2004.]] Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. In ICDT, pages 207--224, 2003.]] Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. To appear in Theoretical Computer Science. In press., 2005.]] Google Scholar
- R. Fagin, P. G. Kolaitis, and L. Popa. Data exchange: getting to the core. In PODS, pages 90--101, 2003. To appear in TODS.]] Google ScholarDigital Library
- E. Franconi, G. Kuper, A. Lopatenko, and L. Serafini. A robust logical and computational characterisation of peer-to-peer database systems. In VLDB Workshop on Databases, Information Systems and Peer-to-Peer Computing, 2003.]]Google Scholar
- E. Franconi, G. Kuper, A. Lopatenko, and I. Zaihrayeu. The coDB robust peer-to-peer database system. In Symposium on Advanced Database Systems, pages 382--393, 2004.]]Google Scholar
- G. Grahne. The Problem of Incomplete Information in Relational Databases. Spring-Verlag, Berlin, 1991. Lecture Notes in Computer Science, vol. 554.]] Google ScholarDigital Library
- G. Grahne and A. Mendelzon. Tableau techniques for querying information sources through global schemas. In ICDT, pages 332--347, 1999.]] Google ScholarDigital Library
- A. Halevy, Z. Ives, D. Suciu, and I. Tatarinov. Schema mediation in peer data management systems. In ICDE, pages 505--518, 2003.]]Google ScholarCross Ref
- M. Lenzerini. Data integration: A theoretical perspective. In PODS, pages 233--246, 2002.]] Google ScholarDigital Library
- C. Li. Raccoon: A peer-based system for data integration and sharing. In ICDE, page 852, 2004. System Demonstration.]] Google ScholarDigital Library
- C. O'Donovan, M. J. Martin, A. Gattiker, E. Gasteiger, A. Bairoch, and R. Apweiler. High-quality protein knowledge resource: Swiss-prot and trembl. Briefings in Bioinformatics, 3(3):275--284, 2002.]]Google ScholarCross Ref
- L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernández, and R. Fagin. Translating web data. In VLDB, pages 598--609, 2002.]] Google ScholarDigital Library
- I. Tatarinov. Semantic Data Sharing with a Peer Data Management System. PhD thesis, University of Washington, 2004.]] Google ScholarDigital Library
- I. Tatarinov and A. Y. Halevy. Efficient query reformulation in peer data management systems. In SIGMOD, pages 539--550, 2004.]] Google ScholarDigital Library
- R. van der Meyden. Logical approaches to incomplete information: A survey. In J. Chomicki and G. Saake, editors, Logics for Databases and Information Systems, pages 307--356. Kluwer, 1998.]] Google ScholarDigital Library
Recommendations
Peer data exchange
In this article, we introduce and study a framework, called peer data exchange, for sharing and exchanging data between peers. This framework is a special case of a full-fledged peer data management system and a generalization of data exchange between a ...
XML data exchange: consistency and query answering
PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsData exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target. Theoretical foundations of data exchange have recently been ...
An Efficient Hybrid Peer-to-Peer System for Distributed Data Sharing
Peer-to-peer overlay networks are widely used in distributed systems. Based on whether a regular topology is maintained among peers, peer-to-peer networks can be divided into two categories: structured peer-to-peer networks in which peers are connected ...
Comments