DBScholar

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
h032b69f9a9c84423
Venue
PODS
Year
2004
Pagerank
0.00014653248
Overall Rank
703 | 95.28%
DOI
10.1145/1055558.1055572

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{fagin_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Composing Schema Mappings: Second-Order Dependencies to the Rescue}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055572},
        doi = {10.1145/1055558.1055572},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fagin, Ronald and Kolaitis, Phokion G. and Tan, Wang-Chiew and Popa, Lucian},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 47 of 47 citing papers.

Rank Citing Paper Year Venue Pagerank
481 Clio Grows Up: From Research Prototype to Industrial Tool 2005 SIGMOD 0.00017600067
517 Schema Mappings, Data Exchange, and Metadata Management 2005 PODS 0.0001694094
793 Model Management 2.0: Manipulating Richer Mappings 2007 SIGMOD 0.00013935809
824 Data Integration: The Teenage Years 2006 VLDB 0.00013641217
1,222 Semantic Adaptation of Schema Mappings when Schemas Evolve 2005 VLDB 0.00011469037
1,460 Inverting Schema Mappings 2006 PODS 0.00010580166
1,522 Composition of Mappings Given by Embedded Dependencies 2005 PODS 0.00010362522
1,683 The iBench Integration Metadata Generator 2016 VLDB 9.8804382e-05
1,811 Supporting Executable Mappings in Model Management 2005 SIGMOD 9.583052e-05
2,075 Graceful Database Schema Evolution: the PRISM Workbench 2008 VLDB 9.0810058e-05
2,101 XML Data Exchange: Consistency and Query Answering 2005 PODS 9.0459184e-05
2,140 Logical Foundations of Peer-To-Peer Data Integration 2004 PODS 8.9696138e-05
2,323 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.637314e-05
2,392 Quasi-inverses of Schema Mappings 2007 PODS 8.5327323e-05
2,399 HePToX: Marrying XML and Heterogeneity in Your P2P Databases 2005 VLDB 8.5178546e-05
2,410 Implementing Mapping Composition 2006 VLDB 8.5106165e-05
2,500 Compiling Mappings to Bridge Applications and Databases 2007 SIGMOD 8.3791317e-05
2,850 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 7.9384121e-05
2,990 Data Exchange and Incomplete Information 2006 PODS 7.7719132e-05
3,019 The Recovery of a Schema Mapping: Bringing Exchanged Data Back 2008 PODS 7.7434413e-05
3,503 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2485903e-05
3,564 The Complexity of Data Exchange 2006 PODS 7.2021386e-05
3,614 On Reconciling Data Exchange, Data Integration, and Peer Data Management 2007 PODS 7.1572016e-05
3,975 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.8839105e-05
4,473 Data Exchange and Schema Mappings in Open and Closed Worlds 2008 PODS 6.5817215e-05
4,533 Data Exchange beyond Complete Data 2011 PODS 6.5552806e-05
4,658 Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++ 2011 VLDB 6.4797461e-05
4,706 Towards a Theory of Schema-Mapping Optimization 2008 PODS 6.4574226e-05
4,884 Value Invention in Data Exchange 2013 SIGMOD 6.3680919e-05
5,751 Answering Aggregate Queries in Data Exchange 2008 PODS 6.0044594e-05
5,982 Active Learning of GAV Schema Mappings 2018 PODS 5.9250649e-05
6,010 Reverse Data Exchange: Coping with Nulls 2009 PODS 5.9119713e-05
6,238 MapMerge: Correlating Independent Schema Mappings 2010 VLDB 5.83873e-05
6,265 Inverting Schema Mappings: Bridging the Gap between Theory and Practice 2009 VLDB 5.8299552e-05
6,891 Query Processing under GLAV Mappings for Relational and Graph Databases 2013 VLDB 5.6523677e-05
8,022 Foundations of Schema Mapping Management 2010 PODS 5.4037117e-05
8,508 Reflections on Schema Mappings, Data Exchange, and Metadata Management 2018 PODS 5.3269436e-05
8,598 XML Schema Mappings 2009 PODS 5.3045486e-05
8,993 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 5.2409174e-05
9,671 Local Transformations and Conjunctive-Query Equivalence 2012 PODS 5.142891e-05
9,758 Nested Dependencies: Structure and Reasoning 2014 PODS 5.1325223e-05
11,991 Structural Generalizability: The Case of Similarity Search 2021 SIGMOD 4.9769913e-05
12,175 Rewriting of Plain SO Tgds into Nested Tgds 2019 VLDB 4.9769913e-05
12,398 Recovering Exchanged Data 2015 PODS 4.9769913e-05
12,707 Certain Answers for XML Queries 2010 PODS 4.9769913e-05
12,906 Incompleteness in Information Integration 2008 VLDB 4.9769913e-05
12,953 GeRoMeSuite: A System for Holistic Generic Model Management 2007 VLDB 4.9769913e-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