Recovering Exchanged Data

Summary: Move from static inverse mappings to instance-based recovery: given a target instance and s→t TGDs, introduce recovery semantics and chase-based methods to compute finite representative sets of candidate source instances. Show coNP-completeness and give a PTIME algorithm that returns a small set yielding sound certain answers for UCQs, with an extension improving results for CQs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1654
Venue: PODS
Year: 2015
Pagerank: 5.093636e-05
Overall Rank: 12,099 | 16.99%
DOI: 10.1145/2745754.2745770

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Gösta Grahne (Concordia University)
2. Ali Moallemi (Concordia University)
3. Adrian Onet (Concordia University)

BibTeX Citation

@inproceedings{grahne_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Recovering Exchanged Data}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745770},
        doi = {10.1145/2745754.2745770},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Grahne, Gösta and Moallemi, Ali and Onet, Adrian},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
183	Applying Model Management to Classical Meta Data Problems	2003	CIDR	0.00026283359
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
525	The Chase Revisited	2008	PODS	0.00017118255
685	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014979915
1,426	Inverting Schema Mappings	2006	PODS	0.00010814403
1,491	Composition of Mappings Given by Embedded Dependencies	2005	PODS	0.00010592592
2,339	Quasi-inverses of Schema Mappings	2007	PODS	8.7249825e-05
2,934	Data Exchange and Incomplete Information	2006	PODS	7.9451055e-05
2,954	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.9234704e-05
5,886	Reverse Data Exchange: Coping with Nulls	2009	PODS	6.0503367e-05
6,130	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB	5.9665863e-05
7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.61159e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,426	Inverting Schema Mappings	2006	PODS
2	5,624	Answering Aggregate Queries in Data Exchange	2008	PODS
3	2,339	Quasi-inverses of Schema Mappings	2007	PODS
4	3,485	The Complexity of Data Exchange	2006	PODS
5	4,432	Data Exchange beyond Complete Data	2011	PODS
6	6,130	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB
7	4,281	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS
8	2,934	Data Exchange and Incomplete Information	2006	PODS
9	5,886	Reverse Data Exchange: Coping with Nulls	2009	PODS
10	2,954	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS