一句话：将 SQL 查询测试数据生成建模为搜索问题，GA 利用查询计划引导，在 2135 条查询上完全覆盖 98.6%。
数据库中心系统依赖 SQL 查询，但为 JOIN、WHERE、子查询等覆盖目标生成测试数据困难且耗时。现有工作常将问题建模为约束满足并用 SAT 求解，然而对 JOIN、子查询和字符串支持有限。本文改将 SQL 查询测试数据生成视为搜索问题，提出并评估随机搜索、偏置随机搜索和遗传算法三种方法。遗传算法从数据库引擎的物理查询计划中提取信息构造适应度函数，作为搜索引导。作者在来自三个开源软件和一个工业系统的 2135 条查询上评估：遗传算法能完全覆盖 98.6% 的查询，每条查询仅需数秒，且不受当前先进技术限制。
Database-centric systems strongly rely on SQL queries to manage and manipulate their data. These SQL commands can range from very simple selections to queries that involve several tables, sub-queries, and grouping operations. And, as with any important piece of code, developers should properly test SQL queries. In order to completely test a SQL query, developers need to create test data that exercise all possible coverage targets in a query, e.g., JOINs and WHERE predicates. And indeed, this task can be challenging and time-consuming for complex queries. Previous studies have modeled the problem of generating test data as a constraint satisfaction problem and, with the help of SAT solvers, generate the required data. However, such approaches have strong limitations, such as partial support for queries with JOINs, subqueries, and strings (which are commonly used in SQL queries). In this paper, we model test data generation for SQL queries as a search-based problem. Then, we devise and evaluate three different approaches based on random search, biased random search, and genetic algorithms (GAs). The GA, in particular, uses a fitness function based on information extracted from the physical query plan of a database engine as search guidance. We then evaluate each approach in 2,135 queries extracted from three open source software and one industrial software system. Our results show that GA is able to completely cover 98.6% of all queries in the dataset, requiring only a few seconds per query. Moreover, it does not suffer from the limitations affecting state-of-the art techniques.
@inproceedings{paperbot4502,
title = {Search-based test data generation for SQL queries},
author = {Jeroen Castelein and Maurício Aniche and Mozhan Soltani and Annibale Panichella and Arie van Deursen},
booktitle = {ICSE},
year = {2018},
doi = {10.1145/3180155.3180202}
}