Serializable ------------ A transaction is a computation that can read and write objects. Suppose we have several transactions and a set of objects whose names are just single lower case letters. A transaction is just a list of read and write operations; for example: Rx Ry Rz Wx Wz where Rx means read object x, Wx means write object x, and so forth. These operations must be executed in the order given. We are abstracting and so neglect to men- tion the computations that derive the value written into x from the values read from x, y, and z. To simplify we will assume that every object has a unique name that is just a single lower case letter. Suppose we have a set of transactions and give each a number: 1, 2, 3, .... For example, 1: Rx Ry Rz Wx Wz 2: Ry Rx Wz 3: Ry Wy A schedule is a list of transaction numbers that tells the order in which operations of the transaction are executed. For example: Schedule A: 1 2 3 1 2 3 2 1 1 1 Rx Ry Ry Ry Rx Wy Wz Rz Wx Wz where we have written the operations executed under each schedule transaction number. In other words, for this schedule transaction 1 executes its first operation Rx, then transaction 2 executes its first operation Ry, then transaction 3 executes its first operation Ry, then transaction 1 executes it next (second) operation Ry, and so forth. A schedule is SERIAL if all the operations of each transaction are consecutive. Thus Schedule B: 2 2 2 1 1 1 1 1 3 3 Ry Rx Wz Rx Ry Rz Wx Wz Ry Wy is a serial schedule. Two schedules have the same effect of one can be made from the other by switching the order of NON-CONFLICTING operations. Two operations conflict if both are on the same object and at least one is a write. Thus Rx and Wx conflict, as do Wx and Wx, but Rx and Rx are non-con- flicting, as are Rx and Wy and Wx and Wy. A schedule is SERIALIZABLE if it has the same effect as a serial schedule. You are asked in this problem to determine whether a schedule is serializable. Input ----- For each of several test cases: one line with the format: T S one or more schedule lines with a total of S transaction numbers T transaction description lines, each of at most 80 characters T is the number of transactions; S is the length of the schedule; 1 <= T <= 20 and 1 <= S <= 100. Transactions are numbered 1 through T, with transaction number 1 being described first. A transaction description line consists of one or more operations separated by white- space, where an operation is a pair of letters Rx or Wx, and x is any lower case letter, that is, any object name. The schedule consists of S whitespace separated integers, each in the range from 1 through T, and the schedule may be broken across several lines. Input ends with an end of file. Output ------ For each test case, one line containing just the word SERIALIZABLE or just the word NON-SERIALIZABLE Sample Input ------ ----- 3 10 1 2 3 1 2 3 2 1 1 1 Rx Ry Rz Wx Wz Ry Rx Wz Ry Wy 3 10 1 2 3 1 2 3 1 1 2 1 Rx Ry Rz Wx Wz Ry Rx Wz Ry Wy Sample Output ------ ------ SERIALIZABLE NON-SERIALIZABLE Remarks ------- Programmers expect transactions on a data base to be executed using a serializable schedule, for if conflic- ting operations from different transactions are inter- leaved, it becomes nearly impossible to understand what is happening. A typical data base system contains a scheduler that employs one of several methods of rendering its sche- dules serializable. One is strict two-phase locking, in which a transaction locks objects before accessing them, and does not release any locks until the end of the transaction. Such a scheduler may get into deadlock situations, in which transaction M is waiting for a lock held by transaction N, and transaction N is at the same time waiting for a lock head by transaction M. The scheduler must then abort one of the transactions; i.e., the transaction must be stopped, any writes it has done must be undone (which is easy if it never writes until after it has all its locks), and all its locks must be released (allowing other transactions to proceed). Then the aborted transaction must be restarted. Reference: Concurrency Control and Recovery in Database Systems by Bernstein, Hadzilacos, and Goodman. File: serializable.txt Author: Bob Walton Date: Tue Oct 10 09:00:01 EDT 2006 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2006/10/10 13:04:01 $ $RCSfile: serializable.txt,v $ $Revision: 1.4 $