Retrieving Cases from Relational Data-Bases: Another Stride Towards Corporate-Wide Case-Base Systems

1 Introduction

This paper describes the architecture and performance evaluation of a case-based reasoning system built on a commercial relational data-base management sys­ tem (RDBMS). Specifically, the authors have developed CARET (~e &lrieval Iool), a tool which generates appropriate SQL [ANSI, 1989] expressions to carry out similarity-based retrieval on a commercially available RDBMS, such as ORACLE [Oracle, 1989] . The core of the algorithm is a novel approach to similarity comput­ ing which pre-computes query form similarities, rather than the similarities of individual cases.

The motivation behind this research was two-fold. First, the use of a RDBMS, or a mechanism with equiv­ alent functions, was found to be the minimum require­ ment for CBR systems to be installed as part of a corporate-wide information system. This requirement was pointed out by engineers and managers in corporate data processing divisions and other administrative divi­ sions. Important reasons include the need for security control and integrity management.

Second, significantly large data-bases in various do­ mains presenly available in many corporate information systems are built on commercial RDBMSs. Applications using CBR would allow exploring new horizons in cor­ porate information systems, since current RDBMSs only provide relatively primitive (i.e. only exact match) query capability. Efforts to convert these dat~bases into in­ dependent CBR systems, however, will inevitably un­ dermine security control and waste computing resources (memory and CPU). In addition, since two separate data-bases would be created in such a conversion, the in­ tegrity of the case-base would not be maintained because the mechanism for automatically reflecting changes in the RDB to case-base would, for both technical and se­ curity reasons, not be installed

The underlying belief behind these observations is the mainstream dogma, which claims that a CBR system should be integrated into a mainstream corporate-wide strategic information system. This idea was first advo­ cated in [Kitano et a/., 1992; Kitano et a/., 1993] and has been the central core of the CBR-related research activ­ ities at NEC Corporation. Development of a CBR ar­ chitecture using RDBMS would be a major step forward toward achieving the goals of the mainstream dogma.

Unfortunately, however, no existing CBR system uses RDBMS as its case-base manager . Even commercial tools, such as CBR Express on ART-1M, ReMind, and ESTEEM, do not incorporate RDBMS. Of course, not all CBR systems require tight security control and integrity management . Nevertheless, the advantages inherent in building CBR systems using RDBMS are remarkable. The authors argue that this is one of the most signifi­ cant unexplored avenues in CBR research and describe the architecture and evaluation results of their proposed CBR system for RDBMS .

2 Problems in Current Case-Base Management

The case-base management concept is critically lacking in the current research on CBR systems. This is mainly due to the fact that a vast majority, if not all, of CBR systems have been built as task-specific domain problem solvers. These systems, similar to most expert systems, are detached from mainstream information systems for a corporation. However, as has been clearly demonstrated in the wide-spread use of data-base management systems (DBMS), data resource management is an essential issue the corporate information systems.

To be more specific, the following issues have not been addressed in previous studies on CBR systems.

Security Control: In real applications, collected cases include secret information for a corporation or a de­ partment. No CBR systems developed so far in­ corporated any security measures. In the absence of the security control, the system can not be used for highly confidential information where maximum value can be exploited.

Scalability The efficiency of a CBR application heavily depends on the number of cases collected. In some real applications, collected cases can increase dras­ tically chronologically. For example, in the SQUAD system, a corporate-wide CBR system for soft­ ware quality control domain [Kitano et al., 1992], over 3,000 cases have been added into its case­ base each year . Since real domains are often very complicated and ill-formed, use of complex index­ ing, as seen in [Hammond, 1986; Hunter, 1988; Ashley and Rissland, 1987; Kolodner, 1984], would require significant development costs and the system behavior would be unstable, as the experts them­ selves do not fully understand the nature of such domains. It would be beyond control of system en­ gineers.

Speed Although various indexing and case-base organi­ zation methods have been investigated, only a few studies addressed the issue of computing cost . Fast case retrieval is an indispensable feature of real­ world applications, particularly for very large case­ bases.

3 CARET Design Decisions

This section describes major design decision made in de­ veloping CARET (CAse REtrieval Tool).

3.1 Case-Base Management using RDBMS

