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
1310
Venue
PODS
Year
2004
Pagerank
0.00014979915
Overall Rank
685 | 95.31%
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
469 Clio Grows Up: From Research Prototype to Industrial Tool 2005 SIGMOD 0.00017973925
506 Schema Mappings, Data Exchange, and Metadata Management 2005 PODS 0.0001728171
762 Model Management 2.0: Manipulating Richer Mappings 2007 SIGMOD 0.00014231163
917 Data Integration: The Teenage Years 2006 VLDB 0.00013224381
1,194 Semantic Adaptation of Schema Mappings when Schemas Evolve 2005 VLDB 0.00011730556
1,426 Inverting Schema Mappings 2006 PODS 0.00010814403
1,491 Composition of Mappings Given by Embedded Dependencies 2005 PODS 0.00010592592
1,652 The iBench Integration Metadata Generator 2016 VLDB 0.00010109142
1,770 Supporting Executable Mappings in Model Management 2005 SIGMOD 9.7967596e-05
2,038 Graceful Database Schema Evolution: the PRISM Workbench 2008 VLDB 9.2727673e-05
2,049 XML Data Exchange: Consistency and Query Answering 2005 PODS 9.255274e-05
2,100 Logical Foundations of Peer-To-Peer Data Integration 2004 PODS 9.1675595e-05
2,268 Efficient Query Reformulation in Peer Data Management Systems 2004 SIGMOD 8.8370676e-05
2,339 Quasi-inverses of Schema Mappings 2007 PODS 8.7249825e-05
2,345 HePToX: Marrying XML and Heterogeneity in Your P2P Databases 2005 VLDB 8.7171017e-05
2,352 Implementing Mapping Composition 2006 VLDB 8.7086189e-05
2,464 Compiling Mappings to Bridge Applications and Databases 2007 SIGMOD 8.5480977e-05
2,785 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 8.1236628e-05
2,934 Data Exchange and Incomplete Information 2006 PODS 7.9451055e-05
2,954 The Recovery of a Schema Mapping: Bringing Exchanged Data Back 2008 PODS 7.9234704e-05
3,433 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.4181806e-05
3,485 The Complexity of Data Exchange 2006 PODS 7.3703451e-05
3,546 On Reconciling Data Exchange, Data Integration, and Peer Data Management 2007 PODS 7.3244507e-05
3,942 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 7.0063604e-05
4,377 Data Exchange and Schema Mappings in Open and Closed Worlds 2008 PODS 6.7358004e-05
4,432 Data Exchange beyond Complete Data 2011 PODS 6.7087209e-05
4,570 Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System: PRISM++ 2011 VLDB 6.6253573e-05
4,608 Towards a Theory of Schema-Mapping Optimization 2008 PODS 6.6082619e-05
4,768 Value Invention in Data Exchange 2013 SIGMOD 6.5171839e-05
5,624 Answering Aggregate Queries in Data Exchange 2008 PODS 6.145135e-05
5,859 Active Learning of GAV Schema Mappings 2018 PODS 6.0637959e-05
5,886 Reverse Data Exchange: Coping with Nulls 2009 PODS 6.0503367e-05
6,104 MapMerge: Correlating Independent Schema Mappings 2010 VLDB 5.9754714e-05
6,130 Inverting Schema Mappings: Bridging the Gap between Theory and Practice 2009 VLDB 5.9665863e-05
6,747 Query Processing under GLAV Mappings for Relational and Graph Databases 2013 VLDB 5.784841e-05
7,859 Foundations of Schema Mapping Management 2010 PODS 5.5303517e-05
8,348 Reflections on Schema Mappings, Data Exchange, and Metadata Management 2018 PODS 5.4469775e-05
8,417 XML Schema Mappings 2009 PODS 5.4288691e-05
8,817 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 5.3637297e-05
9,483 Local Transformations and Conjunctive-Query Equivalence 2012 PODS 5.2634238e-05
9,577 Nested Dependencies: Structure and Reasoning 2014 PODS 5.2528121e-05
11,678 Structural Generalizability: The Case of Similarity Search 2021 SIGMOD 5.093636e-05
11,869 Rewriting of Plain SO Tgds into Nested Tgds 2019 VLDB 5.093636e-05
12,099 Recovering Exchanged Data 2015 PODS 5.093636e-05
12,410 Certain Answers for XML Queries 2010 PODS 5.093636e-05
12,610 Incompleteness in Information Integration 2008 VLDB 5.093636e-05
12,657 GeRoMeSuite: A System for Holistic Generic Model Management 2007 VLDB 5.093636e-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