Reverse Engineering Complex Join Queries

Summary: Efficient algorithm to reverse engineer a join query Q that generates a given output Out from D, supporting arbitrary join graphs beyond prior structural constraints. Uses a star-based decomposition with merge steps forming a lattice over graphs, enabling principled pruning, optimizations, and scalable discovery of equi-join on PK/FK; evaluated on benchmarks, showing accuracy and scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4727
Venue: SIGMOD
Year: 2013
Pagerank: 0.00011298251
Overall Rank: 1,572 | 89.07%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,459	Query From Examples: An Iterative, Data-Driven Approach to Query Construction	2015	VLDB	0.00011889802
1,509	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011612727
2,576	S4: Top-k Spreadsheet-Style Search for Query Discovery	2015	SIGMOD	8.5112408e-05
2,717	REGAL+: Reverse Engineering SPJA Queries	2018	VLDB	8.2425675e-05
2,982	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	7.7801984e-05
3,296	Extracting Equivalent SQL from Imperative Code in Database Applications	2016	SIGMOD	7.2596583e-05
3,661	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	6.8689912e-05
3,663	Reverse Engineering Aggregation Queries	2017	VLDB	6.8647221e-05
3,684	SPARQLByE: Querying RDF data by example	2016	VLDB	6.8465042e-05
4,636	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.0303761e-05
6,679	SQUARES : A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	4.9656458e-05
8,344	Exploring the Data Wilderness through Examples	2019	SIGMOD	4.5428111e-05
8,892	Generation of Training Examples for Tabular Natural Language Inference	2023	SIGMOD	4.4275457e-05
8,955	Shedding Light on Opaque Application Queries	2021	SIGMOD	4.4215357e-05
9,076	DataDiff: User-Interpretable Data Transformation Summaries for Collaborative Data Analysis	2018	SIGMOD	4.401804e-05
9,177	Cost-efficient Data Acquisition on Online Data Marketplaces for Correlation Analysis	2019	VLDB	4.3834281e-05
9,278	Interactive and Deterministic Data Cleaning: A Tossed Stone Raises a Thousand Ripples	2016	SIGMOD	4.3639892e-05
11,471	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.1945683e-05
11,592	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD	4.1945683e-05
11,871	Exploring Databases via Reverse Engineering Ranking Queries with PALEO	2016	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
301	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00028370644
492	Query by Output	2009	SIGMOD	0.00021974699
1,168	SODA: Generating SQL for Business Users	2012	VLDB	0.00013541143
1,564	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00011350495
2,078	Sample-Driven Schema Mapping	2012	SIGMOD	9.599707e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,509	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011612727
901	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD	0.00015487777
3,339	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.2038026e-05
1,796	Summary Graphs for Relational Database Schemas	2011	VLDB	0.00010524897
11,705	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1945683e-05
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
2,982	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	7.7801984e-05