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.00016240185
Overall Rank
818 | 94.32%
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.00022101908
620 Schema Mappings, Data Exchange, and Metadata Management 2005 PODS 0.00018983367
889 Data Integration: The Teenage Years 2006 VLDB 0.00015548507
1,075 Model Management 2.0: Manipulating Richer Mappings 2007 SIGMOD 0.00014233255
1,186 Semantic Adaptation of Schema Mappings when Schemas Evolve 2005 VLDB 0.00013432464
1,490 Supporting Executable Mappings in Model Management 2005 SIGMOD 0.00011687193
1,493 Inverting Schema Mappings 2006 PODS 0.00011682325
1,677 Graceful Database Schema Evolution: the PRISM Workbench 2008 VLDB 0.00010929631
1,739 Composition of Mappings Given by Embedded Dependencies 2005 PODS 0.00010698182
1,767 Logical Foundations of Peer-To-Peer Data Integration 2004 PODS 0.00010609587
1,885 The iBench Integration Metadata Generator 2016 VLDB 0.00010206139
2,202 HePToX: Marrying XML and Heterogeneity in Your P2P Databases 2005 VLDB 9.3038561e-05
2,217 XML Data Exchange: Consistency and Query Answering 2005 PODS 9.2682054e-05
2,252 Compiling Mappings to Bridge Applications and Databases 2007 SIGMOD 9.1887678e-05
2,480 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.682497e-05
2,694 Quasi-inverses of Schema Mappings 2007 PODS 8.2836784e-05
2,749 Implementing Mapping Composition 2006 VLDB 8.18014e-05
2,909 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 7.9282234e-05
3,008 Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++ 2011 VLDB 7.72402e-05
3,325 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2149375e-05
3,388 The Recovery of a Schema Mapping: Bringing Exchanged Data Back 2008 PODS 7.1502016e-05
3,507 Data Exchange and Incomplete Information 2006 PODS 7.0299158e-05
3,647 The Complexity of Data Exchange 2006 PODS 6.8796285e-05
3,922 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.6238781e-05
3,940 On Reconciling Data Exchange, Data Integration, and Peer Data Management 2007 PODS 6.6096825e-05
4,468 Data Exchange and Schema Mappings in Open and Closed Worlds 2008 PODS 6.1543925e-05
4,980 Towards a Theory of Schema-Mapping Optimization 2008 PODS 5.7825422e-05
5,252 Value Invention in Data Exchange 2013 SIGMOD 5.6002884e-05
5,727 Query Processing under GLAV Mappings for Relational and Graph Databases 2013 VLDB 5.3501787e-05
5,775 Data Exchange beyond Complete Data 2011 PODS 5.3282847e-05
5,901 Answering Aggregate Queries in Data Exchange 2008 PODS 5.2791434e-05
6,146 Reverse Data Exchange: Coping with Nulls 2009 PODS 5.1840756e-05
6,158 MapMerge: Correlating Independent Schema Mappings 2010 VLDB 5.1753051e-05
6,346 Inverting Schema Mappings: Bridging the Gap between Theory and Practice 2009 VLDB 5.0969624e-05
7,650 Foundations of Schema Mapping Management 2010 PODS 4.6839185e-05
8,190 XML Schema Mappings 2009 PODS 4.5598146e-05
8,816 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 4.438964e-05
9,339 Local Transformations and Conjunctive-Query Equivalence 2012 PODS 4.351469e-05
9,428 Nested Dependencies: Structure and Reasoning 2014 PODS 4.3399748e-05
11,484 Structural Generalizability: The Case of Similarity Search 2021 SIGMOD 4.1905499e-05
11,679 Rewriting of Plain SO Tgds into Nested Tgds 2019 VLDB 4.1905499e-05
11,908 Recovering Exchanged Data 2015 PODS 4.1905499e-05
12,223 Certain Answers for XML Queries 2010 PODS 4.1905499e-05
12,425 Incompleteness in Information Integration 2008 VLDB 4.1905499e-05
12,472 GeRoMeSuite: A System for Holistic Generic Model Management 2007 VLDB 4.1905499e-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,816 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 4.438964e-05
5,299 Scalable Data Exchange with Functional Dependencies 2010 VLDB 5.5751426e-05
1,186 Semantic Adaptation of Schema Mappings when Schemas Evolve 2005 VLDB 0.00013432464
11,770 Stable Model Semantics for Tuple-Generating Dependencies Revisited 2017 PODS 4.1905499e-05
5,252 Value Invention in Data Exchange 2013 SIGMOD 5.6002884e-05
11,679 Rewriting of Plain SO Tgds into Nested Tgds 2019 VLDB 4.1905499e-05
4,750 Normalization and Optimization of Schema Mappings 2009 VLDB 5.9424107e-05
3,922 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.6238781e-05
4,980 Towards a Theory of Schema-Mapping Optimization 2008 PODS 5.7825422e-05
1,739 Composition of Mappings Given by Embedded Dependencies 2005 PODS 0.00010698182