The Application Of Artificial Intelligence Of Data Base Management

Abstract

An application of Artificial Intelligence Is discussed: an automatic programming system that generates information retrieval programs and data base structure designs for highly structured or network data bases. It ls claimed that these applications are unusual ln that they have more practical value than Is usually the case, being of Immediate utility to commercial data base management. The paper concludes with a short reflection on the problems associated with the representation and acqulsltlon of knowledge for problem solving programs. In particular, representation of knowledge Is Important for efficiency of the programs, yet an efficient representation may not be "natural". it was difficult to separate representation from content, and successful application required that the expert providing the knowledge also know how the program uses that knowledge.

CR categories: 3.5, 3.64, 3.7, 4.2, 5.23

Key words and phrases: application of Artificial Intelligence, automatic programming, procedure generation, information retrieval, network data base, Data Base Task Group, data base design, non-procedural languages.

lntrodyctlon

Most successful Artificial intelligence programs exercise their problem solving ability ln non-realistic environments or apply It to a game playing task, but this state of affairs does not constitute a basis for criticism of AI. As many of the proponents of AI have maintained, It Is necessary for AI to cut Its teeth on toy problems, games, and In otherwise limited environments before It can proceed to fulfill Its highly touted promises. Perhaps the only fair criticism Is that this teeth cutting Is taking longer than envisioned by early

workers In the field.

AI Is entering an age where practical and objective application is feasible. This Is not to say that there have not been very valuable spln-offs

from AI research that have contributed to

* A major portion of the work described herein was done while the author was at Carnegie-Mellon University, Pittsburgh, Pennsy 1 van I a.

Rob Gerritsen The Wharton School (·) University of Pennsylvania

Philadelphia, Pennsylvania

advances In fields such as computer science, linguistics, and psychology, However, there have not been many direct applications of AI technologies {with perhaps the exception of pattern recognition) to problem areas outside the

research laboratory.

My background ls not primarily In AI, but lies more In the area of commercial data processing, data base management, and information retrieval. My experience In these areas predates by several years my introductory exposure to AI. This fact ls relevant because the problems, which will be described shortly, existed for me long before I discovered the technology to solve them. As such, my circumstances provided an amount of practical experience not typically possessed by the AI researcher who Is looking for problems to adapt to his technology,

The application described here Is a practical one. The problem solving systems that have been developed can supplant or augment some of the tasks currently being performed by programmers and data base admlnfstrators.

Data Management Application

The subject of this paper Is the successful application of AI, particularly automatic programming technology, to the problems of Information retrieval and data base nesl~n. This has resulted In a system<l,2,3> that generates Information retrieval programs and data structure declarations.

These two problem solving tasks have been around for a long time, but growing commercial usage of larger and more complex network data bases has suddenly increased their significance. (As used here, the term "network data base" refers to a data base In which a data Item may be linked to many other data Items. Our subject Is not data bases on computer networks.) There has been an attempt within the United States and Canada to develop a standard for network data bases through CODASYL which spawned the Data Base Task Group (DBTG) involving both industry and academia. This group has produced a specification for a general purpose network data base system<4>. Although not yet accepted as a standard, It Is believed by many that the DBTG specification will be so adopted, perhaps by default since many computer manufacturers and software firms are now selling Implementations of the DBTG specl f I cat Jon.

Both applications described herein function In the data base environment as specified by the DBTG. That Is, data structures designed by the system conform to DBTG specifications, and the Information retrieval programs generated by It are COBOL Procedure Divisions contalnln& Data Manipulation Language (DML), as defined by the DBTG.

Programming for Network Data Bases

Introduction of the network type of data base brings with It a new level of complexity for the business programmer. Earley<S> points out that Instead of the usual logical-physical dichotomy that a programmer traditionally deals with, there Is a loglcal(a)-loglcal(b)-physlcal trichotomy facing the network data base programmer. The logical (a) ·level corresponds to data relationships as perceived by the data user. The loglcal(b) level concerns the actual links between the data In the data base.

Bachman<6> recognizes this complexity In the 1973 ACM Turing Award Lecture where he likens the programmer's problem <ln the network data base environment) to that of a navigator. The programmer Is given the user's query requirements; his task Is to find the proper access path to the data through the myriad of connective links In the data base.

The programmer's task should be reduced. After all, much Its complexity Is caused by an artifact Introduced by the data network, the data links. It should be noted here that others In the field, primarily Codd<7,8,9>, have proposed relational models of data bases whereby they hope to avoid this artifact. It Is not clear, however, how this can be done without exactly the kind of problem solving program that Is the subject of this paper.

The technology used to reduce this task comes from work In the area of automatic programming. A compiler developed by Buchanan and Luckham<10,11> was used to create the Information Retrieval Procram Generator.

Prograrnm!ng Rules

