Generalized Schema-Mappings: From Termination To Tractability

Summary: Generalizes schema-mappings with semantics (Soundness, Completeness, Laconicity) shown equal to cores of universal solutions and extended to nulls/equality. Introduces TOC, an oblivious-chase termination criterion strictly generalizing weak‑acyclicity, gives a new PTIME algorithm, and a decidable PTIME relaxation called Super‑weak Acyclicity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: haf9db2cf93929c4c
Venue: PODS
Year: 2009
Pagerank: 0.00010189889
Overall Rank: 1,575 | 89.42%
DOI: 10.1145/1559795.1559799

Incoming Non-self Citations Over Time

Authors

1. Bruno Marnette (University of Oxford)

BibTeX Citation

@inproceedings{marnette_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Generalized Schema-Mappings: From Termination To Tractability}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559799},
        doi = {10.1145/1559795.1559799},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Marnette, Bruno},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,365	Dependencies for Graphs	2017	PODS	8.5625389e-05
2,675	Benchmarking the Chase	2017	PODS	8.1442721e-05
3,560	++Spicy: an Open-Source Tool for Second-Generation Schema Mapping and Data Exchange	2011	VLDB	7.2043062e-05
4,447	Chase Termination for Guarded Existential Rules	2015	PODS	6.5945135e-05
4,461	Semantic Query Optimization in the Presence of Types	2010	PODS	6.5870588e-05
5,177	Scalable Data Exchange with Functional Dependencies	2010	VLDB	6.2385872e-05
6,886	Stratification Criteria and Rewriting Techniques for Checking Chase Termination	2011	VLDB	5.6544151e-05
7,187	Exploiting Equality Generating Dependencies in Checking Chase Termination	2016	VLDB	5.5886012e-05
7,558	Flag & Check: Data Access with Monadically Defined Queries	2013	PODS	5.4954839e-05
8,105	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	5.3917406e-05
8,951	Chase Termination: A Constraints Rewriting Approach	2010	VLDB	5.2517655e-05
9,384	Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study	2023	VLDB	5.1843659e-05
9,385	Non-Uniformly Terminating Chase: Size and Complexity	2022	PODS	5.1843659e-05
9,709	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB	5.1354025e-05
11,101	Restricted Chase Termination: You Want More than Fairness	2025	PODS	4.9769913e-05
11,483	Chase Termination Beyond Polynomial Time	2024	PODS	4.9769913e-05
11,688	Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying	2023	PODS	4.9769913e-05
12,059	All-Instances Restricted Chase Termination	2020	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
392	Data Exchange: Getting to the Core	2003	PODS	0.00019215652
539	The Chase Revisited	2008	PODS	0.0001672793
2,596	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.2387266e-05
3,368	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.3687982e-05
4,473	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS	6.5817215e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,576	Getting Unique Solution in Data Exchange	2013	VLDB
2	3,019	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS
3	2,990	Data Exchange and Incomplete Information	2006	PODS
4	7,364	Schema Mappings for Data Graphs	2017	PODS
5	703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS
6	3,564	The Complexity of Data Exchange	2006	PODS
7	7,073	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB
8	4,473	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS
9	3,975	On the Complexity of Deriving Schema Mappings from Database Instances	2008	PODS
10	4,706	Towards a Theory of Schema-Mapping Optimization	2008	PODS