Database management system for controlling concurrent access to a database

Claim 8

In a program-controlled system having a database including at least one relation, a method of assuring that the data of said relation that are accessible to each of a plurality of contemporaneously active database transactions are unchanged by any transaction other than said each transaction, said plurality of transactions comprising sets of operations on said relation and comprising at most one update transaction including write access to said relation, said method comprising the steps of storing a plurality of versions of said relation, storing in an access dictionary a plurality of access blocks each defining the database location of an associated one of said plurality of relation versions, defining one of said plurality of relation versions as current, storing in a relation dictionary a plurality of relation blocks each associated with one of said plurality of database transactions and defining one of said plurality of access blocks such that as each of said plurality of database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of access blocks defining the database location of the one of said plurality of relation versions then defined as current, permitting access to said relation in said database by each of said plurality of database transactions only via the relation block associated with that database transaction, for said at most one update transaction, storing a new access block in said access dictionary defining a new database location to be used for storing a new relation version, modifying the relation block associated with said at most one update transaction to define said new access block, storing said new relation version in said new database location, redefining as old the one of said plurality of relation versions then defined as current and defining said new relation version as current.

Claim 9

In a program-controlled system having a database including at least one relation, a method of assuring that the data of said relation that are accessible to each of a plurality of contemporaneously active database transactions are unchanged by any transaction other than said each transaction, said plurality of transactions comprising sets of operations on said relation and comprising at most one update transaction including write access to said relation, said method comprising the steps of storing a plurality of versions of said relation, storing in an access dictionary a plurality of access blocks each defining the database location of an associated one of said plurality of relation versions, defining one of said plurality of relation versions as current, storing in a relation dictionary a plurality of relation blocks each associated with one of said plurality of database transactions and defining one of said plurality of access blocks such that as each of said plurality of database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of access blocks defining the database location of the one of said plurality of relation versions then defined as current, permitting access to said relation in said database by each of said plurality of database transactions only via the relation block associated with that database transaction, for said at most one update transaction, storing a new access block in said access dictionary defining a new database location to be used for storing a new relation version, modifying the relation block associated with said at most one update transaction to define said new access block, storing said new relation version in said new database location, redefining as old the one of said plurality of relation versions then defined as current and defining said new relation version as current.

Claim 10

A method in accordance with claim 5 wherein said step of storing a plurality of versions of said relation comprises the steps of allocating a head block for each of said plurality of relation versions, storing each of said plurality of relation versions in at least one data block and for each of said plurality of relation versions, storing at least one index entry in the head block for that relation version, each of said index entries defining the database location of a data block storing a portion of that relation version and wherein said step of storing said new relation version in said new database location comprises the steps of allocating a head block for said new relation version, storing said new relation version in at least one data block and storing at least one index entry in the head block for said new relation version defining the database location of said at least one data block storing said new relation version.

Claim 11

A method in accordance with claim 6 in which each of the access blocks stored in said access dictionary defines the database location of a relation version by defining the database location of the head block for that relation version.

Claim 12

A method in accordance with claim 7 wherein said step of storing said new relation version in at least one data block comprises the steps of copying into a new data block a data block storing a portion of the one of said plurality of relation versions then defined as current, which portion is to be updated by said at most one update transaction and modifying said new data block.

Claim 13

A method in accordance with claim 8 further comprising the step of storing a data duplication control bit of a predetermined logic value in each index entry of the head block of the one of said plurality of relation versions then defined as current when that index entry defines a copied data block.

Claim 15

A method in accordance with claim 9 further comprising including in each of the access blocks stored in said access dictionary a user count representing the number of said plurality of database transactions which access the relation version defined by that access block, deallocating each access block when the user count of that access block is reduced to zero only when that access block was stored prior to the storage of the access block defining the database location of the one of said plurality of relation versions then defined as current, for a given deallocated access block, testing the data duplication control bit of each index entry of the head block defined by said given access block and of each index entry of the head block defined by the immediately previously stored allocated access block, deallocating a data block defined by a given index entry of said head block defined by said given access block when the data duplication control bit of said given index entry and the data duplication control bit of a corresponding index entry of said head block defined by said immediately previously stored allocated access block are both said predetermined logic value and storing a data duplication control bit of said predetermined logic value in said last-mentioned index entry whenever the data duplication control bit of said last-mentioned index entry is not said predetermined logic value and the data duplication control bit of said given index entry is said predetermined logic value and deallocating said head block defined by said given deallocated access block.

