Defining semantic networks using association-oriented metamodel

3.1 Related work

Semantic networks are the template used by humans for more than centuries. The Tree of Porphyry drawn in the third century AD by the Greek philosopher Porphyry showing taxonomy of concept types is probably one of first written approaches [29]. On the other hand the oldest semantic network is probably a graph called Graph, which provided the philosopher comment to Aristotle Categories. It presents concepts as nodes while the edges were the IS-A relationship, both in the context of a generalization-specialization compound as well as class-instance. In the computer science research the outburst of interests in semantic networks dates in 1960s. An example is the concept of semantic memory presented as Teachable Language Comprehender (TLC) [5, 24]. Quillian’s model was based on assigning a words (terms) to nodes of semantic network which represent concepts. The concepts had their inherent properties (has-a), as well as connectivity to other concepts through links in order to store IS-A compounds. Quillians’ concept has become the standard for the semantic network in the area of knowledge engineering followed by many researchers. They are making changes, defining new symbol notation or text representations. Hendrix’s partitioned semantic network theory [8, 3] seems worth mentioning here. It introduced the distinction between a single concept and the whole system of concepts which constitutes a kind of a separate subnet. It derives from the fact that the network elements can be fused together in a space on an equal level and consequently be treated as independent nodes. Another idea worth mentioning is a variation of a semantic network i.e. inheritance networks proposed by Brachman [1] and further developed by other researchers [9, 30]. These networks are directed acyclic graphs and model generalisation-specialisation relationship with its semantic consequences in the form of inheritance of features. Another idea presented and accepted as one of leading formal definition of semantic networks are Conceptual Graphs by Sowa [28]. They are used to represent formulas in first order logic in the form of directed labelled graphs.

Among many applications of semantic networks one can find visualisation of economical and financial knowledge [6]. The idea of the semantic networks as knowledge representation is not merely a conceptual tool. There are a number of project that are either abandoned or being still developed. One of the most well-known is SNePS [27] by S. Shapiro. It is a hybrid system using knowledge representation based on frames and semantic networks. The use of semantic networks in SNePS system involves the representation of sentences in the form of directed, labelled graph. Helbig [7] developed a MultiNet paradigm based on an expanded concept of the semantic network. This system is based on the terms, allowing to assign them the concept in the form of nodes connected by edges, performing relationships predefined in the system. Its main objectives are the possibility of being a interlingua for natural language processing systems, and thus, a layer of semantic annotation of natural languages. Universal Networking Language is a very well documented and interesting project with rich set of semantic relations [4]. At present an extremely popular is a topic of the Semantic Web [26]. Despite the similarity of names it is a distinct trend in relation to the development of the semantic networks. Semantic Web primarily uses two languages: RDF and OWL. RDF allows you to represent knowledge in the form of SOP triples, which define a common semantic network. It is worth to mention that semantic networks can be used to model structures having more constrains, however easier to compute on them. One of the examples are trees with such implementations as [22].

3.2 Key features of ESNM^SKB

The following assumptions have been made and fulfilled while designing of semantic network model of the ESNM^SKB:

formal universal semantic network semantics,

4.1 Syntax and semantics

The proposed grammar and semantics of the knowledge representation system has a number of very important features, especially for the precision of knowledge expression as well as for possibility to build knowledge processing systems.

The basic structure of the operator-operand: r ( p 1 , p 2 , … , p n )(1) where:

r – operator,

p _k – operand, k ∈ 1 .. n

provides a natural approach to n-ary compound, as a primary element of facts representation. Since each operator may also be used as an operand it allows to create complex networks expressing facts with complex structure. The operator may be set as Activity or State. r = Activity | State(2)

Activity requires intentional action to be taken. This means that the ultimate cause of the activity must be an action taken by the actor. The original reason for taking activity may be independent of the actor.

State is characterized by, uninterrupted for the duration of the particular state, having a property set defined for a given concept. Wherein the values describing the property may be defined as a range.

The operands can perform the following pre-defined roles: Actor, Co-operator, Object, Number, Owner, Attribute, Relationship, Adverbial of Manner, Source, Target, Tool. Both operators and operands perform strictly defined roles in the Semantic Network. Assigning specific concepts (CONCEPT) to certain roles provides semantic networks the ability to express concrete facts.

role = Actor | Co - operator | Object | Number | Owner | Attribute | Relationship | Adverbial of Manner | Source | Target | Tool(3) This conception has been extended by multiplicity assigned to link between operand and operator, which provides the ability to determine the size restrictions (cardinality constraint). Both operators and operands may have modifiers, which clearly define the concept performing a specific role.

