Automated logical file design system with reduced data base redundancy

I claim:

1. A method for generating an integrated data base design structure for multiple applications on an interactive terminal computing system, comprising the steps of:

storing local views of data elements of each application of said multiple applications with each of said local views including first indication of forward association and second indication of backward associations between each of said data elements having associations therebetween, said first and second indications specifying whether each of said associations involve a single occurrence of the association, multiple occurrences of the association or a conditional occurrence of the association, and whether each of said data elements is unique;

sorting said indications into a first table of entries to form a list of associations;

removing all associations from said list of associations which have a similar key;

separating unique data elements from non-unique data elements in said list of associations;

calculating implied associations by scanning said list of associations to find any two association entries each of which has a single occurrence of the association and for which there is a common data element therebetween;

storing said implied association into a second table of entries to form an implied association list;

determining essential associations by scanning said list of associations for all single occurrence type associations and comparing each entry having a single occurrence type of association with each of the entries scanned in said implied associations list to determine if any entry in the implied association list corresponds to an entry in the list of associations and marking any entry in the list of associations for which there is a corresponding entry in the implied association list as nonessential and any entry in the list of associations for which there is no corresponding entry in the applied association list as essential; and

storing a graphic representation of said design structure by combining said first table of entries and said second table of entries to minimize data redundancy in the data base design structure.

2. A method according to claim 1, wherein said step of calculating further comprises the steps of scanning entries of said second table; and

comparing each of said entries of said second table of entries with each entry in said first table of entries to find any one-type association in the first table of entries which has a common data element with any one-type association in said second table of entries; and

adding each said further implied association into said second table of entries.

3. In a system for producing an associative file design through the use of a programmed digital computer, wherein said digital computer is programmed to generate an integrated data base design structure for a multi-application computing system from user-specified local views of data required for the various individual user applications of said computing system, wherein said local views are characterized as defined rules for classifying data per a given user, the combination comprising:

means for storing the local views of said individual user applications into said digital computer, with said local views further being characterized as having predefined associations between different data elements, an association being defined as an occurrence of one data element relative to another data element;

means for analyzing the associations in each of said local views to determine which of said associations are the same, including removing associations that are the same such that each association appears only once;

means for processing the remaining associations after all the same associations have been removed, to determine which of the data elements of the remaining associations are unique, wherein a data element is characterized as being unique if no other data element has a similar key;

means for deriving from first and second associations, each of said first and second associations having a common data element, an implied association having the uncommon data elements of said first and second associations;

means for determining which of said associations are essential or non-essential, wherein an implied association is characterized as non-essential, and a non-implied association is characterized as essential; and

means for storing said database design structure as a function of said associations, wherein said database design structure is determined by said essential associations.

4. The method as set forth in claim 1 wherein said step entering said local views of said user applications into said digital computer includes entering said local views into a table of entries to form a list of said predefined associations.

5. The method as set forth in claim 4 wherein said step of deriving an implied association includes entering the implied associations into a table of entries to form an implied association list.

6. The method as set forth in claim 5 wherein said step of deriving an implied association list includes the further steps of;

scanning said implied association to find any two association entries each of which involves a `1` type association and for which there is a common data element therebetween, such as

(A,B):L1=`1` and (B,C):L2=`1`,

where A, B and C are the data elements L1 and L2 are the association labels; and

entering the implied association (A,C):L1,L2=`1` derived therefrom into the implied association list table.

7. The method as set forth in claim 6 wherein said step of deriving an implied association includes the further steps of;

scanning the entries of said implied association list table determined from scanning the list of associations table, one entry at a time, and comparing each of said entries with each of the entries as scanned in the list of associations table such that any entry (W,Z):L3=`1` in the implied association list table for which there is an entry (Z,Q):L4=`1` in the list of associations table has a further implied association (W,Q):L3,L4=`1`; and

entering said further implied association into the implied association list table.

