Multiple version database concurrency control system

In a computer-implemented concurrent transaction and read-only query processing system in which at least two versions of a database are maintained during a present version period, said database including a plurality of data records that are updated by said transactions and read by said queries, at least two versions of each data record of said plurality of data records being distributed among said database versions, each said database version(i) consisting essentially of said data records existing at the beginning of a corresponding said version period (i), each said version period (i) being the time interval between one said database version (i) and the next subsequent said database version (i+1), said versions including a present version and a stable version, a method for concurrency control comprising the underordered steps of:

• (a) maintaining a dynamic Uncommitted List (UL) of all said transactions that are uncommitted;
• (b) maintaining a Non-Stable and Uncommitted List (NSUL) of all said transactions that are either uncommitted or were committed during said present version period;
• (c) directing all said read-only queries that arrive during said present version period to said data records in said stable database version;
• and
• (d) refreshing said present database version by performing the steps of
• (d.1) setting a refresh time t after all said read-only queries are terminated,
• (d.2) creating a new version of said database containing said data records existing at said refresh time t.
• (d.3) resetting said NSUL to equal said UL, and
• (d.4) initiating a new version period at said refresh time t by assigning said present database version to be the new stable database version, whereby database atomicity is maintained by using said stable database version for read-only query processing without lock conflict or transaction rollback.

In a distributed computer-implemented concurrent transaction and query processing system having a plurality of nodes in each of which are maintained portions of up to N versions of a distributed database, said distributed database including a plurality of data records distributed among said nodes, each data record of said plurality of data records being updated by said transactions and read by said queries, a plurality of versions of each said data record being distributed among said database versions, each said database version (i) at each node consisting essentially of the version (i) of said data records existing at said each node at the beginning of a corresponding said version period (i) for each said node, each said version period (i) for said each node being the time interval between one said database version (i) and the next subsequent said database version (i+1) for said each node, said database versions including a present database version (v), a present stable database version (v-1) and an oldest database version (v-N+2), said nodes having both original and received transactions and queries, wherein N is a positive integer greater than 2, a method for concurrency control comprising the unordered steps of:

• (a) maintaining within each said node a dynamic Uncommitted List (UL) of all said transactions that are uncommitted within said each node;
• (b) maintaining for said present version period (v) within each said node a present version (v) of a Non-Stable and Uncommitted List (NSUL) of all said transactions that are either uncommitted or were committed within said each node no earlier than during said present version period (v) for said each node;
• (c) maintaining within each node a dynamic Precommit List (PL) of all precommitted transactions involving said each node;
• (d) directing within each node all said queries that originate during said present version period (v) of the query originating node to said data records of said present stable database version (v-1) within said each node;
• (e) refreshing said present database version (v) by performing within each node the steps of
• (e.1) setting a refresh time t after all said read-only queries that arrived at said each node during said oldest version period (v-N+2 are terminated,
• (e.2) creating a new version (v+1) of said NSUL containing said transactions listed at said refresh time t in said dynamic UL within said each node, and
• (e.3) initiating a new version period (v+1) within said each node at said refresh time t by assigning said present database version (v) to be the new present stable database version (v) and creating a new present database version v+1);
• (f) aborting, within said each node, every said transaction having an originating node version period earlier than said present version period (v) in said each;
• and
• (g) aborting within said each node all said read-only queries directed to a database version represented in said dynamic PL for said each node.

A computer-implemented concurrent transaction and query processing system comprising:

• multi-version database means for storing up to N versions of a database during a present version period (v), said database including a plurality of data records that are updated by said transactions and read by said queries, a plurality of versions of each data record of said plurality of data records being distributed among said database versions, each said database version (i) consisting essentially of said data records existing at the beginning of a corresponding said version period (i), each said version period (i) being the time interval between one said database version (i) and the next subsequent said database version (i+1), said database versions including a present database version (v) and a present stable database version (v-1);
• Uncommitted List (UL) means coupled to said multi-version database means for identifying all uncommitted transactions;
• Non-Stable and Uncommitted List (NSUL) means coupled to said multi-version database means for identifying all said transactions that are either uncommitted or were committed no earlier than during said present version period (v);
• record accession means coupled to said multi-version database means for locating each said data record version and for identifying the transaction that created said each data record version;
• version initiation means coupled to said multi-version database means for starting a new version period by assigning said present database version (v) to be the new present stable database version (v);
• and
• garbage collection means for eliminating superfluous database records in response to an update by a transaction to a data record written by a previous committed transaction listed in said NSUL.

A computer-implemented concurrent transaction and query processing system comprising:

• multi-version database means for storing two versions of a database, said database including a plurality of data records that are updated by said transactions and ready by said queries, up to two versions of each data record of said plurality of data records being distributed among said two database versions, each said database version (i) consisting essentially of said data records existing at the beginning of a corresponding said version period (i), each said version period (i) being the time interval between one said database version (i) and the next subsequent said database version (i+1), said data record versions including a present data record version and a present stable data record version;
• Uncommitted List (UL) means coupled to said multi-version database means for identifying all uncommitted transactions;
• Non-Stable and Uncommitted List (NSUL) means coupled to said multi-version database means for identifying all said transactions that are either uncommitted or were committed during said present version period;
• record accession means coupled to said multi-version database means for locating each said record version and for identifying the transaction that created said each record version;
• version initiation means coupled to said multi-version database means for starting a new version period by assigning said present data record version to be the new present stable data record version;
• and
• garbage collection means for eliminating superfluous database records in response to an update by a transaction to a data record written by a previous committed transaction listed in said NSUL.