Databases Reference
In-Depth Information
number of concrete values. In particular, if two attributes share at least the
70% of their values, KLFA assigns them to the same two-elements data clus-
ter. KLFA identifies data clusters as the transitive closure of the two-elements
data cluster relation: If we consider a graph where nodes are attributes and
edges represent the two-elements data cluster relation, the data clusters are
the connected components of the graph.
For example, one of the data clusters that KLFA automatically identi-
fies from the execution traces in Figure 2.2 is composed of the following at-
tributes: attribute
persons
of event
bookFlight
, attribute
persons
of event
getAvailableFlights
, attribute
return.seats
of event
findBestSolution
,
attribute
return.seats
of event
findCompositeSolution
, and attribute
solution.seats
of event
book
.
2.5.1.2
Global Ordering Rewriting Strategy
The simplest way to annotate traces with data-flow information is to con-
sistently replace all occurrences of the same concrete value with the same
symbol, for example, a number. KLFA incrementally introduces numbers ac-
cording to the order of appearance of new values. Thus, the first concrete value
that occurs in a data cluster is rewritten with a
1
, the second concrete value
is rewritten with a
2
if never observed before, otherwise the same number
is consistently used, and so on for all attribute values within a data cluster.
The numbers represent the re-occurrence by abstracting from concrete values.
This rewriting strategy is named global ordering rewriting strategy. The new
event labels are obtained by concatenating the event names with the numbers
produced by the global rewriting strategy.
Since the attribute
persons
of event
bookFlight
is always assigned with
a same value within a trace (see the traces in Figure 2.2), the global rewriting
strategy would replace all occurrences of this value with the same symbol
1
.
This replacement identifies the re-occurrence of the value assigned to
persons
,
i.e., all the rewritten traces contain the symbolic value
1
for the attribute
persons
.
Since the attributes of the events
bookFlight
,
getAvailableFlights
,
findBestSolution
,
findCompositeSolution
, and
book
belong to the same
data cluster, the global rewriting strategy will replace all attributes with the
same symbolic value. Table 2.1 shows the symbolic values used to replace the
concrete values associated with these attributes: column # indicates the po-
sition of the event in the original trace in Figure 2.2, column Events reports
the name of the event, column Attributes indicates the name of the rewritten
attribute, while columns Actual Values and GO show the value associated to
the attribute in the trace and the symbolic value derived by applying the global
rewriting strategy. Table 2.1 shows that in all the four considered executions
the global ordering rewriting strategy generates the same symbolic values for all
the values in the data cluster thus suitably identifying their re-occurrence. We
can observe that the execution traces 1 and 2 are rewritten in the same way.
Search WWH ::
Custom Search