Claim 16

A method in accordance with claim 10 further comprising the step of permitting access to said relation in said database outside of a transaction via the access block defining the database location of the one of said plurality of relation versions then defined as current.

Claim 23

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a relation in a database, said arrangement comprising means for storing a plurality of versions of said relation representing modifications of said relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of active database transactions and defining one of said plurality of relation versions and means for permitting access by each of said plurality of active database transactions only to the one of said plurality of relation versions defined by the relation block associated with that database transaction.

Claim 24

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a relation in a database, said arrangement comprising means for storing a plurality of versions of said relation representing modifications of said relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of active database transactions and defining one of said plurality of relation versions and means for permitting access by each of said plurality of active database transactions only to the one of said plurality of relation versions defined by the relation block associated with that database transaction.

Claim 25

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a relation in a database, said arrangement comprising means for storing a plurality of versions of said relation representing modifications of said relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, access dictionary means for storing a plurality of access blocks each defining the database location of an associated one of said plurality of relation versions, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of active database transactions and defining one of said plurality of access blocks and means for permitting access by each of said plurality of active database transactions only to the one of said plurality of relation versions having its database location defined by the access block defined by the relation block associated with that database transaction.

Claim 26

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a relation in a database, said arrangement comprising means for storing a plurality of versions of said relation representing modifications of said relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, access dictionary means for storing a plurality of access blocks each defining the database location of an associated one of said plurality of relation versions, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of active database transactions and defining one of said plurality of access blocks and means for permitting access by each of said plurality of active database transactions only to the one of said plurality of relation versions having its database location defined by the access block defined by the relation block associated with that database transaction.

Claim 27

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a relation in a database, said arrangement comprising means for storing a plurality of versions of said relation representing modifications of said relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, access dictionary means for storing a plurality of access blocks each defining the database location of an associated one of said plurality of relation versions, means for defining one of said plurality of relation versions as current, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of active database transactions and defining one of said plurality of access blocks such that as each of said plurality of active database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of access blocks defining the database location of the one of said plurality of relation versions then defined as current, means for permitting access by each of said plurality of active database transactions only to the one of said plurality of relation versions having its database location defined by the access block defined by the relation block associated with that database transaction.

Claim 28

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a relation in a database, said arrangement comprising means for storing a plurality of versions of said relation representing modifications of said relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, access dictionary means for storing a plurality of access blocks each defining the database location of an associated one of said plurality of relation versions, means for defining one of said plurality of relation versions as current, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of active database transactions and defining one of said plurality of access blocks such that as each of said plurality of active database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of access blocks defining the database location of the one of said plurality of relation versions then defined as current, means for permitting access by each of said plurality of active database transactions only to the one of said plurality of relation versions having its database location defined by the access block defined by the relation block associated with that database transaction.

Claim 29

An arrangement in accordance with claims 16, 17, or 18 wherein said means for storing a plurality of versions of said relation further comprises means for allocating a head block for each of said plurality of relation versions, means for storing each of said plurality of relation versions in at least one data block and means for storing for each of said plurality of relation versions at least one index entry in the head block for that relation version, each of said index entries defining the database location of a data block storing a portion of that relation version.

Claim 30

In a program-controlled system having a database including at least one relation, an arrangement for assuring that the data of said relation that are accessible to each of a plurality of contemporaneously active database transactions are unchanged by any transaction other than said each transaction, said plurality of trasactions comprising sets of operations on said relation and comprising at most one update transaction including write access to said relation, said arrangement comprising means for storing a plurality of versions of said relation, access dictionary means for storing a plurality of access blocks each defining the database location of an associated one of said plurality of relation versions, means for defining one of said plurality of relation versions as current, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of database transactions and defining one of said plurality of access blocks such that as each of said plurality of database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of access blocks defining the database location of the one of said plurality of relation versions then defined as current, means for permitting access to said relation in said database by each of said plurality of database transactions only via the relation block associated with that database trasaction, means for storing for said at most one update transaction a new access block in said access dictionary means defining a new database location to be used for storing a new relation version, means for modifying the relation block associated with said at most one update transaction to define said new access block, means for storing said new relation version in said new database location, means for redefining as old the one of said plurality of relation versions then defined as current and means for defining said new relation version as current.

