Databases Reference
In-Depth Information
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