<p>The book <a href="http://rads.stackoverflow.com/amzn/click/1558605088">Transactional Information Systems</a> by Weikum and Vossen covers quite a lot of the area, both in theoretical and practical terms, from different perspectives, not just transactions. It's about 1000 pages long, so will keep you busy for a weekend or two. On the other hand, it's nearly 10 years old, so there might be something more up-to-date available. Other books in the line include <em>Concurrency Control and Recovery in Database Systems</em> by Bernstein, P., Hadzilacos, V., and Goodman, N, Addison-Wesley, 1987, <em><a href="http://rads.stackoverflow.com/amzn/click/1558601902">Transaction Processing: Concepts and Techniques</a></em> by Jim Gray and Andreas Reuter, and <em><a href="http://rads.stackoverflow.com/amzn/click/1558606238">Principles of Transaction Processing</a></em> by Philip A. Bernstein and Eric Newcomer, 2009. I haven't seen the latter one, but being the most recent it could be a good place to start, although your solution may well be found in older texts. A trip to the library may be worthwhile.</p>

<p>A monumental text in this area is <em><a href="http://rads.stackoverflow.com/amzn/click/155860104X">Atomic Transactions</a></em> by Nancy Lynch et al. It presents a formal account and proofs of a number of the kinds of algorithms you are interested in. It's rather formal, and tedious, so may not be to your taste.</p>

<p>A lot of recent work is devoted to <a href="http://en.wikipedia.org/wiki/Software_transactional_memory">Software Transactional Memory</a>, which is applying the transaction ideas to multi-threaded applications. There are tens of publications on this topic each year: the wikipedia page provides plenty of references.</p>

CC BY-SA 2.5
2010-10-31T10:33:34.093Z
thanks dave, especially for the phrase "Software transactional memory", I hadn't come across this name
Nick Fortescue
CC BY-SA 2.5
2010-10-31T10:47:06.347Z
STM is a really hot topic in programming languages research these days. There's a race on to see whether STM or Actor-based programming models will be the basis of future concurrent (= all) programming languages.
Dave Clarke
CC BY-SA 2.5
2010-10-31T12:28:30.833Z
Besides STM, one particular keyword to look for inside these references is MVCC. It's used in most modern DBMSs: http://en.wikipedia.org/wiki/Multiversion_concurrency_control
Maverick Woo
CC BY-SA 2.5
2010-10-31T15:18:18.983Z
@supercooldave I'm not sure it's a race: I think future languages will have to support a bit of both to some degree or another.
Marc Hamann
CC BY-SA 2.5
2010-10-31T15:36:51.673Z
@Marc Harmann: metaphorically speaking.
Dave Clarke
CC BY-SA 2.5
2010-10-31T09:18:15.073Z
2010-10-31T10:19:36.603Z
2010-10-31T10:19:36.603Z
Dave Clarke
<p>A simplified classical database transaction can be viewed as:</p>

<ul>
<li>reading M items</li>
<li>performing some calculation based on those reads</li>
<li>writing some N results based on these calculations, which may include the elements originally read.</li>
</ul>

<p>When performing these transactions (concurrently) the <a href="http://en.wikipedia.org/wiki/ACID">ACID</a> properties need to be maintained.</p>

<p>Exactly the same requirements (N updates based on M reads transactionally) exist in other non-DBMS concurrent systems.</p>

<p>I'm interested in finding out what algorithms exist for performing/resolving these transactions, and what the relative strengths and weaknesses of these algorithms are. Could you recommend some reading? This could be books or online references/tutorials.</p>

<p>Clarification:</p>

<p>So for example, a naive algorithm might be each transaction taking a single global lock, in effect forcing single threading and removing concurrency. A slightly more complicated algorithm would be individual item read/write locks, with an ordering to avoid deadlock). Etc, etc. Is there a good source documenting various algorithms for solving this problem. Even an answer which only pointed to a single algorithm with it's strength and weaknesses would be useful.</p>

CC BY-SA 2.5
2010-10-31T09:06:53.260Z
This question certainly falls within the scope of this site. I would recommend writing a little more about the context in which you are working. At present it is rather general and open.
Dave Clarke
CC BY-SA 2.5
2010-10-31T09:19:14.000Z
Do you think it is worth rephrasing so it is precisely the database question? IE something like "I have a database which can be read and written to, and I want to be able to read and write transactionally with ACID properties. What algorithms exist for ensuring these properties"
Nick Fortescue
CC BY-SA 2.5
2010-10-31T09:51:32.073Z
Rephrasing the question may result in answers closer to what you are looking for, such as giving more details of the problem you are trying to solve; at present you only give hints. In any case, it sounds like you are asking for classical database transaction algorithms.
Dave Clarke
CC BY-SA 2.5
2010-10-31T10:00:45.557Z
@Dave  - thanks, I've edited. Better?
Nick Fortescue
CC BY-SA 2.5
2010-10-31T10:09:48.010Z
Are you already familiar with DBMS textbooks such as the one by Ramakrishnan and Gehrke? And if you are not asking about the internals of a DBMS, can you clarify the question to let us know the difference between a DBMS and what you are interested in?
Maverick Woo
CC BY-SA 2.5
2010-10-31T10:22:30.670Z
@Maverick. I haven't read that textbook. However looking at the TOC on amazon only chapter 9 seems relevant, and judging by the rest of the book, I'd guess it just explains the ACID principles and the concepts of locking/transaction failure and rollback, rather than the TCS variety of algorithms for implementing it. I think my question is reasonably clearly worded on this point, though others might be able to suggest a clarification.
Nick Fortescue
<ds.algorithms><dc.distributed-comp>
What algorithms/reading matter would you recommend on resolving transactions / read-write locks?
Nick Fortescue
# What algorithms/reading matter would you recommend on resolving transactions / read-write locks?

