Week 5 Lecture 1
Download
Report
Transcript Week 5 Lecture 1
Outline
Distributed DBMS
Introduction
Background
Distributed DBMS Architecture
Distributed Database Design
Distributed Query Processing
Distributed Transaction Management
Transaction Concepts and Models
Distributed Concurrency Control
Distributed Reliability
Building Distributed Database Systems (RAID)
Mobile Database Systems
Privacy, Trust, and Authentication
Peer to Peer Systems
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 1
Useful References
C. Papadimitriou, The serializability of
concurrent database updates, Journal of the
ACM, 26(4), 1979.
S. B. Davidson, Optimism and consistency in
partitioned distributed database systems, ACM
Transactions on Database Systems 9(3): 456481, 1984.
B. Bhargava and C. Hua. A Causal Model for
Analyzing Distributed Concurrency Control
Algorithms, IEEE Transactions on Software
Engineering, SE-9, 470-486, 1983.
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 2
Transaction
A transaction is a collection of actions that make
consistent transformations of system states while
preserving system consistency.
concurrency transparency
failure transparency
Database in a
consistent
state
Begin
Transaction
Distributed DBMS
Database may be
temporarily in an
inconsistent state
during execution
Execution of
Transaction
© 1998 M. Tamer Özsu & Patrick Valduriez
Database in a
consistent
state
End
Transaction
Page 10-12. 3
Formal Definitions and Models
Definition 1:
A history is a quadruple h = (n, , M, S) where
n is a positive integer,
is a permutation of the set
n = {R1, W1, R2, W2,…,Rn, Wn
equivalently a one-to-one function
: n -> {1,2,-----,2n}
that (Ri) < (Wi) for i = 1,2,--n,
M is a finite set of variables representing physical data items,
S is a function mapping n to 2M
Set of all histories is denoted by M.
Definition 2:
A transaction Ti is a pair (Ri, Wi). A transaction is a single execution of a
program. This program may be a simple query statement expressed in a
query language.
Definition 3:
Read set of Ti is denoted by S (Ri) and Write set of Ti is denoted by S(Wi).
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 4
Formal Definitions and Models
Definition 4:
A history h = (n, , M, S) is serial if (Wi) = (Ri) + 1 for all
i = 1,2,--n. In other words, a history is serial if Ri immediately precedes Wi for i =
1,2---n.
Definition 5:
A history is serializable if there is some serial history hs such that the
effect of the execution of h is equivalent to hs. Note serializability requires
only that there exists some serial order equivalent to the actual
interleaved execution history. There may in fact be several such
equivalent serial orderings.
Definition 6:
A history h is strongly serializable if in hs the following conditions hold
true:
a) (Wi) = (Ri) + 1
b) (Ri + 1) = (Wi) + 1
If ti + 1 is the next transaction that arrived and obtained the next
time-stamp after Ti. In strongly serializable history, the following
constraint must hold “If a transaction Ti is issued before a transaction Tj,
then the total effect on the database should be equivalent to the effect that
Ti was executed before Tj.
Note if Ti and Tj are independent, e.g., {S(Ri) U S(Wi)} {S(Rj) U S(Wj)} = ø
then the effect of execution TiTj or TjTi will be the same.
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 5
Formal Definitions and Models
history
h ( n, ,V1S ).
h ( n 2 , ,V1S )
h Tn 1 h Tn 2
Live transaction (set can be found in O(n · |V|).
Two histories are equivalent () if they have the same set of live
transactions.
Equivalence can be determined O(n · |V| ).
Theorem: Testing whether a history h is serializable is NP-complete
even if h has no dead transactions.
- Polygraph: Pair of arcs between nodes
- Satisfiability: Problem of Boolean formulas in conjuctive normal forms
with two-/three literals
(SAT)
(Non-circular)
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 6
Concatenation of histories:
h1 ( n1 , 1 ,V1 ,S1 )
h2 ( n2 , 2 ,V2 ,S 2 )
h, h2 ( n1 n2 , ,V1 ,P )
( wi ) 1( wi )
in
( wi ) 2 ( wi n ) 2n for i n
same true for Ri
h1 R1W1
h2 R1W1
h1 h2 R1W1 R2W2
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 7
Two-phase locking:
h ( n, ,V ,S ) is 2PL
If distinct non-integer real numbers
1
, 2 ,...,
n
s1 ,s2 ,...,sn
( Ri )
(a)
(b)
i
(Wi )
for i = …
If s( Ri ) s( w j ) i j
& ( Ri ) (W j )
i
(c)
If
j
s(Wi ) s(W j )
& (Wi ) (W j )
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 8
Transaction Example –
A Simple SQL Query
Transaction BUDGET_UPDATE
begin
EXEC SQL UPDATE PROJ
SET
BUDGET = BUDGET1.1
WHERE PNAME = “CAD/CAM”
end.
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 9
Example Database
Consider an airline reservation example with the
relations:
FLIGHT(FNO, DATE, SRC, DEST, STSOLD, CAP)
CUST(CNAME, ADDR, BAL)
FC(FNO, DATE, CNAME,SPECIAL)
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 10
Example Transaction – SQL Version
Begin_transaction Reservation
begin
input(flight_no, date, customer_name);
EXEC SQL UPDATE FLIGHT
SET
STSOLD = STSOLD + 1
WHERE FNO = flight_no AND DATE = date;
EXEC SQL INSERT
INTO
FC(FNO, DATE, CNAME, SPECIAL);
VALUES (flight_no, date, customer_name, null);
output(“reservation completed”)
end . {Reservation}
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 11
Termination of Transactions
Begin_transaction Reservation
begin
input(flight_no, date, customer_name);
EXEC SQL SELECT
STSOLD,CAP
INTO
FROM
WHERE
if temp1 = temp2 then
temp1,temp2
FLIGHT
FNO = flight_no AND DATE = date;
output(“no free seats”);
Abort
else
EXEC SQL
EXEC SQL
UPDATE FLIGHT
SET
STSOLD = STSOLD + 1
WHERE FNO = flight_no AND DATE = date;
INSERT
INTO
FC(FNO, DATE, CNAME, SPECIAL);
VALUES (flight_no, date, customer_name, null);
Commit
output(“reservation completed”)
endif
end . {Reservation}
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 12
Example Transaction –
Reads & Writes
Begin_transaction Reservation
begin
input(flight_no, date, customer_name);
temp Read(flight_no(date).stsold);
if temp = flight(date).cap then
begin
output(“no free seats”);
Abort
end
else begin
Write(flight(date).stsold, temp + 1);
Write(flight(date).cname, customer_name);
Write(flight(date).special, null);
Commit;
output(“reservation completed”)
end
end. {Reservation}
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 13
Characterization
Ti
Transaction i
Read set (RS)
The set of data items that are read by a transaction
Write set (WS)
The set of data items whose values are changed by this
transaction
Base set (BS)
RS WS
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 14
Formalization Based on
Textbook
Let
Oij(x) be some operation Oj of transaction Ti operating on
entity x, where Oj {read,write} and Oj is atomic
OSi = j Oij
Ni {abort,commit}
Transaction Ti is a partial order Ti = {i, <i} where
i = OSi {Ni }
For any two operations Oij , Oik OSi , if Oij = R(x)
and Oik = W(x) for any data item x, then either
Oij <i Oik or Oik <i Oij
Oij OSi, Oij <i Ni
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 15
Example
Consider a transaction T:
Read(x)
Read(y)
x x + y
Write(x)
Commit
Then
= {R(x), R(y), W(x), C}
< = {(R(x), W(x)), (R(y), W(x)), (W(x), C), (R(x), C), (R(y), C)}
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 16
DAG Representation
Assume
< = {(R(x),W(x)), (R(y),W(x)), (R(x), C), (R(y), C), (W(x), C)}
R(x)
W(x)
C
R(y)
Distributed DBMS
© 1998 M. Tamer Özsu & Patrick Valduriez
Page 10-12. 17