Synthesizing highly expressive SQL queries from input-output examples
Open accessThe DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Abstract
SQL is the de facto language for manipulating relational data. Though powerful, many users find it difficult to write SQL queries due to highly expressive constructs. While using the programming-by-example paradigm to help users write SQL queries is an attractive proposition, as evidenced by online help forums such as Stack Overflow, developing techniques for synthesizing SQL queries from given input-output (I/O) examples has been difficult, due to the large space of SQL queries as a result of its rich set of operators. In this paper, we present a new scalable and efficient algorithm for synthesizing SQL queries based on I/O examples. The key innovation of our algorithm is development of a language for abstract queries, i.e., queries with uninstantiated operators, that can be used to express a large space of SQL queries efficiently. Using abstract queries to represent the search space nicely decomposes the synthesis problem into two tasks: 1) searching for abstract queries that can potentially satisfy the given I/O examples, and 2) instantiating the found abstract queries and ranking the results. We have implemented this algorithm in a new tool called Scythe and evaluated it using 193 benchmarks collected from Stack Overflow. Our evaluation shows that Scythe can efficiently solve 74% of the benchmarks, most in just a few seconds, and the queries range from simple ones involving a single selection to complex queries with 6 nested subqueires.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Muggleton, S. (1991) · New Generation Computing · doi:10.1007/bf03037089 · Cited by 1,044
Alur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E., & Udupa, A. (2013) · 2013 Formal Methods in Computer-Aided Design · doi:10.1109/fmcad.2013.6679385 · Cited by 656
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1925844.1926423 · Cited by 581
Smith, C., & Albarghouthi, A. (2016) · Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2908080.2908102 · Cited by 76
FlashExtract: a framework for data extraction by examples
Le, V., & Gulwani, S. (2014) · ACM SIGPLAN Notices · doi:10.1145/2666356.2594333 · Cited by 59
Schkufza, E., Sharma, R., & Aiken, A. (2013) · ACM SIGARCH Computer Architecture News · doi:10.1145/2490301.2451150 · Cited by 57
Cited by
Yu, T., Zhang, R., Yang, K., Yasunaga, M., Wang, D., Li, Z., Ma, J., Li, I., Yao, Q., Roman, S., et al. (2018) · Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/d18-1425 · Cited by 1,034
Towards Complex Text-to-SQL in Cross-Domain Database with Intermediate Representation
Guo, J., Zhan, Z., Gao, Y., Xiao, Y., Lou, J.-G., Liu, T., & Zhang, D. (2019) · Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/p19-1444 · Cited by 406
Active Inductive Logic Programming for Code Search
Sivaraman, A., Zhang, T., Van den Broeck, G., & Kim, M. (2019) · 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE) · doi:10.1109/icse.2019.00044 · Cited by 34
LooPy: interactive program synthesis with control structures
Ferdowsifard, K., Barke, S., Peleg, H., Lerner, S., & Polikarpova, N. (2021) · Proceedings of the ACM on Programming Languages · doi:10.1145/3485530 · Cited by 18
Metadata
- Authors
- Wang, C., Cheung, A., & Bodik, R.
- Venue
- ACM SIGPLAN Notices
- Published
- 2017-06-14
- Volume
- 52
- Issue
- 6
- Pages
- 452-466
- ISSN
- 0362-1340 (ISSN-L)
- 1558-1160
- OpenAlex
- W4255584681
- Cited by
- 48
- References
- 6
- FWCI
- 4.04
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.