8. The method as set forth in claim 7 wherein the step of determining which of said associations are essential or nonessential includes the steps of;

scanning the list of associations table, one entry at a time, for all type `1` associations and comparing each of said entries having `1` associations with each of the entries as scanned in the implied association list table to determine if there is any entry in the implied association list table corresponding to an entry in the list of associations table; and

making any entry in the list of associations table for which there is a corresponding entry in the implied association list table as nonessential and any entry in the list of associations table for which there is no corresponding entry in the implied association list table as essential.

9. A method of producing an associative file design through the use of a programmed digital computer, wherein said digital computer is programmed to generate an integrated data base design structure for a multi-application computing system from user-specified local views of data, comprised of data elements, required for the various individual user applications of said computing system, wherein said local views are characterized as defined rules or classifying said data elements per a given user, said method comprising the steps of:

storing said local views of said individual user applications into said computer, with said local views further being characterized as having predefined associations between different data elements, said associations being defined as occurrences of one data element relative to another data element;

analyzing said associations in each of said local views to determine which of said associations are the same, including removing associations that are the same such that each association appears only once;

comparing the remaining associations after all said same associations have been removed, to determine which of the data elements of said remaining associations are unique, wherein a data element is characterized as being unique if no other data element has a similar key;

deriving from at least first and second associations, each of said first and second associations have a common data element, an implied association having the uncommon data element of said first and said second associations;

identifying said separating essential and nonessential associations wherein an implied association is characterized as nonessential, and a nonimplied association is characterized as essential; and

storing said database design structure as a function of said associations, wherein said database design structure is determined by said essential associations.

10. The method of claim 9 wherein said associations are further defined as three basic types of associations namely,

(a) a `1` association characterized as:

(A,B)=`1`

wherein;

each occurrence of data element A has a single associated occurrence of data element B;

(b) a `M` association characterized as:

(A,B)=`M`

wherein;

each occurrence of data element A may have multiple occurrences of data element B;

(c) a `C` association characterized as:

(A,B)=`C`

wherein;

not every occurrence of data element A has a single occurrence of data element B, but for those occurrences of data element A that do, each of these occurrences of data element A has only one occurrence of data element B.

11. The combination claimed in claim 3, wherein said associations are further defined as three basic types of associations namely,

(a) a `1` association characterized as:

(A,B)=`1`

wherein;

each occurrence of data element A has a single associated occurrence of data element B;

(b) a `M` association characterized as:

(A,B)=`M`

wherein;

each occurrence of data element A may have multiple occurrences of data element B;

(c) a `C` association characterized as:

(A,B)=`C`

wherein;

not every occurrence of data element A has a single occurrence of data element B, but for those occurrences of data element A that do, each of these occurrences of data element A has only one occurrence of data element B.

12. The combination claimed in claim 11 wherein the means for storing said local views of said user applications to said digital computer includes means for storing said indications to a first table of entries to form a list of said predefined associations.

13. The combination claimed in claim 12 wherein said means for deriving an implied association includes means for storing said implied associations to a second table of entries to form an implied association list.

14. The combination claimed in claim 13 wherein said means for deriving an implied association list includes:

means for scanning said implied association to fine any two association entries each of which involves a `1` type association and for which there is a common data element therebetween, such that

(A,B):L1=`1` and (B,C):L2=`1`

where A,B and C are the data elements and L1 and L2 are the association labels; and

means for storing the implied association (A,C):L1,L2=`1` derived therefrom into the implied association list table.

15. The combination claimed in claim 14 wherein said means for deriving an implied association includes:

means for scanning the entries of said implied association list table determined from scanning the list of associations table, one entry at a time, and comparing each of said entries with each of the entries as scanned in the list of associations table such that any entry (W,Z):L3=`1` in the implied association list table for which there is an entry (Z,Q):L4=`1` in the list of associations table has a further implied association (W,Q):L3,L4=`1`; and

means for storing said further implied association to the implied association list table.

16. The combination claimed in claim 15 wherein said means for determining which of said associations are essential or nonessential includes:

means for scanning the list of associations table, one entry at a time, for all type `1` associations and comparing each of said entries having `1` associations with each of the entries as scanned in the implied association list table to determine if there is any entry in the implied association list table corresponding to an entry in the list of associations table; and

means for marking any entry in the list of associations table for which there is a corresponding entry in the implied association list table as nonessential and any entry in the list of associations table for which there is no corresponding entry in the implied association list table as essential.

17. A method of producing an associative file design through the use of a programmed digital computer, wherein said digital computer is programmed to generate an integrated data base design structure for multiple applications on an interactive terminal computing system from user-specified local views of data, comprised of data elements, required for the various individual user application programs of said computing system, wherein said local views are characterized as defined rules for classifying said data elements per a given user, said method comprising the steps of:

storing the local views of each of said user application programs into said digital computer, with said local views further being characterized as having predefined associations between different data elements, said associations being defined as occurrences of one data element relative to another data element, with there being three types of associations, namely,

(a) a `1` or single association characterized as:

(A,B)=`1`

wherein;

each occurrence of data element A has a single associated occurrence of data element B;

(b) a `M` or multiple association characterized as:

(A,B)=`M`

wherein;

each occurrence of data element A may have multiple occurrences of data element B;

(c) a `C` or conditional association characterized as:

(A,B)=`C`

wherein;

not every occurrence of data element A has a single occurrence of data element B, but for those occurrences of data element A that do, each of these occurrences of data element A has only one occurrence of data sorting said local views into a first table of entries to form a list of said associations;

analyzing said associations in said list of associations to determine which of said associations are the same, including removing associations that are the same such that each association appears only once;

comparing the remaining associations after all the same associations have been removed, to determine which of the data elements of the remaining associations are unique, wherein a data element is characterized as being unique if no other data element has a similar key;

calculating any implied association which may be implied from any other associations by scanning said list of associations to find any two association entries each of which has a `1` type association, with said two associations having a common data element, with said implied association having the uncommon data elements of said two associations;

storing said implied associations into a second table of entries to form an implied association list;

identifying essential and non-essential associations by scanning said first table of entries and said second table of entries, with an implied association being characterized as non-essential, and a non-implied association being characterized as essential; and

storing said database design structure as a function of said associations, wherein said database design structure is determined.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a method and apparatus for designing an integrated data base for a general purpose digital computer system. More particularly, the present invention relates to a computer method and apparatus for automatically designing the logic of an integrated data base, such that the network file organization of the data base has a minimum of data redundancy.

DESCRIPTION OF THE PRIOR ART

Integrated data bases for computers are well-known in the art. Various techniques have been employed to design the logical structure of integrated data base systems. In the main, these techniques involve many man hours and manual steps to formulate the structure and synthesize the data base system. One of the major problems encountered in data base design is attempting to keep track of the myriad of data and the associations between data such that the logical structure designed is free from error, quickly accessible and exhibits a minimum of data redundancy. It is evident that the extent of data redundancy is directly related to the cost of operating the computer system.

Heretofore, the methods employed to design an integrated data base system have been cumbersome and ineffective. In addition, the prior art techniques utilized for this purpose were not formalized but rather varied from individual to individual in accordance with the particular system being designed. Automatic methods for producing graph structures for logical file design were unknown. Although methods for automatically producing an integrated data base file design have been unknown, many proposals have been made for the organization and structure of data base systems. Typical of the prior art that exists on data base systems may be found by reference to the proceedings of the second symposium on computer-centered data base systems, System Development Corp., Santa Monica, Calif., December 1965, Vol. 1, Report No. TN-24/100/00 (AS-625-417), pp. 3-10 of Section 2 in an article entitled "State-of-the-Art Survey of Data-Base systems" by G. H. Dobbs.

SUMMARY OF THE INVENTION

