Browsing in Large Data Bases

1. INTRODUCTION

Consider the tasks of trying to find similarities between the causes of the crashes of several aircraft of a common type, the causes or early warning signs for various diseases, the characteristics of stocks with high growth potential or advanced warning signs of severe weather conditions. All of these tasks require a large amount of data and valuable time spent sifting through the data. Browsing or troubleshooting computer systems of the future will eventually perform these tasks. BROWSER is designed to be the prototype of su~h systems.

BROWSER is an automated system for trouble­ shooting with data bases. It is based on Douglas Lenat's automated discovery in mathematics (1] (2] and is designed with a modified production system architecture (3] (4]. BROWSER explores a data base using models des0ribing the data and .a large collection of

data-dependent and data-independent heuristics.

An ·:!xample of -'i BROWSER data base is a dat'l

bas~ containing information on maintenance acLLons performed on U.S. Navy ~ircraft [5]. Th ,~ d.::~ta base is explored through the definition of data subsets and their examination using simple statistical tec~niques. With~n a data subset BROWSER looks for regularities such a recurring sequences of data or unusually high occurrence rates of a particular datum. BROWSER 3ttempts to find

This work was supported by the Office of Naval Research under Contract N00014-75-C-0612 while the author was at the University of Illinois

at Urbana-Champaign.

sequences of maintenance actions which precede a particular maintenance action. Such an action might be the failure of a component in a system. If such a pattern can be found, i t could be used to give warning of the possible failure of that component. When one of the preceding events occurs the part which is due to fail could be repaired or replacP.d eliminating possible adverse conditions which might later occur due to the failure of the component (e.g., the aircraft crashing).

When comparing two data subsets BROWSER looks for statistically significant differences in the occurrence rates of a particul~r datum. BROWSER can compare aircraft \.Jith very good maintP.nance. histories to aircraft with very poor maintenance histories to find differences. Discovery of these differences might lead to modifications on the aircraft with poor histories which will improve their system performance.

All discoveries or f3cts about the data are reported to the user. The user could be giv~n the option of creating alerters [6] (7], which would monitor for the occurrence of these facts in new data entering the data base. (Alerters

are not currently implmented.)

2. IMPORTANT BROWSER FEATURES

BROWSER contains three significant features . First is the representation of facts and knowledge known about the data base. This knowledge is contained in models ::~nd data­ dependant heuristics. Second is the controlled execution of tasks within the system. For this, BROWSER uses an agenda, an ordered list of ~11

tasks which are to be executed, dat3.independent heuristics, and a controller, which executes the agenda tasks. The final significant feature is the representation of new knowledge. New knowledge is represented and stored in concept trees. Each concept represents a subset of the data and contains several facets which describe the subset.

2. 1 Data Base Knowledge

Knowledge of the data base is stored in models and data-specific heuristics. Five general types of models exist in BROWSER. The first four model types provide detailed knowledge about the data in the data base while the fifth provides general knowledge on data structures useful for examining the data.

The lowest level models are the Data Base Models. One Data Base Model exists for each type of data file in the data base. Each model contains a description of tho data fields which compose the data file, including the field's retri eval name (used in the data base query language), an equivalent English name, the starting position of the field in a data record, the length of the field, and the type of value contained in the field (numeric or character). The Data Base Models are used mainly by the data base man~gement system for retri eving data from the data base.

The Data Specific Models provide information on how the various data fields are related to each other. These models show the semantics of the data fields. Again, one Data Specific Model exists for each type of data file in the data base.

·The Specific Models are of two varieties. The first shows how the data. records, described semantically in the Data Specific ~odels, combine to form larger units called Conceptual Units. For the aircraft data basP. an example Conceptual Unit is a maintenance action performed on :m aircraft. Each performed maintenance consists of several actions, such as the removal of an aircraft part, the repair of a part or the installation of a part, where each action is described by a single data record in the data base. The second type of Data Specific Models dP.scribes the objects from 'Nhich the data was gathered. For the aircraft d~ta base these models are of the F-4 and A-7 aircraft.

Typi cal Models are the most general data specific models. They describe generalizations of the Specific Models. Generalized knowledge which ·3pplies across Specific Models is stored in the Typical Models. BROWSER's Typical Models include a model of a typical aircraft and the model of an aircraft's history. The typical aircraft model represents common knowledge known about all aircraft. The aircraft's history model shows how the Conceptual Units of performed maintenance combine to form thP. overall maintenance history of an aircraft.

The final model type is that of the General Models. They provide information on the typical types of data structures which exist within the data. Included are models of a network, a tree, and a list.

