DOC PREVIEW
UW CSE 444 - Schedules and Serializability

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UW CSE 444 - Schedules and Serializability

Documents in this Course
XML

XML

48 pages

SQL

SQL

25 pages

SQL

SQL

42 pages

Recovery

Recovery

30 pages

SQL

SQL

36 pages

Indexes

Indexes

35 pages

Security

Security

36 pages

Wrap-up

Wrap-up

6 pages

SQL

SQL

37 pages

More SQL

More SQL

48 pages

SQL

SQL

35 pages

XML

XML

46 pages

Triggers

Triggers

26 pages

Load more
Download Schedules and Serializability
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Schedules and Serializability and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Schedules and Serializability 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?