NDLI: Synthesizing highly expressive SQL queries from input-output examples

Please wait, while we are loading the content...

Cache locality optimization for recursive programs

DemoMatch: API discovery from demonstrations

BARRACUDA: binary-level analysis of runtime RAces in CUDA programs

Bringing the web up to speed with WebAssembly

Compositional recurrence analysis revisited

Achieving high coverage for floating-point code via unconstrained programming

Decomposition instead of self-composition for proving the absence of timing channels

Component-based synthesis of table consolidation and transformation tasks from examples

Compiling without continuations

Synthesis of divide and conquer parallelism for loops

A formally verified compiler for Lustre

Repairing sequential consistency in C/C++11

Low-synchronization, mostly lock-free, elastic scheduling for streaming runtimes

Fusing effectful comprehensions

Similarity of binaries through re-optimization

BigFoot: static check placement for dynamic race detection

Miniphases: compilation using modular and efficient tree transformations

Context transformations for pointer analysis

Instruction punning: lightweight instrumentation for x86-64

Automatic program inversion using symbolic transducers

Network configuration synthesis with abstract topologies

FunTAL: reasonably mixing a functional language with assembly

Futhark: purely functional GPU-programming with nested parallelism and in-place array updates

Flatten and conquer: a framework for efficient analysis of string constraints

Taming undefined behavior in LLVM

Practical partial evaluation for high-performance dynamic language runtimes

Generalizations of the theory and deployment of triangular inequality for compiler-based strength reduction

Synthesizing program input grammars

Dynamic race prediction in linear time

Proactive and adaptive energy-aware programming with mixed typechecking

Efficient and precise points-to analysis: modeling the heap by merging equivalent automata

Low overhead dynamic binary translation on ARM

Control-flow recovery from partial failure reports

Synthesizing highly expressive SQL queries from input-output examples

HoTTSQL: proving query rewrites with univalent SQL semantics

Gradual synthesis for static parallelization of single-pass array-processing programs

Responsive parallel computation: bridging competitive and cooperative threading

Alive-Infer: data-driven precondition inference for peephole optimizations in LLVM

Compiling Markov chain Monte Carlo algorithms for probabilistic modeling

Systematic black-box analysis of collaborative web applications

Simple, fast, and safe manual memory management

Static deadlock detection for asynchronous C# programs

Skeletal program enumeration for rigorous compiler testing

Rigorous analysis of software countermeasures against cache attacks

Synthesizing memory models from framework sketches and Litmus tests

Levity polymorphism

StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data

Synthesizing highly expressive SQL queries from input-output examples

Content Provider	ACM Digital Library
Author	Bodik, Rastislav Wang, Chenglong Cheung, Alvin
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. .
Starting Page	452
Ending Page	466
Page Count	15
File Format	PDF
ISBN	9781450349888
DOI	10.1145/3062341.3062365
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-06-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Program synthesis Query by example Sql
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in