Rewriting of Plain SO Tgds into Nested Tgds

Summary: Algorithmic rewriting of plain SO tgds into nested tgds, with a precise characterization of rewritable cases via source predicates and Skolem terms. Produces one or more nested tgds when possible, exceeding prior work by covering a larger subset and offering efficient rewriting despite exponential worst-case complexity. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12032
Venue: VLDB
Year: 2019
Pagerank: 5.093636e-05
Overall Rank: 11,869 | 18.57%
DOI: 10.14778/3342263.3342631

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Rihan Hai (Rheinisch-Westfaelische Technische Hochschule Aachen)
2. Christoph Quix (Fraunhofer Institute; Hochschule Niederrhein)

BibTeX Citation

@article{hai_vldb19,
        title = {{Rewriting of Plain SO Tgds into Nested Tgds}},
        author = {Hai, Rihan and Quix, Christoph},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {11},
        pages = {1526--1538},
        doi = {10.14778/3342263.3342631},
        url = {https://doi.org/10.14778/3342263.3342631},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
403	Querying Object-Oriented Databases	1992	SIGMOD	0.0001907249
685	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014979915
879	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00013456577
971	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00012875736
1,491	Composition of Mappings Given by Embedded Dependencies	2005	PODS	0.00010592592
1,652	The iBench Integration Metadata Generator	2016	VLDB	0.00010109142
2,256	STBenchmark: Towards a Benchmark for Mapping Systems	2008	VLDB	8.8578542e-05
2,785	Nested Mappings: Schema Mapping Reloaded	2006	VLDB	8.1236628e-05
2,913	Constance: An Intelligent Data Lake System	2016	SIGMOD	7.9684737e-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,060	Scalable Data Exchange with Functional Dependencies	2010	VLDB	6.3803935e-05
8,817	Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability	2015	PODS	5.3637297e-05
9,577	Nested Dependencies: Structure and Reasoning	2014	PODS	5.2528121e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,114	Query Rewriting for Semistructured Data	1999	SIGMOD
2	4,608	Towards a Theory of Schema-Mapping Optimization	2008	PODS
3	2,785	Nested Mappings: Schema Mapping Reloaded	2006	VLDB
4	11,584	Rewriting the Infinite Chase	2022	VLDB
5	4,768	Value Invention in Data Exchange	2013	SIGMOD
6	4,320	Normalization and Optimization of Schema Mappings	2009	VLDB
7	11,968	Stable Model Semantics for Tuple-Generating Dependencies Revisited	2017	PODS
8	1,491	Composition of Mappings Given by Embedded Dependencies	2005	PODS
9	685	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS
10	9,577	Nested Dependencies: Structure and Reasoning	2014	PODS