1.TRANSACTION BASICS

______

1. Transaction:

Evaluation of a program accessing the database, reading data from it, modifying data in that. If the same program is run concurrently, say twice, then it is interpreted as 2 different transactions.

  1. 2. Model of a transaction

reading data item X: read(X)

writing data item X: write(X)

We will not deal with insertion and deletion

1.TRANSACTION BASICS

______

Example: reserving seats

T1: concels N seats on flight1, X, and reserves N seats on flight2, Y

T2: reserves M seats on flight1

T1T2

read(X);read(X) ;

X:= X-N;X:= X+M;

write(X);write(X) ;

read(Y);

Y:=Y+N;

write(Y);

1.TRANSACTION BASICS

______

  1. 3. Using the database concurrently

many transactions at the same time

optimizing CPU work ( Input/Output actions )

SHARING CPU

1 CPU2 CPUs

1.Transactions basics

______

Why we need to check concurrent transactions?

Example:

T1T2

read(X);

X:= X-N;

______

read(X) ;

X:= X+M;

______

write(X);

read(Y);

______

read(X) ;

______

Y:=Y+N;

write(Y);

Questions:

-read(X): where we get the value for X in T1, and where in T2?

-Which data is lost?

-Is the database consistent?

1.Transactions basics

______

Example:

T1T2

read(X);

X:= X-N;

write(X);

______

read(X) ;

X:= X+M;

write(X) ;

______

read(Y);

************

system failor

Question: from where we get the value for X in T1, and from wheer in T2?

Here T1 is aborted from some reason. Then it must be rolled back. But T2 already finished, the user is informed..

1.Transactions basics

______

Example: Problem with using aggregate functions

T1T3

sum:=0;

read (A) ;

sum:=sum+A;

read (X);…..

X:= X-N;…..

write(X);…..

read (X) ;

sum:=sum+X;

read (Y) ;

sum:=sum+Y;

read (Y);

Y:=Y+N;

write(Y);

Conflict eqvivalency, see file apr.15.

3.Transactions schedules

3. 3. VIEW eqvivalent schedules

Example: Decide whether the following schedules are view eqvivalent, or not, explain.

SCHEDULE1:

T1T2

read(X);

X:= X-N;

write(X);

read(Y) ;

Y:=Y+N;

write(Y);

read(X);

X:=X+M;

write(X) ;

SCHEDULE2:______

read(X) ;

X:= X-N;

write(X) ;

read(X) ;

X:=X+M;

write(X) ;

read(Y) ;

Y:=Y+N;

write(Y) ;

3.Transactions schedules

Example:Decide whether the following schedules are view eqvivalent, or not, explain.

SCHEDULE1:

T1T2

read(X);

X:= X-N;

read(X);

X:=X+M;

write(X);

read(Y) ;

write(X) ;

Y:=Y+N;

write(Y);

SCHEDULE2: T1, T2(below),

read(X);

X:= X-N;

write(X);

read(Y) ;

Y:=Y+N;

write(Y);

read(X);

X:=X+M;

write(X) ;

SCHEDULE3:T2,T1

3. Transactions schedules

Example: Decide whether the following schedules are view eqvivalent, or not, explain.

T1T2

read(X);

X:= X-N;

read(X);

X:=X+M;

write(X);

read(Y) ;

write(X) ;

Y:=Y+N;

write(Y);

T1T2

read(X);

X:=X+M;

read(X);

X:= X-N;

write(X);

write(X) ;

read(Y) ;

Y:=Y+N;

write(Y);

3. Transactions schedules

Summary:

There are schedules being (conflict or view) eqvivalent to some serial order. These schedules are called serializable.

However there are schedules which are not serializable, that is, there does not exist such a serial schedule, being eqvivalent (view or conflict) to the given one.

The schedule is surely correct, if it is serializable

3. Tranzaction schedules

How to check serializability?

 Precedence graph

 protocols: keeping given rules in the protocol, they automatically ensure serializability.

-Two phase protocols

- Time stamp based protocols

Transactions scheduling

Checking serializability:

Precedence graph (does not work in practice)

