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.1453267e-05
Overall Rank: 9,664 | 35.03%
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,753	Nested Dependencies: Structure and Reasoning	2014	PODS	5.1349531e-05
11,082	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	4.9793485e-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.00055043581
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045899672
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016948466
703	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014660132
813	Composing Mappings Among Data Sources	2003	VLDB	0.00013722762
1,458	Inverting Schema Mappings	2006	PODS	0.00010585133
3,018	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.7471023e-05
4,367	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.633173e-05
4,704	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.4604802e-05
6,262	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB	5.8327164e-05

Semantically Similar Papers

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