Generating meaningful test databases [Elektronische Ressource] / vorgelegt von Carsten Binnig

Carsten Binnig

Sujets

• Informatik

Informations

• Publié par: ruprecht-karls-universitat_heidelberg
• Publié le: 01 janvier 2008
• Nombre de lectures: 18
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

INAUGURAL - DISSERTATION
zur
Erlangung der Doktorwürde
der
Naturwissenschaftlich-Mathematischen Gesamtfakultät
der
Ruprecht-Karls-Universität
Heidelberg
vorgelegt von
M.Sc. Carsten Binnig
aus Buchen
Tag der mündlichen Prüfung: 15.4.2008GENERATING MEANINGFUL TEST DATABASES
Gutachter: Prof. Dr. Donald Kossmann
Prof. Dr. Barbara PaechAbstract
Testing is one of the most time-consuming and cost-intensive tasks in software development
projects today. A recent report of the NIST [RTI02] estimated the costs for the economy of the
Unites States of America caused by software errors in the year 2000 to range from$22.2 to$59.5
billion. Consequently, in the past few years, many techniques and tools have been developed to
reduce the high testing costs. Many of these techniques and tools are devoted to automate various
testing tasks (e.g., test case generation, test case execution, and test result checking). However,
almost no research work has been carried out to automate the testing of database applications (e.g.,
an E-Shop application) and relational database management systems (DBMSs). The testing of a
database application and of a DBMS requires different solutions because the application logic of
a database application or of a DBMS strongly depends on the contents of the database (i.e., the
database state). Consequently, when testing database applications or DBMSs new problems arise
compared to traditional software testing.
This thesis focuses on a specific problem: the test database generation. The test database genera-
tion is a crucial task in the functional testing of a database application and in the testing of a DBMS
(also called test object further on). In order to test a certain behavior of the test object, we need to
generate one or more test databases which are adequate for a given set of test cases. Currently, a
number of academic and commercial test database generation tools are available. However, most
of these generators are general-purpose solutions which create the test databases independently
from the test cases that are to be executed on the test object. Hence, the generated test databases
often do not comprise the necessary data characteristics to enable the execution of all test cases.
In this thesis we present two innovative techniques (Reverse Query Processing and Symbolic Query
Processing), which tackle this problem for different applications (i.e, the functional testing of
database applications and DBMSs). The idea is to let the user specify the constraints on the test
database individually for each test case in an explicit way. These constraints are then used directly
to generate one or more test databases which exactly meet the needs of the test cases that are to be
executed on the test object.
iZusammenfassung
In heutigen Softwareentwicklungsprojekten ist das Testen eine der kosten- und zeitintensivsten
Tätigkeiten. Wie ein aktueller Bericht des NIST [RTI02] zeigt, verursachten Softwarefehler in
den USA im Jahr 2000 zwischen 22,2 und 59,5 Milliarden Dollar an Kosten. Demzufolge wur-
den in den letzten Jahren verschiedene Methoden und Werkzeuge entwickelt, um diese hohen
Kosten zu reduzieren. Viele dieser Werkzeuge dienen dazu die verschiedenen Testaufgaben (z.B.
das Erzeugen von Testfällen, die Ausführung von Testfällen und das Überprüfen der Testergeb-
nisse) zu automatisieren. Jedoch existieren fast keine Forschungsarbeiten zur Testautomatisierung
von Datenbankanwendungen (wie z.B. eines E-Shops) oder von relationalen Datenbankmanage-
mentsystemen (DBMS). Hierzu sind neue Lösungen erforderlich, da das Verhalten der zu tes-
tenden Anwendung stark vom Inhalt der Datenbank abhängig ist. Folglich ergeben sich für den
Test von Datenbankanwendungen oder von Datenbankmanagementsystemen neue Probleme und
Herausforderungen im Vergleich zum traditionellen Testen von Anwendungen ohne Datenbank.
Die vorliegende Arbeit diskutiert ein bestimmtes Problem aus diesem Umfeld: Die Generierung
von Testdatenbanken. Die Generierung von Testdatenbanken ist eine entscheidende Tätigkeit
für den erfolgreichen Test einer Datenbankanwendung oder eines Datenbankmanagementsystems
(im weiteren Verlauf auch Testobjekt genannt). Um eine bestimmte Funktionalität des Testob-
jekts zu testen, müssen die Daten in den Testdatenbanken bestimmte Charakteristika aufweisen.
Zur Erzeugung einer Testdatenbank existieren verschiedene Forschungsprototypen wie auch kom-
merzielle Datenbankgeneratoren. Jedoch sind die existierenden Datenbankgeneratoren meist Uni-
versallösungen, welche die Testdatenbanken unabhängig von den auszuführenden Testfällen erzeu-
gen. Demzufolge weisen die generierten Testdatenbanken meist nicht die notwendigen Daten-
charakteristika auf, die zur Ausführung einer bestimmten Menge von Testfällen notwendig sind.
Die vorliegende Doktorarbeit stellt zwei innovative Ansätze vor (Reverse Query Processing und
Symbolic Query Processing), die dieses Problem für unterschiedliche Anwendungen (d.h. für das
funktionale Testen von Datenbankanwendungen und Datenbankmanagementsystemen) lösen. Die
generelle Idee beider Ansätze ist, dass der Benutzer explizit für jeden Testfall die notwendigen
Bedingungen an die Testdaten formulieren kann. Diese Bedingungen werden dann dazu genutzt,
um eine oder mehrere Testdatenbanken zu generieren, die die gewünschten Datencharakteristika
aufweisen, welche zur Ausführung der Testfälle notwendig sind.
iiAcknowledgments
First of all, I would like to express my deep gratitude to Professor Donald Kossmann who super-
vised and guided my research work in the last three years together with Professor Barbara Paech.
From the very beginning Professor Donald Kossmann put trust in me and motivated me to strive
for the highest goals. While I was struggling with some hard research problems, he encouraged
me to continue and he showed me that I need to step back and see the big picture. Moreover, he
spent much time with me to discuss the pros and cons of doing a PhD even before I started to work
with him.
Furthermore, I would also like to thank Professor Barbara Paech. Without her help it would not
have been possible for me to conduct my research work at the University of Heidelberg. She
always put trust in me and gave me all the support that I needed to follow my research interests.
Moreover, there are a lot of other people who supported me during the last three years:
In the first place, I would like to thank Eric Lo. Together with him, I spent a vast amount of
time behind closed doors in productive discussions about our crazy research ideas. We constantly
motivated each other which finally made our both dreams come true.
Alike, I would also like to thank José A. Blakeley who supported me in applying my research ideas
to an industrial environment at Microsoft Corporation in Redmond. Moreover, he introduced me
to many other nice and supportive colleagues who assisted me in realizing my research ideas for
Microsoft in a very short time.
Furthermore, life would not have been as much fun without all the other colleagues and students
at the University of Heidelberg and at the ETH Zurich. Especially, I would like to mention my
colleague Peter Fischer in Zurich who helped me in many technical and administrative issues in
a completely unselfish way. Alike, I would like to thank two students, Nico Leidecker and Daniil
Nekrassov, who helped me in implementing some of my concepts.
Finally, I would like to thank my wife Daniela and my family for their enduring support while I
was working on my research ideas in the past few years.
iiiContents
I Preliminaries 1
1 Introduction 2
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Contributions and Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background 7
2.1 Software Testing: Overview and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Testing Database Applications and DBMSs . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Generating Test Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Resume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
II Reverse Query Processing 19
3 Motivating Applications 20
4 RQP Overview 23
4.1 Problem Statement and Decidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 RQP Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 RQP Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Reverse Relational Algebra 29
5.1 Reverse Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.2 Reverse Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.3 Reverse Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.4 Reverse Join, Cartesian Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.5 Reverse Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.