Databases Reference
In-Depth Information
Sequential Constraints
c
1
c
2
c
3
c
4
c
5
c
6
c
7
...
f
1
● ●
●
●
f
f
3
f
4
f
5
f
6
f
7
f
8
...
●
●
violation
s
● ●
●
●
●
● ●
● ●
● ●
● ●
●
●
●
●
●
FIGURE 12.6: Sample matrix used as an input to formal concept analy-
sis. Each rectangle corresponds to a pattern; gaps indicate potential viola-
tions. (From [4,8,9]. c 2007, 2010 Association for Computing Machinery, Inc.
Reprinted by permission; and c 2009 IEEE.)
ically obtain sequential constraints (arriving in the end at a set of sequential
constraints particular to each function). However, not every set of sequential
constraints is a specification. Consider the following, hypothetical set:
retval of
Random()
target of
nextInt()
target of
nextInt()
target of
nextInt()
retval of
Random()
1st arg of
println()
target of
nextInt()
1st arg of
println()
The first two sequential constraints in this set can be thought of as being
a specification for one of the possible uses of the
Random
class, but the same
cannot be said about the last two constraints. The fact that the
Random
object
is passed to
println()
is in reality just noise. Such noise can appear in se-
quential constraints obtained from a particular function, or several functions.
To cope with this problem, we will restrict ourselves to sets of sequential con-
straints that occur frequently (i.e., sets that consist of sequential constraints
that occur in sequential constraints abstractions of many functions). In our
example above, if there are many functions that use
Random
and repeatedly
call
nextInt()
on objects of this type, but only a few functions pass these ob-
jects to
println()
, then the last two sequential constraints will be discarded
as not being part of the true specification. This learning by eliminating noise
is done by formal concept analysis.
Concept analysis is, broadly speaking, a technique for finding patterns [2].
We use the Colibri/Java tool for formal concept analysis [5]. We feed Colibri/-
Java with a matrix A = (a
ij
) as an input. In that matrix, rows are functions
from the analyzed program (denoted f
1
;:::;f
k
, where k is the number of the
functions), and columns are sequential constraints (denoted c
1
;:::;c
n
, where
Search WWH ::
Custom Search