1、8.1Chapter 8 Transactions and Concurrency Controln8.1 Transaction Conceptn8.2 Transactions & Schedules（調(diào)度）（調(diào)度）n8.3 Concurrent Executionsn8.4 Concurrency Controln8.5 Transactions in SQLn8.6 Isolation（隔離）（隔離） Levelsn8.7 Pitfalls of Lock-Based Protocols8.28.1 TransactionsnDatabase systems are normally

2、being accessed by many users or processes at the same time. (e.g. Airline reservations)HBoth queries and modifications.nUnlike Operating Systems, which support interaction of processes, a DMBS needs to keep processes from troublesome interactions. (e.g. Banking)8.3nA transaction is a means by which

3、an application programmer can package together a sequence of database operations so that the database system can provide a number of guarantees.nTransaction is a set of changes that must all be made together.事務(wù)是具有完整邏輯意義的數(shù)據(jù)庫(kù)操作序列的集合。對(duì)于事務(wù)是具有完整邏輯意義的數(shù)據(jù)庫(kù)操作序列的集合。對(duì)于DBMS而言，事務(wù)是一個(gè)讀寫(xiě)操作的序列，這些操作是一個(gè)不而言，事務(wù)是一個(gè)讀寫(xiě)操作的序

4、列，這些操作是一個(gè)不可分割的邏輯工作單元，要么都做，要么都不做?？煞指畹倪壿嫻ぷ鲉卧炊甲?，要么都不做。事務(wù)是構(gòu)成數(shù)據(jù)庫(kù)處理邏輯單元的可執(zhí)行程序，由用戶定義的事務(wù)是構(gòu)成數(shù)據(jù)庫(kù)處理邏輯單元的可執(zhí)行程序，由用戶定義的一組操作序列（包括插入、刪除、修改或檢索等操作）組成，一組操作序列（包括插入、刪除、修改或檢索等操作）組成，序列中的操作要么全做，要么全不做，是一個(gè)不可分割的工作序列中的操作要么全做，要么全不做，是一個(gè)不可分割的工作單位。單位。8.4nWhy we need transaction - transaction(交易交易) - booking - fund transfer The

5、need of restoration 恢復(fù)的需要恢復(fù)的需要 The need for concurrent operation并發(fā)操作的需要并發(fā)操作的需要H買(mǎi)賣(mài)交易買(mǎi)賣(mài)交易一手交錢(qián)一手交貨一手交錢(qián)一手交貨H訂票訂票查詢、訂位、查詢、訂位、(交錢(qián)交錢(qián))、出票（往返票？）、出票（往返票？）H轉(zhuǎn)帳轉(zhuǎn)帳轉(zhuǎn)出、轉(zhuǎn)入轉(zhuǎn)出、轉(zhuǎn)入8.5James Gray1998年獲得圖靈獎(jiǎng)年獲得圖靈獎(jiǎng)n在數(shù)據(jù)庫(kù)技術(shù)、特別是事務(wù)處理方面做出了杰在數(shù)據(jù)庫(kù)技術(shù)、特別是事務(wù)處理方面做出了杰出貢獻(xiàn)。出貢獻(xiàn)。n解決了諸如完整性、安全性、并發(fā)控制等一系解決了諸如完整性、安全性、并發(fā)控制等一系列技術(shù)難題。列技術(shù)難題。8.6James N

