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.8620001e-05
Overall Rank: 3,989 | 73.27%
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
581	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016042765
1,619	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010044303
2,263	Characterizing Schema Mappings via Data Examples	2010	PODS	8.7343452e-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.00055201845
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049435337
193	Applying Model Management to Classical Meta Data Problems	2003	CIDR	0.0002567932
519	RoadRunner: Towards Automatic Data Extraction from Large Web Sites	2001	VLDB	0.00016911163
524	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016888746
708	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014605712
2,376	Hypertree Decompositions and Tractable Queries	1999	PODS	8.5345413e-05
2,402	Quasi-inverses of Schema Mappings	2007	PODS	8.5051123e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,199	Scalable Data Exchange with Functional Dependencies	2010	VLDB
2	4,493	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS
3	7,093	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB
4	8,038	Foundations of Schema Mapping Management	2010	PODS
5	12,619	Getting Unique Solution in Data Exchange	2013	VLDB
6	3,572	The Complexity of Data Exchange	2006	PODS
7	3,407	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD
8	4,428	Normalization and Optimization of Schema Mappings	2009	VLDB
9	708	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS
10	4,719	Towards a Theory of Schema-Mapping Optimization	2008	PODS