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/.

In general, a component-based system uses only a part of the functions of its software components. Therefore, precise structural testing for components requires to specify what functions of the components are used in the system. In addition, in the case with an object-oriented component, some existing studies point out that testing of all possible bindings between a call site and the methods that the site may invoke is extremely ineffective. In this paper, we propose a method for precisely estimating test coverage of components on an object-oriented framework by using its deployment descriptor and evaluate its effectiveness.

Web services have been common technologies for providing services over the Internet. In the future, it is expected that a usage model that autonomously integrates services will become ordinary in, for example, B2B integration. However, such method of executing pre-defined process lacks flexibility because a service requestor must know in advance the interface of all integrated services. Accordingly, there is a need for a method that composes a process from the requestor's requirement independent of the interface of services. This paper proposes the architecture and a method for composing a process automatically. Our approach is formulating Web services function and a requestor's requirement as the transitions of his state by means of situation calculus and calculating what process is matched with the requirement. In our method, we model message-oriented execution of service. Moreover, our method is capable of composing not just a sequential process but also a process including conditional choices. Therefore, our method has the basic feature to be able to compose nondeterministic Web service.