Vertices: transactions (by their id)

Edges:TiTkIF

Ti conflict Tk and Tiis scheduled before Tk

Detailed:

There is an edge TiTk IF

Tiwrites the same data item before Tkreads

Tireads the same data item before Tkwrites

Tiwrites the same data item before Tk WRITES

If the graph is acyclic  the schedule is serializable

The order can be get by topological ordering.

Transactions scheduling

Example: Draw the precedence graph to the schedule below.Is the schedule serializable? Explain. If it is, give a serial order.

T1T2

read(X)

read(Y)

read(X)

write(X)

read(Y)

write(X)

write(Y)

Hint:

1. Find first the conflicting statements. These form the arcs, keep the proper orientation.

1. Check the graph for cycles.

2. Now you now the aswer...

Example: Draw the precedence graph to the schedule below.Is the schedule serializable? Explain. If it is, give a serial order.

Megoldás:

T1T2

read(X)

read(Y)

read(X)

write(X)

read (Y)

write(X)

read(Y)

The graph is cyclic, so this schedule is not serializable.

There is another arc pointing from T2 to T1 not drawn in the figure. Which pair of statements causes that arc?

Transactions scheduling

Example: Given the precedence graph below. Is the corresponding schedule serializable? If yes, give 2 possible schedules.

Example: Given the precedence graph below. Is the corresponding schedule serializable? If yes, give 2 possible schedules.

Solution: The graph is acyclic, hence the corresponding schedule is serializable. (topologikus rendezés).

Order1:T1, T2, T3, T4, T5

Order2:T1, T2, T4, T3, T5

4. Concurrent transactions

4.1. Locking techniques

For each data item (granulity!) a flag is assigned, through which the data element can be reached.

Binary lock:

The transaction locks the data element X no other transactin can read or write it.

lock(X)

Release X: the transaction releases the data item X, now it can be reached by other transactions.

unlock(X)

This simple tehnique is not satisfactory, the system throughput would not be optimal.

Separate locks depending on actions: read or write
4. Concurrent transactions

Policy:

1. The transaction MUST submit a request before reading or writing the data item A. LOCK-X(A), LOCK-S(A).

2. The transaction has to release the data element A if the data is no more needed: UNLOCK(A)

3. The transaction does not submit a LOCK-...(A), if it already holds.

4. The transaction does not submit an UNLOCK(A) statement, if the data item A has not been locked by LOCK-..(A)

4. Concurrent transactions

4.1. Locking techniques (lock-manager)

Shared and exlusive locks

SHARED:The transaction wants to read the data item A:

Lock-s(A)

In this case other transactins can also read the same data item. That is why it is called as shared, the right for reading this element is shared.

Exclusive: The transaction wants to write the data item A:

Lock-X(A)

In this case other transaction are not able to read or write this data item A. That is why itis called exclusive.

Releasing the data item (A): unlock(A)

4. Concurrent transactions

Example: how does locking technique work?

T1T2

lock-s(Y);lock-s(X);

read(Y) ;read(X) ;

unlock(Y) ;unlock(X) ;

lock-x(X) ;lock-x(Y) ;

read(X) ;read(Y) ;

X:=X+Y;Y:=X+Y;

write(X) ;write(Y) ;

unlock(X) ;unlock(Y) ;

DATA: X=20, Y=30

SCHEDULE: T1, T2RESULT:X=50, Y=80

SCHEDULE: T2, T1RESULT:X=70, Y=50

Both results are correct, so we have to get back one of these results.

4. Concurrent transactions

EXAMPLE:Unsuccessful locking technique

T1T2

lock-s(Y);

read(Y);

unlock(Y);

lock-s(X);

read(X);

unlock(X);

lock-x(Y);

read(Y);

Y:=Y+X;

write(Y)

unlock(Y);

lock-x(X);

read(X);

X:=X+Y;

write(X);

unlock(X);

Data: X=20, Y=30 Result: X:=50, Y:= 50

So this schedule does not eqvivalent to any of the serial schedulesRESTRICTIONS NEEDED

What did cause the failor?

4. Concurrent transactions

