CSEP 545 Transaction Processing for E-Commerce, Winter 2005                       University of Washington

1/11/05

 

Assignment 2

Preliminaries

a. If you haven’t picked a project (C# or Java) and partner, please do it now.

b. Visit www.tpc.org and spend 15 minutes browsing the site to get a feel for how the Transaction Processing Council describes the TPC-C benchmark and how it presents benchmark results. If you’re interested in the new TPC-W benchmark, look in http://www.tpc.org/tpcw/ and click under Current Version in the upper right.

c. Think about applying shadowing to the course project. In addition to the lecture slides, you might find it helpful to read the handout entitled 6.7 The No-Undo/No-Redo Algorithm. It describes a slight variation of the algorithm presented in class. Since it’s extracted from the middle of a chapter, some terms are undefined. Some of them are explained in notes in the left margin, which should be enough to make the description comprehensible.

d. There’s no reading this week. So it’s a great time to start working on your project. If you want to get a head start on next week’s reading, read Sections 1-3 of the revised Chapter 6, a handout on the course web site.

Problems

For each of the following histories, answer the following:

  1. List all serial histories that are equivalent to it
  2. Is it recoverable? Does it avoid cascading aborts? Is it strict?
    For each, if not, why?

1.      w0[x,y,z] c0 r1[x] r2[y] w2[y] r3[z] w3[z] r2[z] w2[y] w1[z] w1[y] c1 c2 c3

2.      w0[x,y,z] c0 r1[x] r2[y] w2[y] r3[z]           r2[z] w2[y] w1[z] w1[y] c1 c2 c3
 (same as (1), except delete w3[z])

3.      w0[x,y,z] c0 r1[x] r2[y] w2[y] r3[z] w3[z] r2[z] w2[y] w1[z] w1[y] c1 c3 c2
(same as (1), except that c2 is moved after c3)

4.      w0[x,y,z] c0 r1[x] r2[y] w2[x] r3[z] w3[z] r2[z] w2[y] w1[z] w1[y] c1 c2 c3
(same as (1), except the first w2[y] becomes w2[x])

5.      w0[x,y,z] c0 r1[x] r2[y] w2[y] r3[z] w3[z] r2[z] w2[y] c2 w1[z] w1[y] c1 c3
(same as (1), except c2 is moved before w1[z])