Testing Isolation Levels of Relational Database Management Systems .


48 views
Uploaded on:
Description
How could i have been able to I get included ?. Taken an interest in a National Science Foundation (NSF) venture:
Transcripts
Slide 1

´╗┐Testing Isolation Levels of Relational Database Management Systems by Dimitris Liarokapis December 2001

Slide 2

How did I get included ? Taken an interest in a National Science Foundation (NSF) extend: "Disengagement Testing" by, Prof. Patrick O\'Neil, and Elizabeth O\'Neil http://www.cs.umb.edu/~isotest/

Slide 3

References (Sample) [GLPT77] J. Dim, R. Lorie, G. Putzolu and, I. Traiger, "Granularity of Locks and Degrees of Consistency in a Shared Data Base," in Readings in Database Systems, Second Edition, Chapter 3, Michael Stonebraker, Ed., Morgan Kaufmann 1994 [BHG87] P. A. Bernstein, V. Hadzilacos, and N. Goodman. Simultaneousness Control and Recovery in Database Systems. Addison Wesley, 1987. http://research.microsoft.com/bars/ccontrol/default.htm [GR93] J. N. Dark and A. Reuter. Exchange Processing: Concepts and Techniques. Morgan Kaufmann Publishers Inc., 1993. [BBGMOO95] H. Berenson, P. Bernstein, J. Dark, J. Melton, E. O\'Neil, and P. O\'Neil. A Critique of ANSI SQL Isolation Levels. In Proceedings of the SIGMOD International Conference on Management of Data, May 1995. [ALO00] A. Adya, B. Liskov, P. O\'Neil. Summed up Isolation Level Definitions. In Proceedings of IEEE International Conference on Data Engineering, March 2000.

Slide 4

A Database System A Database System keeps up data about a world. It can be questioned for giving a perspective of the world. It can be overhauled for reflecting changes on the planet.

Slide 5

Transaction The connection between a User and A DBMS is finished by utilizing Transactions . The accompanying properties must be fulfilled: Atomicity - Do all the work or not under any condition. Consistency - Leave the database reliable Isolation - Act as though you were separated from everyone else Durability - The outcomes are lasting

Slide 6

Concurrency is the capacity of a Database System to prepare interleaved exchanges. Expands the use of a framework. While an exchange is getting to a circle, another exchange can utilize the CPU. Better reaction. A little exchange require not hold up until a long one completes first. Parallelism is abused (plates, cpus)

Slide 7

Are there any dangers ? At the point when exchanges work on various information there are for all intents and purposes no dangers. When they work on basic information their interleaving can deliver a mistaken outcome. We consider the consequence of an exchange to be the qualities recovered and the express the database is as a rule left.

Slide 8

What is Correctness ? A simultaneous execution of an arrangement of exchanges is viewed as right if the outcomes are the same with a serial execution of similar exchanges. This foundation of rightness is called: SERIALIZABILITY

Slide 9

Modeling Transactions An exchange can be demonstrated as a grouping of read and compose activities. It incorporates a last confer or prematurely end action. The accompanying can be the exchange that exchanges $50 from record A to B. T : r(A,100) r(B,200) w(B,250) w(A,50) c

Slide 10

Transactional Histories We display interleaved executions of various exchanges with histories. The accompanying is a history speaking to the execution of two exchanges T1 and T2. T1 exchanges $50 from A to B. T2 figures the aggregate of the two records. r1(A,100) r1(B,200) r2(A,100) w1(A,50), w1(B,250) c1 r2(B,250) c2

Slide 11

Non Serializable Histories r1(A,100) r1(B,200) r2(A,100) w1(A,50), w1(B,250) c1 r2(B,250) c2 is not a serializable history. In the event that T1, T2 were executed serially then we would have one of the accompanying histories: r1(A,100) r1(B,200) w1(B,250), w1(A,50) c1 r2(A,50) r2(B,250) c2 r2(A,100) r2(B,200) c2 r1(A,100) r1(B,200) w1(B,250), w1(A,50) c1

Slide 12

Serializability by locking A database framework can avert non serializable executions by utilizing locking. Locks can be shared or select and of long or brief length. Imparted locks are good to shared locks. Selective locks are not perfect with different locks.

Slide 13

2 Phase Locking PHASE I : ALL locks are gained. Stage II: Locks can be discharged. Normally stage II happens toward the finish of an exchange. Stops can happen under 2PL, and the framework needs to distinguish them.

Slide 14

Example of 2 Phase Locking Consider a database framework getting the accompanying solicitations. r1(A) r1(B) r2(A) w1(A) r2(B) w1(B) c1 c2 w1(A) and w1(B) will be obstructed until T2 confers. The last execution will be: r1(A) r1(B) r2(A) r2(B) c2 w1(A) w1(B) c1 The above will be proportional to: T2,T1

Slide 15

Serialization Graph (Conflict Serializability) The hubs of the diagram speak to the exchanges in the History For each clashing pair of operations there is an edge between the comparing exchanges. Two operations struggle on the off chance that they work on similar information and one of them is a compose . On the off chance that there is a cycle in the chart the history is not serializable.

