CASE STUDY

Automated SQL Query Generation for Systematic Testing
of Database Engines

Shadi Abdul Khalek
Department of Electrical and Computer

Engineering
The University of Texas at Austin

Austin TX, USA
[email protected]

Sarfraz Khurshid
Department of Electrical and Computer

Engineering
The University of Texas at Austin

Austin TX, USA
[email protected]

ABSTRACT
We present a novel approach for generating syntactically and se-
mantically correct SQL queries for testing relational database sys-
tems. We leverage the SAT-based Alloy tool-set to reduce the prob-
lem of generating valid SQL queries into a SAT problem. Our ap-
proach translates SQL query constraints into Alloy models, which
enable it to generate valid queries that cannot be automatically gen-
erated using conventional grammar-based generators.

Given a database schema, our new approach combined with our
previous work on ADUSA, automatically generates (1) syntacti-
cally and semantically valid SQL queries for testing, (2) input data
to populate test databases, and (3) expected result of executing the
given query on the generated data.

Experimental results show that not only can we automatically
generate valid queries which detect bugs in database engines, but
also we are able to combine this work with our previous work on
ADUSA to automatically generate input queries and tables as well
as expected query execution outputs to enable automated testing of
database engines.

Categories and Subject Descriptors
D.2.5 [Testing and Debugging]: Testing tools; H.2.3 [Database
Management]: Languages—SQL

General Terms
Verification

Keywords
SQL, automated query generation, database management, Alloy.

1. INTRODUCTION
Software testing is the most commonly used methodology for

validating the quality of software. However, testing is typically la-
bor intensive and often amounts to more than one-half of the cost
of software development. Testing applications that require complex

Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
ASE’10, September 20–24, 2010, Antwerp, Belgium.
Copyright 2010 ACM 978-1-4503-0116-9/10/09 …$10.00.

inputs, such as database management systems (DBMSs) or compil-
ers, is particularly expensive. Automation can significantly reduce
the cost of testing as well as enable systematic testing, which can
significantly increase the effectiveness of testing.

This paper presents a novel SAT-based approach to automate
systematic testing of database management systems. There are
three fundamental steps in testing a DBMS: (1) generating test
queries with respect to a database schema, (2) generating a set of
test databases (tables), and (3) generating oracles to verify the result
of executing the queries on the input databases using the DBMS.
Previous work has addressed each of these three steps but largely
in isolation of the other steps [7, 8]. While a brute-force combina-
tion of existing approaches to automate DBMS testing is possible
in principle, the resulting framework is unlikely to be practical: it
will generate a prohibitively large number of test cases, which have
a high percentage of tests that are redundant or invalid, and hence
represent a significant amount of wasted effort. Some approaches,
such as [6], target generating queries with cardinality constraints.
Integrating query generators with data generators, however, is still
either specialized [8], or sometimes not possible [6]. Several aca-
demic and commercial tools target the problem of test database
generation [9, 10, 12]. Nevertheless, they do not support query
generation nor test oracle generation. Recent work in query aware
input generation [5] takes a parameterized SQL query as input and
produces input tables and parameter values, but does not gener-
ate an oracle. Recent approaches introduced query-aware database
generation [11, 13]. These approaches use the information from
the queries as a basis to constrain the data generator to generate
databases that provide interesting results upon query executions.
Query-aware generation is gaining popularity in both DBMS and
database application testing [14, 15] but requires queries to be pro-
vided manually.

A popular framework for query generation is the Random Query
Generator (RQG) [4], which uses the SQL grammar as a basis of
query generation – in the spirit of production grammars. Given a
grammar RQG generates random queries and tests databases by
running the tests against two or more databases and comparing their
results. Since the query generation is purely grammar-based, it gen-
erates a large number of invalid queries as well as redundant ones.
Moreover, validating that the queries generated are syntactically
correct is hard and sometimes impossible to ensure [4].

The insight of our work is that a relational engine backed by
SAT provides a sound and practical basis of a unified approach that
supports all the three fundamental steps in DBMS testing and al-
lows generation of a higher quality test suite: queries generated are
valid, database states generated are query-aware, and expected out-
puts represent meaningful executions. Thus, each test case checks
some core functionality of a DBMS.

329

