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)
Incoming Non-self Citations Over Time
Authors
- 1. Ronald Fagin (IBM)
- 2. Phokion G. Kolaitis (University of California Santa Cruz)
- 3. Wang-Chiew Tan (University of California Santa Cruz)
- 4. Lucian Popa (IBM)
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.
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 |
|---|---|---|---|---|
| 1 | 8,817 | Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability | 2015 | PODS |
| 2 | 5,060 | Scalable Data Exchange with Functional Dependencies | 2010 | VLDB |
| 3 | 1,194 | Semantic Adaptation of Schema Mappings when Schemas Evolve | 2005 | VLDB |
| 4 | 11,968 | Stable Model Semantics for Tuple-Generating Dependencies Revisited | 2017 | PODS |
| 5 | 4,768 | Value Invention in Data Exchange | 2013 | SIGMOD |
| 6 | 11,869 | Rewriting of Plain SO Tgds into Nested Tgds | 2019 | VLDB |
| 7 | 4,320 | Normalization and Optimization of Schema Mappings | 2009 | VLDB |
| 8 | 3,942 | On the Complexity of Deriving Schema Mappings from Database Instances | 2008 | PODS |
| 9 | 4,608 | Towards a Theory of Schema-Mapping Optimization | 2008 | PODS |
| 10 | 1,491 | Composition of Mappings Given by Embedded Dependencies | 2005 | PODS |