Claim 31

In a program-controlled system having a database including at least one relation, an arrangement for assuring that the data of said relation that are accessible to each of a plurality of contemporaneously active database transactions are unchanged by any transaction other than said each transaction, said plurality of trasactions comprising sets of operations on said relation and comprising at most one update transaction including write access to said relation, said arrangement comprising means for storing a plurality of versions of said relation, access dictionary means for storing a plurality of access blocks each defining the database location of an associated one of said plurality of relation versions, means for defining one of said plurality of relation versions as current, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of database transactions and defining one of said plurality of access blocks such that as each of said plurality of database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of access blocks defining the database location of the one of said plurality of relation versions then defined as current, means for permitting access to said relation in said database by each of said plurality of database transactions only via the relation block associated with that database trasaction, means for storing for said at most one update transaction a new access block in said access dictionary means defining a new database location to be used for storing a new relation version, means for modifying the relation block associated with said at most one update transaction to define said new access block, means for storing said new relation version in said new database location, means for redefining as old the one of said plurality of relation versions then defined as current and means for defining said new relation version as current.

Claim 32

An arrangement in accordance with claim 20 wherein said means for storing a plurality of versions of said relation further comprises means for allocating a head block for each of said plurality of relation versions, means for storing each of said plurality of relation versions in at least one data block and means for storing for each of said plurality of relation versions at least one index entry in the head block for that relation version, each of said index entries defining the database location of a data block storing a portion of that relation version and wherein said means for storing said new relation version in said new database location further comprises means for allocating a head block for said new relation version, means for storing said new relation version in at least one data block and means for storing at least one index entry in the head block for said new relation version defining the database location of said at least one data block storing said new relation version.

Claim 33

An arrangement in accordance with claim 21 in which each of the access blocks stored in said access dictionary means defines the database location of a relation version by defining the database location of the head block for that relation version.

Claim 34

An arrangement in accordance with claim 22 wherein said means for storing said new relation version in at least one data block further comprises means for copying into a new data block a data block storing a portion of the one of said plurality of relation versions then defined as current, which portion is to be updated by said at most one update transaction and means for modifying said new data block.

Claim 35

An arrangement in accordance with claim 23 further comprising means for storing a data duplication control bit of a predetermined logic value in each index entry of the head block of the one of said plurality of relation versions then defined as current when that index entry defines a copied data block.

Claim 36

An arrangement in accordance with claims 20, 21, 22, 23 or 24 further comprising means for including in each of the access blocks stored in said access dictionary means a user count representing the number of said plurality of database transactions which access the relation version defined by that access block and means for deallocating each access block when the user count of that access block is reduced to zero only when that access block was stored prior to the storage of the access block defining the database location of the one of said plurality of relation versions then defined as current.

Claim 37

An arrangement in accordance with claim 24 further comprising means for including in each of the access blocks stored in said access dictionary means a user count representing the number of said plurality of database transactions which access the relation version defined by that access block, means for deallocating each access block when the user count of that access block is reduced to zero only when that access block was stored prior to the storage of the access block defining the database location of the one of said plurality of relation versions then defined as current, means for testing, for a given deallocated access block, the data duplication control bit of each index entry of the head block defined by said given access block and of each index entry of the head block defined by the immediately previously stored allocated access block, means for deallocating a data block defined by a given index entry of said head block defined by said given access block when the data duplication control bit of said given index entry and the data duplication control bit of a corresponding index entry of said head block defined by said immediately previously stored allocated across block are both said predetermined logic value, means for storing a data duplication control bit of said predetermined logic value in said last-mentioned index entry whenever the data duplication control bit of said last-mentioned index entry is not said predetermined logic value and the data duplication control bit of said given index entry is said predetermined logic value and means for deallocating said head block defined by said given deallocated access block.

Claim 38

An arrangement in accordance with claim 25 further comprising means for permitting access to said relation in said database outside of a transaction via the access block defining the database location of the one of said plurality of relation versions then defined as current.

