11
$\begingroup$

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 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.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ 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. $\endgroup$
    – Dave Clarke
    Oct 31, 2010 at 9:06
  • $\begingroup$ 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" $\endgroup$
    – Nick Fortescue
    Oct 31, 2010 at 9:19
  • $\begingroup$ 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. $\endgroup$
    – Dave Clarke
    Oct 31, 2010 at 9:51
  • $\begingroup$ @Dave - thanks, I've edited. Better? $\endgroup$
    – Nick Fortescue
    Oct 31, 2010 at 10:00
  • 1
    $\begingroup$ 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? $\endgroup$
    – Maverick Woo
    Oct 31, 2010 at 10:09

1 Answer 1

Reset to default
10
$\begingroup$

The book Transactional Information Systems 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 by Jim Gray and Andreas Reuter, and Principles of Transaction Processing 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 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, 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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ thanks dave, especially for the phrase "Software transactional memory", I hadn't come across this name $\endgroup$
    – Nick Fortescue
    Oct 31, 2010 at 10:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dave Clarke
    Oct 31, 2010 at 10:47
  • 1
    $\begingroup$ Besides STM, one particular keyword to look for inside these references is MVCC. It's used in most modern DBMSs: en.wikipedia.org/wiki/Multiversion_concurrency_control $\endgroup$
    – Maverick Woo
    Oct 31, 2010 at 12:28
  • $\begingroup$ @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. $\endgroup$
    – Marc Hamann
    Oct 31, 2010 at 15:18
  • $\begingroup$ @Marc Harmann: metaphorically speaking. $\endgroup$
    – Dave Clarke
    Oct 31, 2010 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.