Method of recursively deriving and storing data in, and retrieving recursively-derived data from, a computer database system
First Claim
Patent Images
1. In a computerized database system, a method of deriving data and storing the derived data in a memory of the computer, the method comprising:
- deriving new items of data for storage in the memory by iteratively evaluating a database query that receives itself as an argument a plurality of times according to a recursive relation;
associating storage locations in the memory with a plurality of hierarchical iteration levels, one such level corresponding with each iteration of the recursive relation performed by the computer to derive the new data items;
storing all data items derived during a given iteration in locations associated with the corresponding iteration level;
reserving a plurality of memory locations to form a sequence set having a plurality of leaf node locations arranged sequentially to define a bottom index level of an index structure;
for each newly derived data item, entering in a leaf node location of the sequence set a cross-reference between a pointer to that data item, a key value which uniquely identifies that data item, and the iteration level associated with that data item;
reserving a plurality of memory locations to form an index set having a plurality of non-leaf node locations arranged hierarchically to define a plurality of index levels above the bottom index level of the index structure, each level having fewer nodes than the level beneath it;
assigning each node a range of the key values of the sequence set such that all of the nodes on any level together encompass all of said key values, each range encompassed by a node is included in the range encompassed by a node on the next higher level, and each node provides for any key value within its range an access path to a node on the next lower level having said key value within its range;
reserving a plurality of memory locations to form an iteration level index to provide a reference between each iteration level and a data item associated with that level; and
linking the data items associated with each iteration level by storing references in the memory between the data items.
2 Assignments
0 Petitions
Accused Products
Abstract
A structure and method of arranging recursively derived data items in a database. A set of hierarchical iteration levels, one for each iteration of the recursive relation from which the data items are derived, is provided and all data items derived during a given iteration are associated with the corresponding iteration level. Also provided is an index structure including an index set of non-leaf nodes, a sequence set of leaf nodes, and an iteration level index. The leaf nodes include a record of the iteration level of each data item. The data are globally linked according to iteration level or are clustered on pages which are linked according to iteration level. Highly efficient scan and search are implemented by utilizing the iteration level index and the record of iteration level in the leaf nodes to direct the scanning and searching to data generated during a single iteration. The least fixpoint of a set of mutually recursive relations is efficiently calculated by these methods.
-
Citations
18 Claims
-
1. In a computerized database system, a method of deriving data and storing the derived data in a memory of the computer, the method comprising:
-
deriving new items of data for storage in the memory by iteratively evaluating a database query that receives itself as an argument a plurality of times according to a recursive relation; associating storage locations in the memory with a plurality of hierarchical iteration levels, one such level corresponding with each iteration of the recursive relation performed by the computer to derive the new data items; storing all data items derived during a given iteration in locations associated with the corresponding iteration level; reserving a plurality of memory locations to form a sequence set having a plurality of leaf node locations arranged sequentially to define a bottom index level of an index structure; for each newly derived data item, entering in a leaf node location of the sequence set a cross-reference between a pointer to that data item, a key value which uniquely identifies that data item, and the iteration level associated with that data item; reserving a plurality of memory locations to form an index set having a plurality of non-leaf node locations arranged hierarchically to define a plurality of index levels above the bottom index level of the index structure, each level having fewer nodes than the level beneath it; assigning each node a range of the key values of the sequence set such that all of the nodes on any level together encompass all of said key values, each range encompassed by a node is included in the range encompassed by a node on the next higher level, and each node provides for any key value within its range an access path to a node on the next lower level having said key value within its range; reserving a plurality of memory locations to form an iteration level index to provide a reference between each iteration level and a data item associated with that level; and linking the data items associated with each iteration level by storing references in the memory between the data items. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeHewlett-Packard Development Company, L.P. (HP Inc.)
-
Original AssigneeHewlett-Packard Company (HP Inc.)
-
InventorsLu, Hongjun, Shan, Ming-Chien
-
Primary Examiner(s)Treat, William M.
-
Application NumberUS08/018,473Time in Patent Office1,274 DaysField of Search395/600US Class Current1/1CPC Class CodesG06F 16/902 using more than one table i...G06F 16/9027 TreesY10S 707/99933 Query processing, i.e. sear...
