Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-10-13
2001-09-04
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06286007
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to data processing systems and, in particular, to a method and system in a data processing system for efficiently storing and viewing data in a database. Still more particularly, the present invention relates to a method and system in a data processing system for viewing data stored in a database as being flat, where the data is stored utilizing a nested data model without flattening the nested data model.
2. Description of the Related Art
Data may be stored in a database and viewed utilizing one of several different data models. An unnested data model is a type of hierarchical data model where the data is organized and stored where each node of the model has only one owner. The edges point to the nodes owned by the parent node. An edge represents a unique instance of a data object. In an unnested model, each edge represents only one instance of data.
For example,
FIG. 1
depicts a pictorial representation of an unnested data model of data. In this example, a node named “V1” owns one instance of a node named “V2” and two instances of a node named “V3”. The single instance of V2 is named “A” and is represented by edge “A”. The first instance of V3 is named “B”, and the second instance of V3 is named “C”. The first instance of V3 is represented by edge “B”, and the second instance is represented by edge “C”.
A nested data model is a type of hierarchical data model where the data is organized and stored where each node of the model has one or more owners. Unlike an unnested data model where each edge represents only one instance of data, in a nested data model, each edge may represent multiple instances of data.
FIG. 2
illustrates a pictorial representation of a nested model of the same data stored utilizing the unnested model of FIG.
1
.
In a nested model, a single node may have multiple edges leading into a node and multiple edges leading out of a node. Vertices V3, V4, and V5 all have multiple edges leading into them. There are multiple paths to traverse to a vertex or an edge. A path is a collection of all edges traversed from a top node to reach a destination edge. For example, there are three different paths to traverse from vertex V1 to edge H. The first path is from “A” to “E” to “H”. The second path is from “B” to “F” to “H”. And, the third path is from “C” to “F” to “H”. There are three different instances of the data represented by edge H. These three instances are named “A.E.H.”, “B.F.H”, and “C.F.H”. Although the nested model includes only one edge named “H”, there are actually three different instances of that edge, i.e. the data, in the model.
A flat data model is one which has no hierarchical structure and in which the data is stored where a parent node may have multiple dependent nodes. However, the dependent nodes do not have any dependent nodes.
FIG. 3
illustrates a flat data model of the same data represented in the hierarchical model of FIG.
1
. In the flat data model of
FIG. 3
, only the leaf instances of the data are stored. The leaf instances are those instances of data represented by a node which do not own another node. For example, in
FIG. 3
, nodes A.D., A.E.H., and A.E.I. are some of the leaf instances.
As is readily apparent from these figures, storing data utilizing an unnested data model requires more data storage space than storing data utilizing the flat model. The unnested and flat models may both be utilized so that an application may view the data as flat. An application cannot, however, utilize the nested model to view the data as flat. The data must be unfolded from the nested model into either the flat model or the unnested model in order for an application to view the data as flat.
Some programs need to distinguish between the different instances of an edge, and therefore cannot easily utilize a nested model. For example, a program may need to attach some property to each instance of an edge. The value of the property may vary from one of the instances of the edge to the others. Since there is only one H edge in the nested model, storing three different values of the properties with each instance is difficult.
Programs that need to distinguish between the different instances of an edge must either build an unnested model or flatten the data. An unnested model is built by transforming the nested model into an unnested model. To do this, the vertices must be copied so that each vertex has at most only one edge leading into it. However, for large nested models, building an unnested or flattened model is impractical or may be impossible due to the much larger data storage space required for these models.
Therefore, a need exists for a method and system in a data processing system for efficiently storing data in a database utilizing a nested data model and permitting the viewing of the data as flat without flattening the data.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved data processing system.
It is another object of the present invention to provide a method and system in a data processing system for efficiently storing and viewing data in a database.
It is yet another object of the present invention to provide a method and system in a data processing system for viewing data stored in a database as being flat, where the data is stored utilizing a nested data model without flattening the nested data model.
The foregoing objects are achieved as is now described. A method and system are disclosed for efficiently storing and viewing data in a database. Data is stored in a nested data model which includes a plurality of nodes. A plurality of edges connect the plurality of nodes. Each edge has a unique edge name. A plurality of instances of data objects are associated with the nested data model. Each instance is associated with one of the edges such that the instance is also associated with that edge's name. An instance ordinal is associated with each instance which represents the number of times the edge associated with each instance is encountered during a traversal of the nested data model. The data stored utilizing the nested data model is accessed utilizing the instance ordinal and edge name associated with each of the plurality of instances, such that the data is accessed as being flat without flattening the nested data model.
The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5339392 (1994-08-01), Risberg et al.
patent: 5970590 (1999-10-01), Morgenstern
Miller Clinton Frederick
Villarrubia Paul Gerard
Black Thomas
Bracewell & Patterson L.L.P.
England Anthony V. S.
International Business Machines - Corporation
Mills John G.
LandOfFree
Method and system for efficiently storing and viewing data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for efficiently storing and viewing data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for efficiently storing and viewing data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2501986