Lets consider an exemplary sentence “John owns the car”, where operand “car” can be further redefined by the modifier “big”, which will modify the sentence to “John owns a big car”. Complementing this sentence with appropriate cardinality constraint leads to the sentence “John owns one big car”. Modifiers can also be recursively modified, e.g. in the sentence “John owns one very big car.” Another important element influencing the semantic capacity are Quantifiers. In ESNM^SKB quantifiers cf – certainty factor, tq – time quantifier, sq – space quantifier and q – intensity quantifier are defined.

Figure 1 presents a conceptual representation of the semantic network of ESNM^SKB for the sentence: “John owns one very big car” along with its complementary quantifiers.

OPEN IN VIEWER

Fig. 1

The diagram depicting the Semantic Network representation of sentence “John owns one very big car”.

The strength of semantic networks lays in the fact that it can consist of more than one node. The information contained in a set of nodes can be read in many different ways depending on the starting point of graph linearization algorithm. Figure 2 is a representation of a set of facts. It is a complex structure with a quite detailed semantics. Simplified representation of this network is as follows:

Ford is a car.

OPEN IN VIEWER

Fig.2

The diagram depicting the Semantic Network representation of complex fact.

However, it should be noted that it lacks lots of details. Considering again the part of the network presented on Fig. 2 we can distinguish following facts, which approximate natural language representation is as follows:

Certainly (cf=1) John owns

intensively (iq=0.9) one probably (cf=0.5) car.

At the same time we know that:

A car is probably (cf=0.5) big and probably

(cf=0.5*0.2) very big.

The above example shows that the semantic networks presented by authors has high expressiveness, meaning that lots of facts and information can be presented using little elements.

The proposed solutions significantly extend the classical approach to semantic networks. It should be emphasized that the network stored in ESNM^SKB does not require conversion for permanent storage in the database layer. Is does do not require a text representation, which would be parsed in order to determine its grammatical structure. Facts are represented directly in the Association-Oriented Model, the structure of which is described in the next section.

5.1 AOM overview

AOM is part of the AssoBase project that aims at the formal description and the construction of tools for modelling data with complex semantics. It is a metamodel that allows to construct data models, both in the intentional and extensional aspect. Since this paper is dedicated to modelling the structures of semantic networks, further considerations will focus on the properties related to the intentional aspects, namely their use in the aspect of modelling of association-oriented structures. AOM derives its concepts from object modelling, entity-relationships modelling, and the concept of hypergraph structures, although it is not an implementation of any existing paradigm.

The assumptions underlying AOM include the concepts defined by the acronym I USE:

Implementability – The possibility of creating native, physical data sets without translation to other metamodels, without any simplifications and while maintaining all the properties and mechanisms occurring at the conceptual and logical level,

The main ideas of AOM are:

separation of data and relationships;

The abstract syntax, formal notation, and the description of

Association-Oriented Modeling Language (AML AO DB ) have been thoroughly described and discussed in [11, 20]. One of the main metamodel categories is (Assoc), that is used to define relationships built from roles – (Role). The data storage function is performed by (Coll), which is a container for atomic data containers (Kattr). Both (Assoc) and (Coll) can be subject for generalisation-specialisation relationship using (Inheritance) mechanism [21]. AOM supports modelling of n-ary relationships, arbitrary determination of multiplicity of participation in a association, arbitrary limitation of relationships in which an element can participate, as well as free determination of the lifetime constraints between elements.

5.2 Some AOM design patterns and modelling techniques

This section describes selected design patterns and association-oriented modelling techniques that have found their application in ESNM^SKB structure modeling.

5.2.1 Bicompositional association-collection tandem (BACT)

BACT is a solution that allows to model functionally complex entities. As it was previously mentioned, one of the main assumptions behind AOM creation was functional separation of metamodel categories [20]. This implies that each function is represented in AOM by the means of only one category, i.e. association (Assoc) is a category that is used to define relationships, while collection (Coll) is a container for attributes (Attr) in which data is stored.

Motivation

Due to the functional separation of the categories, there is a need in the AOM to create a structure that will allow to represent those entities for which the clear separation of functionalities is not possible, i.e. they connect other entities as well as to represent data. We will refer to these functionalities as aspects.

The name of this design pattern is not a coincidence. The bicompositional term relates to one of AOM categories, namely Composition, which defines the lifetime constrains of elements connected to a particular (Role). A characteristic feature of AOM is the fact that composition can occur on both sides of the role at the same time. This is the case with the BACT design pattern, to ensure that none of the aspects exist without the other, because they are part of same (conceptual) being. The word tandem suggests a tight cooperation of two elements, that are the main participants of the pattern.

Participants

