Multi-model database management system engine for databases having complex data models

• US 5,611,076 A
• Filed: 09/21/1994
• Issued: 03/11/1997
• Est. Priority Date: 09/21/1994
• Status: Expired due to Fees

• Current Assignee: Micro Data Base Systems, Inc.
• Original Assignee: Micro Data Base Systems, Inc.
• Inventors: Logan, Kim M., Reid, Jon D., Durflinger, Kevin
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/309,909
• Time in Patent Office: 902 Days
• Field of Search: 395/600, 364/283.2, 364/974.2, 364/974.3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A multi-model database management system (DBMS) presents to its users a variety of logical models, or views of stored data, using industry-standard interfaces, while the physical storage of data is managed in a manner that closely follows the data model. Databases are built from sets of records using the entity-relationship data model. Space is reserved in each owner record for a set pointer pointing to either a member record or a Dynamic Pointer Array (DPA) structure that relates the owner record to member records. The DPA itself contains set pointers to all of the related member records. Each member record, in turn, has a set pointer pointing back to a particular owner record, or, in certain instances, to another DPA. In such cases, the DPA contains set pointers pointing to all of the related owner records. The DBMS supports a variety of logical models including the relational model, and further supports a plurality of industry-standard Application Program Interfaces using SQL query access language.

Claims

1. A computer database management system for storing, retrieving and modifying data objects stored in a database, said database management system comprising:

a number of application processes, each of said application processes including;

a user accessible external application; and

one of a multiplicity of application program interfaces for translating complex input data from said external application into a predefined intermediate data format and for translating said predefined intermediate data format into complex output data for said external application;

a schema coupled to said number of application processes, said schema defining a number of predetermined data models for translating said predefined intermediate data format into a predetermined data model format and for translating said predetermined data model format into said intermediate data format; and

a database server including storage means for storing and retrieving the data objects in and from the database, said server storing and retrieving the data objects according to said predetermined data model format,

said predetermined data model format including;

a plurality of owner records each having associated therewith at least some data;

a plurality of member records each having associated therewith at least some data, wherein set relationships exist between certain ones of said owner records and said member records, each of said owner records of any of said set relationships being linked directly to a corresponding member record when only said corresponding member record exists in said set relationship, and each of said member records of any of said set relationships being linked directly to a corresponding owner record when only said corresponding owner record exists in said set relationship; and

a plurality of dynamic pointer arrays for linking each of said member records of any of said set relationships to a corresponding owner record when a multiplicity of member records exist in said set relationship, and for linking each of said owner records of any of said set relationships to a corresponding member record when a multiplicity of owner records exist in said set relationship.

2. The system of claim 1 wherein said data objects include complex data.

3. The system of claim 2 wherein said set relationships include at least one of one-to-one, one-to-many, many-to-many, one-to-many recursive, N-ary, many-to-many recursive and N-ary many-to-many recursive.

4. The system of claim 2 wherein said schema includes:

a logical data model layer for translating said predefined intermediate data format into a logical data model format and for translating said logical data model format into said predefined intermediate data format; and

a conceptual data model layer for translating said logical data format into said predetermined data format and for translating said predetermined data format into said logical data format, wherein

said conceptual data model layer includes the entity-relationship data model.

5. The system of claim 4 wherein said user accessible external application includes at least one of a programming language and a query language.

6. The system of claim 5 wherein said multiplicity of application program interfaces (APIs) includes the SQL Access Group Call Level Interface and the Open DataBase Connectivity API.

7. The system of claim 5 wherein said query language includes SQL and said logical data model layer includes the relational logical data model.

8. The system of claim 7 wherein said logical data model layer further includes an Object oriented data model and the CODASYL Network data model.

9. The system of claim 7 wherein said logical data model layer includes an SQL Access Manager module to automatically perform upstream and downstream navigation of said set relationships to store and retrieve data in and from said storage means.

10. The system of claim 9 wherein said logical data model layer further includes a table definition file to manage the translation from said relational logical data model to said entity-relationship data model.

11. The system of claim 1 wherein said data associated with said plurality of owner and member records includes at least one of a number of principal fragments contained within said records and a number of tributary fragment pointers pointing to tributary fragments contained elsewhere within said storage means.

12. The system of claim 11 wherein each of said owner records further includes a number of set pointers for linking said owner record of any of said set relationships to one of said corresponding member record and one of said plurality of dynamic pointer arrays.

13. The system of claim 12 wherein each of said member records further includes a number of set pointers for linking said member record of any of said set relationships to one of said corresponding owner record and one of said plurality of dynamic pointer arrays.

14. The system of claim 13 wherein each of said owner and member records further includes an object position header portion for identifying the location of said record within said storage means.

15. A computer database management system for storing, retrieving and modifying data objects stored in a database, said system coupled to a number of application processes each having a user accessible external application and one of a multiplicity of application program interfaces for translating input data from said external application into a predefined intermediate data format and for translating said predefined intermediate data format into output data for said external application;

