Softw Syst Model DOI 10.1007/s10270-016-0521-5 THEME SECTION PAPER Formalization of the classification pattern: survey of classification modeling in information systems engineering Chris Partridge1,2 · Sergio de Cesare1 · Andrew Mitchell 2 · James Odell 3 Received: 14 February 2015 / Revised: 29 February 2016 / Accepted: 3 March 2016 © The Author(s) 2016. This article is published with open access at Springerlink.com Abstract Formalization is becoming more common in all stages of the development of information systems, as a better understanding of its benefits emerges. Classification systems are ubiquitous, no more so than in domain model- ing. The classification pattern that underlies these systems provides a good case study of the move toward formaliza- tion in part because it illustrates some of the barriers to formalization, including the formal complexity of the pat- tern and the ontological issues surrounding the “one and the many.” Powersets are a way of characterizing the (com- plex) formal structure of the classification pattern, and their formalization has been extensively studied in mathemat- ics since Cantor’s work in the late nineteenth century. One can use this formalization to develop a useful benchmark. There are various communities within information systems engineering (ISE) that are gradually working toward a for- malization of the classification pattern. However, for most of these communities, this work is incomplete, in that they have not yet arrived at a solution with the expressiveness of the powerset benchmark. This contrasts with the early smooth adoption of powerset by other information systems communities to, for example, formalize relations. One way of understanding the varying rates of adoption is recogniz- ing that the different communities have different historical baggage. Many conceptual modeling communities emerged from work done on database design, and this creates hur- Communicated by Prof. Colin Atkinson, Thomas Kühne, and Juan de Lara. B Sergio de Cesare sergio.decesare@brunel.ac.uk 1 Brunel University London, London, UK 2 BORO Solutions, London, UK 3 James Odell Associates, Ann Arbor, MI, USA dles to the adoption of the high level of expressiveness of powersets. Another relevant factor is that these communities also often feel, particularly in the case of domain modeling, a responsibility to explain the semantics of whatever formal structures they adopt. This paper aims to make sense of the formalization of the classification pattern in ISE and surveys its history through the literature, starting from the relevant theoretical works of the mathematical literature and gradu- ally shifting focus to the ISE literature. The literature survey follows the evolution of ISE’s understanding of how to for- malize the classification pattern. The various proposals are assessed using the classical example of classification; the Linnaean taxonomy formalized using powersets as a bench- mark for formal expressiveness. The broad conclusion of the survey is that (1) the ISE community is currently in the early stages of the process of understanding how to formalize the classification pattern, particularly in the requirements for expressiveness exemplified by powersets, and (2) that there is an opportunity to intervene and speed up the process of adoption by clarifying this expressiveness. Given the central place that the classification pattern has in domain model- ing, this intervention has the potential to lead to significant improvements. Keywords Classification system · Classification · Powerset · Powertype · Set theory 1 Introduction Classification (in the everyday sense) is ubiquitous [28, 36,102]. This should not be surprising; classifications are one of the major ways we organize things in the world. Biologists classify our species as Homo sapiens and our pet dogs as Canis lupus familiaris; governments classify 123 -- 1 of 37 -- C. Partridge et al. us in all sorts of ways. Wherever we need to organize information of any size, indeed whenever we think, we start classifying. In “Primitive Classification,” Durkheim and Mauss [28] argued that the sophistication of the clas- sification system reflected the sophistication of the culture using it—more sophisticated cultures used more sophisti- cated classifications. In “The Order of Things,” Foucault [36] described how classification systems have evolved over time. The history of information shows an obvious correlation between the amount of information available and the nature of its classification; as the amount of information grows, more instances of classification as well as more sophisticated classification structures emerge (Ong [86]). Furthermore, the nature of the storage medium plays a role in shaping the kind of structures that emerge (Olson [82]). One would expect the emergence of computer sys- tems to follow this evolutionary pattern. It can already be seen that computers lead to substantial increases in the amount of information and how this has led to a need for better classification systems. Computers, unlike their paper precursors, are formal systems; this suggests that one avenue for improvement would be a more formal structure. However, there is currently no survey that examines this. This paper aims to start to fill that gap. It surveys how the formalization of the classification pattern has emerged and evolved in information systems engineering (ISE). It briefly tracks the history of its emergence and builds a picture of the current status. This survey identifies a small number of communities cur- rently working in this area, with different approaches and with different underlying formalizations. This necessitates the creation of a framework and benchmark against which to assess them. A classic example, the Linnaean classification, is chosen as a benchmark example. A mathematical frame- work is developed for characterizing the formal structure of classification, and this is used to expose the formal structure of the chosen example. This is described in the first part of the paper. With this framework and benchmark in place, the ISE liter- ature is reviewed revealing a variety of emerging approaches. Their underlying formalizations are analyzed, benchmarked, and compared. This exposes a general slow adoption over time of the formal structures needed for the classification pattern, as well as different adoption routes and stages in different communities. The conclusion of this research is that the way to formalize classification is being explored by the ISE community, but that this has not yet arrived at a mature stable mainstream state. The hypothesis is that both the formal complexity of the pattern and the require- ment for an explanation of what the formal structures being proposed represent (a semantic-ontological narrative about what aspect of reality they are reflecting) contribute to the slow adoption. This is described in the second part of the paper. 1.1 Why classification is being formalized now As a community acquires more information, this creates a corresponding need to improve its classification systems. For example, if a community is originally only interested in five or ten objects in a domain, there is little need for a sophisti- cated classification system. When this increases to a couple of hundred, there is need for a simple system. For exam- ple, Lakoff’s [66] title “Women, Fire and Dangerous Things” refers to one of the four basic categories hard-wired into the language of a preliterate community. When this increases to thousands or millions, the need for a more sophisticated system becomes overwhelming. Observers of information technology revolutions (such as Ong [86] and Olson [82]) have noted that these tend to encourage developments in classification systems, driven in part by increases in the volume of information. They give as examples one of the earliest systems of classification, the Aristotelian categories, which emerged in Ancient Greece as writing was establishing itself, and the Linnaean classifica- tion, which emerged as printing established itself. There seems to be a similar situation now with the com- puting (information technology) revolution. Many of the methods of classification used currently were developed for paper technology, prior to the emergence of computing; how- ever, the classifications and the data they classify are now typically stored on computers. Computer storage not only offers opportunities for increasing the amount of data stored, it also offers opportunities for structuring the data in ways that paper technology does not. Computers operate within more formal structures, so one of the first hurdles facing the more informal, implicit paper-based classification pat- terns in their migration to computer systems is formalization. This then opens the door to opportunities for innovation and improvement, to deal with the increases in the volume of data. This paper starts to look within ISE at how the for- malization of the techniques for classifying has emerged and developed. 1.2 What is the classification pattern? The term “classification” has a variety of senses, typically associated with kinds of classification systems. Our inter- est is in a pattern that can be discerned at the core of these classification systems, which underpins its structure, what we therefore call the “classification pattern.” In our formal analysis, we highlight this pattern and characterize its struc- ture. Our focus on this specific pattern is to enable us to 123 -- 2 of 37 -- Formalization of the classification pattern make clearer comparisons. It is not to dismiss any of the other senses. 1.3 Separating the concerns One of the issues faced when starting to build up a picture of the classification pattern in computing is that there were several competing concerns. As well as the requirement to represent the classifications in the domain, there are compet- ing implementation requirements on the representation that distort the picture. To resolve this, the question of what is being represented is separated from how it is implemented in a particular system. The survey is only concerned with the first aspect—what is being represented—independent of any implementation requirement. This kind of separation of concerns approach is well estab- lished in computing and software engineering. The Object Management Group’s (OMG) Model-Driven Architecture (MDA) is a well-known example; in their terms, the focus here is on the Computational Independent Model (CIM). It is also important to separate the core of the classification pattern, whose formal structure can be exemplified by pow- ersets and subsets, from more general peripheral concerns. For example, powersets are a mechanism for generating higher-order sets (types). However, as the formal exposition below shows, higher-order sets (types) are not sufficient, by themselves, to characterize the classification pattern. Indeed, from some perspectives, they are not even necessary, as illustrated by the communities who have developed clas- sification pattern characterizations that deliberately exclude them (as described below). While higher-order types can use- fully be characterized using a particular notion of powertypes as powersets, this dependence is not symmetrical. Hence, while higher-order types may be a natural extension of one approach to the classification pattern, they are not a core ele- ment of it and so not a core concern of this paper. They are nonetheless important, and so we discuss future research into them in Sect. 8. 1.4 How to assess the formalization There are a number of communities currently working in this area, with different approaches and different underlying formalizations. These are, broadly speaking, communities with an interest in conceptual modeling. To assess their approaches, a benchmark framework was developed as described in the first part of the paper. The benchmark frame- work has three components. The first is an example of classification that is sufficiently rich to illustrate a reasonably broad set of requirements. For this, a classic example of classification from biology is used, the Linnaean classification. This is often seen in the literature on classification and because of its richness can be regarded as a classification system. The second is a formal structure for classification. We use a mathematical theory, set theory, with a particular emphasis on the mathematical object, the powerset (often called powertype in computing) and associated objects. The purpose of this structure was to provide sufficient formal detail to benchmark the classification structures under analy- sis. It is not intended to be a fully fledged formalization, to, for example, stand shoulder to shoulder and compete with the approaches reviewed here. Nor is there intended to be any suggestion that set theory (and its semantics) is the only possible way of formalizing these structures (indeed, as discussed below, there are competing formal approaches within mathematics). For us, it is one useful way of characterizing the structure we are looking at so we can benchmark it. The third component is built from the preceding com- ponents, it is an analysis of the selected example’s formal structure using the mathematical objects. This gives an insight into the underlying formal structure of the classifi- cation pattern. 1.5 ISE survey: assessing the formalization The benchmark framework was used to survey the evolution of the formalization. The survey starts by taking a brief gen- eral look at the adoption of the mathematical structures, to provide a benchmark against which to measure their adoption of a formalized classification structure. The paper then surveys the formalization by commu- nity. Three communities were found making significant contributions in this area; these communities are reviewed in some detail. The completeness of their formalization was analyzed against the formalized benchmark. More- over, the literature of a number of communities making indirect contributions was reviewed. This is described in the second part of the paper. Finally, a summary of the survey is provided, looking at how far the adoption has progressed across the communities, both from the perspec- tive of the mathematical structures and from the benchmark requirements. 2 The classification benchmark In this section, the classic example, i.e., the Linnaean bio- logical classification, is described. This example was chosen as the benchmark for the surveyed literature. The example is reasonably sophisticated and helps to illustrate the level of complexity that appears in real situations. An important benefit of choosing a classical biological example is that it is well studied. This does not mean the example is not rel- 123 -- 3 of 37 -- C. Partridge et al. Fig. 1 Linnaean classification scheme Fig. 2 Example individuals evant in other areas; there are many examples in business with a similar kind of classification structure; ISO 10962— Classification of Financial Instruments is a modern example. Biological classification is one of the earliest modern (after the emergence of printing) systems of classification. It is crystallized in the ranked system of Carl Linnaeus upon which the current Nomenclature Codes are based. One stan- dard definition of the classification is Mayr and Bock [75]: “The arrangement of entities in a hierarchical series of nested classes, in which similar or related classes at one hierarchi- cal level are combined comprehensively into more inclusive classes at the next higher level.” Carl Linnaeus published his classification system in the book Systema Naturae. This went through several editions, the first being published in 1735. The Linnaean system, in its original form, represented a classification of all natural things (including animals, plants, and minerals). In its mod- ern equivalent, it is primarily used as a classification of living organisms (animals and plants). The Linnaean system classifies livings organisms at dif- ferent levels known as ranks. In this example, there are five ranks: Kingdom, Class, Order, Genus, and Species. Each rank breaks down the classifications of the previous rank into finer detail. Figure 1 illustrates this breakdown. Individ- ual animals are typically shown as instances of the lowest level rank, Species; Fig. 2 has some examples. (Class is an overloaded term, but it should be clear from the con- text here that “Class” means Linnaean class and not some other sense; for example object-oriented class or set-theoretic class). Linnaeus’s Systema Naturae went through several edi- tions, with the classification updated in each. Subsequently, the classification continued to evolve. One aspect of the evolution was the emergence of different bases for the clas- 123 -- 4 of 37 -- Formalization of the classification pattern Fig. 3 Structure of the Linnaean classification scheme sification, for example, morphology-based phenetics and ancestor-based cladistics. More recently, Ghiselin [39] and Hull [54] suggest that instead of viewing species as natural kinds, they should be thought of as individuals. For the bench- mark example, the question of the “correct” classification is not material. What is required is merely an example of a suf- ficiently sophisticated classification structure. Hence, a basic Linnaean structure is adopted, as this is adequate for almost all the needs of this paper. There is an aspect of classification that this simple Lin- naean example by its nature does not illustrate; this is that something can be classified in multiple ways. Within the example, each individual organism is classified once and only once—at the lowest rank. To see that this might not be the whole picture, consider the phenetic and cladis- tic classifications mentioned above. In a system with both classifications, some individual organisms will be classified twice, once by each of the two systems, and some clas- sifications will have multiple parents. This is not an odd extreme situation. There are classification systems with this kind of multiple classification built into their framework. The colon classification developed by Ranganathan [101] for libraries is an unambiguous example. This has multiple classification taxonomies called facets, and every document is multiply classified under each facet. This is sufficient evi- dence that multiple classification is a requirement that should be supported by a reasonably sophisticated classification pattern. 2.1 Formal structure This paper is concerned with the formal structure of the cho- sen classification scheme. One common way of illustrating this is by substituting meaningless labels for names, show- ing the structure without the content (for a classic example, see the railroad map in Carnap’s The Logical Structure of the World [16]). This is done for Figs. 1 in 3. The aim of this work was to characterize the nature of this structure, irrespective of the content; elements of which would re-appear in other classifications. 3 Mathematical background Modern mathematics can be seen as the science of formal patterns, as described by Devlin [27] and Shapiro [105]. This makes it a good tool for capturing the formal structure of the classification pattern, such as that in Fig. 3. This section describes the mathematical objects needed for this. 3.1 Which mathematical theory? There is a choice of theories from which to select the required objects. The foundations of mathematics are an active research area, and there are three broad mathemati- cal theories in play. In historical order of emergence, these are set theory, type theory, and category theory. All these 123 -- 5 of 37 -- C. Partridge et al. theories contain the resources to characterize the classi- fication pattern and much else. While there are technical differences between the theories, these differences are not relevant for the purposes of this paper. In principle, the frame- work could be based upon any (or all) of the three theories. However, to simplify the exposition, this paper is based on one theory, set theory, as it is the most approachable for the non-specialist. For the interested reader, a brief overview of such differences and the relations between the theories is provided at the end of this section along with some useful references. 3.2 Scope Only a small core of the theory is required for the for- malization of the classification pattern. The interest of this study centers primarily on the mathematical object that set theory calls “powerset” and its associated objects, such as “set” and “subset.” Analogous objects appear in all three theories, sometimes with different suffixes. In type the- ory, the suffix “type” is used instead of set; it has types, powertypes, and subtypes. In category theory, there are objects called “set,” “powerset,” and “subset,” and these have been generalized to “objects,” “powerobjects,” and “subobjects.” In the literature, these terms are sometimes spelled as a single word (“powerset,” “powertype,” etc.), while at other times the two-word form is used (“power set,” “power type,” etc.). In this paper, the single word form will be adopted. This section will focus on the powerset, core to the formal structure of classification, and provide a brief overview of the formal structure of powersets and associated mathematical objects. Powersets are introduced in the next section from a simple historical perspective; for more detail on the early history, see Ferreirós [31], Kanamori [61], Van Heijenoort [117], and Grattan-Guinness [44]. 3.3 Powersets and related mathematical objects As subsequent sections will show, the ISE literature sur- veyed normally does not always have a sufficiently clear understanding of the mathematical objects underpinning the mathematical framework that this paper adopts. Hence, care is taken to describe the mathematical underpinnings in this section. Readers familiar with set theory can skim or skip this section. To assist the reader, the key symbols used are explained in Appendix. 3.3.1 Origin and definition of powerset Set theory is a core part of modern mathematics and is often employed as a foundational system for the whole of the disci- pline. Powerset is a key part of the theory and is commonplace in mathematics. Its origin can be traced back to Cantor’s [12] diagonalization theorem, which used but did not explic- itly mention powerset. The first explicit mention of powerset is in Zermelo’s [120] axiomatization of set theory, which includes among its axioms AXIOM IV: Axiom of the pow- erset (Axiom der Potenzmenge): ∀x ∃y ∀z [z ∈ y ≡ ∀w (w ∈ z → w ∈ x)] (1) Or, informally: To every set T, there corresponds a set T’, the powerset of T, that contains as elements precisely all subsets of T. It is from Zermelo’s axiomatization that powersets then became commonplace in mathematics. Zermelo’s axioma- tization was developed by Abraham Fraenkel retaining the powerset axiom, and the resultant Zermelo–Fraenkel theory, known as ZF, is the basis for the standard axiomatization used in mathematics today. In modern mathematics, the pow- erset of A is usually written as ℘ (A) (where ℘ is called the “Weierstrass p”). This convention shall be followed here. A simple example will help to illustrate what a powerset is. Consider the following set: A ≡ {Africa, Asia, Europe} The powerset of A or ℘ (A) is a set that has as members all the subsets of A; therefore, ℘ (A) ≡ { {Africa} , {Asia} , {Europe} , {Africa, Asia} , {Asia, Europe} , {Africa, Europe} , {Africa, Asia, Europe} } Figure 4 illustrates this example, showing visually that all subsets of A are members of ℘ (A) and all members of ℘ (A) are subsets of A. It also shows the instance-of-powerset relation between the power-instance and its power-set. Tradi- tionally, the empty set is considered to be a member of every powerset; however, there are nonstandard approaches that eschew this. To simplify presentation, particularly in rela- tion to the classification pattern, here and elsewhere in the paper, the empty set has deliberately been omitted from pow- ersets. The definition of a powerset uses the terms “set,” “mem- bers,” and “subsets.” These are part of a closely associated group of mathematical objects required in order to charac- terize the formal structure of classification. These elements are described in the following subsections. 3.3.2 Set (and members) Sets are often described as collections of objects. There is some debate as to how close the natural notion of collections 123 -- 6 of 37 -- Formalization of the classification pattern Fig. 4 Example powerset is to sets. For example, Black [10] suggests that there may be differences between set and collection, while Halmos [47] (p. 1) considers the two almost synonymous, stating: “A pack of wolves, a bunch of grapes, or a flock of pigeons are all examples of sets of things.” [47] Although mathematicians worked with sets before Cantor, it is Cantor who is closely associated with them due to a few often-cited descriptions: “By a ‘set’ we understand any collection into a whole M of definite well distinguished objects m of our intuition or thought.” [13] [A set as a] “many, which can be thought of as one, i.e., a totality of definite elements that can be combined into a whole by a law.” [13] This “one over many” argument has roots going back to Plato; for example, in [100], he writes “We customarily hypothesize a single form in connection with each collection of many things to which we apply the same name.” Plato’s dialogues contain arguments against this position, for exam- ple the “third man argument” in [99]. This argument was taken up by Aristotle, and the debate has generated significant discussion; a recent example is Fine [33]. Cantor’s resolu- tion, introducing an object that is both one and many, is now standard in set theory. However, a couple of the powertype strands we examine later do not accept the Cantorian reso- lution and propose a different approach. Hence, we use this formalization as a benchmark for classification functionality, rather than as a template for a solution. There are little or no constraints on what a set can be. Sets are arbitrary, and any collection of objects in a domain qualifies as a set as described by Ferreirós [32]. One modern view is that sets are defined by the member-of relation. It is said that A is a member-of the set B (in symbols A ∈ B), or that the set B contains A as its element. The importance of the member-of relation is shown by the way the identity of a set is determined by its members; two sets are equal if they have exactly the same elements as members. In Zermelo’s [120] set theory, this was enshrined in AXIOM I: Axiom of extensionality (Axiom der Bestimmtheit): ∀x ∀y[∀z(z ∈ x ≡ z ∈ y) → x = y] (2) Or, informally: If every element of a set M is also an element of N and vice versa, then M ≡ N. Briefly, every set is determined by its elements. 3.3.3 Ur-elements Some objects in a domain do not have members, so they are not sets. These are traditionally known as ur-elements (from the German prefix ur-, “primordial”). In the simple exam- ple above (Fig. 4), Africa, Asia, and Europe are ur-elements. This distinction can be seen as having similar formal prop- erties to the distinction between universals and particulars that started with Aristotle’s division into primary substance (particular, ur-element) and secondary substance (universal, set); in Categories, Aristotle [3] stated that primary substance cannot have instances, though it can be an instance, whereas a secondary substance typically has instances. 123 -- 7 of 37 -- C. Partridge et al. 3.3.4 Subset-of A subset is a set contained in another set. More formally, if A is a subset of B (this is equivalent to “B is a superset of A”) then every member-of A is also a member-of B. This can be written in a number of ways, as “x is a subset-of y” or “subset-of (x, y)” or “x ⊆ y” and is defined as: x ⊆ y iff ∀z (z ∈ x → z ∈ y). (3) From this definition, it follows that a set is a subset-of itself, a property known as reflexivity. ∀z(z is a Set → z ⊆ z). (4) From the definition, it also follows that the subset-of relation is transitive. A relation TR is transitive if xTRy (TR relates x to y) and yTRz implies that xTRz. Formally, ∀x ∀y ∀z (xTRy ∧ yTRz) → xTRz (5) In terms of the subset-of relation, this schema becomes: ∀a ∀b ∀c (a ⊆ b ∧ b ⊆ c) → a ⊆ c (6) Here is an example with the constants given a specific inter- pretation. A ≡ (set of) animals B ≡ (set of) mammals C ≡ (set of) dogs Here given that C is a subset-of B (i.e., all dogs are mam- mals) and B is a subset-of A (i.e., all mammals are animals), then C is a subset-of A (i.e., all dogs are animals). More formally, (A ⊆ B ∧ B ⊆ C) → A ⊆ C (7) These relationships are illustrated in Fig. 5. A common mistake for beginners is to conflate the subset- of and the member-of relations as, for example, noted in Partridge [88] and Kühne [63]. A good rule of thumb is that the subset relation is transitive, whereas the member-of rela- tion is not. This member-of intransitivity stratifies the sets into a leveled hierarchy—in a way that the subset-of relation does not. Subset-of (like sets) have few, if any, constraints. Given a set X and its members, then every combination of the mem- bers is also a set and a subset-of X. For example, given the set X = {1, 2, 3}, all of the following are sets with a subset-of relation to X: Fig. 5 Subset transitivity 1. {1, 2, 3}, 2. {1, 2}, 3. {2, 3}, 4. {1}, 5. {2}, 6. {3}. 3.3.5 Powerset expanded The objects defined above are required to understand the def- inition of powerset in Zermelo’s AXIOM IV (given above). The definition is expanded here with two of its consequences that show the relationship between subsets and members as this will prove useful in the exposition. Given a set T and its powerset ℘ (T): 1. All subsets of T are members of ℘ (T). 2. All members of ℘ (T) are subsets of T. More formally, ∀T ∀z [(z ⊆ T ) → (z ∈ ℘ (T ))] (8) ∀T ∀z [(z ∈ ℘ (T )) → (z ⊆ T )] (9) One way of viewing these two consequences is as closure rules. (8) can be seen as powerset-member closure—where any object that is recognized as a subset of the power-member (the set that is being “powerset-ed”) has also to be recognized as a member of the powerset. (9) correspondingly can be seen as a powerset-subset closure. In standard set theory, each set has one and only one pow- erset, and vice versa, each powerset is a powerset of one and only one set. In modeling terms, this is usually stated as the powerset-of relation is one-to-one. 123 -- 8 of 37 -- Formalization of the classification pattern 3.3.6 Set of subsets of a set (powerset-subset) A non-empty collection of subsets of a given set S is called a set of subsets of S, or a set of sets over S or a family of subsets of S. This can be regarded as weaker than the powerset as it meets (9), but not necessarily (8); as all instances of the “set of subsets of S” are subsets of S, there may be subsets of S that are not instances of the “set of subsets of S.” Another way of thinking of a “set of subsets of S” is of a subset of a powerset, a powerset-subset. The powerset of S will contain all the subsets of S. So any sets of subsets of S will be a subset of the powerset of S. The limiting case is where the set of subsets of S is all the subsets and so it is the powerset of S. The powerset of S is a powerset-subset of S because the subset relation is reflexive, so the powerset of S is a subset of itself. Formalizing this Powerset-Subset-Of relation can be done by deconstructing it into already existing relations. If x is a powerset-subset of y, then x is a subset of the powerset of y. More formally, Powerset-Subset-Of ≡ PSO (10) (< x, y >∈ PSO) ≡ (x ⊆ ℘ (y)) (11) Powerset-subsets, as subsets of a powerset, are subject to the powerset-member closure mentioned above. In other words, every member of the powerset-subset is also a subset of power-member. However, it is not subject to powerset- subset closure, for obvious reasons. It turns out that many simple classifications are powerset- subsets. This is illustrated in the following example. Consider the set {1, 2, 3}. Its powerset, ℘ ({1, 2, 3}), is a set of all its subsets—shown in Fig. 6. As the figure shows, there are various subsets of the powerset (in other words, powerset- subsets) that classify the original set: three-member sets, two-member sets, and one-member sets. A more compli- cated classification system will take these powerset-subsets as a ranking of the classifications by number of members—a topic presented later in the paper when the Linnaean example is examined. Unlike the powerset-of relation, the powerset-subset-of relation is many-to-many. Given a set of subsets of S, there are a number of other sets of which it could be the powertype- subset; any superset of S will be a candidate. Similarly, for a set S of a reasonable size, there will be a significant number of sets of subsets it could have. This makes the relation many-to- many. The following example will help to clarify this point. Consider the set S = {{1}, {2}}. S is a set of subsets for any set that has 1 or 2 as members, for example, any of the following sets and all their supersets qualify: {1, 2}, {1, 2, 3, 4}. Figure 7 represents this example. 3.3.7 Intersection and union of sets Two important operations that can be conducted on sets are intersection and union. The intersection of a group of sets is the set of elements that belong to every set in the group. For example, the intersection of the sets, {1, 2}, {1, 3} and {1, 4} is {1}. The union of a group of sets is the set of elements that belong to any set in the group. For example, the union of the sets, {1, 2}, {1, 3}, and {1, 4} is {1, 2, 3, 4}. Loosely speaking, two or more sets are said to be disjoint if they have no element in common, this is often stated as their intersection being empty. For example, {1, 2, 3} and Fig. 6 Example powerset 123 -- 9 of 37 -- C. Partridge et al. Fig. 7 Many-to-many powerset-subset-of relation {4, 5, 6} are said to be disjoint sets, whereas {1, 2, 3, 4} and {4, 5, 6} are not; in this case, one says that they “overlap.” More technically, a set of disjoint sets is a set whose members are sets that have no element in common; the set {{1, 2, 3}, {4, 5, 6}} is a set of disjoint sets. 3.3.8 Cover of S A (non-empty) set Z of non-empty subsets of S is called a cover (or covering) of S if the union of Z’s members is the original set S. For example, there is only a single cover of {1}, namely {1}. However, there are five covers of Y = {1, 2}, namely: 1. {{1}, {2}}, 2. {{1, 2}}, 3. {{1}, {1, 2}}, 4. {{2}, {1, 2}}, 5. {{1}, {2}, {1, 2}}. As this example shows, the subsets in a cover can overlap. Examples of sets of subsets of Y that do not cover it are: {{1}} and {{2}}. If Z is a cover of S, then Z is also a powerset-subset of S. Hence, the Cover-Of relation is a subset of the Powerset- Subset-Of relation, formally: Cover-Of ≡ CO (12) ∀x ∀y[(< x, y >∈ CO) → (< x, y >∈ PSO)] ≡ (CO ⊆ PSO) (13) The powerset can be divided by cover into two sets: the covering sets and the non-covering sets. Every set of subsets of S falls into one or the other of these two. Of course, one needs to know S to determine which side the set goes. 3.3.9 Partition of S A partition of a set S is a set of disjoint subsets whose union is S, in other words disjoint subsets of S that cover S. If Z is a partition of S, then Z is also a powerset-subset of S. Hence, the Partition-Of relation is a subset of the Cover-of and Powerset-Subset-Of relations, formally: Partition-Of ≡ PaO (14) ∀x ∀y [(< x, y >∈ PaO) → (< x, y >∈ CO)] ≡ (PaO ⊆ CO) (15) (PaO ⊆ CO) ∧ (CO ⊆ PSO) → (PaO ⊆ PSO) (16) The partition-set of a set S is the set of all partitions of S. A set of size n (i.e., with n members) can be partitioned into a fixed number of non-empty subsets; in other words, the partition-set has a fixed number of members. This can be calculated and is known as the Bell number. For example, there are five ways a three-membered set can be partitioned; so the partition-set has five members. This means that the Bell number for a set of size = 3 is 5. For example, the set of numbers {1, 2, 3} can be partitioned as follows: 1. {{1}, {2}, {3}} 2. {{1, 2}, {3}} 3. {{1}, {2, 3}} 4. {{1, 3}, {2}} 5. {{1, 2, 3}} The set of these five subsets is the set of partitions of the set {1, 2, 3}. Each one of the five members of this set is a partition of the set {1, 2, 3}. For each member partition, the union of all its members is the set {1, 2, 3}. The Bell number increases quickly, so for size = 10 it is 115,975. The partition-set of a set S is a subset of the powerset of S. An incomplete partition of a set S is a collection of disjoint subsets whose union is a subset of S, but not S itself (also known as a proper subset of S), in other words disjoint subsets of S that do not cover S. For example, the set of numbers {1, 2, 3} can be incompletely partitioned as: 1. {{1}, {2}} 2. {{1}, {3}} 123 -- 10 of 37 -- Formalization of the classification pattern 3. {{2}, {3}} 4. {{1, 2}} 5. {{2, 3}} 6. {{1, 3}} 7. {{1}}, 8. {{2}} and 9. {{3}}. 3.4 Reifying the operations Conceptual modeling prefers a declarative style, where things such as the relation between a set and its powerset are treated explicitly as a relation rather than, as in logic textbooks, as an operation. 3.4.1 Powerset-of relation The relation between a set and its powerset has already been identified as one-to-one. Also, from the above def- initions, it is known that the set is a member-of the powerset—as it is a subset of itself. So for each set-powerset combination, there is a unique member-of relation that links them; these are labeled powerset-of relations. More formally, Powerset-Of ≡ PO (17) ∀x ∀y [(< x, y >∈ PO) → (y ∈ x)] equivalent to (18) ∀x ∀y [(x = ℘ (y)) → (y ∈ x)] (19) 3.4.2 Powerset-subset-of The simplest declarative solution is to deconstruct this into two already existing relations. Saying that x is a powerset- subset of y is equivalent to saying that x is a subset of the powerset of y. More formally, Powerset-Subset-Of (x, y) ≡ PSO(x, y) (20) PSO (x, y) ≡ x ⊆ ℘ (y) (21) 3.5 A technical point 3.5.1 The powerset axiom and the universal set Though this is a technical matter and only indirectly of con- cern here, it is worth being aware that the topic exists. One of the areas of study in set theory is the universal set, see Church [18], Barwise and Moss [9], and Forster [35]. This is the set that contains all other sets as members, it is a way to formalize the statement “x is a set”; this becomes “x is a member-of the universal set.” However, it turns out that if one wants to include this in one’s formalization, then there are a number of formal trade-offs that need to be considered. One trade-off relates to the ZF powerset axiom which says that every set has a powerset. This is problematic as the cardinality (the num- ber of members) of a powerset is always greater than the original set. If one adopts this axiom as it stands and the universal set, then one arrives at an inconsistency. The pow- erset is a set and so a member-of the universal set. Every instance of the powerset is a set, and so a member-of the universal set, hence the powerset is a subset of the universal set. But it has more members than the universal set which is impossible. There are a number of technical ways of accommodat- ing this. ZF avoids the problem by having no universal set. Church [18] proposed a weaker powerset axiom. Quine proposed, in New Foundations, a subset of Cantorian sets to which the cardinality of the powerset axiom applied. While it is important to have a consistent formal struc- ture, the particular way of dealing with this issue does not affect the topic of this paper, and so is outside the scope. 3.5.2 The extensionality of set theory Set theory is extensional. This means that the extension, the members, of the set do not change and that two sets with the same extension (members) are the same set. This is an extraordinarily powerful criterion of identity. Any formal the- ory of a domain will need to provide a semantics and face issues such as accounting for change over time and possible members; our use of set theory here is no different. The stan- dard way to do this is through the use of a four-dimensional, possible world semantics, see Lewis [67], and we assume a similar semantics for our benchmark. Some of the classifi- cation systems we review later in the paper explicitly adopt this semantics. 3.6 Alternative mathematical frameworks Earlier it was noted that there are alternative foundational mathematical frameworks—type theory and category the- ory which contain objects with an analogous structure to set theoretic objects described above. These are very tech- nical subjects, but for completeness, a very brief description is provided in this section along with references. 3.6.1 Type theory Russell [103] introduced the first type theory in 1903. Com- puter scientists have found a later type theory, Martin-Löf [74] type theory, useful. Mathematicians have more recently developed this into homotopy type theory [114]. 123 -- 11 of 37 -- C. Partridge et al. What distinguishes set theory and type theory is that in set theory, objects are assumed to exist independently, whereas in type theory each object is assumed to be dependent upon its type. For example, in set theory, the set {1, 2, 3} is assumed to exist. In type theory, one might say that the set {1, 2, 3} exists and is of type SET. To illustrate the difference, in type theory everything has to have a type, so one has to ask what type the object SET is. One could say it is of type TYPE and, to stop an infinite regress, say the object TYPE is of type TYPE. Barwise and Moss [9] discuss the logical issues this circularity creates. 3.6.2 Category theory Eilenberg and MacLane [29] introduced categories as a formal ground for what they called functors and natural transformations. Since then, they have evolved significantly. Though Grothendieck [45], Freyd [38], and others chose for practical reasons to define categories in set-theoretic terms, subsequently sets have been treated as a kind of category, a special kind of topos. Category theory formalizes mathematical structures into categories that are collections of objects and arrows (also called morphisms) that satisfy some basic conditions. There is a category of sets, where the objects are sets and the arrows are functions from one set to another (though the objects of a category need not be sets nor the arrows functions). Any way of formalizing a mathematical concept such that it meets the basic conditions on the behavior of objects and arrows is a valid category, and all the results of category theory will apply to it. The relationship between categories and sets is quite technical—see Blass [11] for an overview—and is outside the scope of this paper. 4 Formalizing classifications using mathematical set-theoretic objects The formal structures captured by powerset and its related mathematical objects, described in the previous section, are sufficient to characterize the core formal structure of clas- sifications. In particular, it provides tools to examine the formal structure of the classical Linnaean system introduced earlier. This is traditionally considered taxonomical. This is true, but as the following analysis shows, the implicit pattern underlying the Linnaean system is more intricate than a mere taxonomy (i.e., hierarchy just based on subsets). 4.1 The Linnaean taxonomy Figure 1 above presented the explicit Linnaean taxonomy which can be interpreted formally. A natural interpretation for this, as for many taxonomies, is of the classification nodes as sets, as they have members. Natural Things is the set of all natural things, Animals is the set of all animals, and so on. From this, it naturally follows that the relationship between these sets in the taxonomic hierarchy is a subset relation. For example, Animals is a subset of Natural Things; every member-of Animals is also a member-of Natural Things. The subset schema is: x ⊆ y iff ∀z (z ∈ x → z ∈ y). (22) Translating this into the current context: Natural Things ≡ NT (23) Animals ≡ An (24) ∀z (z ∈ An → z ∈ NT) (25) Fig. 8 Taxonomic nodes as sets 123 -- 12 of 37 -- Formalization of the classification pattern This implies that: An ⊆ NT (26) This interpretation is shown in Fig. 8. 4.2 The Linnaean classifications As Natural Things is a set, any arbitrary collection of its members is a subset. Only a select few of these are Linnaean Classifications. For example, arbitrary unions of the classifi- cations, such as the union of Mammalia and Plants, are not. This can be made explicit by reifying the selected sets as members of the set Linnaean Classifications. This is a subset of the powerset of Natural Things, Natural Things Powerset. Natural Things Powerset ≡ NTP ≡ ℘ (NT) (27) Linnaean Classifications ≡ LC ≡ {Animals, Plants, . . . , Primates, . . . , Felis tigris, . . .} (28) LC ⊆ ℘ (NT) (29) It is assumed that the powerset relation has been reified as a powerset-of relation as described above. Then, <Natural Things Powerset, Natural Things> is an instance of the powerset-of relation; formally, ∃x [(x ≡< ℘ (NT), NT >) ∧ (x ∈ PO)] (30) Fig. 9 Linnaean classifications This is modeled in Fig. 9. The dashed line with an open arrowhead represents the member-of (i.e., type-instance) relation while the continuous line with closed arrowhead rep- resents the subset-of relation. Since the powertype instance relation is a type of type-instance relation, a similar notation is used. 4.3 The five Linnaean ranks Figure 1 shows the five Linnaean ranks as levels in the tax- onomy. The question is how to interpret these. A natural interpretation of their formal structure is as a set of the sets in that rank. So, for example, the rank Orders is the set {Primates, Bruta, Ferae, …}, and so Bruta is a member-of Orders, more formally: Orders = Or = {Primates, Bruta, Ferae, . . .} (31) Bruta = Br (32) Br ∈ Or (33) As the subset relation is transitive and given the interpreta- tion above, it follows that every Linnaean classification node is a subset of all the nodes above it in the taxonomic hier- archy. In particular, it is a subset of the root node, Natural Things. The full formal analysis for Felis leo is below. [(Felis leo ⊆ Felis) ∧ (Felis ⊆ Ferae)] → ( Felis leo ⊆ Ferae) (34) [(Felis leo ⊆ Ferae) ∧ (Ferae ⊆ Mammalia)] → (Felis leo ⊆ Mammalia) (35) [(Felis leo ⊆ Mammalia) ∧ (Mammalia ⊆ Animals)] → (Felis leo ⊆ Animals) (36) [(Felis leo ⊆ Animals) ∧ (Animals ⊆ NT)] → (Felis leo ⊆ NT) (37) So the Species Felis leo, its parent Felis, and all the nodes above it are subsets of the root node, Natural Things, as shown in Fig. 10, with the new subset-of relations shaded gray—this transitivity is also shown in Fig. 5. With these subset relations exposed, a natural extension is to see ranks as a set of subsets of the root node, Natural Things. A more formal way of expressing this is that each rank is a subset of the powerset of the root node, Natural Things Powerset; more formally (and shown graphically in Fig. 11), Natural Things Powerset ≡ NTP ≡ ℘ (NT) (38) Orders ≡ Or (39) Or ⊆ ℘ (NT) (40) 123 -- 13 of 37 -- C. Partridge et al. In Fig. 1, there is no explicit Linnaean ranks object. It is implicit, implied by a virtual column on the right-hand side of the figure. It can now be made explicit. It is the set of the individual Linnaean ranks; more formally, Linnaean Ranks ≡ LR ≡ {Kingdoms, Classes, Orders, Genera, Species} (41) Again, the Linnaean Ranks can be tied back to the root, by noting that Linnaean Ranks is a subset of the Natural Things Powerset Powerset; more formally (and shown in Fig. 12 with the reified powerset-of member relation), Fig. 10 Subsets of the root node Natural Things Powerset Powerset ≡ NTPP ≡ ℘ (℘ (NT)) (42) LR ⊆ ℘ (℘ (NT)) (43) Linnaean Ranks is a subset of Natural Things Powerset Powerset and Linnaean Classifications is a subset of Natural Things Powerset. There is a relationship between the two; members of Linnaean Ranks are also subsets of Linnaean Classifications. More formally, Linnaean Ranks = LR (44) Linnaean Classifications ≡ LC (45) ∀y[(y ∈ LR) → (y ⊆ LC)] (46) This can be expressed by using the powerset of Linnaean Classifications as (see Fig. 13 with the reified powerset-of relations); Linnaean Classifications Powerset ≡ LCP ≡ ℘ (LC) (47) (LC ⊆ NTP) → (LCP ⊆ NTPP)] (48) As the example shows, powersets are used as contain- ers for classifications. The Natural Things Powerset contains Linnaean Classifications and the individual ranks. The Lin- naean Classifications Powerset contains Linnaean Ranks. Powerset is a formal object—given the set, one can construct its powerset. There is no extra analytic or explanatory work to do; hence, it is, to use Armstrong’s [4] phrase, “an onto- logical free lunch.” Pragmatically, one can regard it is as a useful organizational device. 4.4 Rank ordering and partitioning A feature of the taxonomic classification is that for each node, its subnodes at the next level partition it. For example, at the first stage, the set Natural Things is partitioned into the sets, Fig. 11 Ranks as subsets of natural things powerset 123 -- 14 of 37 -- Formalization of the classification pattern Fig. 12 Linnaean ranks as an object Fig. 13 Linnaean classifications powerset Fig. 14 Mammalia set partitioned Animals, Plants, etc. At the second stage, each of these sets is further partitioned; for example, the set Animals is par- titioned into the sets Mammalia, Aves, etc. Then, the Class Mammalia is partitioned into Primates, Bruta, Ferae, and so on. Each member-of the set Mammalia belongs to one and only one of the subnodes (subsets)—as shown in Fig. 14. These partitions are not explicitly specified in most clas- sification structures. One option would be to specify each partition individually. This is less than ideal: firstly because there would be a significant number of partitions and sec- ondly, and more importantly, because the underlying general pattern would not be specified explicitly. So the pattern would not scale well, as when new nodes were added, there would be nothing to enforce the general pattern. A more general approach is to recognize that each rank partitions the root node, Natural Things, and that the ranks are ordered by the subset relation. From this, the individual partitions can be inferred. This begins by introducing the set of partitions of Natural Things—Natural Things Partitions. Linnaean Ranks is a sub- 123 -- 15 of 37 -- C. Partridge et al. Fig. 15 Superset-subset member pattern Fig. 16 Rank ordering set of this. The rank ordering is then specified by indicating that a member-of the higher node has subsets that are mem- bers of the lower node. And conversely, that a member-of the lower node is a superset of one, and only one, member-of the higher node. For example, take Kingdoms and Classes. Every member- of Kingdoms is a superset of members of Classes, and vice versa, every member-of Classes is a subset of one and only one member of Kingdoms. Formally, this is described as follows: recognizing the appropriate subset of the subset relation: K ≡ Kingdoms (49) C ≡ Classes (50) ∀x [(x ∈ K] → ∃y [(y ∈ C) ∧ (y ⊆ x)] (51) ∀y [(y ∈ C) → ∃x [(x ∈ K) ∧ (y ⊆ x) ∧∀z [((z ∈ K) ∧ (y ⊆ z)) → (x = z)]] (52) From this, one can identify the class of subsets relat- ing Kingdoms and Classes, the “kingdoms-super-classes- subsets.” kingdoms-super-classes-subsets(a, b) ≡ kscs(a, b) (53) ∀x ∀y [(kscs(x, y)) → ((x ∈ K) & (y ∈ C) & (y ⊆ c)] (54) It is perhaps easy to visualize this in a modeling diagram— see Fig. 15. This pattern extends to all the ranks giving them a linear ordering—as shown in Fig. 16. Note that “kingdom-super- classes-subset” is the set of subset relations between King- doms and Classes. In general, there will be such a set between consecutive linear ranks. This is a good example of the use- fulness of being able to build a hierarchy of subset relations. 4.5 The underlying formal structure The analysis has, hopefully, exposed some of the kinds of formal structures that arise in classification patterns, in par- 123 -- 16 of 37 -- Formalization of the classification pattern ticular the repeated use of powersets. The central structure is a set-subset hierarchy for selected sets. One needs to go up a powerset level to reify these selected sets into a classi- fications set. In the selected example, the classifications are divided into ordered ranks. One needs to go up a second pow- erset level to reify these ranks. The ranks are then ordered using a subset of the subset-of relation. This illustrates the ways in which the classification pattern involves a range of inter-locking formal structures generated by powersets. The example shows how powersets can be used to charac- terize the formal structure of the classification pattern. One side effect of the adoption of set theory as the framework for formalization is that this leads to the introduction of types whose instances are also types—types of types. However, it is the powertypes that generate the classification pattern— types of types, by themselves are inadequate. Later, we will look at approaches that aim to characterize the classification generating pattern without the use of types of types. 5 A survey of powertypes in ISE The evolution of the formalization of classification took place in the communities working on the development of seman- tic or conceptual models. Their focus on how to represent domains is leading to the recognition of a requirement to represent the classification pattern formally. However, there is another interconnecting group of com- munities and avenues of adoption that is of interest here. This is the general adoption of the formal mathematical struc- tures addressed in this paper. Mathematics is an obvious tool for working with formal structures; hence, it is no surprise that communities working with computer systems adopted it. The adoption is of interest here for two reasons. Firstly, the development of conceptual modeling can be better under- stood when it is realized that it emerged from the early stages of a more general adoption of mathematical structures. Sec- ondly, it provides a historical benchmark against which the less clean adoption in the conceptual modeling communities can be measured. Broadly speaking, there is a general order of adoption of the mathematical structures. Basic notions of set and member-of in some form were adopted from the start. Sub- sequently, subset-of is adopted, and finally, powerset is adopted. However, the analysis shows a difference in the pace of adoption in the conceptual modeling and the main mathematics adopting ISE communities. While many math- ematics adopting ISE communities absorbed the full range of objects analyzed earlier, some conceptual modeling com- munities have not yet completely adopted them. In the first section below, the context is provided, describ- ing briefly the history of the adoption of mathematical objects. In the subsequent sections, the focus is on the con- ceptual modeling communities. Initially, a broad outline of the adoption will be given and the main strands of devel- opment identified. Then, the various strands of development will be examined. In the conceptual modeling communities, the literature shows clearly that the adoption of powerset was and is driven by the requirement for a classification pattern. The research shows that the adoption of powerset as part of the classifica- tion pattern is still in the process of maturing, and that the development has been in a number of different strands with differing approaches. Unlike the mathematics adopting communities, the con- ceptual modeling communities have not, in general, focused on providing an account of the formal structure, though there are references to similarities with mathematical objects, such as powerset (indeed, the objects are often called power- types). From what can be determined of the formal structure, there is a partial adoption of the mathematical objects or the development of related alternative formal structures. One of the recurring issues with some of these structures, which is described in later sections, is that they do not have the formal expressiveness of the mathematical framework detailed in this study and so often cannot support the benchmark exam- ple of this paper. 5.1 The mathematics adopting communities One area where the use of mathematics appeared at an early stage was the construction of database models. The first uses were focused on organizing data, rather than reveal- ing semantics. Historically, the goal was to build database models that used data abstractions to hide the implementa- tion details from the database user, see Smith and Smith and Smith [111], Lockemann et al. [68], Cardelli and Wegner [15], and Goldstein and Storey [40]. The database models that emerged in the early 1970s used abstractions grounded in data structures. Their primary focus was on the representation, not the represented, so they identi- fied data objects such as records and their primary and foreign keys. They made use of mathematical objects to characterize the data object’s formal structures. For example, Codd [21, 22] introduced the relational model, which made extensive use of the notion of a set and associated set-theoretic objects, such as tuples, to capture the formal structure. Implicit in this was the use of member-of relations; subset-of relations were only used with the Cartesian product to define relations in general, and there was no evidence of powersets. In a pattern of semantic drift, this can be seen repeated elsewhere, Codd explicitly used the mathematical tuple object to develop an alternative formalization that he called “relationships”—to distinguish it from mathematical relations. Something similar happened in the early days of structured programming, where set theoretic structures were explicitly 123 -- 17 of 37 -- C. Partridge et al. used to characterize the data being processed. For example, Hoare [53] (p. 122) in Sect. 7 titled “THE POWERSET” (p. 122) explicitly says “The powerset of a given set is defined as the set of all subsets of that set.” As the analysis of data structures became more sophisti- cated, powerset was also used by Kuper [65], Elmasri et al. [30], Gyssens and Van Gucht [46], Hull and Su [57], Soldano and Ventos [112]. Some researchers worked with type and category theory rather than set theory; Martin Löf [74] type theory was (and still is) popular, see Maietti and Valentini [70], Valentini [115], Sambin and Valentini, [104]. Cardelli [14] introduced powertypes, and these were developed by Aspinall [5]. Category theoretic approaches (such as John- son et al. [60]) also use powersets. By the end of the twentieth century, there were commu- nities that had adopted the mathematical structures and used all three of the main mathematical foundational theories as a basis. From the perspective of the limited and relatively simple set of mathematical structures needed for the clas- sification benchmark, the adoption of these was stable and mature. 5.2 Historical context Things are less advanced in the conceptual modeling com- munities. By the mid-seventies, there was a recognition that models needed to “capture more of the semantics of an appli- cation,” see Codd [23] (See also Mealy [76], Kent [62], Van Griethuysen [116], and similarly Carnap [16] origi- nally published in 1928). The focus shifted from data toward semantics, from the representation to what was being rep- resented. Early signs were the introduction of Abrial’s [