DSpace Repository

PATSQL: Efficient Synthesis of SQL Queries from Example Tables with Quick Inference of Projected Columns

Show simple item record

dc.contributor.author Takenouchi, Keita en
dc.contributor.author Ishio, Takashi en
dc.contributor.author Okada, Joji en
dc.contributor.author Sakata, Yuji en
dc.date.accessioned 2022-03-28T08:01:24Z en
dc.date.available 2022-03-28T08:01:24Z en
dc.date.issued 2021-07-01 en
dc.identifier.uri http://hdl.handle.net/10061/14696 en
dc.description.abstract SQL is one of the most popular tools for data analysis, and it is now used by an increasing number of users without having expertise in databases. Several studies have proposed programming-by-example approaches to help such non-experts to write correct SQL queries. While existing methods support a variety of SQL features such as aggregation and nested query, they suffer a significant increase in computational cost as the scale of example tables increases. In this paper, we propose an efficient algorithm utilizing properties known in relational algebra to synthesize SQL queries from input and output tables. Our key insight is that a projection operator in a program sketch can be lifted above other operators by applying transformation rules in relational algebra, while preserving the semantics of the program. This enables a quick inference of appropriate columns in the projection operator, which is an essential component in synthesis but causes combinatorial explosions in prior work. We also introduce a novel form of constraints and its top-down propagation mechanism for efficient sketch completion. We implemented this algorithm in our tool PATSQL and evaluated it on 226 queries from prior benchmarks and Kaggle's tutorials. As a result, PATSQL solved 68% of the benchmarks and found 89% of the solutions within a second. Our tool is available at https://naist-se.github.io/patsql/. en
dc.language.iso en en
dc.publisher VLDB Endowment en
dc.relation.isreplacedby https://dl.acm.org/doi/10.14778/3476249.3476253 en
dc.rights This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. en
dc.title PATSQL: Efficient Synthesis of SQL Queries from Example Tables with Quick Inference of Projected Columns en
dc.type.nii Journal Article en
dc.contributor.transcription タケノウチ, ケイタ ja
dc.contributor.transcription イシオ, タカシ ja
dc.contributor.transcription オカダ, ジョウジ ja
dc.contributor.transcription サカタ, ユウジ ja
dc.contributor.alternative 竹之内, 啓太 ja
dc.contributor.alternative 石尾, 隆 ja
dc.contributor.alternative 岡田, 譲二 ja
dc.contributor.alternative 坂田, 祐司 ja
dc.textversion none en
dc.identifier.eissn 2150-8097 en
dc.identifier.jtitle Proceedings of the VLDB Endowment (PVLDB) en
dc.identifier.volume 14 en
dc.identifier.issue 11 en
dc.identifier.spage 1937 en
dc.identifier.epage 1949 en
dc.relation.doi 10.14778/3476249.3476253 en
dc.identifier.NAIST-ID 74653577 en


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account