Regression Test Selection for Database Applications - Advanced Topics in Database Research - page 155

TEST CASE REDUCTION ALGORITHMS
In the impact analysis phase (phase 1), the test cases traversing the modules that are
included in the fi rewall are selected for regression testing. However, this results in a rela-
tively large number of selected test cases, since the Component Firewall does not distinguish
between the modifi cation-revealing test cases and the non-modifi cation revealing ones.
Therefore, it is useful to explore new techniques to reduce the number of test cases selected
in phase 1 by concentrating on modifi cation revealing tests. In this section, we discuss two
such techniques. The fi rst technique is the Graph Walk technique. This technique works
when statement trace and statement components usages are available. In addition, it works
at both the inter-module level and intra-module level. The second technique is Call Graph
Firewall. It is an adaptation of the fi rewall regression testing technique proposed by Leung
and White for procedural programs (Leung & White, 1990a, 1990b). It works at the inter-
module level, utilizing the Call Graph of the database application and selecting test cases
based on the data fl ow dependency resulting from the various usages of database tables.

Graph Walk Technique
In the Graph Walk technique, we use control fl ow graphs of all modules in the applica-
tion and its modifi ed version, and trace-information linked to control fl ow nodes. We also
utilize the dependency created between statements and various database components.
Applying this technique to a module, we traverse the control fl ow of the module and
its modifi ed version. When a pair of nodes N and N* in the graphs of the original module
and its modifi ed version are discovered (i.e., the statements associated with N and N* are
different), this technique selects all tests from the test suite that reach N in the original
program. For two nodes N and N* to be different, at least one of the following conditions
must be satisfi ed:

(a) N and N* are lexically different,
(b) N uses a modifi ed component,
(c) N uses a component that is not used by N*, or
(d) N* uses a component that is not used by N.

To extend the technique to the inter-module level, we should change condition (b) to
become: N uses a modifi ed non-module component. Moreover, for each module call linked
to a control fl ow graph node N we should perform the Graph Walk algorithm recursively on
this module and intersect the result with the test cases passing through node N.
In Figure 7 we give the Graph Walk algorithm. It takes two modules as parameters Graph Walk

and returns a list of test cases to retest. This algorithm is based on the Compare algorithm
that works on the control fl ow graph nodes. The Compare algorithm takes two control fl ow
nodes: one from the original module and the other from the modifi ed version, and it returns
the test cases passing through the original node that should be retested. The Compare algo-
rithm is presented in Figure 8. It calls the Is_Different algorithm that checks whether two Is_Different

control fl ow nodes satisfy one of the four conditions listed earlier. Figure 9 gives the details
of the Is_Different algorithm. Is_Different

To optimize the performance of the Graph Walk in the inter-module level, we save
the results of the Graph Walk algorithm for each module. This will prevent performing the

Is_Different algorithm.