Index of /deeptelos

[ICO]NameLast modifiedSizeDescription

[DIR]Parent Directory  -  
[TXT]deeptelos-principle.cbs19-Aug-2016 11:58 1.1K 
[TXT]deeptelos.sml.txt15-Aug-2016 09:11 1.4K 
[TXT]deeptelos-telos.cbs05-Oct-2016 07:26 2.0K 
[TXT]deeptelos-time.cbs18-Aug-2016 09:44 2.1K 
[TXT]deeptelos-products.cbs15-Aug-2016 09:11 2.2K 
[TXT]deeptelos-species.cbs22-Sep-2016 07:14 2.6K 
[TXT]deeptelos-products-entities.cbs22-Aug-2016 09:54 2.8K 
[TXT]deeptelos-products-entities2.cbs15-Aug-2016 12:54 2.9K 
[TXT]deeptelos-GTs.sml.txt15-Aug-2016 09:11 3.0K 
[IMG]deeptelos0b.png19-Aug-2016 11:58 7.1K 
[IMG]deeptelos0a.png19-Aug-2016 11:58 8.0K 
[   ]deeptelos0b.gel19-Aug-2016 11:58 9.5K 
[   ]deeptelos0a.gel19-Aug-2016 11:58 9.7K 
[   ]deeptelos0.gel19-Aug-2016 11:58 10K 
[IMG]deeptelos3a.png22-Sep-2016 07:14 11K 
[IMG]deeptelos6a.png23-Sep-2016 11:12 11K 
[   ]deeptelos1.gel16-Aug-2016 13:08 11K 
[   ]deeptelos6a.gel23-Sep-2016 11:12 11K 
[   ]deeptelos6.gel23-Sep-2016 11:00 12K 
[   ]deeptelos7a.gel09-Jan-2017 10:52 12K 
[   ]deeptelos3a.gel22-Sep-2016 07:14 12K 
[   ]deeptelos7.gel04-Oct-2016 07:32 12K 
[   ]deeptelos2.gel22-Aug-2016 09:54 12K 
[   ]deeptelos5.gel18-Aug-2016 09:54 12K 
[   ]deeptelos3.gel22-Sep-2016 07:14 13K 
[   ]deeptelos4.gel16-Sep-2016 11:12 13K 
[IMG]deeptelos6.png23-Sep-2016 11:00 13K 
[IMG]deeptelos0.png19-Aug-2016 11:58 13K 
[IMG]deeptelos7a.png09-Jan-2017 10:52 22K 
[IMG]deeptelos1.png16-Aug-2016 13:08 22K 
[IMG]deeptelos7.png04-Oct-2016 07:32 22K 
[IMG]deeptelos3.png22-Sep-2016 07:14 24K 
[IMG]deeptelos2.png22-Aug-2016 09:54 25K 
[IMG]deeptelos4.png16-Sep-2016 11:12 44K 
[IMG]deeptelos5.png18-Aug-2016 09:54 49K 
[   ]jeusfeld-neumayr-deeptelos-final.pdf16-Nov-2016 10:56 1.0M 

BACK

Download Φ Forum Φ Team Φ Home



DeepTelos: Implementation and Examples

This directory contains the implementation and examples for the paper

