Peer data exchange

ABSTRACT

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 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 deciding the existence of a solution and for computing the certain answers of target conjunctive queries. To this effect, we identify broad syntactic conditions on the constraints between the peers under which the existence-of-solutions problem is solvable in polynomial time. We also identify syntactic conditions between peer data exchange settings and target conjunctive queries that yield polynomial-time algorithms for computing the certain answers. For both problems, these syntactic conditions turn out to be tight, in the sense that minimal relaxations of them lead to intractability. Finally, we introduce the concept of a universal basis of solutions in peer data exchange and explore its properties.

REFERENCES

• 1: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 2: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Consistent query answers in inconsistent databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.68-79, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303983]
• 3: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 4: Bernstein, P., Giunchiglia, F., Kementsietsidis, A., Mylopoulos, J., Serafini, L., and Zaihrayeu, I. 2002. Data management for peer-to-peer computing: A vision. In Proceedings of the International Workshop on the Web and Databases (WebDB). 89--94.
• 5: Bertossi, L. and Bravo, L. 2004. Query answering in peer-to-peer data exchange systems. In Proceedings of the EDBT Workshop on Peer-to-Peer Computing and Databases. 476--485.
• 6: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Data integration under integrity constraints, Information Systems, v.29 n.2, p.147-163, April 2004 [doi>10.1016/S0306-4379(03)00050-4]
• 7: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 8: Calvanese, D., Damaggio, E., De Giacomo, G., Lenzerini, M., and Rosati, R. 2004a. Semantic data integration in P2P systems. In Databases, Information Systems, and Peer-to-Peer Computing. Lecture Notes in Computer Science, vol. 2944. Springer-Verlag, Berlin, Germany, 77--90.
• 9: Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., and Rosati, R. 2005. Inconsistency tolerance in P2P data integration: An epistemic logic approach. In Database Programming Languages. Lecture Notes in Computer Science, vol. 3774. Springer-Verlag, Berlin, Germany, 90--105.
• 10: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Riccardo Rosati, Logical foundations of peer-to-peer data integration, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055593]
• 11: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 12: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 13: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 14: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 15: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, ACM Transactions on Database Systems (TODS), v.30 n.1, p.174-210, March 2005 [doi>10.1145/1061318.1061323]
• 16: Franconi, E., Kuper, G., Lopatenko, A., and Serafini, L. 2003. A robust logical and computational characterisation of peer-to-peer database systems. In Proceedings of the VLDB Workshop on Databases, Information Systems and Peer-to-Peer Computing.
• 17: Franconi, E., Kuper, G., Lopatenko, A., and Zaihrayeu, I. 2004. The coDB robust peer-to-peer database system. In Proceedings of the Symposium on Advanced Database Systems. 382--393.
• 18: G. Grahne, Problem of Incomplete Information in Relational Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 19: Gösta Grahne , Alberto O. Mendelzon, Tableau Techniques for Querying Information Sources through Global Schemas, Proceeding of the 7th International Conference on Database Theory, p.332-347, January 10-12, 1999
• 20: Y. Halevy , G. Ives , Dan Suciu , Igor Tatarinov, Schema mediation for large-scale semantic data sharing, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.1, p.68-83, March 2005 [doi>10.1007/s00778-003-0116-y]
• 21: Phokion G. Kolaitis , Jonathan Panttaja , Wang-Chiew Tan, The complexity of data exchange, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142357]
• 22: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 23: Chen Li , Jia Li , Qi Zhong, RACCOON: A Peer-Based System for Data Integration and Sharing, Proceedings of the 20th International Conference on Data Engineering, p.852, March 30-April 02, 2004
• 24: Nash, A., Deutsch, A., and Remmel, J. 2006. Data exchange, data integration, and chase. Tech. rep. CS2006-0859, University of California, San Diego, San Diego, CA.
• 25: O'Donovan, C., Martin, M. J., Gattiker, A., Gasteiger, E., Bairoch, A., and Apweiler, R. 2002. High-quality protein knowledge resource: Swiss-prot and trembl. Briefings Bioinformat. 3, 3, 275--284.
• 26: Popa, L., Velegrakis, Y., Miller, R. J., Hernández, M. A., and Fagin, R. 2002. Translating Web data. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 598--609.
• 27: Igor Tatarinov , Alon Halevy, Semantic data sharing with a peer data management system, 2004
• 28: Igor Tatarinov , Alon Halevy, Efficient query reformulation in peer data management systems, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007629]
• 29: Ron van der Meyden, Logical approaches to incomplete information: a survey, Logics for databases and information systems, Kluwer Academic Publishers, Norwell, MA, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
Data exchange, certain answers, conjunctive queries, data integration, metadata model management, schema mapping