Local Transformations and Conjunctive-Query Equivalence

Summary: Define local transformations wrt conjunctive‑query (CQ) equivalence and prove the GLAV chase (and SO‑tgd chase) is local: it preserves bounded CQ‑indistinguishability with polynomial bounds, but locality breaks with target constraints. Decompose GLAV into LAV/GAV cases to characterize when compositions are GLAV or CQ‑equivalent, and show CQ‑equivalence between an SO‑tgd and a GLAV is decidable (logical equivalence undecidable). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h4fefc233b7d56830
Venue: PODS
Year: 2012
Pagerank: 5.142891e-05
Overall Rank: 9,671 | 35.00%
DOI: 10.1145/2213556.2213583

Incoming Non-self Citations Over Time

Authors

1. Ronald Fagin (IBM)
2. Phokion G. Kolaitis (IBM; University of California Santa Cruz)

BibTeX Citation

@inproceedings{fagin_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Local Transformations and Conjunctive-Query Equivalence}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213583},
        doi = {10.1145/2213556.2213583},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fagin, Ronald and Kolaitis, Phokion G.},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,758	Nested Dependencies: Structure and Reasoning	2014	PODS	5.1325223e-05
11,091	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.00055018384
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045878061
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001694094
703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014653248
814	Composing Mappings Among Data Sources	2003	VLDB	0.000137163
1,460	Inverting Schema Mappings	2006	PODS	0.00010580166
3,019	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.7434413e-05
4,370	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.6300346e-05
4,706	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.4574226e-05
6,265	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB	5.8299552e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,975	On the Complexity of Deriving Schema Mappings from Database Instances	2008	PODS
2	703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS
3	12,788	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS
4	4,408	Normalization and Optimization of Schema Mappings	2009	VLDB
5	814	Composing Mappings Among Data Sources	2003	VLDB
6	2,392	Quasi-inverses of Schema Mappings	2007	PODS
7	5,747	Conjunctive Query Equivalence of Keyed Relational Schemas (Extended Abstract)	1997	PODS
8	4,370	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS
9	6,891	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB
10	4,706	Towards a Theory of Schema-Mapping Optimization	2008	PODS