Data Models Conceptual representa1on of the data Data Retrieval How to ask ques1ons of the database How to answer those ques1ons Data Storage How where to store data how to access it Data Integrity Manage crashes concurrency Manage seman1c inconsistencies 1 Transaction A sequence of database actions enclosed within special tags Properties Atomicity Entire transaction or nothing Consistency Transaction executed completely takes database from one consistent state to another Isolation Concurrent transactions appear to run in isolation Durability Effects of committed transactions are not lost Consistency Transaction programmer needs to guarantee that DBMS can do a few things e g enforce constraints on the data Rest DBMS guarantees this relate to queries that we discussed Queries don t update data so durability and consistency not relevant Would want concurrency Consider a query computing total balance at the end of the day Would want isolation What if somebody makes a transfer while we are computing the balance Typically not guaranteed for such long running queries TPC C vs TPC H 2 Assumptions The system can crash at any time Similarly the power can go out at any point Contents of the main memory won t survive a crash or power outage BUT disks are durable They might stop but data is not lost For now Disks only guarantee atomic sector writes nothing more Transactions are by themselves consistent Goals Guaranteed durability atomicity As much concurrency as possible while not compromising isolation and or consistency Two transactions updating the same account balance NO Two transactions updating different account balances YES States of a transaction A simple solution called shadow copy Satisfies Atomicity Durability and Consistency but no Concurrency Very inefficient 3 Make updates on a copy of the database Switch pointers atomically after done Some text editors work this way 4 Atomicity As long as the DB pointer switch is atomic Okay if DB pointer is in a single block Concurrency 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 Concurrency control schemes A CC scheme is used to guarantee that concurrency does not lead to problems For now we will assume durability is not a problem So no crashes Though transactions may still abort Schedules When is concurrency okay Serial schedules Serializability 5 Transactions T1 transfers 50 from A to B T2 transfers 10 of A to B Database constraint A B is constant checking saving accts T1 read A A A 50 write A read B B B 50 write B T2 Effect A B Before 100 50 After 45 105 read A tmp A 0 1 A A tmp write A read B B B tmp write B Each transaction obeys the constraint This schedule does too A schedule is simply a possibly interleaved execution sequence of transaction instructions Serial Schedule A schedule in which transaction appear one after the other ie No interleaving Serial schedules satisfy isolation and consistency Since each transaction by itself does not introduce inconsistency 6 Another serial schedule T1 T2 read A tmp A 0 1 A A tmp write A read B B B tmp write B read A A A 50 write A read B B B 50 write B T1 read A A A 50 write A Effect A B Before 100 50 After 40 110 Consistent Constraint is satisfied Since each Xion is consistent any serial schedule must be consistent T2 Is this schedule okay read A tmp A 0 1 A A tmp write A read B B B 50 write B read B B B tmp write B Lets look at the final effect Effect A B Before 100 50 After 45 105 Consistent So this schedule is okay too 7 T1 read A A A 50 write A T2 Is this schedule okay read A tmp A 0 1 A A tmp write A Lets look at the final effect Effect A B read B B B 50 write B read B B B tmp write B Before 100 50 After 45 105 Further the effect same as the serial schedule 1 Called serializable A bad schedule T1 read A A A 50 T2 Effect read A tmp A 0 1 A A tmp write A read B A B Before 100 50 After 50 60 Not consistent write A read B B B 50 write B B B tmp write B 8 A schedule is called serializable if its final effect is the same as that of a serial schedule Serializability schedule is fine and does not result in inconsistent database Since serial schedules are fine Non serializable schedules are unlikely to result in consistent databases We will ensure serializability Typically relaxed in real high throughput environments Not possible to look at all n serial schedules to check if the effect is the same Instead we ensure serializability by allowing or not allowing certain schedules Conflict serializability View serializability View serializability allows more schedules 9 Two read write instructions conflict if They are by different transactions They operate on the same data item At least one is a write instruction Why do we care If two read write instructions don t conflict they can be swapped without any change in the final effect However if they conflict they CAN T be swapped without changing the final effect T1 read A A A 50 write A T1 read A A A 50 write A T2 T2 read A tmp A 0 1 A A tmp write A read A tmp A 0 1 A A tmp read B read B B B 50 write B write A B B 50 write B read B B B tmp write B Effect A B Before 100 50 After 45 105 read B B B tmp write B Effect A B Before 100 50 After 45 105 10 T1 read A A A 50 write A T1 read A A A 50 write A T2 T2 read A tmp A 0 1 A A tmp write A read A tmp A 0 1 A A tmp write A read B B B 50 write B read B B B 50 read B write B read B B B tmp write B Effect A B Before 100 50 After 45 105 B B tmp write B Effect A B Before 100 50 After 45 55 Conflict equivalent schedules If S can be transformed into S through a series of swaps S and S are called conflict equivalent conflict equivalent guarantees same final effect on the database A schedule S is conflict serializable if it is conflict equivalent to a serial schedule 11 T1 read A A A 50 write A T1 read A A A 50 write A T2 T2 read A tmp A 0 1 A A tmp write A read A tmp A 0 1 A A tmp read B B B 50 read B B B 50 write B write A write B read B B B tmp write B Effect A B Before 100 50 T1 read A A A 50 …
View Full Document
Unlocking...