6、. Gray1966年從年從Berkeley獲獲得其工程數(shù)學(xué)的學(xué)士學(xué)位，并于得其工程數(shù)學(xué)的學(xué)士學(xué)位，并于1969年獲得其計(jì)算機(jī)科學(xué)的博士學(xué)位。年獲得其計(jì)算機(jī)科學(xué)的博士學(xué)位。Gray博士畢業(yè)后，加入了工業(yè)界，先博士畢業(yè)后，加入了工業(yè)界，先后任職于后任職于IBM( )，Tandem( , 已經(jīng)是已經(jīng)是HP( )的一部分和的一部分和DEC( ，目前已是，目前已是HP的的一部分一部分)。目前，目前，Gray任職與微軟研究院任職與微軟研究院(http:/ )，主要從事大型數(shù)據(jù)庫(kù)和事務(wù)處理，主要從事大型數(shù)據(jù)庫(kù)和事務(wù)處理的研究。的研究。8.7nExample: 飛機(jī)訂票系統(tǒng)有兩個(gè)表飛機(jī)訂票系統(tǒng)有兩個(gè)表Sal

7、e,Flight,分別記錄各分別記錄各售票點(diǎn)的售票數(shù)及全部航班的剩余票數(shù)售票點(diǎn)的售票數(shù)及全部航班的剩余票數(shù) Sale(agentNo,flightNo,date,saleNumber) Flight(flightNo,date,remainNumber) 現(xiàn)有現(xiàn)有A0010售票點(diǎn)欲出售售票點(diǎn)欲出售F005航班航班2014年年12月月8日機(jī)票日機(jī)票2張張8.8n（1）查詢）查詢F005航班航班2014年年12月月8日剩余票數(shù)日剩余票數(shù) （2）IF(A2) 拒絕操作，并通知票不足拒絕操作，并通知票不足 ELSE 更新更新A0010的售票數(shù)及航班的剩余票數(shù)的售票數(shù)及航班的剩余票數(shù)8.9nSELECT

8、 remainNumbernFROM FlightnWHERE flightNo=F005AND date=2014-12-08nUPDATE SalenSet saledNumber=saledNumber+2nWHERE agentNo=A0010 AND flightNo=F005 AND date=2014-12-08nUPDATE FlightnSET remainNumber=remainNumber-2nWHERE flight=F005 AND date=2014-12-088.10n銀行轉(zhuǎn)賬業(yè)務(wù)，從賬戶銀行轉(zhuǎn)賬業(yè)務(wù)，從賬戶A轉(zhuǎn)出轉(zhuǎn)出1000元到賬戶元到賬戶B，通過(guò)兩個(gè)業(yè)務(wù)完成

9、，哪兩個(gè)？，通過(guò)兩個(gè)業(yè)務(wù)完成，哪兩個(gè)？8.11nCommit:事務(wù)提交事務(wù)提交 將成功完成事務(wù)的執(zhí)行結(jié)果（即更新）永久化將成功完成事務(wù)的執(zhí)行結(jié)果（即更新）永久化，并釋放事務(wù)占有的全部資源，并釋放事務(wù)占有的全部資源nRollback ：事務(wù)回滾：事務(wù)回滾 終止當(dāng)前的事務(wù)，撤銷其對(duì)數(shù)據(jù)庫(kù)所做的更新終止當(dāng)前的事務(wù)，撤銷其對(duì)數(shù)據(jù)庫(kù)所做的更新，并釋放事務(wù)占有的全部資源，并釋放事務(wù)占有的全部資源8.12Transaction ConceptnTransaction to transfer $50 from account A to account B:1. read(A)2. A := A 503. wr

10、ite(A)4. read(B)5. B := B + 506. write(B)8.13nIf the machine crashes in between the step 4 and 5, the money has already been subtracted from the account A, but it will not be added to account B. The $50 is lost. nIf the system crashes before the end of the transactions (Commit), none of the changes

11、are written to the database. On restart, the changes may all be rolled back, or the transaction restarted. 8.14TransactionsnThe solution to the problems of serialization(可串可串行化）行化） and atomicity is to group database operations into transactions.nA transaction is a collection of one or more operation

12、s on the database that must be executed atomically, that is, either all operations are performed or none are.All-or-None原則原則8.15ACID TransactionsnA DBMS is expected to support “ACID transactions”, which are:HAtomic: Either the whole process is done or none is. This property guarantees that a set of

13、record that are part of a transaction is indivisible . Thus either all operations of the transaction are properly reflected in the database or none are.事務(wù)中包含的所有操作要么全做，要么全不做事務(wù)中包含的所有操作要么全做，要么全不做, 原子性由恢復(fù)機(jī)制實(shí)現(xiàn)原子性由恢復(fù)機(jī)制實(shí)現(xiàn)8.16HConsistent: Database constraints are preserved. Database consistency is the prope

14、rty that every transaction sees a consistent database instance. 事務(wù)的隔離執(zhí)行必須保證數(shù)據(jù)庫(kù)的一致性事務(wù)的隔離執(zhí)行必須保證數(shù)據(jù)庫(kù)的一致性事務(wù)開(kāi)始前，數(shù)據(jù)庫(kù)處于一致性的狀態(tài)；事務(wù)結(jié)束后，數(shù)據(jù)庫(kù)必須仍事務(wù)開(kāi)始前，數(shù)據(jù)庫(kù)處于一致性的狀態(tài)；事務(wù)結(jié)束后，數(shù)據(jù)庫(kù)必須仍處于一致性狀態(tài)處于一致性狀態(tài)數(shù)據(jù)庫(kù)的一致性狀態(tài)由數(shù)據(jù)庫(kù)的一致性狀態(tài)由用戶來(lái)負(fù)責(zé)，由并發(fā)控制機(jī)制實(shí)現(xiàn)來(lái)負(fù)責(zé)，由并發(fā)控制機(jī)制實(shí)現(xiàn)如銀行轉(zhuǎn)帳，轉(zhuǎn)帳前后兩個(gè)帳戶金額之和應(yīng)保持不變?nèi)玢y行轉(zhuǎn)帳，轉(zhuǎn)帳前后兩個(gè)帳戶金額之和應(yīng)保持不變8.17HIsolated (隔離性隔離性) : It appe

15、ars to the user as if only one process executes at a time. Although multiple transactions may execute concurrently, each transaction must be unaware of other concurrently executing transactions. Intermediate transaction results must be hidden from other concurrently executed transactions. 系統(tǒng)必須保證事務(wù)不受

16、其它并發(fā)執(zhí)行事務(wù)的影響系統(tǒng)必須保證事務(wù)不受其它并發(fā)執(zhí)行事務(wù)的影響對(duì)任何一對(duì)事務(wù)對(duì)任何一對(duì)事務(wù)T1，T2，在，在T1看來(lái)，看來(lái)，T2要么在要么在T1開(kāi)開(kāi)始之前已經(jīng)結(jié)束，要么在始之前已經(jīng)結(jié)束，要么在T1完成之后再開(kāi)始執(zhí)行完成之后再開(kāi)始執(zhí)行隔離性通過(guò)并發(fā)控制機(jī)制實(shí)現(xiàn)隔離性通過(guò)并發(fā)控制機(jī)制實(shí)現(xiàn)8.18HDurable（長(zhǎng)期的）（長(zhǎng)期的）: Effects of a process do not get lost if the system crashes. After a transaction completes successfully, the changes it has made to th

17、e database persist, even if there are system failures. 一個(gè)事務(wù)一旦提交之后，它對(duì)數(shù)據(jù)庫(kù)的影響必須是永久的一個(gè)事務(wù)一旦提交之后，它對(duì)數(shù)據(jù)庫(kù)的影響必須是永久的系統(tǒng)發(fā)生故障不能改變事務(wù)的持久性系統(tǒng)發(fā)生故障不能改變事務(wù)的持久性持續(xù)性通過(guò)恢復(fù)機(jī)制實(shí)現(xiàn)持續(xù)性通過(guò)恢復(fù)機(jī)制實(shí)現(xiàn)8.19Example of Fund TransfernTransaction to transfer $50 from account A to account B:1. read(A)2. A := A 503. write(A)4. read(B)5. B := B + 5

18、06. write(B)n(1) Consistency requirement the sum of A and B is unchanged by the execution of the transaction.8.20Example of Fund Transfer(Cont.)n(2) Atomicity requirement if the transaction fails after step 3 and before step 6, the system should ensure that its updates are not reflected in the datab

19、ase, else an inconsistency will result.8.21Example of Fund Transfer(Cont.)n(3) Durability requirement once the user has been notified that the transaction has completed (i.e., the transfer of the $50 has taken place), the updates to the database by the transaction must persist despite failures.8.22E

20、xample of Fund Transfer (Cont.)n(4) Isolation requirement if between steps 3 and 6, another transaction is allowed to access the partially updated database, it will see an inconsistent database (the sum A + B will be less than it should be).8.23Example of Fund Transfer (Cont.)nCan be ensured trivial

21、ly（平凡）（平凡） by running transactions serially, that is one after the other. nHowever, executing multiple transactions concurrently has significant benefits, as we will see.8.242) Transaction State (Cont.)activefailedcommitrollbackPartially committed8.251. BEGIN TRANSACTION2. READ/WRITE TRANSACTION3. C

