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: 1442
Venue: PODS
Year: 2008
Pagerank: 7.0063604e-05
Overall Rank: 3,942 | 72.96%
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
605	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00015839628
1,594	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010252583
2,215	Characterizing Schema Mappings via Data Examples	2010	PODS	8.93781e-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
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
183	Applying Model Management to Classical Meta Data Problems	2003	CIDR	0.00026283359
503	RoadRunner: Towards Automatic Data Extraction from Large Web Sites	2001	VLDB	0.00017314037
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
685	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014979915
2,330	Hypertree Decompositions and Tractable Queries	1999	PODS	8.7447066e-05
2,339	Quasi-inverses of Schema Mappings	2007	PODS	8.7249825e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,060	Scalable Data Exchange with Functional Dependencies	2010	VLDB
2	4,377	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS
3	6,933	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB
4	7,859	Foundations of Schema Mapping Management	2010	PODS
5	12,279	Getting Unique Solution in Data Exchange	2013	VLDB
6	3,485	The Complexity of Data Exchange	2006	PODS
7	3,341	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD
8	4,320	Normalization and Optimization of Schema Mappings	2009	VLDB
9	685	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS
10	4,608	Towards a Theory of Schema-Mapping Optimization	2008	PODS