Data-dependent heuristics are contained within the models. These heuristics provide knowledge about the data values in the data fields and other knowledge not represented by the structure of the model. Interconections between models are provided so this heuristic knowledge can be shared.

2.2 Controlled Execution of Tasks

The second significant feature of BROWSER is the use of an agenda to control the execution of tasks within the system. BROWSER's basic operation is to define new subsets of data and explore them. At any one time BROWSER mi~ht have 50 or more subsets of data being considered for examination, many additional subsets currently being ex·3mined, and some subsets which have alre'ldy been fully examin:~d. The system uses an agenda to keep track of all of the tasks associated with the subsets which must be performed. These tasks are of two types: those which fill in the facets of 1 concept and those which explore and examine the

data subsets associated with the concept.

The tasks on the agenda are ordered. This ordering is determined by several factors. Certain tasks must be executed before others: e.g., the definition of the data contained in a subset must exist before that subset can be retrieved from the data base, and the subs~t must be retrieved before it can be ex~mined for regularities. Additionally, some tasks 1ppe.ar to be more interesting to perform than others because of the results of previous tasks. Each task has a list of reasons ·,.rhy it should be executed, each reason has a value and the sum of all of the values, the task priority, gives the position of the task within the agenda.

The basic procedure of BROWSER is as follows. All tasks are sorted according to their priorities. The highest priority task is removed to be executed. All heuristics, both data-dependent and data-independent, which ~re relevant to the execution of this task are gathered. These heuristics .~re then exP.cuted one by one. When all of the relevant heuristics

have been executed the cycle is repeated. This cycle is continually repeated until all tasks have been executed.

2. 3 Repres.:mtation of New Knowledge

The final significant fe:1tur·~ of BROWSER is the representation and storage of new knowledge. New knowledge consists of facts gathered by BROWSER from the data base ano is stor~d as faceted concepts on concept trees. Initi~lly the data base is described by a sm::tll set of concepts: ALL-PLANES (the entire data base), CRASH (aircraft which have cr~shed), NON-CRASH (aircraft which have not crashed), HI-MAIN (aircraft requiring excessive maintenance) and LO-MAIN (aircraft with good maintenance histories). BRO~SER creates more subsets and their associated concepts by examining existing subsets of data and offering ideas on how the existing subsets might be restricted to form smaller subsets or, possible, generalized to form larger subsets. Each new subset is described by a concept in a concept tree with its facets holding the important and relevant information desired about the subset. Note that the subsets of data described by the concepts can intersect in their coverage of the d3ta b:JSe, and that new subsets are always

ere·:l.ted from existing subsets.

The concepts hold the relevant information nP.ed~d about the data subsets. They represent the subsets and show their relationship to the oth~r subsets. Each concept consists of a number of facets or characteristic knowledge ~bout the subset. Typical facets include: NAME - tn·~ n2me used to refer to the subset; DEFN - ti'l~ d·3finition of the data contained within the subset; INTEREST - a ~umeric measure of how interesting the subset of data is; GENERALIZATIONS - pointers to more general (larger, containing) subsets; SPECIALIZATIONS - pointers to more r3stricted (smaller,

~ont'lin~d) subsets.

~. .'iUi'iMARY OF RESULTS

The initial imple~ntation of BROWSER was design::!d to test the fe.::lsibility of :tutomatic browsing. It was implemented in MACLISP and ran on a KI DgC-10 computer, occupying a total of IIIJO pages of memory (this indudes the data b:.ise :nanagP.ment system). The data base ~onsisted of one ye.::~r of maintenance 1uthorization records for six aircraft. For r~lated models w~re implemented: the lAta Base -tnd ~ta Specific Models for the particul3r

this initi1l implF!mentation two of the dat':l. daLa files used.

The initial testing occupied 24.5 CPU hours. The data base management system used 54% of this time retrieving the data. Approximately on:! half of the remaining time was used examining the data returned. The ex'lmination suggested the creation of 224 dat~ subsets. I found 45 of the 115 subsP.ts actu::tlly created to be of interest. Of the subsets suggested, 16? were suggested becnuse dat .::t values occurred at statistically significant rates. T judged one half (q2) of these subsets to be worthwhile to create. Several interesting differences were found between the data subsets, differences too complex to summarize here [8] .

While the initial implementation of BROWSER was limited in its scope, it h::ts provided some important ideas and insights for developing more complex systems. It is hoped that in the near future such systems will be able to provid·e valuable information to users, information which currently is not available or is very expensive to obtain.