22、OMMIT TRANSACTION 事務(wù)完成所有數(shù)據(jù)操作，同時(shí)保存操作結(jié)果，事務(wù)完成所有數(shù)據(jù)操作，同時(shí)保存操作結(jié)果， 它標(biāo)志著事務(wù)成功完成。它標(biāo)志著事務(wù)成功完成。4. ROLLBACK TRANSACTION 事務(wù)未完成所有數(shù)據(jù)操作，重新返回到事務(wù)開(kāi)始狀態(tài)，標(biāo)志著事務(wù)的撤銷事務(wù)未完成所有數(shù)據(jù)操作，重新返回到事務(wù)開(kāi)始狀態(tài)，標(biāo)志著事務(wù)的撤銷.8.26nSQLServer提供了提供了3種類型的事務(wù)模式種類型的事務(wù)模式 顯式事務(wù)顯式事務(wù) 使用使用SQL事務(wù)定義的語(yǔ)句定義事務(wù)事務(wù)定義的語(yǔ)句定義事務(wù) 隱式事務(wù)隱式事務(wù) 事務(wù)提交或回滾后，事務(wù)提交或回滾后，SQL Server自動(dòng)開(kāi)始新自動(dòng)開(kāi)始新事務(wù)事務(wù) 自

23、定義事務(wù)自定義事務(wù) 一個(gè)語(yǔ)句成功執(zhí)行后，被自動(dòng)提交，而當(dāng)執(zhí)行一個(gè)語(yǔ)句成功執(zhí)行后，被自動(dòng)提交，而當(dāng)執(zhí)行過(guò)程中出錯(cuò)后，自動(dòng)回滾過(guò)程中出錯(cuò)后，自動(dòng)回滾8.27Transactions in SQLnSQL supports transactions, often behind the scenes.HEach statement issued at the generic query interface is a transaction by itself.HIn programming interfaces like Embedded SQL, a transaction begins the f

