Reverse Engineering SPJ-Queries from Examples

Summary: Reverse-engineer SPJ queries from positive/negative examples: decide satisfiability (exists SPJ returning all positives and no negatives) and learn such a query. Presents a fine-grained classical and parameterized complexity landscape across operator subsets, schema/query/example sizes (bounded vs unbounded), proving new W[3]-completeness results and implications for avoiding overfitting. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1723
Venue: PODS
Year: 2017
Pagerank: 6.5901073e-05
Overall Rank: 4,644 | 68.14%
DOI: 10.1145/3034786.3056112

Incoming Non-self Citations Over Time

Authors

1. Yaacov Y. Weiss (Hebrew University)
2. Sara Cohen (Hebrew University)

BibTeX Citation

@inproceedings{weiss_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Reverse Engineering SPJ-Queries from Examples}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056112},
        doi = {10.1145/3034786.3056112},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Weiss, Yaacov Y. and Cohen, Sara},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,048	Duoquest: A Dual-Specification System for Expressive SQL Queries	2020	SIGMOD	9.2560185e-05
2,631	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	8.3231158e-05
3,677	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2076465e-05
6,200	New Trends on Exploratory Methods for Data Analytics	2017	VLDB	5.9457282e-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

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
414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018893507
517	Query by Output	2009	SIGMOD	0.00017169735
856	How to ConQueR Why-Not Questions	2010	SIGMOD	0.00013573466
1,313	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00011186284
2,639	Learning and Verifying Quantified Boolean Queries by Example	2013	PODS	8.3078378e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,192	Query From Examples: An Iterative, Data-Driven Approach to Query Construction	2015	VLDB
2	11,245	Relational Query Synthesis ⋈ Decision Tree Learning	2024	VLDB
3	8,007	Complete Approximations of Incomplete Queries	2013	VLDB
4	8,970	Understanding Queries by Conditional Instances	2022	SIGMOD
5	4,759	Explaining Wrong Queries Using Small Examples	2019	SIGMOD
6	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
7	2,631	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD
8	4,393	Bounded Conjunctive Queries	2014	VLDB
9	1,262	Discovering Queries based on Example Tuples	2014	SIGMOD
10	1,313	Reverse Engineering Complex Join Queries	2013	SIGMOD