{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T03:14:51Z","timestamp":1792034091450,"version":"4.4.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p>\n            In this article, we introduce and study a framework, called\n            <jats:italic>peer data exchange<\/jats:italic>\n            , 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 \u201cacyclic\u201d 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 \u201cacyclic\u201d 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.\n          <\/jats:p>","DOI":"10.1145\/1189769.1189778","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"1454-1498","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":69,"title":["Peer data exchange"],"prefix":"10.1145","volume":"31","author":[{"given":"Ariel","family":"Fuxman","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Ont., Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ren\u00e9e J.","family":"Miller","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Ont., Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wang-Chiew","family":"Tan","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Workshop on the Web and Databases (WebDB). 89--94","author":"Bernstein P.","unstructured":"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 .]] 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.]]"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the EDBT Workshop on Peer-to-Peer Computing and Databases. 476--485","author":"Bertossi L.","unstructured":"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 .]] 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.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(03)00050-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773179"},{"key":"e_1_2_1_8_1","volume-title":"Lecture Notes in Computer Science","volume":"2944","author":"Calvanese D.","unstructured":"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.]] 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.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055593"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 225--241","author":"Deutsch A.","unstructured":"Deutsch , A. and Tannen , V . 2003. Reformulation of XML queries and constraints . In Proceedings of the International Conference on Database Theory (ICDT). 225--241 .]] Deutsch, A. and Tannen, V. 2003. Reformulation of XML queries and constraints. In Proceedings of the International Conference on Database Theory (ICDT). 225--241.]]"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 207--224","author":"Fagin R.","unstructured":"Fagin , R. , Kolaitis , P. G. , Miller , R. J. , and Popa , L . 2003. Data exchange: Semantics and query answering . In Proceedings of the International Conference on Database Theory (ICDT). 207--224 .]] Fagin, R., Kolaitis, P. G., Miller, R. J., and Popa, L. 2003. Data exchange: Semantics and query answering. In Proceedings of the International Conference on Database Theory (ICDT). 207--224.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the VLDB Workshop on Databases, Information Systems and Peer-to-Peer Computing.]]","author":"Franconi E.","unstructured":"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.]] 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.]]"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Symposium on Advanced Database Systems. 382--393","author":"Franconi E.","unstructured":"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 .]] 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.]]"},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Computer Science","volume-title":"The Problem of Incomplete Information in Relational Databases","author":"Grahne G.","unstructured":"Grahne , G. 1991. The Problem of Incomplete Information in Relational Databases . Lecture Notes in Computer Science , vol. 554 . Springer-Verlag , Berlin, Germany .]] Grahne, G. 1991. The Problem of Incomplete Information in Relational Databases. Lecture Notes in Computer Science, vol. 554. Springer-Verlag, Berlin, Germany.]]"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 332--347","author":"Grahne G.","unstructured":"Grahne , G. and Mendelzon , A . 1999. Tableau techniques for querying information sources through global schemas . In Proceedings of the International Conference on Database Theory (ICDT). 332--347 .]] Grahne, G. and Mendelzon, A. 1999. Tableau techniques for querying information sources through global schemas. In Proceedings of the International Conference on Database Theory (ICDT). 332--347.]]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0116-y"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142357"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 852","author":"Li C.","year":"2004","unstructured":"Li , C. 2004 . Raccoon: A peer-based system for data integration and sharing . In Proceedings of the International Conference on Data Engineering (ICDE). 852 . (System Demonstration).]] Li, C. 2004. Raccoon: A peer-based system for data integration and sharing. In Proceedings of the International Conference on Data Engineering (ICDE). 852. (System Demonstration).]]"},{"key":"e_1_2_1_24_1","volume-title":"CS2006-0859","author":"Nash A.","unstructured":"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.]] 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.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/3.3.275"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 598--609","author":"Popa L.","unstructured":"Popa , L. , Velegrakis , Y. , Miller , R. J. , Hern\u00e1ndez , M. A. , and Fagin , R . 2002. Translating Web data . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 598--609 .]] Popa, L., Velegrakis, Y., Miller, R. J., Hern\u00e1ndez, M. A., and Fagin, R. 2002. Translating Web data. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 598--609.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007629"},{"key":"e_1_2_1_29_1","volume-title":"Logics for Databases and Information Systems","author":"van der Meyden R.","unstructured":"van der Meyden , R. 1998. Logical approaches to incomplete information: A survey . In Logics for Databases and Information Systems , J. Chomicki and G. Saake, Eds. Kluwer, Dordrecht , The Netherlands , 307--356.]] van der Meyden, R. 1998. Logical approaches to incomplete information: A survey. In Logics for Databases and Information Systems, J. Chomicki and G. Saake, Eds. Kluwer, Dordrecht, The Netherlands, 307--356.]]"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189769.1189778","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:09:26Z","timestamp":1672261766000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189769.1189778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1145\/1189769.1189778"],"URL":"https:\/\/doi.org\/10.1145\/1189769.1189778","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"2006-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}