24、irst time an SQL statement is executed and ends with the program or an explicit end.當(dāng)使用基本的當(dāng)使用基本的SQL界面，即使用方便人們提交查詢和別的界面，即使用方便人們提交查詢和別的SQL語(yǔ)句的工具時(shí)，每條語(yǔ)句自身就是一個(gè)事務(wù)。語(yǔ)句的工具時(shí)，每條語(yǔ)句自身就是一個(gè)事務(wù)。8.28Transactions in SQLnStart Transaction HBEGIN TRANSACTIONnEnd TransactionHCOMMIT TRANSACTIONHROLLBACK TRANSACTION數(shù)據(jù)庫(kù)應(yīng)用程序中

25、，事務(wù)以數(shù)據(jù)庫(kù)應(yīng)用程序中，事務(wù)以BEGIN_TRANSACTION語(yǔ)句開(kāi)始，語(yǔ)句開(kāi)始，以以COMMIT或或ROLLBACK語(yǔ)句結(jié)束。語(yǔ)句結(jié)束。8.29COMMITnThe SQL statement COMMIT causes a transaction to complete.HIts database modifications are now permanent in the database.8.30ROLLBACKnThe SQL statement ROLLBACK also causes the transaction to end, but by aborting.HNo ef

26、fects on the database.nFailures like division by 0 can also cause rollback, even if the programmer does not request it.8.311st Sample TransactionnBEGIN TRANSACTIONnCREATE TABLE test1 (id int, lname varchar(20) default unknown);nINSERT INTO test1 VALUES(1,default);nINSERT INTO test1 VALUES (2,default

27、);nINSERT INTO test1 VALUES (3,default);nSELECT * FROM test1;nCOMMIT TRANSACTIONnSELECT * FROM test1;8.322nd Sample TransactionnBEGIN TRANSACTIONnCREATE TABLE test2 (id int, lname varchar(20) default unknown);nINSERT INTO test2 VALUES(1,default);nINSERT INTO test2 VALUES(2,default);nINSERT INTO test

28、2 VALUES(3,default);nSELECT * FROM test2;nROLLBACK TRANSACTIONnSELECT * FROM test2;8.333rd Sample TransactionnBEGIN TRANSACTIONnINSERT INTO test1 VALUES (4,default);nINSERT INTO test1 VALUES (5,default);nINSERT INTO test1 VALUES (6,default);nINSERT INTO test1 VALUES(default);nSELECT * FROM test1;nRO

