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.00014660132
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
480 Clio Grows Up: From Research Prototype to Industrial Tool 2005 SIGMOD 0.00017608007
517 Schema Mappings, Data Exchange, and Metadata Management 2005 PODS 0.00016948466
793 Model Management 2.0: Manipulating Richer Mappings 2007 SIGMOD 0.00013942384
824 Data Integration: The Teenage Years 2006 VLDB 0.00013646923
1,220 Semantic Adaptation of Schema Mappings when Schemas Evolve 2005 VLDB 0.00011474444
1,458 Inverting Schema Mappings 2006 PODS 0.00010585133
1,522 Composition of Mappings Given by Embedded Dependencies 2005 PODS 0.00010367399
1,681 The iBench Integration Metadata Generator 2016 VLDB 9.8851118e-05
1,811 Supporting Executable Mappings in Model Management 2005 SIGMOD 9.5872249e-05
2,073 Graceful Database Schema Evolution: the PRISM Workbench 2008 VLDB 9.0852947e-05
2,100 XML Data Exchange: Consistency and Query Answering 2005 PODS 9.050183e-05
2,138 Logical Foundations of Peer-To-Peer Data Integration 2004 PODS 8.9737764e-05
2,321 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.6413639e-05
2,390 Quasi-inverses of Schema Mappings 2007 PODS 8.5367469e-05
2,398 HePToX: Marrying XML and Heterogeneity in Your P2P Databases 2005 VLDB 8.5218825e-05
2,408 Implementing Mapping Composition 2006 VLDB 8.5146431e-05
2,498 Compiling Mappings to Bridge Applications and Databases 2007 SIGMOD 8.3830999e-05
2,849 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 7.942171e-05
2,989 Data Exchange and Incomplete Information 2006 PODS 7.7755739e-05
3,018 The Recovery of a Schema Mapping: Bringing Exchanged Data Back 2008 PODS 7.7471023e-05
3,503 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2520222e-05
3,561 The Complexity of Data Exchange 2006 PODS 7.2055481e-05
3,614 On Reconciling Data Exchange, Data Integration, and Peer Data Management 2007 PODS 7.1605909e-05
3,974 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.8868916e-05
4,471 Data Exchange and Schema Mappings in Open and Closed Worlds 2008 PODS 6.5848385e-05
4,532 Data Exchange beyond Complete Data 2011 PODS 6.5583849e-05
4,656 Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++ 2011 VLDB 6.4827966e-05
4,704 Towards a Theory of Schema-Mapping Optimization 2008 PODS 6.4604802e-05
4,882 Value Invention in Data Exchange 2013 SIGMOD 6.3711076e-05
5,750 Answering Aggregate Queries in Data Exchange 2008 PODS 6.0073031e-05
5,981 Active Learning of GAV Schema Mappings 2018 PODS 5.9278637e-05
6,010 Reverse Data Exchange: Coping with Nulls 2009 PODS 5.9147707e-05
6,235 MapMerge: Correlating Independent Schema Mappings 2010 VLDB 5.8414951e-05
6,262 Inverting Schema Mappings: Bridging the Gap between Theory and Practice 2009 VLDB 5.8327164e-05
6,887 Query Processing under GLAV Mappings for Relational and Graph Databases 2013 VLDB 5.6550447e-05
8,017 Foundations of Schema Mapping Management 2010 PODS 5.4062707e-05
8,503 Reflections on Schema Mappings, Data Exchange, and Metadata Management 2018 PODS 5.3294549e-05
8,591 XML Schema Mappings 2009 PODS 5.3070609e-05
8,982 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 5.2433996e-05
9,664 Local Transformations and Conjunctive-Query Equivalence 2012 PODS 5.1453267e-05
9,753 Nested Dependencies: Structure and Reasoning 2014 PODS 5.1349531e-05
11,985 Structural Generalizability: The Case of Similarity Search 2021 SIGMOD 4.9793485e-05
12,169 Rewriting of Plain SO Tgds into Nested Tgds 2019 VLDB 4.9793485e-05
12,392 Recovering Exchanged Data 2015 PODS 4.9793485e-05
12,701 Certain Answers for XML Queries 2010 PODS 4.9793485e-05
12,900 Incompleteness in Information Integration 2008 VLDB 4.9793485e-05
12,947 GeRoMeSuite: A System for Holistic Generic Model Management 2007 VLDB 4.9793485e-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