Rewrite Rules for Search Database Systems

Summary: Models search-query augmentation as rewrite programs (hedge-rewriting) that produce a least fixpoint (lfp) set of alternative queries and introduces lfp‑convergence (finiteness of each lfp). Shows lfp‑convergence undecidable, gives a polynomial-time decidable safety condition that guarantees convergence and validates it on a deployed rewrite program. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1558
Venue: PODS
Year: 2011
Pagerank: -
Overall Rank: 13,684 | 6.12%
DOI: 10.1145/1989284.1989322

Incoming Non-self Citations Over Time

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

Authors

1. Ronald Fagin (IBM)
2. Benny Kimelfeld (IBM)
3. Yunyao Li (IBM)
4. Sriram Raghavan (IBM India Research Lab)
5. Shivakumar Vaithyanathan (IBM)

BibTeX Citation

@inproceedings{fagin_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{Rewrite Rules for Search Database Systems}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989322},
        doi = {10.1145/1989284.1989322},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fagin, Ronald and Kimelfeld, Benny and Li, Yunyao and Raghavan, Sriram and Vaithyanathan, Shivakumar},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,499	Cleaning Inconsistencies in Information Extraction via Prioritized Repairs	2014	PODS	6.6608401e-05
12,260	Next Generation Data Analytics at IBM Research	2013	VLDB	5.093636e-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
4,433	Avatar Semantic Search: A Database Approach to Information Retrieval	2006	SIGMOD	6.7082016e-05
8,329	Understanding Queries in a Search Database System	2010	PODS	5.4528142e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,787	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD
2	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
3	6,090	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD
4	8,936	Toward Scalable Keyword Search over Relational Data	2010	VLDB
5	2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS
6	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
7	8,453	A Learned Query Rewrite System	2023	VLDB
8	2,452	A Learned Query Rewrite System using Monte Carlo Tree Search	2022	VLDB
9	12,287	Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data	2013	VLDB
10	8,329	Understanding Queries in a Search Database System	2010	PODS