29、LLBACK TRANSACTIONnSELECT * FROM test1; 8.34Problems hiding in concurrent operationsnLose update （丟失更新）（丟失更新）nDirty Read （讀臟數(shù)據(jù)）（讀臟數(shù)據(jù)）nUnrepeatable read（不可重復(fù)讀）（不可重復(fù)讀）8.35Example: Lose update nYou and your spouse each take $100 from different ATMs at about the same time.HThe DBMS better make sure one

30、account deduction doesnt get lost.nCompare: An OS allows two people to edit a document at the same time. If both write, ones changes get lost.8.36nExample 飛機(jī)訂票系統(tǒng)，假設(shè)某航班剩余飛機(jī)訂票系統(tǒng)，假設(shè)某航班剩余16張機(jī)票，張機(jī)票，A售票點(diǎn)（售票點(diǎn)（事務(wù)事務(wù)T1）賣(mài)了一張票，）賣(mài)了一張票，B售票點(diǎn)（事務(wù)售票點(diǎn)（事務(wù)T2）賣(mài)掉一張）賣(mài)掉一張票，如果正常操作，即事務(wù)票，如果正常操作，即事務(wù)T1執(zhí)行完再執(zhí)行執(zhí)行完再執(zhí)行T2，則剩，則剩余余14張機(jī)票

31、。將兩個(gè)事務(wù)拆分張機(jī)票。將兩個(gè)事務(wù)拆分 T1（1）：）：T1讀取機(jī)票余額讀取機(jī)票余額 T1（2）: T1修改機(jī)票余額修改機(jī)票余額R=R-1 T2（1）：）：T2讀取機(jī)票余額讀取機(jī)票余額 T2（2）：）：T2 修改機(jī)票余額修改機(jī)票余額R=R-1 如果執(zhí)行順序如下：如果執(zhí)行順序如下： T1（1） T2（1） T1（2） T2（2） 則余票為？則余票為？ 原因？原因？T2執(zhí)行時(shí)丟失了執(zhí)行時(shí)丟失了T1對(duì)數(shù)據(jù)庫(kù)的更新對(duì)數(shù)據(jù)庫(kù)的更新8.37Example: Lose update并發(fā)操作引起的丟失修改并發(fā)操作引起的丟失修改nTransaction T1 update the data , but it c

32、overed by the data which is modified by transaction T2 T1Read: A=16A=A-1Write: A15T2Read:A=16A=A-1Write:A15事務(wù)事務(wù)T1對(duì)數(shù)據(jù)的對(duì)數(shù)據(jù)的修改被事務(wù)修改被事務(wù)T2的的修改覆蓋修改覆蓋8.38Example: Dirty readnDirty data is common term for data written by a transaction that has not yet committed.nA dirty read is a read of dirty data written

33、by another transaction.臟數(shù)據(jù)：還沒(méi)有提交的事務(wù)所寫(xiě)的數(shù)據(jù)臟數(shù)據(jù)：還沒(méi)有提交的事務(wù)所寫(xiě)的數(shù)據(jù)臟讀：對(duì)臟數(shù)據(jù)的讀取臟讀：對(duì)臟數(shù)據(jù)的讀取8.39n事務(wù)事務(wù)T1 修改了某數(shù)修改了某數(shù)據(jù)并寫(xiě)回磁盤(pán)，事?lián)?xiě)回磁盤(pán)，事務(wù)務(wù)T2 讀取了同一數(shù)讀取了同一數(shù)據(jù)后，據(jù)后，T1由于某種由于某種原因被撤銷，被修原因被撤銷，被修改的值復(fù)原，此時(shí)改的值復(fù)原，此時(shí)T2讀到的數(shù)據(jù)與數(shù)讀到的數(shù)據(jù)與數(shù)據(jù)庫(kù)中的數(shù)據(jù)不一據(jù)庫(kù)中的數(shù)據(jù)不一致致T1Read: C=1C=C*2Write: C=2ROLLBACKC恢復(fù)為1T2Read:C=2Example: Dirty read8.40Example: Unrep

