EP0375307A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Structure for and method of arranging recursively derived data in a database
Assignee: LU, HONGJUN
•
Filing: 1989-12-18
•
Granted: —
•
Expires: 2009-12-18
Abstract
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.
Inventors
- 👤 Ming-Chien Shan
- 👤 Hongjun Lu
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-30 01:55
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9027; G06F16/9017; G06F16/902; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
258 words
A database structure for recursively derived data items, the structure comprising: a plurality of hierarchical iteration levels, one such level corresponding with each iteration of the recursive relation from which the data items are derived, all data items derived during a given iteration being associated with the corresponding iteration level; an index structure for indexing the data items, the index structure comprising: a sequence set having a plurality of leaf nodes arranged sequentially to define a bottom index level of the structure, each such node providing a reference between a pointer to one of the data items, a key value which uniquely identifies that data item, and the iteration level associated with that data item; an index set having a plurality of non-leaf nodes arranged hierarchically to define a plurality of index levels above the bottom index level of the structure, each level having fewer nodes than the level beneath it, each node encompassing a range of the key values of the sequence set, all of the nodes on any level together encompassing all of said key values, each range encompassed by a node being included in the range encompassed by a node on the next higher level, each node providing 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; and an iteration level index providing a reference between each iteration level and a data item associated with that level; and means for linking the data items associated with each iteration level.
Claim 2
Dependent Claim
258 words
A database structure for recursively derived data items, the structure comprising: a plurality of hierarchical iteration levels, one such level corresponding with each iteration of the recursive relation from which the data items are derived, all data items derived during a given iteration being associated with the corresponding iteration level; an index structure for indexing the data items, the index structure comprising: a sequence set having a plurality of leaf nodes arranged sequentially to define a bottom index level of the structure, each such node providing a reference between a pointer to one of the data items, a key value which uniquely identifies that data item, and the iteration level associated with that data item; an index set having a plurality of non-leaf nodes arranged hierarchically to define a plurality of index levels above the bottom index level of the structure, each level having fewer nodes than the level beneath it, each node encompassing a range of the key values of the sequence set, all of the nodes on any level together encompassing all of said key values, each range encompassed by a node being included in the range encompassed by a node on the next higher level, each node providing 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; and an iteration level index providing a reference between each iteration level and a data item associated with that level; and means for linking the data items associated with each iteration level.
Claim 3
Dependent Claim
25 words
A database structure according to claim 1 wherein the linking means comprises global chain references which link the data items associated with each iteration level.
Claim 4
Dependent Claim
27 words
A database structure according to claim 1 wherein each data item associated with a given iteration level is assigned to a page associated with that iteration level.
Claim 5
Dependent Claim
24 words
A database structure according to claim 3 wherein the linking means comprises page chain references which link the pages associated with each iteration level.
Claim 6
Independent Claim
253 words
A method of arranging recursively derived data items in a database, the method comprising: defining a plurality of hierarchical iteration levels, one such level corresponding with each iteration of the recursive relation from which the data items are derived; associating all data items derived during a given iteration with the corresponding iteration level; defining a sequence set having a plurality of leaf nodes arranged sequentially to define a bottom index level of an index structure; associating each leaf node with a pointer to one of the data items, a key value which uniquely identifies that data item, and the iteration level associated with that data item; defining an index set having a plurality of non-leaf nodes 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; defining 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.
Claim 7
Independent Claim
253 words
A method of arranging recursively derived data items in a database, the method comprising: defining a plurality of hierarchical iteration levels, one such level corresponding with each iteration of the recursive relation from which the data items are derived; associating all data items derived during a given iteration with the corresponding iteration level; defining a sequence set having a plurality of leaf nodes arranged sequentially to define a bottom index level of an index structure; associating each leaf node with a pointer to one of the data items, a key value which uniquely identifies that data item, and the iteration level associated with that data item; defining an index set having a plurality of non-leaf nodes 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; defining 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.
Claim 8
Dependent Claim
23 words
A method according to claim 5 wherein linking the data items comprises globally chaining the data items associated with a given iteration level.
Claim 9
Dependent Claim
114 words
A method according to claim 6 and further comprising inserting a new data item into the database by: identifying which of the data items associated with the iteration level of the new item has the closest key value to the key value of the new item; inserting the new data item into the database adjacent the identified data item; linking the new data item to the other data items associated with the iteration level of the new item; creating a new leaf node having a pointer to the new data item; inserting the new leaf node into the sequence set; and adjusting the index set to include a path to the new leaf node.
Claim 10
Dependent Claim
30 words
A method according to claim 7 and further comprising discarding the new data item if its key value is the same as the key value of the identified data item.
Claim 11
Dependent Claim
25 words
A method according to claim 8 and further comprising stopping iteration of the recursive relation if all the items generated during an iteration are discarded.
Claim 12
Dependent Claim
23 words
A method according to claim 7 and further comprising discarding the new data item if it is identical to the identified data item.
Claim 13
Dependent Claim
25 words
A method according to claim 10 and further comprising stopping iteration of the recursive relation if all the items generated during an iteration are discarded.
Claim 14
Dependent Claim
27 words
A method according to claim 5 and further comprising assigning each data item associated with a given iteration level to a page associated with that iteration level.
Claim 15
Dependent Claim
21 words
A method according to claim 12 wherein linking the data items comprises chaining the pages associated with a given iteration level.
Claim 16
Dependent Claim
104 words
A method according to claim 13 and further comprising inserting a new data item by: identifying which of the data items associated with the iteration level of the new item has the closest key value to the key value of the new item; assigning the new data item to a page associated with the iteration level of the new item at a location adjacent the identified data item; creating a new leaf node having a pointer to the new data item; inserting the new leaf node into the sequence set; and adjusting the index set to include a path to the new leaf node.
Claim 17
Dependent Claim
30 words
A method according to claim 14 and further comprising discarding the new data item if its key value is the same as the key value of the identified data item.
Claim 18
Dependent Claim
25 words
A method according to claim 15 and further comprising stopping iteration of the recursive relation if all the items generated during an iteration are discarded.
Claim 19
Dependent Claim
23 words
A method according to claim 14 and further comprising discarding the new data item if it is identical to the identified data item.
Claim 20
Dependent Claim
25 words
A method according to claim 17 and further comprising stopping iteration of the recursive relation if all the items generated during an iteration are discarded.
Claim 21
Dependent Claim
92 words
A method of searching a set of data items arranged according to the method of claim 5 to find a data item having a specified key value and an iteration level within a specified range, the method comprising: selecting an access path from the paths provided by the non-leaf nodes to locate a leaf node associated with the specified key value; determining whether the iteration level associated with said leaf node is within the specified range; and returning the data item associated with said leaf node only if said determination is affirmative.
Claim 22
Dependent Claim
112 words
A method of scanning a set of data items arranged according to the method of claim 5 to find any data items satisfying a specified condition and having a specified iteration level, the method comprising: utilizing the iteration level index to locate a first data item associated with that iteration level; following the linking of the data items to locate the other data items associated with that iteration level; examining each located data item in sequence to determine whether it satisfies the prescribed condition; and if the examined item satisfies the prescribed condition, retrieving the item, the items retrieved during the scan being arranged in sequential order according to their key values.
Claim 23
Dependent Claim
108 words
A method of performing a nested loop join in a database wherein data items have been arranged according to the method of claim 5, the method comprising: scanning a first set of the data items to find any data items satisfying a specified condition and having a specified iteration level; for each data item found in the preceding step, searching a second set of the data items to find any data items having a key value corresponding with the key value of said data item and a specified iteration level; and joining each data item found in the scan with any corresponding data item found in the search.
Claim 24
Dependent Claim
80 words
A method of performing a merge scan join in a database system wherein data items have been arranged according to the method of claim 5, the method comprising: simultaneously scanning a first set of data items having a first specified iteration level and a second set of data items having a second iteration level; and joining any data item found in the scan of the first set with any matching data item found in any scan of the second set.
Claim 25
Dependent Claim
22 words
A digital computer when programmed to operate in accordance with a database structure as claimed in any of claims 1 to 4.
Claim 26
Independent Claim
19 words
A method of operating a digital computer in accordance with the method of any of claims 5 to 22.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.