◊RelationshipAspect – an association that is an aspect of the being that represents the ability of an element to connect to other elements,

□DataAspect – a collection constituting an aspect representing the ability of an element to store data.

Structure The structure of BACT is firmly set. An instance of the design pattern is always built from two aspects connected with one role with multiplicity one-to-one and composition on both sides.

(4)

Consequences

While using the BACT design pattern, particular care should be taken when it is combined with the generalisation-specialisation mechanism. Due to the separability of relationship building from data aspects, inheritance exists independently for collections and associations [21]. Therefore, if BACT is defined at the generalisation level, the substitutability of types should be taken into account, both in terms of the data aspect as well as the relationship aspect. For example, let us consider the following association-oriented data model:

(5) (6) (7) (8) (9)

The expression 5 defines the exemplary instance of BACT. Next, the generalisation-specialisation was defined in which an association fulfilling the aspect of relation in the BACT is set as an generalisation. Subsequent expressions present the structure of associations being specialisations. The all have inherited role Animal : : Animal in which take part all elements of collections being specialisations of BACT’s data aspect.

The exact consequences resulting from the combination of the use of inheritance mechanism and BACT design pattern will be subject of future papers.

5.2.2 Recursive association

Recursive association is an another AOM design pattern that is a specific form of the self-reference. The self-reference pattern is very often used in database modeling in case of hierarchies [2, 13], what is a also a case in object-oriented modeling. It should be noted that despite the similarity to the self-referential structures in other data metamodels, self-referential association has a different grammar, thus its semantics varies from them. In AOM, it is possible to connect two associations with the means of one role, consequently it gives the possibility of direct linking same association with this one role. The conventional approach, i.e. in other methodologies, requires the creation of separate being in the intentional sense, the relationship and two roles that will connect this being through the relationship.

Motivation  The recursive association pattern solves the problem of taxonomy modeling for relationships of the same type. Due to one of AOM features, namely the possibility of multiplicity limiting on the relationship side, it is possible to build both tree or generally graph-based structures. It is also the basic building block in the field of networks, if there is no constraint for its nodes to be of different types.

Participants There is always exactly one participant of this design pattern, namely ◊Element being an association that forms the relation.

Structure An exemplary general structure of the recursive association design pattern is shown below:

(10)

Consequences The structure of the design pattern as following parameters:

multiplicities of the role. With * on both sides an association network representing arbitrary any graph will be created. With the 0 . .1 on the owner side provides the structure representing the tree.

navigability of the role. If the role is non-navigable, association objects being the target of the role have no information in regard to the association they take part in. Consequently, the network traverse towards destination → owner is very inefficient from the computational point of view.

5.2.3 Association inheritance

Inheritance of associations is the AOM mechanism used to implement the generalization-specialization relationship for named relationships. It is a solution directly resulting from the assumption that the metamodel category of Association should be treated as first-class citizen of models being built. This mechanism allows to use the technique of modeling relations by building complex, multilevel and branched taxonomies.

Motivation Its main motivation is to avoid redundancy at the stage of association’s roles definition by abstracting the common roles to higher-order, possibly abstract associations. This, combined with the primary category characteristics of the association, the Liskov substitution principle is in motion [23]. It means that in every place (in the right to perform the role, following the expression in the query language), where the association A _g occurs, the association object ao : A _{s k} may occur, assuming that generalization was defined as follows: R _p  ⟶ A _{s k} , k ∈ ℕ .

Participants

◊RootRelationship is abstract root of a gen-spec relationship hierarchy.

◊ConcreteRelationship₁, . . ., ConcreteRelationship _n are the concrete specialization associations of ◊RootRelationship.

◊OtherRelationship is an association that is referring to the root of association taxonomy by setting its role destination as ◊RootRelationship.

The Association Inheritance design pattern has a general nature due to the number of levels of inheritance hierarchy, the inheritance mode used, as well as the number of nodes at a particular hierarchy level. Its formal structure in the simplest form can be written as follows [10]:

(11) (12) (13) (14) (15)

Consequences The consequence of the application of this design pattern is to minimise the effort in modelling relationships, both during the definition of its structure (roles possessed), as well as for relation positioning, ie. to determine in which other relationships it may participate.

5.3 ESNM^SKB model

As it was stated in the introduction, the main scientific contribution of the authors being an extension of the article [15] is the description of the ESNM^SKB model structure by the means of AOM formalism. The model of the system in AML AO DB is presented in Fig. 3.

OPEN IN VIEWER

Fig.3

Intensional part of ESNM^SKB model in AOM.

The substructures can be distinguished in the model (including template instances) that implement the issues discussed below.

