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: 4789
Venue: SIGMOD
Year: 2013
Pagerank: 0.00011186284
Overall Rank: 1,313 | 91.00%
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,192	Query From Examples: An Iterative, Data-Driven Approach to Query Construction	2015	VLDB	0.00011740132
1,262	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011427456
2,387	S4: Top-k Spreadsheet-Style Search for Query Discovery	2015	SIGMOD	8.6482009e-05
2,631	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	8.3231158e-05
2,939	Extracting Equivalent SQL from Imperative Code in Database Applications	2016	SIGMOD	7.9395908e-05
3,300	Reverse Engineering Aggregation Queries	2017	VLDB	7.5412976e-05
3,422	SPARQLByE: Querying RDF data by example	2016	VLDB	7.426997e-05
3,444	REGAL+: Reverse Engineering SPJA Queries	2018	VLDB	7.4094584e-05
3,677	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2076465e-05
4,644	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.5901073e-05
5,859	Active Learning of GAV Schema Mappings	2018	PODS	6.0637959e-05
6,607	SQUARES: A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	5.8236702e-05
8,358	Exploring the Data Wilderness through Examples	2019	SIGMOD	5.4446041e-05
8,945	Generation of Training Examples for Tabular Natural Language Inference	2023	SIGMOD	5.3480421e-05
9,105	Shedding Light on Opaque Application Queries	2021	SIGMOD	5.3239455e-05
9,129	DataDiff: User-Interpretable Data Transformation Summaries for Collaborative Data Analysis	2018	SIGMOD	5.318789e-05
9,253	Cost-efficient Data Acquisition on Online Data Marketplaces for Correlation Analysis	2019	VLDB	5.297659e-05
9,442	Interactive and Deterministic Data Cleaning: A Tossed Stone Raises a Thousand Ripples	2016	SIGMOD	5.2677992e-05
11,668	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	5.093636e-05
11,787	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD	5.093636e-05
12,072	Exploring Databases via Reverse Engineering Ranking Queries with PALEO	2016	VLDB	5.093636e-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
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022695855
517	Query by Output	2009	SIGMOD	0.00017169735
1,214	SODA: Generating SQL for Business Users	2012	VLDB	0.0001163751
1,555	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010370683
1,751	Sample-Driven Schema Mapping	2012	SIGMOD	9.838446e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,262	Discovering Queries based on Example Tuples	2014	SIGMOD
2	1,052	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD
3	3,572	Summary Graphs for Relational Database Schemas	2011	VLDB
4	3,263	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD
5	11,909	Improving Join Reorderability with Compensation Operators	2018	SIGMOD
6	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
7	316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB
8	6,678	Output-sensitive Conjunctive Query Evaluation	2024	PODS
9	3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
10	2,631	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD