Database Paper Browser

Back to papers

Composing Schema Mappings: Second-Order Dependencies to the Rescue

Summary: Composition of s-t tgds can transcend first-order: some compositions are not definable by any (finite or infinite) s-t tgds or by LFP, and composition queries can be NP-complete. Introduces second-order tgds (existential SO with functions and essential equalities) as the right closure: compositions of s-t tgds (and of SO-tgds) are SO-tgds, and an extended chase yields PTIME universal solutions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1311
Venue
PODS
Year
2004
Pagerank
0.00016255689
Overall Rank
822 | 94.29%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 45 of 45 citing papers.

Rank Citing Paper Year Venue Pagerank
483 Clio Grows Up: From Research Prototype to Industrial Tool 2005 SIGMOD 0.00022125107
621 Schema Mappings, Data Exchange, and Metadata Management 2005 PODS 0.00019005115
893 Data Integration: The Teenage Years 2006 VLDB 0.00015558352
1,078 Model Management 2.0: Manipulating Richer Mappings 2007 SIGMOD 0.00014245848
1,186 Semantic Adaptation of Schema Mappings when Schemas Evolve 2005 VLDB 0.00013443953
1,489 Supporting Executable Mappings in Model Management 2005 SIGMOD 0.00011699282
1,494 Inverting Schema Mappings 2006 PODS 0.00011693148
1,677 Graceful Database Schema Evolution: the PRISM Workbench 2008 VLDB 0.00010939366
1,742 Composition of Mappings Given by Embedded Dependencies 2005 PODS 0.00010708408
1,769 Logical Foundations of Peer-To-Peer Data Integration 2004 PODS 0.00010619921
1,883 The iBench Integration Metadata Generator 2016 VLDB 0.00010215862
2,195 HePToX: Marrying XML and Heterogeneity in Your P2P Databases 2005 VLDB 9.3136935e-05
2,211 XML Data Exchange: Consistency and Query Answering 2005 PODS 9.2771941e-05
2,252 Compiling Mappings to Bridge Applications and Databases 2007 SIGMOD 9.1976999e-05
2,479 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.6909119e-05
2,692 Quasi-inverses of Schema Mappings 2007 PODS 8.2908844e-05
2,746 Implementing Mapping Composition 2006 VLDB 8.1878278e-05
2,904 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 7.9355829e-05
3,011 Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++ 2011 VLDB 7.7183382e-05
3,324 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2213002e-05
3,389 The Recovery of a Schema Mapping: Bringing Exchanged Data Back 2008 PODS 7.157044e-05
3,502 Data Exchange and Incomplete Information 2006 PODS 7.0366655e-05
3,643 The Complexity of Data Exchange 2006 PODS 6.8862411e-05
3,921 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.6301252e-05
3,937 On Reconciling Data Exchange, Data Integration, and Peer Data Management 2007 PODS 6.6159574e-05
4,466 Data Exchange and Schema Mappings in Open and Closed Worlds 2008 PODS 6.1601459e-05
4,978 Towards a Theory of Schema-Mapping Optimization 2008 PODS 5.7881299e-05
5,249 Value Invention in Data Exchange 2013 SIGMOD 5.6054145e-05
5,717 Query Processing under GLAV Mappings for Relational and Graph Databases 2013 VLDB 5.3553228e-05
5,767 Data Exchange beyond Complete Data 2011 PODS 5.3334039e-05
5,897 Answering Aggregate Queries in Data Exchange 2008 PODS 5.2842198e-05
6,145 Reverse Data Exchange: Coping with Nulls 2009 PODS 5.1886368e-05
6,155 MapMerge: Correlating Independent Schema Mappings 2010 VLDB 5.1802715e-05
6,349 Inverting Schema Mappings: Bridging the Gap between Theory and Practice 2009 VLDB 5.101852e-05
7,649 Foundations of Schema Mapping Management 2010 PODS 4.6884158e-05
8,190 XML Schema Mappings 2009 PODS 4.5641911e-05
8,815 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 4.4432234e-05
9,334 Local Transformations and Conjunctive-Query Equivalence 2012 PODS 4.3556432e-05
9,422 Nested Dependencies: Structure and Reasoning 2014 PODS 4.3441378e-05
11,480 Structural Generalizability: The Case of Similarity Search 2021 SIGMOD 4.1945683e-05
11,674 Rewriting of Plain SO Tgds into Nested Tgds 2019 VLDB 4.1945683e-05
11,900 Recovering Exchanged Data 2015 PODS 4.1945683e-05
12,215 Certain Answers for XML Queries 2010 PODS 4.1945683e-05
12,416 Incompleteness in Information Integration 2008 VLDB 4.1945683e-05
12,463 GeRoMeSuite: A System for Holistic Generic Model Management 2007 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,815 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 4.4432234e-05
5,295 Scalable Data Exchange with Functional Dependencies 2010 VLDB 5.580776e-05
1,186 Semantic Adaptation of Schema Mappings when Schemas Evolve 2005 VLDB 0.00013443953
11,762 Stable Model Semantics for Tuple-Generating Dependencies Revisited 2017 PODS 4.1945683e-05
5,249 Value Invention in Data Exchange 2013 SIGMOD 5.6054145e-05
11,674 Rewriting of Plain SO Tgds into Nested Tgds 2019 VLDB 4.1945683e-05
4,752 Normalization and Optimization of Schema Mappings 2009 VLDB 5.9481448e-05
3,921 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.6301252e-05
4,978 Towards a Theory of Schema-Mapping Optimization 2008 PODS 5.7881299e-05
1,742 Composition of Mappings Given by Embedded Dependencies 2005 PODS 0.00010708408