Claim 39

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a database comprising a plurality of relations, said arrangement comprising means for storing for each of said plurality of relations a plurality of versions of that relation representing modifications of that relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, relation dictionary means for storing for each of said plurality of active database transactions one relation block associated with that database transaction for each of said plurality of relations to be accessed by that database transaction, each relation block stored for a given relation defining one of the plurality of versions of said given relation and means for permitting access, for each of said plurality of relations, by each of said plurality of active database transactions only to the one of the plurality of versions of that relation defined by the relation block associated with that database transaction for that relation.

Claim 40

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a database comprising a plurality of relations, said arrangement comprising means for storing for each of said plurality of relations a plurality of versions of that relation representing modifications of that relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, relation dictionary means for storing for each of said plurality of active database transactions one relation block associated with that database transaction for each of said plurality of relations to be accessed by that database transaction, each relation block stored for a given relation defining one of the plurality of versions of said given relation and means for permitting access, for each of said plurality of relations, by each of said plurality of active database transactions only to the one of the plurality of versions of that relation defined by the relation block associated with that database transaction for that relation.

Claim 41

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a database comprising a plurality of relations, said arrangement comprising means for storing for each of said plurality of relations a plurality of versions of that relation representing modifications of that relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, access dictionary means for storing a plurality of access blocks each defining the database location of an associated one of the plurality of versions of one of said plurality of relations, relation dictionary means for storing for each of said plurality of active database transactions one relation block associated with that database transaction for each of said plurality of relations to be accessed by that database transaction, each relation block defining one of said plurality of access blocks and means for permitting access, for each of said plurality of relations, by said plurality of active database transactions only to the one of the plurality of versions of that relation having its database location defined by the access block defined by the relation block associated with that database transaction for that relation.

Claim 42

An arrangement for controlling access by each of a plurality of contemporaneously active database transactions to a database comprising a plurality of relations, said arrangement comprising means for storing for each of said plurality of relations a plurality of versions of that relation representing modifications of that relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, access dictionary means for storing a plurality of access blocks each defining the database location of an associated one of the plurality of versions of one of said plurality of relations, relation dictionary means for storing for each of said plurality of active database transactions one relation block associated with that database transaction for each of said plurality of relations to be accessed by that database transaction, each relation block defining one of said plurality of access blocks and means for permitting access, for each of said plurality of relations, by said plurality of active database transactions only to the one of the plurality of versions of that relation having its database location defined by the access block defined by the relation block associated with that database transaction for that relation.

Claim 43

An arrangement for each of a plurality of contemporaneously active database transactions to a database comprising a plurality of relations, said arrangement comprising means for storing for each of said plurality of relations a plurality of versions of that relation representing modifications of that relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, access dictionary means for storing a plurality of access blocks and each defining the database location of an associated one of the plurality of versions of one of said plurality of relations, dynamic dictionary means for storing one dynamic block for each of said plurality of relations, and dynamic block stored for each relation including an access block pointer defining one of said plurality of access blocks, relation dictionary means for storing for each of said plurality of active database transactions one relation block associated with that database transaction for each of said plurality of relations to be accessed by that database transaction, each relation block defining one of said plurality of access blocks such that as each of said plurality of active database transactions is begun, the relation block stored for a given relation includes the access block pointer of the dynamic block for said given relation and means for permitting access, for each of said plurality of relations, by each of said plurality of active database transactions only to the one of said plurality of versions of that relation defined by the relation block associated with that database transaction for that relation.

Claim 44

An arrangement for each of a plurality of contemporaneously active database transactions to a database comprising a plurality of relations, said arrangement comprising means for storing for each of said plurality of relations a plurality of versions of that relation representing modifications of that relation resulting from previously executed database transactions and at most one of said plurality of active database transactions, access dictionary means for storing a plurality of access blocks and each defining the database location of an associated one of the plurality of versions of one of said plurality of relations, dynamic dictionary means for storing one dynamic block for each of said plurality of relations, and dynamic block stored for each relation including an access block pointer defining one of said plurality of access blocks, relation dictionary means for storing for each of said plurality of active database transactions one relation block associated with that database transaction for each of said plurality of relations to be accessed by that database transaction, each relation block defining one of said plurality of access blocks such that as each of said plurality of active database transactions is begun, the relation block stored for a given relation includes the access block pointer of the dynamic block for said given relation and means for permitting access, for each of said plurality of relations, by each of said plurality of active database transactions only to the one of said plurality of versions of that relation defined by the relation block associated with that database transaction for that relation.