5.3.1 Implementation of operator-operand structure

Inorder to implement the network formally defined as Equation 1 two elements has been defined:

Operator – the occurrence of a specific operator (association),

Operand^∅ – the occurrence of an operand within the operator (abstract association).

Moreover, the operator should store information in regard to its type, i.e. Activity, State. Since i has only informative meaning, it shall be represented symbolically as an ASCII character. Thus, the following structure of the operator in the form of a BACT template instance was defined:

(16)

Similarly, to address the issues related to the determination of parameters specific for each operand, including the multiplicities (cardinalitymax, cardinalitymin, margintype, marginmax, marginmin) as well as its the type, the instance of BACT pattern has been proposed for the implementation of the operand. In order to avoid the previously described issues that arise when BACT is used parallel with inheritance mechanism, only one participant in the pattern was defined as abstract.

(17)

In order to allow determination of different types of operands that differ from each other by a structure, specific specialisations of abstract association were defined ◊Operand^∅.

(18)

The above-described elements are part of the operator-operand structure. The expression itself was modelled using the role +Operand in association ◊Operator with multiples many-to-many, with the consideration that at least one operator must be present within the operator association. The role may be fulfilled by all specialisations of ◊Operand.

(19)

The particular specialisations have the following semantics:

OperandOperator – the type of operand that is implemented by the operator, i.e. in this case the operator is treated as an operand in another structure forming multilevel network.

OperandInstance – operand type that is taken from ◊Instance^∅ and is directly representing a concept defined withing another SKB module – Ontological Core.

OperandNode – operand type that is a node defined for a given semantic network, that allows the use of substitutability.

OperandNet – operand that is representing a partitioned network, i.e. another network that holds multiple operator-operand structures.

5.3.2 Implementation of semantic network

The centre of the semantic network in the ESNM^SKB model is the ◊Net association, which is a group of interrelated operators. The network concept was defined as an instance of the BACT design pattern due to the need to include attributes that allow the description of the network.

(20) (21)

The ESNM^SKB structure allows modular network construction. This means that many subnetworks can be distinguished within one network. This requirement was accomplished using the recursive role of +SubNet in the ◊Net association. At the same time, both ◊Net and ◊Conclusion can be used as the network specialisation for storing networks derived from the applied inference rules.

(22)

Regardless of the above-mentioned mechanism, ESNM^SKB implements the partitioned network mechanism proposed by Hendrix [8]. This was accomplished through one of the Operand^∅ specializations, namely ◊OperandNet. This association has the uninavigable +Net role, through which a specific association object can be combined with any number of networks constituting an operand.

(23) OPEN IN VIEWER

Fig.4

AOM extensional diagram depicting data structure for conceptual example in the Fig. 2.

5.4 Building semantic networks

In this section we will describe the method of defining semantic networks within the ESNM^SKB model defined in AOM metamodel. The process of building a network can be considered in the followingsteps:

Identify semantic network nodes. These should be identified as the one of the ◊Operand^∅ specialisation. Create specialisation association object for each of the network nodes. To implement the example network from the Fig. 1, the following instances have been identified from the SKB ontological core (Fig. 3):

object from collection □INSTANCE associated with object from collection □CLASS with attribute name = “car” (identified in semantic network as association object of ◊OperandInstance),

object from collection □INSTANCE with attribute name = “John”.

For each identified semantic network nodes (operands), create an object in collection □OPERAND. Define reference to the Ontological Core, to predefined concepts defining roles in semantic networks. In the Fig. 4, operands are playing roles designated by the following:

an Object object from the □CONCEPT collection,

an Actor object from the □CONCEPT collection.

For a chosen subset of semantic network nodes (operands), define modification by creating an association object of ◊Modifier. If the modification involves quantification, create describing object of □QUANTIFIER collection defining desired modification. If the modification involves a concept from Ontological Core, associate an object of chosen □CONCEPT subclass by role Concept. If the modification involves existing modifier, associate new association object of association ◊Modifier using role Modifier.

In the Fig. 4 few OperandInstance modifications have been shown:

modification by quantification (by : QUANTIFIER instances), item[–] modification by concept assignment (: FEATURE instances)

modification of modifier with additional : Modifier association object.

Define operator structure by creating ◊Operator association object as well as □OPERATOR object, forming together a BACT instance. For each operand o, add o to ◊Operator association object’s Operand role. In the Fig. 4 the operator BACT instance has been created, which has been associated to the own : □ RELATIONSHIP instance from Ontological Core.

If needed, create ◊Modifier association object for operator. Use the same recipe as for operand. In the Fig. 4 an operator has been modified by the : QUANTIFIER instance.