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

Figure 7: The Graph Walk algorithm

Graph Walk ( Graph Walk ( Graph Walk M , M1 ) : T

if module M is not visited then visited visited then

mark M as visited
S := Start_Node ( M )
S1 := Start_Node ( M1 )
Retest ( M ) := Compare ( S , S1 )

T := Retest ( M )

return T

algorithm more than once in case there was more than one call to the same module in the
module Call Graph .
The Compare algorithm recursively calls itself on the successor nodes of the current
nodes to traverse all the graph nodes of the original and modifi ed modules. It also collects test
cases that should be called due to module calls. Term Test(N) denotes the test cases that reach
node N. To prevent the algorithm from running endlessly we mark the visited nodes.
Function Component (N) in the Is_Different algorithm returns the database components
used by node N. In the fi rst step of the Is_Different algorithm, we check whether the nodes

Is_Different
are lexically different. In the next steps, we check for differences resulting from the usage
of database components.
Next, we discuss the results of applying the Graph Walk reduction algorithm on the

previous example for each modifi cation case.

Figure 8: The Compare algorithm

Compare ( N1 , N2 ) : T

mark node N1 as visited

if Is_Different ( N1 , N2 ) then
return test( N1 )

for each module M1 in CALL( N1 )
let M2 be the corresponding module in the modifi ed application
T := T U (test( N1 ) ∩ Graph Walk ( Graph Walk ( Graph Walk M1 , M2 ))

for each successor node s1 of N1 and corresponding node s2 in N2
if s is not visited then
T := T U Compare ( s1 , s2 )

return T