Patent US3596497A successfully refreshed from Google Patents.
Patent US5999931A successfully refreshed from Google Patents.
US5999931A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Concurrency control protocols for management of replicated data items in a distributed database system
Assignee: Nokia of America Corp
•
Filing: 1997-10-17
•
Granted: 1999-12-07
•
Expires: 2017-10-17
Abstract
Abstract The invention provides protocols for managing transactions operating on replicated data items at multiple physical sites in a distributed database system. The protocols make use of dynamically changing sets of data items referred to as "virtual sites" and a replication graph or other suitable globally consistent representation of the relationships between the transactions and the virtual sites. Illustrative embodiments of the invention include a static global serializability (SGS) protocol, a commit-oriented protocol (COP) and a multiversion optimistic protocol (MOP). The SGS protocol broadcasts the data access set of a given transaction to all physical sites, and applies the Thomas Write Rule (TWR) to write-write conflicts on secondary copies of data items. The COP protocol defers testing of the replication graph until a transaction is ready to commit, and each transaction is allowed to proceed at its origination site independently of other transactions that are executing at other sites. The MOP protocol uses two versions of each data item to ensure global multiversion serializability. The two versions are the current version of the data item, and a "last certified version" of the data item. All read-only transactions read the last certified version, and can therefore proceed without delay. The protocols ensure global serializability while substantially reducing communication overhead relative to conventional protocols.
Inventors
- 👤 Yuri Breitbart
- 👤 Henry F. Korth
- 👤 Abraham Silberschatz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 03:16
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/27; G06F16/273; G06F9/00; G06F9/06; G06F9/46; G06F9/466; G06F16/23; G06F16/2308; G06F16/2315; G06F16/2329; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99938
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
194 words
A method of managing a plurality of transactions in a distributed database system storing a plurality of data items and including a plurality of physical sites, each of the transactions originating at one of the physical sites, the plurality of transactions including a number of global transactions each being processed at multiple physical sites, the method including the steps of: specifying sets of data items such that a given set S i j of data items at a particular point in time includes replicated data items at a physical site s j that a given transaction T i has accessed from an initial operation up to the point in time; maintaining a representation of relationships between the transactions and the sets of data items; and permitting the transaction T i to enter a completed state even if T i has not finished updating all replicated data items in the sets of data items associated with T i , wherein T i and any sets of data items S i j associated therewith are removed from the representation when T i enters the completed state, such that consistency among the replicated data items is maintained.
Claim 2
Independent Claim
194 words
A method of managing a plurality of transactions in a distributed database system storing a plurality of data items and including a plurality of physical sites, each of the transactions originating at one of the physical sites, the plurality of transactions including a number of global transactions each being processed at multiple physical sites, the method including the steps of: specifying sets of data items such that a given set S i j of data items at a particular point in time includes replicated data items at a physical site s j that a given transaction T i has accessed from an initial operation up to the point in time; maintaining a representation of relationships between the transactions and the sets of data items; and permitting the transaction T i to enter a completed state even if T i has not finished updating all replicated data items in the sets of data items associated with T i , wherein T i and any sets of data items S i j associated therewith are removed from the representation when T i enters the completed state, such that consistency among the replicated data items is maintained.
Claim 3
Dependent Claim
71 words
The method of claim 1 wherein T i is in the completed state if T i is not preceded by any non-completed transaction in a local serialization order at a physical site s j at which T i executes, and (i) T i has executed its serialization point operation at each physical site at which it executes; or (ii) T i has committed at each physical site at which it executes.
Claim 4
Dependent Claim
86 words
The method of claim 1 wherein the representation includes a first set of identifiers for at least a subset of the transactions, a second set of identifiers for at least a subset of the sets of data items, and a connection between an identifier corresponding to the transaction T i and an identifier corresponding to the set S i j if a schedule of transaction operations includes a write operation by the transaction T i on a data item in the set S i j .
Claim 5
Dependent Claim
113 words
The method of claim 3 wherein the representation of the relationships between the transactions and the sets of data items is in the form of a graph, the graph including a first set of nodes corresponding to the first set of identifiers for the transactions, a second set of nodes corresponding to the second set of identifiers for the sets of data items, and a connection between a node corresponding to the transaction T i and a node corresponding to the set S i j if the schedule of the transaction operations includes a write operation by the transaction T i on a replicated data item in the set S i j .
Claim 6
Dependent Claim
49 words
The method of claim 1 wherein each of the transactions reads data items only at the physical site at which the transaction originates, and only transactions originating at a physical site at which a primary copy of a data item is located are permitted to update that data item.
Claim 7
Dependent Claim
69 words
The method of claim 1 further including the steps of: assigning a timestamp to transaction T i when T i submits an access set of data items; broadcasting the access set of data items to all physical sites in the system; and permitting T i to proceed to execution at its origination site if it is determined that the representation will be acyclic if T i proceeds to execution.
Claim 8
Dependent Claim
77 words
The method of claim 6 further including the steps of: when T i submits a write operation on a secondary copy of a data item, comparing the timestamp of T i to that of another transaction which executed the last write operation on the same data item; and executing the write operation of T i only if the T i timestamp is less than that of the transaction which executed the last write on the data item.
Claim 9
Dependent Claim
85 words
The method of claim 1 further including the steps of: permitting each transaction to proceed at its origination site independently of other transactions that are executing at other sites; when a given transaction T i submits a commit operation at its origination site, making tentative updates to the representation to include the transaction T i and its associated sets of data items; making the tentative changes permanent if the resulting representation is acyclic; and aborting transaction T i if the resulting representation is not acyclic.
Claim 10
Dependent Claim
68 words
The method of claim 1 further including the steps of: providing first and second versions of each of a plurality of data items in the system, the first version representing a current version of a given data item, and the second version representing a last certified version of the given data item; and permitting read-only transactions to read only the last certified version of the given data item.
Claim 11
Dependent Claim
45 words
The method of claim 9 wherein the last certified version of the given data item is a version written by a completed transaction T i such that any other completed transaction that writes the given data item precedes T i in a global serialization order.
Claim 12
Independent Claim
203 words
An apparatus for use in a distributed database system for storing a plurality of data items and controlling access to the data items at a plurality of physical sites configured to communicate over a network, comprising: at least one processor for managing a plurality of transactions involving the data items, each of the transactions originating at one of the physical sites, wherein the processor is operative to specify sets of data items such that a given set S i j of data items at a particular point in time includes replicated data items at a physical site s j that a given transaction T i has accessed from an initial operation up to the point in time; to maintain a representation of relationships between the transactions and the sets of data items; and to permit the transaction T i to enter a completed state even if T i has not finished updating all replicated data items in the sets of data items associated with T i , wherein T i and any sets of data items S i j associated therewith are removed from the representation when T i enters the completed state, such that consistency among the replicated data items is maintained.
Claim 13
Independent Claim
203 words
An apparatus for use in a distributed database system for storing a plurality of data items and controlling access to the data items at a plurality of physical sites configured to communicate over a network, comprising: at least one processor for managing a plurality of transactions involving the data items, each of the transactions originating at one of the physical sites, wherein the processor is operative to specify sets of data items such that a given set S i j of data items at a particular point in time includes replicated data items at a physical site s j that a given transaction T i has accessed from an initial operation up to the point in time; to maintain a representation of relationships between the transactions and the sets of data items; and to permit the transaction T i to enter a completed state even if T i has not finished updating all replicated data items in the sets of data items associated with T i , wherein T i and any sets of data items S i j associated therewith are removed from the representation when T i enters the completed state, such that consistency among the replicated data items is maintained.
Claim 14
Dependent Claim
71 words
The apparatus of claim 11 wherein T i is in the completed state if T i is not preceded by any non-completed transaction in a local serialization order at a physical site s j at which T i executes, and (i) T i has executed its serialization point operation at each physical site at which it executes; or (ii) T i has committed at each physical site at which it executes.
Claim 15
Dependent Claim
86 words
The apparatus of claim 11 wherein the representation includes a first set of identifiers for at least a subset of the transactions, a second set of identifiers for at least a subset of the sets of data items, and a connection between an identifier corresponding to the transaction T i and an identifier corresponding to the set S i j if a schedule of transaction operations includes a write operation by the transaction T i on a data item in the set S i j .
Claim 16
Dependent Claim
113 words
The apparatus of claim 13 wherein the representation of the relationships between the transactions and the sets of data items is in the form of a graph, the graph including a first set of nodes corresponding to the first set of identifiers for the transactions, a second set of nodes corresponding to the second set of identifiers for the sets of data items, and a connection between a node corresponding to the transaction T i and a node corresponding to the set S i j if the schedule of the transaction operations includes a write operation by the transaction T i on a replicated data item in the set S i j .
Claim 17
Dependent Claim
49 words
The apparatus of claim 11 wherein each of the transactions reads data items only at the physical site at which the transaction originates, and only transactions originating at a physical site at which a primary copy of a data item is located are permitted to update that data item.
Claim 18
Dependent Claim
73 words
The apparatus of claim 11 wherein the processor is further operative to assign a timestamp to transaction T i when T i submits an access set of data items; to broadcast the access set of data items to all physical sites in the system; and to permit T i to proceed to execution at its origination site if it is determined that the representation will be acyclic if T i proceeds to execution.
Claim 19
Dependent Claim
80 words
The apparatus of claim 16 wherein the processor is further operative, when T i submits a write operation on a secondary copy of a data item, to compare the timestamp of T i to that of another transaction which executed the last write operation on the same data item; and to execute the write operation of T i only if the T i timestamp is less than that of the transaction which executed the last write on the data item.
Claim 20
Dependent Claim
90 words
The apparatus of claim 11 wherein the processor is further operative to permit each transaction to proceed at its origination site independently of other transactions that are executing at other sites; when a given transaction T i submits a commit operation at its origination site, to make tentative updates to the representation to include the transaction T i and its associated sets of data items; to make the tentative changes permanent if the resulting representation is acyclic; and to abort transaction T i if the resulting representation is not acyclic.
Claim 21
Dependent Claim
71 words
The apparatus of claim 11 wherein the processor is further operative to provide first and second versions of each of a plurality of data items in the system, the first version representing a current version of a given data item, and the second version representing a last certified version of the given data item; and to permit read-only transactions to read only the last certified version of the given data item.
Claim 22
Dependent Claim
45 words
The apparatus of claim 19 wherein the last certified version of the given data item is a version written by a completed transaction T i such that any other completed transaction that writes the given data item precedes T i in a global serialization order.
References Cited (Backward Citations)
US4432057A
Cited
US5504900A
Cited
US5504899A
Cited
US5701480A
Cited
US5459871A
Cited
US5835766A
Cited
US5734817A
Cited
US5781910A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-06 | 2003-06-07 | 2003-12-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-06 | 2007-06-07 | 2007-12-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-06 | 2011-06-07 | 2011-12-07 | $7700.00 | Window Closed / Lapsed |