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.1258854e-05
Overall Rank: 9,700 | 34.98%
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,790	Nested Dependencies: Structure and Reasoning	2014	PODS	5.115551e-05
11,152	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	4.9605343e-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.00055201845
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045733094
524	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016888746
708	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014605712
817	Composing Mappings Among Data Sources	2003	VLDB	0.00013671477
1,464	Inverting Schema Mappings	2006	PODS	0.00010547427
3,026	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.7180269e-05
4,392	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.6087376e-05
4,719	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.4363252e-05
6,277	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB	5.8106802e-05

Semantically Similar Papers

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