3/3/2019
Security and integrity
CMT207 Information modelling & database systems
1
DBMS security support
DBMS can provide some security
each user has an account name and password
these are used to identify a user and control their access to information
DBMS verifies user’s password and checks their permissions whenever they try to
view data
modify data
modify the database structure
4
Lecture
in this lecture we will consider briefly a range of issues concerning database applications
database security
aspects of security access to databases privileges and views
database integrity
view updating
integrity constraints
2
Privileges
Database security
database security is about controlling access to information
some information should be available freely
other information should only be available to certain users
many different aspects of security: legal issues
physical security
OS/network security
security policies and protocols encryption and passwords
DBMS security
3
Privileges
SQL uses different privileges to control access to tables and other database objects
SELECT privilege INSERT privilege UPDATE privilege DELETE privilege
the owner (creator) of a database has all privileges on all objects in the database and can grant privileges to other users
the owner (creator) of an object has all privileges on that object and can pass them on to others
6
1
3/3/2019
Privileges in SQL
SELECT
UPDATE
GRANT
3/3/2019
Views
privileges work at the level of tables
access can be restricted by columns access cannot be restricted by row!
views, together with privileges, allow for customised access control
a view is a table that is derived as the result of a SELECT statement
SELECT statement can then be used with views in the same way tables can
UPDATE statement can sometimes be used with views
13
Views and privileges
views and privileges are combined to control access
create a view that contains the information needed
grant privileges to that view, rather than the underlying tables
views are virtual tables
their content depends on the underlying tables we can select from views just like a table
… but what about update, insert, and delete?
16
Creating views
the name of the newly created view
CREATE VIEW
AS
3/3/2019
Example
Employee(ID, Name, Salary, Department)
we want to let the user John see Department and Name,
and be able to update Department (only) creating a view
CREATE VIEW JohnsView
AS SELECT Name, Department FROM Employee;
setting the privileges
GRANT SELECT, UPDATE(Department)
ON JohnsView TO John;
REVOKE ALL ON Employee FROM John;
19
Domains and attributes
domain constraints are data types
SQL statement:CREATE DOMAIN (note: not in Oracle)
CREATE DOMAIN Colour VARCHAR(15)
CONSTRAINT checkCol CHECK (VALUE IN (‘red’,’blue’,…);
attributes are constrained by their domains
CREATE TABLE Dress (
size Int,
col Colour );
22
Database integrity
Assertions
assertions provide a way to specify relation and database constraints
CREATE ASSERTION
assertions state a Boolean condition that must
always be true
no action is permitted that would make the condition false
often use EXISTS or NOT EXISTS note: not supported in Oracle!
23
Security vs. integrity
database security makes sure that the user is authorised to access information
database integrity makes sure that (authorised) users use that information correctly
integrity constraints:
domain constraints apply to data types
attribute constraints apply to columns
relation constraints apply to rows in a single table database constraints apply between tables
21
Relation constraints
to create a relation constraint we simply create an assertion that checks the given constraint
e.g. in the Employee table, no Bonus should be more than 15% of the employee’s Salary
CREATE ASSERTION checkSalaryBonus CHECK (
NOT EXISTS (
) );
SELECT *
FROM Employee
WHERE Bonus > 0.15*Salary
24
4
3/3/2019
Database constraints
database constraints are similar to relation constraints, but they refer to multiple tables
e.g. given tables Student(ID, Name, Department) and Enrolment(ID, Module), make sure no computer science student takes more than 12 modules
CREATE ASSERTION CSEnrolment CHECK (
NOT EXISTS (
) );
SELECT *
FROM Student AS S
WHERE S.Department=’computerscience’
AND ((SELECT COUNT(*) FROM Enrolment AS E
WHERE S.ID = E.ID) > 12
25
Constraints in Oracle
Oracle does not support domains or assertions! … but it does support row–level constraints using
CHECK
row–level constraints are declared like other constraints:
CONSTRAINT
less general than assertions since the condition refers to a single row of a single table
26
Example
add a check on the Employee table to make sure no employee’s Bonus is more than 15% of their Salary
ALTER TABLE Employee
ADD CONSTRAINT checkSalaryBonus CHECK (Bonus < 0.15*Salary);
27
5
3/3/2019
Transactions & recovery
CMT207 Information modelling & database systems
1
ACID properties
a transaction must satisfy the ACID properties: Atomicity
Consistency Isolation
Durability
4
Lecture
in the previous lecture we learn about database integrity
database integrity is paramount and DBMS often include the ability to handle transactions to maintain the integrity of data
in this lecture we introduce the concept of transaction
2
ACID properties
atomicity
transactions do not have parts
transactions cannot be executed partially
consistency
transactions take the database from one consistent
state into another
note: midway through a transaction the database might not be consistent, but at the and it has to be!
5
Transactions
a transaction is an action, or a series of actions, carried out by a single user or an application program, which reads or updates the contents of a database
a transaction is a logical unit of work that transforms the database from one consistent state to another consistent state
transactions are the units of: recovery
consistency integrity
3
ACID properties
isolation
the effects of a transaction are not visible to other
transactions until it has completed
durability
once a transaction is completed, its updates survive, even if there is a subsequent system crash
6
1
3/3/2019
Example
transaction: "transfer £50 from account A to account B"
1. read(A)
2. A=A–50
3. write(A)
4. read(B)
atomicity: should not take money from A without giving it to B
consistency: no money lost or gained overall
isolation: other queries should not see A or B change until completion
durability: the money does not go back to A
5. B=B+50
6. write(B)
7
Recovery
in theory, transactions should be durable
... but in practice we cannot always prevent all types of
failures, e.g.
system crash
power failure
disk crash
user mistake
sabotage
natural disaster
10
Transaction manager
transaction manager enforces the ACID properties
it schedules the operations of transactions
COMMIT and ROLLBACK are used to ensure atomicity
locks or timestamps are used to ensure consistency and isolation for concurrent transactions
a log is kept to ensure durability in the event of system failure
8
Transaction log
transaction log records details of all transactions
any changes transactions make to the database how to undo these changes
when transactions complete and how
the log is stored on disk, not in memory
if the system crashes, then the log is preserved
write ahead log rule
the entry in the log must be recorded before COMMIT
11
COMMIT and ROLLBACK
COMMIT signals the successful end of a transaction
any changes made by the transaction are saved
these changes become visible to other transactions
ROLLBACK signals the unsuccessful end of a transaction any changes made by the transaction are undone as if the transaction never occurred
9
System failures
a system failure affects all running transactions software crash
power failure
the physical media (disks) are not damaged at various times a DBMS takes a checkpoint
all committed transactions are written to disk
a record is made (on disk) of the transactions that are currently running
12
2
3/3/2019
System recovery
any transaction that was running at the time of failure needs to be undone and restarted
any transaction that committed since the last checkpoint needs to be redone
13
Transaction recovery
UNDO: T2, T3 active transactions: T2, T3 REDO: add them to UNDO
16
Types of transactions
needs no recovery
redo
undo and restart
COMMIT
undo and restart
redo
in progress
14
Transaction recovery
UNDO: T2, T3, T4 T4 begins
REDO: add it to UNDO
17
Transaction recovery
two lists of transaction
UNDO: all transaction that were in progress at the
last checkpoint
REDO: empty list
for each entry in the log (at the last checkpoint) do:
if a BEGIN TRANSACTION entry is found for
transaction T, then add T to UNDO
if a COMMIT entry if found for T, then move T from UNDO to REDO
15
Transaction recovery
UNDO: T2, T3, T4, T5 T5 begins
REDO: add it to UNDO
18
3
3/3/2019
Transaction recovery
UNDO: T3, T4, T5 T2 commits
REDO: T2 move it to REDO
19
Media failures
system failures are not too severe
only information since the last checkpoint is
affected
this can be recovered from the transaction log
media failures (e.g. disk crash) are more serious the data stored to disk is damaged
the transaction log itself may be damaged
22
Transaction recovery
UNDO: T3, T5 T4 commits
REDO: T2, T4 move it to REDO
20
Backups
backups are needed to recover from media failure
the transaction log and entire contents of the
database is written to secondary storage (e.g. tape)
time consuming and thus often requires down time
backup frequency
frequent enough to minimise information loss not too frequent as to cause problems
daily backup (e.g. overnight) is common
23
Forwards and backwards recovery
backwards recovery
we need to undo some transactions
working backwards through the log we undo any operation by a transaction on the UNDO list
this returns the database to a consistent state forwards recovery
some transactions need to be redone
working forwards through the log we redo any
operation by a transaction on the REDO list
this brings the database up to date
21
Recovery from media failure
1. use the last backup to restore the database
2. use the transaction log to redo any changes made since the last backup
if the transaction log is damaged, we cannot do step 2 store the transaction log and the database on separate
physical devices
this minimises the risk of losing both
24
4
3/3/2019
Concurrency control
CMT207 Information modelling & database systems
1
Problem: lost update
occurs when two different transactions are trying to update the same cell at the same time
the final value of C has increased by 5 (i.e. C=12), but should not have changed (i.e. C=7–5+5=7)
4
Transaction A
Time
Transaction B
e.g. C = 7
read(C)
t1
7
C=C–5
t2
2
t3
read(C)
7
t4
C=C+5
12
write(C)
t5
2
t6
write(C)
12
COMMIT
t7
2
t8
COMMIT
12
Concurrency
large databases are used by many users
many users → many transactions
if these transactions are run sequentially, then long transactions will make others wait for long periods
therefore, it is desirable to let transactions run concurrently
... but we need to preserve isolation
2
Problem: uncommitted update ("dirty read")
occurs when a transaction reads data that has been modified by another transaction, but not yet committed
the final value of C has not changed (i.e. C=7), but should have increased by 5 (i.e. C=12)
it should be as if transaction A never happened
5
Transaction A
Time
Transaction B
e.g. C = 7
read(C)
t1
7
C=C–5
t2
2
write(C)
t3
2
t4
read(C)
2
t5
C=C+5
7
t6
write(C)
7
ROLLBACK
t7
7
t8
COMMIT
7
Example
let C be a column
transaction A: decrease the value of C by 5, i.e. C := C – 5
transaction B: increase the value of C by 5, i.e. C := C + 5
What would be the effect on C after completing transactions A and B?
(C – 5) + 5 = C → no change in the value of C
3
Problem: inconsistent analysis
occurs when a transaction reads several values trying to aggregate them, but another transaction updates some of them
Transaction A
Time
Transaction B
e.g. C = 7, D = 4
read(C)
t1
7
C=C–5
t2
2
write(C)
t3
2
t4
read(C)
2
t5
read(D)
4
t6
SUM = C + D
6
read(D)
t7
4
D=D+5
t8
9
write(D)
9
print(SUM)
6
SUM should be C + D = 2 + 9 = 11
6
1
3/3/2019
Concurrency control
a transaction may be correct in itself, but it can still produce incorrect result if its execution is interfered by other transactions
concurrency control is about managing simultaneous execution of multiple transactions without them interfering with one another
to solve the problem, transactions use locks on shared data items before operating on them
7
Transaction A
Time
Transaction B
e.g. C = 7
read(C)
t1
7
C=C–5
t2
2
write(C)
t3
2
COMMIT
t4
2
t5
read(C)
2
t6
C=C+5
7
t7
write(C)
7
t8
COMMIT
7
Serial schedule
serial schedules are guaranteed to avoid interference and keep the database consistent
however, databases need concurrent access, which means interleaving operations from different transactions
10
Serialisability
Serialisability
two schedules are equivalent if they always have the same effect
a schedule is serialisable if it is equivalent to some serial schedule
e.g.
if two transactions only read some data items, then the
order is which they do it is not important
if transaction A reads and updates a data item C and transaction B reads and updates a different data item D, then again they can be scheduled in any order
11
Schedule
a schedule is a time–ordered execution of operations from a set of concurrent transactions
a serial schedule is a schedule in which ...
operations of individual transactions are executed
consecutively
... and do not interleave with operations from other
transactions
... and each transaction commits before another one is allowed to begin
9
Serial vs. serialisable
if two transactions only read some data items, then the order is which they do it is not important
interleaved schedule
this schedule is serialisable
serial schedule
Transaction
Operation
A
read(X)
B
read(X)
B
read(Y)
A
read(Z)
A
read(Y)
B
read(Z)
Transaction
Operation
B
read(X)
B
read(Y)
B
read(Z)
A
read(X)
A
read(Z)
A
read(Y)
~
12
2
3/3/2019
Conflict serialisability
Do two transactions have a conflict?
NO NO YES
if they refer to different resources
if they only read
if at least one is a write and they use the same resource
a schedule is conflict serialisable if transactions in the schedule have a conflict, but the schedule is still serialisable
13
Precedence graphs
to determine whether a schedule is serialisable or not, we build a precedence graph
nodes are transactions
edges are precedence: there is an edge from A to B if A must happen before B in any equivalent serial schedule
the schedule is serialisable if there are no cycles in its precedence graph
16
Conflict serialisable schedule
interleaved schedule
this schedule is serialisable even though A and B read
and write the same resources X and Y, i.e. they have a conflict 14
serial schedule
Transaction
Operation
A
read(X)
A
write(X)
B
read(X)
B
write(X)
A
read(Y)
A
write(Y)
B
read(Y)
B
write(Y)
Transaction
Operation
A
read(X)
A
write(X)
A
read(Y)
A
write(Y)
B
read(X)
B
write(X)
B
read(Y)
B
write(Y)
~
Precedence
let A and B be two transactions
let a be an action of A and b is an action of B A takes precedence over B if:
a is ahead of b in the schedule
both a and b involve the same resource R at least one of a and b is a write action
in other words, A → B if:
A read(R) A write(R) A write(R)
followed by followed by followed by
B write(R) B read(R) B write(R)
17
Conflict serialisable schedules
the main focus of concurrency control
they allow for interleaving and at the same time they
are guaranteed to behave like serial schedules
important questions:
1. How to determine whether a schedule is conflict serialisable?
2. How to construct conflict serialisable schedules?
15
Example 1
remember, A → B if:
AC
BD
this schedule is serialisable
Transaction
Action
A
write(Y)
B
read(X)
C
read(Y)
D
write(X)
B
read(Z)
D
read(Y)
A
read(Z)
A read(R) A write(R) A write(R)
followed by followed by followed by
B write(R) B read(R) B write(R)
18
3
3/3/2019
Example 2
AC
BD
this schedule is not serialisable remember, A → B if:
Transaction
Action
A
write(Y)
B
read(X)
C
read(Y)
D
write(X)
B
read(Z)
D
read(Y)
A
read(Z)
A
write(Z)
B
read(X)
A read(R) A write(R) A write(R)
followed by followed by followed by
B write(R) B read(R) B write(R)
19
Locks
two types of locks:
read lock (shared lock or S–lock)
write lock (exclusive lock or X–lock)
read lock allows several transactions simultaneously to read a resource, but no transactions can change it at the same time
write lock allows one transaction exclusive access to write to a resource and no other transaction can read this resource at the same time
the lock manager in the DBMS assigns locks and records them in the data dictionary
22
Locking
Concurrency control by locking
let T be a transaction and R be a resource
if T holds a write lock on R, then no other transactions
may lock R
if T holds a read lock on R, then no other transactions may write lock A
T must acquire a read lock on R before reading R
T must acquire a write lock on R before writing R
after using a lock on R, T must release the lock in order to free up R
if the requested lock is not available, transaction waits
23
Locking
locking is a procedure used to control concurrent access to data by ensuring serialisability of concurrent transactions
in order to use a resource (e.g. table, row, etc.) a transaction must first acquire a lock on that resource
this may deny access to other transactions to prevent incorrect results
21
Two–phase locking
a transaction follows the two-phase locking protocol (2PL) if all locking operations precede the first unlock operation in the transaction
two phases:
1. growing phase where locks are acquired on resources
2. shrinking phase where locks are released
24
4
3/3/2019
Example
A follows 2PL protocol
all of its locks are acquired before any of them is released
B does not follow 2PL
it releases its lock on X and then goes on acquire a lock on Y
25
Transaction A
Transaction B
read-lock(X)
read-lock(X)
read(X)
read(X)
write-lock(Y)
unlock(X)
unlock(X)
write-lock(Y)
read(Y)
read(Y)
Y=Y+X
Y=Y+X
write(Y)
write(Y)
unlock(Y)
unlock(Y)
Uncommitted update cannot happen with 2PL
Comment
Transaction A
Transaction B
Comment
read–lock(C)
read(C)
C=C–5
write–lock(C)
write(C)
read(C)
waits for A
to release write–lock(C)
C=C+5
write(C)
locks released
ROLLBACK
COMMIT
28
Serialisability theorem
Any schedule of two–phased transactions is conflict serialisable.
26
Inconsistent analysis cannot happen with 2PL
Comment
Transaction A
Transaction B
Comment
read–lock(C)
read(C)
C=C–5
write–lock(C)
write(C)
read(C)
waits for A
to release write–lock(C) and later write–lock(D)
read(D)
sum = C + D
read–lock(D)
read(D)
D=D+5
write–lock(D)
write(D)
29
Lost update cannot happen with 2PL
Comment
Transaction A
Transaction B
Comment
read–lock(C)
read(C)
C=C–5
read(C)
read–lock(C)
C=C+5
cannot acquire write–lock(C) because B has read–lock(C)
write(C)
write(C)
cannot acquire write–lock(C) because A has read–lock(C)
COMMIT
COMMIT
27
Deadlocks
5
3/3/2019
Deadlocks
deadlock detection deadlock prevention timestamping
31
Wait for
transaction B waits for A in any of the following scenarios: A read–locks R, then B tries to write–lock it
A write–locks R, then B tries to read–lock it
A write–locks R, then B tries to write–lock it
34
Deadlock
the use of locks solves one problem (serialising schedules)
... but introduces another (deadlocked schedules)
deadlock is a situation in which two or more transactions are in a simultaneous wait state, each waiting for others to release a lock
e.g.
transaction A has a lock on a resource C and is
waiting for a lock on a resource D
transaction B has a lock on a resource D and is waiting for a lock on a resource C
32
Transaction
Action
Lock
Waits for
A
write(P)
write–lock(P)
C
read(S)
read–lock(S)
D
read(R)
read–lock(R)
C
read(P)
A
B
write(R)
D
C
read(S)
read–lock(S)
B
read(Q)
read–lock(Q)
D
write(P)
A
A
read(Q)
read–lock(Q)
A
write(Q)
B
B
read(S)
read–lock(S)
Example
AC
BD
the transactions will be deadlocked
35
Wait–for graphs
given a schedule, potential deadlocks can be detected using a wait–for graph (WFG)
nodes are transactions
there is an edge from transaction B to transaction A if B
waits for A, i.e.
A holds a lock on a resource R
B is waiting for a lock on the resource R
B cannot get the lock on R unless A releases it
if the graph does not contain cycles, then the schedule will not be deadlocked
33
Deadlock prevention
deadlocks can arise with two–phase locking
deadlock is less of a problem than an inconsistent
database
we can detect and recover from deadlock
... but it would be nice to avoid it altogether
e.g. conservative two–phase locking
all locks must be acquired before the transaction starts
low 'lock utilisation' – transactions can hold on to locks for a long time, but not effectively use them much
36
6
3/3/2019
Deadlock prevention
deadlocks may be prevented if transactions are to lock resources in some arbitrary but fixed order
we impose an ordering on the resources
transactions must acquire locks in this order
transactions can be ordered on the last resource they locked
this prevents deadlock
if B is waiting for a resource from A then that
resource must come after all of A's current locks
all edges in the wait–for graph point 'forwards', so no cycles
37
Timestamping
transactions can run concurrently using a variety of techniques
we previously looked at using locks to prevent interference
an alternative technique is timestamping
requires less overhead in terms of tracking locks or
detecting deadlocks
determines the order of transactions before they are executed
40
Resource ordering
let the resource order be X < Y, i.e.
if a transaction need locks on X and Y, it will first
acquire a lock on X and only afterwards a lock on Y
it is impossible to end up in a situation where:
B is waiting for a lock on X held by A, and
A is waiting for a lock on Y held by B
therefore, no deadlocks
38
Timestamping
each transaction has a timestamp, TS
if transaction A starts before transaction B,
then TS(A) < TS(B)
timestamps can be generated using the system clock or an incrementing counter
each resource X has two timestamps:
R(X) the largest timestamp of any transaction
that has read X
W(X) the largest timestamp of any transaction that has written X
41
Timestamping
Timestamp protocol
let T be a transaction and X be a resource If T tries to read X, then
if TS(T) < W(X), then T is rolled back and restarted with a later timestamp
otherwise the read succeeds and R(X) is set to be max(R(X), TS(T))
if T tries to write X, then
if TS(T) < W(X) or TS(T) < R(X), then T is rolled back
and restarted with a later timestamp
otherwise the write succeeds and W(X) is set to TS(T)
42
7
3/3/2019
Example
let A and B be two transactions we assume that:
the transactions make alternate actions
timestamps are allocated from a counter starting with 1
A goes first
A
B
read(X)
read(X)
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
43
Example
resources
transactions
TS
A
TS
B
1
read(X)
2
read(X)
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
2
W
A
B
TS
1
2
no W(X) stamp, so B succeeds in read(X)
R(X) is set to max(R(X), TS(B)) = max(1, 2) = 2
46
Example
resources
transactions
TS
A
TS
B
read(X)
read(X)
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
W
A
B
TS
44
Example
resources
transactions
TS
A
TS
B
read(X)
2
read(X)
1
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
2
1
W
A
B
TS
1
2
no W(Y) stamp, so A succeeds in read(Y) R(Y) is set to TS(A), which is 1
47
Example
resources
transactions
TS
A
TS
B
1
read(X)
read(X)
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
1
W
A
B
TS
1
no W(X) stamp, so A succeeds in read(X) R(X) is set to TS(A), which is 1
45
Example
resources
transactions
TS
A
TS
B
read(X)
read(X)
1
read(Y)
2
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
2
2
W
A
B
TS
1
2
no W(Y) stamp, so B succeeds in read(Y)
R(Y) is set to max(R(Y), TS(B)) = max(1, 2) = 2
48
8
3/3/2019
Example
resources
transactions
TS
A
TS
B
read(X)
read(X)
read(Y)
2
read(Y)
1
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
2
2
W
A
B
TS
1
2
no reading or writing, so no change in timestamps
49
Example
resources
transactions
TS
A
TS
B
read(X)
read(X)
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
2
2
W
A
B
TS
3
2
A is rolled back and restarted with a later timestamp
52
Example
resources
transactions
TS
A
TS
B
read(X)
read(X)
read(Y)
read(Y)
1
Y=Y+X
2
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
2
2
W
A
B
TS
1
2
no reading or writing, so no change in timestamps
50
Example
resources
transactions
TS
A
TS
B
read(X)
read(X)
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
2
write(Z)
X
Y
Z
R
2
2
W
2
A
B
TS
3
2
B succeeds to write(Z)
W(Z) is set to TS(B), which is 2
53
Example
TS(A) = 1 < 2 = read(Y)
resources
transactions
TS
A
TS
B
read(X)
read(X)
read(Y)
read(Y)
Y=Y+X
2
Z=Y–X
1
write(Y)
write(Z)
X
Y
Z
R
2
2
W
A
B
TS
1
2
51
Example
A succeeds in read(X)
R(X) is set to TS(A), which is 3
resources
transactions
TS
A
TS
B
3
read(X)
read(X)
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
3
2
W
2
A
B
TS
3
2
54
9
3/3/2019
Example
A succeeds in read(Y)
R(Y) is set to TS(A), which is 3
resources
transactions
TS
A
TS
B
read(X)
read(X)
3
read(Y)
read(Y)
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
3
3
W
2
A
B
TS
3
2
55
Timestamping
transactions with higher timestamps take precedence equivalent to running transactions in order of their
final time values
no waiting, no deadlock
disadvantages
long transactions might keep getting restarted by
new transactions
rolls back old transactions, which may have done a lot of work
58
Example
resources
transactions
TS
A
TS
B
read(X)
read(X)
read(Y)
read(Y)
3
Y=Y+X
Z=Y–X
write(Y)
write(Z)
X
Y
Z
R
3
3
W
2
A
B
TS
3
2
no reading or writing, so no change in timestamps
56
Example
resources
transactions
TS
A
TS
B
read(X)
read(X)
read(Y)
read(Y)
Y=Y+X
Z=Y–X
3
write(Y)
write(Z)
X
Y
Z
R
3
3
W
3
2
A
B
TS
3
2
A succeeds to write(Y)
W(Y) is set to TS(A), which is 3
57
10