Can We Benefit from Metrics in KBS Development?

1 Introduction

The maintenance of knowledge-based systems (KBS) is one of the major issues in their practical use. According to the experience with conventional software develop­ ment, many maintenance problems stem from bad de­ signs and implementations. So , improving these is an effective approach to address the maintenance problem.

Both in "traditional" and in object-oriented (0-0) software engineering , metrics are used (among other things) to determine current and to predict future qual­ ities of a product relative to expected standards. In par­ ticular, it is possible to pinpoint those parts of a product with potential defects. In this way, it is easier to improve the quality of the product and therefore to improve its maintainability.

In order to address the maintenance problem of KBS, we devised the first metrics suite for KBS development. 1

1 The research reported has been carried out in the ViVa (Verification, Improvement and Validation of Knowledge­ Based Systems) project, partially funded by the ESPRIT Programme of the Commission of the European Communities

Stefan Schlee Softlab A us tria Moeringgasse 20 A- 1150 Vienna, Austria sts@softlab.co.at

In this paper, we present three metrics of this suite deal­ ing with frames and rules and their relationship in a knowledge base. These metrics represent quantitative models of the fundamental concepts coupling and cohe­ sion, as well as the impact of modifications.

We have applied these metrics to a real-world KBS based on frames and rules. The numerical values com­ puted there helped locating those frames and rules which would most likely pose problems during the maintenance of the KBS . So, the application of our metrics helped pinpointing maintenance problems.

This paper is organized as follows. First, we present some of the metrics that we devised for frames and rules. Then we show some empirical evidence with these met­ rics from real-world experience and from using a pub­ lished knowledge base. After that, we shortly discuss previous work on the use of metrics. Finally, we discuss our approach and the use of metrics in KBS development more generally.

2 Metrics for Frames and Rules

We propose to use metrics for knowledge bases consisting of frames and rules in order to pinpoint potential prob­ lems with maintenance. Another possible use of metrics reported in the literature is the evaluation and compar­ ison of alternatives. In both cases, metrics are useful as a means to make certain properties related to quality objective and quantifiable.

In the metrics literature there is a general distinction between process metrics (measuring certain aspects of the development process), and product metrics (mea­ suring aspects of items produced during software de­ velopment). In this paper we focus on product met­ rics related to knowledge bases consisting of frames and rules. In case of procedural attachment in the form of method slots, it would have been possible to sim­ ply transfer well-known metrics from the object-oriented paradigm. (For a comprehensive discussion of 0-0 metrics, see [Henderson-Sellers, 1996].) However, for knowl­ edge bases consisting of frames and rules that are not at­ tached to frames, a new set of metrics had to be derived. 2

as project number 6125. The overall goal of the ViVa project is to provide a methodology and a supporting tool-set for V & V of knowledge-based systems in industry. More details can be found at http:/ /www.cri.dk/ViVa- the ViVa Web­ where also our metrics suite can be tried out .

2.1 Procedure for the Derivation and Validation of Metrics

For the derivation and validation of the metrics, we adopted a procedure that is agreed upon in the soft­ ware engineering literature (e.g. see [Hitz and Montaz­ eri , 1996]). This procedure consists of three steps:

1. Identify the attributes of interest. In this context, attributes are properties of the item in question. For the attributes of interest, quantitative models are to be defined.
2. Derive the metrics for these attributes. The deriva­ t ion starts with an intuitive account of the so-called empirical relation system, i.e., a kind of qualitative model of the attribute of interest. Then formalize the relations established in the empirical relation system.
3. Validate the metrics by determining the scale type, by careful application of some of Weyuker's axioms [Weyuker, 1988] and by checking the effects of so­ called atomic modifications [Zuse, 1990].

We followed this procedure, and our description par­ allels its steps.

2.2 Identification of the Attributes of Interest

Regarding the selection of attributes of interest , we de­ cided to focus on the concepts of coupling and cohe­ sion, which are generally accepted to be relevant both in object-oriented and "traditional" software engineering. Coupling and cohesion can be explained in terms of el­ ements (like modules, classes or frames) that are linked in some way (for instance by function calls , common us­ age of global variables, or message connections) . The degree of connect ivity within such an element is called cohesion, and the degree of connectivity among these el­ ements is called coupling. In general, low coupling and high cohesion are indicators of good modularization and minimal interfaces, and thus contribute to maintainable software. In our context, the elements are frames, and they are linked by those rules where they are referenced together. Regarding cohesion, we are interested in the degree to which the slots belong together. This is differ­ ent from the object-oriented version of cohesion, where the cohesion of methods is usually determined by their use of instance variables.

Besides coupling and cohesion, we are interested in measuring the impact that a change of a frame may have on the rule base. This additional attribute sup­ plements coupling and cohesion, and is also related to main tenance.