The most significant design decision was the use of a commercial RDBMS for its case-base manager. Each case is represented as a record of a relational database table. The use of a RDBMS offers several advantages, such as (1) data security, (2) data independence, (3) data standardization, and ( 4) data integrity. The use of RDBMS, however, automatically forces CARET to generate SQL specifications [Codd, 1970; Chamberlin et al., 1976] to carry out any case-base retrievals. SQL is the standard relational database access language. How­ ever, SQL does not entail any similarity-based retrieval features. The essence of this work, therefore, is to find a method to carry out similarity-based retrievals using SQL.

The other constraint, imposed from the use of RDBMS, is that cases have to be represented as a flat record of n-ary relations. RDBMS do not entail a mech­ anism to support a complex indexing scheme, as seen in most CBR researches. However, this constraint is not necessarily a limiting factor for case representations. Through the SQUAD development, the authors learned that complex indexing schemes are too difficult to main­ tain, particularly for ordinary system engineers.

3.2 Similarity Definition using Abstraction Hierarchy

Similarity between values is defined using an abstraction hierarchy, shown in Figure 1. It is defined for each at­ tribute in a flat table, such as language, machine, and OS. In this example, the similarity between C and C++ is 0. 7. Similarity between the input query and each case in the case-base is calculated by referring to the similarity of values in each attribute.

3.3 Case Retrieval using Nearest Neighbor

CARET uses nearest neighbor retrieval, instead of indexing-based methods. Typically, a similarity between a query (Q) and a case (C) in the case-base (S(Q, C)) is the weighted sum of similarities for individual attributes:

where Wi is the i-th attribute weight, s(Qi, q) is sim­ ilarity between the i-th attribute value for a query (Q) and that for a case (C) in the RDB.

Traditional implementations would compute the sim­ ilarity value for all records, and sort records based on their similarity. However, this is a time consuming task, as computing time increases linearly with regard to the number of records in the case-base ( C : Cardinality of the data-base) and to the number of defined attributes (D : Degree of the data-base). This results in time-complexity of O(C x D). This implementation strategy for RDBMS would be a foolish decision, as individual records have to be retrieved to compute similarity. Thus, the total transaction number would be intolerable.

The challenge here is to discover an algorithm to im­ plement the nearest neighbor algorithm using SQL suf­ ficiently efficient to be practical. The following sections describe such an algorithm and report on its performance using the deployed system.

4 Generating SQL specifications with Similarity Measures

4.1 Creating Neighbor Value Sets

For each attribute, CARET refers to the abstraction hi­ erarchies, as shown in Figure 1, to generate a set of values neighboring the value specified by the user. For example, assume that the user specified BSD4. 2 in the hierarchy shown in Figure 2, BSD4. 2 is an element in the first­ order neighbor value set {lst-NVS) . BSD4. 3 is an element in the second-order neighbor value set {2nd-NVS) . SVR2 and SVR4 are elements in the third-order neighbor value set {3rd-NVS ). Such sets are created for each attribute.

Assume that the user specified VAX for an attribute machine and ADA for an attribute language in the hier­ archies in Figure 1, Table 1 shows the generated NVS sets.

4.2 Enumerating the Combinations

Next, all possible neighbor value combinations are cre­ ated from the n-th order neighbor value sets. Figure 3 illustrates how such combinations are created. This ex­ ample assumes that the user specified values for attribute language and machine. All value combinations under attribute language and machine will be created. Weight of attributes (0.3 for language and 0.4 for machine) and similarity measure (such as 1.0, 0.2, 0.8 assigned to each value set) are used to calculate the similarity between a combination and the problem definition specified by the user. Using the neighbor value sets from the previous example, combinations shown in Table 2 are created.

and(language(ADA), machine(VAX))

and(language(ADA), machine(or(SUN, NEWS, ... ))) and(language(ADA), machine(or(MIPS, EWS4800, .. )))

and(language(or(C, C++, COBOL, COBOL/S)), machine(VAX))

and(language(or(C, C++, COBOL, COBOL/S)),

machine(or(SUN, NEWS, ... )))

and(language(or(C, C++, COBOL, COBOL/S)),

machine(or(MIPS, EWS4800 , .. )))

Table 2: Combinations created

Disjunction is created for values under the same node. Under this assumption, the maximum number of combi­ nations (N) produced in a given query will be:

