US5806076A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Tracking dependencies between transactions in a database
Assignee: Oracle International Corp
•
Filing: 1996-10-29
•
Granted: 1998-09-08
•
Expires: 2016-10-29
Abstract
Abstract A method and an apparatus for tracking of the dependencies between transactions is provided. Every time a data item is updated, a record is made of the transaction that updated the data item. Before another transaction locks a data item previously locked by the transaction, the entry is updated to indicate that the transaction committed and the commit time of the transaction. These entries are contained in a list head that is maintained on the same block as the data item, and a list tail that is stored separate from the data block that contains the data item. A depends-on time is maintained for each transaction. Whenever the transaction updates a data item, the depends-on time is set to the greater of the current depends-on time and the commit time of the most recently committed transaction that updated the version of the data item. Whether a transaction depends on a committed transaction is then determined based on a simple comparison between the depends-on time associated with the transaction and the commit time of the committed transaction.
Inventors
- 👤 Gary C. Ngai
- 👤 Roger J. Bamford
- 👤 Garret Swart
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 22:15
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/466; G06F16/00; G06F16/20; G06F16/23; G06F16/2308; G06F16/2315; G06F16/2329; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953; Y10S707/99954
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
159 words
A method for tracking dependencies between transactions, the method comprising the steps of: storing data that indicates which transactions have updated a data item, said data including commit times for those transactions that have committed after updating the data item; storing a depends-on time associated with an active transaction; accessing a version of the data item in response to executing said active transaction; reading said data to determine a time value that represents a time that is at least as recent as a commit time of a committed transaction that most recently updated said version of the data item; updating the depends-on time associated with the active transaction to said time value if said time value represents a time more recent than said depends-on time; and approximating a determination of whether said active transaction depends on another transaction based on a comparison between a commit time for said other transaction and the depends-on time associated with the active transaction.
Claim 2
Independent Claim
159 words
A method for tracking dependencies between transactions, the method comprising the steps of: storing data that indicates which transactions have updated a data item, said data including commit times for those transactions that have committed after updating the data item; storing a depends-on time associated with an active transaction; accessing a version of the data item in response to executing said active transaction; reading said data to determine a time value that represents a time that is at least as recent as a commit time of a committed transaction that most recently updated said version of the data item; updating the depends-on time associated with the active transaction to said time value if said time value represents a time more recent than said depends-on time; and approximating a determination of whether said active transaction depends on another transaction based on a comparison between a commit time for said other transaction and the depends-on time associated with the active transaction.
Claim 3
Dependent Claim
71 words
The method of claim 1 wherein the step of storing data that indicates which transactions have updated a data item includes the steps of: storing in a data block with said data item a list head that includes a fixed number of entries for transactions that updated said data item; and storing separate from said data item a list tail that includes additional entries for transactions that updated said data item.
Claim 4
Dependent Claim
26 words
The method of claim 2 wherein the step of reading data to determine a time value includes reading said data block without reading said list tail.
Claim 5
Dependent Claim
92 words
The method of claim 2 further comprising the steps of: updating said data item in response to executing a second transaction; writing over an entry in said list head in response to updating said data item, wherein said entry is the only entry in said list head for a committed transaction; writing a include time value into the data block in response to writing over said entry, wherein said include time value represents a time that is at least as recent as the commit time of the transaction associated with said entry.
Claim 6
Dependent Claim
56 words
The method of claim 4 wherein, when all entries in said list head represent active transactions: the step of reading said data to determine a time value includes reading said include time value; and the step of updating the depends-on time associated with the active transaction includes updating the depends-on time to said include time value.
Claim 7
Independent Claim
116 words
A method for tracking dependencies between transactions, the method comprising the steps of: when a version of a data item is supplied to a transaction, determining an include-time value that represents a time at least as recent as a commit time of a transaction that most recently updated said version of said data item; resetting depends-on time value associated with said transaction to said include time value if said include time value represents a time that is more recent that said depends-on time value; and approximating a determination of whether said transaction depends on a committed transaction based on a comparison between a commit time for the committed transaction and the depends-on time of said transaction.
Claim 8
Independent Claim
116 words
A method for tracking dependencies between transactions, the method comprising the steps of: when a version of a data item is supplied to a transaction, determining an include-time value that represents a time at least as recent as a commit time of a transaction that most recently updated said version of said data item; resetting depends-on time value associated with said transaction to said include time value if said include time value represents a time that is more recent that said depends-on time value; and approximating a determination of whether said transaction depends on a committed transaction based on a comparison between a commit time for the committed transaction and the depends-on time of said transaction.
Claim 9
Dependent Claim
49 words
The method of claim 6 further comprising the steps of: storing in a data block on a persistent storage device a stored version of said data item; and wherein the step of determining said include-time value includes determining said include-time value based on data stored on said data block.
Claim 10
Dependent Claim
65 words
The method of claim 7 further comprising the steps of: storing on said data block a list head that indicates commit times of transactions that have updated said data block; and wherein the step of determining said include-time value based on data stored on said data block includes determining said include-time value based on said commit times of transactions that have updated said data block.
Claim 11
Dependent Claim
87 words
The method of claim 7 further comprising the steps of: storing in said data block entries that identify a set of transactions that have updated said data block, said entries including commit times for any transaction in said set of transactions that is committed; and storing in said data block a commit time value specified in an entry of said entries when the entry is to be overwritten; wherein the step of determining said include-time value includes determining said include-time value based on said commit time value.
Claim 12
Dependent Claim
73 words
The method of claim 9 wherein: the method further comprises the step of determining whether the entry to be overwritten is the only entry of said entries associated with a committed transaction; and the step of storing in said data block a commit time value specified in an entry is performed in response to determining that the entry to be overwritten is the only entry of said entries associated with a committed transaction.
Claim 13
Dependent Claim
67 words
The method of claim 7 further comprising the steps of: reconstructing said data block by applying one or more undo records to said data block; wherein said version of said data item is the version of said data item in said reconstructed data block; and wherein the step of determining said include-time value includes determining said include-time value based on data stored in said reconstructed data block.
Claim 14
Dependent Claim
136 words
A computer readable medium having stored thereon sequences of instructions, said sequences of instructions including sequences of instructions which, when executed by a processor, cause the processor to perform the steps of: when a version of a data item is supplied to a transaction, determining an include-time value that represents a time at least as recent as a commit time of a transaction that most recently updated said version of said data item; resetting a depends-on time value associated with said transaction to said include time value if said include time value represents a time that is more recent that said depends-on time value; and approximating a determination of whether said transaction depends on a committed transaction based on a comparison between a commit time for the committed transaction and the depends-on time of said transaction.
Claim 15
Dependent Claim
136 words
A computer readable medium having stored thereon sequences of instructions, said sequences of instructions including sequences of instructions which, when executed by a processor, cause the processor to perform the steps of: when a version of a data item is supplied to a transaction, determining an include-time value that represents a time at least as recent as a commit time of a transaction that most recently updated said version of said data item; resetting a depends-on time value associated with said transaction to said include time value if said include time value represents a time that is more recent that said depends-on time value; and approximating a determination of whether said transaction depends on a committed transaction based on a comparison between a commit time for the committed transaction and the depends-on time of said transaction.
Claim 16
Dependent Claim
55 words
The computer-readable medium of claim 12 further comprising sequences of instructions for performing the steps of: storing in a data block on a persistent storage device a stored version of said data item; and wherein the step of determining said include-time value includes determining said include-time value based on data stored on said data block.
Claim 17
Dependent Claim
71 words
The computer-readable medium of claim 13 further comprising sequences of instructions for performing the steps of: storing on said data block a list head that indicates commit times of transactions that have updated said data block; and wherein the step of determining said include-time value based on data stored on said data block includes determining said include-time value based on said commit times of transactions that have updated said data block.
Claim 18
Dependent Claim
93 words
The computer-readable medium of claim 13 further comprising sequences of instructions for performing the steps of: storing in said data block entries that identify a set of transactions that have updated said data block, said entries including commit times for any transaction in said set of transactions that is committed; and storing in said data block a commit time value specified in an entry of said entries when the entry is to be overwritten; wherein the step of determining said include-time value includes determining said include-time value based on said commit time value.
Claim 19
Dependent Claim
80 words
The computer-readable medium of claim 15 wherein: the computer-readable medium further includes sequences of instructions for performing the step of determining whether the entry to be overwritten is the only entry of said entries associated with a committed transaction; and the step of storing in said data block a commit time value specified in an entry is performed in response to determining that the entry to be overwritten is the only entry of said entries associated with a committed transaction.
Claim 20
Dependent Claim
73 words
The computer-readable medium of claim 13 further comprising sequences of instructions for performing the steps of: reconstructing said data block by applying one or more undo records to said data block; wherein said version of said data item is the version of said data item in said reconstructed data block; and wherein the step of determining said include-time value includes determining said include-time value based on data stored in said reconstructed data block.
References Cited (Backward Citations)
US5559991A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-07 | 2002-03-09 | 2002-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-07 | 2006-03-09 | 2006-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-07 | 2010-03-09 | 2010-09-08 | $7700.00 | Window Closed / Lapsed |