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.1415698e-05
Overall Rank: 2,679 | 82.00%
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.2806224e-05
3,504	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2483123e-05
5,523	PATSQL: Efficient Synthesis of SQL Queries from Example Tables with Quick Inference of Projected Columns	2021	VLDB	6.0935914e-05
6,731	SQUARES: A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	5.6922895e-05
7,880	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	5.4330096e-05
7,884	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.4315851e-05
9,143	Shedding Light on Opaque Application Queries	2021	SIGMOD	5.2203125e-05
10,241	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	5.0524002e-05
10,813	Efficient Query Repair for Aggregate Constraints	2026	VLDB	4.9769913e-05
11,981	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.9769913e-05
12,025	A Demonstration of RELIC: A System for REtrospective Lineage InferenCe of Data Workflows	2021	VLDB	4.9769913e-05
12,137	Demonstration of a Multiresolution Schema Mapping System	2019	CIDR	4.9769913e-05
12,149	Generating Selective Filters for Access Method and Physical Design Evaluation	2019	SIGMOD	4.9769913e-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.00064391979
38	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00047373961
182	Schema Mapping as Query Discovery	2000	VLDB	0.00026265768
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022588961
319	Making Database Systems Usable	2007	SIGMOD	0.00021155013
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001831946
519	Query by Output	2009	SIGMOD	0.00016937515
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015692059
1,211	Query From Examples: An Iterative, Data-Driven Approach to Query Construction	2015	VLDB	0.00011522028
1,273	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011243661
1,345	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00010948072
1,501	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010456517
1,533	On Multi-Column Foreign Key Discovery	2010	VLDB	0.00010328081
1,736	Schema Summarization	2006	VLDB	9.7505629e-05
1,776	Sample-Driven Schema Mapping	2012	SIGMOD	9.6631141e-05
1,907	EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data	2008	SIGMOD	9.3936687e-05
2,204	Automated Creation of a Forms-based Database Query Interface	2008	VLDB	8.8567756e-05
2,950	Reverse Data Management	2011	VLDB	7.817636e-05
3,349	Reverse Engineering Aggregation Queries	2017	VLDB	7.3878253e-05
3,397	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD	7.3332055e-05
3,470	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	7.273555e-05
3,509	Keyword Search on External Memory Data Graphs	2008	VLDB	7.24401e-05
3,626	Summary Graphs for Relational Database Schemas	2011	VLDB	7.1495071e-05
4,208	Querying Complex Structured Databases	2007	VLDB	6.7308334e-05
4,662	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.4792038e-05
9,600	Size-l Object Summaries for Relational Keyword Search	2012	VLDB	5.1539819e-05

Semantically Similar Papers

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