where r is a number of attributes specified by the user, and d; is the depth of the tree of the attribute i. Aug­ menting this formula to a more general case which does not involve disjunction, would lead to the following equa­ tion:

where F;d; is an average fanout of the tree for attribute l .

4.3 Assigning Similarity Value

For each combination, a similarity value is calculated using similarity between values of attributes specified by the user and values of combinations created in the pre­ vious stage. The calculation is similar to the weighted nearest neighbor, except that not all attributes are in­ volved . The CARET algorithm does not compute any attributes not specified by the user. The rationale for this approach is described in [Kitano et al., 1992]. Whether the user specified the attribute or not is shown in a mask matrix (M), which is a one-dimension matrix whose size is equivalent to the case-base degree. The matrix element M; will be 1, if the user specified the value for the attribute i. Otherwise, M; will be 0. The formula for calculating the similarity is as follows:

where F is an NVS combination and Fi is the i-th at­ tribute for the combination. It should be noted that sim­ ilarity is calculated between the user specified attributes and combinations of NVSs which is the seed for SQL specifications. In essence, the similarity is computed be­ tween a user's specification and SQL specifications. This is counter to traditional methods, which compare a user's query specification with each case instance. For exam­ ple, the similarity of a combination, ([C, C++, COBOL, COBOL/S], [SUN, NEWS, ... ]) to the user's query spec­ ification is calculated as follows:

The similarity value is 0.54 because only attributes language and machine are involved (the user specified only these attributes), whose weights are 0.3 and 0.4, re­ spectively. The similarity bet ween ADA and [C, C++, COBOL, COBOL/S] is 0.2 and that for VAX and [SUI, JEWS , ... ] is 0.8.

4.4 Thresholding and N-Best Match

When there are too many combinations, translating all combinations and dispatching all SQL specifications are inefficient and wasteful. Methods to limit the number of SQL specifications to be created are necessary in real deployment. Two approaches are incorporated in the CARET system.

The first method is the N-Best match. CARET dis­ patches SQLs from highest similarity score, and counts the number of cases retrieved to stop the retrieval, when the number of retrieved cases exceeds a predetermined number.

Second, a threshold can be set in order to dispatch SQL specifications, which are sufficiently similar to the user's problem specifications. SQL specifications below a specified threshold will not be created.

4.5 Generating SQL Specifications

Each combination is translated into a corresponding SQL specification. Since SQL does not involve the similarity measure, the value assigned in the previous process is stored in CARET, and is referred to when the query results are returned.

The only SQL expression type used here is the SELECT-FROM-WHERE type . Its form is

SELECT fields list FROM case-base table WHERE field conditions;

This should read "Select records in a case-base ta­ ble which satisfy specific field conditions in the WHERE clause, and return the value of the requested fields in the SELECT clause from the selected records".

Each element in a specific combination is translated into a certain condition expression of SQL. For ex­ ample, machine(EWS4800) is translated into (machine = EWS4800) which means that the attribute machine must be EWS4800. Language( or( C, C++, COBOL, COBOL/S)) is translated into (language in (C, C++, COBOL, COBOL/S)) which means that the attribute language must be C, C++, COBOL, or COBOL/S. Then, each condition expression is connected with the logical­ AND operators. For example, and( machine(VAX), language( or(C, C++, COBOL, COBOL/S)) is trans­ lated into (machine = VAX) and (language in (C, C++, COBOL, COBOL/S)).

As a result, the SQL specification would be produced. An example of the generated SQL is shown below.

SELECT *

FROM case-table

WHERE (machine = VAX) AID

(language in (C,C++,COBOL,COBOL/S));

5 Performance Evaluation

CARET performance was evaluated using the SQUAD-II system which is a deployed case-base sys­ tem built on CARET using ORACLE, a commer­ cial RDBMS. SQUAD-II is a direct descendent of the SQUAD system which has been applied to the soft­ ware quality control (SWQC) domain. The prime dif­ ference between SQUAD and SQUAD-II is the use of RDB in SQUAD-II , where SQUAD was built on a home­ made case-base manager. SQUAD-II users are assumed to choose several attributes and their values which de­ scribes the problem which the user is facing. The user's choice, then, is interpreted by CARET, embedded in SQUAD-II, to produce SQL specifications. SQL spec­ ifications are sent to ORACLE to retrieve cases of soft­ ware quality control. Results are shown in the SQUAD­ II screen (Figure 4) .

The experiments were carried out on SUN Spare Sta­ tion 2, using ORACLE version 6 installed on SunOS ver­ sion 4.1.2. Figure 5 shows the response times measured for three user queries, and various sizes of case-bases. The three queries are:

Query-2: (LAJGUAGE = ADA) and (MACHINE = VAX)

SYSTEM-GEIERATIOI-TIME) and (CHOSEN-METHOD

Query-1: LAJGUAGE = C Query-3: (PROBLEM-TIME-BEFORE-QC = SYSTEM-GEJERATIOI-TIME) and (PURPOSE-TIME-OF-QC = = CHAIGE-IJ-PROCESS-SEQUEICE)

For query-2, the following SQL specifications and their similarity values are derived (See Table 3) .

Characteristics for each query are shown in Table 4. Query length refers to the number of conjunctive clause in the WHERE clause . Tree depth shows abstraction hi­ erarchy depth for each attribute. Tree width is the number of terminal nodes of the abstraction hierarchy of each attribute . Generated SQL number is the num­ ber of SQLs generated and actually sent to RDBMS. Cases matched shows the number of cases matched in each query. 158+4+199 should read as 158 matches at the first SQL, 4 matches at · the second SQL, and 199 matches at the third SQL. These numbers are measured with a case-base containing 800 cases .

The algorithm scalability has been tested by increasing the number of cases in the case-base. The number of cases was increased up to 1 ,600. Response times (in real­ time, not in CPU time) are shown in Figure 5.

Query-1 returned the major part of cases in the case­ base, resulting in slower response time due to the neces­ sity to retrieve these cases. The response time for the query-1 increases linearly as the case-base size increases . Indexing methods for the commercial database systems are not effective for reducing response time in such sit­ uations. Also, most of the time is spent on retrieving matched cases, rather than on matching itself.

Fortunately, however, users generally specify a query in a much more detailed manner . An empirical anal­ ysis, using the SQUAD system, showed that the aver­ age number of specified attributes for each retrieval was 3.4 out of 75 features [Kitano et al., 1992] . This would help RDBMS to constrain the search and the query time would be dramatically shorter. The second and third queries confirm this observation.

The second and the third queries show a nearly con­ stant time responses, regardless of the case-base size. This is due to the fact that SQL specifications are spe­ cific enough to constrain the search on RDBMS. Since the system provides fast response time, it would suffice for most tasks.

A brief analysis of the performance results would shed light on the system behavior. There are two major fac­ tors which affect retrieval speed. They are: number of SQL specifications actually dispatched to the RDBMS, and number of cases retrieved. The maximum number of the SQL specifications which may be created is decided by a number of specified attributes by the user and the depths of the tree of the specified attribute (Equation 2) . Longer response time is required with a larger num­ ber of cases to be retrieved . The number of cases to be retrieved depends upon the specificity employed in the SQL specifications. Query-1 resulted in longer response time than query-2 and query-3, because a large number of cases had to be retrieved. Query-2 and query-3 at­ tained faster response time, because SQL specifications were specific.

6 Conclusion

This paper proposes a new method which enables the use of RDBMS as a case-base management system. Al­ though case-base management, such as data-security and data-integrity, which are readily available in RDBMS, has not been the subject of significant case-base reason­ ing (CBR) research, case-base management functions are essential to the integration of CBR systems with main­ stream corporate information systems.

This paper has proposed a novel method to implement similarity-based retrieval using SQL, hereby enabling CBR systems to use RDBMS. The algorithm was imple­ mented as a CARET case retrieval tool. CARET gener­ ates SQL specifications of varying degrees of similarity, and the generated SQL specifications are dispatched to

-

RDBMS to retrieve cases from RDB. The method we have proposed here determines a pre-compute similari­ ties for individual query forms, rather than computing the similarities of individual cases.

A performance test using SQUAD-II, a corporate-wide CBR system built on CARET, has demonstrated that the proposed method attains acceptable performance and suggests that the proposed method is practical for large-scale case-bases used in workstations. The pro­ posed method, then, is well-suited to serve as a basic algorithm for corporate-wide large-scale case-based sys­ tems.