US5999931A — Concurrency control protocols for management of r…

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.

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

Concurrency control protocols for management of replicated data items in a distributed database system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag