This paper contains the consideration of knowledge extraction mechanisms of such object-oriented knowledge representation models as frames, object-oriented programming and object-oriented dynamic networks. In addition, conception of universal exploiters within object-oriented dynamic networks is also discussed. The main result of the paper is introduction of new exploitersbased knowledge extraction approach, which provides generation of a finite set of new classes of objects, based on the basic set of classes. The methods for calculation of quantity of new classes, which can be obtained using proposed approach, and of quantity of types, which each of them describes, are proposed. Proof that basic set of classes, extended according to proposed approach, together with union exploiter create upper semilattice is given. The approach always allows generating of finitely defined set of new classes of objects for any objectoriented dynamic network. A quantity of these classes can be precisely calculated before the generation. It allows saving of only basic set of classes in the knowledge base.
Nowadays methods of knowledge extracting and reasoning about knowledge are significant constituent part of majority of knowledge-based systems. It gives an opportunity to extract or to obtain new knowledge, based on such called, basic knowledge. Such abilities make knowledge-based systems intelligent and applicable ones at least in such areas of artificial intelligence as information search, problem solving, planning, patterns recognition, decision making, etc.
Currently there is variety of knowledge representation models (KRMs), which implement different approaches to knowledge representation. One of them is an objectoriented knowledge representation, the main idea of which is representation of knowledge in terms of objects, classes of objects and relationships among them. Nowadays the most famous KRMs within this approach are frames and object-oriented programming (OOP). Both of them have their own knowledge extraction methods, which give some abilities for new knowledge obtaining. Let us consider these mechanisms and their main features in more detail.
Frames as a KRM provide representation of knowledge in terms of hierarchies of frames
(system of frames), where particular frame is a class-frame or instance-frame [
In addition, each frame can have definite procedural attachments, which allow
execution of actions on it. Some procedures execute only when they are in need
(whenprocedures), other ones execute in particular situations. Thus, extracting of new
knowledge in the frame system can be done by dint of the reasoning in inheritance hierarchy
or by means of procedural attachments executing [
In contrast to frames, OOP is divided on two styles – class-based and prototype
based ones [
Class-based approach provides ability to work only with instantiated objects, to
change values of their properties, to execute their methods and in such a way to obtain
new knowledge. We cannot change the description of a class, type of object or hierarchy
of classes during program execution. It means that we can obtain only objects of the
same type with changed values of the properties. In addition, inheritance in OOP causes
the same problems as in frames [
Prototype-based style gives an opportunity to operate with prototypes. Each new prototype is a modified clone of another one. It means that such approach is more flexible for description of new concepts, because it allows creating of new prototypes during program execution and implements the idea of partial inheritance. However, it requires much more computer memory and leads to redundancy in representation of particular prototypes. 3
Besides mentioned object-oriented KRMs, there is one more KRM, such as
objectoriented dynamic networks (OODNs), that was proposed in [
OODN = (O, C, R, E, M ), where: • O – a set of objects; • C – a set of classes of objects, which describe objects from the set O; • R – a set of relations, which are defined on the set O and C; • E – a set of exploiters, which are defined on the set O and C; • M – a set of modifiers, which are defined on the set O and C.
Definitions of all elements from the tuple OODN = (O, C, R, E, M ) were introduced
and considered in detail in [
p(T ) = (v(p(T )), u(p(T ))),
where v(p(T )) is an quantitative value of p(T ) and u(p(T )) are units of its measure.
Definition 3 Qualitative property of class of objects T is a verification function p(T ) =
vf (T ), which is defined as a mapping vf (T ) : p(T ) → [
Let us define the conception of equivalence of these kinds of properties. Definition 4 Two quantitative properties p(T1) and p(T2) of arbitrary classes of objects T1 and T2 are equivalent, i.e. Eq(p(T1), p(T2)) = 1, if and only if (u(p(T1)) = u(p(T2))) ∧ (v(p(T1)) = v(p(T2))).
Definition 5 Two qualitative properties p1(T1) and p2(T2) of arbitrary classes of objects T1 and T2 are equivalent, i.e. Eq(p1(T1), p2(T2)) = 1, if and only if (vf1(T1) = vf2(T1)) ∧ (vf1(T2) = vf2(T2)).
For every object of a class we can define methods, which can be applied to them and allow definition of their behaviour and manipulating on them.
Definition 6 Method of class of objects T is a function f (T ), which can be applied to the class T , considering the features of its specification (vector of properties). From the previous definition, we can see that method is a function, which is defined under the properties. To define the equivalence of methods we should define the equivalence of two arbitrary functions, but in general case such problem is unsolvable one. So, we are going to introduce the equivalence of methods via following definition. Definition 7 Two methods f1(T1) and f2(T2) of arbitrary classes of objects T1 and T2 are equivalent, i.e. Eq(f1(T1), f2(T2)) = 1, if and only if (f1(T1) = f1(T2)) ∧ (f2(T1) = f2(T2)). It introduces the equivalence of two methods on the same argument. It means that two methods f1(T1) and f2(T2) can be different as functions, however they can return the same results on the same objects.
Concepts of objects, classes and relations among them have different
implementations in various KRMs. One of the main differences is the definition of the class. Within
frames and OOP, concept of class is defined as abstract description of some quantity
of objects, which have the same nature [
According to this definition, all objects of such class have the same type, i.e. they have the same properties and methods as their class. Let us consider the definition of inhomogeneous class of objects.
Definition 9 Inhomogeneous (heterogeneous) class of objects T is a tuple
T = (Core(T ), pr1(A1), . . . , prn(An)), where Core(T ) = (P (T ), F (T )) is the core of class of objects T , which includes only properties and methods similar to corresponding properties of specifications P (A1), . . . , P (An) and corresponding methods of signatures F (A1), . . . , F (An) respectively, and where pri(Ai) = (P (Ai), F (Ai)) , i = 1, n are projections of objects A1, . . . , An, which consist of properties and methods typical only for these objects. According to this definition, it is possible to represent certain amount of any types by dint of one class within object-oriented approach. While representation of each type of objects in OOP always requires definition of new class.
Analyzing definitions 8 and 9, we can conclude that a homogeneous class of objects defines a type of objects. In this case the type and the class of objects mean the same. However, an inhomogeneous class of objects defines at least two different types of objects within one class of objects that is why in this case the type and the class are not equivalent. In other words inhomogeneous class of objects includes a few types of objects. Let us define a type of inhomogeneous class of objects.
T = (Core(T ), pr1(T ), . . . , prn(T )) is a homogeneous class of objects Ti = (Core(T ), pri(T )), where i = 1, n.
Now, let us define the following tree kinds of subclass relations for classes of objects: homogeneous ⊆ homogeneous, inhomogeneous ⊆ inhomogeneous and homogeneous ⊆ inhomogeneous. Definition 11 Homogeneous class of objects T1 = (P (T1), F (T1)) is a subclass of homogeneous class of objects T2 = (P (T2), F (T2)), i.e. T1 ⊆ T2 if and only if (∀pi ∈ P1 ∃pj ∈ P2 | Eq(pi, pj ) = 1) ∧ (∀fk ∈ F1 ∃fw ∈ F2 | Eq(fk, fw) = 1), where P1, P2, F1, F2 are sets, which contain elements of vectors P (T1), P (T2), F (T1), F (T2) respectively and i = 1, |P1|, j = 1, |P2|, k = 1, |F1|, w = 1, |F2|.
T1 = (Core(T1), pr1(T1), . . . , prn(T1))
T2 = (Core(T2), pr1(T2), . . . , prm(T2)), i.e. T1 ⊆ T2 if and only if
(∀ai ∈ C1 ∃aj ∈ C2 | Eq(ai, aj ) = 1)∧ ∧(∀bhk ∈ prh ∃!bvw , prv ∧ bvw ∈ prv | Eq(bhk , bvw ) = 1), where C1, C2, prh, prv are sets, which contain elements of vectors from the sets Core(T1), Core(T2), prh(T1), prv(T2) respectively and i = 1, |C1|, j = 1, |C2|, k = 1, |prh|, w = 1, |prv|, h = 1, n, v = 1, m.
Definition 13 Homogeneous class of objects T1 = (P (T1), F (T1)) is a subclass of inhomogeneous class of objects T2 = (Core(T2), pr1(T2), . . . , prn(T2)), i.e. T1 ⊆ T2 if and only if (∀pi ∈ P1 ∃pj ∈ C2 ∨ prv | Eq(pi, pj ) = 1)∧ ∧(∀fk ∈ F1 ∃fw ∈ C2 ∨ prv | Eq(fk, fw) = 1), where P1, F1 are sets, which contain elements of vectors P (T1), F (T1) and C2, prv are sets, which contain elements of vectors from the sets Core(T2) and prv(T2) respectively, i = 1, |P1|, j = 1, |C2| + |prv|, k = 1, |F1|, w = 1, |C2| + |prv|, v = 1, n.
According to the definitions of class of objects, it is possible to define the vector of methods for each class of objects, concerning its specification. Such kind of methods are internal ones, because they are defined under particular properties of the class. Besides them, there are methods, which are called external ones and are defined under whole specification of the class. Depending on the character of actions, all methods can be divided on exploiters and modifiers. Exploiters do not change objects or classes, they just use them as parameters for new knowledge obtaining. While, modifiers change the basic knowledge and allow modelling of their changes or evolution over the time. That is why F (T ) contains internal, E and M contain external methods of the class of objects.
Summarizing, OODN can be considered as two conceptual parts. First of them is declarative, which includes sets O, C, R, and allows representation of knowledge about particular domain. Second part is procedural one. It includes sets E, M and provides the tools for obtaining new knowledge from basic ones. All following considerations are connected with applications of procedural part of OODN, in particular exploiters-based knowledge extraction.
As it was mentioned above, exploiters form significant constituent of procedural part of
OODN. Generally, we can define variety of exploiters for each class of objects,
however majority of them are locally closed under their classes. That is why, such universal
exploiters as union, intersection, difference and symmetrical difference were introduced
in [
Let us define union exploiter for classes of objects, using definition 10. Definition 14 Union ∪ of two arbitrary nonequivalent classes of objects T1 and T2 is an inhomogeneous class of objects T = (Core(T ), pr1(T ), . . . , prn(T )), where Core(T ) = (P (T ), F (T )) is its core and includes only properties and methods, which are similar for types T11 , . . . , T1m , T21 , . . . , T2k , and where prj (T ) = (P (T ), F (T )) is projection of type Tij , i = 1, 2, j = 1, n, n = m + k which consist of properties and methods typical only for this type.
Application of union exploiter to classes of objects has some important features besides generation of new classes of objects. Let us formulate and prove a few theorems, which illustrate these features.
Theorem 1 For any OODN = (O, C = {T1, . . . , Tn}, R, E = {∪}, M ), where classes T1, . . . , Tn are homogeneous ones and do not have any common properties and methods, all possible applications of union exploiter ∪, including all possible its superpositions, to classes of objects from the set C always generate finite quantity of new classes of objects, which can be calculated by the following formula: q(CE ) = 2n − n − 1, where n = |C|.
Proof. It is known that the number of all possible unique k-elements combinations from the n-elements set can be calculated as Cnk. Similarly, the number of all possible unique classes of objects created from the basic set of classes C = {T1, . . . , Tn} using union exploiter can be represented as a combination of k = 2, n different classes from the set C. It is known that k X Cnk = 2n.
n=0 However, we cannot create classes of objects, which describe 1 and 0 different types, applying union exploiter to the classes of objects from the set C, i.e. we do not count Cn0 and Cn1, we can conclude that q(CE ) =
C = {T1, . . . , Tn, Tn+1, . . . , T2n−1} of any OODN, extended according to Theorem 1, with exploiter ∪ create the upper semilattice, where class T1,...,n = T1 ∪ · · · ∪ Tn is its greatest upper bound.
Using results of Theorem 2, we can formulate the following corollary. Corollary 21 Set of classes of objects C of any OODN, extended according to Theorem 1, and union exploiter ∪, which is defined under it, create a finitely-generated universal algebra
G = (C = {T1, . . . , Tn, Tn+1, . . . , T2n−1}, Ω = {∪}) , where Cb = {T1, . . . , Tn} is generative set for the set C.
Now let us consider an example, which illustrates specific of exploiters-based knowledge extraction within OODN. Let us define the OODN
Salad = (O, C, R, E, M ), which describes some ingredients of a salad, for example cucumber, tomato, onion, cabbage, salt and sunflower oil. For this purpose, we define following sets of objects O, classes of objects C and set of relations R
O = {cuc, tom, on, cab, sal, soil},
C = {Cuc, T om, Cab, On, Spi, Oil}, R = {cuc −a−n−−−in−s−t.−−−o→f Cuc, tom −a−n−−−in−s−t.−−−o→f T om, cab −a−n−−−in−s−t.−−−o→f Cab, on −a−n−−−in−s−t.−−−o→f On, sal −a−n−−−in−s−t.−−−o→f Spi, soil −a−n−−−in−s−t.−−−o→f Oil.}. Suppose the set of exploiters is defined as E = {∪}. We do not define the set of modifiers M , because it is not necessary within consideration of exploiters-based knowledge extraction.
Let us define the specifications of classes from set C in the following way P (Cuc) = (p1(Cuc), . . . , p4(Cuc)), P (T om) = (p1(T om), . . . , p4(T om)), P (Cab) = (p1(Cab), . . . , p4(Cab)), P (On) = (p1(On), . . . , p4(On)), P (Spi) = (p1(Spi), . . . , p4(Spi)), P (Oil) = (p1(Oil), . . . , p4(Oil)), where p1(Cuc), p1(T om), p1(Cab), p1(On) – masses of vegetables, p1(Spi) – type of spices, p1(Oil) – type of oil, p2(Cuc), p2(T om), p2(Cab), p2(On) – colors of vegetables, p2(Spi) – mass of spices, p2(Oil) – volume of oil, p3(Cuc), p3(T om), p3(Cab), p3(On) – freshness of vegetables, p3(Spi) – taste of spices, p3(Oil) – color of oil, p4(Cuc), p4(T om), p4(Cab), p4(On), p4(Spi), p4(Oil) – prices. Values of all properties of these classes are defined in Table 1.
Let us define the specifications of objects from the set O, using specifications of their classes (see Table 2). p1 [0.07, 0.18] kg [0.08, 0.2] kg [0.4, 1.3] kg [0.05, 0.1] kg undefined undefined p2 green red green green-white [0.1, 1.0] kg [0.5, 1.0] l p3 undefined undefined undefined undefined undefined yellow p4 3 USD/kg 3.5 USD/kg 4 USD/kg 2 USD/kg 12 USD/kg 9 USD/l p1 0.09 kg 0.08 kg 0.12 kg 0.1 kg 0.5 kg 0.1 kg salt sunflower p2 green green red red green green-white 0.5 kg 0.5 l p3 1 1 1 1 1 1 salty yellow p4 0.27 USD 0.24 USD 0.42 USD 0.35 USD 2 USD 0.2 USD 6 USD 4.5 USD
We have described the OODN for the salad. Clearly that all elements of sets O, C and R are basic knowledge. Let us obtain all possible new knowledge from them using exploiter ∪. According to Theorems 1-2 we obtain such 15 classes, that each of them describes 2 different types of objects such 20 classes, that each of them describes 3 different types of objects such 15 classes, that each of them describes 4 different types of objects CucT omCabOn, CucT omCabSpi, CucT omCabOil, CucT omOnSpi, CucT omOnOil, CucT omSpiOil, CucCabOnSpi, CucCabOnOil, CucCabSpiOil, CucOnSpiOil, T omCabOnSpi, T omCabOnOil,
T omCabSpiOil, T omOnSpiOil, CabOnSpiOil; such 6 classes, that each of them describes 5 different types of objects CucT omCabOnSpi, CucT omCabOnOil, CucT omCabSpiOil,
CucT omOnSpiOil, CucCabOnSpiOil, T omCabOnSpiOil; and 1 class, which describes 6 different types of objects
CucT omCabOnSpiOil.
As we can see, we obtain 57 new classes of objects, or in other words, 57 different combinations of salad’s ingredients from the 6 basic ones. In such a way we extended the set of classes C by adding new knowledge, extracted from basic ones. The most general obtained class CucT omCabOnSpiOil is an inhomogeneous one and has following structure
CucT omCabOnSpiOil = (pr1(CucT omCabOnSpiOil), . . . ,
pr6(CucT omCabOnSpiOil)), where pr1(CucT omCabOnSpiOil) = P (Cuc), pr2(CucT omCabOnSpiOil) = P (T om), pr3(CucT omCabOnSpiOil) = P (Cab), pr4(CucT omCabOnSpiOil) = P (On), pr5(CucT omCabOnSpiOil) = P (Spi), pr6(CucT omCabOnSpiOil) = P (Oil).
According to Theorem 2, the extended set of classes C and exploiter ∪ create upper semilattice. It means, that there is partial order relation ⊆, which is defined on the set C. Furthermore, according to Corollary 21 they create a finitely-generated universal algebra G = (C = {Cuc, T om, Cab, On, Spi, Oil, . . . , CucT omCabOnSpiOil}, E = {∪}), where Cb = {Cuc, T om, Cab, On, Spi, Oil} ⊆ C is generative or basic set for the set C.
Summarizing, we obtained all possible unions of the basic classes from the set C. All these classes can be viewed as schemas or recipes for which we can use objects defined in Table 2. In means that in such a way we can create particular salad, moreover we can create different salads using one scheme putting different proportions of ingredients. Using chosen scheme, we can calculate different properties of the cooked salad, for example its prise, mass, etc. 5
This paper contains consideration of main features of knowledge extraction mechanisms of such object-oriented KRMs as frames, OOP and OODNs. Furthermore, conception of universal exploiters within object-oriented dynamic networks is also discussed.
The main achievement of the paper is introduction of new exploiters-based knowledge extraction method for OODNs, which always provides generating of finitely defined set of new classes of objects, based on the basic set of classes. The main features of the proposed method are: • ability to calculate: • quantity of new classes, which can be obtained, using proposed approach, • quantity of different types, which each of obtained classes describes; • the basic set of classes of any OODN, extended according to proposed approach, together with union exploiter, create: • upper semilattice, • finitely generated universal algebra, for which the basic set of classes of OODN is a generative set.
It allows us to extract new knowledge from the basic ones when we need them and to save only basic set of classes in the knowledge base and database. Moreover, obtained knowledge always have the defined structure, i.e. they form the upper semilattice. It means that we can use the results of upper semilattice theory in such kind of knowledge extraction and representation.
However, despite all advantages, proposed approach requires further research, at least in the following directions: • study of the case when the basic set of classes of OODN contains classes that has some common properties or methods, • study of the case when the OODN is a fuzzy one, • adapting and usage of proposed approach in other known object-oriented KRMs.