Quasi-inverses of Schema Mappings

Summary: Introduce quasi-inverse, a relaxation of inverse that quotients instances equivalent for data exchange; give a necessary-and-sufficient combinatorial criterion for s-t tgds, showing LAV mappings always have quasi-inverses while some full s-t tgds do not. Characterize the languages needed to express quasi-inverses and inverses (resolving an open problem) and show quasi-inverses can often recover exported data in data-exchange scenarios. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2016e631ca402b9e
Venue: PODS
Year: 2007
Pagerank: 8.5367469e-05
Overall Rank: 2,390 | 83.94%
DOI: 10.1145/1265530.1265548

Incoming Non-self Citations Over Time

Authors

1. Ronald Fagin (IBM)
2. Phokion G. Kolaitis (IBM; University of California Santa Cruz)
3. Lucian Popa (IBM)
4. Wang-Chiew Tan (University of California Santa Cruz)

BibTeX Citation

@inproceedings{fagin_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Quasi-inverses of Schema Mappings}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265548},
        doi = {10.1145/1265530.1265548},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fagin, Ronald and Kolaitis, Phokion G. and Popa, Lucian and Tan, Wang-Chiew},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
793	Model Management 2.0: Manipulating Richer Mappings	2007	SIGMOD	0.00013942384
1,505	Generic Schema Matching, Ten Years Later	2011	VLDB	0.00010454635
2,073	Graceful Database Schema Evolution: the PRISM Workbench	2008	VLDB	9.0852947e-05
3,018	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.7471023e-05
3,974	On the Complexity of Deriving Schema Mappings from Database Instances	2008	PODS	6.8868916e-05
4,532	Data Exchange beyond Complete Data	2011	PODS	6.5583849e-05
4,656	Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++	2011	VLDB	6.4827966e-05
4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.4604802e-05
5,750	Answering Aggregate Queries in Data Exchange	2008	PODS	6.0073031e-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
6,299	Classification of Annotation Semirings over Query Containment	2012	PODS	5.8190435e-05
6,887	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB	5.6550447e-05
8,017	Foundations of Schema Mapping Management	2010	PODS	5.4062707e-05
8,503	Reflections on Schema Mappings, Data Exchange, and Metadata Management	2018	PODS	5.3294549e-05
8,591	XML Schema Mappings	2009	PODS	5.3070609e-05
12,392	Recovering Exchanged Data	2015	PODS	4.9793485e-05
12,570	Getting Unique Solution in Data Exchange	2013	VLDB	4.9793485e-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
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
190	Applying Model Management to Classical Meta Data Problems	2003	CIDR	0.00025768763
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016948466
703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014660132
813	Composing Mappings Among Data Sources	2003	VLDB	0.00013722762
1,458	Inverting Schema Mappings	2006	PODS	0.00010585133
1,522	Composition of Mappings Given by Embedded Dependencies	2005	PODS	0.00010367399

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,017	Foundations of Schema Mapping Management	2010	PODS
2	703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS
3	4,406	Normalization and Optimization of Schema Mappings	2009	VLDB
4	2,244	Characterizing Schema Mappings via Data Examples	2010	PODS
5	3,018	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS
6	9,664	Local Transformations and Conjunctive-Query Equivalence	2012	PODS
7	4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS
8	6,010	Reverse Data Exchange: Coping with Nulls	2009	PODS
9	6,262	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB
10	1,458	Inverting Schema Mappings	2006	PODS