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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,119 | The Complexity of Causality and Responsibility for Query Answers and non-Answers | 2011 | VLDB | 0.0001386199 |
| 1,699 | Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases | 2011 | SIGMOD | 0.00010858983 |
| 2,124 | Characterizing Schema Mappings via Data Examples | 2010 | PODS | 9.4912951e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 48 | Data Integration: A Theoretical Perspective | 2002 | PODS | 0.00069720859 |
| 49 | Consistent Query Answers in Inconsistent Databases | 1999 | PODS | 0.00067660624 |
| 188 | Applying Model Management to Classical Meta Data Problems | 2003 | CIDR | 0.00035968389 |
| 533 | RoadRunner: Towards Automatic Data Extraction from Large Web Sites | 2001 | VLDB | 0.00020757722 |
| 621 | Schema Mappings, Data Exchange, and Metadata Management | 2005 | PODS | 0.00019005115 |
| 822 | Composing Schema Mappings: Second-Order Dependencies to the Rescue | 2004 | PODS | 0.00016255689 |
| 2,692 | Quasi-inverses of Schema Mappings | 2007 | PODS | 8.2908844e-05 |
| 2,796 | Hypertree Decompositions and Tractable Queries | 1999 | PODS | 8.1112658e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,295 | Scalable Data Exchange with Functional Dependencies | 2010 | VLDB | 5.580776e-05 |
| 4,466 | Data Exchange and Schema Mappings in Open and Closed Worlds | 2008 | PODS | 6.1601459e-05 |
| 7,078 | Laconic Schema Mappings: Computing the Core with SQL Queries | 2009 | VLDB | 4.8424931e-05 |
| 7,649 | Foundations of Schema Mapping Management | 2010 | PODS | 4.6884158e-05 |
| 12,082 | Getting Unique Solution in Data Exchange | 2013 | VLDB | 4.1945683e-05 |
| 3,643 | The Complexity of Data Exchange | 2006 | PODS | 6.8862411e-05 |
| 4,752 | Normalization and Optimization of Schema Mappings | 2009 | VLDB | 5.9481448e-05 |
| 3,866 | Designing and Refining Schema Mappings via Data Examples | 2011 | SIGMOD | 6.6837e-05 |
| 822 | Composing Schema Mappings: Second-Order Dependencies to the Rescue | 2004 | PODS | 0.00016255689 |
| 4,978 | Towards a Theory of Schema-Mapping Optimization | 2008 | PODS | 5.7881299e-05 |