Nested Dependencies: Structure and Reasoning

Summary: Systematic investigation of nested GLAV mappings (nested tgds) for data exchange, focusing on reasoning, algorithms, and structural properties. Key results: decidability of the implication problem for nested tgds, structural analysis of cores, techniques separating nested from SO tgds, and a decidable test whether a nested GLAV mapping is equivalent to a (non-nested) GLAV mapping. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hb78dfab2a9e28009
Venue: PODS
Year: 2014
Pagerank: 5.1349531e-05
Overall Rank: 9,753 | 34.43%
DOI: 10.1145/2594538.2594544

Incoming Non-self Citations Over Time

Authors

1. Phokion G. Kolaitis (IBM; University of California Santa Cruz)
2. Reinhard Pichler (Vienna University of Technology)
3. Emanuel Sallinger (Vienna University of Technology)
4. Vadim Savenkov (Vienna University of Technology)

BibTeX Citation

@inproceedings{kolaitis_pods14,
        address = {New York, NY, USA},
        series = {{PODS} '14},
        title = {{Nested Dependencies: Structure and Reasoning}},
        url = {https://dl.acm.org/doi/10.1145/2594538.2594544},
        doi = {10.1145/2594538.2594544},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kolaitis, Phokion G. and Pichler, Reinhard and Sallinger, Emanuel and Savenkov, Vadim},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,503	Reflections on Schema Mappings, Data Exchange, and Metadata Management	2018	PODS	5.3294549e-05
8,982	Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability	2015	PODS	5.2433996e-05
12,169	Rewriting of Plain SO Tgds into Nested Tgds	2019	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
392	Data Exchange: Getting to the Core	2003	PODS	0.0001922472
703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014660132
813	Composing Mappings Among Data Sources	2003	VLDB	0.00013722762
2,849	Nested Mappings: Schema Mapping Reloaded	2006	VLDB	7.942171e-05
3,018	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.7471023e-05
4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.4604802e-05
9,664	Local Transformations and Conjunctive-Query Equivalence	2012	PODS	5.1453267e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	813	Composing Mappings Among Data Sources	2003	VLDB
2	4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS
3	9,664	Local Transformations and Conjunctive-Query Equivalence	2012	PODS
4	6,887	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB
5	3,397	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD
6	2,849	Nested Mappings: Schema Mapping Reloaded	2006	VLDB
7	4,582	Reasoning about Nested Functional Dependencies	1999	PODS
8	703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS
9	1,522	Composition of Mappings Given by Embedded Dependencies	2005	PODS
10	12,169	Rewriting of Plain SO Tgds into Nested Tgds	2019	VLDB