Use case diagrams are the core diagrams of the Unified Modeling Language (UML), de facto standard for software modeling. They are used to visualize relations between the users (Actors) and the functionality of the software system (Use Cases). Galois sub hierarchy (GSH) is a sub-order of the concept lattice that contains only concepts with object or attribute labels. This paper investigates the viability of GSH for visualizing the information contained within use case diagrams. While it is possible that a GSH diagram is more complex than a use case diagram for certain formal contexts a study of 87 student projects found no such case. On average, use case diagrams had 3.7 times more graphical elements than corresponding GSH diagrams, demonstrating the viability of GSH as a more compact alternative to the use case diagram.
Software engineering has a long tradition of graphical modeling, there are many
different diagram types like flowcharts, BPMN, ERD and even languages like
UML containing over dozen diagram types. Most of these diagrams have
elements connected with directed or non-directed connections. Each element is
represented as a node and each connection as a line between these nodes. While
this approach is easy to understand and apply, methods of Formal Concept
Analysis (FCA) like Galois sub hierarchies (GSH) can represent the same information
in a more concise way, significantly reducing the number of graphical elements.
This is achieved because a single node in GSH diagram can represent several
elements (it can have many labels) and a line can represent many connections.
This conforms to the “reduce redundant data-ink” principle from E. Tufte’s
classic work on visual information displays [
GSH diagrams are most natural to use when there are two types of elements and connections between these (a bipartite graph). This applies to the UML use case diagram that describes actors, use cases and connections between them. A study presented here compares the GSH approach with the UML use case diagram. There is also a brief overview about describing the connections between use cases and data tables with diagrams, information present in CRUD matrix, another traditional software engineering artifact. c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 21{32, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes.
Our method of visual representation is based on Galois sub- hierarchy (GSH)
diagrams from the field of Formal Concept Analysis (FCA). This article uses
some FCA terminology (formal concept, concept lattice, extent, intent) without
explanation and definitions, these can be found from many foundational articles
of this field [
This work differs from the standard FCA practice as the main area of interest is not finding the concepts but visualizing the connections between the elements of G and M in a concise way. Semantics of G and M can vary: objects and attributes, use cases and actors, use cases and data tables. Users of GSH diagrams would need to be acquainted with the following properties to see the connections between G and M : 1. GSH diagrams show nodes (concepts), connections between them and labels from the sets G and M attached to the nodes. Each element from G and M has exactly one corresponding label. 2. g ∈ G is connected to m ∈ M iff there is an upward path from label g to label m or they are labels of the same node. 3. If g1, g2 ∈ G and there is an upward path from g1 to g2 then the set of elements g2 is connected to, g20, is a subset of g10. 4. Dually, if m1, m2 ∈ M and there is a downward path from m1 to m2 then the set of elements m2 is connected to, m02, is a subset of m01. 5. If g1, g2 ∈ G and g1 and g2 are labels of the same node then g20 = g0 . 1 6. Dually, if m1, m2 ∈ M and m1 and m2 are labels of the same node then m02 = m01.
Figure 1 presents a simple formal context where G = {1, 2, 3, 4, 5, 6} and M = {a, b, c, d, e, f } and its corresponding GSH diagram.
a b c d e f 1 2 x 3 4 5 6 x x
x x x x x x x
There are several tools for concept lattice generation: Concept Explorer
[
Use Case modeling is a common tool for specifying functional requirements. An
actor is something with behavior (person, computer system) who interacts with
our system. A use case is a collection of related success and failure scenarios that
describe an actor using a system to support a goal [
Following example (Figure 2) is redrawn from Craig Larmans partial use case
diagram describing NextGen sales system: a computerized application used to
record sales and handle payments in a retail store [
Extend and include arrows correspond to the direction of reference within the use case documentation. In the case of an include relation, use case containing the sub-functionality has a reference to it, in the case of an extend relation, the sub-functionality has a reference to the use case containing it. Extend relation is treated here as an include relation going to the opposite direction.
A method used here to deal with the include and extend relations is to focus on a single level of abstraction (preferably user goal or summary ). Use cases at higher or lower levels of abstractions are removed and their relations to actors are added to the use cases they have include/extend relations with. This can introduce superfluous relations: it is impossible to deduce from the use case diagram if a particular actor from the higher level use case participates in certain sub-functionality or not, use case text has to be examined for that.
Figure 5 shows how previous diagram (Figure 4) has been flattened as described to the user goal abstraction level through the removal of generalization and include relations and is now in the form that can be used for GSH generation.
GSH diagrams scale well when the number of use cases increases. Figure 6 is based on the example project Chair in University from the course “Introduction to information systems” in Tallinn University of Technology. Original documentation had entire use case model split into four use case diagrams containing 25 use cases, 3 actors and 30 connections between actors and use cases. These 4 diagrams are not reproduced here due to limited space. Equivalent GSH diagram contains 5 nodes and 4 lines. That is a significant improvement in conciseness.
In the previous examples GSH diagrams have all been simpler (less nodes, less connections) than use case diagrams. It is easy to see that GSH diagram can have no more nodes than the corresponding use case diagram as each GSH node must have at least one label and labels don’t repeat. However, for certain contexts, GSH diagram can have more connections than the corresponding use case diagram, as shown in the following example.
Figure 7 shows a formal context with 16 connections and a corresponding GSH diagram with 18 connections. That raises a question if GSH diagrams are really simpler than use case diagrams for practical applications. Following study tries to answer this. A study of 87 student projects, that were presented to the author for 2012 “Introduction to information systems” course, was completed to compare the use case and GSH diagrams. Student projects contained the analysis documentation for a freely chosen information system, including use case diagrams. Some of these projects were done in groups and were larger and there was also a variation of effort and quality. For all these projects a corresponding GSH diagram was generated, based on its use case diagram.
Some diagrams contained generalization relations between actors. In this case sub-actors inherited all the relations from super-actors in the corresponding formal context. Some diagrams contained include relationships between use cases. For these cases, only use cases at the user goal level were kept, use cases included in these and their connections with actors were merged into the user goal level use cases as described in the previous section. Use case and connection counts are for diagrams after removing the use cases not at the user goal level of abstraction but before the removal of generalization relations. Generalization relation is counted as one line.
Ratio between the average number of elements of the use case diagrams and the GSH diagrams is (U C + A + L)/GSHC+L = 3.72.
Figure 8 shows the scatter plot of student projects showing the number of visual elements on use case and GSH diagrams. It is easy to see that in all cases GSH diagram was simpler than use case diagram, as all the data points lie below the diagonal (U C + A + L) = GSHC+L line. This confirms that, at least for the information systems with 30 or less use cases, GSH diagrams are much more concise than the use case diagrams.
Use case diagrams have their own advantages. They are easier to sketch and modify by hand and they are easier to decompose into several diagrams. That seems to suggest complementary roles for use case and GSH diagrams, use case diagrams for quick sketching and GSH diagrams for a well-formated and concise view of the system.
Use cases are not only connected to the actors who require such a functionality
but they operate on data tables. GSH diagrams are useful for modeling these
connections too. CRUD matrix is a well known artifact of software engineering
that describes relations between data tables and use cases. It is described in
several popular books about systems design [
Table 2 contains a CRUD matrix for a simplified library system. Columns correspond to data tables and rows to use cases. Letters c, r, u, d inside the cells of the matrix correspond to 4 basic actions. For example, use case Add New Task reads data from the table Employee and creates (adds) new data to the table Task.
We can think of a CRUD matrix as defining dependencies between use case layer and data layer. To describe only dependencies we introduce a new binary matrix where all entries with no actions in the original CRUD matrix are replaced with 0 and all entries with at least one action are replaced with 1. We refer to such a matrix as a usage matrix. Table 3 is a usage matrix for Table 2.
It is obvious that usage matrix, and therefore GSH diagram, can be generated automatically from CRUD matrix. That kind of tool could provide visual representation of CRUD matrix without extra effort from the tool user.
Figure 9 is a GSH diagram based on the usage matrix from Table 3. From the GSH diagram it is much easier to see the elements with same dependencies, like use cases Add loan and Return loaned book and disconnected subsystems, like use case Manage Readers with data table Reader. GSH diagrams are also helpful for detecting hidden similarities/isomorphisms between different contexts. It is much easier to see that GSH diagrams from Figures 1 and 9 are isomorphic than that matrices from Figure 1 and Table 3 are isomorphic. 6
The use of methods of FCA for software engineering is not a novel idea. A
thorough survey of FCA support for software engineering activities is given in
[
Dolques et al [
Wolfgang Hesse and Thomas Tilley [
GSH diagrams can be a concise replacement for UML use case diagrams. In our study they had 3.7 times less visual elements. GSH diagrams are likely to be useful wherever there are connections between two types of elements: actors and use cases, use cases and data tables, use cases and classes, business processes and use cases and so on.
One area for further research is the software engineering activity of grouping elements into subsystems. Similar use cases can be grouped into functional subsystems, similar data tables can be grouped into registers. GSH and concept lattice diagrams can help here by organizing elements by similar connections. Use cases that depend on the same data tables are likely to be similar. Grouping elements with similar connections into same subsystems would also help to minimize the connections at subsystem level. GSH diagrams can also be used to visualize the subsystem level connections, thus promising to be a quite universal tool for software engineering.