34、eatable ReadnThe same query issued more than once is not quite guaranteed to get the same answer.nIt is possible that a second or subsequent execution of the same query will retrieve phantom（幻影）（幻影） tuples.8.41Unrepeatable Readn事務(wù)事務(wù)T1讀取某一數(shù)據(jù)后讀取某一數(shù)據(jù)后，事務(wù)，事務(wù)T2對(duì)其做了修改對(duì)其做了修改，當(dāng)，當(dāng)T1按同樣條件再讀按同樣條件再讀時(shí)得到不同的值時(shí)得到不同

35、的值n事務(wù)事務(wù)T1讀取某些數(shù)據(jù)后讀取某些數(shù)據(jù)后，事務(wù)，事務(wù)T2刪除刪除(或插入或插入)了一些記錄，當(dāng)了一些記錄，當(dāng)T1按同按同樣條件再讀時(shí)發(fā)現(xiàn)少樣條件再讀時(shí)發(fā)現(xiàn)少(或或多多)了一些記錄了一些記錄T1read:A=1,B=2Solve A+B=3Read:A=1,B=4Solve:A+B=5T2Read:B=2B=B*2Write:B=48.42n事務(wù)事務(wù)Ti兩次從數(shù)據(jù)庫(kù)中讀取的結(jié)果不同，可分為三種情兩次從數(shù)據(jù)庫(kù)中讀取的結(jié)果不同，可分為三種情況：況：1） Ti 讀取一數(shù)據(jù)后，讀取一數(shù)據(jù)后， Tj對(duì)該數(shù)據(jù)進(jìn)行了更改。當(dāng)對(duì)該數(shù)據(jù)進(jìn)行了更改。當(dāng)Ti 再次再次讀該數(shù)據(jù)時(shí)，則會(huì)讀到與前一次不同的值讀該數(shù)據(jù)

36、時(shí)，則會(huì)讀到與前一次不同的值2） Ti 按某條件讀取數(shù)據(jù)庫(kù)中某些記錄后，按某條件讀取數(shù)據(jù)庫(kù)中某些記錄后， Tj刪除了其中刪除了其中部分記錄。當(dāng)部分記錄。當(dāng)Ti 再次按相同條件讀取時(shí)，發(fā)現(xiàn)記錄變?cè)俅伟聪嗤瑮l件讀取時(shí)，發(fā)現(xiàn)記錄變少了少了3） Ti 按某條件讀取數(shù)據(jù)庫(kù)中某些記錄后，按某條件讀取數(shù)據(jù)庫(kù)中某些記錄后， Tj插入了新的插入了新的記錄。當(dāng)記錄。當(dāng)Ti 再次按相同條件讀取時(shí)，發(fā)現(xiàn)記錄變多了再次按相同條件讀取時(shí)，發(fā)現(xiàn)記錄變多了 2）3）兩種不可重復(fù)讀稱為幻影現(xiàn)象）兩種不可重復(fù)讀稱為幻影現(xiàn)象phantom tuples.8.438.2 Transactions & SchedulesnA tran

37、saction is seen by the DBMS as a series or list of actions. The actions that can be executed by a transaction include reads and writes of database objects.nTwo assumptions：HTransactions interact with each other only via database read and write operations. They are not allowed to exchange messages.HA

38、 database is a fixed collection of independent objects.8.448.2 Transactions & SchedulesnA schedule （調(diào)度）（調(diào)度）is a list of actions (reading, writing, rollbacking, or committing) from a set of transactions, and the order in which two actions of a transaction T appear in a schedule must be the same as th

39、e order in which they appear in T.nA schedule represents an actual or potential execution sequence.事務(wù)并發(fā)執(zhí)行順序是隨機(jī)的，將由多個(gè)事務(wù)操作組成的隨機(jī)事務(wù)并發(fā)執(zhí)行順序是隨機(jī)的，將由多個(gè)事務(wù)操作組成的隨機(jī)執(zhí)行序列稱為一個(gè)調(diào)度。執(zhí)行序列稱為一個(gè)調(diào)度。8.458.2 Transactions & SchedulesnThe effect of a transaction on another transaction can be understood solely in terms of the co

40、mmon database objects that they read and write.8.468.2 Transactions & SchedulesnIf the actions of different transactions are not interleaved（交錯(cuò)的）（交錯(cuò)的）-that is, transactions are executed from start to finish, one by one-we call the schedule a serial schedule（串行調(diào)度）（串行調(diào)度）.nIf the actions of different t