CREATE TABLE students( CREATE TABLE grades(
id int, studetnID int,
name varchar(50) courseID int,

); grade int
);

Figure 1: Example database schema.

We make the following contributions:

• Constraint-based query generation. We present a frame-
work that leverages the Alloy tool-set to model the language
constraints of a useful subset of SQL and provides automated
generation of valid queries (with respect to the constraints).

• SAT for query generation. We present a non-conventional
use of SAT: to solve syntactic and semantic constraints of
SQL language to enumerate queries as test inputs.

• Case-studies. We evaluate our approach using case-studies
to demonstrate its usefulness in automation of DBMS testing.

2. EXAMPLE
In this section we give a simple example of automated SQL

query generation which can not be generated using conventional
grammar-based generators. We describe the input database schema
and the corresponding SQL queries generated by our approach.

Let us consider a sample database schema as shown in Fig. 1.
SQL statements such as primary and foreign keys constraints, as
well as other statements which do not interfere with SQL query
generation, are ignored in our approach since they are irrelevant to
the problem we are solving. The SQL statements in Fig. 1 create
two relations (also known as tables): (1) students table with
two attributes, id of type int, and name of type varchar, (2)
grades table with three attributes, studentID of type int rep-
resenting a student ID number, courseID of type int represent-
ing the course ID number and grade of type int representing the
grade which the student earned in that course.

Let us consider a subset of SQL grammar consisting of selecting
up to two table attributes from either one or two tables cross joined.
The terminal strings of the grammar are the table names and at-
tribute names: students, grades, id, name, sID, and courseID. In
addition, we consider that the grammar allows the use of aggregate
functions when selecting a field. Let MAX and MIN be the only ag-
gregate functions allowed. Below is the grammar of SQL queries
that we will consider in this example:

QUERY ::= SELECT FROM
SELECT ::= ’SELECT’ selectTerm+
FROM ::= ’FROM’ (table | table JOIN table)
selectTerm ::= term | agg(term)
table ::= ’students’ | ’grades’
term ::= ’id’|’name’|’studentID’|’courseID’|’grade’
agg ::= ’MAX’ | ’MIN’

After automatically generating the complete Alloy model for this
SQL grammar, the Alloy analyzer, based on SAT, will convert all
Alloy formulas into boolean formulas and enumerates all possible
solutions satisfying the model. We run the output through our con-
cretization program to convert Alloy instances into complete SQL
queries. For the grammar in this example, considering up to two
SELECT terms, up to two FROM tables, and two aggregates, the
Alloy Analyzer generates 186 unique non isomorphic1 instances,
1Two queries are considered isomorphic if they only differ in the
order at which the SELECT terms, or the FROM tables are used.

SELECT courseID, studetnID FROM GRADES, STUDENT;
SELECT MAX (courseID), MAX (NAME) FROM GRADES, STUDENT;
SELECT MIN (courseID), MIN (NAME) FROM GRADES, STUDENT;
SELECT courseID FROM GRADES, STUDENT;
SELECT MAX (courseID), MIN (NAME) FROM GRADES, STUDENT;
SELECT MAX (NAME), MIN (courseID) FROM GRADES, STUDENT;
SELECT courseID, MIN (NAME) FROM GRADES, STUDENT;
SELECT courseID, MAX (NAME) FROM GRADES, STUDENT;
SELECT NAME, MAX (courseID) FROM GRADES, STUDENT;
SELECT NAME FROM STUDENT;
SELECT MIN (NAME) FROM STUDENT;
SELECT id FROM STUDENT;
SELECT MAX (NAME), MIN (id) FROM STUDENT;
SELECT MAX (id), MIN (NAME) FROM STUDENT;
SELECT id, MAX (NAME) FROM STUDENT;
…

Figure 2: SQL queries generated by our approach.

QUERY ::= SELECT FROM WHERE GROUP_BY HAVING
SELECT ::= ’SELECT’ selectTerm+
selectTerm :: term | aggregate(term)
FROM ::= ’FROM’ (table | table JOIN table)
WHERE ::= ’WHERE’ term operator (term | value)
GROUP_BY ::= ’GROUP BY’ term
HAVING ::= ’HAVING’ term operator value
aggregate ::= ’MAX’ | ’MIN’ | ’AVG’ | ’COUNT’
operator ::= ’<’ | ’<=’ | ’>’ | ’>=’ | ’=’

