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: h06d78b06cf6850df
Venue: SIGMOD
Year: 2013
Pagerank: 0.00010953079
Overall Rank: 1,345 | 90.96%
DOI: 10.1145/2463676.2465320

Incoming Non-self Citations Over Time

Authors

1. Meihui Zhang (National University of Singapore)
2. Hazem Elmeleegy (Turn Inc.)
3. Cecilia M. Procopiuc (AT&T)
4. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{zhang_sigmod13,
        title = {{Reverse Engineering Complex Join Queries}},
        author = {Zhang, Meihui and Elmeleegy, Hazem and Procopiuc, Cecilia M. and Srivastava, Divesh},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465320},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465320},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
2,412	S4: Top-k Spreadsheet-Style Search for Query Discovery	2015	SIGMOD	8.5101348e-05
2,679	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	8.1453935e-05
2,993	Extracting Equivalent SQL from Imperative Code in Database Applications	2016	SIGMOD	7.7721951e-05
3,349	Reverse Engineering Aggregation Queries	2017	VLDB	7.391292e-05
3,461	REGAL+: Reverse Engineering SPJA Queries	2018	VLDB	7.2839794e-05
3,481	SPARQLByE: Querying RDF data by example	2016	VLDB	7.2668673e-05
3,504	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2516839e-05
4,660	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.4822086e-05
5,981	Active Learning of GAV Schema Mappings	2018	PODS	5.9278637e-05
6,725	SQUARES: A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	5.6949573e-05
8,510	Exploring the Data Wilderness through Examples	2019	SIGMOD	5.326492e-05
9,109	Generation of Training Examples for Tabular Natural Language Inference	2023	SIGMOD	5.2280464e-05
9,137	Shedding Light on Opaque Application Queries	2021	SIGMOD	5.2222795e-05
9,294	DataDiff: User-Interpretable Data Transformation Summaries for Collaborative Data Analysis	2018	SIGMOD	5.1995938e-05
9,424	Cost-efficient Data Acquisition on Online Data Marketplaces for Correlation Analysis	2019	VLDB	5.1792137e-05
9,619	Interactive and Deterministic Data Cleaning: A Tossed Stone Raises a Thousand Ripples	2016	SIGMOD	5.1502244e-05
11,975	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.9793485e-05
12,089	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD	4.9793485e-05
12,365	Exploring Databases via Reverse Engineering Ranking Queries with PALEO	2016	VLDB	4.9793485e-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
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022599109
518	Query by Output	2009	SIGMOD	0.00016944862
1,221	SODA: Generating SQL for Business Users	2012	VLDB	0.00011473702
1,501	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010461358
1,776	Sample-Driven Schema Mapping	2012	SIGMOD	9.6674087e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,272	Discovering Queries based on Example Tuples	2014	SIGMOD
2	1,057	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD
3	3,625	Summary Graphs for Relational Database Schemas	2011	VLDB
4	3,267	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD
5	12,209	Improving Join Reorderability with Compensation Operators	2018	SIGMOD
6	1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
7	321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB
8	6,467	Output-sensitive Conjunctive Query Evaluation	2024	PODS
9	3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
10	2,679	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD