Conceptual models are often built with techniques which propose a strict stratification of entities into two classification levels: a level of types (or classes) and a level of instances. Despite that, there are several situations in which domains of inquiry transcend the conventional two-level stratification and domain experts use types of types (or categories of categories) to articulate their conceptualizations. In these settings, types are instances of other types and multiple levels of classification can be identified (individuals, classes, metaclasses, metametaclasses, and so on), characterizing what is now called “multi-level modeling”. Over the last years, we have worked out a foundational theory for multi-level modeling (dubbed MLT), whose aim is to clarify the basic elements of multi-level conceptual modeling. This paper describes the development of this theory, and reports on some of its applications, namely: the detection of (thousands of) occurrences of anti-patterns in the Wikidata knowledge base and the revision of the powertype pattern in UML.
Conceptual modeling is a complex task that involves understanding a subject domain
In the conventional two-level representation scheme, a conceptual model is
stratified into entities in two levels: a level of types (or classes) and a level of instances. The
level of types captures invariants which apply exclusively to the level of individuals. In
this scheme, the subject matter can be understood as consisting of individuals, and the
purpose of the conceptual model is to establish which structures of individuals are
admissible according to some (shared) conceptualization of the world [
The two-level scheme, however, reveals its limitations whenever categories
of categories are part of the domain of inquiry. In this setting, we are
interested not only in invariants about individuals but also about categories themselves
[Carvalho and Almeida 2018]. For example, in the military domain, experts often
refer to “vessel types”, “vessel classes” or “ship classes” in their accounts. Instances
of VESSEL TYPE, such as CARGO SHIP, CIVILIAN SHIP, SUBMARINE,
SUPERCARRIER or NIMITZ-CLASS AIRCRAFT CARRIER are themselves types, instantiated by
individual vessels. For instance, the USS ABRAHAM LINCOLN (an aircraft carrier of
the United States Navy) is an instance of both the SUPERCARRIER and NIMITZ-CLASS
AIRCRAFT CARRIER types. In their turn, SUPERCARRIER and NIMITZ-CLASS
AIRCRAFT CARRIER are instances of VESSEL TYPE. Thus, to describe the
conceptualization in this domain, one needs to represent entities of different (but nonetheless
related) classification levels, such as specific ships out there in a mission, types of ships,
and (even) types of types of ships (VESSEL TYPE, SUBMARINE TYPE, CARGO SHIP
TYPE). Other examples of multiple classification levels come from domains such as
that of organizational roles (or professional positions) [Carvalho and Almeida 2015],
software engineering [
The need to support the representation of subject domains dealing with multiple
classification levels has given rise to what has been referred to as “multi-level modeling”
[
Over the last years, we have worked out a foundational theory for multi-level modeling (dubbed MLT), whose aim is to clarify the basic elements of multi-level conceptual modeling. Our investigation was motivated by the lack of (language-independent) foundations for multi-level modeling. In particular, we were driven by the need to clarify (and thereby demystify) the semantics of multi-level modeling constructs as well as to justify modeling choices. This paper describes the development of this theory, and reports on two applications, including: the detection of (thousands of) occurrences of anti-patterns in the Wikidata knowledge base and the revision of the powertype pattern in UML.
This paper is further structured as follows. Section 2 motivates multi-level modeling by discussing the workarounds which are required when we are confined to two levels of classification. Section 3 leads us into multi-level modeling territory, introducing briefly the MLT theory by discussing its key definitions, and presenting rules that arise out of these definitions. Sections 4 and 5 discuss how MLT was applied to identify problems in Wikidata multi-level taxonomies as well as to revise the UML support for powertypes. Finally, section 6 provides concluding remarks and outlines current research in this topic.
(This is an invited paper to accompany the keynote speech delivered by the first author at the 2018 Ontobras Seminar on Ontology Research in Brazil. It focuses on some of the contributions that were offered in successive publications over the last three years, including [Almeida et al. 2017, Carvalho and Almeida 2018, Brasileiro et al. 2016b, Carvalho et al. 2017, Carvalho et al. 2015], a Ph.D. thesis [Carvalho 2016] and two M.Sc. thesis [Brasileiro 2016, Fonseca 2017]. It does not cover formalization and related work. We refer the reader to these other publications for details.)
Let us consider the biological taxonomy domain as a paradigmatic example of a
multilevel domain [
In the conventional two-level approach, entities in the domain have to be classified
either as classes (or types) or as instances. Strictly speaking, there is no room for
metatypes such as SPECIES or meta-meta-types such as TAXONOMIC RANK. Workarounds
are available as discussed in [
Species 1
*
Organism
Lion
This creates a number of difficulties, some of which are discussed in
[
In the Semantic Web lightweight ontologies, a workaround called punning
explores this duplication as a semantic approach. In order to maintain a strict separation of
terminological (T-Box) and assertion (A-Box) fragments, a class is also considered as an
individual in the A-Box when it instantiates another class. Its interpretations as a class
and as an individual are completely independent of each other. This “independent”
interpretation means that a constraint stated to a class will not be considered when it is seen as
an individual, which leads to non-intuitive interpretations [
The two-level workarounds fail to address the root of the problem: there are in fact
two facets to classes, and classes may themselves be regarded as instances of other
(meta)classes [
First of all, an essential requirement1 for a multi-level modeling theory is to account for
entities of multiple classification levels, which are related through chains of
instantiation between the involved entities (requirement R1). This means that the theory must
admit entities that represent both types (class) and instances (object) simultaneously
[
Second, the size of chains of instantiation may vary according to the nature of
the phenomena being captured and according to the model purposes. Because of this,
a general-purpose theory should admit an arbitrary number of classification levels (R2)
(including the two-level scheme as a special case). The ability to deal with an
arbitrary number of levels is identified as a key a requirement by many authors (e.g., see
[
Further, in previous work, some of us have found empirical evidence to support
the claim that representations capturing chains of instantiation can benefit greatly from
rules for organizing entities into levels [Brasileiro et al. 2016a]. This is because when
chains of instantiation relations are allowed, developers need support to avoid producing
incorrect models. The so-called “level-blind” approaches [Atkinson et al. 2014] fail to
provide such support. We have found that over 87% of the classes in multi-level
taxonomies in Wikidata were involved in errors that could have been prevented with some
support to detect the inadequate use of instantiation (and its combination with subtyping).
Based on this evidence, we consider that a multi-level modeling theory should define
principles (rules) for the organization of entities into levels (R3). An example of this sort
1These requirements are based in [Brasileiro et al. 2016b, Almeida et al. 2017]. [Carvalho 2016]
reviews the multi-level modeling literature to corroborate these requirements.
of principle, which is adopted in some prominent multi-level modeling approaches, is the
strict metamodeling principle [
Finally, an important characteristic of domains spanning multiple levels of
classification is that there are domain rules that apply to the instantiation of types of different
levels. For example, in a conceptual model encompassing the notions of DOG BREED and
DOG, all instances of DOG BREED (e.g. COLLIE and BEAGLE) are types whose instances
are instances of DOG. Hence, in this setting, instances of DOG BREED specialize DOG.
Given the recurrence of this kind of scenario [
Based on the requirements discussed in the previous section, we have defined an axiomatic theory to establish key notions in multi-level modeling, building up on the primitive notion of instantiation. The resulting theory (MLT) can be considered a reference top-level ontology for types in multi-level conceptual modeling.
The theory quantifies over individuals and types alike. Types are organized into stratified levels related by instantiation. We have called these levels “orders” to distinguish this principle of organization from other principles in the multi-level modeling literature.
In this section, we present informal definitions to introduce the reader to the theory and its applications. For a formalization of the theory in first-order logic, see the original paper describing it [Carvalho and Almeida 2018]. A formalization in the lightweight formal method Alloy is also available in https://nemo.inf.ufes.br/mlt/. The formalization in Alloy was instrumental in exploring the various alternatives for MLT; an iterative design cycle with simulation of implied models and verification of the various theorems was performed with the support of the Alloy analyzer.
Individuals are those entities which cannot possibly play the role of type in the instantiation relation. Examples include ALBERT EINSTEIN, CECIL THE LION and the 1985 MEXICO CITY EARTHQUAKE.
First-order types are those types whose instances are individuals. Examples include PERSON, ADULT, LION, ANIMAL, ORGANISM, EARTHQUAKE, NATURAL DISASTER, EVENT.
Second-order types are those types whose instances are first-order types. Examples include PERSON TYPE BY AGE, ANIMAL SPECIES, SPECIES, EVENT TYPE. Third-order types are those types whose instances are second-order types (TAXONOMIC RANK), and so on. The topmost order can be established as required by applications, and the scheme can thus be extended to cope with an arbitrary number of levels.
Using the basic framework outline above, a number of intra-level and cross-level
relations are defined in MLT. This was done in order to account for the notion of
powertype, more specifically clarifying and positioning conflicting definitions
A categorization relation between types was defined to reflect Odell’s notion of powertype [Odell 1994]. Differently from Cardelli’s, Odell’s definition excludes the base type from the set of instances of the powertype. Further, not all specializations of the base type are required to be instances of the powertype. Odell’s definition corresponds more directly to the notion of powertype that was incorporated in the UML. Thus, there may be specializations of the base type that are not instances of the categorizing higher-order type. For example, we may define a type named ORGANISM TYPE BY HABITAT (with instances TERRESTRIAL ORGANISM and AQUATIC ORGANISM) that categorizes ORGANISM. ORGANISM TYPE BY HABITAT is not a (Cardelli) powertype of ORGANISM since there are specializations of ORGANISM that are not instances of ORGANISM TYPE BY HABITAT (e.g. PLANT and GOLDEN EAGLE) [Brasileiro et al. 2016b].
Specializations of the categorization relation were defined in order to capture different scenarios of categorization: disjoint categorization, to accommodate the cases in which each instance of the base type is instance of at most one instance of the higher-order type; complete categorization, when each instance of the base type is instance of at least one instance of the higher-order type; and partitioning, when an instance of the base type is instance of exactly one instance of the higher-order type.
The consequences of the theory can be used to identify sound multi-level structures, including the following derived rules (these rules are formally proven theorems that follow from the MLT definitions and axioms):
The instance of relation in MLT is irreflexive, antisymmetric and anti-transitive. Further, it only relates entities of adjacent levels, in a strictly stratified scheme; Specialization is a partial order (i.e., a reflexive, antisymmetric and transitive relation); Proper specialization is a strict partial order (i.e., an irreflexive, antisymmetric and transitive relation); Specialization (whether proper or not) cannot cross level boundaries (i.e., a firstorder type can only be specialized by first-order types, a second-order type can only be specialized by second-order types, and so on).
Both relations is powertype of and categorizes can only be applied between adjacent levels, with the base type one order lower than the high-order type; The powertype of a base type (in Cardelli’s sense) is unique for that base type; Types that categorize a base type always specialize the base type’s powertype; If two types partition the same base type then they cannot specialize each other.
As we will show in section 4, some of these rules can be employed to detect problems in knowledge bases which include multi-level taxonomies. They are not available to level-blind approaches and are also not available to users of the powertype pattern that emulate the instantiation relation with an association without specialized semantics. Further, as we will show in section 5, these rules can serve as a basis to inform the revision of the UML powertype pattern, along with corresponding tool support.
The theory also accounts for attributes of high-order types, and a phenomenon
called deep instantiation [
An early application of MLT concerned the assessment of the multi-level taxonomies in the structured Wikidata knowledge base. The Wikidata project aims to create a structured version of the content in Wikipedia, thereby facilitating automated querying and processing. Wikidata structures its knowledge base into the so-called “items” encompassing classes and individuals alike. “Statements” capture information about “items”, using property–value pairs resulting in a linked data structure.
Two properties are central to structure the content in Wikidata and can be applied to any item: the instance of (P31) and subclass of (P279). The definition of instance of provided in Wikidata is informal and silent about its formal logic properties (concerning symmetry, reflexivity and transitivity). In its turn, subclass of is explicitly characterized as transitive and asymmetric (i.e., antisymmetric and irreflexive) (corresponding to proper specialization). By chaining the instance of property, Wikidata can represent many levels of instantiation (R1, R2). However, since Wikidata is silent about formal logic properties of instance of, it offers no special support both for organization of entities along levels (not satisfying R3). We have observed that this leads to a number of representation issues.
To access data, we used the simplified and derived RDF dumps of Wikidata from January 4th, 2016, available at RDF Exports from Wikidata2. Moreover, we have queried these using SPARQL, where instance of and subclass of are represented as rdf:type and rdfs:subClassOf, respectively. The total number of classes involved in taxonomic hierarchies is 337,102. This number is obtained by counting the items that are either a subject or an object in subclass of statements. From this total number of items, 17,819 classes are also the object of instance of statements, which means they are simultaneously classes and instances of other classes, and thus involved in hierarchies spanning more than one level of classification (our target classes for this investigation). 2http://tools.wmflabs.org/wikidata-exports/rdf/
In order to obtain some indication of the use of multi-level hierarchies in Wikidata, we have queried for three simple cases of anti-patterns that violate the MLT stratification of types into orders [Brasileiro et al. 2016a].
We highlight here two anti-patterns detected. For the first one
The structure of this first anti-pattern is shown in Figure 2. The pattern violates stratification of orders with a combination of subclassing (any depth) and instantiation. Occurrences of this pattern in Wikidata are shown in the right-hand side of the figure. In the first fragment, COMPUTER SCIENTIST is a subclass of PROFESSION. Since TIM BERNERS-LEE is declared to be an instance of COMPUTER SCIENTIST we are forced to conclude that Tim is an instance of PROFESSION(!), which clearly violates our sense of what professions and persons are. Formally, these statements are inconsistent in the light of MLT: since instance of is anti-transitive and COMPUTER SCIENTIST is instance of PROFESSION, Tim cannot be declared instance of PROFESSION. The mistake is probably the subclassing of PROFESSION into CREATOR. If the subclassing statement is removed, we are able to stratify the model into levels, and recognize that PROFESSION is a secondorder type, while its instances are first-order types. In the second fragment, EARTHQUAKE is considered both an instance of, and a specialization of NATURAL DISASTER. Considering that instances of NATURAL DISASTER are specific events, i.e., specific occurrences of natural disasters, then these instances are attributed a point in time. For example, we can say that the “1985 Mexico City earthquake” took place on “September 19th, 1985”. However, since EARTHQUAKE is also declared to be an instance of NATURAL DISASTER, EARTHQUAKE itself—a type!—can be said to occur at a specific point in time. In this example, it seems that the undesired relation is the instance of relation between EARTHQUAKE and NATURAL DISASTER, and perhaps, there is a missing NATURAL DISASTER TYPE second-order class.
Natural Disaster
Earthquake instance of
For a second anti-pattern
A instance of
A reference ontology can be used to inform the revision and redesign of a
modeling language, not only through the identification of semantic overload, construct
deficit, construct excess and construct redundancy [Guizzardi 2015], but also through
the definition of modeling patterns and semantically-motivated syntactic constraints
[
Basically, the powertype pattern in UML follows Odell’s work. However, differently from what was discussed in section 2, the UML 2.x support for powertypes relies on a construct called “generalization set”. A generalization set is a means to identify sets of specializations (or generalizations as they are called in UML). Each generalization is a binary relation between two classes, and these binary relations are bundled in a “generalization set”. The generalization set is then annotated with constraints and, optionally, a powertype (in Odell’s sense) of the type being specialized. Figure 4 revisits the example of Figure 1, now using UML 2.x powertype support. Although a regular association is still used to relate the base type to the powertype, the powertype becomes a powertype in the model through its role in a generalization set (hence, differently from the two-level workaround discussed in section 2, there is some explicit support for powertypes). 3In Figure 3, we abuse the diagrammatic notation and do not distinguish between classes and individuals. 4We emphasize the version number here, since the support for the powertype pattern in the now obsolete version 1.x was quite different.
The only syntactic constraint defined in UML concerning powertypes is that “the
classifier that maps to a generalization set may neither be a specific nor a general classifier
in any of the generalization relationships defined for that generalization set” [
Further, a key observation is that for a classifier to be considered a “powertype” in UML, it must be related to a generalization set. Thus, in UML, the powertype pattern can only be applied when specializations of the base type are explicitly modeled (otherwise there would be no generalization set). We consider this undesirable as it rules out simple models such as one defining SPECIES as a “powertype” of ORGANISM, without forcing the modeler to “hardcode” specific instances for SPECIES. Thus our first recommendation concerning the UML support for powertypes is to drop the reliance on generalization sets.
Our solution is to mark the association between the base type and the higher order type with the instantiation stereotype, in order to distinguish it from other domain relations that do not have an instantiation semantics. An association stereotyped instantiation represents that instances of the target type are instantiated by instances of the source type and, thus, denote that there is a categorization relation between the involved types (regardless of possible generalization sets). Variations of the categorization—disjoint categorization, overlapping categorization and partitioning—can be identified through the target cardinality of the instantiation association (0..* in the case of categorization, lower bound 1 in the case of complete categorization, upper bound 1 in the case of disjoint categorization and exactly 1 in the case of partitioning). Figure 5 shows this recommendation in use, revisiting the biological taxonomy example, with no explicit subtypes of ORGANISM required.
Species 1 Whenever a modeler wants to make generalization sets explicit, this is allowed in the usual way, as shown in Figure 6. Note that the constraints on the generalization set are not identical to those in the categorization. In this particular case, SPECIES partitions ORGANISM, which means that it completely and disjointly categorizes ORGANISM. This reflects a domain conceptualization that considers every organism to belong to exactly one species. However, the generalization set is marked incomplete, reflecting the fact that there are other instances of SPECIES that are not explicitly enumerated in the generalization set.
Species 1
The MLT profile establishes rules concerning the constraints that can be employed in combination with instantiation associations: (i) in the case of a (non-complete) categorization (lower bound 0 in the target of the instantiation ), a generalization set marked with the higher-order class cannot carry a complete constraint; (ii) in the case of disjoint categorization and partitioning (upper bound 1 of the instantiation relation), a generalization set marked with the higher-order class cannot carry an overlapping constraint. Figure 7 shows an example of an invalid combination of constraints that can be detected by the syntactic constraints in the MLT profile. If the generalization set is marked complete, than any instance of PERSON must instantiate also at least one of the subclasses MAN or WOMAN. However, the lower bound 0 indicates that there are instances of PERSON which do not instantiate instances of PERSON TYPE BY GENDER. This leads to a contradiction, and either: (i) the constraint should be amended (e.g., changed to incomplete, thereby admitting in the conceptualization persons with no gender), or (ii) the lower bound should be fixed to 1 (to establish that every person instantiates a PERSON TYPE BY GENDER).
Person Type by Gender 0..*
0..* :Person Type by Gender fcompleteg
Person Man
Woman Our final recommendation is to use the powertype stereotype to represent Cardelli’s notion of powertype. If a class stereotyped powertype is the target of an instantiation association, then it is the (Cardelli) powertype of the base type. An example of this is shown in Figure 8, with the introduction of the ORGANISM TYPE powertype for ORGANISM. Because of the semantics of Cardelli’s powertype, all other specialization of ORGANISM are instances of ORGANISM TYPE, including in this example MALE LION and LIONNESS, which are not instances of SPECIES. The lower bound of the association attached to ORGANISM TYPE is 1, because all instances of ORGANISM are at least instances of ORGANISM, which is, by definition, an instance of ORGANISM TYPE. Finally, the specialization between SPECIES and ORGANISM TYPE can be inferred automatically, since all types that partition a base type specialize that type’s unique powertype . This corresponds to our intuition that every SPECIES is an ORGANISM TYPE.
powertype Organism Type
Species 1..* 1 :Species fdisjoint, incompleteg fdisjoint, completeg Male Lion
Lionness
In this paper, we have briefly described the MLT Multi-Level Theory and discussed two of its applications. Other applications of MLT thus far include: (i) a combination with the Unified Foundational Ontology (UFO) to equip it with means to deal with secondorder types in ontology-driven conceptual modeling [Carvalho et al. 2017]; (ii) the design of a core ontology for organizational structure modeling [Carvalho and Almeida 2015]; and (iii) the design of an OWL vocabulary to support the representation of multi-level vocabularies in the Semantic Web [Brasileiro et al. 2016a].
MLT differs from a number of related works in multi-level conceptual modeling given its focus on conceptual modeling (rather than language engineering) and further given the use of formal tools in its conception. A contribution of MLT to the literature on multi-level modeling concerns the study and harmonization of different notions of powertype in the literature, as well as a formal harmonization of powertype and clabjectbased approaches.
Recently, we have extended MLT in order to account for types that do not fit
a particular order and thereby defy a strict stratification scheme [Almeida et al. 2017].
This was necessary as this scheme rules out abstract and general types such as ENTITY
and TYPE (which are instances of themselves). We have observed that these types
correspond to general notions that are ubiquitous in comprehensive conceptualizations, see e.g.,
(foundation) ontologies such as UFO [Guizzardi 2015], Cyc [
Using MLT*, we have designed a text-based multi-level modeling language called ML2 [Fonseca 2017, Fonseca et al. 2018]. ML2 incorporates the rules of MLT* into its syntax, and an Eclipse-based editor that supports live verification of ML2 models ensures adherence to the theory. The use of a formally-verified semantic foundation is one of the distinctive features of ML2 when compared to other multi-level modeling approaches in the literature [Fonseca et al. 2018].
Our ongoing investigation concerning the theoretical aspects os multi-level
modeling includes:
(i) the full integration of MLT* as a microtheory of the Unified Foundational Ontology
Concerning the various applications, we intend to investigate in the near future:
(i) the incorporation of the UML profile for MLT into the OntoUML profile
[Guizzardi 2015];
(ii) the development of an integrated constraint language to further increase the
expressiveness of ML2;
(iii) the development of transformations from ML2 into the Semantic Web approach
discussed in [Brasileiro et al. 2016a] and into the Alloy-based model simulation
tooling we have built for OntoUML [