4.2. Two phase protocol for ensuring serializability

1. Growing phase:

The transaction can submit only lock requests, adn should not release any locked data item.

2. Shrinking phase:

The locked dta item can be released, but new lock requests should not submitted

Example:

T1T2

lock-s(Y);lock-s(X);

read(Y) ;read(X) ;

lock-x(X) ;lock-x(Y) ;

unlock(Y) ;unlock(X) ;

read(X) ;read(Y) ;

X:=X+Y;Y:=X+Y;

write(X) ;write(Y) ;

unlock(X) ;unlock(Y) ;

4. Concurrent transactions

EXAMPLE:Unsuccessful locking technique

T1T2

lock-s(Y);

read(Y);

unlock(Y);

lock-s(X);

read(X);

unlock(X);

lock-x(Y);

read(Y);

Y:=Y+X;

write(Y)

unlock(Y);

lock-x(X);

read(X);

X:=X+Y;

write(X);

unlock(X);

Data: X=20, Y=30 Result: X:=50, Y:= 50

4. Concurrent transactions

Theorem:

Any schedule of transactions satisfying the 2 Phase protocol is (conflict) serializable.

Qestion: To what serial order is it eqvivalent?

Serialorder by COMMIT points

COMMIT point: Right after last LOCK..request

4. Concurrent transactions

2PHASE Protocol

Problem: Deadlock:

T1T2

lock-x(X)

lock-s(Y)

read(X)

X=X+10

read(Y)

write(X)

lock-s(X)

lock-x(Y)

……

…

T2 is waiting for T1 (X), and T1 is waiting for T2

Solution:

-Discovering building wait-for graphs, choose a victim

-Time bound, transaction abort, rollback,restart

4. Concurrent transactions

2 Phase protocol

Problem: Cascading Rollback

Example:

T1T2T3

read(A)

read(B)

write(A)

other read(A)

actionswrite(A)

...read (A)

FAILORT1 is aborted

Suppose that the schedule above is already completed with appropriate lock requests.

Because T1 must be rolled back, so T2 would be also, because it read the data written by T1, and similarly T3

4. Concurrent transactions

Modified 2 Phase protocol

Performance is better if locks can be upgraded or downgraded, still keeping the two phase.

  1. Growing phase:

-all lock request must be submit in this phase

-lock-s can be strenghtend by upgraded it into lock-x

  1. Shrinking Phase:

-Locked data item can be released, but new lock request must not be submit

-lock-x can be weakned by downgraded it into lock-s

4. Concurrency Control

Modified 2Phase Protocol

Examlple:

T1T2

lock-x(x1);lock-s(x1);

read (x1)read(x1);

lock-s(x2);T2 can not read x1

lock-s(x2);

lock-s(x3);

lock-s(x3);

.

lock-s(xn)

write(x1)

T1T2

lock-s(x1);lock-s(x1);

read (x1)read(x1);

lock-s(x2);T2 can read x1

lock-s(x2);

lock-s(x3);

lock-s(x3);

.

lock-s(xn)

upgrade(x1)

write(x1)

Concurrency control

TIMESTAMP-BASED PROTOCOL

Transaction – TS(ID)

Timestamps

Data element Q

W-timestamp(Q)R-timestamp(Q)

Concurrency control

TIMESTAMP-BASED PROTOCOL

 Tk: read (Q) statement:

1. if W-timestamp(Q)>TS(TK) TK has to be aborted

2. if W-timestamp(Q)  TS(TK) TK read (Q) is OK

 Tk : write(Q) statement:

  1. TS(TK)<W-timestamp(Q)  TK has to be aborted

2. TS(TK)<R-timestamp(Q)  TK has to be aborted

3. Otherwise write(Q) is carried out

Concurrency control

TIMESTAMP-BASED PROTOCOL

It ensures a serializable schedule since the precedence graph is cycle-free:

The times-stamp based protocol provides conflist eqvivalent schedule with respect to the order of timestamps.

Concurrency control

TIMESTAMP-BASED PROTOCOL

THOMAS’ Writing rule

TS(TK)< W-timestamp (Q)

TK : write (Q)

