US5440730A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Time index access structure for temporal databases having concurrent multiple versions
Assignee: Nytell Software LLC
•
Filing: 1990-08-09
•
Granted: 1995-08-08
•
Expires: 2010-08-09
Abstract
Abstract A time index for temporal databases is provided which enables the retrieval of database object versions that are valid during specified time periods. Unlike prior access and retrieval structures, the present index is based on objects whose search values are time intervals rather than time points. A series of ordered indexing points is defined by the start and end of object version intervals and these points are used to build an indexing structure, which may take the form of a B + -tree. Each leaf node entry of the B + -tree represents an indexing point and has an associated bucket of pointers which identify all object versions that are valid at that time. Storage space is reduced by including only incremental change indicators in the buckets of non-leading leaf entries and calculating needed pointers from such indicators. The time index may be employed in multi-level structures with attribute indexes to greatly improve the efficiency of temporal search operations, such as aggregate functions and temporal selection, as well WHEN and JOIN operators.
Inventors
- 👤 Ramez A. Elmasri
- 👤 Tzyh-Jain G. Wuu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 06:40
CPC Classifications
G; G06; G06F; G06F16/00; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99954
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
66 words
A computer-based temporal database management system including a time index which comprises: a) an ordered series of indexing time points defining time intervals during which at least one of a plurality of concurrent object version in said database is valid; and b) associated with each indexing point, pointer means identifying all database object versions that are valid at the time represented by said each indexing point.
Claim 2
Dependent Claim
66 words
A computer-based temporal database management system including a time index which comprises: a) an ordered series of indexing time points defining time intervals during which at least one of a plurality of concurrent object version in said database is valid; and b) associated with each indexing point, pointer means identifying all database object versions that are valid at the time represented by said each indexing point.
Claim 3
Dependent Claim
26 words
A system according to claim 1 wherein said each indexing time point defines a change of state of said database with respect to an object version.
Claim 4
Dependent Claim
50 words
A system according to claim 1 wherein said indexing time points are situated on a scale of regularly occurring time points and represent those scalar time points: a) at which a database object version begins; and b) next following the scalar time point at which a database object version terminates.
Claim 5
Dependent Claim
22 words
A system according to claim 1 wherein said indexing time points populate the leaf nodes of a B + -tree index structure.
Claim 6
Dependent Claim
27 words
A system according to claim 4 wherein each said indexing time point has an associated pointer to a bucket of pointers identifying said valid database object versions.
Claim 7
Dependent Claim
19 words
A system according to claim 5 wherein each said valid database object version is identified by a bucket pointer.
Claim 8
Dependent Claim
22 words
A system according to claim 5 wherein the bucket pointers of selected indexing points identify only beginning and terminating database object versions.
Claim 9
Independent Claim
74 words
A method for structuring a time index in a computer-based temporal database management system which comprises: a) assembling in computer memory an ordered series of indexing time points defining time intervals during which at least one of a plurality of concurrent object version in said database is valid; and b) associating with each indexing point pointer means identifying all database object versions that are valid at the time represented by said each indexing point.
Claim 10
Independent Claim
74 words
A method for structuring a time index in a computer-based temporal database management system which comprises: a) assembling in computer memory an ordered series of indexing time points defining time intervals during which at least one of a plurality of concurrent object version in said database is valid; and b) associating with each indexing point pointer means identifying all database object versions that are valid at the time represented by said each indexing point.
Claim 11
Dependent Claim
40 words
A method according ,to claim 8 which further comprises selecting as said indexing time points those points on a scale of regularly occurring time points that define a change of state of said database with respect to an object version.
Claim 12
Dependent Claim
34 words
A method according to claim 9 which comprises selecting time points: a) at which a database object version begins; and b) next following the scalar time point at which a database object version terminates.
Claim 13
Dependent Claim
29 words
A method according to claim 8 wherein said assembling comprises inserting said indexing time points as the population of the leaf nodes of a B + -tree index structure.
Claim 14
Dependent Claim
29 words
A method according to claim 11 which further comprises associating with each said indexing time point a pointer to a bucket of pointers identifying said valid database object versions.
Claim 15
Dependent Claim
52 words
A method according to claim 12 which further comprises associating with said time index B + -tree, by means of a leaf node pointer therefrom to said time index B + -tree, a higher level B + -tree index of database attributes related to the time interval object versions of said database.
Claim 16
Dependent Claim
135 words
A method according to claim 12 which further comprises, upon inserting in said database a new object version whose time interval extends from a first time point to a second time point: a) if there exists no indexing point at said first time point, creating an indexing point at said first time point and creating a pointer bucket for said indexing point; b) if there exists no indexing point at the next scalar time point following said second time point, creating an indexing point at said next time point and creating a pointer bucket for said indexing point; and c) inserting a pointer to said new object version in the bucket for the indexing point at said first time point and in the buckets for all subsequent indexing points prior to said second time point.
References Cited (Backward Citations)
US3568155A
Cited
US3681781A
Cited
US4646229A
Cited
US4989133A
Cited
US4805107A
Cited
US5058002A
Cited
US4914586A
Cited
US4894846A
Cited
US5089952A
Cited
US5093794A
Cited
US5257365A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-07 | 1999-02-06 | 1999-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-07 | 2003-02-06 | 2003-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-07 | 2007-02-06 | 2007-08-08 | $7700.00 | Window Closed / Lapsed |