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: haa2e0eeafab521d4
Venue: SIGMOD
Year: 2018
Pagerank: 8.1453935e-05
Overall Rank: 2,679 | 81.99%
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,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
5,520	PATSQL: Efficient Synthesis of SQL Queries from Example Tables with Quick Inference of Projected Columns	2021	VLDB	6.0964774e-05
6,725	SQUARES: A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	5.6949573e-05
7,875	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	5.4355826e-05
7,879	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.4341576e-05
9,137	Shedding Light on Opaque Application Queries	2021	SIGMOD	5.2222795e-05
10,235	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	5.0547931e-05
10,803	Efficient Query Repair for Aggregate Constraints	2026	VLDB	4.9793485e-05
11,975	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.9793485e-05
12,019	A Demonstration of RELIC: A System for REtrospective Lineage InferenCe of Data Workflows	2021	VLDB	4.9793485e-05
12,131	Demonstration of a Multiresolution Schema Mapping System	2019	CIDR	4.9793485e-05
12,143	Generating Selective Filters for Access Method and Physical Design Evaluation	2019	SIGMOD	4.9793485e-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.00064420972
38	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00047394041
182	Schema Mapping as Query Discovery	2000	VLDB	0.00026277842
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022599109
319	Making Database Systems Usable	2007	SIGMOD	0.00021164857
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001832766
518	Query by Output	2009	SIGMOD	0.00016944862
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
1,211	Query From Examples: An Iterative, Data-Driven Approach to Query Construction	2015	VLDB	0.00011524858
1,272	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011248674
1,345	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00010953079
1,501	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010461358
1,532	On Multi-Column Foreign Key Discovery	2010	VLDB	0.00010332696
1,733	Schema Summarization	2006	VLDB	9.7551427e-05
1,776	Sample-Driven Schema Mapping	2012	SIGMOD	9.6674087e-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,203	Automated Creation of a Forms-based Database Query Interface	2008	VLDB	8.8609567e-05
2,949	Reverse Data Management	2011	VLDB	7.821181e-05
3,349	Reverse Engineering Aggregation Queries	2017	VLDB	7.391292e-05
3,397	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD	7.3366398e-05
3,470	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	7.2765721e-05
3,509	Keyword Search on External Memory Data Graphs	2008	VLDB	7.2474338e-05
3,625	Summary Graphs for Relational Database Schemas	2011	VLDB	7.1526073e-05
4,208	Querying Complex Structured Databases	2007	VLDB	6.7339511e-05
4,660	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.4822086e-05
9,592	Size-l Object Summaries for Relational Keyword Search	2012	VLDB	5.1564222e-05

Semantically Similar Papers

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