Manfred A. Jeusfeld, Bernd Neumayr:
DeepTelos: Multi-level Modeling with Most General Instances.
In Proc. 35th International Conference on Conceptual Modeling (ER 2016), Gifu, Japan,
Springer, LNCS 9974, 2016, pp. 198-211 (slides@ER'2016 by Bernd).
The source models (*.sml.txt,*.cbs) in this directory and their derivates (*.gel,*.png) are provided under a CC BY-NC 4.0 license: Attribution-NonCommercial 4.0 Unported. You need ConceptBase 7.8 released July 2016 or later to test the implementation. Download it from http://conceptbase.cc.

You can configure your ConceptBase installation to directly start the example graph files (*.gel). The graph files contain all necessary Telos definitions including the DeepTelos axioms and the dedicated graphical types. You only need to configure your web browser to open the CBGraph utility when you click a graph file. The procedure is simple:



DeepTelos definition

DeepTelos is an extension of Telos by three additional axioms that define multi-level modeling. A new construct "most general instance" (predicate "IN") allows to define multiple hierarchies of levels into which instances are classified. This allows to define properties and relations at various abstraction levels.

The DeepTelos axioms interact with the Telos axioms that are pre-defined in ConceptBase. The predicates A(x,m,y) and In(x,c) used for the Telos axiom specification are at a lower stratum in the Datalog semantics for Telos that the user-defined predicates notations (x m y) and (x in c) used for defining DeepTelos. User-defined predicates do not occur in the pre-defined Telos axioms. Hence, the semantics of instantiation, specialization, and attribution as defined by the Telos axioms remains unchanged and virtually unaffected by DeepTelos. In contrast, DeepTelos is affected by the Telos axioms since the predicates for instantiation (In(x,c)), specialization (Isa(c,d)), and attribution (A(x,m,y)) form the basis for the user-definable predicates (x in c) and (x m y). Note that the DeepTelos predicates (x IN c) and (c ISA d) are formally attribution predicates.

The semantics of most general instances

Example 0 Example 0a Example 0b The generic example defines the most general instance M of a class C. The class C has two instances c1 and c2. These instances have themselves instances x1, x2, x3 and y1, y2, y3, respectively. This information is explicitely defined. This is shown in the first screendump deeptelos0a.png. The second screendump deeptelos0.png shows in addition the information derived by the DeepTelos axioms. The first DeepTelos axiom 'mrule1' is:
  forall m,x,c/Proposition (x in c) and (m IN c) ==> (x ISA m)
In our example, it derives the facts (c1 ISA M) and (c2 ISA M). The second DeepTelos axiom 'mrule2' is:
  forall x,c,d/Proposition (c ISA d) and (x in c)  ==> (x in d)
This is the classical class membership inheritance for specializations. This rule then populates the class M with all instances of its subclasses c1 and c2, i.e. x1, x2, x3, y1, y2, and y3. Thus, M is populated with all instances of all instances of C. This instantiation to M allows to define attributes/relations at M that are applicable to all its (derived) instances. The class M is essentially a proxy of class C at one abstraction level lower. While C has instances like c and d, the class M has the instances of c and d as instances. It is called the "most general instance" of C because it is the superclass of all instances of C. In the example, the class M defines a relation 'a' to class d. Since x1 is a derived instance of M, it can instantiate this relation.

Example 1: product hierarchies

Example 1 The first example features a simple product hierachy Product-ProductModel-ProductCategory. A sibling hierarchy CarModel-Car is defined as specialization of ProductModel. Car and Product are simple classes (OMG M1 level). CarModel and Car are meta classes (M2) and ProductCategory is a metameta class (M3). The DeepTelos axioms make sure that all cars are instances of Car and all products are instances of Product. Likewise, all car models will be instances of CarModel and all product models (incl. all car models) are instances of ProductModel. The object CarModel is declared as instance of ProductCategory. The first axiom of DeepTelos then makes it automatically a subclass of ProductModel since ProductModel is the most general instance of ProductCategory, i.e. (ProductModel IN ProductCategory). CarModel defines among others an attribute 'numberofDoors', which may be instantiated by all instances of CarModel. Porsche911 is such an instance and this can instantiate this attribute. The object Car is defined as most general instance of CarModel. Hence, the first axiom of DeepTelos derived that Porsche911 is a subclass of Car, i.e. (Porsche911 ISA Car). Since Porsche911 is an instance of CarModel, and CarModel is a specialization of ProductModel, we can derive that Porsche911 is also an instance of ProductModel, and as a consequence of the first DeepTelos axiom, Porsche911 becomes a subclass of Product, thus all instances of Porsche911 including marysCar are instances of Product. We define a relation owner for Product and now can instantiate it for marysCar.

Example 2: product hierarchies and entities

Example 2 This example puts the (ontological) product hierarchy next to the (lingustic) Entity-EntityType hierarchy. So, products also are entities. The class Porsche911 is defined as instance of both CarModel and EntityType. As a consequence, the object 'marysCar' is an instance of both Car and Entity.

Example 3: the animal kingdom

Example 3 Example 3a Animal species are organized in taxonomies for mammals, birds, fishes etc. In this example, we use superscripts to express the hierarchy levels. Hence, Animal1 stands for all physical animals. It is the most general instance of Animal2, which stands for animal species such as 'Dog' and 'Chicken'. Finally, Animal3 is the class of animal categories such as mammals, birds etc. Those categories get their taxonomies as well to classify for example all physical mammals (e.g., 'pluto' being a dog and thus a mammal).

Example 4: variant of example 2

Example 4 In example 2, the class Porsche911 was defined as instance of EntityType. In this variant, we define ProductModel as specialization of EntityType. This will ensure that any instance of ProductModel (incl. Porsche911) also is an instance of EntityType. The specialization link between ProductModel and EntityType will instantiate all instances of ProductModel also to EntityType, in particular the class Porsche911.

Example 5: the time hierarchy

Example 5 Roll-up hierarchies are known from multi-dimensional data model. The classifical example is time, e.g. the calendar of days rolled up to the parallel sub-hierarchies of calendar weeks and calendar months. The essence of such a calendar is that days of a certain week can belong to different calendar months. So, the drill-down of a year can be down to weeks of this year (e.g. 'W2016' stands for all weeks of the year 2016), or to months of the year (e.g. 'M2016' stands for all months of the year 2016). DeepTelos automatically populates the most general instances DAY (= all days over all years), WEEK (= all weeks over all years), and MONTH (=all months over all years). The object 'D2016' is defined as most general instance of both 'W2016' and 'M2016'. This will populate 'D2016' with all days of the year 2016.

Example 6: most general instances of properties

Example 6 Telos regards attributes and relationships as first-class objects. This allows to apply the construct of most-general instances to them as well. For example, the meta-class EntityType defines an attribute 'property' to the meta-class Domain. Entity is the most general instance of EntityType and Value is the most general instance of Domain. Then, the attribute 'value' of Entity is defined as most general instance of the 'property' attribute of EntityType. Example 6 Consider as example the 'budget' attribute of the entity type 'Project'. It is an instance of the 'property' attribute of EntityType. Since the 'value' attribute is its most general instance, all attributes like 'budget' become a specialization of the 'value' attribute. The example project 'p346' has such a filler for the 'budget' property. Thus, it also becomes an instance of the 'value' attribute of Entity. The consequence is that we can now realize schema-less querying. For example, we can list all entities that have a real number as value. Like 'value' is the most general instance of 'property', one can also define most general instances for the 'key' property of EntityType. This will allow to formulate queries like for listing all entities that include foreign keys of other entities.

Example 7: Abstraction hierarchies in Telos

Example 7a Example 7 Telos was one of the first data models that fully supported objects at all abstractions levels: proper objects (M0), simple classes (M1), metaclasses (M2), metametaclases (M3), and beyond. The construct of most general instances can be used to define the semantics of these levels by just three statements: (M0Object IN M1Object), (M1Object IN M1Object), (M2Object IN M3Object). The axioms for DeepTelos then populate the classes by their semantics: M0Object shall have all regular objects as instances, M1Object has all simple as instances, and M1Object has all metaclasses as instances. The example is related to the notation used by the UML Infrastructure, which strongly separates abstraction levels. ConceptBase does not enforce such a separation. As the example show, few definitions are sufficient to formalize these abstraction levels. Additional constraints may be defined to forbid any relation between objects of different abstraction levels. Only Node is declared as an explicit instance of M3Object. The other level objects M2Object, M1Object, and M0Object get their instances assigned via the axioms of DeepTelos und the class membership inheritance axiom
mrule2: $ forall x,c,d/Proposition (c ISA d) and (x in c) ==> (x in d) $

The diagram also shows the cascading effect of the DeepTelos axioms: the class Node is an instance of M3Object. Since M2Object is a most general instance of M3Object, the class Node become a subclass ("ISA") of M2Object. EntityType and Domain are instance of Node. Hence, the are also instances of M2Object. Now, since M1Object is a most general instance of M2Object, both EntityType and Domain become subclasses ("ISA") of M1Object. Next, Employee is declared an instance of EntityType, thus also an instance of M1Object. Since M0Object is a most general instance of M2Object, Employee (and analogously Integer) becomes a subclass ("ISA) of M0Object. Finally, any instance of Employee and Integer become instances of M0Object via inheritance.

The three facts (M2Object IN M3Object), (M1Object IN M2Object), (M0Object IN M1Object) are all that is needed to populate the these level objects. Instances of M3Object will lead to specializations of the most general instance M2Object and thus instantiate all M2-level objects to M2Object. This instantiation then will populate M1Object, which finally ensures that M0Object is populated by all M0-level objects.

The number of derived specializations (x ISA m) is exactly the number of instances of the class c in (m IN c). This number typically increases exponentially by descending the level objects M3Object, ..., M0Object.

Implementation report

DeepTelos is implemented by just adding its three axioms deeptelos.sml.txt to the ConceptBase database that is supposed to use DeepTelos. ConceptBase already provides a couple of optimizations to instantiation (x in c). The DeepTelos affect for the instantiation predicate and thus benefits substantially from the optimizations. The most significant optimization is the partial evaluation used by the formula compiler of ConceptBase. It transforms a formula that has a predicate occurrance (x in c) with a variable c as class argument into an equivalent set of formulas, where c is replaced by the possible values that the class argument can assume. Instantiation predicates with a constant value in the class argument are much faster to evaluate due to the data structures used in the ConceptBase object store.

Consider for example deeptelos-principle.cbs in the section "The semantics of most general instances". The class C has two instances: (c1 in C) and (c2 in C). Further, it has the most general instance M: (M IN C). The first axiom of DeepTelos then derives two specializations: (c1 ISA M) and (c2 ISA M).

The second axiom of DeepTelos realizes the classical class membership inheritance for (c ISA d):

mrule2: $ forall x,c,d/Proposition (c ISA d) and (x in c)  ==> (x in d) $
This formula is subject to partial evaluation since both c and d are variables. ConceptBase uses the predicate (c ISA d) in the formula to compute all possible value combination for the two variables, in this case (c1 ISA M) and (c2 ISA M). The compilation then yields two partially evaluated formulas where the predicate (c ISA d) vanished by binding the variables to the constants in the facts (c1 ISA M) and (c2 ISA M). The resulting simplified formulas are added to the definition of M:
M in Class with  
  IN
    class : C
  rule
    mrule2_generated : $ forall x/c1 (x in M) $;
    mrule21_generated : $ forall x/c2 (x in M) $
end 
The generated rules are structurally very simple: they copy the instances of the class c1 and c2 to the class M (=most general instance of C). As a result, ConceptBase can very quickly compute the instances of class M. The benefit of the partial evaluation further increases with hierarchies of most general instances. Note that the clause x/c1 is a shortcut for (x in c1).

Another beneficial implementation feature of ConceptBase is the "tabling" used by ConceptBase to store the extension of derived predicates, such as (x in c). The extension is only computed once and only when needed, and then stored in an indexed data structure. If a class C with a most general instance M has many instances, then many rules like mrule2_generated are created. This could be in the thousands, if the class C has thousands of instances. This can lead to a huge extension of a class like M, which also is time-consuming to compute. The "tabling" feature of ConceptBase will however store the extension and speed-up subsequent accesses.

The class membership axiom mrule2 is formulated for the DeepTelos predicate (c ISA d) This predicate mimics the semantics of the original Telos predicate (c isA d), which is defined by a very similar axiom. For historical reasons, the Telos axioms in ConceptBase are hard-coded and not subject to partial evaluation. Still, it would have been preferable to use (c isA d) instead of (c ISA d). The technical reason that prevented its use is a restriction on the use of (c isA d) in rules: it may not occur as conclusion predicate. This restriction made good sense at the time when the Telos axioms were implemented in ConceptBase. It allowed to precompute the set of instances of superclasses in the object store. This optimization became virtually obsolete when tabling was introduced to implement recursive deductive rules. However, the technical restriction remains intact and forced us to define a second specialization predicate (c ISA d).

The original Telos axioms are hard-coded. They were meant to form the second stratum of predicates In(x,c), Isa(c,d), AL(x,m,n,y), and A(x,m,y). The first stratum is formed by the P-facts P(o,x,n,y). Certain axioms of Telos, in particular the attribute typing axiom, do in principle not "see" instantiation facts derived by user-defined rules such as mrule2. That would mean that DeepTelos databases would systematically violate the attribute typing axiom, whenever it is used to define attribute at most-general instances. The formal strata of Telos axioms have however been abandoned since several years in ConceptBase. In particular, the attribute typing axiom now also "sees" instances derived by user-defined rules.


Manfred Jeusfeld, 2017-01-23