class, i.e., it may not be instantiated by concrete objects, and of abstract object, i.e., is does not represent a single concrete object but properties common to a set of concrete objects. This paper clarifies the distinction between abstract and concrete clabjects and discusses the role of concrete clabjects for mandatory constraints at multiple levels and for coping with dual inheritance introduced with the combination of generalization and deep instantiation. The reflections in this paper are formalized based on a simplified form of dual deep instantiation but should be relevant to deep characterization in general.
What is represented as instance data in one application may be represented as schema data in another application. For example, in an application for managing a product catalog, product category car is represented by a class Car which is instantiated by objects representing particular car models, such as BMW Z4. In a customer service application, the same car model may be represented by a class which is instantiated by objects representing individual cars, such as PetersZ4.
Potency-based Deep Instantiation [
categoryMgr1-1 = Person producer2-1 = Company owner3-1 = Person soldPrice3-2 = Currency
categoryMgr0-0 = MsBlack soldPrice2-1 = EuropeanCurrency engine2-2 = Engine
BMW Vehicle1 producer0-0 = BMW engine1-1 = BMW Engine y r o tega Car2 C soldPrice2-1= Euro engine2-2 = CarEngine
engine2-2 = MotorcylceEngine
categoryMgr0-0 = MrWhite
BMW Z41 engine1-1 = EngineK5
F700GS1 R1200GS1 engine1-1 = EngineS5 engine1-1 = EngineR12
owner0-0 = Peter
soldPrice0-0 = € 38,200 engine0-0 =Engine123
soldPrice0-0 = €16,430 engine0-0 =Engine212 coowner0-0 = Sarah
Clabjects with common properties may be generalized to a superclabject. In Dual Deep Instantiation, superclabjects are abstract and are not considered as objects in their own right. For example, concrete clabjects Car and Motorcycle are generalized to an abstract superclabject Vehicle which defines properties shared by Car and Motorcycle, e.g., MsBlack is the category manager of the two product categories represented by Car and Motorcycle.
In the remainder of the paper we introduce, in Sect. 2, a simplified form of Dual Deep Instantiation along which we discuss, in Sect. 3, the distinction between abstract and concrete clabjects. In Sect. 4, we define an inheritance mechanism and describe the role of concrete clabjects in dealing with dual inheritance stemming from the combination of generalization and deep instantiation. Sect. 5 introduces support for defining mandatory constraints over concrete clabjects at multiple levels in order to control the stepwise instantiation process. Sect. 6 gives a brief overview of related work and Sect. 7 concludes the paper. t o o R l e d o M .i v d n I t o o R ti n U
value2-1 = Number exchRate1-1 = Number Yen1 exchRate0-0 = 0.03 European
exchRate0-0 = 1.0 Pound1 exchRate0-0 = 1.32 eu € 38,2000 laV value0-0 = 38,200 ...
£ 1320 value0-0 = 132,0 y r o g e t aC CarEngine2
l e d o
.i vnd Engine1230 Engine2350 Engine2120 I
t o o R
v id MsBlack0 Sarah0 MrWhite0 Peter0 n I too Company1 R v i d n I
BMW0
Dual Deep Instantiation (DDI) [
A DDI model contains a set of clabjects (see No. 1 in Table 2). Clabjects are organized in instantiation hierarchies with an arbitrary number of instantiation levels, where in(x, y) expresses that clabject x is an instantiation of clabject y (No. 2); we also say y is the class-clabject of x. Clabjects at the same instantiation level may be organized in specialization hierarchies, where spec(x, y) expresses that clabject x is a direct specialization of clabject y (No. 3); we also refer to y as the superclabject of x.
We use the term clabject in a wide sense. It covers what is traditionally
modeled as individual objects (tokens, instance specifications), classes, simple values,
and primitive datatypes. In DDI, even individuals may refine or extend their own
schema, e.g., property coowner is introduced at individual PetersR1200GS, and
we assume, in this regard, that every individual comes with its own class facet.
So, in DDI everything is a clabject. Note, in the original DDI approach [
Each clabject comes with a clabject potency (No. 4). A potency of a clabject
is given by a natural number (including 0) and indicates the number of
instantiation levels of the clabject, where ptcy (x) = n expresses that x has descendants at
the next n instantiation levels beneath. Note, in our previous work [
In order to simplify discussion and formalization of the approach, we introduce auxiliary terms, predicates and shorthand notations. We say x isa y if x is either a specialization or an instantiation of y (No. 5), we also say y is a parent of x. We say x is a member of y if x relates to y by a chain of isa with exactly one instantiation step (No. 6). We say x is an n-member of y if x relates to y by a chain of isa with n instantiation steps (No. 7). We use .+ and .∗ to denote the transitive and transitive-reflexive closure, respectively, of a binary relation. We say, x is a descendant of y and y is an ancestor of x if isa+(x, y). We say, x is a specialization of y and y is a generalization (or is a superclabject ) of x if spec+(x, y).
When a clabject x instantiates a clabject c then the potency of x is the potency of c decremented by one (No. 8). Clabjects in generalization hierarchies all have the same clabject potency (No. 9). (5) isa(x, y) :⇔ in(x, y) ∨ spec(x, y) (6) member (x, c) :⇔ ∃s∃d : spec∗(x, s) ∧ in(s, d) ∧ spec∗(d, c) (7) nmember (x, c, n) :⇔ (n = 0 ∧ spec∗(x, c)) ∨
∃m∃d : ((n = m + 1) ∧ nmember (x, d, m) ∧ member (d, c)) Well-formedness Criteria and Syntactic Restrictions: (8) in(x, y) → ptcy(x) = ptcy(y) − 1 (9) spec(x, y) → ptcy(x) = ptcy(y) (10) isa+(x, c) → x 6= c (11) in(x, c) ∧ in(x, d) → c = d (12) spec(x, s) ∧ spec(x, z) → s = z (13) spec(x, s) ∧ in(x, c) → ∃y : isa∗(s, y) ∧ isa∗(c, y) (14) spec∗(x, y) ∧ in(x, c) ∧ in(y, d) → spec∗(c, d)
In DDI every clabject hierarchy comes with its own set of instantiation levels which is introduced by the potency of the root clabject (a root clabject is a clabject without parent). For example, root clabject Product with potency 3 introduces a clabject hierarchy with three instantiation levels (not counting the instantiation level of the root clabject). These instantiation levels may be given labels. For example, root clabject Product has three instantiation levels, labelled Category, Model, and Individual. Instead of saying “BMW Z4 is 2-member of Product” one may now say “BMW Z4 is a Product Model”.
We assume acyclic clabject hierarchies (No. 10) with single classification, i.e., every clabject has at most one class-clabject (No. 11), and single generalization, i.e., every clabject has at most one direct superclabject (No. 12).
In the original formalization of DDI [
Two clabjects may be related via property references. A quintuple R(x, i, p, j, y) is an asserted property reference of source clabject x via a property p to target clabject y with source potency i and target potency j (No. 16), we also say there is a pi−j reference from x to y. The source potency and the target potency (17) R(x, i, p, j, y) ∧ R(s, k, p, l, t) → ∃c∃m∃n∃d : R(c, m, p, n, d) ∧
isa∗(x, c) ∧ isa∗(s, c) (18) R(x, i, p, j, y) ∧ R(x, k, p, l, d) → i = k ∧ j = l ∧ y = d (19) R(x, i, p, j, y) → ptcy(x) ≥ i ∧ ptcy(y) ≥ j (20) R(x, i, p, j, y) ∧ R(c, k, p, l, d) ∧ nmember (x, c, n) → n = k − i (21) R(x, i, p, j, y) ∧ R(c, k, p, l, d) ∧ nmember (y, d, n) → n = l − j (22) R(x, i, p, j, y) ∧ R(c, k, p, l, d) ∧ isa+(x, c) → isa∗(y, d) indicate how many instantiation levels below the source clabject and the target clabject, respectively, the property is to be ultimately instantiated. For example, the soldPrice2−3 reference from Product to Currency is ultimately instantiated by the soldPrice0−0 reference from PetersZ4 to 38,200.
Well-formed property references obey the following constraints. Every property is introduced with a single clabject, i.e., if two clabjects have the same property, then they must have a common ancestor which introduced that property (No. 17). For simplicity (and space limitations) we only consider singlevalued properties, that is, there may only be a single property reference per source clabject and property (No. 18). The source and target potency must be lower or equal to the potency of the source and target clabject, respectively (No. 19). When instantiating and refining properties, source and target potencies must be reduced according to the number of instantiation steps between the source clabjects (No. 20) and target clabjects (No. 21), respectively. A clabject c with a reference to clabject d via property p with a target potency higher than 0 or if d is abstract introduces a range referential integrity constraint for all descendants of c: descendants of c may only refer via p to descendants of d (No. 22). This is akin to co-variant refinement and, in terms of the UML, to redefinition of association ends. 3
In this section we clarify the distinction between abstract and concrete clabject. We revisit the abstract superclass rule and adapt it to the setting of multi-level modeling with abstract and concrete clabjects.
Abstract clabjects combine aspects of abstract classes and abstract objects.
Concrete clabjects combine aspects of concrete classes and concrete objects. The
distinction between abstract and concrete class is described as: ‘A class that has
the ability to create instances is referred to as instantiable or concrete, otherwise
it is called abstract.’ [
In the literature it has been proposed that only abstract classes may be specialized:
Abstract Superclass Rule: All superclasses are abstract [
Obeying this rule improves the clarity of object-oriented models, especially
when the extension (set of instances) of classes is of interest. Despite the
tradeoff of additional classes to be modeled and maintained, we feel that obeying
the abstract superclass rule in multi-level modeling is beneficial because of the
increased clarity. That is why in the original DDI approach [
Abstract Superclabject Rule: All superclabjects are abstract in that they have no direct concrete instances (but they may have abstract instances).
This is formalized as: All superclabjects are abstract (No. 25). If an abstract clabject acts as class in an instantiation relationship, then the clabject playing the instance role must be abstract as well (No. 26). Every concrete clabject that is member of some clabject must be member of a concrete clabject (No. 27).
The meaning of the allowed kinds of instantiation relationships depends on the abstractness of the related clabjects. An instantiation relationship between a clabject x in the role of the instance and a clabject c in the role of the class, denoted as in(x, c), can be classified as one of the following: – An immediate concrete instantiation relationship is between a concrete clabject in the instance role and a concrete clabject in the class role. For example, the relationship between BMW Z4 and Car is an immediate concrete instantiation relationship, meaning that BMW Z4 is an instance of Car, or, more exactly, that the object facet of BMW Z4 is an instance of a class-facet of Car. – A shared concrete instantiation relationship is between an abstract clabject x in the instance role and a concrete class c in the class role. For example, the relationship between BMW Motorcycle and Motorcycle is a shared concrete instantiation, meaning that all concrete specializations of BMW Motorcycle, such as F700GS and R1200GS, are instances of Motorcycle. – A shared abstract instantiation relationship is between an abstract clabject x in the instance role and an abstract clabject c in the class role. For example, the relationship between BMW Vehicle and Vehicle is a shared abstract instantiation relationship, meaning that all concrete specializations of BMW Vehicle are instances of a concrete specialization of Vehicle, e.g., BMW Z4 is an instance of Car. 4
In this section we define the mechanism for inheritance of property references along generalization and instantiation relationships. A clabject inherits both from its class-clabject and from its superclabject. We refer to this specific form of multiple inheritance as dual inheritance. Dual inheritance leads to potential conflicts. We propose one way to guarantee that concrete clabjects are conflictfree and, thus, satisfiable. (28) R◦(x, i, p, j, y) :⇔ R(x, i, p, j, y) ∨ (∃s : spec(x, s) ∧ R?(s, i, p, j, y)) ∨ (∃c : in(x, c) ∧ R?(c, i + 1, p, j, y) ∧ i ≥ 0) (29) R?(x, i, p, j, y) :⇔ R◦(x, i, p, j, y) ∧ ¬(∃j0∃y0 : isa+(y0, y) ∧ R◦(x, i, p, j0, y0)) (30) concrete(x) ∧ spec(x, s) ∧ R?(s, i, p, j, y) ∧ in(x, c) ∧ R?(c, i + 1, p, j0, y0) → isa∗(y, y0) ∨ isa∗(y0, y) ∨ (∃j00∃y00 : R(x, i, p, j00, y00))
Inheritance of property references is defined using the following predicates: predicate R (No. 16 in Table 2) holds asserted property references of all clabjects. Auxiliary predicate R◦ (No. 28 in Table 4) holds asserted and inherited property references. Derived predicate R? (No. 29) holds effective property references which are the most-specific property references out of the asserted and inherited property references.
We first look at asserted and inherited property references (No. 28). From its superclabject a clabject inherits all effective property references. From its class-clabject it inherits all effective property references with a source potency of 1 or above. When inheriting property references from the class-clabject, the source potency is decremented by 1. For example, clabject BMW Z4 inherits from its superclabject BMW Vehicle a soldPrice reference to Euro and from its class-clabject Car a soldPrice reference to EuropeanCurrency.
An inherited or asserted property reference of a clabject x at source potency i for property p to target object y is effective if x has no inherited or asserted property reference for property p to a target object which is a descendant of y (No. 29). For example, the reference to Euro is the effective soldPrice reference for clabject BMW Z4 since it is more specific than the reference to EuropeanCurrency.
We now discuss the role of concrete clabjects in resolving or detecting conflicts introduced by dual inheritance along generalization and instantiation relationships. If a concrete clabject inherits from its superclabject and from its class-clabject references for property p to y and y0, respectively, we demand that one of the references is a descendant of the other. If this is not the case the modeler needs to resolve the potential conflict by asserting a reference of property p to some clabject y00 (No. 30) which needs to be, due to the previously introduced constraints, a descendant of both y and y0. If this is not possible, the modeler detects a conflict. This guarantees that concrete clabjects that obey this constraint are satisfiable at the instantiation levels beneath. Conflicts are resolved or detected at concrete objects. For example, BMW Z4 inherits for property engine via specialization from BMW Vehicle and via instantiation from Car references to BMW Engine and CarEngine, respectively. To avoid a potential conflict, BMW Z4 asserts for property engine a reference to EngineK5.
Other approaches to detecting and resolving conflicts are (1) to ignore the problem and accept the possiblity of unsatisfiable properties, (2) to use more sophisticated techniques to decide whether two conflicting property references are satisfiable or not, or (3) to make the above check not only for concrete clabjects but also for abstract clabjects, for example it would make necessary to add a property reference from BMW Motorcycle to a to-be created clabject, e.g., called BMW MotorcycleEngine, that specializes BMW Engine and instantiates MotorcycleEngine and which is a generalization of BMW F700GS and BMW R1200GS. With regard to the effort associated with such an immediate conflict resolution, delaying conflict resolution to concrete clabjects, as introduced above, seems to be a good compromise. 5
By now, it is up to the modeler to decide whether properties are to be instantiated and at which levels they are to be instantiated. In this short section we introduce support for defining mandatory constraints at multiple levels. Mandatory constraints allow to control the stepwise instantiation process by demanding that concrete source clabjects at a given level of the domain of the property need to refer to a concrete clabject at a given level of the range of the property or to a clabject that is a descendant of a concrete clabject at the given level.
In more formal terms, a mandatory constraint total (i, p, j) (No. 31 in Table 5) expresses that property p, which is introduced between clabject c and d with potencies n and m, is mandatory for potencies i and j, with potencies i and j being lower or equal to potencies n and m, respectively (No. 32). This means (31) total ⊆ N × P × N (32) total (i, p, j) → ∃c∃n∃m∃d : R(c, n, p, m, d) ∧ i ≤ n ∧ j ≤ m (33) R(c, n, p, m, d) ∧ total (i, p, j) ∧ j ≤ m ∧ nmember (x, c, n − i) ∧ concrete(x) → ∃j0∃y∃y0 : R?(x, i, p, j0, y0) ∧ isa∗(y0, y) ∧ concrete(y) ∧ nmember (y, d, m − j) that concrete (n − i)-members of c must refer via property p to a clabject that is a (descendant of a) (m − j)-member of d (No. 33).
For example, property engine is introduced at clabject Vehicle by a reference with source potency 2 and target potency 2 to clabject Engine. The multi-level domain of property engine is given by the 0-, 1-, and 2-members of Vehicle and its multi-level range is given by the 0-, 1-, and 2-members of Engine. Mandatory constraint total (2, engine, 2) demands that every concrete 0-member of Vehicle refers to some concrete 0-member of Engine or to a descendant of Engine. 6
DDI is heavily influenced by the classical work on deep instantiation of Atkinson
and Ku¨hne [
From M-Objects and M-Relationships [
The most important related work is that of de Lara et al. [
We have discussed the distinction between abstract and concrete clabjects as one
way of clarifying the meaning of superclabjects in multi-level models. In a
simplified setting (only considering single-valued and uni-directional property
references) we have introduced and relaxed the abstract superclabject rule, showed
how the distinction between abstract and concrete clabjects helps to cope with
dual inheritance, and introduced support for mandatory constraints over
concrete clabjects at multiple levels. We currently work on extending the full DDI
approach (also considering bi-directional and multi-valued relationships) and its
ConceptBase implementation [