41、ransactions are interleaved, we call the schedule a concurrent schedule.8.478.2 Transactions & SchedulesnExample :HTwo transactions are T0 and T1 . T0 transfers $50 from account A to account B. T1 transfers the 10% of money of account A to account B. HBefore the transformation, there is $1000 in acc

42、ount A and $2000 in account B. The sum of the two accounts must be $3000 and can not be changed.8.488.2 Transactions & SchedulesnSerial scheduleT0T1read(A1)A1 := A1 50write(A1)read(B1)B1 := B1 + 50write(B1)read(A2)temp:=A2*0.1A2 := A2 tempwrite(A2)read(B2)B2 := B2 + tempwrite(B2) After the transform

43、ation, there is $855 in account A and $2145 in account B . The sum of money in them is still $3000.8.498.2 Transactions & SchedulesnSerial scheduleT0T1read(A2)A2 := A2 50write(A2)read(B2)B2 := B2 + 50write(B2)read(A1)temp:=A1*0.1A1 := A1 tempwrite(A1)read(B1)B1 := B1 + tempwrite(B1) After the transf

44、ormation, there is $850 in account A and $2150 in account B . The sum of money in them is still $3000.8.508.2 Transactions & SchedulesnConcurrent scheduleT0T1read(A1)A1 := A1 50write(A1)read(B1)B1 := B1 + 50write(B1)read(A2)temp:=A2*0.1A2 := A2 tempwrite(A2)read(B2)B2 := B2 + tempwrite(B) After the

45、transformation, there is $855 in account A and $2145 in account B . The sum of money in them is still $3000.8.518.2 Transactions & SchedulesnConcurrent scheduleT0T1read(A1)A1 := A1 50write(A1)read(B1)B1 := B1 + 50write(B1)read(A2)temp:=A2*0.1A2 := A2 tempwrite(A2)read(B2)B2 := B2 + tempwrite(B)After

46、 the transformation, there is $950 in account A and $2100 in account B . The sum of money in them is $3050. The sum of money is changed.S4 is a wrong schedule because the sum of money is not consistent.8.52Serial Scheduling(1)nLet T1 transfer $50 from A to B, and T2 transfer 10% of the balance from

47、A to B. nInitial status : A ($1,000), B($2,000) total : $3,000 1) T1 T2 2) T2 T1 A: 1,000 950 B: 2,000 2,050 A: 1,000 900 B: 2,000 2,100 DatabaseDatabase8.53Serial Scheduling(2) 3) T1 T2 T1 T2 4) T1 T2 T1 T2 A: 1,000 950 B: 2,000 2,050 A: 1,000 900 B: 2,000 2,050 DatabaseDatabase1,0001,0009009502,00

48、02,0002,0502,1001,0009509508652,0002,0502,0502,050950 - 952,000+502,050+951,000-501,000-502,000-1008.548.2 Transactions & SchedulesnIf there are n transactions , there will be n! serial schedules and more than n! concurrent schedules. nA good concurrent schedule should not only have the same effect

49、as the serial schedules ,but also execute efficiently.8.558.2 Transactions & SchedulesnIf a concurrent schedule is equivalent to the serial schedule, then we call the concurrent schedule is a serializable schedule.nTwo schedules are equivalent when two operations in different transactions conflict ,

50、 and the order in which the operations occur is important. nThat is the order of the conflicting operations can be changed without breaking the consistency of the data. 8.568.2 Transactions & SchedulesnConflicting operations: If the operations reference the same data item and at least one of them is

51、 a write, the two operations are conflicting operations.n1)read(Q) ,write(Q)n2) write(Q),read(Q)n3) write(Q), write(Q)Conflicting operations 沖突操作沖突操作:在一調(diào)度中在一調(diào)度中,如果如果Qi和和Qj是不同事務(wù)在相同數(shù)據(jù)是不同事務(wù)在相同數(shù)據(jù)對(duì)象上的操作，并且其中至少有一個(gè)是寫(xiě)操作，則稱對(duì)象上的操作，并且其中至少有一個(gè)是寫(xiě)操作，則稱Qi和和Qj是沖突操作是沖突操作8.57read(Q)write(P)8.2 Transactions & Schedules