The Information Retrieval Program Generator Is compiled from a set of rules. These rules are stated In a formalism that closely corresponds to the formalism developed by Hoare<12> to describe the logic of programs. Each such rule describes construct, be It statement, a DML program construct. some type of program a loop, assignment statement, or other One type of rule describes the conditions under which a program statement may be used, and the effect of Its use. For example, the rule for a "GET" statement says that It Is not possible to GET a record unless Its location In the data base Is known to the data management system, and that the object record will be located In working storage following execution of the GET.

This rule Is formally stated (to the compiler) as:

(CURRENT R1) IIGET Rlll (INCORE Rl) In this rule Rl Is a variable (for record name) and (CURRENT Rl) and (INCORE Rl) are predicates. Henceforth we use the convention that Rl, R2, Xl, 11, etc., are variable names.

Other rules do not bear such close resemblance to a description one might find In a programmln& manual as does the rule for GET. These other rules capture my own programming knowledge, Including heurlsltlcs, that I had previously acquired and developed as a professional programmer.

One such rule ls the rule that describes the top level composition of a program:

(OPENED A!)I\(CURRENT Rl)l\ (LINKED Rl R2)1\ (CLOSED Al)I\(STOP X1)

--> (PROGRAM Xl)

This rule Is different than the rule for GET: It does not defIne a program statement, rather It Is an Implication stated with predicates. The order of the predicates Is obviously Important.

A semantic Interpretation of this rule Is that a program consists of five blocks that (1) open the required files of the data base, (2) locate the first record of Interest, (3) follow the access path from this record to all other records of Interest, (~) close the files opened above, and ( 5) term! nate execution.

Of these five blocks, the second and especially the third, are the most complex. They may Involve many further levels of refinement, revealing Iterations, alternations and compositions. The third block wil l Include the processing of the records on the access path to display values , calculate statistics, etc.

Translation to Micro-Planner Theorems

The rules are translated by the Buchanan-Luckham compiler to Mlcro-Planner<13,14> theorems that constitute the Information Retrieval Program Generator.

For example, the GET rule Is compiled to:

( DEFPROP GET (THCONSE (Rl) (I NCORE (THV Rl)) (THGOAL (CURRENT (THV R1))) (THSET (CAR (THV ANS)) (CONS (CONS (QUOTE GET) (LIST <THV R1))) (EVAL (CAR (THV ANS))))) (THASSERT (INCORE (THV R1)))) THEOREM)

