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.00013851012 |
| 1,698 | Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases | 2011 | SIGMOD | 0.00010857033 |
| 2,130 | Characterizing Schema Mappings via Data Examples | 2010 | PODS | 9.4784293e-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 |
|---|---|---|---|---|
| 47 | Data Integration: A Theoretical Perspective | 2002 | PODS | 0.00069691761 |
| 49 | Consistent Query Answers in Inconsistent Databases | 1999 | PODS | 0.00067607389 |
| 188 | Applying Model Management to Classical Meta Data Problems | 2003 | CIDR | 0.00035935715 |
| 534 | RoadRunner: Towards Automatic Data Extraction from Large Web Sites | 2001 | VLDB | 0.00020739037 |
| 620 | Schema Mappings, Data Exchange, and Metadata Management | 2005 | PODS | 0.00018983367 |
| 818 | Composing Schema Mappings: Second-Order Dependencies to the Rescue | 2004 | PODS | 0.00016240185 |
| 2,694 | Quasi-inverses of Schema Mappings | 2007 | PODS | 8.2836784e-05 |
| 2,804 | Hypertree Decompositions and Tractable Queries | 1999 | PODS | 8.1039107e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,299 | Scalable Data Exchange with Functional Dependencies | 2010 | VLDB | 5.5751426e-05 |
| 4,468 | Data Exchange and Schema Mappings in Open and Closed Worlds | 2008 | PODS | 6.1543925e-05 |
| 7,072 | Laconic Schema Mappings: Computing the Core with SQL Queries | 2009 | VLDB | 4.8378485e-05 |
| 7,650 | Foundations of Schema Mapping Management | 2010 | PODS | 4.6839185e-05 |
| 12,090 | Getting Unique Solution in Data Exchange | 2013 | VLDB | 4.1905499e-05 |
| 3,647 | The Complexity of Data Exchange | 2006 | PODS | 6.8796285e-05 |
| 3,872 | Designing and Refining Schema Mappings via Data Examples | 2011 | SIGMOD | 6.6737583e-05 |
| 4,750 | Normalization and Optimization of Schema Mappings | 2009 | VLDB | 5.9424107e-05 |
| 818 | Composing Schema Mappings: Second-Order Dependencies to the Rescue | 2004 | PODS | 0.00016240185 |
| 4,980 | Towards a Theory of Schema-Mapping Optimization | 2008 | PODS | 5.7825422e-05 |