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: 1473
Venue: PODS
Year: 2009
Pagerank: 0.00010720323
Overall Rank: 1,736 | 87.93%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Bruno Marnette

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,527	Dependencies for Graphs	2017	PODS	8.5954406e-05
2,727	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2216778e-05
3,004	Benchmarking the Chase	2017	PODS	7.7314538e-05
3,830	++Spicy: an Open-Source Tool for Second-Generation Schema Mapping and Data Exchange	2011	VLDB	6.7193951e-05
3,909	Chase Termination for Guarded Existential Rules	2015	PODS	6.6375375e-05
5,295	Scalable Data Exchange with Functional Dependencies	2010	VLDB	5.580776e-05
6,470	Exploiting Equality Generating Dependencies in Checking Chase Termination	2016	VLDB	5.0513478e-05
6,552	Stratification Criteria and Rewriting Techniques for Checking Chase Termination	2011	VLDB	5.0164865e-05
6,848	Flag & Check: Data Access with Monadically Defined Queries	2013	PODS	4.9089877e-05
7,509	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	4.7180617e-05
8,484	Chase Termination: A Constraints Rewriting Approach	2010	VLDB	4.5007769e-05
9,045	Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study	2023	VLDB	4.4039656e-05
9,046	Non-Uniformly Terminating Chase: Size and Complexity	2022	PODS	4.4039656e-05
9,377	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB	4.347117e-05
10,356	Restricted Chase Termination: You Want More than Fairness	2025	PODS	4.1945683e-05
10,908	Chase Termination Beyond Polynomial Time	2024	PODS	4.1945683e-05
11,160	Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying	2023	PODS	4.1945683e-05
11,553	All-Instances Restricted Chase Termination	2020	PODS	4.1945683e-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
494	Data Exchange: Getting to the Core	2003	PODS	0.00021805832
698	The Chase Revisited	2008	PODS	0.00018030148
2,829	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.0546963e-05
3,424	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.110765e-05
4,466	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS	6.1601459e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,082	Getting Unique Solution in Data Exchange	2013	VLDB	4.1945683e-05
3,389	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.157044e-05
3,502	Data Exchange and Incomplete Information	2006	PODS	7.0366655e-05
7,436	Schema Mappings for Data Graphs	2017	PODS	4.7311358e-05
822	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00016255689
3,643	The Complexity of Data Exchange	2006	PODS	6.8862411e-05
7,078	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB	4.8424931e-05
4,466	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS	6.1601459e-05
3,921	On the Complexity of Deriving Schema Mappings from Database Instances	2008	PODS	6.6301252e-05
4,978	Towards a Theory of Schema-Mapping Optimization	2008	PODS	5.7881299e-05