# US 2004/0064439 A1 · Computer method and system for concurrency control using dynamic serialization ordering

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0064439 A1
- Document ID: US20040064439A1
- Status: Published application
- Kind: A1
- Application number: 10/653,455
- Filed: 2003-09-02
- Published: 2004-04-01
- Earliest claimed: 2002-09-13
- Assignees: Netezza Corporation
- Inventors: Foster D. Hinshaw; Craig S. Harris; Sunil K. Sarin
- Web page: https://patentgrep.com/patent/US20040064439A1

## CPC

- G06F 16/2315: {Optimistic concurrency control}
- G06F 16/2308: {Concurrency control (transaction processing G06F9/466)}
- Y10S 707/99938: Concurrency, e.g. lock management in shared database
- Y10S 707/99942: Manipulating data structure, e.g. compression, compaction, compilation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A mechanism controls concurrency among database transactions through the use of serial ordering relations. The ordering relations are computed dynamically in response to patterns of use. An embodiment of the present invention serializes a transaction that accesses a resource before a transaction that modifies the resource, even if the accessor starts after the modifier starts or commits after the modifier commits. A method of concurrency control for a database transaction in a distributed database system stores an intended use of a database system resource by the database transaction in a serialization graph. A serialization ordering is asserted between the database transaction and other database transactions based on the intended use of the database system resource by the database transaction. The serialization ordering is then communicated to a node in the distributed database system that needs to know the serialization ordering to perform concurrency control. Cycles in the serialization graph are detected based on the asserted serialization order and in order to break such cycles and ensure transaction serializability a database transaction is identified that is a member of a cycle in the serialization graph.

## Claims

### Claim 1

A method of establishing serialization ordering among database transactions in a database system, comprising:
given a database transaction, storing a representation of an intended use of a database resource by the database transaction;
asserting serialization ordering between the database transaction and other database transactions based upon a pattern of use of the database resource by the database transaction and the other database transactions.

### Claim 2 (depends on 1)

The method of establishing serialization ordering of claim 1, wherein asserting serialization ordering further comprises dynamically asserting serialization ordering between the database transaction and other database transactions based upon intended use of the database resource.

### Claim 3 (depends on 2)

The method of establishing serialization ordering of claim 2, wherein the intended use of the database resource includes at least one of: accessing state of the database resource and modifying the state of the database resource.

### Claim 4 (depends on 3)

The method of establishing serialization ordering of claim 3, wherein the serialization ordering between a first transaction accessing the state of the database resource and a second transaction modifying the state of the database resource is in the first transaction preceding the second transaction.

### Claim 5 (depends on 4)

The method of establishing serialization ordering of claim 4, wherein the serialization ordering imposed applies whether the first transaction accessed the state of the database resource temporally before or temporally after the second transaction modifies the state of the database resource.

### Claim 6 (depends on 3)

The method of establishing serialization ordering of claim 3, wherein the serialization ordering imposed when a first database transaction accesses or modifies the database resource and a second database transaction modifies or accesses the database resource is that the second database transaction waits for the first database transaction to complete.

### Claim 7 (depends on 1)

The method of establishing serialization ordering of claim 1, wherein storing the representation of the intended use of database resource further comprises:
creating a resource usage record; and
associating the resource usage record with the database transaction.

### Claim 8 (depends on 7)

The method of establishing serialization ordering of claim 7, wherein the resource usage record is released when the database transaction is aborted or rolled back.

### Claim 9 (depends on 7)

The method of establishing serialization ordering of claim 7, wherein the resource usage record is maintained for a period of time after the database transaction commits, and is not released until no serialization orderings can be created that would involve the committed database transaction in a cycle of serialization orderings.

### Claim 10 (depends on 1)

The method of establishing serialization ordering of claim 1, wherein the database resource includes at least one of the following: a record, a subset of records in a table identified by a qualifier on contents of records, and a table of records in a relational database system.

### Claim 11 (depends on 1)

The method of establishing serialization ordering of claim 1, wherein the database system operates in conjunction with serial ordering of database transactions, such that a first database transaction having a serialization ordering before a second database transaction can access versions of the database resource that existed before any modifications made by the second database transaction.

### Claim 12 (depends on 1)

The method of establishing serialization ordering of claim 1, wherein the use of the database resource comprises modifying the state of the database resource with a commutative operation.

### Claim 13 (depends on 12)

The method of establishing serialization ordering of claim 12, wherein the commutative operation is at least one of: addition, subtraction, multiplication and division.

### Claim 14 (depends on 12)

The method of establishing serialization ordering of claim 12, wherein no serialization ordering is imposed when a plurality of database transactions operate to modify the database resource using arithmetically commutative operations.

### Claim 15 (depends on 1)

The method of establishing serialization ordering of claim 1, wherein the serialization ordering imposed when a first database transaction commits before a second database transaction starts is that the first database transaction precedes the second database transaction.

### Claim 16 (depends on 1)

The method of establishing serialization ordering of claim 1, wherein the step of storing a representation of the use does not assert the serialization ordering when at least one of the following occurs: the database transaction guarantees that it does not intend to use any database resource in a way that would cause a modification to any database resource, the database transaction intends only to create or insert new resources, the database transaction modifying the database resource acquired the database resource in reverse mode, the use of the database resource does not require concurrency control, and the database resource can never be shared by another database transaction.

### Claim 17

A system for establishing serialization orderings among database transactions in a database system, comprising:
at least two transactions;
a representation of intended use of a database resource by the at least two transactions; and
a serialization graph storing an ordering between the at least two database transactions based upon a pattern of use of the database resource by the at least two database transactions.

### Claim 18 (depends on 17)

A system as claimed in claim 17 wherein the database system is a multi-versioning database system.