write(Q) is skipped , otherwise the execution continues

/The other rules are the same /

Problems: livelock

Solution: aborts should be reported, then precedence has to be given to the transaction suffering by livelock

4.Concurrency control

TIMESTAMP-BASED PROTOCOL

Transactions T1, T2, T3, T4, T5 have 1, 2, 3, 4, 5, as timestamps. The table below is a „planned” schedule. Which transactions has to be aborted? What are the timestamps of the data items? Can you apply Thomas’ writing rule?

T1 / T2 / T3 / T4 / T5
Read(Y)
Read(X)
Read(Y)
Write(Y)
Write(Z)
Write(Z)
Read(Z)
Write(X)
Read(X)
Write(Z)
Write(X)
Write(Z)

Summary: Transactions

We answered the following questions:

What is concurrent access, why it is needed, why it has to be controlled

What is good schedule (ensuring database consistency

 How can we provide serializable schedules

What we did not learn –other techniques:

-validation (seversal transactions are working on one page=block)

-graph-based locking (known db structure data ordering)

-multiple granulity (db, area, file(relation), record, field level locking)

Summary: Transactions

Real implementations

Strict 2 phase protocol: IBM DB2, Informix, Microsoft SQL-Server, Sybase ASE

Timestamp: Microsoft SQL- Server

Multiversion concurrency control: Oracle 8 (readers never wait)

All use wait-for graphs for detecting deadlocks

All support multiple-granulity (DB, Table, raw levels)

SQL statements for setting transaction levels:

Serializable (default)

Repeatable read

Read committed

Read uncomitted

Summary: Transactions

Transaction properties:

- number and type of error conditions (diagnostic size )

- ( we do not deal with)

- access mode:

read only (not eligible for writing deleting):

lock-S()

read-write – lock-X()

- isolation level:

read uncommitted

read comitted

repeatable read

serializable

Example:

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE READ ONLY

GRANTS

Syntax:

GRANT activity-list

ONtable-name

TOuser-name

WITHGRANT OPTION

Revoking:

REVOKE activity-list

ONtable-name

FROMuser-name CASCADE/RESTRICT

Translate the following pages below:

Részletesebben:

  • az adhat jogot egy objektumra (tábla, nézettábla, stb.) vonatkozóan, aki rendelkezik ezzel a joggal, és továbbadási joggal is
  • az adatbázis-adminisztrátor (DBA) kezdetben minden joggal rendelkezik minden objektumra
  • az adatbázis felhasználóit a DBA hozza létre, és adhat nekik jogokat
  • léteznek alapértelmezések
  • az objektum tulajdonosa az, aki létrehozta az objektumot
  • az objektum tulajdonosa minden joggal rendelkezik a saját objektuma felett
  • a PUBLIC az összes felhasználót jelenti

GRANT jogosultság_1,…, jogosultság_k ON objektum TO felhasználó_1, … , felhasználó_m

WITH GRANT OPTION;

  • Jogosultságok: SELECT, INSERT, DELETE, UPDATE, ALTER, ….
  • Az összes jogot jelenti az ALL.
  • A továbbadási jog a WITH GRANT OPTION, ami el is hagyható.

Példa:

  • Felhasználó_1 kiadja a következő parancsot:

GRANT insert TO Felhasználó_2 ON szeret WITH GRANT OPTION;

  • Ekkor Felhasználó_2 is továbbadhatja a kapott jogot:

GRANT insert TO Felhasználó_3 ON szeret;

Jogosultságok visszavonása

REVOKE jogosultság_1,…, jogosultság_k ON objektum FROM felhasználó_1, … , felhasználó_m;

  • A paraméterek megegyeznek a GRANT parancsnál használhatóakkal
  • A WITH GRANT OPTION segítségével továbbadott jogok is visszavonja.

Példa ( a GRANT-nál megadott példa folytatása):

Felhasználó_1 kiadja a következőt:

REVOKE insert ON szeret FROM felhasználó_2;

Hatása: Felhasználó_2 és Felhasználó_3 mindegyikétől megvonja az a szeret táblára vonatkozó insert jogot.