The theorem presented here Is Quite condensed from the one actually generated, which also contains bookkeeping, tracing, uniQueness, and other special functions. Note that the pre-condition of the rule, (CURRENT R1), Is a goal In the theorem. Similarly, the post-condition, (INCORE R1~ Is defined as the consequence of the theorem and will be asserted when the theorem Is used. When the theorem Is used 'GET R1 1 will be catenated onto the ANSwer.

Program construction proceeds In a sub-goaling fashion. For example, If ((NCORE PATIENT) Is a goal then the GET theorem Is tried, and (CURRENT PATIENT) becomes a sub-goal. A sub-goal may Invoke other theorems In turn, generating further sub-goals. This process generates a goal tree with leaf nodes which are true or false In a set of assertions known as the "state".

The Initial state Is the only Input to the program generation process and Is made up of two major subsets of assertions. One $uch subset describes the structure of the data base, the other describes the query for which program generation Is required.

The description of one more rule will give us a sufficient number of rules for an example. A rule for FINDing records:

(HASHKEY R1 K1)A(DESIRE K1 V1)A

(CONTAINS K1 V1) IIFIND R1ll (CURRENT R1)

This rule Is similar to the rule for GET; It defines a program statement. Again, It corresponds closely to a paragraph In a programming manual: To FIND a record, first Initialize the key for that record with the value Identifying the desired record. Following the execution of FIND, the record Is current to the data management system. Current Is a DBTG term meaning that a record's exact location In the data base Is presently know to the data management system.

Example

Assume that a data base definition specifies that STUDENT records are (hash)keyed on SNUM. If a Query asks for Information regarding the student having number (SNUM) 126, then two of the assertions In the Initial state will be: (HASHKEY STUDENT SNUM)

(DESIRE SNUM 126}.

The first assertion belongs to the set defining the data base, the second to the set defining the query.

Micro-Planner Is given the goal (PROGRAM EXAMPLE), and program generation commences. The first sub-goal, (OPENED Al), Is satisfied with a set of rules not Illustrated here resulting In an Initial block of procedure to open the f 11 es.

The next sub-goal Is (CURRENT R1}. Since the rule for FIND has this as a conseQuence,lt Is tried. The first two sub-goals In this rule are Immediately true In the state, and the variables R1, K1, and V1 get bound to STUDENT, SNUM, and 126, respectively. The third sub-goal Is satisfied with the assignment statement rule (not Illustrated here), and an assignment statement Is Inserted In the program. The pre-condltton now being true, 'FIND STUDENT' Is put Into the program.

as: At this stage the program appears

(Block to open files) MOVE 126 TO SNUM. FIND STUDENT.

The state (set of assertions> has also been altered and now contains an additional assertion, (CURRENT STUDENT), because of the FIND rule. This may affect subseQuent procedure generation. For example, If the Query requires that values from the STUDENT record be In working-storage, the system will not generate any procedure for the (CURRENT R1) sub-goal In the GET rule.

peslgnlng Network Qata Stryctyres

Another problem attendant to data base management Is data base structure design, that Is, the design of appropriate links between data elements so that data relationships can be properly captured and reconstructed. Since all such relationships must be Implicitly contained In the set of all retrieval requests, It should be possible to derive a data base structure from such a set<3>.

The Automatic Data Structure Designer operates In exactly this fashIon. It generates a data structure design that Is satisfactory for a set of queries. The resulting structure Is not optimal but has the characteristic that data redundancy Is minimized (and as a corrolary, the number of links are max lml zed).

The design program has two major tasks: to design a network structure that can accomodate all of the hierarchical relationships referenced In the queries, and to determine the best location In the structure for each data Item.

Detection of a hierarchical relationship in a query is not difficult. The system simply looks for quantifiers or sunwnarizlng commands such as "all," "any," "average," "total," etc. For example, a query asking for a class list <All values of student-name when class "history") suggests a hierarchical relationship between class and student-name. Similarly, axerage grade for student-name · "Anderson, suggests that there may be many values for grade for a given value of student-name.

A designer has a problem If, for example, In addition to the class list discussed above, a second query asks for a student transcript (all values of class when student-name · "Anderson"). The two queries' views of the data base are inverted with respect to each other.

Included in the Automatic Design System are rules that recognize such situations. These rules will Insure that a special 1 inking record is included In the data base design. Through this record will pass two linked lists, one for each hierarchy.

The second principal task of the Designer is to determine the location of data items (attributes) In the hierarchical structure. Queries may differ In their views of attribute associations. For example, hospital name may be viewed as a patient attribute In one query (where he's being treated), as a doctor attribute (where he works), or as a hospital attribute In other queries. If hospital-patient and hospital-doctor hierarchies (several patients and several doctors per hospital) have already been constructed by the system, then It will assign the attribute In question to the hospital record. This permits usage of hospital name as a unique attribute of hospital, doctor, and patient.

Using Earley's terminology, we can say that the Automatic Data Structure Designer finds a logical(b) arrangement that accomodates all loglcal(a) relationships. As a matter of fact, translation from loglcal(a) to loglcal(b) also characterizes the system's activities as a programmer. Further translation to the physical level Is not the task of these programs. That activity Is performed by the data management system, e.g. an Implementation of the DBTG specification .

As was the case with the Information Retrieval Program Generator, the Automatic Data Structure Designer Is defined with a set of rules that are translated by a compiler to a program of Micro-Planner theorems. However, In this case the resulting system Is not a code generator, It Is a declarative generator .

Representation of Knowledge

If a system Is to apply knowledge, It must of course first obtain such knowledge. Until generalized learning systems become available that can be adapted In a practical way for use within a particular application domain, It Is necessary to imbed knowledge of the application either by building a specific learner for that ~ystem or by providing the system directly with the knowledge It needs. The trouble with the former approach Is that building the learner may turn out to be Impractically difficult. The latter approach Is the one that was taken for the applications discussed here.

Complexity of Knowledge

The rule formalism provided a good framework for capturing network data base programming and design knowledge. Even so, capturing the knowledge involved many trial-and-error iterations because much of it does not have a well understood structure. Furthermore, It Is possible to map the knowledge into a structured set of formal rules in several val ld ways. These representations may differ with respect to efficiency.

However, some of the knowled&e does have a well-understood structure, for example the knowledge regarding GET or FIND as discussed above. In general, the rules for single program statements like GET are similar to usage rules that might be found In a reference manu a 1. It Is the rules that control the next higher level of programming, the construction of program blocks, that are complex and not easily derived.

Such rules were further complicated by considerations of efficiency both for the generated programs and for the program generation process Itself.

As an example we Illustrate the two rules that control code generation for alternation. Alternation occurs In the generated program whenever the query specifies conditional processing. During program generation, the condition that Is to be tested In the generated program Is contained In a list, FORLIS, In disjunctive form. For example, the CCCGT A B)(GT B C)) ((LT A 26))) CA>B and B>D> or A<26. The two rules are: (NULL FORLIS)V 11 st means (CONJUNCT ACTION (CAR FORLIS) DUM)A (DISJUNCT ACTION (CDR FORLIS)) --> (DISJUNCT ACTION FORLIS) ((NULL CONJ)A(ACT ACTION)A(SETQ DUM O))V (SETQ REL (CAAR CONJ))A (SETQ ITMl CCADAR CONJ))A CSETQ ITM2 (CADDAR CONJ))A (DETVAL ITM2)A(DETVAL ITMl) A (TEST (LIST REL ITM1 ITM2))A (CONJUNCT ACTION (CDR CONJ) DUM) --> (CONJUNCT ACTION CONJ DUM)

Those readers who are programmers will agree that these rules bear little correspondence to their own programming knowledge, either viewed Introspectively, or as such knowledge might be represented In a programming text.

The first rule CDR's through FORLIS, each time picking off the CAR, which Is a conjunctive list of predicates. The CAR of FORLIS will be bound to CONJ In the second rule.

The second rule CDR's through CONJ until It becomes NULl, at which point the processing code can be generated (accomplished by Invoking the ACT rule, not shown here>.

Each time the second rule Is used, code Is generated to determine the values of the two Items In the test described by the CAR of CONJ. Then the test Itself Is Inserted In the generated program.

For the example above, the generated following form: of FORLIS given procedure has the (block to determine value of B) (block to determine value of A) IF A>B THEN BEGIN (block to determine value of C) IF B>C THEN BEGIN (block of conditional processing) END ELSE PROC2 END ELSE PROC3 PROC2: (and PROC3) BEGIN IF A<6 THEN BEGIN ENO (block of conditional processing) END

The Buch~nan-Luckham compiler takes special care with rules that may generate alternations. Unbound variables become Important, and It is for this reason that DUM Is Included In the second rule. For further details see <1,10,11>.

Tests are separated In the generated procedure to Increase runtime efficiency. In the example above, the value of C Is determined only If A>B. Since such a value determination may require a lot of processing, It Is best to avoid It If possible.

Impact of Representation on Efficiency

Since the content of the rules determines the decision tree that controls the search space, the choice of mappings mentioned above can have a dramatic Impact on the efficiency of the search for a program. If the use of a particular rule occurs far out In the branches of the tree, and If the rule Is a powerful discriminator, then It would be appropriate to consider an alternative rule structure that would permit earlier use of the rule In question.

It Is also Important to direct the Information Retrieval Program Generator as much as possible. Consider the FIND rule previously discussed. This rule states that FIND has the effect of making a record current. There are In fact four other rules describing statements that have the same effect. These rules all differ In the way In which they make records current: some use pointers, another utilizes sequential access, etc.

Since there are five ways of making a record current, Micro-Planner may try several Inappropriate rules to satisfy a CURRENT goal before the proper one Is attempted. This can be very expensive since an Inappropriate rule may not be discarded until a very large subtree has been evaluated.

Frequently, such searches can be eliminated because the programming context will determine which type of FIND Is needed. In the Iteration step of a loop, for example, we would not expect a direct FIND, rather we would expect a FIND for the next record on a list or the next record In sequence.

By changing the rules so that the system Is directed to a specific rule whenever possible, we were obviously able to avoid a lot of unnecessary searching.

It Is Important to note that the rules were correct without these specific directions. The way In which the rules were used required additional knowledge about the application so that the rules could be used efficiently.

For a particular set of programs that the system generated, It tried (on average) about 94 rules per program. Of these (on average) only 13 rules were Inappropriately tried, resulting In backtracking to use alternative rules.

Although we have no exact figures to compare with, the system was trying 10 to 20 times as many unnecessary rules prior to the addition of more specific direction. The difference Is multiplicative rather than additive because the sub-tree associated with a single Inappropriate rule may be quite large.

Conclyslon

As a user of A I technology, am somewhat disappointed that It was not sufficient to directly transfer my knowledge to the machine, In Itself a difficult task. It was also necessary to observe how that knowledge was being used by the machine so that I could change and augment the representation for more efficient use of the knowledge.

These problems were also encountered while building the Automatic Data Structure Designer. Another difficulty arose as well. As the Designer took shape It became apparent that my design knowledge contained many ad hoc techniques that were not easily captured In a set of general rules. This realization led me to develop the rules for the more direct, general purpose algorithm that Is embedded In the Designer.

Although the difficulties of transferring knowledge to the machine were somewhat frustrating, the process (and the machine as a mirror of myself) also led to new Insights Into the problem domain.

Acknowledgements

The assistance and encouragement of my thesis advisor, Jack R. Buchanan, Is gratefully acknowledged, as are the suggestions of one of the referees.

This research was supported In part by the Advanced Research Projects Agency of the Office of the Secretary of Defense under contract F44620-73-C-0074, and In part by the Office of Naval Research under contract N00014-75-C-0462. I am also Indebted to the William Larimer Mellon Fellowship, which provided personal funding during the course of this research.