On the Complexity of Deriving Schema Mappings from Database Instances

Summary: Formalizes inferring a schema mapping from source I to target J over different unknown schemata by requiring a minimal repair to produce J as the 'optimal' translation. Proves high decision complexity for finding such mappings across mapping languages—even in restricted fragments—and develops theoretical foundations without providing a synthesis algorithm. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h4ee729d531f9e406
Venue: PODS
Year: 2008
Pagerank: 6.8868916e-05
Overall Rank: 3,974 | 73.29%
DOI: 10.1145/1376916.1376921

Incoming Non-self Citations Over Time

Authors

1. Pierre Senellart (INRIA; University of Paris)
2. Georg Gottlob (Man Institute of Quantitative Finance; University of Oxford)

BibTeX Citation

@inproceedings{senellart_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{On the Complexity of Deriving Schema Mappings from Database Instances}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376921},
        doi = {10.1145/1376916.1376921},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Senellart, Pierre and Gottlob, Georg},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
578	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016096504
1,615	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010067073
2,244	Characterizing Schema Mappings via Data Examples	2010	PODS	8.7653687e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049349003
190	Applying Model Management to Classical Meta Data Problems	2003	CIDR	0.00025768763
515	RoadRunner: Towards Automatic Data Extraction from Large Web Sites	2001	VLDB	0.00016970049
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
2,365	Hypertree Decompositions and Tractable Queries	1999	PODS	8.5654557e-05
2,390	Quasi-inverses of Schema Mappings	2007	PODS	8.5367469e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,176	Scalable Data Exchange with Functional Dependencies	2010	VLDB
2	7,071	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB
3	4,471	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS
4	8,017	Foundations of Schema Mapping Management	2010	PODS
5	12,570	Getting Unique Solution in Data Exchange	2013	VLDB
6	3,561	The Complexity of Data Exchange	2006	PODS
7	3,397	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD
8	4,406	Normalization and Optimization of Schema Mappings	2009	VLDB
9	703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS
10	4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS