Problem Solving Approach In Data Management

Introduction

This paper presents a problem in the data management area and demonstrates how that problem can be solved using an Artificial Intelligence Technique known as Problem Solving. The problem is that of determining a data path through a data base which consists of data and programs in order to determine the desired answer to a user's re­ quest. The data structure is viewed as the initial s tate, the queries provide the goal, and the various functions in the data base provide the operators which are used to map from the initial state to the goal. This paper will primarily be concerned with describing this problem and the development of its solution and then discussing the particular algorithm involved in the solution . The work presented here was a development made in the data management area and is not simply a new appli­ cation developed for an Artificial Intelligence Algorithm. The following, then, is a description of the problem.

One of the many concerns facing organizations , both in the private and public sector, deals with the need to analyze as well as report information from their data bases. There is an increasing demand for these organizations to perform such planning functions involving forecasting, simu­ lation, and optimizations. The GPLAN [ll research project at .Purdue University is concerned with developing a framework for a generalized planning system which will help to satisfy that demand. The system being developed will provide the planner with an environment consisting of data, programs for generating reports using this data, and a collection of models (programs) which can easily be used to analyze the data. The interface be­ tween the user and this environment will be Englis~ like interactive query language. The following is a brief discussion of the major components of the GPLAN system. (Figure 1)

Andrew B. Whinston Purdue University Lafayette, Indiana

The user (1) interfaces to the system through an interactive query language known as the GPLAN/ QA [2J. The query system (2) accepts the user's request as stated in the query language, parses and verifies the syntax, and stores the query in a standard matrix form. All of the tables used in the parsing are actually stored in the data base to permit each application to have its own set of keywords and operators. A more thorough discussion of the query language can be found in user's manual [ 2 J and paper by Haseman and Whinston [3].

After the query has been parsed, the control program (3) analyzes the query and determines what action will be required to answer the re ­ quest. These actions not only include generating calls to the data base through the Data Mani­ pulation Language (DML), but also include the execution of functions (programs) which will operate on the data retrieved via the DML cal l s . This process will be discussed in more detail in the next section of the paper, while the following is a description of the rest of the system.

The core of the system is a Data Management System (3, 4, 5), which is called the GPLAN/DMS f4] (5] system. The DMS was developed using t he specifications of the CO~SYL DBTG Report [61 and will support data structures which range from sequential files to complex network data struc­ tures. The data structure which is supported by the query language is a hierarchical data struc­ ture. The schema consists of a group of tables which describe the logical structure of the data base while the physical data is stored in the data b'ase. The system generates the schema. based on a user's description of the data structure using the Data Description Language (DDL). The basic unit of data is known as an item-type, where a group of item-types forms a record-type. The user can also define set-types which generate an owner­ membership relation between two record-types. The DML commands are used by the control program to search through the various set relationships to determine the desired data.

The final component of the system is a collection of functions (programs) which will perform various operations on the data involved. In general, we can have any collection of appli­ cation programs. Current implementation has the following: report generators, plotting, simu­ lation, and optimizations. These functions re­ ceive their input from files generated from the data base by control program and may return the output to the user as well as store results back into the data base.

Using this introduction to the GPLAN system as background information, the following, then, is a description of the problem of how to design a control program to intermix DML calls on the data base and functions on this data to answer more involved queries. This can be viewed as a path finding problem.

Problem

The previous approach used to answer a query involves determining the shortest path through the data structure which includes all the item­ types which were requested in the query. For example, assuming the data structure as shown in Figure 2a, the following query could be requested:

LIST REACH-NUMBER AND FIDY-RATE.

The algorithm would determine that the correct path would involve Sl and S3. Assuming each reach contains three meas.urements of flow, the following response would be obtained:

and the derived data path would appear as follows:

As can be seen, if each set has only one owner record-type and one member record-type, the data path can be completely determined by the sets in­ volved. Extending the concept of currency as discussed in the CODASYL Report, the following is a definition of a current set:

A current set is a set which is used to describe a data path required for a.nswering a query.

One of the problems with this approach of answering a query is that functions can only be attached at the end of a data path; in other words, all the data along the path is collected and then passed to the function. The following query cannot be answered using the above approach without a specialized average function:

LIST REACH-NUMBER AND AVERAGE (FLOW-RATE)

This query essentially requires tha.t a function be inserted into the data structure, and there­ fore requires a restructuring of the data base. A second type of query which cannot be handled with the above approach is:

LIST REACH-NUMBER, FLOW-RATE, AND TEMPERATURE

since this request involves splitting a path at the logical level. Assuming that the user speci­ fies that there exists a relationship between Flm-RATE and TEMPERATURE (say, a one-to-one relationship), the system should be able to answer this query.

It was these two requirements which lead to the development of a control program using A.I. techniques. The following, then, is a descrip­ tion of the formulation of the problem in terms of the initial state, the goal, and the operators available to transform the initial state into the goal. It is assumed that the reader is familiar with predicate calculus as discussed by Nilsson [7] and with theorem proving algorithms such as discussed by Fikes and Nilsson (8].

Initial State

The purpose of the initial world model is to describe the initial state of the system in terms of a group of well-formed formulas (wffs). These wffs provide a description of what the theorem proving system is given as known's or truths. As a particular solution is generated, various operators will change or modify this initial model to represent the current state at that point in the solution. This is done in terms of gener­ ating a list of those wffs which should be removed from the initial state, and those which should be

added to the list.

In terms of the specific problem addressed in this paper, the initial world model contains a description of the initial data structure as described in the data description language. The wffs include definitions of which variables are item-types, record-types, and set-types, as well as a description of the item-types which compose the various record-types, and various record­ types which form the various set relationships. Additional wffs can be defined which will provide a description of the relationships such as was discussed previously with the TEMPERATURE and FLOW-RATE problem. These relationships can either be defined as an addition to the DOL, or inter­ actively by the user.

The wffs which would describe the data structure shown in Figure 2 are as follows :

TYPE (R 1 , RECORD)

TYPE (R 2 , RECORD)

TYPE (Rs· RECORD)

TYPE (REACH-NUMBER, ITEM)

TYPE (FLOW-RATE, ITEM)

TYPE (TEMPERATURE, ITEM)

TYPE (SO, SET)

TYPE (S 1 , SET)

TYPE (s 2 , SET)

TYPE (S 3 , SET)

TYPE (S 4 , SET)

TYPE (REL, RElATIONSHIP)

BELONG (REACH-NUMBER, R 3 )

BELONG (FLCJoi-RATE, R 4 )

BELONG (TEMPERATURE, R 5 )

CONNECT (S 0 , SYSTEM, R 1 )

CONNECT (S 1 , R 1 , R 3 )

CONNECT (S 2 , R 1 , R 2 )

CONNECT (S 3 , R 3 , R 4 )

CONNECT (S 4 , R 3 , R 4 )

CONNECT (REL, R 4 , R 5 )

STATUS (S 0 , ON) .

STATUS (S 1 , OFF)

STATUS (S 2 , OFF)

STATUS (S 3 , OFF)

STATUS (s 4 , OFF)

STATUS (REL, OFF)

where the following wffs are defined as:

TYPE - define the type of a variable

BELONG - define which record- type contains an item-type

CONNECT - define which records form a set or relationship

STATUS - define whether the set or relation­ ship is currently connected (determines path through data base)

Two additional wffs are required for determining uniqueness. The first states that a par.ticular variable cannot be more than one type:

The second states that sn item-type can only be­ long to one record-type:

Specifying the Goal

The goal is specified by the user in terms of the query language. Although the query can contain arithmetic and logical operators, the portion of the query which is critical to the con­ trol program is the item-types involved and any functions which are specified to operate on those item-types. The goal essentially becomes a list

of item-types and functions which must appear along a single data path in order for the query to be valid.

For the following query:

PLOT THE REACH-NUMBER VERSUS THE AVERAGE (FIDI-RATE)

the goal would be to determine a data pth which contained REACH-NUMBER, FIDI-RATE, AVERAGE, PLOT. One path (not necessarily unique) which would satisfy this goal is shown in Figure 3. Since ma.ny models can produce specific item-types as outputs, the function names may be implied by the goal, rather than specifically stated. An ex­ ample might be:

LIST LEAST-COST-SOLUTION

where this query would imply the execution of an optimization program whose output is a variable called "LEAST-COST-SOWTION," As the technique is further developed, it is hoped that goals can be implied from ordinary English-like questions. It should be noted that this definition of goal is substantially different from the concepts used in many of the so-called "question and answering" systems. The goal, in our context, is to determine the data path which will satisfy the desired query. Once this data path is determined, a separate al­ gorithm will actually go out and access the data and execute the functions along that path for the different record occurrences.

Operators

The operators are used to transform the initial state to the final state, which satisfies the goal. These operators can be classified into two groups. The first group is used to connect and disconnect various set relationships in the data base to reach those item-types of interest. The second group relates to those functions which are stored in the data base and are used to oper­ ate on the data items. The format which will be used to describe the operators are as follows:

1. Name and Parameters.
2. Preconditions: This expression must be evaluated as being true for existing state before this operator can be applied.
3. Delete List: These wffs should be deleted from the current state of the system when this operator is applied.
4. Add List: These wffs should be added to the current state of the system when this operator is applied.

The following predicate will be referred by the operators:

1. available (P) · (~ X) (8 Y) (3 Z) [TYPE (P, ITEM) A BELONG (P,X) A CONNECT (Y,Z,X) A STATUS (Y,ON)]

The following function is used to determine the unique X for a given P.

1. record (P) = X such that (~ X) BELONG (P,X) is true

The predicate available determines if item-type P is available; in other words, if item-type p currently lies along a path which is "ON". The record function determines which record-type X owns the item-type P.. The following, then, are two operators which connect and disconnect the set structures;

1. link (P): Link together two records
2. to form a set Precondition: STATUS (P,OFF) A (3 W)(3 X) (2 Y)(3 Z) (CONNECT (P,X,Y) A CONNECT (Z,W,X) A STATUS (Z,ON) A TYPE (Z,SET) A [-(V A)(VU)(CONNECT (V,W,U) A STATUS (V,ON) A TYPE (V,SET)AU #X]] Delete List: STATUS (P,OFF) Add List: STATUS (P,ON) 2) unlink (P): unlink two recorda from a set Precondition: STATUS (P,ON) A (a X)(3 Y) (CONNECT (P,X,Y) 1\- ('I W)(1f Z) [CONNECT (Z,Y,W) A STATUS (Z,ON)] Delete List: STATUS (P,ON) Add List : STATUS (P ,OFF)

The link operator is used to link together two records in a set or link together two records which form a relationship. Before a record can own a set or a relationship, it must itself be owned by another record through a set relation­ ship. Records which are owned through a relation­ ship cannot in turn own other records. The un­ link operator is used to break the set and re­ lationship links. This operator will not break a link in the middle of the chain; in other words, it will only remove records from the bottom of the path.

The following operators are two examples of the kinds of functions which can be defined to operate on any data items:

1. ave (P): Average the value of P

Precondition: AVAILABLE (P)

Delete List: STATUS (S-AVE,OFF)

Add List:

CONNECT (S-AVE,RECORD (P),R-AVE) STATUS (S-AVE, ON)

4) plot (P 1 ,P 2 ): PLOT P 1 VERSUS P 2

Precondition: AVAILABLE (P 1 ) ~

AVAILABLE (Pz) Delete List: STATUS (S-PLOT,OFF)

Add List:

STATUS (S-PLOT,ON)

CONNECT (S-PLOT, RECORD

(P l), R-PLOT)

CONNECT (S-PLOT, RECORD

(P 2 ),R_PLOT)

where the above functions assume the following in­ formation which was initial in the initial world description:

The third operator describes the average function which inputs one item-type and generates a new item-type called P-AVE. When this function is used, a new record is actually created in the data base. The fourth function is PLOT which in­ puts two item-types and generates a plot as its output. Since the result of the PLOT function is only output, no new data structures are created by the PLOT function.

The two operators just discussed are general functions which are designed to operate on any data items. Another class of operators can be defined which requires specific data items rather than any data item. An example of this type might be:

1. Temp A Temperature Analysis Routine

Preconditions: available (TEMPERATURE;

Delete List:

STATUS (S-TEMP,OFF)

Add List :

STATUS (S-TEMP,ON)

where the following would be included in the initial state:

TYPE (S-TEMP,FUNCTION) STATUS (S-TEMP,OFF) ~~}

This function could be requested by the simple query:

TEMP

Examples

The following examples will show how the previously defined operators may be used to determine the logical data path through the data and the programs stored in the data base. The first example is the query mentioned previously :

PLOT REACH-NUMBER VERSUS AVERAGE (FLGI-RATE).

One example of the sequence of operators which might be applied to the initial world model to solve this problem would be as follows:

The logical structure this query would generate is shown in Figure 3. Once this path was determined, the data would be accessed and the functions (AVE and PLOT) would operate on the collected data.

The second example would involve the following query:

PLOT Flm-RATE AND TEMPERATURE

The query cannot be answered using the set re­ lationships alone since these two item-types do not lie along the same data path. If the user were to define a relationship as given in the initial world model, then the logical data path for the query would be generatea as follows:

where the generated data structure is shown in Figure 4a.

The third example involves requesting a function whish will operate on a specific set of data. For example:

EXECUTE TEMP

The functions which would be required are:

where the logical data structure for this qu~ry is shown in Figure 4b.

Conclusion

The approach which was presented offers one possible solution to the complex problem of dynami­ cally restructuring a da.ta base in order to respond to a user's query. The problem solving technique provides the unique capability of determining if the goal (query) can be obtained given the initial world model. There still clearly remains several areas which need to be explored in more detail. . One area involves trying to recognize "classes of queries" such that for simple requests, the tra­ ditional data path algorithm can be used, and for more involved reqvests, the problem solving ap­ proach should be used. Another area involves the possibility of saving queries and their paths for future reference, thus providing a learning capability to the system. The final area is con­ cerned with placing more preconditions on the various functions to prevent such things as trying to average a group of names, and to perform other syntactical checks.

Acknowledgement

This work was supported in part by Grant Number 65377-55 from the Office of Computin~ Activities of the National Science Foundation. The authors are indebted to Professors Dave Workman and Bob Bonczek of Purdue University and Jack Buchanan of Carnegie-Mellon University.