Figure 3: SQL Grammar supported

which is the number of SQL queries expected. We then automat-
ically translate each Alloy instance into a SQL query. Fig. 2 is a
sample subset of the SQL queries generated by our approach.

3. FRAMEWORK
In this section, we discuss the general algorithm of our approach.

In our approach, we consider a subset of SQL query grammar; the
complete grammar supported is shown in Fig. 3.

Alloy can be used to model a relational database schema2. To
illustrate, consider the example used in section 2, the schema of
the tables is shown in Fig. 1. Our approach generates an Alloy
specification that represents both students and grades tables
and each of their attributes. To systematically generate Alloy mod-
els for all tables, we model a general representation of tables and
fields in Alloy as follows:

abstract sig FieldNames {}
abstract sig FieldTypes {}
abstract sig Field {

name : one FieldNames,
type : one FieldTypes

}
abstract sig TableNames {}
abstract sig Table {

name : one TableNames,
fields : some Field

}

We model aggregate functions by creating an abstract signature
for all aggregates and extending this signature with the ones that
we want to use. If we consider the aggregate functions MIN and
MAX as in the grammar in our example, then the following Alloy
code models these aggregates to be used in the query generation:

abstract sig AggregateNames {}
one sig MAX extends AggregateNames {}
one sig MIN extends AggregateNames {}

2Details about Alloy and Alloy Analyzer can be found in [2, 3].

330

Modeling the SQL grammar in Alloy requires modeling each of
the SELECT and FROM parts as separate entities. This guarantees
the generation of syntactically correct queries. After modeling the
query grammar in Alloy, we add constraints over the model which
gives the ability to prune out queries which are either not useful or
semantically incorrect. The following Alloy code models both the
SELECT and FROM sections:

sig term {
field : one Field,
agg : lone AggregateNames

}
one sig SELECT {

fields : some term
}
one sig FROM {

tables: some Table
}

Our approach reads the database schema and automatically gen-
erates signatures and constraints for the tables and fields. First, we
populate the FieldNames and TableNames with elements rep-
resenting all the names of fields and tables that exist in the database
schema. We use the extends keyword to extend any of the ex-
isting signatures in the model. We also use the multiplicity lone
for these elements since they can be either singletons when used in
a query or empty when not used. The following Alloy code covers
all the field names and table names in our example that would be
potentially used in queries generated:

lone sig id, name, studentID, courseID, grade
extends FieldNames {}

one sig students, grades extends TableNames {}

We then automatically create a signature for each of the fields
of the tables. These signatures extend the Field type. In addi-
tion, for each Field type extended we explicitly set the relation
constraints, setting the name and type of every field explicitly. Sim-
ilarly for each table in the schema, we create a signature extending
the Table type.

This provides us with a backbone for syntactically SQL queries,
we add to this model constraints to enforce semantically correct
query generation. We mention some of these constraints here. To
enforce that only attributes in the tables selected within the FROM
clause can be chosen in the SELECT clause, we add the following
Alloy fact to the model:

fact field_in_table {
all f: term.field | some t: FROM.tables |

f in t.fields
}

Similarly, to ensure that an attribute is selected only once in the
SELECT clause, we add the following Alloy fact to the model:

fact unique_select_terms {
all a, b : SELECT.fields.term |
(a.field = b.field and a.agg = b.agg ) => a=b

}

4. CASE STUDIES
In this section we discuss the use of our framework in different

case studies. We perform tasks for generating SQL queries based
on different subsets of the SQL grammar.

Case# SQL Grammar

1
QUERY ::= SELECT FROM
SELECT ::= ’SELECT’ selectTerm+
FROM ::= ’FROM’ (table | table JOIN table)

2

QUERY ::= SELECT FROM WHERE
SELECT ::= ’SELECT’ selectTerm+
FROM ::= ’FROM’ (table | table JOIN table)
WHERE ::= ’WHERE’ term operator (term | value)

3

QUERY ::= SELECT FROM GROUP_BY HAVING
SELECT ::= ’SELECT’ selectTerm+
FROM ::= ’FROM’ (table | table JOIN table)
GROUP_BY ::= ’GROUP BY’ term
HAVING ::= ’HAVING’ term operator value

*

selectTerm ::= term | agg ( term )
term ::= ’id’ | ’name’ | ’studentID’ | ’courseID’ | ’grade’
agg ::= ’MAX’ | ’MIN’
table ::= ’students’ | ’grades’

Table 1: The SQL grammar used in each case study. (The *
indicates common terminal values.)

4.1 Auto Query Generation
In each case study we use our approach to enumerate all possible

valid queries for a given schema. We compare the approach by
applying it to different subsets of the SQL grammar. We consider
the same schema presented in Fig. 1 consisting of the two tables:
student and grades. The subsets of SQL grammar that we
consider are presented in Table 1. Case#1 consists of only SELECT
and FROM clauses. For each test, we consider two cases: (1) up
to one table in the FROM section, and (2) up to two tables in the
FROM section. So, queries generated in (1) are inclusive to (2).

Table 2 shows the results of our approach. The total number of
queries increases drastically for Case#2, this is because the fact that
the WHERE clause can contain terms from the tables which are not
constrained by the SELECT statement, and the fact that each term
can be related to either another term or a value, thus the number
of possible queries increases. Case#3, using up to one table in the
FROM section, generates the minimum amount of queries. This
is because both constraints for GROUP BY and HAVING must be
satisfied in all the queries generated. In the grammar for Case#3,
the GROUP BY and HAVING clauses are mandatory, thus limiting
the output space.

4.2 Integration with ADUSA
One of the motivations for automatic generation of syntactically

and semantically valid SQL queries is to automate the three funda-
mental steps in database testing. Our previous work on Automated
Database Testing Using SAT (ADUSA) [1] uses model-based test-
ing to perform (1) query-aware database generation to construct a
useful test input suite covering various scenarios for query execu-
tion and (2) test oracle generation to verify query execution results
on the generated databases. ADUSA takes as input (1) a database
schema and (2) a SQL query. It populates the database with mean-
ingful data and verifies the output of executing the query upon the
database using an automatically generated oracle.

Our current approach, closes the gap of having a SQL query as
a user-provided input for ADUSA. Given an input schema, our
approach automatically generates valid SQL queries for testing.
These queries along with the schema are used by ADUSA to per-
form a black-box testing on the database system. Having both ap-
proaches based on Alloy and SAT enables us combining the Alloy
models to minimize number of variables used to solve the model.
Tests generated using ADUSA were able to find and reproduce
bugs in Oracle 11g, MySQl 4.0, and HSQLDB (injected bug) [1].

331

Case# #Tables Primary Vars Total Vars Clauses Solving Time Concret. Time/Query #Queries
1 1 155 1586 2648 375 4.03 66
1 2 155 1586 2652 343 3.53 186
2 1 247 3013 5135 390 3.86 3456
2 2 247 3011 5129 422 5.13 27081
3 1 263 3209 5524 437 4.61 26
3 2 263 3210 5528 422 4.08 76

Table 2: Solving time of each of the case studies. The #Tables is the maximum number of tables in the FROM section. Primary
variables and total variables are the Alloy variables used in generating the Boolean formula. The clauses are the Boolean clauses.
Solving time is the SAT time to generate the first possible solution for the Boolean formula (next solutions take negligible time).
Concretization time per query, is the processing time our approach does to concretize an Alloy instance into a SQL query in ms. The
#Queries is the total number of queries generated for the specific case study.

5. FUTURE WORK AND CONCLUSION
Our approach shows how to use Alloy and the Alloy Analyzer

to model a subset of SQL query grammar and its constraints to en-
sure the validity of the syntax and semantics of queries generated.
The approach is extensible; we can systematically add support for
a larger subset of SQL grammar. For example, we showed how
to integrate in our framework the types for table attributes; these
types can be used to add type checking constraints in the WHERE,
GROUP BY, and HAVING clauses. SQL transactional grammar
can be extended as well. DELETE statements can be introduced
by modifying the grammar as: DELETE FROM TABLE WHERE
term in (SELECT term FROM table WHERE condition).
The constraint that the term to be deleted is the same as the term to
be selected is simple to write in Alloy. Nested SELECT statements
can be extended by ensuring that the inner SELECT statements can
have access to the outer SELECT terms but not vice-versa.

