FastQRE: Fast Query Reverse Engineering

Summary: FastQRE solves QRE by efficiently recovering a simple project-join SQL that reproduces a target table. It delivers 2–3 orders of magnitude speedups over state-of-the-art NP-hard search, solving complex queries in seconds rather than days. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5509
Venue: SIGMOD
Year: 2018
Pagerank: 8.3231158e-05
Overall Rank: 2,631 | 81.96%
DOI: 10.1145/3183713.3183727

Incoming Non-self Citations Over Time

Authors

1. Dmitri V. Kalashnikov (AT&T)
2. Laks V.S. Lakshmanan (AT&T; University of British Columbia)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{kalashnikov_sigmod18,
        title = {{FastQRE: Fast Query Reverse Engineering}},
        author = {Kalashnikov, Dmitri V. and Lakshmanan, Laks V.S. and Srivastava, Divesh},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3183727},
        url = {https://dl.acm.org/doi/10.1145/3183713.3183727},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,444	REGAL+: Reverse Engineering SPJA Queries	2018	VLDB	7.4094584e-05
3,677	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2076465e-05
5,438	PATSQL: Efficient Synthesis of SQL Queries from Example Tables with Quick Inference of Projected Columns	2021	VLDB	6.2195845e-05
6,607	SQUARES: A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	5.8236702e-05
7,748	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.5528084e-05
7,880	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	5.5244204e-05
9,105	Shedding Light on Opaque Application Queries	2021	SIGMOD	5.3239455e-05
10,042	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	5.1708123e-05
10,576	Efficient Query Repair for Aggregate Constraints	2026	VLDB	5.093636e-05
11,668	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	5.093636e-05
11,716	A Demonstration of RELIC: A System for REtrospective Lineage InferenCe of Data Workflows	2021	VLDB	5.093636e-05
11,830	Demonstration of a Multiresolution Schema Mapping System	2019	CIDR	5.093636e-05
11,843	Generating Selective Filters for Access Method and Physical Design Evaluation	2019	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 26 of 26 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.0006567919
37	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00048017193
180	Schema Mapping as Query Discovery	2000	VLDB	0.00026772368
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022695855
314	Making Database Systems Usable	2007	SIGMOD	0.00021574636
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
517	Query by Output	2009	SIGMOD	0.00017169735
618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015711835
1,192	Query From Examples: An Iterative, Data-Driven Approach to Query Construction	2015	VLDB	0.00011740132
1,262	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011427456
1,313	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00011186284
1,521	On Multi-Column Foreign Key Discovery	2010	VLDB	0.00010506299
1,555	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010370683
1,702	Schema Summarization	2006	VLDB	9.9697258e-05
1,751	Sample-Driven Schema Mapping	2012	SIGMOD	9.838446e-05
1,878	EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data	2008	SIGMOD	9.5651166e-05
2,160	Automated Creation of a Forms-based Database Query Interface	2008	VLDB	9.0607273e-05
2,914	Reverse Data Management	2011	VLDB	7.9667467e-05
3,300	Reverse Engineering Aggregation Queries	2017	VLDB	7.5412976e-05
3,341	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD	7.5028917e-05
3,450	Keyword Search on External Memory Data Graphs	2008	VLDB	7.4038805e-05
3,456	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	7.3998323e-05
3,572	Summary Graphs for Relational Database Schemas	2011	VLDB	7.2980153e-05
4,131	Querying Complex Structured Databases	2007	VLDB	6.8834743e-05
4,644	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.5901073e-05
9,413	Size-l Object Summaries for Relational Keyword Search	2012	VLDB	5.2745733e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,438	PATSQL: Efficient Synthesis of SQL Queries from Example Tables with Quick Inference of Projected Columns	2021	VLDB
2	3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
3	4,644	Reverse Engineering SPJ-Queries from Examples	2017	PODS
4	6,090	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD
5	3,300	Reverse Engineering Aggregation Queries	2017	VLDB
6	5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
7	143	Optimization of Nonrecursive Queries	1986	VLDB
8	1,262	Discovering Queries based on Example Tuples	2014	SIGMOD
9	10,394	Query Optimization for Database-Returning Queries	2026	SIGMOD
10	1,313	Reverse Engineering Complex Join Queries	2013	SIGMOD