Schedules and SerializabilitySchedulesSchedule NotationSerial SchedulesSerializable SchedulesSchedules and Serializability TheoryConflictsRecoverabilityRecoverable SchedulesRecognizing SerializabilityConflict SerializabilityGranularity IssuesNot the Final Word11/12/97 M-1Schedules and Serializability17.4-17.511/12/97 M-2Schedules•A "schedule" is the abstraction of the activity of simultaneous transactions.•Everything is stripped away except:–transaction identifiers (as subscripts)–DB READs and WRITEs and the data they operate on–COMMITs and ABORTs–The order of these operations11/12/97 M-3Schedule Notation•Sa A schedule of one or more transactions•TiA transaction.•ri(X) Transaction Ti performs a READ of data item X.•wi(X) Transaction Ti performs a WRITE of data item X.•aiTransaction i aborts.•ciTransaction i commits.11/12/97 M-4Serial Schedules•If Ti does not overlap Tj, ACID behavior is assured. –Notation: Ti;Tj means Ti executes fully, then Tj executes–Called a "serial" schedule•T1;T2;T3 and T2;T3;T1 might have different results, but either is acceptable.11/12/97 M-5Serializable Schedules•Serial schedules, though safe, are unacceptably costly–Transactions are I/O-bound (most elapsed time is spent waiting for I/O)•Non-serial (overlapped) schedules allow shorter turn-around and better resource utilization•A serializable schedule is one which is equivalent to some serial schedule11/12/97 M-6Schedules and Serializability Theory•Schedules are a major tool in studying concurrent processing of transactions•Goals: –be able to recognize when a schedule is serializableand/or:–be able to force schedules to be serializableand/or–be able to recognize when a schedule is recoverable if an abort occurs11/12/97 M-7Conflicts•A conflict occurs when one transaction in a schedule WRITEs a data item which another transaction also uses (READs or WRITEs)–Note: no order requirement in this definition–The two operations are said to conflict–The two Ts are also said to conflict–A conflict per se is not a show-stopper11/12/97 M-8Recoverability•The TP monitor must have the power to undo or "rollback" the effect of a transaction.–Example: if a transaction aborts after doing some WRITE•If one transaction in a schedule aborts, it may be necessary to abort and rollback others.–committed transactions should never be rolled back11/12/97 M-9Recoverable Schedules•Ti reads from Tj (with respect to a schedule) if Ti READs some item which had previously been WRITten by Tj.•A schedule is recoverable if no transaction in it COMMITs until all transactions that it READs from have COMMITted.•Stronger: in a strict schedule, a transaction cannot even read or write X until the last transaction which wrote X has COMMITted.11/12/97 M-10Recognizing Serializability•In general, difficult or impossible–depends on the semantics of the transactions•Some forms of serializability can be detected•Two schedules are conflict equivalent if the order of any two conflicting operations is the same in both schedules.11/12/97 M-11Conflict Serializability•A schedule is conflict serializable if there is some serial schedule with which it is conflict equivalent.•Turns out there's a simple algorithm to test for conflict serializability!–Make a digraph ("precedence graph") of the T's–Directed edges mark conflictsTheorem: schedule is conflict serializable iff graph has no cycles.11/12/97 M-12Granularity Issues•Granularity refers to the size of the data being read or written–whole DB; table; row; one attribute value, etc.•Smaller granularity means more concurrency, but more overhead•DBMSs differ in granularity supported•Transaction semantics may determine needed granularity11/12/97 M-13Not the Final Word•There are schedules which are not conflict serializable, but still serializable–"View serializability" is another definition; harder to check but allows more cases•There are even schedules which are not serializable but nevertheless safe•Serializability is a tool for analysis, not a
View Full Document