said database management system comprising;

a schema defining a number of predetermined data models for translating said predefined intermediate data format into a predetermined data model format and for translating said predetermined data model format into said intermediate data format; and

a database server including storage means for storing and retrieving the data objects in and from the database, said server storing and retrieving the data objects according to said predetermined data model format,

said predetermined data model format including;

a plurality of owner records each having associated therewith at least some data and a number of first set pointers;

a plurality of member records each having associated therewith at least some data and a number of second set pointers; and

a plurality of dynamic pointer arrays (DPAs) each having associated therewith a multiplicity of third set pointers;

wherein set relationships exist between certain ones of said owner records and said member records, each of said first set pointers corresponding to a distinct set relationship that its associated owner record participates in and each of said second set pointers corresponding to a distinct set relationship that its associated member record participates in, and further wherein

each of said first set pointers points to one of a single member record and a distinct one of said plurality of DPAs, each of said multiplicity of third set pointers of said distinct DPA pointing to one of said member records related to the owner record associated with said first set pointer, and

each of said second set pointers points to one of a single owner record and another distinct one of said plurality of DPAs, each of said multiplicity of third set pointers of said another distinct DPA pointing to one of said owner records related to the member record associated with said second set pointer.

16. The system of claim 15 wherein said data objects include complex data.

17. The system of claim 16 wherein said schema includes:

a logical data model layer for translating said predefined intermediate data format into a logical data model format and for translating said logical data model format into said predefined intermediate data format; and

a conceptual data model layer for translating said logical data format into said predetermined data format and for translating said predetermined data format into said logical data format, wherein

said conceptual data model layer includes the entity-relationship data model.

18. The system of claim 17 wherein said user accessible external application includes at least one of a programming language and a query language.

19. The system of claim 18 wherein each of said plurality of DPAs includes a multiplicity of entries corresponding to said multiplicity of third set pointers, each of said entries including an index element and one of said multiplicity of third set pointers.

20. The system of claim 19 wherein each of said plurality of DPAs further includes a header portion having at least an upper pointer, wherein said upper pointer points to one of said owner record having a first set pointer pointing to said DPA and said member record having a second set pointer pointing to said DPA.

21. The system of claim 20 wherein said DPA header portion further includes a used portion, wherein said used portion indicates the total number of currently used entries in said DPA.

22. The system of claim 21 wherein said DPA header portion further includes a prior pointer and a next pointer, wherein said prior pointer points to a previous DPA and said next pointer points to a following DPA, whereby some of said plurality of DPAs may be laterally chained together.

23. The system of claim 22 wherein one of said first and second set pointers corresponding to an owner and member record respectively points to the first DPA in said chain, and said upper pointers of said DPA in said chain point to the record corresponding to said one of said first and second set pointers.

24. The system of claim 23 wherein said prior pointer of said first DPA in said chain points to the last DPA in said chain and said next pointer of said last DPA in said chain points to said first DPA in said chain.

25. The system of claim 24 wherein said third set pointers of all of said DPAs in said chain point to the other of said owner record and said member record.

26. The system of claim 22 wherein said DPA header portion further includes a dpabit portion, wherein said dpabit portion indicates a type of said DPA, whereby said DPA types may be formed into a multi-level hierarchy.

27. The system of claim 26 wherein said DPA types include a TOPDPA, MIDDPA and LOWDPA, said TOPDPA indicating a single DPA in the top level of said hierarchy, said MIDDPA indicating any of a number of DPAs in any of a number of middle level chains of said hierarchy, and said LOWDPA indicating any of a number of DPAs in the lowest level chain of said hierarchy.

28. The system of claim 27 wherein one of said first and second set pointers corresponding to an owner and member record respectively points to said TOPDPA and said upper pointer of said TOPDPA points back to the record corresponding to said one of said first and second set pointers.

29. The system of claim 28 wherein said third set pointers of said TOPDPA point to said MIDDPAs of a first middle level chain of said hierarchy, said third set pointers of said MIDDPAs of a last middle level chain of said hierarchy pointing to said LOWDPAs of said lowest level chain of said hierarchy, there being a number of middle level chains of said MIDDPAs in said hierarchy between said first middle level and said last middle level, said third set pointers of said MIDDPAs of any of said middle level chains pointing to the MIDDPAs of the next lower level.

30. The system of claim 29 wherein said third set pointers of all of said LOWDPAs in said lowest level chain point to the other of said owner record and said member record.

31. The system of claim 30 wherein said prior pointer of said first LOWDPA in said lowest level chain and said next pointer of the last LOWDPA in said lowest level chain point to said TOPDPA, and said upper pointer of each of said LOWDPA points to said MIDDPA of said last middle level chain of said hierarchy having a third set pointer pointing to said LOWDPA.

32. The system of claim 31 wherein said upper pointer of each of said MIDDPA points to said MIDDPA of the previous middle level chain of said hierarchy having a third set pointer pointing to said MIDDPA.

33. The system of claim 32 wherein said upper pointer of each of said MIDDPA in said first middle level of said hierarchy points to said TOPDPA.

34. The system of claim 33 wherein said next pointer of said TOPDPA points to said first LOWDPA in said lower level chain and said prior pointer of said TOPDPA points to said last LOWDPA in said lower level chain.

35. The system of claim 34 wherein said dpabit portion of said first and last DPA in any of said levels is further identified with FSTDPA and LSTDPA indicators respectively, except when a sole DPA occupies any of said levels wherein said dpabit portion of said sole DPA is further identified with both FSTDPA and LSTDPA indicators.

36. The system of claim 27 wherein said number of middle level chains of said hierarchy is zero.

37. The system of claim 36 wherein one of said first and second set pointers corresponding to an owner and member record respectively points to said TOPDPA and said upper pointer of said TOPDPA points back to the record corresponding to said one of said first and second set pointers.

38. The system of claim 37 wherein said third set pointers of said TOPDPA point to said LOWDPAs of said lowest level chain of said hierarchy.

39. The system of claim 38 wherein said third set pointers of all of said LOWDPAs in said lowest level chain point to the other of said owner record and said member record.

40. The system of claim 39 wherein said prior pointer of said first LOWDPA in said lowest level chain and said next pointer of the last LOWDPA in said lowest level chain point to said TOPDPA, and said upper pointer of each of said LOWDPA points to said TOPDPA.

41. The system of claim 40 wherein said next pointer of said TOPDPA points to said first LOWDPA in said lower level chain and said prior pointer of said TOPDPA points to said last LOWDPA in said lower level chain.

42. The system of claim 41 wherein said dpabit portion of said first and last DPA in any of said levels is further identified with FSTDPA and LSTDPA indicators respectively, except when a sole DPA occupies any of said levels wherein said dpabit portion of said sole DPA is further identified with both FSTDPA and LSTDPA indicators.

43. The system of claim 16 wherein said set relationships include at least one of one-to-one, one-to-many, many-to-many, one-to-many recursive, N-ary, many-to-many recursive and N-ary many-to-many recursive.

44. The system of claim 15 wherein said data associated with said plurality of owner and member records includes at least one of a number of principal fragments contained within said records and a number of tributary fragment pointers pointing to tributary fragments contained elsewhere within said storage means.

45. The system of claim 44 wherein each of said owner records further includes a number of set pointers for linking said owner record of any of said set relationships to one of said corresponding member record and one of said plurality of pointer arrays.

46. The system of claim 45 wherein each of said member records further includes a number of set pointers for linking said member record of any of said set relationships to one of said corresponding owner record and one of said plurality of pointer arrays.

47. The system of claim 46 wherein each of said owner and member records further includes a header portion for identifying the location of said record within said storage means.

48. A method of storing, retrieving and manipulating data objects in a computer system having storage means, said computer system being coupled to a number of application processes each having a user accessible external application and one of a multiplicity of application program interfaces for translating input data from said external application into a predefined intermediate data format and for translating said predefined intermediate data format into output data for said external application;

said method comprising the steps of;

(1) translating said predefined intermediate data format into an entity-relationship model format;

(2) storing entities of said entity-relationship model format in said storage means;

(3) pointing a first set pointer for each relationship in which one of said entities participates in to another entity if said one of said entities is related solely to said another entity;

(4) otherwise pointing said first set pointer for each relationship in which said one of said entities participates in to a dynamic pointer array (DPA) and performing steps (5)-(6);

(5) pointing a second set pointer from said DPA to every entity related to said one of said entities via said first set pointer;

(6) pointing a third set pointer from each of said related entities back to said one of said entities if said one of said entities is solely related to each of said related entities;

(7) otherwise pointing a third set pointer from each of said related entities to a distinct DPA corresponding to a separate relationship and performing step (8);

(8) pointing a fourth set pointer from each of said distinct DPAs to every entity related to said related entities;

(9) performing steps (3)-(8) until each of said entity-relationships is associated with a pointer pointing to all related entities; and

(10) translating said entity-relationship model format into said predefined intermediate data format.

49. The method of claim 48 wherein the step (2) includes:

translating said predefined intermediate data format into one of a number of logical data formats; and

translating said number of logical data formats into said entity-relationship format.

50. The method of claim 49 wherein said number of logical data formats includes at least one of the relational logical data model and an SQL Access Manager module to automatically perform upstream and downstream navigation of said entity-relationships to store and retrieve data in and from said storage means.

51. The method of claim 49 wherein the step (10) includes:

translating said entity-relationship format into said number of logical data formats; and

translating said number of logical data formats into said predefined intermediate data format.

52. The method of claim 51 wherein said data objects include data records having complex data associated therewith.