A Journey to the Frontiers of Query Rewritability

Summary: Proves the FUS/FES conjecture for a broad class of BDD theories called “local,” showing that FES plus rewritability implies uniform boundedness in that regime. Analyzes how non-local BDD theories can deviate and uncovers surprising phenomena that challenge prevailing intuitions about rewritability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: had15ef9e7fa2e547
Venue: PODS
Year: 2022
Pagerank: 4.9793485e-05
Overall Rank: 11,836 | 20.43%
DOI: 10.1145/3517804.3524163

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Piotr Ostropolski-Nalewaja (University of Wrocław)
2. Jerzy Marcinkowski (University of Wrocław)
3. David Carral (CNRS; INRIA; University of Montpellier)
4. Sebastian Rudolph (Technical University of Dresden)

BibTeX Citation

@inproceedings{ostropolskinalewaja_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{A Journey to the Frontiers of Query Rewritability}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3524163},
        doi = {10.1145/3517804.3524163},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ostropolski-Nalewaja, Piotr and Marcinkowski, Jerzy and Carral, David and Rudolph, Sebastian},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,087	No Cliques Allowed: The Next Step Towards BDD/FC Conjecture	2025	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
539	The Chase Revisited	2008	PODS	0.00016735847
2,584	Advanced Processing for Ontological Queries	2010	VLDB	8.2585389e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,441	On the BDD/FC Conjecture	2013	PODS
2	4,317	Safe Constraint Queries	1998	PODS
3	2,292	Finitely Representable Databases	1994	PODS
4	8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS
5	6,954	Querying Big Data by Accessing Small Data	2015	PODS
6	4,367	Locally Consistent Transformations and Query Answering in Data Exchange	2004	PODS
7	14,734	Expressibility of Bounded-Arity Fixed-Point Query Hierarchies	1989	PODS
8	7,230	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS
9	2,790	Processing First-Order Queries under Limited Access Patterns	2004	PODS
10	12,324	Bounded Query Rewriting Using Views	2016	PODS