Category Archives: Conceptual modelling

Theoretical Basis of Object-oriented Analysis

Posted on by
Reply

Classification is the core activity of object-oriented analysis. Classification is the means via which people order knowledge according to the similarities they recognize between different objects they observe in the world. The specific classification approach that is applied when doing object-oriented analysis is called classical categorization. Classification, in specific classical categorization, does not pertain to object-orientation alone, but rather, it reflects how people think in general about the world [1] [2] [3]. Olive explains the need and use of classification as follows [2]:

Classification provides cognitive economy because it allows us to structure knowledge about objects into two levels: concept and instance. At the concept level, we find the properties (both defining and nondefining) common to all instances of the concept. At the instance level, we find only the concept of which the object is an instance, and the particular properties of that instance. In the absence of classification, we would have to associate every instance with all of its properties. Classification reduces the amount of information we have to remember, communicate, and process; the extent to which it is reduced depends on the number of properties of the concept.

It is precisely this cognitive economy, provided by a complete and consistent object-oriented conceptual schema, that is the essence of enabling efficient communication between stakeholders of software development projects. When software development projects decide to forgo the creation of conceptual schemas, it is at the cost of efficient communication.

 

Notice that classification is inherently set theoretic. Sets have a characteristic function that essentially determines from a possible universe of elements, which elements belong to the set. With classification commonalities between instances are recognized which cause us to classify these instances as belonging to the same concept. In this way concepts and sets are equivalent.

 

Bibliography

[1] G. Booch, R. A. Maksimchuk, M. W. Engel, B. J. Young, J. Conallen and K. A. Houston, Object-oriented analysis and design with applications, Addison-Wesley Professional, 2007.

[2] A. Olive, Conceptual modeling of information systems, Springer, 2007.

[3] G. Lakoff, Women, fire and dangerous things: what categories reveal about the mind, Chicago: University of Chicago Press, 1990.

What are Description Logics?

Posted on by
Reply

Description logics (DLs) are syntactic variants of first-order logic that are specifically designed for the conceptual representation of an application domain in terms of concepts and relationships between concepts [1].

 
Expressions in DLs are constructed from atomic concepts (unary predicates), atomic roles (binary predicates) and individuals (constants). Complex expressions can be built inductively from these atomic elements using concept constructors. Formally a concept represents a set of individuals and a role a binary relation between individuals [2].

 

Formally every DL ontology consists of a set of axioms that are based on finite sets of concepts, roles and individuals. Axioms in a DL ontology are divided into the TBox, the RBox and the ABox. A TBox is used to define concepts and relationships between concepts (that is the terminology or taxonomy) and an ABox is used to assert knowledge regarding the domain of interest (i.e. that an individual is a member of a concept). Depending on the expressivity of the DL used, an ontology may include an RBox. An RBox is used to define relations between roles as well as properties of roles [2].

 

A feature of DLs is that they have decidable reasoning procedures for standard reasoning tasks.  This means these reasoning procedures will give an answer, unlike undecidable reasoning procedures which may not terminate and thus may not give an answer.  A fundamental goal of DL research is to preserve decidability to the point that decidability is considered to be a precondition for claiming that a formalism is a DL. Standard DL reasoning algorithms are sound and complete and, even though the worst-case computational complexity of these algorithms is ExpTime and worse, in practical applications they are well-behaved [3].

 

Standard reasoning procedures for DLs are the following [2].

  • Satisfiability checking checks that every axiom in an ontology can be instantiated. Axioms that cannot be instantiated indicates that modelling errors exist within the ontology.
  • Consistency checking checks whether there are axioms that contradict each other, which again is indicative of modelling errors.
  • Subsumption checking checks whether an axiom subsumes another axiom, which is used for classifying axioms into a parent-child taxonomy.

 

Various DLs exist with different levels of expressivity and computational complexity. The most widely supported DL is SROIQ(D) which forms the mathematical basis of the W3C OWL 2 standard [4]. In OWL concepts are referred to as classes, roles are referred to as properties and individuals are still referred to as individuals.

 

In subsequent posts I will provide an intuitive understanding of OWL 2 and explain some of its uses. If you are using OWL or other semantic technologies, I will love to hear from you. Please leave a comment and feel free to explain the novel ways in which you use semantic technologies.

 

Bibliography

[1] D. Berardi, D. Calvanese and G. De Giacomo, “Reasoning on UML class diagrams,” Artificial Intelligence, vol. 168, no. 1-2, p. 70–118, 2005.

[2] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi and P. F. Patel-Schneider, The Description Logic Handbook: Theory, Implementation and Applications, Cambridge University Press, 2007.

[3] F. Baader, “What’s new in Description Logics,” Informatik-Spektrum, vol. 34, no. 5, p. 434–442, 2011.

[4] W3C, “OWL 2 Web Ontology Language – Document Overview (Second Edition),” W3C, 11 December 2012. [Online]. Available: https://www.w3.org/TR/owl2-overview/. [Accessed 9 September 2017].

The Rectangle/Square Controversy

Posted on by
Reply

A software design problem that has often been discussed in the literature is whether a square should inherit from a rectangle or whether a rectangle should inherit from a square? Two opposing arguments are made by Meyer [1] and Martin, et.al. [2], both of which seem to have some merit. How is a software developer to decide which is the correct design? In this post I will discuss why I believe both approaches are wrong and I will provide the solution I prefer.

Meyer [1] proposes the design where square inherits from rectangle with square imposing the invariant that the width must equal the height. The conceptual design is shown in Figure 1. This design makes sense since a square “is-a” rectangle. Remember, that “is-a” is the litmus test for inheritance [3]. To state this more precisely: inheritance defines a subset relation between a child and a parent class. Thus, the Square class represents the set of squares which is a subset of the set of rectangles which is represented by the Rectangle class. This is shown in Figure 2. For a detailed discussion on the mathematical semantics of inheritance, see Meyer [1]. The implementation is shown in Figure 3.

Figure 1: Square extends Rectangle

Figure 1: Square extends Rectangle

Figure 2

Figure 2: The set of squares is a subset of the set of rectangles

Figure 3

Figure 3: The implementation of a Square extending a Rectangle

Martin’s criticism against the design of Figure 1 is that it violates the Liskov substitution principle, which states that subtypes must be substitutable for their base types [2]. Clients of instances of the Square class cannot set the width and height of a square as if they are using a rectangle. In particular they need to ascertain that the width and height of instances of square are equal. The main problem is that a square does not require both a width and a height and it therefore needs to ignore either of the attributes.

An alternative design that Martin discusses is where the setWidth (respectively setHeight) method is changed to set the height equal to the width (respectively to set the width equal to the height). However, the problem is when setWidth (respectively setHeight) is called it will overwrite the value of the height (respectively width) (see Figure 4). Hence, a client that first sets the width to 5 and then the height to 3 will expect the perimeter to be 16, but instead it will be 12. This again violates the Liskov substitution principle.

Figure 4

Figure 4: Forcing the width and height to be equal

The solution that Martin [2] proposes is that the Rectangle class must inherit from the Square class (see Figure 5). The objection that Meyer has against this design is that it violates the “is-a” relation in that a rectangle is not a square. Now you may reason that a rectangle is indeed a square when its width and height are equal, but the crucial point is that a rectangle is not always a square. Remember, inheritance enforces a subset relation between a child and a parent. That is, all instances of the child are necessarily instances of the parent, but not all instances of the parent are necessarily instances of the child.

The flaw in the solution that Martin proposes is that he uses inheritance for the sole purpose of reuse without there being an “is-a” relation. Meyer calls this “convenience inheritance” which should be avoided.

Figure 5

Figure 5: Rectangle extends Square

From a conceptual perspective a way around these objections is to introduce a class (i.e. Quadrilateral) from which both the Rectangle and Square classes can inherit. The related UML class diagram is shown in Figure 6. The {incomplete, overlapping} annotation indicates that other quadrilaterals may exist and that rectangles may occasionally be squares (when width=height).

Figure 6

Figure 6: Conceptual solution for Square and Rectangle problem

The implementation of this conceptual solution can be done where Quadrilateral is either an interface or an abstract class. Figure 7 shows the implementation where Quadrilateral is defined as an interface.

Figure 7

Figure 7: A correct implementation for the Square and Rectangle classes

Naturally I am not the first to point this solution out. [5] gives a general discussion of the problem and [4] provides a solution similar to mine.

Bibliography

[1] B. Meyer, Object-oriented software construction, Prentice Hall, 1997.

[2] R. Martin and M. Micah, Agile principles, patterns, and practices in C#, Prentice Hall, 2006.

[3] G. Booch, R. A. Maksimchuk, M. W. Engel, B. J. Young, J. Conallen and K. A. Houston, Object-oriented analysis and design with applications, Addison-Wesley Professional, 2007.

[4] R. Carr, “Is a Square a Rectangle?,” [Online]. Available: http://www.blackwasp.co.uk/SquareRectangle.aspx.

[5] H. Makabee, “When a square is not a rectangle,” [Online]. Available: http://effectivesoftwaredesign.com/2010/09/20/when-a-square-is-not-a-rectangle/.