Transcript Write skew anomaly

The ACID properties of transactions:
----------------------------------------------• Atomicity = the all or nothing update property.
• Consistency = if a database is consistent before a
transaction is exected, then the database must alo
be consistent after the transaction is executed.
• Isolation = The updates of a transaction must not
be seen by other transactions before the
transaction is committed.
• Durability = Committed data can be recovered in
case of failures.
DBMS Implementation of ACID Properties:
Logging and Recovery:
Guarantees Atomicity and Durability.
Concurrency control:
Guarantees Consistency and Isolation.
Two phase locking (2PL):
All locks must be obtained in first phase of 2PL
and released in second phase.
Number
of
locks
Lock growing phase
Commit point
shrinking
phase
Time
Is it the same phases that are used in 2PL and 2PC?
Isolation anomalies
occurs when you brake locking rules:
-----------------------------------------------
Example of Lost Update anomaly:
History: r1(x)…w2(x)…w1(x)…c1
Read
without
lock
1
Database
2. Make corrections
Reread with
exclusive
lock
3. Write
The history of Lost update anomaly:
How can the Lost Updates be prevented?
Countermeasures against isolation anomalies:
•The Reread Counter-measure
•The Commutative Updates Counter-measure
•The Version File Counter-measure
•The Version File combined with the Commutative Updates
Counter-measure
•The Pessimistic View Counter-measure
•The Semantic Lock Counter-measure
•Counter-measures by Value
•The Timestamp Counter-measure
•The Re-timestamp Counter-measure
•The End of Day Transaction Countermeasure
•
•
Countermeasures against lost updates:
r1(x)…w2(x)…w1(x)…c1
•The Reread Counter-measure can prevent lost updates, dirty
reads, non-repeatable reads, write skews and asynchronous
replication anomalies in compensatable and pivot
subtransactions
•The Commutative Updates Counter-measure can prevent lost
updates in all types of subtransactions
•The Version File Counter-measure can prevent lost updates in
all types of subtransactions
• The Version File and Commutative Updates Counter-measure
is a combination of the two countermeasures
The history of Dirty read anomaly:
The history of Fuzzy read anomaly =
Non-repeatable read anomaly:
The history of Phantom anomaly:
Countermeasures against dirty reads and
non-repeatable read anomalies :
w1(x)…r2(x)…a1...
•The Pessimistic View Countermeasure can reduce the
consequenses of dirty reads and non-repeatable read
anomalies in all types of subtransactions
•The Semantic Lock Countermeasure can reduce the
consequenses of dirty reads and non-repeatable read
anomalies in all types of subtransactions
The Pessimistic View Counter-measure:
The idea of this countermeasure is to “limit” the options of concurrent
users to prevent them in using non existing resources.
• Therefore, compensatable subtransactions should be used for updates
that decrease the users’ options. That is, concurrent transactions cannot
use resources that are reserved by a compensatable subtransaction.
• The retriable subtransactions should be used for updates that “increase”
the users’ options. That is, concurrent transactions can only use increased
resources after the increase has been committed globally.
• The pivot subtransactions may be used for updates that “increase”
and/or “limit” the users’ options because this update reflects the real
world reality.
The Semantic Lock Counter-measure:
May function as a generalization of locking if compensatable
subtransactions mark records as locked and retriable subretriable
transactions un-marks the marked records after use. However, it is
up to the concurrent transactions, how to deal with the markings.
The markings need not be restricted to be only exclisive and shared
locks. For example, the marking may be common for a special
transaction action. In accounting and product stock management, a
”counter” attribute may accumulate the number of compensatable
uncommitted stock reductions and in this situation, retriable
subtransactions should decrease the number of uncommitted stock
reductions. That is, the counter attribute is only zero when no
uncommitted transactions are using the stock.
Consistency in E commerce systems:
Customers
Orders
Locations
Orderlines
Products
Productstocks
What countermeasures are necessary in the non replicated
Product-stocks of the ERP system?
Customers
Orders
Locations
Orderlines
Productstocks in
ERP
Products
The history of the Phantom anomaly:
r1 (P)…w2(y now in P)…c2…r1 (P)...
Examples:
The phantom anomaly may occur in all transaction models when
low SQL isolation levels are used.
If consistency is needed and full isolation is unacceptable, it may
be a solution to use a data warehouse.
Anomalies between a record x and its replica y:
The Read skew anomaly illustrates that that a shared lock
(read lock) does not exclude the writing of a related record:
Read skew: r1(y)…w2(x)… w2(y)…c2… r1(x) …...
The Write skew anomaly illustrates that that an exclusive lock
(write lock) does not exclude the writing of a related record:
Write skew: r1(x)… r2(y)… w2(y)…w1(x)…c1…c2.
The Asynchronous replication anomaly illustrates that that a
exclusive lock (write lock) does not exclude the reading of a
related record:
Asynchronous replication anomaly:
w1(x)... r2(y)...c2…w1(y)… c1.
Example of the Asynchronous replication anomaly:
w1(x)…c1… r2(y)…c2…w1(y)…Asynchronous c1.
The replicated object may be patient records that may be created
locally in different hospital databases. In this situation, the
anomaly may occur when the second transaction cannot read
missing Y patient records from other hospitals, and as the patient
may have visited any hospital in the world, it can also be
difficult to get all the records of a patient.
Generalized Asynchronous Replication Anomaly:
w1(x)…c1… r2(y)…c2…w1(y)…Asynchronous c1.
The asynchronous replication anomaly can be generalized to dependencies
between related records in general. Suppose a table has information about
persons and all person records have an attribute saying whether the persons
are married or not and another attribute saying whether the persons are dead
or not.
In this case we will assume that x and y are person records where the
corresponding persons are married.
Suppose transaction 1 mark x to be a dead person and y to be a widow. In this
case, transaction 2 may read that y is married even though her husband x is
dead.
For protection the primary copy countermeasure may be generalized to
update/read related records in a fixed order. That is, in this case all related
records should be updated before a person record is marked as dead.
The replication read skew anomaly:
Read skew: r1(x)…w2(x)… w2(y)…c2… r1(y) …...
The read skew anomaly is a situation where a first transaction reads a
record. Next, a second transaction updates the record and a related
record. The updates are committed. Finally, the first transaction reads
the related record. In this situation, the first transaction may find that
the integrity rules of the database have been violated by the changes
made by the second transaction.
For protection the primary copy countermeasure may be used to
update/read related records in a fixed order.
The generalizied read skew anomaly:
Read skew: r1(y)…w2(x)… w2(y)…c2… r1(x) …...
Example: Suppose a table has information about persons and all person
records have an attribute saying whether the persons are married or not
and another attribute saying whether the persons are dead or not.
In this case we will assume that x and y are person records where the
corresponding persons are married.
Suppose transaction 2 mark x to be a dead person and y to be a widow.
In this case, transaction 1 may read that y is married even though her
husband x is dead.
For protection the primary copy countermeasure may be
generalized to update/read related records in a fixed order.
That is, in this case all related records should be updated
before a person record is marked as dead.
The replication write skew anomaly:
Write skew: r1(x)… r2(y)… w2(y)…w1(x)…c1…c2.
The write skew anomaly is a situation where two
transactions both read two different related records.
Next, the two transactions each update one of the two
related records. Finally, both transactions commit. If a
constraint has existed between the two related
records, it might have been violated.
For protection the primary copy countermeasure may
be used to update/read related records.
The generalizied write skew anomaly:
Write skew: r1(x)… r2(y)… w2(y)…w1(x)…c1…c2.
Example: Suppose a table has information about persons and all person
records have an attribute saying whether the persons are married or not
and another attribute saying whether the persons are dead or not.
In this case we will assume that x and y are person records where the
corresponding persons are married.
Suppose transaction 1 mark x to be a dead person and transaction 2
mark y to be a widow. In this case, the database is inconsistent until
transaction 1 is committed.
For protection the primary copy countermeasure may be generalized to
update/read related records in a fixed order. That is, in this case all
related records should be updated before a person record is marked as
dead.
The history of the Asynchronous replication anomaly:
w1(x)…c1… r2(y)…c2…w1(y)…Asynchronous retriable c1.
In its most simple form, the asynchronous replication anomaly
occurs when a primary record is updated by a first transaction while
a second transaction reads an outdated secondary copy.
The primary copy countermeasure can protect against the anomaly.
However, in practice the primary copy are only used in case of
updates.
The history of the Asynchronous replication anomaly:
w1(x)…c1… r2(y)…c2…w1(y)…Asynchronous retriable c1.
1. Is the Asynchronous replication anomaly acceptable when the
address of a customer is changed?
2. Is the Asynchronous replication anomaly acceptable when the
amount of available airplane tickets are red by B2C ecommerce?
3. Is the Asynchronous replication anomaly acceptable when you
want to read the diagnoses of a patient?
4. Is the Asynchronous replication anomaly acceptable if you want
to change the diagnoses of a patient?
5. Is the Asynchronous replication anomaly acceptable when you
have to decide whether to give a loan to a customer?
Consistency between E commerce/ERP systems:
Customers
Orders
Locations
Orderlines
Products
Productstocks
What countermeasures are necessary in the replicated
Product, Order, and Orderline tables?
What countermeasures are necessary in the replicated
Customer table if it does not have a balance attribute?
What countermeasures are necessary in the replicated
Customer table if it does have a balance attribute?
Airline
Design local databases and the
Design a Distributed Airline
Database
companies
workflow of an integrated
distributed database that integrate
Airports
the e-commerce sale of different
airline companies in a way that
optimize performance, availability
and consistency of a common
Plains
distributed airline system with
local databases in the airline
companies, airports, and “sale
offices” at e.g. travel agents,
Plain
hotels and
types
e-commerce servers. (Do not use a
GDS in this exercise).
Customers
Flight routes
Subroutes
Departures
Tickets
Travel
arrangement
Exercise:
Design local databases and the
workflow of an integrated distributed
database that integrate the e-commerce
sale of different airline companies, hotel
chains in a way that optimize
performance, availability and
consistency of a common distributed
system with local databases in the
airline companies, hotel chains, airports,
car rental companies, and “sale offices”
at e.g. travel agents, hotels and ecommerce servers. (Do not use a GDS
in this exercise).
Describe the workflow of the integrated
e-commerce system.
Hotel
chains
Hotels
Rooms
Room
reservations
Services/
tours/
car rentals
Customer
groups
Check-in
periods
Customers
Exercise
How would you recommend
integrating two airline
companies?
Does it make any difference
whether the companies are in
alliance or not?
What problems may occur if
travel arrangements are
converted while some of the
flights are not finished yet?
Airline
companies
Flight routes
Airports
Subroutes
Plains
Departures
Plain
types
Tickets
Can the ideas of a distributed
modular ERP system be used?
Customers
Travel
arrangement
Exercise: A GDS (Global Distribution Service) is a worldwide computerized
reservation system for reserving airline tickets, hotel rooms, rental cars, and other
travel related items. The largest GDSs are Amadeus, Galileo, Sabre, and Worldspan.
Design an integrated distributed database that integrate the databases of different
airline companies and hotel chains in a way that optimize performance, availability
and consistency of a common distributed system with local databases in GDSs, the
airline companies, hotel chains, airports, and “sale offices” at e.g. travel agents,
hotels and e-commerce servers.
Suppliers
of travel
products
GDS
Primary
online
reservation
sites
Secondary
online
reservation
sites
The relationships of the diagram illustrate that a travel product stored in one system
may be stored in many other systems from where data are replicated in sequence
from left to right between the different types of systems.
How would you design relaxed ACID properties in the global distributed system?
End of session
Thank you !!!
Anomalies between a record x and its replica y:
The Read skew anomaly illustrates that that a shared lock
(read lock) does not exclude writes globally:
Read skew: r1(x)…w2(x)… w2(y)…c2… r1(y) …...
The Write skew anomaly illustrates that that an exclusive lock
(write lock) does not exclude writes globally:
Write skew: r1(x)… r2(y)… w2(y)…w1(x)…c1…c2.
The Asynchronous replication anomaly illustrates that that a
exclusive lock (write lock) does not exclude reads globally:
Asynchronous replication anomaly:
w1(x).. r2(y)..c2..w1(y).. c1.