Method of integrating software application programs using an attributive data model database

• US 4,864,497 A
• Filed: 04/13/1988
• Issued: 09/05/1989
• Est. Priority Date: 04/13/1988
• Status: Expired due to Term

• Current Assignee: Compaq Information Technologies Group LP (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Nixon, David M., Van Horn, Earl C., Lowry, Edward S.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US07/181,095
• Time in Patent Office: 510 Days
• Field of Search: 364/200, 364/300, 364/900
• US Class Current: 1/1
• CPC Class Codes: G06F 16/212 with details for data modelling support
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A common data structure for access by several application programs is created from a single primitive data element or attribute data object. The attribute data objects can be extracted from node data and node data descriptors in the application program'"'"'s databases. The attribute data objects are arranged in an attribute file in accordance with certain rules which impose a hierarchical organization upon the attribute data objects. Nonhierarchical relationships may also be used to represent the node data descriptors. The simplicity of the attribute data objects and their lack of limitations make them well suited for use with a wide variety of application programs'"'"' databases.

Claims

1. A method for creating a data structure for access by a plurality of application programs, said application programs being executed by a data processor which also creates said data structure in a memory coupled to the data processor, said data structure being created from application data originating in said application programs and including a plurality of node data and node data descriptors, and said method comprising the steps, executed by said data processor, of:

(a) creating a different one of a plurality of attribute data objects for each of said node data;

(b) organizing said attribute data objects hierarchically according to a being-held relationship by choosing from said plurality of attribute data objects for each of said attribute data objects, a holder data object such that a hierarchical being-held relationship exists between each attribute data object and a single holder data object;

(c) establishing non-hierarchical relationships for selected ones of said attribute data objects created from node data associated with at least one of said node data descriptors by choosing, from said attribute data objects, referent data objects for said selected attribute data objects such that the chosen referent data object reflects a node data descriptor of the node data for which a corresponding selected attribute data object was created, said selected attribute data objects being called relation data objects and the attribute data objects without referent data objects being called element data objects;

(d) creating an apex data object with which at least one of said attribute data objects has a being-held relationship, said apex data object having no being-held relationship with any of said attribute data objects;

(e) creating an attribute file for said attribute data objects;

(f) entering each of said attribute data objects into said attribute file;

(g) entering holding pointers for each of said attribute data objects, the holding pointer of each attribute data object indicating the one of said attribute data objects having a being-held relationship with that attribute data object; and

(h) entering referent pointers into said attribute file, said referent pointers reflecting said non-hierarchical relationships between said attribute data objects.

2. The method according to claim 1 wherein said attribute file includes an object block for each of said attribute data objects, and wherein said step of entering said attribute data objects into said attribute file includes the substeps of

creating an object header block for each different attribute data object;

and

entering into that object header block information about that object block.

3. The method according to claim 2, wherein the step of entering holding pointers into said attribute file includes the substep of

entering into each of said object blocks the holding pointer for the attribute data object corresponding to that object block, the holding pointer identifying the location in said attribute file of the object block of the attribute data object with which that attribute data object has a being-held relationship.

4. The method according to claim 2, wherein selected sets of said object header blocks are linked and wherein the method further comprise the substep of

entering linkage pointers into each said object header blocks in said selected sets.

5. The method according to claim 2, wherein selected ones of said object blocks also include held object sub-blocks and wherein the method further comprises the substep of

placing into said held object sub-blocks of each of said selected object blocks being-held pointers to object blocks for attribute data objects having a being-held relationship with the attribute data object for that selected object block.

6. The method according to claim 2, wherein selected ones of each of said object blocks for relation data objects include relation sub-blocks and wherein the step of entering referent pointers into said attribute file includes the substep of entering into said relation sub-blocks for each relation data object one of said referent pointers to the referent attribute data object for that relation data object.

7. The method according to claim 6, wherein the object blocks for certain of the relation data objects includes a plural relation sub-block identifying a plurality of referent pointers, and for said certain referent data objects, the sub-step of entering referent pointers further includes the sub-step of entering a pointer to one of said plural relation sub-blocks into the relation sub-block for the certain relation data objects.

8. The method according to claim 7, wherein the object block for said certain relation data objects includes a plural relation header block, and wherein the method further includes the sub-steps for each of said certain relation data objects, of

creating a valid plural relation sub-block for each of said referent attribute data objects for that relation data object, and

placing a indicator into the plural relation header block that the created plural relation sub-block is valid.

9. The method according to claim 8, further including the sub-step of

linking the plural relation header blocks for each referent data object.

10. The method according to claim 1 further comprising the steps of:

identifying each of said attribute data objects as one of a plurality of object types;

specifying an identifier for each of said object types;

creating a dictionary file containing a storage area for each of said object types for holding information associated with that object type; and

entering into said storage areas for each object type the specified identifier for that object type and the information associated with that said object type, said associated information, including a name pointer between that object type and the identifier specified for that object type.

11. The method according to claim 10 wherein the step of entering identifiers and associated information into storage areas includes the step of entering into each of said storage areas instance pointers identifying in said attribute file those attribute data objects having the object type associated with that storage area for which all of the attribute data objects have a being-held relationship with the same attribute data object.

12. The method according to claim 10 wherein said storage areas of said dictionary file include an object type block for each of said object types, and wherein the method includes the step of placing into each said object type blocks linkage pointers to effect an order of said object blocks.

13. The method of claim 12 further including the step of placing into each said object type blocks an indicator of whether attribute data objects of that type are ordered.

14. The method according to claim 10, further comprising the steps of:

(a) creating a first file for said apex data object; and

(b) entering holding pointers into said first file for said apex data object, said holding pointers identifying said attribute data objects having a being-held relationship with said apex data object.

16. The method according to claim 1 further comprising the steps of:

(a) assigning to certain ones of said attribute data objects unique key values for allowing quick access to said certain ones of said attribute data objects in said attribute file,

(b) creating leaf blocks each corresponding to a different set of said key values such that each said key value is in only one one set,

(c) entering, into each of said leaf blocks, pointers to the locations in said attribute file of each of the attribute data objects having one of the assigned set of key values corresonding to that leaf block, and

(d) organizing said leaf blocks according to said sets of key values to provide expedited determination of the leaf block corresponding to each of said set of key values to obtain the location of a desired attribute data object, the assigned key value of which corresponds to one of said set of key values for that leaf block.

17. The method according to claim 16 wherein said step of organizing said index blocks includes the substep of ordering said index blocks into at least one tree structure.

18. The method according to claim 17 wherein the substep of ordering said index blocks into a tree structure includes the substeps of

(a) creating a root block for said tree structure to provide an entry into said tree structure,

(b) creating a plurality of branch blocks, each corresponding to a different nonoverlapping group of said sets of key values,

(c) organizing said branch blocks to provide a unique pathway through said nonoverlapping groups of key values for each of said sets of key values, and

(d) organizing said leaf blocks and said branch blocks such that each of said unique pathways leads to the leaf block corresponding to the set of key values for which that pathway was provided, the set of key values including the assigned key value for the desired attribute data object.

19. The method according to claim 18 further including the step of building an index directory block in said attribute file identifying, for a specified one of said certain attribute data objects, the tree structure containing a pathway to the index block for the key value associated with the specified one of said certain attribute data objects.

20. The method according to claim 10, wherein the step of entering said holder pointer into said attribute data file comprises the substeps of:

determining the object type of each attribute data object;

allocating, in accordance with the object type of each element data object, an attribute file area in said attribute file for that element data object and for said holding pointers;

deriving an object pointer to each of said attribute file areas containing one of said attribute data objects;

providing, as said holding pointers to each holder data object, said object pointers for at least one of said element data objects having a being-held relationship with that holder data object; and

providing, as a holder pointer for each attribute data object in said attribute area for that attribute data object, said object pointer to the one of said attribute file areas containing said holder data object of that element data object.

21. The method according to claim 20, wherein the step of entering said holding pointer into said attribute data file further comprises the substep of

linking selected sets of said attribute data objects which are of the same object type by including, in said attribute file area for each of said attribute data objects which are of the same object type, at least one of said object pointers for one of said attribute data objects of the same type as that attribute data object.

22. The method according to claim 21, wherein the step of linking selected sets of said attribute data objects includes the substep of

providing as a first object pointer a pointer to a first one in each of said sets of attribute data objects.

23. The method according to claim 22, wherein the step of linking selected sets of attribute data objects also includes the substep of

providing a second object pointer a pointer to a last one in each of said sets of attribute data objects.

24. The method according to claim 23, wherein said sets of attribute data objects include only element data objects.

25. The method according to claim 20, wherein the step of entering said holder pointers into said attribute data file further comprises the substep of

linking selected sets of said attribute data objects having said being-held relationship with the same holder data object by including, in said attribute file area for each of said attribute data objects having the same holder data object, at least one of said object pointers for one of said attribute data objects having the same said holder data object as that attribute data object.

26. The method according to claim 25, wherein the step of linking selected sets of said attribute data objects includes the substep of

providing as a first object pointer a pointer to a first one in each of said sets of attribute data objects.

27. The method according to claim 26, wherein the step of linking selected sets of attribute data objects also includes the substep of

providing as a second object pointer a pointer to a last one in each of said sets of attribute data objects.

28. The method according to claim 27, wherein said sets of attribute data objects include only element data objects.

29. The method according to claim 20 wherein the step of entering referent pointer into said attribute file further comprises the substeps of:

determining, for each of first ones of said relation data object having a being-held relationship with one of a first set of said element data objects, whether the referent attribute data object for that relation data object is to be specified in an attribute file area for that element data object;

choosing as the referent pointer for each said elements data objects in said first set, the object pointer of the referent attribute data object for the relation data object having a being-held relationship with that element data object entering, for each of the first set of element data objects for which the referent attribute data object for first relation data object is to be specified in the attribute file area of that element data object, that chosen referent pointer into the attribute file area for that element data object;

allocating in the attribute file area for each of said first set of element data object for which one of said relation data objects has a being-held relationship, a referent data object area in the attribute file area for that element data object when the referent attribute data object of that relation attribute object is not to be specified in the attribute file area of that attribute data object; and

providing, in the referent data object area of that element data object, the object pointer of said chosen referent attribute data object as the referent pointer for that relation data object.

15. The method according to 14 wherein said first file is said dictionary file.

30. In a data processing system including at least one central processor executing a plurality of application programs and also including a memory containing a data structure common to said application programs, said common data structure containing a plurality of attribute data objects each having hierarchical being-held relationships with a single other one of said attribute data objects or with an apex, wherein selected ones of said attribute data objects have non-hierarchical relationships, and wherein each of said attribute data objects has an associated memory area including pointers to memory areas for other ones of said attribute data object which have said being-held relationship with that attribute data object, a method for adding a desired one of said attribute data objects to said data structure comprising the steps, executed by said central processor, of:

creating a memory area for said desired attribute data object;

locating, as a holder attribute data object, the one of said attribute data objects with which said desired attribute data object has a being-held relationship;

adding in the memory area for said holder attribute data object, a pointer to the memory area of said desired attribute data object; and

linking said desired attribute data object with other ones of said attribute data objects having a being-held relationship with said holder attribute data object.

31. In a data processing system including at least one central processor executing a plurality of application programs and also including a memory containing a data structure common to said application programs, said common data structure containing a data structure with a plurality of attribute data objects each having hierarchical being-held relationships with a single other one of said attribute data objects or with an apex, wherein selected ones of said attribute data objects have non-hierarchical relationships with others of said attribute data objects, and wherein each of said attribute data objects has an associated memory area, a method for creating a desired non-hierarchical relationship between a given one of said attribute data objects and a referent one of said attribute data objects comprising the steps, executed by said central processor, of:

determining a location of said referent attribute data object;

accessing the memory area for said given attribute data object; and

placing a pointer to said referent attribute data object location in said memory area of said given attribute data object.

32. The method according to claim 31 wherein said desired non-hierarchical relationship is selected to be one of a predetermined type of relationships, wherein said memory system includes a type area identifying said types of non-hierarchical relationships and identifying where in said memory area for said attribute data objects to find pointers to referent attribute data objects of said types, and wherein the step of placing a pointer includes the substeps of

determining the type of said desired non-hierarchical relationship;

finding, in said type area, a location in said memory area for relationships of the type of said desired non-hierarchical relationship; and

placing said pointer into said memory area of said given attribute data object found for said desired non-hierarchical relationship type.

33. In a data processing system including at least one central processor executing a plurality of application programs and also including a memory containing a data structure common to said application programs, said common data structure containing a data structure with a plurality of attribute data objects each having hierarchical being-held relationships with a single holder one of said attribute data objects or with an apex, wherein selected ones of said attribute data objects have non-hierarchical relationships, and wherein each of said attribute data objects has an associated memory area containing

sequence pointers to the ones of said attribute data elements having a being-held relationship with the same holder one of said attribute data objects,

a holder pointer to said holder one of said attribute data objects, and

referent pointers to any of said referent ones of said attribute data objects with which that attribute data object has a non-hierarchical relationship, a method for erasing a memory area for a desired one of said attribute data objects comprising the steps, executed by said central processor, of:

locating said memory area for said desired attribute data object;

erasing said referent pointers;

locating the memory area for said holder attribute data object;

erasing the one of said holder pointers for said desired attribute data object;

adjusting said sequence pointer to remove any pointers to said desired attribute data object; and

erasing the memory areas for all containment tree ones of said attribute data objects which have a being-held relationship with said desired attribute data object or which have a being-held relationship with another one of said containment tree attribute data objects.

34. In a data processing system including at least one central processor executing a plurality of application programs and also including a memory containing a data structure common to said application programs, said common data structure containing a data structure with a plurality of attribute data objects each having hierarchical being-held relationships with a single other one of said attribute data objects or with an apex, wherein selected ones of said attribute data objects have non-hierarchical relationships with referent others of said attribute data objects, and wherein each of said attribute data objects has an associated memory area, containing referent pointers to any of said referent ones of said attribute data objects with which that attribute data object has a non-hierarchical relationship, said associated memory area for each of said referent attribute data objects containing a non-hierarchical relationship pointer to that attribute data object having a non-hierarchical relationship with that referent attribute data object, a method for erasing a desired non-hierarchical relationship between a given one of said attribute data objects and a referent one of said attribute data objects comprising the steps, executed by said central processor, of:

locating the memory area for said given attribute data object;

locating the referent pointer to said given referent attribute data object in the memory area for said given attribute data object;

locating said given referent attribute data object using said referent pointer;

locating the non-hierarchical relationship pointer to said given attribute data object in the memory area for said referent attribute data object;

erasing said non-hierarchical relationship pointer; and

erasing said referent pointer.

35. A method for managing different versions of a data structure stored in a memory system containing a master data file, which is used for updating the data structure to create a new version of said data structure, and a secondary file, from which the different versions of said data structure can be accessed, said master data file being divided into a series of pages, and said secondary file being composed of a plurality of slots each large enough to contain one of said pages of said master data file, the method comprising the steps of:

generating a new version of said data structure to modify zero or more of the pages in said master data file;

creating a new version block for each new version of said data structure, said new version block containing information about the new version of said data structure;

creating, for each of the pages of said master data file which is modified in generating said new version of said data structure, a corresponding and unique switch block;

copying into said secondary file, each of the pages from said master data file which have been modified in said new version of said data structure; and

entering into each of said switch blocks an identifier for the page corresponding to that switch block, the version during which that page was modified, and the slot in the secondary file into which that modified page has been copied.

36. The method of claim 35 further including the steps of:

linking the switch blocks which correspond to the same one of said pages, and

building a table to locate at least one of the switch blocks corresponding to each of the pages in said master data file.

37. A memory system for storing and maintaining different versions of a data structure, said memory system comprising:

master data file means for creating a new version of said data structure, said master data file means being divided into a series of pages and containing the most recent version of said data structure;

secondary file means, coupled to said master data file means, for holding different versions of said data structure for external access, said secondary file means containing a plurality of slots each large enough to hold one of said pages of said master data file means; and

data base control file means, coupled to said master data file means and to said secondary file means, for storing information necessary for the management of said memory system, said data base control file means including

a plurality of version blocks each containing information about a different version of said data structure, and

a plurality of switch blocks, each corresponding to one of said versions of said data structure and to a page

in said data structure which was modified during the corresponding version, said switch blocks each containing an identifier for the page corresponding to that switch block, the version during which that page was modified, and the slot in said secondary file means into which that modified page has been copied.

38. The method of claim 37 wherein said switch blocks also include linking information for the ones of said switch blocks which correspond to the same one of said pages, and wherein said memory system further comprises

a table containing mapping information for locating at least one of the switch blocks corresponding to one of said pages in said master data file means.

39. A memory system coupled to a central processor and containing a data structure including an apex, a plurality of elements each corresponding to a different node datum in an application program executed by said central processor, hierarchical holding relationships among said elements, and non-hierarchical relations for said elements, said hierarchical holding relationships in said data structure being restricted such that for each of said elements, only one other element or said apex has a holding relationship with that element, said memory system comprising:

element storage means for containing information about each of said elements, said element storage means including

a header portion containing identifying information about said elements,

holding pointers identifying the elements for which each of said element has one of said holding relationships, and

relation identifiers specifying said non-hierarchical relations; and

apex storage means for containing information about said apex, said apex storage means including

identifier information for said apex, and

element pointers to the elements having one of said holding relationships with said apex.

40. The memory system according to claim 39

wherein said data structure includes at least one context with which said apex has a holding relationship,

wherein each said at least one context has a holding relationship with at least one of said elements,

wherein each said at least one context corresponds to a containinment tree which includes all of said elements with which that element has a holding relationship and any other of said elements with which other ones of said elements in the containment tree of that at least one context has a holding relationship, such that each of said element is included in the containment tree of only one said at least one context,

wherein said elements are named such that the ones of said elements in the containment tree of each said at least one context have unique names which need not b different from the names of said elements in the containment trees of different ones of said at least one context, and

wherein said memory also includes

context storage means for containing said at least one context, said context storage means further including

identifier information for said at least one context, and

element pointers to the elements having one of said holding relationships with each said at least one context.

41. The memory system according to claim 39 wherein certain of said elements are each associated with a different one of a plurality of key values, and wherein said memory also includes

index storage means for containing said plurality of key values, said index storage means further including

index storage portions placing nonoverlapping subsets of said key values in an ordered fashion, and

key value pointers for specifying, for each of said key values, the location of in said element storage means of the identifying information for the elements associated with that key value;

and

index pointers for identifying said portions of said index storage means containing each of said key values.

42. The memory system according to claim 39 wherein certain of said elements and relations are associated with different types, and wherein said memory also includes

dictionary storage means for containing information about said types of elements and relations, said dictionary storage means including

element fields containing, for each of said types of elements, information about the elements of that type, and

relation fields containing, for each of said types of relations, information about the relations of that type;

index pointers for identifying portions of said index storage means containing desired key values.

43. A data processing system for maintaining and providing access to a common data structure, said data processing system comprising:

a central processor executing a plurality of application programs which exchange data via said common data structure, said common data structure including an apex, a plurality of elements each corresponding to a different node datum in an application program executed by said central processor, hierarchical holding relationships among said elements, and non-hierarchical relations for said elements, said hierarchical holding relationships in said data structure being restricted such that for each of said elements, only one other element or said apex has a holding relationship with that element;

a memory being coupled to said central processor and containing said common data structure, said memory including

element storage means for containing information about each of said elements, said element storage means further including

a header portion containing identifying information about said elements,

holding pointers identifying the elements for which each of said element has one of said holding relationships, and

relation identifiers specifying said non-hierarchical relations, and

apex storage means for containing information about said apex, said apex storage means further including

identifier information for said apex, and

element pointers to the elements having one of said holding relationships with said apex.

44. A data processing system for maintaining and providing access to a common data structure, said data processing system comprising:

a plurality of central processors simultaneously executing a plurality of application programs which exchange data via said common data structure, said common data structure including an apex, a plurality of elements each corresponding to a different node datum in an application program executed by said central processors, hierarchical holding relationships among said elements, and non-hierarchical relations for said elements, said hierarchical holding relationships in said data structure being restricted such that for each of said elements, only one other element or said apex has a holding relationship with that element;

a memory system being coupled to said central processors and containing said common data structure, said memory system including

element storage means for containing information about each of said elements, said element storage means further including

a header portion containing identifying information about said elements,

holding pointers identifying the elements for which each of said element has one of said holding relationships, and

relation identifiers specifying said non-hierarchical relations, and

apex storage means for containing information about said apex, said apex storage means further including

identifier information for said apex, and

element pointers to the elements having one of said holding relationships with said apex.