Microsoft PowerPoint – 13- 3NF_Transaction Managemet
© 2018 A. Alawini & A. Parameswaran
Database Design: 3NF
& Transaction
Management
Abdu Alawini
University of Illinois at Urbana-Champaign
CS411: Database Systems
October 15, 2018
1
© 2018 A. Alawini & A. Parameswaran
Announcements
• HW 2 is due TODAY (23:59)
• Midterm: 10/29 in class 11-12:15 pm
• I’ll announce the midterm review session once
I reserve a room.
2
© 2018 A. Alawini & A. Parameswaran
Outline
Third Normal forms (3NF)
Transactions and ACID properties: the dangers in concurrent executions
(Ch. 6.6)
Transactions and SQL: isolation levels (Ch. 18.1-18.4)
3
© 2018 A. Alawini & A. Parameswaran
Normal Forms
First Normal Form = all attributes are atomic
Second Normal Form (2NF) = old and obsolete
Boyce Codd Normal Form (BCNF)
Third Normal Form (3NF)
Fourth Normal Form (4NF)
Others…
4
© 2018 A. Alawini & A. Parameswaran
3NF: A Problem with BCNF
Phone Address Name
FD’s: Phone -> Address; Address, Name -> Phone
So, there is a BCNF violation (Phone Address), and we decompose.
Phone Address
Phone Name
Phone -> Address
No FDs
5
© 2018 A. Alawini & A. Parameswaran
So where’s the problem?
Phone Address Phone Name
1234 10 Downing 1234 John
5678 10 Downing 5678 John
FD’s: Phone-> Address; Address, Name -> Phone
No problem so far. All local FD’s are satisfied.
Let’s put all the data into a single table:
Phone Address Name
1234 10 Downing John
5678 10 Downing John
Violates the dependency: Address, Name Phone
6
© 2018 A. Alawini & A. Parameswaran
Preserving FDs
•Thus, if the X and Y of a FD X->Y do not both end up in
the same decomposed relation:
• Such a decomposition is not “dependency-preserving.”
• No way to force BCNF to preserve dependencies
•Thus, while BCNF gives us lossless join and less
redundancy, it doesn’t give us dependency preservation
7
© 2018 A. Alawini & A. Parameswaran
An alternative: 3rd Normal Form (3NF)
A simple condition for removing anomalies from relations:
A relation R is in 3rd normal form if :
Whenever there is a nontrivial dependency A1, A2, …, An -> B
for R, then {A1, A2, …, An } is a super-key for R,
or B is part of a key.
Prevents the “Phone Address” FD from causing a decomposition
Textbook uses rule with many Bi on the RHS, if so, then each one must
be part of some key.
8
© 2018 A. Alawini & A. Parameswaran
3NF vs. BCNF
• R is in BCNF if whenever X->A holds, then X is a superkey.
• Slightly stricter than 3NF.
• Doesn’t let R get away with it if A is part of some key
• Thus, BCNF “more aggressive” in splitting
• Example: R(A,B,C) with {A,B}->C, C->A
• 3NF but not BCNF
9
© 2018 A. Alawini & A. Parameswaran
Decomposing R into 3NF
• Some preliminaries first: the “minimal basis”
10
© 2018 A. Alawini & A. Parameswaran
Minimal basis
• Given a set of FDs: S.
• Say the set S’ is equivalent to S, in the sense that S’ can be inferred
from S and v. versa.
• Any such S’ is said to be a basis for S.
• “Minimal basis”
• A basis with all RHS singletons, where any modifications lead to no
longer a basis, including:
• Dropping attribute from LHS of a rule: compact rules
• Dropping a rule: small # of rules
11
© 2018 A. Alawini & A. Parameswaran
Example of minimal basis
• R(A, B, C) with FDs:
• A -> B,C; B -> A,C; C -> A,B
• A basis:
• A->B; A->C; B->A; B->C; C->A; C->B
• One minimal basis:
• A->B
• B->C
• C->A
• Check this.
12
© 2018 A. Alawini & A. Parameswaran
Conversion into minimal basis
• “Minimal basis” Condition
• A basis with all RHS singletons, where any modifications lead to no
longer a basis, including:
• Dropping an attribute from the LHS of a rule
• Dropping a rule
Algorithm for converting S to a minimal basis
• R = S with all RHS singletons:
• Repeat until convergence:
• If a rule minus an attribute from LHS is inferred from S, replace rule
with rule minus attribute from LHS
• If a rule is inferred from rest, drop it
13
© 2018 A. Alawini & A. Parameswaran
Minimal basis example
Given R (u v w x y) and F = { U->X, VW->UX, W->V, Y->U, Y->X}
Find F’, the minimal basis for F. Algorithm:
1- Only singleton in RHS
2- Remove unnecessary att. from LHS
3- Remove FDs that can be inferred
from the rest
14
© 2018 A. Alawini & A. Parameswaran
Decomposing R into 3NF
1. Get a “minimal basis” G of given FDs (Section 3.2.7)
2. For each FD A B in the minimal basis G, use AB as the
schema of a new relation.
3. If none of the schemas from Step 2 is a superkey, add
another relation whose schema is a key for the original
relation.
Result will be lossless, will be dependency-preserving, 3NF;
might not be BCNF
15
© 2018 A. Alawini & A. Parameswaran
Decomposing R into 3NF
1. Get a “minimal basis” G of given FDs (Section 3.2.7)
2. For each FD A B in the minimal basis G, use AB as the
schema of a new relation.
3. If none of the schemas from Step 2 is a superkey, add
another relation whose schema is a key for the original
relation. Implicitly this is connecting all the LHSs with the
remaining attributes
Result will be lossless, will be dependency-preserving
Basically every minimal FD is preserved somewhere
16
© 2018 A. Alawini & A. Parameswaran
Example
•R(A, B, C) with FDs:
• A -> B,C; B -> A,C; C -> A,B
Minimal Basis: A->B; B->C; C->A
So, first cut:
R(A, B), R(B, C), R(C, A)
Any attributes left? Nope done
17
© 2018 A. Alawini & A. Parameswaran
Example
•R(A, B, C, D, E) with FDs:
• A -> B; CD -> B; DA -> C
BCNF Decomp:
(AB), (ACD), (ADE) or:
(BCD), (ACD), (ADE)
Which FDs do each of these not preserve?
Minimal Basis:
A -> B; CD -> B; DA -> C
3NF Decomp: (AB), (BCD), (ACD), (ADE)
18
© 2018 A. Alawini & A. Parameswaran
3NF
1) minimize redundancy
✔2) avoid info loss
✔ 3) preserve dependency
4) ensure good query performance
Desirable Properties of Schema Refinement
19
© 2018 A. Alawini & A. Parameswaran
Fact of life…
Finding a decomposition which is both lossless and dependency-
preserving is not always possible.
Guideline: Aim for BCNF and settle for 3NF
20
© 2018 A. Alawini & A. Parameswaran
Multi-valued Dependencies and 4NF
•we will not cover this.
21
© 2018 A. Alawini & A. Parameswaran
Caveat
•Normalization is not the be-all and end-all of DB design
•Example: suppose attributes A and B are always used
together, but normalization theory says they should be in
different tables.
• decomposition might produce unacceptable performance loss
(extra disk reads)
22
© 2018 A. Alawini & A. Parameswaran
Outline
Third Normal forms (3NF)
Transactions and ACID properties: the dangers in concurrent executions
(Ch. 6.6)
Transactions and SQL: isolation levels (Ch. 18.1-18.4)
23
© 2018 A. Alawini & A. Parameswaran
Transaction Management
Ch 6.6.1 – 6.6.3
and 18.1-18.4
24
© 2018 A. Alawini & A. Parameswaran
Motivating “Transactions”
•We’ve learned how to interact with DB using SQL.
•We assumed that:
• each operation (e.g., UPDATE … SET … WHERE) is executed
one at a time. One operation executes, perhaps changes the DB
state, then next operation executes. (ISOLATION)
• each operation is executed in entirety or not executed at all.
(ATOMIC)
•Complications arise if these assumptions are violated
• multiple operations acting on the same table simultaneously?
• system crash in the middle of an operation (e.g., half the tuples
have been updated the others not)
25
© 2018 A. Alawini & A. Parameswaran
Example 1: flight seat selection
• Program:
• Check if seat is available : SFW (A)
• Book seat (change availability to “occupied”): USW (B)
Two simultaneous runs
A1
A2
B1
B2
• Two executions of the same “UPDATE … SET … WHERE” leads to seat
being double-booked
26
© 2018 A. Alawini & A. Parameswaran
Example 1: lesson
• Group the “SELECT … FROM … WHERE” (which retrieved seat
availability) and the “UPDATE … SET … WHERE” (which reserved a seat)
into one TRANSACTION.
• Transaction is a sequence of statements that are considered a “unit of
operation” on a database
• Either user1’s transaction executes first and then user2’s transaction, or
the other way, but not in parallel. Serializability of transactions.
27
© 2018 A. Alawini & A. Parameswaran
Example 2: bank inter-account transfer
28
Problems can also occur if a crash occurs in the middle of executing
a transaction:
Need to guarantee that the write to X does not persist (ABORT)
• Default assumption if a transaction doesn’t commit
Transfer
read(X.bal)
read(Y.bal)
{X.bal= X.bal-$100}
write(X.bal)
Y.bal= Y.bal+$100
write(Y.bal)
CRASH
© 2018 A. Alawini & A. Parameswaran
Example 2: lesson
•Steps 2 and 3 must be done as one unit. Atomically.
•Either they both execute, or neither does.
•Transactions must be atomic.
29
© 2018 A. Alawini & A. Parameswaran
Transactions
•Standard notion for updates is a transaction:
• Sequence of read and write operations on data items
that logically functions as one unit of work
• If it succeeds, the effects of all write operations persist
(commit); if it fails, no effects persist (abort)
• These guarantees are made despite concurrent activity
in the system, and despite failures that may occur
30
© 2018 A. Alawini & A. Parameswaran
Transaction Manager
•Part of the DBMS
• Its job is to ensure that a transaction is executed as
expected.
•Purpose 1: Ensure that transactions that
execute in parallel don’t interfere with each
other.
•Purpose 2: Talks to “Log Manager”, ensures that
steps inside a transaction are being “logged”.
•Purpose 3: Performs recovery after crashes, using
logs.
•We will not cover recovery in this class.
31
© 2018 A. Alawini & A. Parameswaran
ACID Properties
Atomicity
• either all of the actions of a transaction are executed, or none
are.
Consistency
• each transaction executed in isolation keeps the database in a
consistent state
Isolation
• Transactions are isolated from the effects of other, concurrently
executing, transactions.
Durability
• updates stay in the DBMS!!!
32
© 2018 A. Alawini & A. Parameswaran
Outline
Third Normal forms (3NF)
Transactions and ACID properties: the dangers in concurrent executions
(Ch. 6.6)
Transactions and SQL: isolation levels (Ch. 18.1-18.4)
33
© 2018 A. Alawini & A. Parameswaran
Transactions in SQL
• A transaction begins when any SQL statement that queries the db
begins.
• To end a transaction, the user issues a COMMIT or ROLLBACK
statement.
Transfer
BEGIN
UPDATE Accounts
SET balance = balance – $100
WHERE account#= ‘1234’;
UPDATE Accounts
SET balance = balance + $100
WHERE account#= ‘5678’;
COMMIT; 34
© 2018 A. Alawini & A. Parameswaran
Read-Only Transactions
• When a transaction only reads information, we have more
freedom to let the transaction execute concurrently with other
transactions.
• We signal this to the system by stating:
SET TRANSACTION READ ONLY;
SELECT * FROM Accounts
WHERE account#=‘1234’;
…
35
© 2018 A. Alawini & A. Parameswaran
Read-Write Transactions
• If we state “read-only”, then the transaction cannot perform any updates.
• Instead, we must specify that the transaction may update (the default):
SET TRANSACTION READ ONLY;
UPDATE Accounts
SET balance = balance – $100
WHERE account#= ‘1234’; …
SET TRANSACTION READ WRITE;
update Accounts
set balance = balance – $100
where account#= ‘1234’; …
ILLEGAL!
36