19-1 How can a serial execution of a composite operation be guaranteed? What is a serialisable execution of a composite operation?

A serial execution can be achieved by locking all the objects required by a composite operation before it starts. A serialisable execution of the component operations of a number of composite operations is equivalent (with respect to output and final system state) to some serial execution of those composite operations.

19-2 In a TP system a client submits a transaction, it is done and acknowledged to the client. What must the system guarantee when that acknowledgement is given?

That the result persists irrespective of subsequent system crashes or media failures.

19-3 What are the ACID properties of atomic transactions and how can they be ensured under concurrency and crashes?

See Section 19.4 for a definition of A. C. I. D. It is useful to point out that A and D are the concern of recovery procedures and C and I are the concern of concurrency control.

A is ensured by the ability to recover state.

C is ensured by serialisable executions.

I is ensured by enforcing strict execution schedules in strict 2PL and strict TSO and by OCC when invocations take place in isolation on shadow objects. It should be mentioned that we shall see that I is not necessarily enforced in the implementation; that is, non-strict executions may be allowed. This would increase concurrency at the risk of having to abort transactions.

D is ensured by writing the results of a transaction to persistent store, with whatever degree of redundancy is deemed necessary for the requirements of the application, before commit is acknowledged.

19-4 Relate the system model based on object invocation given in Section 19.6, to the discussion of Section 14.9 on object naming, location and invocation.

This is discussed in the solution to exercise 20-3.

19-5 How does the graph which represents the history of a set of transactions being executed differ from a serialisation graph? What property of the serialisation graph must hold for the transactions that it represents to be serialisable?

An execution history shows all the component operations of the transactions and the order in which conflicting operations take place.

A serialisation graph shows only transactions. A directed arc from one transaction to another in a serialisation graph is drawn to indicate the order of execution of conflicting operations. The serialisation graph must be acyclic for the transactions represented in it to be serialisable.

19-6 Why might the decision to abort one transaction lead to the need to abort another?

If a transaction has seen state that is subsequently undone on the abort of another transaction then it must also be aborted.

Could this happen if the property of isolation of atomic transactions was enforced at all times? No.

19-7 Give some practical examples of conflicting operations on an object.

Our definition of conflict starts from some system state. The final state on executing two conflicting operations differs depending on the order of execution. It is better to focus on state than on output.

Simple examples can be taken from arithmetic.

(a+b)*c (add b then multiply by c) is not the same as a*c+b (multiply by c then add b).

"Calculate the interest on a bank account" conflicts with deposit. Performing any computation on an object’s state conflicts with changing the state.

"Calculate the sum of a number of object values" conflicts with changing any of the values.

"Change the value of an object to X" conflicts with "Change the value of an object to Y". This can be applied to writing new versions of parts of documents, changing part of a chip layout in a CAD system and so on.

19-8 Assume that every operation on an object has an inverse or undo operation. Assume that a number of operations have taken place on an object. When can an undo operation simply be applied to the current state of an object, even if there have been operations on the object since the one that must be undone?

If all the operations subsequent to the one which must be undone do not conflict with it then it may be applied to the current object state.