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: 1575
Venue: PODS
Year: 2012
Pagerank: 5.2634238e-05
Overall Rank: 9,483 | 34.94%
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,577	Nested Dependencies: Structure and Reasoning	2014	PODS	5.2528121e-05
10,639	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	5.093636e-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
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
685	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014979915
788	Composing Mappings Among Data Sources	2003	VLDB	0.00014031294
1,426	Inverting Schema Mappings	2006	PODS	0.00010814403
2,954	The Recovery of a Schema Mapping: Bringing Exchanged Data Back	2008	PODS	7.9234704e-05
4,281	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS	6.7848108e-05
4,608	Towards a Theory of Schema-Mapping Optimization	2008	PODS	6.6082619e-05
6,130	Inverting Schema Mappings: Bridging the Gap between Theory and Practice	2009	VLDB	5.9665863e-05

Semantically Similar Papers

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