52、nIf two operations are not conflicting operations, their order to operate can be switched（轉(zhuǎn)換）（轉(zhuǎn)換）.T1T2read(Q)write(P)T1T1T2read(Q)write(P)read(Q)write(Q) S5nIn S5, write(P) in T1 and write(Q) are not conflicting operations, then we switch their order and get S6. Further, we get S7 by switching the o

53、rder of write(P) and read(Q).read(Q)write(Q)read(Q)write(Q)S6S7T28.588.2 Transactions & SchedulesnConflict Equivalent: （沖突等價(jià)）（沖突等價(jià)） If schedule S can became S by switching the order of its operations without conflicts , then S and S are conflict equivalent.nConflict Serializable Schedule：沖突可串行化沖突可串行

54、化 If a concurrent schedule S is conflict equivalent to the serial schedule S on the same transactions , S is a conflict serializable schedule如果一調(diào)度如果一調(diào)度S與一串行調(diào)度是沖突等價(jià)的，則稱與一串行調(diào)度是沖突等價(jià)的，則稱S是是沖突可串行化沖突可串行化8.59T4T5ABR（A）A=A-2W（A）R（A）A=A-3W（A）R（B）B=B-2W（B）R（B）B=B-3W（B）1088515131310T4T5R（A）A=A-2W（A）R（B）B=B-2W（

55、B）R（A）A=A-3W（A）R（B）B=B-3W（B）A=10，B=15Concurrent ScheduleConflict Serializable Schedule8.608.3 Concurrent ExecutionsnMultiple transactions are allowed to run concurrently in the system. nAdvantages are:Hincreased processor and disk utilization, leading to better transaction throughput: one transactio

56、n can be using the CPU while another is reading from or writing to the diskHreduced average response time for transactions: short transactions need not wait behind long ones.8.618.3 Concurrent ExecutionsnConcurrency control schemes mechanisms to achieve isolation, i.e., to control the interaction am

57、ong the concurrent transactions in order to prevent them from destroying the consistency of the database.8.628.3 Lock-Based ProtocolsnMultiple transactions executed at same timeHother applications have access to inconsistent (intermediate) stateHsolution: Lock-Based Protocols8.638.4 Lock-Based Proto

58、colsnA lock is a mechanism to control concurrent access to a data item.nData items can be locked in two modes : 1. exclusive (X) mode. Data item can be both read as well as written. X-lock is requested using lock-X instruction. 排他鎖排他鎖 2. shared (S) mode. Data item can only be read. S-lock is request

59、ed using lock-S instruction. 共享鎖共享鎖nLock requests are made to concurrency-control manager. Transaction can proceed only after request is granted.8.64n排它鎖（X鎖) 排他鎖也稱為獨(dú)占鎖或?qū)戞i。一旦事務(wù)排他鎖也稱為獨(dú)占鎖或?qū)戞i。一旦事務(wù)T對(duì)數(shù)據(jù)對(duì)對(duì)數(shù)據(jù)對(duì)象象A加上排它鎖加上排它鎖(X鎖鎖)，則只允許，則只允許T讀取和修改讀取和修改A，其他，其他任何事務(wù)既不能讀取和修改任何事務(wù)既不能讀取和修改A，也不能再對(duì)，也不能再對(duì)A加任何類加任何類型的鎖，直到型

60、的鎖，直到T釋放釋放A上的鎖為止。上的鎖為止。n共享鎖（S鎖）共享鎖又稱讀鎖。如果事務(wù)共享鎖又稱讀鎖。如果事務(wù)T對(duì)數(shù)據(jù)對(duì)象對(duì)數(shù)據(jù)對(duì)象A加上共加上共享鎖享鎖(S鎖鎖)，事務(wù)，事務(wù)T對(duì)數(shù)據(jù)對(duì)象對(duì)數(shù)據(jù)對(duì)象A只能讀不能修改，其他只能讀不能修改，其他事務(wù)對(duì)事務(wù)對(duì)A只能再加只能再加S鎖，不能加鎖，不能加X(jué)鎖，直到事務(wù)鎖，直到事務(wù)T釋放釋放A上的上的S鎖為止。鎖為止。8.658.3 Lock-Based ProtocolsnTransactions obtain locks on objects xHS-locks (shared) for read: slock(x)HX-locks (exclusive