In conclusion, we presented a novel approach for SQL query
generation to automate DBMS testing. Our approach automatically
generates syntactically and semantically valid SQL queries. When
combined with our previous work on ADUSA, we are capable of
generating (1) test SQL queries, (2) query aware input databases,
and (3) test oracles to verify the result of the query execution.

Our approach leverages the SAT-based Alloy tool-set. We sys-
tematically model the SQL queries in Alloy and add constraints to
ensure semantic meaning of the queries, and then use the Alloy
Analyzer to generate possible test queries out of the model.

We compared the output of our approach using different subsets
of SQL grammar. Combined with our previous work, our frame-
work allows finding new bugs and reproducing bugs in different
database engines.

Acknowledgments
This material is based upon work partially supported by the NSF
under Grant Nos. IIS-0438967, CCF-0845628, and CNS-0958231,
and AFOSR grant FA9550-09-1-0351.

6. REFERENCES
[1] Shadi A. Khalek, Bassem Elkarablieh, Y. O. Laleye, and

Sarfraz Khurshid. Query-Aware Test Generation Using a
Relational Constraint Solver. In ASE ’08: Proceedings of the
2008 23rd IEEE/ACM International Conference on
Automated Software Engineering , pages 238Ű-247, 2008.

[2] Daniel Jackson. Alloy: A lightweight object modeling
notation. ACM Transactions on Software Engineering and
Methodology (TOSEM), 11(2), April 2002.

[3] Emina Torlak and Daniel Jackson. Kodkod: A relational
model finder. In Tools and Algorithms for the Construction
and Analysis of Systems, Vol. 4424, pages 632–647. 2007.

[4] MySQL Forge Random Query Generator. http://forge.
mysql.com/wiki/RandomQueryGenerator/.

[5] Margus Veanes, Nikolai Tillmann, and Jonathan de Halleux.
Qex: Symbolic SQL Query Explorer Microsoft Research
Technical Report MSR-TR-2009-2015, October 2009

[6] Nicolas Bruno, Surajit Chaudhuri, and Dilys Thomas.
Generating queries with cardinality constraints for DBMS
testing. IEEE Transactions on Knowledge and Data
Engineering, 18(12):1721–1725, 2006.

[7] Donald R. Slutz. Massive stochastic testing of sql. In
VLDB’98, Proceedings of 24rd International Conference on
Very Large Data Bases, August 24-27, 1998, New York City,
New York, USA, pages 618–622. Morgan Kaufmann, 1998.

[8] Meikel Poess and Jr. John M. Stephens. Generating thousand
benchmark queries in seconds. In VLDB’2004: Proceedings of
the Thirtieth international conference on Very large data
bases, pages 1045–1053, 2004.

[9] Nicolas Bruno and Surajit Chaudhuri. Flexible database
generators. In VLDB ’05: Proceedings of the 31st
international conference on Very large data bases, pages
1097–1107. VLDB Endowment, 2005.

[10] Kenneth Houkjaer, Kristian Torp, and Rico Wind. Simple
and realistic data generation. In VLDB ’06: Proceedings of the
32nd international conference on Very large data bases, pages
1243–1246. VLDB Endowment, 2006.

[11] Carsten Binnig, Donald Kossmann, and Eric Lo. Reverse
query processing. In ICDE, pages 506–515. IEEE, 2007.

[12] IBM DB2. Test database generator.
www.ibm.com/software/data/db2imstools/
db2tools/db2tdbg/.

[13] Carsten Binnig, Donald Kossmann, Eric Lo, and M. Tamer
Özsu. Qagen: generating query-aware test databases. In
SIGMOD Conference, pages 341–352, 2007.

[14] Michael Emmi, Rupak Majumdar, and Koushik Sen.
Dynamic test input generation for database applications. In
ISSTA ’07: Proceedings of the 2007 international symposium
on Software testing and analysis, pages 151–162, 2007.

[15] David Willmor and Suzanne M. Embury. An intensional
approach to the specification of test cases for database
applications. In ICSE ’06: Proceeding of the 28th
international conference on Software engineering, pages
102–111, New York, NY, USA, 2006. ACM.

332