Composition of Mappings Given by Embedded Dependencies

Summary: Gives algorithms and sufficient conditions for composing mappings specified by embedded, full, or Skolemized SO dependencies (beyond source→target). Shows limits: full deps not closed, non‑source→target SO deps fail closure under restricted composition, and deciding expressibility is undecidable. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h5c9821a87ae53238
Venue: PODS
Year: 2005
Pagerank: 0.00010367399
Overall Rank: 1,522 | 89.77%
DOI: 10.1145/1065167.1065189

Incoming Non-self Citations Over Time

Authors

1. Alan Nash (Microsoft; University of California San Diego)
2. Philip A. Bernstein (Microsoft)
3. Sergey Melnik (Microsoft)

BibTeX Citation

@inproceedings{nash_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Composition of Mappings Given by Embedded Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065189},
        doi = {10.1145/1065167.1065189},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Nash, Alan and Bernstein, Philip A. and Melnik, Sergey},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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,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,390	Quasi-inverses of Schema Mappings	2007	PODS	8.5367469e-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
3,561	The Complexity of Data Exchange	2006	PODS	7.2055481e-05
4,471	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS	6.5848385e-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,361	Interactive Schema Translation with Instance-Level Mappings	2005	VLDB	6.1611691e-05
5,750	Answering Aggregate Queries in Data Exchange	2008	PODS	6.0073031e-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
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
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

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
190	Applying Model Management to Classical Meta Data Problems	2003	CIDR	0.00025768763
703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014660132
813	Composing Mappings Among Data Sources	2003	VLDB	0.00013722762
905	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00013170652
1,208	Towards a Sound View Integration Methodology	1983	PODS	0.00011538101

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,169	Rewriting of Plain SO Tgds into Nested Tgds	2019	VLDB
2	1,458	Inverting Schema Mappings	2006	PODS
3	7,127	Embedded Join Dependencies As A Tool For Decomposing Full Join Dependencies	1985	PODS
4	3,475	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB
5	4,406	Normalization and Optimization of Schema Mappings	2009	VLDB
6	1,220	Semantic Adaptation of Schema Mappings when Schemas Evolve	2005	VLDB
7	2,408	Implementing Mapping Composition	2006	VLDB
8	4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS
9	9,753	Nested Dependencies: Structure and Reasoning	2014	PODS
10	703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS