Automated logical file design system with reduced data base redundancy

• US 4,468,732 A
• Filed: 04/28/1980
• Issued: 08/28/1984
• Est. Priority Date: 12/31/1975
• Status: Expired due to Term

• Current Assignee: Forschungszentrum Jã¼Lich GmbH (Bundesrepublik Deutschland)
• Original Assignee: International Business Machines Corporation
• Inventors: Raver, Norman
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Williams, Jr., Archie E.
• Application Number:
  US06/144,116
• Time in Patent Office: 1,583 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An associative file design method and apparatus are used for automatically generating an integrated data base design structure, with minimal data redundancy, for use in multi-application general purpose digital computing systems. The integrated data base design structure is automatically produced by a programmed digital computer in the form of a report or graph structure which permits the data base designer to design a data base system with minimal data redundancy. The data needed by each application program, i.e., the local data view, is specified with certain constructs. The local data views are checked to ensure that specified rules are followed. The collection of local views is processed on a general purpose digital computer to separate "keys" from "attributes," then to determine "implied" and "essential" associations, and finally to generate the integrated data base graph structure.

Claims

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.

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

space="preserve" listing-type="equation">(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.

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.

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:

space="preserve" listing-type="equation">(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;

space="preserve" listing-type="equation">(A,B)=`M`

wherein;

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

(c) a `C` association characterized as;

space="preserve" listing-type="equation">(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

space="preserve" listing-type="equation">(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.

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:

space="preserve" listing-type="equation">(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;

space="preserve" listing-type="equation">(A,B)=`M`

wherein;

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

(c) a `C` association characterized as;

space="preserve" listing-type="equation">(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.

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;

space="preserve" listing-type="equation">(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;

space="preserve" listing-type="equation">(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;

space="preserve" listing-type="equation">(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.