Data processing system having a data structure with a single, simple primitive

• US 5,664,177 A
• Filed: 04/13/1988
• Issued: 09/02/1997
• Est. Priority Date: 04/13/1988
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Lowry, Edward S.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Von Buhr, Maria N.
• Application Number:
  US07/181,105
• Time in Patent Office: 3,429 Days
• Field of Search: 364/200, 364/900, 364/DIG. 1, 364/DIG. 2, 395/600, 395/611
• 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

Abstract

A data structure in a computer memory is constructed from a single primitive data element or attribute. Attributes of the data structure are arranged in accordance with certain rules which impose a hierarchical organization upon the attributes as well as non-hierarchical relationships. The attributes may be created and erased by a data processing system containing the memory.

Claims

1. A memory for storing data for access by an application program being executed on a data processing system, comprising:

a data structure stored in said memory, said data structure including information resident in a database used by said application program and including;

a plurality of attribute data objects stored in said memory, each of said attribute data objects containing different information from said database;

a single holder attribute data object for each of said attribute data objects, each of said holder attribute data objects being one of said plurality of attribute data objects, a being-held relationship existing between each attribute data object and its holder attribute data object, and each of said attribute data objects having a being-held relationship with only a single other attribute data object, thereby establishing a hierarchy of said plurality of attribute data objects;

a referent attribute data object for at least one of said attribute data objects, said referent attribute data object being nonhierarchically related to a holder attribute data object for the same at least one of said attribute data objects and also being one of said plurality of attribute data objects, attribute data objects for which there exist only holder attribute data objects being called element data objects, and attribute data objects for which there also exist referent attribute data objects being called relation data objects; and

an apex data object stored in said memory and having no being-held relationship with any of said attribute data objects, however, at least one of said attribute data objects having a being-held relationship with said apex data object.

2. The memory of claim 1 wherein more than one of said attribute data objects can have a being-held relationship with another one of said attribute data objects.

3. The memory of claim 1 wherein at least one of said attribute data objects is a referent attribute data object for a plurality of said attribute data objects.

4. The memory of claim 1 wherein at least one of said attribute data objects includes type data descriptive of a relationship between that at least one of said attribute data objects and the other ones of said attribute data objects having a being-held relationship with that one attribute data object.

5. The memory of claim 1 wherein at least one of said relation data objects includes type data descriptive of a relationship between that at least the one of said relation data objects and the referent attribute data object of that one relation data object.

6. A data processing system executing an application program and containing a database used by said application program, said data processing system comprising:

cpu means for processing said application program; and

memory means for holding a data structure for access by said application program, said data structure being composed of information resident in said database used by said application program and including

a plurality of attribute data objects stored in said memory, each of said attribute data objects representing different information from said database;

a single holder attribute data object for each of said attribute data objects, each of said holder attribute data objects being one of said plurality of attribute data objects, a being-held relationship existing between each attribute data object and its holder attribute data object, and each of said attribute data objects having a being-held relationship with only a single other attribute data object thereby establishing a hierarchy of said plurality of attribute data objects;

a referent attribute data object for at least one of said attribute data objects, said referent attribute data object being nonhierarchically related to a holder attribute data object of the same at least one of said attribute data objects and also being one of said plurality of attribute data objects, attribute data objects for which there exist only holder attribute data objects being called element data objects, and attribute data objects for which there also exist referent attribute data objects being called relation data objects; and

an apex data object stored in said memory and having no being-held relationship with any of said attribute data objects, however, at least one of said attribute data objects having a being-held relationship with said apex data object.

7. The data processing system of claim 6 wherein more than one of said attribute data objects can have a being-held relationship with another one of said attribute data objects.

8. The data processing system of claim 6 wherein at least one of said attribute data objects is a referent attribute data object for a plurality of attribute data objects.

9. The data processing system of claim 6 wherein at least one of said attribute data objects includes type data descriptive of a relationship between that at least one of said attribute data objects and the other ones of said attribute data objects having a being-held relationship with that one attribute data object.

10. The data processing system of claim 6 wherein at least one of said relation data objects includes type data descriptive of a relationship between that at least one of said relation data objects and the referent attribute data object of that one relation data object.

11. The data processing system of claim 6 further including means for retrieving from said data structure the ones of said attribute data objects having a being-held relationship with a specified attribute data object, in response to a request for access from said application program.

12. The data processing system of claim 6 further including means for retrieving from said data structure the ones of said referent attribute data objects for a specified relation data object, in response to a request for access from said application program.

13. The data processing system of claim 6 further including means for creating a new attribute data object in said data structure from one of said attribute data objects which is the holding data object for the new attribute data object.

14. The data processing system of claim 13 wherein said means for creating a new attribute data object also includes means for creating that new attribute data object as one of said relation data objects from a referent attribute data object for the new relation data object.

15. The data processing system of claim 9 further including means for retrieving from said data structure each of said attribute data objects having type data that are the same, in response to a request for access from said application program.

16. The data processing system of claim 9 further including means for retrieving from said data structure the type data from a specified attribute data object, in response to a request for access from said application program.

17. The data processing system of claim 6 further including means for removing from said data structure a specified attribute data object, in response to a request for access from said application program.

18. The data processing system of claim 17 wherein said means for removing also includes means for removing from said data structure all attribute data objects which have a being-held relationship with said specified attribute data object and all attribute data objects which have a being-held relationship with any attribute data object removed from said data structure by said removing means.

19. The data processing system of claim 6 wherein said cpu means executes a plurality of application programs, and wherein said data structure is a common data structure for access by all of said application programs and composed of information resident in databases used by said application programs.

20. In a data processing system executing an application program, wherein said application program is accessing a data structure composed of information resident in a database used by said application program, wherein said data structure resides in a memory of said data processing system and includes a plurality of attribute data objects each representing different information from said database, wherein for each of said attribute data objects there exists a holder attribute data object and for certain of said attribute data objects there also exists a referent attribute data object related to a holder attribute data object for that attribute data object, each of said holder and referent attribute data objects being one of said plurality of attribute data objects, and wherein each of said plurality of attribute data objects has a being-held relationship with its holder attribute data object thereby establishing a hierarchy of said plurality of attribute data objects, a method of accessing attribute data objects in said data structure comprising the steps of:

selecting, by said application program, information resident in said database;

searching, by a data management program executed by said data processing system, said data structure for one of said attribute data objects representing said selected information;

retrieving, by said data management program, the attribute data objects having a being-held relationship with said one of said attribute data objects representing said selected information; and

transmitting to said application program by said data management program, information related to said retrieved attribute data objects.

21. In a data processing system executing an application program, wherein said application program is accessing a data structure composed of information resident in a database used by said application program, wherein said data structure resides in a memory of said data processing system and includes a plurality of attribute data objects each representing different information from said database, wherein for each of said attribute data objects there exists a holder attribute data object and for certain of said plurality of attribute data objects there also exists a referent attribute data object related to a holder attribute data object for that attribute data object, each of said holder and referent attribute data objects being one of said plurality of attribute data objects, and wherein each of said attribute data objects has a being-held relationship with its holder attribute data object thereby establishing a hierarchy of said plurality of attribute data objects, a method of accessing attribute data objects in said data structure comprising the steps of:

selecting, by said application program, information resident in said database;

searching, by a data management program executed by said data processing system, said data structure for one of said attribute data objects representing said selected information;

retrieving, by said data management program, a referent attribute data object for said attribute data object representing said selected information; and

transmitting to said application program by said data management program, information related to said retrieved referent attribute data object.

22. In a data processing system executing an application program, wherein said application program is accessing a data structure composed of information resident in a database used by said application program, wherein said data structure resides in a memory of said data processing system and includes a plurality of attribute data objects each representing different information from said database, wherein for each of said attribute data objects there exists a holder attribute data object and for certain of said attribute data objects there also exists a referent attribute data object related to a holder attribute data object for that attribute data object, each of said holder and referent attribute data objects being one of said plurality of attribute data objects, and wherein each of said attribute data objects has a being-held relationship with its holder attribute data object thereby establishing a hierarchy of said plurality of attribute data objects, a method of creating attribute data objects in said data structure comprising the steps of:

selecting, by said application program, information to be entered into said database;

creating, by a data management program executed by said data processing system, an attribute data object for said selected information;

choosing, by said data management program, one of said attribute data objects as a holder attribute data object for said created attribute data object, the chosen holder attribute data object being chosen according to said selected information; and

entering, by said data management program, the created data object into said data structure.

23. The method of claim 22 further including the step of choosing a referent attribute data object for said created attribute data object from said data structure, said chosen referent attribute data object being chosen according to said selected information.

24. A method for creating a data structure for access by an application program, said application program 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 program, and said method comprising the steps, executed by said data processor, of:

(a) creating a different one of a plurality of attribute data objects from said application data;

(b) organizing said plurality of 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, a hierarchical being-held relationship existing between each attribute data object and a single holder data object;

(c) establishing nonhierarchical relationships for certain ones of said attribute data objects created from said application data by choosing, from said attribute data objects, referent data objects for the ones of said selected attribute data objects, each chosen referent data object corresponding to one of said attribute data objects, said selected attribute data objects being called relation data objects and attribute data objects without referent data 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, each of said holding pointers indicating 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 nonhierarchical relationships between said attribute data objects.

25. In a data processing system including a central processor and a memory, said memory 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 certain 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 including pointers to memory areas for other ones of said attribute data objects which have a being-held relationship with that attribute data object, a method for adding new attribute data objects to said data structure comprising the steps, executed by said central processor, of:

creating a memory area for said new attribute data object;

choosing, as a holder attribute data object, one of said attribute data objects, said new attribute data object having a being-held relationship with the chosen one of said attribute data objects;

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

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

26. In a data processing system including a central processor and a memory, said memory 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 certain 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 non-hierarchical relationship between 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 the one of said attribute data objects; and

placing a pointer to said referent attribute data object location in said memory area of the one of said attribute data objects.

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

determining the one of a predetermined type of said 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.

28. In a data processing system including a central processor and a memory, said memory 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 certain 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 containing

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

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

referent pointers to any of said attribute data objects with which that attribute data object has a non-hierarchical relationship,

a method for erasing a memory area for one of said attribute data objects comprising the steps, executed by said central processor, of:

locating said memory area for the one of said attribute data objects;

erasing from said memory area for the one of said attribute data objects any referent pointers to any of the ones of said attribute data objects with which the one of said attribute data objects has a non-hierarchical relationship;

locating the memory area for said holder attribute data object;

erasing from said memory area for the one of said attribute data objects said holder pointer for the one of said attribute data objects;

adjusting said sequence pointers in said memory area for the one of said attribute data objects to remove any pointers to the one of said attribute data objects; and

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

29. In a data processing system including a central processor and a memory, said memory 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 certain ones of said attribute data objects have non-hierarchical relationships with referent ones 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 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 object, a method for erasing a desired non-hierarchical relationship between 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 the one of said attribute data objects;

locating the referent pointer to said referent attribute data object in the memory area for the one of said attribute data objects;

locating said referent attribute data object using said referent pointer;

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

erasing said non-hierarchical relationship pointers; and

erasing said referent pointer.