TransactionsOverviewHow does..Assumptions and GoalsNext…Transaction statesShadow CopySlide 8Slide 9A ScheduleSchedulesExample ScheduleAnother scheduleSlide 14Example Schedules (Cont.)SerializabilitySlide 17Conflict SerializabilityEquivalence by SwappingSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25View-SerializabilityOther notions of serializabilityTesting for conflict-serializabilityExample Schedule (Schedule A) + Precedence GraphRecapRecoverabilitySlide 32Slide 33Slide 34TransactionsTransactionsAmol DeshpandeAmol DeshpandeCMSC424CMSC424OverviewOverviewTransaction: A sequence of database actions enclosed within special tagsProperties:Atomicity: Entire transaction or nothingConsistency: Transaction, executed completely, takes database from one consistent state to anotherIsolation: Concurrent transactions appear to run in isolationDurability: Effects of committed transactions are not lostConsistency: Transaction programmer needs to guarantee thatDBMS can do a few things, e.g., enforce constraints on the dataRest: DBMS guaranteesHow does..How does.... this relate to queries that we discussed ?Queries don’t update data, so durability and consistency not relevantWould want concurrency Consider a query computing total balance at the end of the dayWould want isolationWhat if somebody makes a transfer while we are computing the balanceTypically not guaranteed for such long-running queriesTPC-C vs TPC-HAssumptions and GoalsAssumptions and GoalsAssumptions:The system can crash at any timeSimilarly, the power can go out at any pointContents of the main memory won’t survive a crash, or power outageBUT… disks are durable. They might stop, but data is not lost.For now.Disks only guarantee atomic sector writes, nothing moreTransactions are by themselves consistentGoals:Guaranteed durability, atomicityAs much concurrency as possible, while not compromising isolation and/or consistencyTwo transactions updating the same account balance… NOTwo transactions updating different account balances… YESNext…Next…States of a transactionA simple solution called shadow copySatisfies Atomicity, Durability, and Consistency, but no ConcurrencyVery inefficientTransaction statesTransaction statesShadow CopyShadow CopyMake updates on a copy of the database.Switch pointers atomically after done.Some text editors work this wayShadow CopyShadow CopyAtomicity:As long as the DB pointer switch is atomic. Okay if DB pointer is in a single blockConcurrency:No.Isolation:No concurrency, so isolation is guaranteed.Durability:Assuming disk is durable (we will assume this for now).Very inefficient:Databases tend to be very large. Making extra copies not feasible. Further, no concurrency.Next…Next…Concurrency control schemesA CC scheme is used to guarantee that concurrency does not lead to problemsFor now, we will assume durability is not a problemSo no crashesThough transactions may still abortSchedulesWhen is concurrency okay ?Serial schedulesSerializabilityA ScheduleA ScheduleT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Transactions: T1: transfers $50 from A to B T2: transfers 10% of A to BDatabase constraint: A + B is constant (checking+saving accts)Effect: Before After A 100 45 B 50 105Each transaction obeys the constraint.This schedule does too.SchedulesSchedulesA schedule is simply a (possibly interleaved) execution sequence of transaction instructionsSerial Schedule: A schedule in which transaction appear one after the otherie., No interleavingSerial schedules satisfy isolation and consistencySince each transaction by itself does not introduce inconsistencyExample ScheduleExample ScheduleAnother “serial” schedule:T1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Consistent ? Constraint is satisfied.Since each Xion is consistent, any serial schedule must be consistentEffect: Before After A 100 40 B 50 110Another scheduleAnother scheduleT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Is this schedule okay ?Lets look at the final effect…Effect: Before After A 100 45 B 50 105Consistent. So this schedule is okay too.Another scheduleAnother scheduleT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Is this schedule okay ?Lets look at the final effect…Effect: Before After A 100 45 B 50 105Further, the effect same as theserial schedule 1.Called serializableExample Schedules (Cont.)Example Schedules (Cont.) A “bad” scheduleNot consistentT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A – tmpwrite(A)read(B)B = B+ tmpwrite(B)Effect: Before After A 100 50 B 50 60SerializabilitySerializabilityA schedule is called serializable if its final effect is the same as that of a serial scheduleSerializability schedule is fine and does not result in inconsistent databaseSince serial schedules are fineNon-serializable schedules are unlikely to result in consistent databasesWe will ensure serializabilityTypically relaxed in real high-throughput environmentsSerializabilitySerializabilityNot possible to look at all n! serial schedules to check if the effect is the sameInstead we ensure serializability by allowing or not allowing certain schedulesConflict serializabilityView serializabilityView serializability allows more schedulesConflict SerializabilityConflict SerializabilityTwo read/write instructions “conflict” if They are by different transactionsThey operate on the same data itemAt least one is a “write” instructionWhy do we care ?If two read/write instructions don’t conflict, they can be “swapped” without any change in the final effectHowever, if they conflict they CAN’T be swapped without changing the final effectEquivalence by SwappingEquivalence by SwappingT1read(A)A = A -50write(A)read(B)B=B+50write(B)T2read(A)tmp = A*0.1A = A
View Full Document
Unlocking...