This is a problem about transaction processing for a special database

application. The database consists of a small number of data items, and all

the transactions are of one of the following two types.

(i) Update transactions with only one operation, a write step writing

one data item. (These do not have any read steps.)

(ii) Scan transactions with only read operations, one read step for each

data item; the read steps are not ordered. (These do not have any write steps.)

For all the following questions, assume that the correctness criterion for

concurrent executions is conflict-serializability (of the committed transactions)

with the additional constraint that each pair of non-interleaved transactions

occurs in the same order in an equivalent serial history as in the history

produced by the scheduler, that is, order-preserving conflict-serializability.

Design the following schedulers. Schedulers discussed in class for general

databases may be used here also. Try some simplification or optimization

which may be possible for this special database application. If you think you

cannot simplify/optimize, explain why. All the properties you attribute to

your schedulers must be proven, at least informally.

1.(a) Design a 2PL based scheduler for this database

system.

(b) Are deadlocks possible? If so, suggest a method of avoiding or resolving

deadlocks.

2. Design a timestamp based scheduler.

3. Design BOCC and FOCC schedulers assuming that

only validation phase is in the critical section, that is, the write phase will

be concurrent with the read phases and write phases of other transactions.

4. Give an example of a non-serializable history (of read and

write steps, and no commit or abort steps). For this question alone, assume

that the database consists of only three items A, B, and C.

5. Assuming that the schedules are log-recoverable, design an

efficient crash recovery algorithm. You can choose redo-winners or redohistory

paradigm. Indicate, informally, the simplifications or modifications

of the algorithm (during the normal operation, redo pass and undo pass)

given in the book.

Justify the correctness informally.

There is no language constraint, use any programming language to answer the question(generalized answer is expected in a pseudo code form).