(Asked by: username_0 on 2010-10-31)

A simplified classical database transaction can be viewed as:

* reading M items
* performing some calculation based on those reads
* writing some N results based on these calculations, which may include the elements originally read.

When performing these transactions (concurrently) the [ACID](http://en.wikipedia.org/wiki/ACID) properties need to be maintained.

Exactly the same requirements (N updates based on M reads transactionally) exist in other non-DBMS concurrent systems.

I'm interested in finding out what algorithms exist for performing/resolving these transactions, and what the relative strengths and weaknesses of these algorithms are. Could you recommend some reading? This could be books or online references/tutorials.

Clarification:

So for example, a naive algorithm might be each transaction taking a single global lock, in effect forcing single threading and removing concurrency. A slightly more complicated algorithm would be individual item read/write locks, with an ordering to avoid deadlock). Etc, etc. Is there a good source documenting various algorithms for solving this problem. Even an answer which only pointed to a single algorithm with it's strength and weaknesses would be useful.

**Tags:** ds.algorithms, dc.distributed-comp
> **Comments:**
> **username_1**: This question certainly falls within the scope of this site. I would recommend writing a little more about the context in which you are working. At present it is rather general and open.  
> **username_0**: Do you think it is worth rephrasing so it is precisely the database question? IE something like "I have a database which can be read and written to, and I want to be able to read and write transactionally with ACID properties. What algorithms exist for ensuring these properties"  
> **username_1**: Rephrasing the question may result in answers closer to what you are looking for, such as giving more details of the problem you are trying to solve; at present you only give hints. In any case, it sounds like you are asking for classical database transaction algorithms.  
> **username_0**: @Dave  - thanks, I've edited. Better?  
> **username_2**: Are you already familiar with DBMS textbooks such as the one by Ramakrishnan and Gehrke? And if you are not asking about the internals of a DBMS, can you clarify the question to let us know the difference between a DBMS and what you are interested in?  
> **username_0**: @Maverick. I haven't read that textbook. However looking at the TOC on amazon only chapter 9 seems relevant, and judging by the rest of the book, I'd guess it just explains the ACID principles and the concepts of locking/transaction failure and rollback, rather than the TCS variety of algorithms for implementing it. I think my question is reasonably clearly worded on this point, though others might be able to suggest a clarification.  

---

## 1 answers

### Answer by username_1 on 2010-10-31. Score: 10

The book [Transactional Information Systems](http://rads.stackoverflow.com/amzn/click/1558605088) by Weikum and Vossen covers quite a lot of the area, both in theoretical and practical terms, from different perspectives, not just transactions. It's about 1000 pages long, so will keep you busy for a weekend or two. On the other hand, it's nearly 10 years old, so there might be something more up-to-date available. Other books in the line include *Concurrency Control and Recovery in Database Systems* by Bernstein, P., Hadzilacos, V., and Goodman, N, Addison-Wesley, 1987, *[Transaction Processing: Concepts and Techniques](http://rads.stackoverflow.com/amzn/click/1558601902)* by Jim Gray and Andreas Reuter, and *[Principles of Transaction Processing](http://rads.stackoverflow.com/amzn/click/1558606238)* by Philip A. Bernstein and Eric Newcomer, 2009. I haven't seen the latter one, but being the most recent it could be a good place to start, although your solution may well be found in older texts. A trip to the library may be worthwhile.

A monumental text in this area is *[Atomic Transactions](http://rads.stackoverflow.com/amzn/click/155860104X)* by Nancy Lynch et al. It presents a formal account and proofs of a number of the kinds of algorithms you are interested in. It's rather formal, and tedious, so may not be to your taste.

A lot of recent work is devoted to [Software Transactional Memory](http://en.wikipedia.org/wiki/Software_transactional_memory), which is applying the transaction ideas to multi-threaded applications. There are tens of publications on this topic each year: the wikipedia page provides plenty of references.

> **Comments:**
> **username_0**: thanks dave, especially for the phrase "Software transactional memory", I hadn't come across this name  
> **username_1**: STM is a really hot topic in programming languages research these days. There's a race on to see whether STM or Actor-based programming models will be the basis of future concurrent (= all) programming languages.  
> **username_2**: Besides STM, one particular keyword to look for inside these references is MVCC. It's used in most modern DBMSs: http://en.wikipedia.org/wiki/Multiversion_concurrency_control  
> **username_3**: @supercooldave I'm not sure it's a race: I think future languages will have to support a bit of both to some degree or another.  
> **username_1**: @Marc Harmann: metaphorically speaking.  

---

