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: hcb94c152cfbd1712
Venue: PODS
Year: 2015
Pagerank: 4.9793485e-05
Overall Rank: 12,392 | 16.69%
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
190	Applying Model Management to Classical Meta Data Problems	2003	CIDR	0.00025768763
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023591683
539	The Chase Revisited	2008	PODS	0.00016735847
703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014660132
1,458	Inverting Schema Mappings	2006	PODS	0.00010585133
1,522	Composition of Mappings Given by Embedded Dependencies	2005	PODS	0.00010367399
2,390	Quasi-inverses of Schema Mappings	2007	PODS	8.5367469e-05
2,989	Data Exchange and Incomplete Information	2006	PODS	7.7755739e-05
3,018	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.7471023e-05
6,010	Reverse Data Exchange: Coping with Nulls	2009	PODS	5.9147707e-05
6,262	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB	5.8327164e-05
7,605	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.485681e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,458	Inverting Schema Mappings	2006	PODS
2	5,750	Answering Aggregate Queries in Data Exchange	2008	PODS
3	2,390	Quasi-inverses of Schema Mappings	2007	PODS
4	3,561	The Complexity of Data Exchange	2006	PODS
5	4,532	Data Exchange beyond Complete Data	2011	PODS
6	6,262	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB
7	4,367	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS
8	2,989	Data Exchange and Incomplete Information	2006	PODS
9	6,010	Reverse Data Exchange: Coping with Nulls	2009	PODS
10	3,018	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS