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.00010948072
Overall Rank: 1,345 | 90.97%
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.00011522028
1,273	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011243661
2,413	S4: Top-k Spreadsheet-Style Search for Query Discovery	2015	SIGMOD	8.5063082e-05
2,679	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	8.1415698e-05
2,994	Extracting Equivalent SQL from Imperative Code in Database Applications	2016	SIGMOD	7.7685417e-05
3,349	Reverse Engineering Aggregation Queries	2017	VLDB	7.3878253e-05
3,461	REGAL+: Reverse Engineering SPJA Queries	2018	VLDB	7.2806224e-05
3,482	SPARQLByE: Querying RDF data by example	2016	VLDB	7.263568e-05
3,504	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2483123e-05
4,662	Reverse Engineering SPJ-Queries from Examples	2017	PODS	6.4792038e-05
5,982	Active Learning of GAV Schema Mappings	2018	PODS	5.9250649e-05
6,731	SQUARES: A SQL Synthesizer Using Query Reverse Engineering	2020	VLDB	5.6922895e-05
8,516	Exploring the Data Wilderness through Examples	2019	SIGMOD	5.3239705e-05
9,118	Generation of Training Examples for Tabular Natural Language Inference	2023	SIGMOD	5.2255715e-05
9,143	Shedding Light on Opaque Application Queries	2021	SIGMOD	5.2203125e-05
9,304	DataDiff: User-Interpretable Data Transformation Summaries for Collaborative Data Analysis	2018	SIGMOD	5.1971324e-05
9,433	Cost-efficient Data Acquisition on Online Data Marketplaces for Correlation Analysis	2019	VLDB	5.1767619e-05
9,626	Interactive and Deterministic Data Cleaning: A Tossed Stone Raises a Thousand Ripples	2016	SIGMOD	5.1477881e-05
11,981	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.9769913e-05
12,095	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD	4.9769913e-05
12,371	Exploring Databases via Reverse Engineering Ranking Queries with PALEO	2016	VLDB	4.9769913e-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.00022588961
519	Query by Output	2009	SIGMOD	0.00016937515
1,221	SODA: Generating SQL for Business Users	2012	VLDB	0.00011469979
1,501	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010456517
1,776	Sample-Driven Schema Mapping	2012	SIGMOD	9.6631141e-05

Semantically Similar Papers

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