Claim 45

In a program-controlled system having a database including at least one relation, a method of assuring that the data of said relation that are accessible to each of a plurality of contemporaneously active database transactions are unchanged by any transaction other than said each transaction, said plurality of transactions comprising sets of operations on said relation and comprising at most one update transaction including write access to said relation, said method comprising the steps of storing a plurality of versions of said relation, defining one of said plurality of relation versions as current, storing in a relation dictionary a plurality of relation blocks each associated with one of said plurality of database transactions and defining one of said relation versions such that as each of said plurality of database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of relation versions then defined as current, permitting access to said relation in said database by each of said plurality of database transactions only via the relation block associated with that database transaction, for said at most one update transaction, modifying the relation block associated with that transaction to define a new relation version, storing said new relation version in said database, redefining as old the one of said plurality of relation versions then defined as current and defining said new relation version as current.

Claim 46

In a program-controlled system having a database including at least one relation, a method of assuring that the data of said relation that are accessible to each of a plurality of contemporaneously active database transactions are unchanged by any transaction other than said each transaction, said plurality of transactions comprising sets of operations on said relation and comprising at most one update transaction including write access to said relation, said method comprising the steps of storing a plurality of versions of said relation, defining one of said plurality of relation versions as current, storing in a relation dictionary a plurality of relation blocks each associated with one of said plurality of database transactions and defining one of said relation versions such that as each of said plurality of database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of relation versions then defined as current, permitting access to said relation in said database by each of said plurality of database transactions only via the relation block associated with that database transaction, for said at most one update transaction, modifying the relation block associated with that transaction to define a new relation version, storing said new relation version in said database, redefining as old the one of said plurality of relation versions then defined as current and defining said new relation version as current.

Claim 47

A method in accordance with claim 31 further comprising the step of deferring execution of a second update transaction including write access to said relation, until said at most one update transaction is completed.

Claim 48

In a program-controlled system having a database including at least one relation, an arrangement for assuring that the data of said relation that are accessible to each of a plurality of contemporaneously active database transactions are unchanged by any transaction other than said each transaction, said plurality of transactions comprising sets of operations on said relation and comprising at most one update transaction including write access to said relation, said arrangement comprising means for storing a plurality of versions of said relation, means for defining one of said plurality of relation versions as current, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of database transactions and defining one of said relation versions such that as each of said plurality of database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of relation versions then defined as current, means for permitting access to said relation in said database by each of said plurality of database transactions only via the relation block associated with that database transaction, means for modifying the relation block associated with said at most one update transaction to define a new relation version, means for storing said new relation version in said database, means for redefining as old the one of said plurality of relation versions then defined as current and means for defining said new relation version as current.

Claim 49

In a program-controlled system having a database including at least one relation, an arrangement for assuring that the data of said relation that are accessible to each of a plurality of contemporaneously active database transactions are unchanged by any transaction other than said each transaction, said plurality of transactions comprising sets of operations on said relation and comprising at most one update transaction including write access to said relation, said arrangement comprising means for storing a plurality of versions of said relation, means for defining one of said plurality of relation versions as current, relation dictionary means for storing a plurality of relation blocks each associated with one of said plurality of database transactions and defining one of said relation versions such that as each of said plurality of database transactions is begun a relation block associated with that database transaction is stored defining the one of said plurality of relation versions then defined as current, means for permitting access to said relation in said database by each of said plurality of database transactions only via the relation block associated with that database transaction, means for modifying the relation block associated with said at most one update transaction to define a new relation version, means for storing said new relation version in said database, means for redefining as old the one of said plurality of relation versions then defined as current and means for defining said new relation version as current.

Claim 50

An arrangement in accordance with claim 33 further comprising means for deferring execution of a second update transaction including write access to said relation, until said at most one update transaction is completed.