In accordance with the principles of the present invention, a method and apparatus if provided which automatically generates a graph structure for the logical file design of an integrated data base system. The data needed by each application program of the system is first specified with certain constructs and rules. These are characterized as the local data view or LVIEW. The local data views are automatically checked by the computer process to ensure that the constructs and rules are followed. The collection of all local data views is then processed by the computer to separate "keys" from "attributes" and determine the "implied" associations that exist among the data elements. Then the "essential" associations that exist among data elements are determined, and a graph structure indicative of the "essential" associations is produced which characterizes an integrated data base network with a minimum of data redundancy.

It is, therefore, an object of the present invention to provide a method and apparatus for automatically producing the design structure for an integrated data base.

It is a further object of the present invention to provide a method and apparatus for producing an integrated data base design structure with minimal data redundancy.

It is yet a further object of the present invention to provide a method and apparatus for automatically generating an integrated data base design structure with minimal data redundancy for use in multi-application general purpose digital computer systems.

It is yet still a further object of the present invention to provide a method and apparatus for efficiently producing, in a systematic, efficient and simplified manner, a network file organization for use in multi-application general purpose digital computing systems which file organization exhibits minimal data redundancy and which may be used, for example, as a canonical representation to measure the amount of redundancy in the actual implemented data base.

It is another object of the present invention to provide an improved method and apparatus for designing the logical structure of an integrated data base which logical structure is free from error and is quickly accessible.

It is yet another object of the present invention to provide an improved method and apparatus for designing and organizing data base structures for use in a multi-application digital computer system such that the data base structure exhibits a minimum of data redundancy whereby the cost of operating the system is significantly reduced.

It is yet still another object of the present invention to provide a method and apparatus for automatically producing graph structures for the logical file design of an integrated data base for use in multi-application digital computer systems.

It is yet still another further object of the present invention to provide a data base design tool that aids in obtaining a more efficient and consistent design, and helps reduce design cycle time.

It is also an object of the present invention to provide a data base design tool the output of which provides a visual criteria for breaking the totality of data into a convenient and natural division of parcels for a distributed data base system having minimal interconnections with other parcels.

It is a further object of the present invention to provide a data base design method and device which automatically organizes application data requirements into segments and hierarchies for use by the data base designer.

The foregoing and other objects, features and advantages will be apparent from the following more particular description of the preferred embodiments of the invention illustrated in the accompanying drawings. For purposes of illustration, the specification relates to the execution of implemented programs operating under IBM Operating System/370, Model 155 VS2 (Release 1.7). The terms used in the specification in describing the present invention will be known to those familiar with the internal design of said Operating System. However, the various terms used are sufficiently defined in the context of the embodiments so as to be understood by one familiar with the internal design of an operating system for any general purpose computer.

To aid in the description of the preferred embodiments, a PL/1 code listing of the associative file design program method is presented as Appendix A at the end of the specification. Throughout the description provided in the specification, cross-reference is made to code identified by line numbers in the listing.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1A shows a block diagram representation generally depicting the various steps carried out by the digital computer, in accordance with the principles of the present invention.

FIGS. 1B1, 1B2 and 1B3 depict in graphical form the three basic types of data associations recognized by the disclosed embodiments of the program process in accordance with the principles of the present invention.

FIG. 1C depicts a directed graph structure used in the description to define the terms and relationships of data, as implemented in accordance with the program process of the present invention.

FIGS. 2A and 2B depict flow charts representing a more detailed way in which the general step represented by Block 1 of the overall process of FIG. 1A may be carried out.

FIGS. 2B1 and 2B2 represent tables created by the flow chart process described with regard to FIGS. 2A and 2B.

FIGS. 3A, 3B and 3C depict flow charts representing a more detailed way in which the general step represented by Block 3 of the overall process of FIG. 1A may be carried out.

FIG. 3A1 represents a table utilized in the flow-charted routine shown in FIG. 3A.

FIGS. 4A and 4B depict flow charts representing a more detailed way in which the general step represented by Block 5 of the overall process of FIG. 1A may be carried out.

FIGS. 4A1 and 4A2 represent tables used in the description of the flow charted process depicted in FIG. 4A.

FIG. 4C depicts a flow chart which is a further more detailed way in which the step represented by Block 121 of the flow charted routine of FIG. 4B may be carried out.

FIG. 4D depicts a flow chart representing a further more detailed way in which the step represented by Block 123 of the flow-charted routine of FIG. 4B may be carried out.

FIG. 5 depicts a flow chart representing a more detailed way in which the general step represented by Block 7 of the overall process of FIG. 1A may be carried out.

FIGS. 6A and 6B depict flow charts representing a detailed matter in which the data processed in accordance with Blocks 1-7 in FIG. 1A is further processed in preparation of the generation of a graph structure, in accordance with the step represented by Block 9 in FIG. 1A.

FIG. 7 depicts a flow chart representing a more detailed way in which the general step represented by Block 9 of the overall process of FIG. 1A may be carried out.

FIG. 8 depicts a table representation utilized in the description of the flow-charted routine shown in FIG. 7.

FIG. 9 shows a chart setting forth an example of implied associations according to the method of the present invention.

DETAILED DESCRIPTION

With regard to FIG. 1A, there is depicted a block diagram generally representing the overall process to be carried out by the general purpose digital computer, in accordance with the principles of the present invention. As is understood by those skilled in the art, any of a variety of general purpose digital computers may be programmed to carry out the several steps depicted in FIG. 1A. Typically, an IBM System/370 CPU utilizing, for example, OS/VS or DOS/VS may be used. In this regard, a System/370 Model 145 may be used with OS/VS and a Model 115 with DOS/VS. It is clear that other types and models of CPUs may be readily employed, in this regard.

As hereinabove indicated, for purposes of illustration the description of the various flow-chart routines is supported by cross-references to the detailed code set forth in a PL/1 program implementation of the present invention, as set forth in Appendix A. As previously indicated, the specific PL/1 program implementation appearing in Appendix A operates under an IBM Operating System/370, Model 155 VS2 (Release 1.7). As is understood by those skilled in the art, however, a particular program implementation of the various routines set forth in the drawings may be carried out through utilization of any of a variety of programming languages, such as Assembler Language, FORTRAN, etc.

Before describing the various steps set forth in the overall process depicted in block form in FIG. 1A, it is considered worthwhile to describe, by way of background, the nature of an integrated data base and the characteristics thereof. An integrated data base is generally described as network file organization with minimal data redundancy. With the advent of the sophisticated general purpose digital computer (computer), multiple applications of the computer to maximize its utilization was inevitable. Typically, in this regard, applications of the computer are extended in a piecewise manner, such that each application program may have its own data base, or at least its "own" view of the data base utilized in the system.

Basically, the integrated data base approach is a departure from the traditional batch processing approach. Prior to the integrated data base approach, each application area would comprise a series of runs, and each run would involve a batch of similar transactions. Each batch run would require data files structured for efficient processing; hence a considerable amount of processing time would be expended in restructuring data files between batch runs. Such restructuring would be accomplished by a combination of massive sorts and processing routines. In this sense, each batch run would require separation of data into distinctly separate files, even though there may be a large amount of common data between these files.

The integrated data base approach involves setting up a network structure of data and, from this network, generating the local data structure needed by each application. With the integrated data base approach, a clean separation of data into distinct files is deliberately avoided so as to reduce the amount of data redundancy. The network structure of an integrated data base permits each application program to operate with its "own" view, i.e., its local or logical view of the data. With each application retaining its "own" view, i.e., its logical view of the data, the application code will continue to operate regardless of what changes are made to the data files. Thus, with an integrated data base, a data name is stored only once, and all applications share this single, nonredundant data.

In an integrated data base, data occurs on at least three distinct levels:

1. external--The external level is data as presented on output reports, displays, etc. and therefore corresponds to the structure of data as it appears to a user at a terminal or a user reading a report printed by the system.

2. logical or LVIEW--The LVIEW is the data structure required to support a particular application and it is used to generate the external view.

3. associative model or view--The associative view is the data structure required by the system to generate the multiple logical or local views used by the various application programs. The associative model is synonymous with the internal file network or integrated data base structure.

The program process in accordance with the principles of the present invention operates upon the various LVIEWS of a multi-application computer system, and from the information contained within these LVIEWS themselves, acts to produce an integrated data base structure supportive of all the LVIEWS. In particular, the resultant integrated data base structure exhibits minimal data redundancy by reducing duplicate information common among the various LVIEWS, and does so in a manner such that each LVIEW appears to have its own data base or view.

Accordingly, a data base may be looked upon as comprising a mass of data occurrences with special structure or arrangement. The program process in accordance with the principles of the present invention is designed to automatically specify and arrange this special structure with minimal data redundancy. In this regard, a "data occurrence" may be defined as a specific instance of data from a group of data. A "data element" is the smallest, nondivisible data reference used. A "data element name" is the symbolic reference to all occurrences of that data element, and a "data element occurrence" is a specific value. For example, the data element name "ship date" may have a data element occurrence of "2 April 1974."

In this regard, it should be noted that there are two types of data elements recognized in accordance with the program process of the present invention. In particular, "keys" and "attributes" are recognized as having a specific meaning. A key is a data element whose occurrences are unique, whereas an attribute has value which is not necessarily unique. For example, if personnel data is being stored, the social security number could readily be made the "key" while age, weight, salary, etc. would most likely be "attributes."

A "segment," as defined herein, may be characterized as a group of data elements. Each segment occurrence is uniquely identified by a key. A key that consists of more than one data element is called a compound key. In this regard, if A, B and C form a compound key, then one may write (A*B*C).

As is evident, different segments or segment sets may be associated with each other. For example, a given segment set with NAME-A and whose key is KEY-A can be associated with another segment set with NAME-B and whose key is KEY-B. The collection of association instances between A and B may be defined as an association set and is minimally defined by KEY-A and KEY-B. As an example of a simple illustration, one may consider departments and employees. Each department can be uniquely represented by a segment whose KEY-A is department number, and each employee, can be uniquely represented by a segment whose KEY-B is EMPLOYEE#. Each department is associated with certain employess, hence there is an association set containing the relationships of DEPT# to EMPLOYEE#. Each DEPT# has multiple EMPLOYEE#S associated with it. Notationally, the association may be written as (A,B) or DEPT#, EMPLOYEE#).

An association is a "from"-"to" relationship between two data elements; that is, one element may be characterized as the FROM element while the other element may be characterized as the TO element. Thus, an orientation is established between two elements by the FROM and TO designation. The FROM-TO relationship may be specified, as hereinabove indicated with respect to the EMPLOYEE#-DEPT# relationship, as (A,B): LABEL. The data elements A and B are the FROM and TO portions, respectively, (establishing direction) while the LABEL is an optional name that may be assigned to that association. In this regard, if A and B are KEY-A and KEY-B having more than one relationship, then the LABEL is used to distinguish the difference. Thus, it is possible to have, for example,:

(Sales Order, Division): SELL=`1`

(Sales Order, Division): MFG=`1`

(Sales Order, Division): SHIP=`1`

The associative file or data base design process in accordance with the present embodiments recognizes three basic types of associations between data elements. It should be appreciated that when reference is made to associations between data elements, either key or attribute, the permutations and combinations are of enormous variety. The three basic types of associations may be enumerated as the `1` association, the `M` association and the `C` or conditional association. Given a data element name A and a data element name B, the three associations can be distinguished by writing: ##EQU1##

The three basic types of associations may be more graphically depicted with reference to FIGS. 1B. FIG. 1B1 shows examples of `1` association between A and B. In such an association, each occurrence of the data elemen