Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-05-13
2001-02-20
Alam, Hosain T. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S960000, C714S001000, C714S002000
Reexamination Certificate
active
06192377
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to database systems, and more specifically, to a method and apparatus for determining whether a transaction in a database system can use a version of a data item.
BACKGROUND OF THE INVENTION
In typical database systems, users store, update and retrieve information by submitting commands to a database application. To be correctly processed by the database application, the commands must comply with the database language that is supported by the database application. One popular database language is known as Structured Query Language (SQL).
In the context of database systems, a transaction is a logical unit of work that is comprised of one or more database language statements. When a database system executes a transaction, the transaction may read or update a data item that was written or updated in response to the execution of previous transactions. Consequently, the results returned by the database system in response to executing any given transaction are typically dictated by changes made by a set of previously executed transactions. The term “data item” is used herein to refer to any logical data type. An example of a logical data type is a row in a database, where a row is an exclusive set of one or more associated data elements.
In contemporary database systems, copies of data items contained in the database are often stored in a volatile memory which requires less time to access than non-volatile memory to improve transaction processing performance. Different versions of the data item are reconstructed by applying one or more undo records to the copies of the data item. Sometimes, multiple copies of a data item in the database are maintained in volatile memory so that concurrently executing transactions can simultaneously access different versions of the data item.
Because each transaction must see a database in a consistent state when it begins executing and must also leave the database in a consistent state when it completes processing, not all versions of a data item can necessarily be used by a transaction. Some versions of a data item may not contain updates which must be seen by a transaction for that transaction to see a consistent view of that data item. On the other hand, other versions of the data item may contain updates which cannot be seen by the transaction. Hence, in situations where multiple versions of a data item are available to transactions, access to the versions of a data item by transactions must be managed so that database consistency is maintained.
One approach for managing the execution of transactions to maintain database consistency involves processing transactions in what is referred to herein as “Consistent Read Mode”. Consistent Read Mode is characterized by two rules. First, every statement executed by a Consistent Read Mode transaction sees only (1) changes that were committed to the database by a particular set of committed transactions and (2) changes made by prior statements of the transaction itself. The set of transactions whose changes are visible to a statement is referred to as the statement's “snapshot set.” The ability to execute transactions in consistent read mode allows transactions that are issuing reads to be isolated from the changes made by excluded transactions that are concurrently issuing writes. Second, an updating transaction locks the rows it writes, and holds those locks until it commits. A lock on any given row may be held by only one transaction at a time. A row, as the term is used herein, refers to an exclusive set of one or more associated data elements.
A Consistent Read Mode transaction requires that statements see a “snapshot” of the database. A statement's snapshot includes all changes made by the transactions in its snapshot set, and none of the changes made by any transactions that are not in its snapshot set (“excluded transactions”). Transactions are sometimes assigned a snapshot time that corresponds to the state of a database at the time the transaction began executing. For consistent read, a transaction must see all changes made to a database by transactions that committed on or before the snapshot time of the transaction.
The concept of consistent read is described in more detail in U.S. patent application Ser. No. 08/842,169, entitled “SHARING SNAPSHOTS FOR CONSISTENT READS,” filed on Apr. 23, 1997, U.S. patent application Ser. No. 08/838, 967, entitled “TECHNIQUES FOR REDUCING THE NUMBER OF SNAPSHOTS OF A DATABASE,” filed on Apr. 23, 1997, and U.S. patent application Ser. No. 08/841,541, entitled “DYNAMIC SNAPSHOT SET ADJUSTMENT,” filed on Apr. 23, 1997, the contents of each of which are incorporated herein by reference.
As a simple example, suppose a transaction requires access to a version of a data block as it existed at time T
15
(i.e. the snapshot time of the transaction is T
15
). The transaction must be supplied a version of the data block that contains all changes made by transactions that committed on or before time T
15
, but no changes made by transactions that committed after time T
15
. Versions of the data block that include updates made by transactions that have not yet committed (except for the requesting transaction itself), or committed after time T
15
, cannot be used.
INCLUDE AND EXCLUDE TIMES
In some database systems, prior versions of a data block are reconstructed to allow a transaction to see a particular state of a database. For example, sometimes a prior version of a data block is reconstructed by applying undo records to remove changes made by another transaction. To support the reconstruction of prior versions of a data block, some database systems maintain an INCLUDE TIME and an EXCLUDE TIME for each version of a data block. The INCLUDE TIME specifies the commit time of the most recently committed transaction whose changes are included in the version of the data block. The EXCLUDE TIME specifies the commit time of the oldest transaction whose changes have been removed from the version of the data block. If a particular version of a data block is the most recent version of the data block, then the EXCLUDE TIME for that version is infinity, since no changes have been removed.
For example, suppose a first transaction causes a copy of a data block to be loaded into a volatile memory, updates the copy of the data block to create a new version (the “first version”) of the data block, and then commits at time T
10
. The INCLUDE TIME for this first version is set to time T
10
and the EXCLUDE TIME is set to infinity. Then a second transaction updates the same copy of the data block to create a second version of the data block and commits at time T
30
. The INCLUDE TIME of the second version of the data block is changed to time T
30
to reflect that the second version of the data block includes changes made by a transaction that committed at time T
30
, while the EXCLUDE TIME remains at infinity, since no changes have been removed from the second version of the data block. Any transaction having a snapshot time that is greater than or equal to the INCLUDE TIME of T
30
, can be supplied this second version of the data block because it contains all changes to the data block made by all transactions that committed at a time up to and including time T
30
.
Now suppose that a third transaction requires access to the data block as of time T
20
. The second version of the data block cannot be used in its current state because it contains an update made by the second transaction that committed at time T
30
. Therefore, the first version of the data block is reconstructed by removing the change made by the second transaction. Once the reconstruction operation is completed, the INCLUDE TIME of the new copy is changed to time T
10
, and the EXCLUDE TIME is changed to time T
30
, to reflect that this version of the data block contains the changes made by the first transaction that committed at time T
10
, and that the changes made by the second transaction, that committed at time T
30
, have been removed. Thus, any transaction
Ganesh Amit
Ngai Gary C.
Alam Hosain T.
Becker Edward A
Fleurantin Jean Bolte
Hickman Brian D.
Hickman Palermo & Truong & Becker LLP
LandOfFree
Method and apparatus for determing whether a transaction can... 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 apparatus for determing whether a transaction can..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determing whether a transaction can... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2607284