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.00010711961
Overall Rank: 1,737 | 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,517	Dependencies for Graphs	2017	PODS	8.6058545e-05
2,732	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2137395e-05
3,007	Benchmarking the Chase	2017	PODS	7.7243073e-05
3,835	++Spicy: an Open-Source Tool for Second-Generation Schema Mapping and Data Exchange	2011	VLDB	6.7129526e-05
3,913	Chase Termination for Guarded Existential Rules	2015	PODS	6.6311557e-05
5,299	Scalable Data Exchange with Functional Dependencies	2010	VLDB	5.5751426e-05
6,459	Exploiting Equality Generating Dependencies in Checking Chase Termination	2016	VLDB	5.048352e-05
6,549	Stratification Criteria and Rewriting Techniques for Checking Chase Termination	2011	VLDB	5.0116687e-05
6,847	Flag & Check: Data Access with Monadically Defined Queries	2013	PODS	4.9042778e-05
7,508	Optimizing the Chase: Scalable Data Integration under Constraints	2014	VLDB	4.7135369e-05
8,483	Chase Termination: A Constraints Rewriting Approach	2010	VLDB	4.4964612e-05
9,045	Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study	2023	VLDB	4.3997447e-05
9,046	Non-Uniformly Terminating Chase: Size and Complexity	2022	PODS	4.3997447e-05
9,385	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB	4.342951e-05
10,368	Restricted Chase Termination: You Want More than Fairness	2025	PODS	4.1905499e-05
10,912	Chase Termination Beyond Polynomial Time	2024	PODS	4.1905499e-05
11,163	Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying	2023	PODS	4.1905499e-05
11,557	All-Instances Restricted Chase Termination	2020	PODS	4.1905499e-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
493	Data Exchange: Getting to the Core	2003	PODS	0.00021782199
695	The Chase Revisited	2008	PODS	0.00018013323
2,835	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.0468415e-05
3,426	Data Exchange: Computing Cores in Polynomial Time	2006	PODS	7.1040993e-05
4,468	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS	6.1543925e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,090	Getting Unique Solution in Data Exchange	2013	VLDB	4.1905499e-05
3,388	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.1502016e-05
3,507	Data Exchange and Incomplete Information	2006	PODS	7.0299158e-05
7,435	Schema Mappings for Data Graphs	2017	PODS	4.7265981e-05
3,647	The Complexity of Data Exchange	2006	PODS	6.8796285e-05
818	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00016240185
7,072	Laconic Schema Mappings: Computing the Core with SQL Queries	2009	VLDB	4.8378485e-05
4,468	Data Exchange and Schema Mappings in Open and Closed Worlds	2008	PODS	6.1543925e-05
3,922	On the Complexity of Deriving Schema Mappings from Database Instances	2008	PODS	6.6238781e-05
4,980	Towards a Theory of Schema-Mapping Optimization	2008	PODS	5.7825422e-05