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: 4728
Venue: SIGMOD
Year: 2013
Pagerank: 0.00011288804
Overall Rank: 1,575 | 89.06%
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,456	Query From Examples: An Iterative, Data-Driven Approach to Query Construction	2015	VLDB	0.00011891284
1,502	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011614522
2,577	S4: Top-k Spreadsheet-Style Search for Query Discovery	2015	SIGMOD	8.5066436e-05
2,717	REGAL+: Reverse Engineering SPJA Queries	2018	VLDB	8.2370772e-05
2,990	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	7.7727915e-05
3,298	Extracting Equivalent SQL from Imperative Code in Database Applications	2016	SIGMOD	7.2527707e-05
3,662	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	6.8647421e-05
3,668	Reverse Engineering Aggregation Queries	2017	VLDB	6.8581987e-05
3,684	SPARQLByE: Querying RDF data by example	2016	VLDB	6.8399983e-05
4,636	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.0270157e-05
6,681	SQUARES : A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	4.9608812e-05
8,338	Exploring the Data Wilderness through Examples	2019	SIGMOD	4.538469e-05
8,892	Generation of Training Examples for Tabular Natural Language Inference	2023	SIGMOD	4.4233018e-05
8,960	Shedding Light on Opaque Application Queries	2021	SIGMOD	4.4173276e-05
9,072	DataDiff: User-Interpretable Data Transformation Summaries for Collaborative Data Analysis	2018	SIGMOD	4.3975844e-05
9,181	Cost-efficient Data Acquisition on Online Data Marketplaces for Correlation Analysis	2019	VLDB	4.3792262e-05
9,283	Interactive and Deterministic Data Cleaning: A Tossed Stone Raises a Thousand Ripples	2016	SIGMOD	4.3598353e-05
11,474	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.1905499e-05
11,596	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD	4.1905499e-05
11,879	Exploring Databases via Reverse Engineering Ranking Queries with PALEO	2016	VLDB	4.1905499e-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
302	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00028343691
491	Query by Output	2009	SIGMOD	0.00021960753
1,168	SODA: Generating SQL for Business Users	2012	VLDB	0.00013531301
1,564	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00011340407
2,081	Sample-Driven Schema Mapping	2012	SIGMOD	9.58883e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,502	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011614522
898	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD	0.00015476243
1,794	Summary Graphs for Relational Database Schemas	2011	VLDB	0.00010516799
3,338	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.1990012e-05
11,710	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1905499e-05
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
2,990	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	7.7727915e-05