Understanding Queries in a Search Database System

Summary: Formalize interpretations as parses in a 'search database system'; generate parses with nonempty evaluation in polynomial time (combined input+output) and decide specificity efficiently. Most-specific parse is intractable, but under mild assumptions parses can be enumerated by decreasing specificity with polynomial delay and space. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1525
Venue: PODS
Year: 2010
Pagerank: 5.4528142e-05
Overall Rank: 8,329 | 42.86%
DOI: 10.1145/1807085.1807121

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{fagin_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Understanding Queries in a Search Database System}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807121},
        doi = {10.1145/1807085.1807121},
        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 = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,883	Facet Discovery for Structured Web Search: A Query-log Mining Approach	2011	SIGMOD	5.7468523e-05
13,684	Rewrite Rules for Search Database Systems	2011	PODS	-

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
37	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00048017193
302	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021963347
1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00010811133
1,542	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00010421046
1,555	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010370683
1,839	BANKS: Browsing and Keyword Searching in Relational Databases	2002	VLDB	9.6426575e-05
3,239	Keyword Search on Structured and Semi-Structured Data	2009	SIGMOD	7.6078324e-05
4,433	Avatar Semantic Search: A Database Approach to Information Retrieval	2006	SIGMOD	6.7082016e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
2	1,897	Exemplar Queries: Give me an Example of What You Need	2014	VLDB
3	1,542	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
4	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
5	8,528	Aggregate Queries on Sparse Databases	2020	PODS
6	3,651	Keyword Search over Relational Databases: A Metadata Approach	2011	SIGMOD
7	5,609	Combining Keyword Search and Forms for Ad Hoc Querying of Databases	2009	SIGMOD
8	212	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB
9	13,684	Rewrite Rules for Search Database Systems	2011	PODS
10	8,936	Toward Scalable Keyword Search over Relational Data	2010	VLDB