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.1157127e-05
Overall Rank: 2,686 | 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,462	REGAL+: Reverse Engineering SPJA Queries	2018	VLDB	7.2620842e-05
3,503	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2305074e-05
5,507	PATSQL: Efficient Synthesis of SQL Queries from Example Tables with Quick Inference of Projected Columns	2021	VLDB	6.0882949e-05
6,746	SQUARES: A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	5.6743008e-05
7,884	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	5.4169982e-05
7,901	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.4136249e-05
9,163	Shedding Light on Opaque Application Queries	2021	SIGMOD	5.2034849e-05
10,273	Scalable and Usable Relational Learning With Automatic Language Bias	2021	SIGMOD	5.0356939e-05
10,874	Efficient Query Repair for Aggregate Constraints	2026	VLDB	4.9605343e-05
12,025	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.9605343e-05
12,069	A Demonstration of RELIC: A System for REtrospective Lineage InferenCe of Data Workflows	2021	VLDB	4.9605343e-05
12,181	Demonstration of a Multiresolution Schema Mapping System	2019	CIDR	4.9605343e-05
12,192	Generating Selective Filters for Access Method and Physical Design Evaluation	2019	SIGMOD	4.9605343e-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.0006440069
38	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00047300197
184	Schema Mapping as Query Discovery	2000	VLDB	0.00026196483
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022559588
321	Making Database Systems Usable	2007	SIGMOD	0.00021093212
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018277436
520	Query by Output	2009	SIGMOD	0.00016910379
602	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015670535
1,214	Query From Examples: An Iterative, Data-Driven Approach to Query Construction	2015	VLDB	0.00011490045
1,275	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011213614
1,353	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00010913748
1,505	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010424285
1,538	On Multi-Column Foreign Key Discovery	2010	VLDB	0.00010295575
1,745	Schema Summarization	2006	VLDB	9.7195373e-05
1,787	Sample-Driven Schema Mapping	2012	SIGMOD	9.6333179e-05
1,914	EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data	2008	SIGMOD	9.3684002e-05
2,214	Automated Creation of a Forms-based Database Query Interface	2008	VLDB	8.8286366e-05
2,962	Reverse Data Management	2011	VLDB	7.7949147e-05
3,353	Reverse Engineering Aggregation Queries	2017	VLDB	7.3674867e-05
3,407	Designing and Refining Schema Mappings via Data Examples	2011	SIGMOD	7.3096046e-05
3,467	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	7.2609187e-05
3,512	Keyword Search on External Memory Data Graphs	2008	VLDB	7.2253736e-05
3,619	Summary Graphs for Relational Database Schemas	2011	VLDB	7.1360652e-05
4,225	Querying Complex Structured Databases	2007	VLDB	6.7098929e-05
4,665	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.4634883e-05
9,626	Size-l Object Summaries for Relational Keyword Search	2012	VLDB	5.1369628e-05

Semantically Similar Papers

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