Here we will show an execution of the algorithm and how it traverses through a
lattice. A hypothetical
discernibility matrix will be used. The process of generating the
matrix from an information
system has assumingly been done prior to this stage.
The discernibility matrix is shown in Table
. This will be written as , a shortcut for describing the contents
of the matrix. Note that the condition
attribute d should not be confused as a decision attribute.
| - | a | b, c | |
| a | - | c, d | |
| b, c | c, d | - |
Figure: An example of a lattice traversal.
The nodes in the lattice will be visited in the order shown in Figure
. The top node is visited first. Since there are
three different elements in the discernibility matrix at this node,
there are three possible directions to go from here. Either of all occurrences
of the attributes in the sets , , or can be removed
in order to create inconsistencies. Following that
order, a is first removed from the matrix, which is then being
passed in the recursive
call. Therefore the node (b c d) is visited next. The
next element to be removed is . The only attribute in the
discernibility
matrix is now (d), so this node is visited. This last element is
then removed, and node () is visited at the bottom of the
lattice. All nodes are marked when they are returned from, in order not
to visit them again.
From here it is not possible to go further down the lattice, so the execution returns to node (d). It is now not possible to explore down from here neither, so the execution goes back one more step to (b c d). At this node, the discernibility matrix is . The path with (b, c) removed has already been explored, so this time (c, d) is removed in the call to the node with what is left, and that is node (b). The only node under this is () has been visited earlier, so the program does not go there. Instead, it returns all the way to the top node, since there are nowhere to explore until it reaches this node. From the original discernibility matrix, the attributes in the element (b, c) is removed in the call to node (a d). In the same fashion, nodes (a) and (a b) is visited to complete the traversal of the lattice and the execution of the algorithm.
%