Slide 16

Example of a Serialization Graph r1(A,100) r1(B,200) r2(A,100) w1(A,50) w1(B,250) c1 r2(B,250) c2 A cycle demonstrates that an exchange happens previously, then after the fact of another exchange. T1 T2

Slide 17

Serializability by numerous forms. A framework can keep up various adaptations of an information thing. Each compose operation makes another form. The framework chooses what variant will be come back to a read operation. r1(A0,100) r1(B0,200) r2(A0,100) w1(A1,50), w1(B1,250) c1 r2(B0,200) c2

Slide 18

Predicates & Phantoms In genuine database frameworks there are operations that work on a gathering of information things that fulfill a predicate ( e.g. select sum(balance) from records where city=Boston ) New sorts of contentions are presented: predicate clashes Traditional information thing locking is not sufficiently defensive prompting to apparitions (e.g. embed into records (acount_id, balance,city) values (1001, $30, Boston)

Slide 19

S A P B D C E Predicate Conflicts PR ( P ): peruses the information things {B,C,D} and clashes with: W (An into P ): overhauls A so that fulfills P. W (D outof P ): upgrades D to not fulfill P. I (F in P ): embeds the thing F that fulfills P. D (C in P ): erases the thing C that fulfills P. F

Slide 20

Approximating Predicate Locks by Using Index Locking Select * from BankAccounts where Status = Married AND City = Boston Washington Status Index Married City Index Seattle Single Boston BankAccounts Table

Slide 21

Isolation Levels An element gave by database administration frameworks keeping in mind the end goal to expand execution when: Full rightness is redundant or Correctness could be guaranteed at the application level

Slide 22

Isolation Levels (ANSI) 1. Grimy Read (P1). An exchange T1 changes some line and another exchange T2 peruses that column before T1 confers. The ramifications of this wonder is that if exchange T1 issues a ROLLBACK proclamation (prematurely end) it will be as though exchange T2 read values that have never existed. 2. Non-Repeatable Read (P2). An exchange T1 peruses some line. Another exchange T2 adjusts that column and plays out a submit. On the off chance that T1 endeavors to re-read that line it can watch the progressions done by exchange T2. 3. Ghost (P3). An exchange T1 peruses an arrangement of lines that fulfill some condition. Another exchange T2 executes an announcement that causes new lines to be included or expelled from the inquiry condition. On the off chance that T1 rehashes the read it will acquire an alternate arrangement of lines. 1. The Serializable level ought to permit just serializable executions. 2. There are no unmistakable uncommitted activities aside from the RU level. 3. There are no redesign operations permitted at the RU level.

Slide 23

Definitions in "Summed up Isolation Levels" byA.Atul, B.Liskov, P.Oneil G0: The Serialization Graph can contain a cycle comprising just of w-w edges G1: Aborted or Intermediate Reads or the SG contains a cycle comprising just of w-w, w-r, w-pr edges G2-thing: The SG contains a cycle with at least one r-w edges. G2: The SG contains a cycle with at least one r-w or pr-w edges.

Slide 24

HISTEX Threads Monitor Input History r1(A)w2(A)c2w1(B)c1 Database System (Oracle, DB2, and so on.) Output History r1(A,100,10000)w2(A,100,10001)c2w1(B,200,20001)c1

Slide 25

Histex Data Model Operation Examples: R(A,X1) W(B,898), W(C,X1) PRED(W,"K50=49") PR(P) PR(P;10, Z1) Data Item Map Predicate Map Value Map Database

Slide 26

Histex Operations

Slide 27

Testing Methodologies Comparative Testing Based on the claim that normal conduct is right conduct. Dim Box Testing Based on presumptions however not finish information of the fundamental framework.

Slide 28

Comparative Testing Execute a similar testing situations by utilizing a few database frameworks. Bunch the outcomes in view of their comparability. The gatherings with less individuals are more plausible to contain a blunder. On the off chance that an entire investigation is craved, the bunching diminishes the required work.

Slide 29

Comparative Testing: Issues It is conceivable that yields of various frameworks could be distinctive yet redress in the meantime. This is common when distinctive strategies are utilized for simultaneousness control (single adaptation cc with locking versus multi-form cc) A standardization of the yields is proposed before the examination stage.

Slide 30

Comparative Testing: Example A,B,C,... : Indicate diverse classes +:Indicates that a TIMEOUT happened - : Indicates that an ERROR happened

Slide 31

Comparative Testing : History A web seek uncovered that generally the term has been utilized as a part of controls other than programming. A comparative approach was utilized as a part of Microsoft for testing SQL however not simultaneousness. Enormous Stochastic Testing of SQL, Don Slutz, 24th VLDB meeting, 1998 I have seen the term utilized at a venture of the University of Washington. http://www.cs.washington.edu/homes/egs/kimera-dsl99/ppframe.htm

Slide 32

Gray Box Testing A locking scheduler is exceptionally prohibitive. It anticipates not just the presence of cycles in the Serialization Graph yet the simultaneous execution of any clashing sets of operations. In view of this presumption we

Recommended
View more...