Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-06-10
2001-05-22
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06237001
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to accessing stored data in a distributed database environment, and more specifically, to a method and apparatus for determining which version of a data item to provide to a transaction that requests the data item.
BACKGROUND OF THE INVENTION
In typical database systems, users store, update and retrieve information by submitting commands or statements to a database application. To be correctly processed, the statements must comply with the database language that is supported by the database application. One popular database language is known as Structured Query Language (SQL).
A logical unit of work that is comprised of one or more database language statements is referred to as a transaction. When multiple users share a database system, it is impractical to allow only one transaction to execute at a time. However, when many transactions are allowed to execute at the same time, the issue of consistency arises. Transactional database management systems provide a special statement—“commit”—which a user or program submits to delineate the statements that make up a transaction.
To ensure predictable and reproducible results, techniques have been developed which protect concurrently executing transactions from interacting with one another in uncontrolled ways. Transactions are designed to make database changes in such a way that the database, as a whole, moves from one consistent state to another.
Not only must transactions leave the database in a consistent state upon completion, but transactions must also see the database in a consistent state when they begin. This condition is difficult to satisfy because there may be concurrently executing transactions, each of which may be causing a temporary inconsistency visible only within that single transaction. Consequently, transactions must not be able to see the changes made by concurrently executing transactions until those transactions commit (i.e. terminate and make their changes permanent).
One approach to ensure that transactions do not see changes made by concurrently executing transactions is to prevent transactions from reading a data item that has been updated until the transaction that updated the data item commits. However, this approach reduces the concurrency in the system by causing transactions that wish to read data items (readers) to wait for transactions that have written to data items (writers) to commit.
An alternate approach to ensure that transactions see a consistent view of the database is to provide a mechanism that allows a reader transaction to see a version of the data item that does not include the updates made by any uncommitted transaction. However, in systems that provide a less-than-newest version of a data item, it is not always apparent which versions of a data item can and cannot be supplied to a transaction. Further, among those versions of a data item that can be supplied to a transaction, some versions will consume more overhead to supply than other versions.
Based on the foregoing, it is desirable to provide a mechanism for determining which versions of a data item may be supplied to a transaction. It is further desirable to provide a mechanism that selects the versions of data items to supply to transactions in a way that reduces the overhead required to supply the version of the data item. Specifically, it is desirable to select versions that require less overhead to construct, while still ensuring that the versions seen are recent enough.
SUMMARY OF THE INVENTION
According to one aspect of the invention, a method for is provided for selecting a version of a data item to be provided to a transaction executing on a distributed database system. The method includes the steps of determining version criteria based on which location of a plurality of locations in the distributed database system is associated with the data item and which location of the plurality of locations in the distributed database system is the location at which the transaction is executing. A version of the data item to be provided to the transaction is selected based upon the version criteria.
According to another aspect of the invention, the method includes the step of generating a MUST SEE time and a CANNOT SEE time for each of the plurality of locations. In this situation, the step of selecting, based upon the version criteria, a version of the data item to be provided to the transaction, includes the step of selecting, based upon a particular MUST SEE time and a particular CANNOT SEE time for the location associated with the data item, a version of the data item to be provided to the transaction.
According to yet another aspect of the invention, the step of determining version criteria includes the step of determining a base snapshot time for the location where the transaction is executing and a delta snapshot time for the location associated with the data item. In this situation, the step of selecting, based upon the version criteria, a version of the data item to be provided to the transaction includes the step of selecting, based upon the base snapshot time and the delta snapshot time, a version of the data item to be provided to the transaction.
REFERENCES:
patent: 5247664 (1993-09-01), Thomson et al.
patent: 5280612 (1994-01-01), Lorie et al.
patent: 5287496 (1994-02-01), Chen et al.
patent: 5327556 (1994-07-01), Mohan et al.
patent: 5333303 (1994-07-01), Mohan
patent: 5701480 (1997-12-01), Raz
patent: 5729738 (1998-03-01), Watanabe et al.
patent: 5781910 (1998-07-01), Gostanian et al.
patent: 5826270 (1998-10-01), Rutkowski et al.
patent: 5835757 (1998-11-01), Oulid-Aissa et al.
patent: 5884327 (1999-03-01), Cotner et al.
patent: 5920857 (1999-07-01), Rishe et al.
patent: 5946698 (1999-08-01), Lomet
Bamford Roger J.
Klots Boris
Becker Edward A.
Black Thomas
Do Thuy
Hickman Brian D.
Hickman Palermo & Truong & Becker LLP
LandOfFree
Managing access to data in a distributed database environment does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Managing access to data in a distributed database environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Managing access to data in a distributed database environment will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2555065