Database Reference
In-Depth Information
Two transitions are in confl ict if there is some common state that would be exited
if any one of them were to be taken (Harel & Naamad, 1996). Nonconfl uent statecharts,
or systems, are caused by non-determinism of execution and confl icting transitions in the
statecharts. In other words, when a statechart encounters non-determinism (that is, when
there is more than one possible execution sequence of the confl icting transitions in a step),
the fi nal database state may be different due to a different order of execution of the confl ict-
ing transitions. However, for some confl icting transitions, a different order of execution
may still lead to the same fi nal database state after the statechart becomes stabilized. This
is because they do not have a read-write racing problem or a write-write racing problem,
which are defi ned as follows:
Two transitions t
1
and t
2
and t
2
and t have a read-write racing problem if t
1
reads the value of a data item
x and t
2
x and t
2
x and t writes a value to x.
Two transitions t
1
and t
2
and t
2
and t have a write-write racing problem if both t
1
and t
2
and t
2
and t write values to
a common data item x.
The two racing problems mentioned above are related to concurrency control problems
inherent in database management systems (Bhargava, 1999). In this research, however, we
adhere to the terminology used in the statechart literature. That is, we will keep using the
terms read-write racing problems and write-write racing problems.
Figure 9 demonstrates a read-write racing situation. In this example, when the event
“New Year” occurs, two transitions take place at the same time. Whether the new payment
will be based on the new interest rate or the old interest rate depends on which transition is
executed fi rst. In this case, the statechart is not confl uent.
We now introduce Algorithm 2, whose purpose is to identify a set of concurrently
executed transitions that may lead to non-confl uence.
Figure 9: A read-write racing problem