2 For a discussion of t he concepts underlying object­ oriented sys tems, frame systems and description logics see Appendix A.

Figure 1: Frames and rules of a hypothetical mini-KBS.

2.3 Derivation of the Metrics

The derivation will be illustrated by a running example, a hypothetical mini-KBS as shown in Fig. 1. It consists of four rules. The rules refer to frames (A, B, C', D) and their slots (A.v, A.w, ... ).

First we want to derive a quantitative model for cou­ pling. We focus on a single frame, and the degree of coupling between this frame and the other frames . The degree of coupling of a frame can be thought of as the "connectivity" with respect to other frames. The larger the number of other frames that are linked to a frame, the higher the coupling of the frame. As stated above, frames are linked by rules, but more precisely they are linked if and only if there is at least one rule where both frames are referred to. So, the degree of coupling of a frame may simply be defined as the number of other frames that are referred to in the same rules as the frame under consideration .

To formalize this notion of coupling of a frame, we define two auxiliary functions. Let R be the set of rules in the knowledge base, and F be the set of frames in the taxonomy. Then we define Rules as

This function determines all rules that refer to a par­ ticular frame. For our running example, Rules(A) = {1·1 , r2 , 1'3}. Dually, we define Frames as

This function simply returns the set offrames referred to by a given rule. For instance, Frames( 1·1 ) = {A, B, C'}. Now we can define the metric for coupling, DC'pF (Degree of Coupling of Frame) as:

In our running example, DC'pF(A) 2, si nce U· E{ . }Frames(r;) ={A, B, C'}. 1, r1 ,1 2,r3

Another attribute of interest related to maintenance is the impact that a modification of some frame has on the rule base. 3 In case of such a modification, the affected rules have to be checked if they are still valid. Given that we have to check those rules where the particular frame is referred to , the impact on the rule base may simply be measured by the number of rules using the frame. So we define the metric I M F (Impact of Modification oj Frame) as follows:

So, for our running example, I M F(A) = 3.

Next , we want to derive a quantitative model for cohe­ sion. Our goal is to define a function measuring the de­ gree to which the slots of a frame belong together (with respect to the rules). Intuitively, two slots belong to­ gether if they are connected by the rules, i.e. if they are used in the same rules. In other words, there is a connec­ tion between two slots if and only if they are both used by at least one rule. It is convenient to think of this in terms of graphs: for each frame we define a graph, where the nodes represent the slots, and an arc exists if the corresponding slots are both used in at least one of the rules. An obvious way to define the lack of cohe­ sion is to count the number of "disconnected sub graphs", in graph-theoretical terminology the number of compo­ nents. We define the metric for cohesion, LChF (Lack of Cohesion of Frame) as follows:

LChF(f) = Number of components of graph G, where the nodes of G represent the slots of f , and an arc exists in G if the correspon­ ding slots are both used in at least one of the rules.

ln our example, there are two components of the corre­ sponding graph of frame A, one containing { w, x , y }, and one containing { v, z} (see Fig. 2). Thus , LChF(A) = 2.

2.4 Validation of the Metrics

The soundness of these met rics can be checked by deter­ mining the sca le type, by applying those of Weyuker's axioms that make sense in our context, and by checking the effects of atomic modifications. These "acid tests" are based on measurement theory and are established in the theory of metrics in the software engineering litera­ ture.

The scale type of all three metrics is absolute, since they are all counting some entities. This means that a full range of descriptive statistics is applicable, for in­ stance, means and standard deviations may be calcu­ lated.

Weyuker 's axioms state desirable properties of soft­ ware complexity measures . For various reasons (ex­ plained in [Henderson-Sellers, 1996; Chidamber and Ke­ merer , 1994]) only a subset of Weyuker's axioms makes sense in our context . These properties can be para­ phrased as follows:

3 This attribute is different from coupling, since it relates elements of different sorts (frames and rules), while coupling just relates elements of the same sort (namely frames).

• Property 1: not all possible frames have the same values for the metric.
• Property 3: for every frame there might exist an­ other frame of the same complexity.
• Property 4: design decisions should be reflected in the values calculated by the metrics.
• Property 5: complexity should increase when adding something.

Properties 1, 3 and 4 are trivially satisfied. For property 5, we define the concatenation of frames as the merging of the slots into a new frame. The proof for property 5 is simple, but we cannot include it in this paper due to lack of space. In brief, all of these properties are satisfied by the metrics.

Finally, we check the effects of atomic modifications [Zuse, 1990]. Atomic modifications are the smallest pos­ sible changes in the model underlying the calculation of the metric. If the changes in the values of a metric caused by these modifications do not translate back to acceptable statements within the empirical relation sys­ tem, the metric has to be rejected. In our context , the atomic modifications are additions or deletions of rules or frames. Since our metrics are all basically counting some entities, there is a direct correspondence between the modifications and the values of the metrics. Due to the straightforward derivation of the metrics , the increase in the metrics directly translates back to correct qualitative statements about the KBS. For instance, adding a rule that refers to a frame A increases I M F by 1, and the statement in the empirical relation system is that the impact of changing A increases as well .

We briefly sketched three ways of validating the met­ rics for frames and rules. Summing up, our metrics turned out to be valid according to all three "acid tests".

3 Empirical Results

In this section we present the results obtained for two knowledge bases. First, we present some findings from a real-world proj ect, where the knowledge base is im­ plemented in Kappa [IntelliCorp, 1993], a hybrid frame system with traditional frames and rules. In the second application, we put the generality of the approach to the test , and calculated values for a knowled~e base repre­ sented in CLASSIC [Brachman et al., 1991J, a knowledge representation system based on description logi c.

3.1 Results for a "Traditional" Frame System

In the following, we describe the app lication of the met­ rics to a real-world KBS implemented using a "tradition­ al" frame system. Our role was to control the quality of the KBS in question. So we were not involved in the development of the KBS , but in quality assurance. Ta­ ble 1 summarizes the data obtained by the metrics. To improve the comprehensibility of the results, we also in­ clude percentages.

Applying the metric for coupling (DCpF) shows that the frame Diagnosers couples all frames (5 frames , 100%). In addition , the value for IM F indicates that a change in this frame affects the whole rule base (66 rules, 100%). The second finding is that the frame Amf Models couples 4 out of 5 frames (80%), and that 60% of the rules (40 rules) would be affected by some change of this frame . These findings hinted at the pos­ sibility that both frames Amf Models and Diagnosers might have been pragmatically created for implementa­ tion considerations rather than designed as semantically meaningful units. So we asked the development team, and they confirmed our assumptions. In effect, the met­ ri cs helped us uncover a flaw that might have led to serious maintenance problems.

Checking the cohesion of the frames, we did not find indi cations for problems using the corresponding metric, since LChF = 1 for all frames. However, the appli­ cations of our other metrics helped pinpointing serious problems with maintenance. Our experience also sug­ gests that metrics are useful as a means to determine cPrtain properties of KBS in an objective and effective way, and that they help to focus the attention on poten­ ti al problems.

3.2 Results for a CLASSIC Knowledge Base

We applied our metrics to the "winery" knowledge base that is distributed as a demo of the CLASSIC knowl­ edge representation system. In order to apply our met­ ri cs to CLASSIC knowledge bases, it is first necessary to conclude which concept is the right-hand side concept of a rule. In Table 2, we summarize a few results for the "winery" knowledge base. We included values for its most fundamental concepts , wine and meal-course, and for a subconcept of meal-course: fruit-course . In addition , we performed a thought experiment , and cal­ culated values for a slightly modified knowledge base: in CLASSIC, the antecedent of a rule has to refer to a de­ fined concept. So if the antecedent of the rule is not yet defined as a concept , we have to define it to formulate the rule. We were interested in the values for the met­ rics if we could simply substitute the definitions of these "antecedent" concepts , and refer to them directly in the rules.

The results for the original winery knowledge base show that for the concept wine the degree of coupling ( DCpF) is high (23 frames, 17%), and that the impact of modifications (IM F) is very high (148 rules, 100%). This is due to the fact that many rules (91 rules, 61 %) are used to define contingent properties of wines (properties that do not belong to the concept itself) , and that the rest of the rules (57 rules, 39%) make statements about the relationship between specific meal courses and sorts of wine. Note that the concept meal-course itself is never referred to in the rules (0 rules, 0%) , but only specific meal courses like fruit-course.

Looking at the modified knowledge base, we find that the degree of coupling of the concept wine ( DCpF) is low (1 concept, namely meal-course), but the value for IM F is sti ll very high ( 148 rules, 100%). Moreover , meal­ course itself is referred to in the rules, but it couples only the concept wine (so DCpF = 1). Although coupling is low, the impact of modifications of this concept (I M F) is high (57 rules, 39%).

For the original knowledge base (without substitution of the antecedent definition) , the cohesion of wine and meal- course is low (the lack of cohesion LChF is high). The reason for this is that all the rules use only one attribute/role of these concepts. Interestingly, this is not the case if we substitute the antecedent definitions. The metric reflects that the substitution yields rules where attributes/roles of the same concept are used together.

Although the metrics have not been devised for de­ scription logics, they helped us make a few interesting observations.

4 Related Work

Coupling and cohesion are well-known and established concepts from traditional software engineering. Al­ though the definition of the concepts of coupling and co­ hesion is clear and established in software engineering, there are various versions of metrics defined for these concepts (e.g. , in [Heyliger , 1994]).

Chidamber and Kemerer [1994] were the first to define a metrics suite for object-oriented design and program­ ming. Their metrics suite includes measures for coupiing and cohesion. Coupling among objects is defined in terms of incoming and outgoing messages (method invo­ cations) of an object. We defined coupling in analogy to this formulation in the object-oriented framework, where the rules take the role of the methods. Additionally, we defined a metric measuring the impact of modifications of a frame (I M F) , that is specific for knowledge bases consisting of frames and rules.

Since Chidamber and Kemerer's metric for cohe­ sion suffers several measurement-theoretic anomalies, we took a different approach. We adopted both the view of cohesion as proposed in [Li and Henry, 1993] and the graph-theoretic approach by [Hitz and Montazeri, 1996] . In a graph-theoretic view of Li and Henry's definition, the nodes represent the methods of a class, and they are connected if there is at least one instance variable that is used by both methods corresponding to the nodes. While in this view the measure for cohesion by Li and Henry also counts the number of components of a graph, in our approach the graph is defined in a dual way, i.e., the nodes represent slots, and the arcs are defined by "common" rules.

Besides coupling and cohesion, there are various met­ rics in the object-oriented literature measuring proper­ ties of taxonomies. (Some of them, like DIT, the depth of inheritance tree, are problematic from a measurement­ theoretic view.) We also developed a few metrics for taxonomies, but in this paper we focus on coupling and cohesion.

In conventional and object-oriented software engineer­ ing there is a rapidly increasing number of publications about metrics. To the best of our knowledge, however, metrics have not yet been described in the published lit­ erature about KBS development.

5 Discussion

Now let us discuss our approach more generally. The question may arise, for instance, what such numbers sig­ nify. In some sense, this question relates to the utility of metrics in general. While this issue is surely beyond the scope of this paper, we claim to have developed our met­ rics suite according to the state of the art. In addition, we have validated them both according to acknowledged theoretical standards and through practical experience.

It must be understood that these like any other com­ parable metrics are just special quantitative models of "quality". So, it is very important for successful applica­ tions to beware of misunderstandings and misuse. Still, wherever some of these numbers indicate problems, it is worth a closer look.

More specifically, the concepts of coupling and cohe­ sion and therefore also the corresponding metrics are re­ lated to the principle of minimal interfaces. While this principle is generally agreed to in the context of software engineering, it is not normally dealt with in frame sys­ tems and rule bases. A major effect of adhering to this principle is that we can achieve greater ease of mainte­ nance. Since this should be a goal for the development based on frames and rules as well, and since also our third metric pursues this goal, we think that the metrics proposed in this paper should be useful for improving the development of KBS based on frames and rules.

Let us shortly point to an interesting difference of our approach compared to the corresponding approach for 0-0 software development (for the general correspon­ dence between objects and frames see the Appendix A). While we measure how rules use the slots of frames, the usual 0-0 approach measures how the methods within an object use the instance variables of the same object. So, our approach measures more global dependencies be­ tween frames and rules that are outside of these frames. Normally, global dependencies are more critical for main­ tenance than local ones. So, we conjecture· that our ap­ proach may be even more helpful in the context of KBS based on frames and rules than the approach for 0-0 software development.

Finally, our metrics approach relates to verification and validation of KBS consisting of rules and frames. In contrast to mainstream work in this area dealing with static KBS properties, we focus on the relation between rules and frames.

6 Conclusion

In this paper, we presented three metrics from our met­ rics suite for KBS development. They represent the core of this suite and measure the fundamental concepts of coupling and cohesion, as well as the impact of modifi­ cations. In essence, these metrics help pinpointing prob­ lems for the maintenance of knowledge bases consisting of frames and rules.

To the best of our knowledge, this is the first pub­ lished account of a metrics suite for KBS development. Some of our metrics have been developed in analogy to existing metrics in software engineeri_ng, but we also de­ veloped completely new metrics: the metric measuring the impact of modifications of a frame has no analogue, and our measure for cohesion is dual to the one proposed by [Li and Henry, 1993].

The results from applying these metrics to a real-world KBS ("traditional" frames and rules) as well as to a demo for CLASSIC (description logic and rules) suggest the usefulness of these metrics. So, we think that this approach has the potential to improve the development of a KBS in the sense of enabling quantitative and ob­ jective judgements of quality properties relevant for the developer. Therefore, we propose to use our and other yet to be developed metrics in order to improve KBS development.

Acknowledgments

We would like to thank Martin Hitz for useful discus­ sions and comments on an earlier draft of this paper. Leslie Benjamin helped to improve the English. The im­ plementation of our metrics in the ViVa Web is due to Gert Schmeltz Pedersen.