Peer Data Exchange

Summary: Defines peer data exchange, a generalization of data exchange that models authority relations between peers via source-to-target and target-to-source constraints, with the target augmentable but not allowed to modify source data. Studies the fundamental solution-existence problem: proves it is in NP and can be NP-complete (even for “acyclic” settings), shows certain-answer data complexity is coNP/coNP-complete, and identifies tight syntactic fragments (e.g., arbitrary TGDs s→t with LAV t→s) that yield polynomial-time solvability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1349
Venue: PODS
Year: 2005
Pagerank: 8.4855313e-05
Overall Rank: 2,510 | 82.79%
DOI: 10.1145/1065167.1065188

Incoming Non-self Citations Over Time

Authors

1. Ariel Fuxman (University of Toronto)
2. Phokion G. Kolaitis (IBM; University of California Santa Cruz)
3. Renée J. Miller (University of Toronto)
4. Wang-Chiew Tan (University of California Santa Cruz)

BibTeX Citation

@inproceedings{fuxman_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Peer Data Exchange}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065188},
        doi = {10.1145/1065167.1065188},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fuxman, Ariel and Kolaitis, Phokion G. and Miller, Renée J. and Tan, Wang-Chiew},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
525	The Chase Revisited	2008	PODS	0.00017118255
834	Debugging Schema Mappings with Routes	2006	VLDB	0.00013724553
1,599	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010241307
3,247	On Chase Termination Beyond Stratification	2009	VLDB	7.5993811e-05
3,546	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.3244507e-05
4,369	Semantic Query Optimization in the Presence of Types	2010	PODS	6.7390374e-05
4,768	Value Invention in Data Exchange	2013	SIGMOD	6.5171839e-05
5,154	Cooperative Update Exchange in the Youtopia System	2009	VLDB	6.3423714e-05
5,264	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.2947526e-05
5,624	Answering Aggregate Queries in Data Exchange	2008	PODS	6.145135e-05
6,611	Information Preserving XML Schema Embedding	2005	VLDB	5.8228205e-05
7,702	Interactive Source Registration in Community-oriented Information Integration	2008	VLDB	5.5647785e-05
8,348	Reflections on Schema Mappings, Data Exchange, and Metadata Management	2018	PODS	5.4469775e-05
8,853	Data Conflict Resolution Using Trust Mappings	2010	SIGMOD	5.3576841e-05
9,726	Data Integration and Data Exchange: It’s Really About Time	2013	CIDR	5.2302483e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
377	Data Exchange: Getting to the Core	2003	PODS	0.00019643793
416	Translating Web Data	2002	VLDB	0.00018877803
2,100	Logical Foundations of Peer-To-Peer Data Integration	2004	PODS	9.1675595e-05
2,268	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.8370676e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,624	Answering Aggregate Queries in Data Exchange	2008	PODS
2	5,060	Scalable Data Exchange with Functional Dependencies	2010	VLDB
3	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
4	884	Mapping Data in Peer-to-Peer Systems: Semantics and Algorithmic Issues	2003	SIGMOD
5	377	Data Exchange: Getting to the Core	2003	PODS
6	3,302	Data Exchange: Computing Cores in Polynomial Time	2006	PODS
7	4,794	CWA-Solutions for Data Exchange Settings with Target Dependencies	2007	PODS
8	2,550	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS
9	3,485	The Complexity of Data Exchange	2006	PODS
10	3,546	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS