 |
Claims  |
|
|
What is claimed is:
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.
15. The method according to 14 wherein said first file is said dictionary
file.
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.
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. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
RELATED APPLICATION
This application is related to U.S. Ser. No. 181,105, entitled "Data
Processing System Having a Data Structure With a Single, Simple Primitive"
by Edward S. Lowry, filed Apr. 13, 1988.
BACKGROUND OF THE INVENTION
This invention relates generally to the field of databases, and more
specifically to the uses of common databases by several application
programs.
Often many different application programs must be adapted to share or
exchange information with other programs in a computer system. One notable
example is a set of interactive computer programs which provide assistance
in the design and manufacture of products. Such interactive programs
typically include computer-aided design (CAD) programs and computer-aided
manufacturing (CAM) programs that are used in the development of products.
Other examples of application programs often requiring information
exchange are document retrieval programs and project management programs.
In such systems, output data from one application program is often input
data for one or more other application programs. For example, the output
data of a CAD program used to develop the design of a circuit board may be
used as input data for a CAM program which facilitates manufacture of the
designed circuit board.
In order for output data from any application program to function as the
input data for another application program, however, both application
programs must be designed to allow such a transfer of data may take place.
The output data must be prepared and presented in a form which is
acceptable for use by the application program which operates on the data.
Application programs which communicate in this manner are said to be
integrated.
Achieving integration between pairs of software application programs is a
relatively simple task. Such integration merely requires modification to
one or both of the two application programs sought to be integrated.
Achieving integration among several other application programs, on the
other hand, becomes increasingly complex as the number of programs
increases. Integrating several programs is not uncommon, however. For
example, one CAD program for designing integrated circuits may need to be
integrated with another CAD program for designing circuit boards as well
as with a CAM program to manufacture the boards.
Typically, the integration of one application program with several other
application programs is achieved by designing the first program to be
integrable with each of the other programs. This design strategy, however,
requires detailed knowledge about the input requirements of each program
and may require redesign of the first application program each time a new
application program is added. If the other application programs are
instead redesigned for integration with the first application program,
similar problems arise.
Alternatively, a conversion program may be used to integrate the first
application program with the other application programs. As other programs
are added, however, additional conversion programs must be designed.
The use of these conversion programs and the redesign of the application
programs to achieve integration require considerable time, effort, and
expense. This time, effort and expense dramatically increases with the
number of programs to be integrated.
To obviate the need for additional conversion programs, common databases
have been adopted to store data in memory in an area which is accessible
by the different programs. Systems using a common database only require
each applicaation program to have an interface with the common database.
Such interfaces convert data output by an application program into a
common format for storage at the common database, and convert the data
from its common format into a format in the common database acceptable for
the application programs. Common database systems which are known or used
to store data include, for example, the "relational," "functional," and
"Codasyl" data models.
Although common database systems using conventional data models overcome
the threshhold problem of program integration described above, the use of
conventional data models presents distinct programming and performance
problems for the integrated programs. For one discussion of the
programming and performance problems presented by conventional data models
see U.S. Pat. No. 4,631,664 issued to Charles W. Bachman.
Accordingly, it is an object of the present invention to provide a method
for integrating several application programs using a common data structure
in a manner which reduces the need and complexity of additional conversion
programs or redesign of application programs.
It is also an object of the present invention to provide a program
integration method which overcomes the practical performance problems
encountered by common database systems utilizing conventional data models.
It is another object of this invention to provide a means for managing the
access to such a common data structure by application programs.
Yet another object of the present invention is to provide a common data
structure which can be easily adapted to a data processing system with
auxiliary memory.
It is a further object of the present invention to express information in
application programs using only a single primitive element which can
represent the complex interrelationships of application program
information.
Additional objects and advantages of the invention will be set forth in the
description which follows or may be learned by practice of the invention.
SUMMARY OF THE INVENTION
To achieve the foregoing objects, and in accordance with the purpose of the
invention as embodied and broadly described herein, a data structure for
access by a plurality of application programs is created from single
primitive data elements or attribute data objects. According to the
present invention, a the data structure in a memory coupled to the data
processor. The data structure is created using data or | | |
