DBScholar

Back to papers

DISCOVER: Keyword Search in Relational Databases

Summary: Schema-agnostic keyword search over relational databases, returning tuple-joining networks covering all query terms. DISCOVER enumerates nonredundant, schema-bounded candidate networks and reuses common subexpressions; optimal planning is NP-complete, motivating a near-optimal greedy algorithm. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h8a0c91320616afc0
Venue
VLDB
Year
2002
Pagerank
0.00047394041
Overall Rank
38 | 99.75%
DOI
10.1016/B978-155860869-6/50065-2

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{hristidis_vldb02,
        title = {{DISCOVER: Keyword Search in Relational Databases}},
        author = {Hristidis, Vagelis and Papakonstantinou, Yannis},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50065-2},
        url = {https://doi.org/10.1016/B978-155860869-6/50065-2},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 99 citing papers.

Rank Citing Paper Year Venue Pagerank
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042936299
81 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00036346781
89 WebTables: Exploring the Power of Tables on the Web 2008 VLDB 0.00035129658
180 Constructing an Interactive Natural Language Interface for Relational Databases 2015 VLDB 0.0002654471
217 Efficient IR-Style Keyword Search over Relational Databases 2003 VLDB 0.00024465994
270 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022599109
290 ObjectRank: Authority-Based Keyword Search in Databases 2004 VLDB 0.00021955068
293 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021943678
319 Making Database Systems Usable 2007 SIGMOD 0.00021164857
439 ATHENA: An Ontology-Driven System for Natural Language Querying over Relational Data Stores 2016 VLDB 0.00018251249
505 Schema-Free XQuery 2004 VLDB 0.00017161757
715 Data Integration with Uncertainty 2007 VLDB 0.00014559092
768 Effective Keyword Search in Relational Databases 2006 SIGMOD 0.00014105849
825 Efficient Keyword Search for Smallest LCAs in XML Databases 2005 SIGMOD 0.00013643331
942 SPARK: Top-k Keyword Query in Relational Databases 2007 SIGMOD 0.00012956137
1,182 SQAK: Doing More with Keywords 2008 SIGMOD 0.0001161771
1,221 SODA: Generating SQL for Business Users 2012 VLDB 0.00011473702
1,272 Discovering Queries based on Example Tuples 2014 SIGMOD 0.00011248674
1,318 LSH Ensemble: Internet-Scale Domain Search 2016 VLDB 0.00011047393
1,445 Finding and Approximating Top-k Answers in Keyword Proximity Search 2006 PODS 0.0001063035
1,501 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00010461358
1,565 Keyword Proximity Search in Complex Data Graphs 2008 SIGMOD 0.00010220855
1,760 Structured Querying of Web Text: A Technical Challenge 2007 CIDR 9.7106555e-05
1,776 Sample-Driven Schema Mapping 2012 SIGMOD 9.6674087e-05
1,882 BANKS: Browsing and Keyword Searching in Relational Databases 2002 VLDB 9.4403196e-05
1,886 Probabilistic Ranking of Database Query Results 2004 VLDB 9.4339749e-05
1,906 EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data 2008 SIGMOD 9.3981082e-05
2,025 OpenSearch-SQL: Enhancing Text-to-SQL with Dynamic Few-shot and Consistency Alignment 2025 SIGMOD 9.163622e-05
2,242 Automatic Categorization of Query Results 2004 SIGMOD 8.7685327e-05
2,254 Relational link-based ranking 2004 VLDB 8.7448663e-05
2,262 Identifying Meaningful Return Information for XML Keyword Search 2007 SIGMOD 8.7333724e-05
2,396 Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? * 2005 CIDR 8.5278724e-05
2,412 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.5101348e-05
2,414 Structured Search Result Differentiation 2009 VLDB 8.5081277e-05
2,472 Keyword++: A Framework to Improve Keyword Search Over Entity Databases 2010 VLDB 8.4125186e-05
2,679 FastQRE: Fast Query Reverse Engineering 2018 SIGMOD 8.1453935e-05
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0525756e-05
2,840 Towards Keyword-Driven Analytical Processing 2007 SIGMOD 7.9505128e-05
2,880 Expressive and Flexible Access to Web-Extracted Data: A Keyword-based Structured Query Language 2010 SIGMOD 7.9144548e-05
2,888 DB&IR: Both Sides Now (Extended Abstract) 2007 SIGMOD 7.9072366e-05
3,088 Learning to Create Data-Integrating Queries 2008 VLDB 7.6596008e-05
3,288 Ten Years of WebTables 2018 VLDB 7.4530805e-05
3,312 Keyword Search on Structured and Semi-Structured Data 2009 SIGMOD 7.4385614e-05
3,349 Reverse Engineering Aggregation Queries 2017 VLDB 7.391292e-05
3,461 REGAL+: Reverse Engineering SPJA Queries 2018 VLDB 7.2839794e-05
3,504 Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity 2019 VLDB 7.2516839e-05
3,509 Keyword Search on External Memory Data Graphs 2008 VLDB 7.2474338e-05
3,728 Keyword Search over Relational Databases: A Metadata Approach 2011 SIGMOD 7.0696128e-05
3,902 CSV: Visualizing and Mining Cohesive Subgraphs 2008 SIGMOD 6.9340634e-05
4,140 Efficient Type-Ahead Search on Relational Data: a TASTIER Approach 2009 SIGMOD 6.7854783e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank Cited Paper Year Venue Pagerank
129 Efficient and Extensible Algorithms for Multi Query Optimization 2000 SIGMOD 0.0003040756
155 Common Expression Analysis in Database Applications 1982 SIGMOD 0.00028527932
303 Proximity Search in Databases 1998 VLDB 0.0002164278
2,167 An Approximate Search Engine for Structural Databases 2000 SIGMOD 8.9288519e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,508 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD
2 4,306 Discovering Topical Structures of Databases 2008 SIGMOD
3 9,974 A Graph Method for Keyword-based Selection of the top-K Databases 2008 SIGMOD
4 217 Efficient IR-Style Keyword Search over Relational Databases 2003 VLDB
5 5,845 Effective Keyword-based Selection of Relational Databases 2007 SIGMOD
6 768 Effective Keyword Search in Relational Databases 2006 SIGMOD
7 1,272 Discovering Queries based on Example Tuples 2014 SIGMOD
8 3,728 Keyword Search over Relational Databases: A Metadata Approach 2011 SIGMOD
9 4,447 Keyword Search on Relational Data Streams 2007 SIGMOD
10 1,501 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD