Transcript presentation source

Databases on 1 Foot
Joe Hellerstein
Computer Science Division
UC Berkeley
Overview for the day
•
•
•
•
•
•
Motivation
Relational model
Relational Algebra
SQL
Concurrency Control
Recovery
What we’re skipping
• Access Methods
– disk layout for tuples and pages
– indexes (B-trees, linear hashing)
• Query optimization
– how to map a declarative query (SQL) to a query
plan (relational algebra + implementations)
• Query processing algorithms
– sort, hash, join algorithms
• Database design
– logical design: E-R models & normalization
– physical design: indexes, clustering, tuning
More Background
• Overview Texts:
– Ramakrishnan, Database Management Systems (the cow
book)
– Silberschatz, Korth, Sudarshan: Database System Concepts
(the sailboat book)
– O’Neil: Database Principles, Programming, Performance
– Ullman & Widom: A 1st Course in Database Systems
• Graduate-level Texts
– Stonebraker & Hellerstein, eds. Readings in Database
Systems (http://redbook.cs.berkeley.edu)
– Gray & Reuter: Transaction Processing: Concepts and
Techniques.
– Ullman: Principles of Database Systems
Database Management Systems
• What more could we want than a file system?
– Simple, efficient ad hoc1 queries
– concurrency control
– recovery
– benefits of good data modeling
1ad
hoc: formed or used for specific or immediate problems or needs
Describing Data: Data Models
• A data model is a collection of concepts for
describing data.
• A schema is a description of a particular
collection of data, using the a given data
model.
• The relational model of data is the most widely
used model today.
– Main concept: relation, basically a table with rows
and columns.
– Every relation has a schema, which describes the
columns, or fields.
Levels of Abstraction
• Many views, single
conceptual (logical) schema
and physical schema.
– Views describe how users
see the data.
– Conceptual schema defines
logical structure
– Physical schema describes
the files and indexes used.
View 1
View 2
View 3
Conceptual Schema
Physical Schema
Example: University Database
• Conceptual schema:
– Students(sid: string, name: string, login: string,
age: integer, gpa:real)
– Courses(cid: string, cname:string, credits:integer)
– Enrolled(sid:string, cid:string, grade:string)
• Physical schema:
– Relations stored as unordered files.
– Index on first column of Students.
• External Schema (View):
– Course_info(cid:string,enrollment:integer)
Data Independence
• Applications insulated from how data is
structured and stored.
• Logical data independence: Protection from
changes in logical structure of data.
• Physical data independence: Protection from
changes in physical structure of data.
 One of the most important benefits of using a DBMS!
These layers
must consider
concurrency
control and
recovery
Structure of a DBMS
• A typical DBMS has a
layered architecture.
• The figure does not show
the concurrency control
and recovery
components.
• This is one of several
possible architectures;
each system has its own
variations.
Query Optimization
and Execution
Relational Operators
Files and Access Methods
Buffer Management
Disk Space Management
DB
Advantages of a DBMS
•
•
•
•
•
•
•
Data independence
Efficient data access
Data integrity & security
Data administration
Concurrent access, crash recovery
Reduced application development time
So why not use them always?
– Can be expensive, complicated to set up and
maintain
– This cost & complexity must be offset by need
- Often worth it!
Relational Algebra
By relieving the brain of all unnecessary
work, a good notation sets it free to
concentrate on more advanced problems,
and, in effect, increases the mental power of
the race.
-- Alfred North Whitehead (1861 - 1947)
p
Relational Query Languages
• Query languages: Allow manipulation and retrieval of
data from a database.
• Relational model supports simple, powerful QLs:
– Strong formal foundation based on logic.
– Allows for much optimization.
• Query Languages != programming languages!
– QLs not expected to be “Turing complete”.
– QLs not intended to be used for complex calculations.
– QLs support easy, efficient access to large data sets.
Formal Relational Query Languages
Two mathematical Query Languages form the
basis for “real” languages (e.g. SQL), and for
implementation:
 Relational Algebra: More operational, very
useful for representing internal execution
plans. (Database byte-code…)
 Relational Calculus: Lets users describe what
they want, rather than how to compute it.
(Non-operational, declarative -- SQL comes
from here.)
Preliminaries
• A query is applied to relation instances, and the
result of a query is also a relation instance.
– Schemas of input relations for a query are fixed (but
query will run regardless of instance!)
– The schema for the result of a given query is also
fixed! Determined by definition of query language
constructs.
– Languages are closed (can compose queries)
R1
Example Instances
• “Sailors” and “Reserves”
relations for our examples.
S1
• We’ll use positional or named
field notation, assume that
names of fields in query
results are `inherited’ from
names of fields in query input
relations.
sid bid
day
22 101 10/10/96
58 103 11/12/96
sid
22
31
58
sname rating age
dustin
7
45.0
lubber
8
55.5
rusty
10 35.0
S2 sid
sname rating age
yuppy
9
35.0
lubber
8
55.5
guppy
5
35.0
rusty
10 35.0
28
31
44
58
Relational Algebra
• Basic operations:
– Selection ( ) Selects a subset of rows from relation.
– Projection (p ) Deletes unwanted columns from
relation.
– Cross-product (
) Allows us to combine two relations.
– Set-difference (
) Tuples in reln. 1, but not in reln. 2.
– Union (  ) Tuples in reln. 1 and in reln. 2.
• Additional operations:
– Intersection, join, division, renaming: Not essential, but
(very!) useful.


Projection
• Deletes attributes that are not in
projection list.
• Schema of result:
– exactly the fields in the
projection list, with the same
names that they had in the
(only) input relation.
• Projection operator has to
eliminate duplicates! (Why??)
– Note: real systems typically
don’t do duplicate elimination
unless the user explicitly asks
for it. (Why not?)
sname
rating
yuppy
lubber
guppy
rusty
9
8
5
10
p sname,rating(S2)
age
35.0
55.5
p age(S2)
Selection
• Selects rows that satisfy
selection condition.
• No duplicates in result!
• Schema of result:
– identical to schema of
(only) input relation.
• Result relation can be the
input for another relational
algebra operation!
(Operator composition.)
sid sname rating age
28 yuppy 9
35.0
58 rusty
10
35.0
 rating 8(S2)
sname rating
yuppy 9
rusty
10
p sname,rating( rating 8(S2))
Union,
Intersection,
Set-Difference
• All of these operations take
two input relations, which
must be union-compatible:
– Same number of fields.
– `Corresponding’ fields
have the same type.
• What is the schema of result?
sid sname
22 dustin
rating age
7
45.0
S1 S2
sid sname
rating age
22
31
58
44
28
7
8
10
5
9
dustin
lubber
rusty
guppy
yuppy
S1 S2
sid sname
31 lubber
58 rusty
45.0
55.5
35.0
35.0
35.0
rating age
8
55.5
10
35.0
S1 S2
Cross-Product
• S1 x R1: Each row of S1 is paired with each row of
R1.
• Result schema has one field per field of S1 and R1,
with field names `inherited’ if possible.
– Conflict: Both S1 and R1 have a field called sid.
(sid) sname rating age
(sid) bid day
22
dustin
7
45.0
22
101 10/10/96
22
dustin
7
45.0
58
103 11/12/96
31
lubber
8
55.5
22
101 10/10/96
31
lubber
8
55.5
58
103 11/12/96
58
rusty
10
35.0
22
101 10/10/96
58
rusty
10
35.0
58
103 11/12/96
 Renaming operator:
 (C(1 sid1, 5 sid2), S1 R1)
Joins
• Condition Join:
(sid) sname
22
dustin
31
lubber
R  c S   c ( R  S)
rating age
7
45.0
8
55.5
S1
(sid) bid
58
103
58
103
S1.sid  R1.sid
day
11/12/96
11/12/96
R1
• Result schema same as that of cross-product.
• Fewer tuples than cross-product, might be
able to compute more efficiently
• Sometimes called a theta-join.
Joins
• Equi-Join: Special case: condition c contains only
conjunction of equalities.
sid
22
58
sname
dustin
rusty
rating age
7
45.0
10
35.0
S1 
sid
bid
101
103
day
10/10/96
11/12/96
R1
• Result schema similar to cross-product, but only
one copy of fields for which equality is specified.
• Natural Join: Equijoin on all common fields.
Basic SQL Query
SELECT
FROM
WHERE
[DISTINCT] target-list
relation-list
qualification
• relation-list : A list of relation names
– possibly with a range-variable after each name
• target-list : A list of attributes of tables in relation-list
• qualification : Comparisons combined using AND, OR and
NOT.
– Comparisons are Attr op const or Attr1 op Attr2, where op is
one of , , , , , 
• DISTINCT: optional keyword indicating that the answer
should not contain duplicates.
– Default is that duplicates are not eliminated!
Conceptual Evaluation Strategy
• Semantics of an SQL query defined in terms of the
following conceptual evaluation strategy:
– Compute the cross-product of relation-list.
– Discard resulting tuples if they fail qualifications.
– Delete attributes that are not in target-list.
– If DISTINCT is specified, eliminate duplicate rows.
• Probably the least efficient way to compute a query!
– An optimizer will find more efficient strategies same
answers.
Example of Conceptual Evaluation
SELECT S.sname
FROM Sailors S, Reserves R
WHERE S.sid=R.sid AND R.bid=103
(sid) sname rating age
(sid) bid day
22
dustin
7
45.0
22
101 10/10/96
22
dustin
7
45.0
58
103 11/12/96
31
lubber
8
55.5
22
101 10/10/96
31
lubber
8
55.5
58
103 11/12/96
58
rusty
10
35.0
22
101 10/10/96
58
rusty
10
35.0
58
103 11/12/96
A Note on Range Variables
• Really needed only if the same relation
appears twice in the FROM clause. The
previous query can also be written as:
SELECT S.sname
FROM Sailors S, Reserves R
WHERE S.sid=R.sid AND bid=103
OR
SELECT sname
FROM Sailors, Reserves
WHERE Sailors.sid=Reserves.sid
AND bid=103
Some folks suggest
using range
variables always!
Find sailors who’ve reserved at least one
boat
SELECT S.sid
FROM Sailors S, Reserves R
WHERE S.sid=R.sid
• Would adding DISTINCT to this query make a
difference?
• What is the effect of replacing S.sid by S.sname in
the SELECT clause?
– Would adding DISTINCT to this variant of the query
make a difference?
Expressions and Strings
SELECT S.age, age1=S.age-5, 2*S.age AS age2
FROM Sailors S
WHERE S.sname LIKE ‘B_%B’
• Arithmetic expressions, string pattern matching.
• AS and = are two ways to name fields in result.
• LIKE is used for string matching.
– `_’ stands for any one character and `%’ stands for 0 or
more arbitrary characters.
Aggregate Operators
• Significant extension of
relational algebra.
SELECT COUNT (*)
FROM Sailors S
SELECT AVG (S.age)
FROM Sailors S
WHERE S.rating=10
COUNT (*)
COUNT ( [DISTINCT] A)
SUM ( [DISTINCT] A)
AVG ( [DISTINCT] A)
MAX (A)
MIN (A)
single column
SELECT S.sname
FROM Sailors S
WHERE S.rating= (SELECT MAX(S2.rating)
FROM Sailors S2)
SELECT COUNT (DISTINCT S.rating)
FROM Sailors S
WHERE S.sname=‘Bob’
SELECT AVG ( DISTINCT S.age)
FROM Sailors S
WHERE S.rating=10
Find name and age of the oldest sailor(s)
• The first query is illegal!
– We’ll look into the reason
a bit later, when we
discuss GROUP BY.
• Third query equivalent to
second query
– allowed in SQL/92
standard, but not
supported in some
systems.
SELECT S.sname, MAX (S.age)
FROM Sailors S
SELECT S.sname, S.age
FROM Sailors S
WHERE S.age =
(SELECT MAX (S2.age)
FROM Sailors S2)
SELECT S.sname, S.age
FROM Sailors S
WHERE (SELECT MAX (S2.age)
FROM Sailors S2)
= S.age
GROUP BY and HAVING
• So far, we’ve applied aggregate operators to all
(qualifying) tuples.
– Sometimes, we want to apply them to each of several
groups of tuples.
• Consider: Find the age of the youngest sailor for
each rating level.
– In general, we don’t know how many rating levels
exist, and what the rating values for these levels are!
– Suppose we know that rating values go from 1 to 10;
we can write 10 queries that look like this (!):
SELECT MIN (S.age)
For i = 1, 2, ... , 10:
FROM Sailors S
WHERE S.rating = i
Queries With GROUP BY and HAVING
SELECT
FROM
WHERE
GROUP BY
HAVING
[DISTINCT] target-list
relation-list
qualification
grouping-list
group-qualification
• The target-list contains (i) attribute names (ii) terms
with aggregate operations (e.g., MIN (S.age)).
– The attribute list (i) must be a subset of grouping-list.
Intuitively, each answer tuple corresponds to a group, and
these attributes must have a single value per group. (A
group is a set of tuples that have the same value for all
attributes in grouping-list.)
Conceptual Evaluation
• The cross-product of relation-list is computed, tuples
that fail qualification are discarded, `unnecessary’
fields are deleted, and the remaining tuples are
partitioned into groups by the value of attributes in
grouping-list.
• The group-qualification is then applied to eliminate
some groups. Expressions in group-qualification must
have a single value per group!
– In effect, an attribute in group-qualification that is not an
argument of an aggregate op also appears in grouping-list.
(SQL does not exploit primary key semantics here!)
• One answer tuple is generated per qualifying group.
Find the age of the youngest sailor with age 
18, for each rating with at least 2 such sailors
SELECT S.rating, MIN (S.age)
FROM Sailors S
WHERE S.age >= 18
GROUP BY S.rating
HAVING COUNT (*) > 1
• Only S.rating and S.age are
mentioned in the SELECT, GROUP
BY or HAVING clauses; other
attributes `unnecessary’.
• 2nd column of result is unnamed.
(Use AS to name it.)
sid sname rating age
22 dustin
7
45.0
31 lubber
8
55.5
71 zorba
10 16.0
64 horatio
7
35.0
29 brutus
1
33.0
58 rusty
10 35.0
rating age
1
33.0
rating
7
45.0
7
35.0
7
35.0
8
55.5
Answer relation
10 35.0
For each red boat, find the number of
reservations for this boat
SELECT B.bid, COUNT (*) AS scount
FROM Sailors S, Boats B, Reserves R
WHERE S.sid=R.sid AND R.bid=B.bid AND B.color=‘red’
GROUP BY B.bid
• Grouping over a join of three relations.
• What do we get if we remove B.color=‘red’
from the WHERE clause and add a HAVING clause
with this condition?
• What if we drop Sailors and the condition
involving S.sid?
Find the age of the youngest sailor with age >
18, for each rating with at least 2 sailors (of any
age)
SELECT S.rating, MIN (S.age)
FROM Sailors S
WHERE S.age > 18
GROUP BY S.rating
HAVING 1 < (SELECT COUNT (*)
FROM Sailors S2
WHERE S.rating=S2.rating)
• Shows HAVING clause can also contain a subquery.
• Compare this with the query where we considered
only ratings with 2 sailors over 18!
• What if HAVING clause is replaced by:
– HAVING COUNT(*) >1
Find those ratings for which the average
age is the minimum over all ratings
• Aggregate operations cannot be nested! WRONG:
SELECT S.rating
FROM Sailors S
WHERE S.age = (SELECT MIN (AVG (S2.age)) FROM Sailors S2)
• Correct solution (in SQL/92):
SELECT Temp.rating, Temp.avgage
FROM (SELECT S.rating, AVG (S.age) AS avgage
FROM Sailors S
GROUP BY S.rating) AS Temp
WHERE Temp.avgage = (SELECT MIN (Temp.avgage)
FROM Temp)
Null Values
• Field values in a tuple are sometimes unknown (e.g., a
rating has not been assigned) or inapplicable (e.g., no
spouse’s name).
– SQL provides a special value null for such situations.
• The presence of null complicates many issues. E.g.:
– Special operators needed to check if value is/is not null.
– Is rating>8 true or false when rating is equal to null? What
about AND, OR and NOT connectives?
– We need a 3-valued logic (true, false and unknown).
– Meaning of constructs must be defined carefully. (e.g.,
WHERE clause eliminates rows that don’t evaluate to true.)
– New operators (in particular, outer joins) possible/needed.
Embedded SQL
• SQL commands can be called from within a host
language (e.g., C or COBOL) program.
– SQL statements can refer to host variables
(including special variables used to return status).
– Must include a statement to connect to the right
database.
– Requires compiler preprocessing
– SQL relations are (multi-) sets of records, with no a
priori bound on the number of records. No such
data structure in C.
– SQL supports a mechanism called a cursor to
handle this.
Cursors
• Can declare a cursor on a relation or query statement
(which generates a relation).
• Can open a cursor, and repeatedly fetch a tuple then
move the cursor, until all tuples have been retrieved.
– Can use ORDER BY to control the order in which tuples are
returned.
• Fields in ORDER BY clause must also appear in SELECT clause.
• Can also modify/delete tuple pointed to by a cursor.
Cursor that gets names of sailors who’ve
reserved a red boat, in alphabetical order
DECLARE sinfo CURSOR FOR
SELECT S.sname
FROM Sailors S, Boats B, Reserves R
WHERE S.sid=R.sid AND R.bid=B.bid AND B.color=‘red’
ORDER BY S.sname;
FETCH 5 IN sinfo;
• Note that it is illegal to replace S.sname by, say,
S.sid in the ORDER BY clause! (Why?)
• Can we add S.sid to the SELECT clause and replace
S.sname by S.sid in the ORDER BY clause?
Embedding SQL in C: An Example
char SQLSTATE[6];
EXEC SQL BEGIN DECLARE SECTION
char c_sname[20]; short c_minrating; float c_age;
EXEC SQL END DECLARE SECTION
c_minrating = random();
EXEC SQL DECLARE sinfo CURSOR FOR
SELECT S.sname, S.age FROM Sailors S
WHERE S.rating > :c_minrating
ORDER BY S.sname;
do {
EXEC SQL FETCH sinfo INTO :c_sname, :c_age;
printf(“%s is %d years old\n”, c_sname, c_age);
} while (SQLSTATE != ‘02000’);
EXEC SQL CLOSE sinfo;
Database APIs: alternative to
embedding
• Rather than modify compiler, add library with
database calls (API)
– special procedures/objects
– passes SQL strings from language, presents result
sets in a language-friendly way
– Microsoft’s ODBC becoming C/C++ standard on
Windows
– Sun’s JDBC a Java equivalent
– Supposedly DBMS-neutral
• a “driver” traps the calls and translates them into DBMSspecific code
• database can be across a network
SQL API in Java (JDBC)
Connection con = // connect
DriverManager.getConnection(url, ”login", ”pass");
Statement stmt = con.createStatement(); // set up stmt
String query = "SELECT COF_NAME, PRICE FROM COFFEES";
ResultSet rs = stmt.executeQuery(query);
try { // handle exceptions
// loop through result tuples
while (rs.next()) {
String s = rs.getString("COF_NAME");
Float n = rs.getFloat("PRICE");
System.out.println(s + "
" + n);
}
} catch(SQLException ex) {
System.out.println(ex.getMessage ()
+ ex.getSQLState () + ex.getErrorCode ());
}
Concurrency Control & Recovery.
Why Have Concurrent Processes?
• Better transaction throughput, response time
• Done via better utilization of resources:
– While one processes is doing a disk read, another
can be using the CPU or reading another disk.
• DANGER DANGER! Concurrency could lead to
incorrectness!
– Must carefully manage concurrent data access.
– There’s (much!) more here than the usual OS tricks!
Query Optimization & Processing
• Optimizer maps SQL to algebra tree with
specific algorithms
– access methods and join algorithms
• relational operators implemented as iterators
– open()
– next(possible with condition)
– close
• processing engine is a pull-based, singlethreaded data flow
– parallelizes naturally
Transactions
• Basic concurrency/recovery concept: a
transaction (Xact).
– A sequence of many actions which are
considered to be one atomic unit of work.
• DBMS “actions”:
– reads, writes
– Special actions: commit, abort
– for now, assume reads and writes are on tuples;
we’ll revisit this assumption later.
The ACID Properties
• A tomicity: All actions in the Xact happen, or none
happen.
• C onsistency: If each Xact is consistent, and the DB
starts consistent, it ends up consistent.
• I solation: Execution of one Xact is isolated from that
of other Xacts.
• Durability: If a Xact commits, its effects persist.
Passing the ACID Test
• Concurrency Control
– Guarantees Consistency and Isolation, given
Atomicity.
• Logging and Recovery
– Guarantees Atomicity and Durability.
• C. C.:
– What problems could arise?
– What is acceptable behavior?
– How do we guarantee acceptable behavior?
T1
Schedules
T2
R(A)
W(A)
R(B)
• Schedule: An interleaving of actions
W(B)
from a set of Xacts, where the actions
of any 1 Xact are in the original order. R(C)
– Represents some actual sequence of
W(C)
database actions.
– Example: R1(A), W1(A), R2(B), W2(B),
R1(C), W1(C)
– In a complete schedule, each Xact ends in
commit or abort.
• Initial State + Schedule  Final State
Acceptable Schedules
• One sensible “isolated, consistent” schedule:
– Run Xacts one at a time, in a series.
– This is called a serial schedule.
– NOTE: Different serial schedules can have different final
states; all are “OK” -- DBMS makes no guarantees
about the order in which concurrently submitted Xacts
are executed.
• Serializable schedules:
– Final state is what some serial schedule would have
produced.
– Aborted Xacts are not part of schedule; ignore them for
now (they are made to `disappear’ by using logging).
Serializability Violations
transfer
add 6%
$100 from interest to
A to B
A&B
T1
T2
R(A)
• Two actions conflict when 2 xacts
W(A)
access the same item:
– W-R conflict: T2 reads something
T1 wrote.
Database is
– R-W and W-W conflicts:
inconsistent!
Similar.
• WR conflict (dirty read):
– Result is not equal to any serial
R(B)
execution!
W(B)
Commit
R(A)
W(A)
R(B)
W(B)
Commit
More Conflicts
• RW Conflicts (Unrepeatable Read)
– T2 overwrites what T1 read.
– If T1 reads it again, it will see something new!
• Example when this would happen?
• The increment/decrement example.
– Again, not equivalent to a serial execution.
• WW Conflicts (Overwriting Uncommited Data)
– T2 overwrites what T1 wrote.
• Example: 2 Xacts to update items to be kept equal.
– Usually occurs in conjunction w/other anomalies.
• Unless you have “blind writes”.
Locking: A Technique for C. C.
• Concurrency control usually done via locking.
• Lock info maintained by a “lock manager”:
– Stores (XID, RID, Mode) triples.
• This is a simplistic view; suffices for now.
– Mode  {S,X}
-- S X
– Lock compatibility table:
--   
• If a Xact can’t get a lock, it is
suspended on a wait queue.
S  
X

Two-Phase Locking (2PL)
• 2PL:
– If T wants to read an object, first obtains an S
lock.
– If T wants to modify an object, first obtains X lock.
– If T releases any lock, it can acquire no new locks!
• Locks are automatically obtained by DBMS.
lock point
• Guarantees serializability!
– Why?
# of
locks
growing phase
shrinking
phase
Time
Strict 2PL
• Strict 2PL:
– If T wants to read an object, first obtains an S
lock.
– If T wants to modify an object, first obtains X lock.
– Hold all locks until end of transaction.
• Guarantees serializability, and avoids
cascading aborts, too!
– also avoids WW problems!
# of
locks
Time
Precedence Graph
• A Precedence (or Serializability) graph:
– Node for each commited Xact.
– Arc from Ti to Tj if an action of Ti precedes and
conflicts with an action of Tj.
• T1 transfers $100 from A to B, T2 adds 6%
– R1(A), W1(A), R2(A), W2(A), R2(B), W2(B), R1(B),
W1(B)
T1
T2
Conflict Serializability
• 2 schedules are conflict equivalent if:
– they have the same sets of actions, and
– each pair of conflicting actions is ordered in the
same way.
• A schedule is conflict serializable if it is conflict
equivalent to a serial schedule.
– Note: Some serializable schedules are not conflict
serializable!
Conflict Serializability & Graphs
• Theorem: A schedule is conflict serializable iff its
precedence graph is acyclic.
• Theorem: 2PL ensures that the precedence
graph will be acyclic!
• Strict 2PL improves on this by avoiding
cascading aborts, problems with undoing WW
conflicts.
Lock Manager Implementation
• Question 1: What are we locking?
– Tuples, pages, or tables?
– Finer granularity increases concurrency, but also
increases locking overhead.
• Question 2: How do you “lock” something??
• Lock Table: A hash table of Lock Entries.
– Lock Entry:
•
•
•
•
OID
Mode
List: Xacts holding lock
List: Wait Queue
Handling a Lock Request
Lock Request (XID, OID, Mode)
Mode==S
Mode==X
Currently Locked?
Empty Wait Queue?
Yes
No
Yes
Currently X-locked?
Yes
No
Put on Queue
Grant Lock
No
More Lock Manager Logic
• On lock release (OID, XID):
– Update list of Xacts holding lock.
– Examine head of wait queue.
– If Xact there can run, add it to list of Xacts holding
lock (change mode as needed).
– Repeat until head of wait queue cannot be run.
• Note: Lock request handled atomically!
– via latches (i.e. semaphores/mutex; OS stuff).
Lock Upgrades
• Think about this scenario:
– T1 locks A in S mode, T2 requests X lock on A, T3
requests S lock on A. What should we do?
• In contrast:
– T1 locks A in S mode, T2 requests X lock on A, T1
requests X lock on A. What should we do?
• Allow such upgrades to supersede lock requests.
– Consider this scenario:
• S1(A), X2(A), X1(A):
DEADLOCK!
• BTW: Deadlock can occur even w/o upgrades:
– X1(A), X2(B), S1(B), S2(A)
Deadlock Detection
• Lock Mgr maintains a “Waits-for” graph:
– Node for each Xact.
– Arc from Ti to Tj if Tj holds a lock and Ti is waiting
for it.
• Periodically check graph for cycles.
• “Shoot” some Xact to break the cycle.
• Simpler hack: time-outs.
– T1 made no progress for a while? Shoot it.
To lock such rascal counters from his friends,
Be ready, gods, with all your thunderbolts:
Dash him to pieces!
-- Shakespeare, Julius Caesar
Prevention vs. Detection
• Prevention might abort too many Xacts.
• Detection might allow deadlocks to tie up
resources for a while.
– Can detect more often, but it’s time-consuming.
• The usual answer:
– Detection is the winner.
– Deadlocks are pretty rare.
– If you get a lot of deadlocks, reconsider your
schema/workload!
Multiple-Granularity Locks
• Hard to decide what granularity to lock (tuples
vs. pages vs. tables).
• Shouldn’t have to decide!
• Data “containers” are nested:
Database
contains
Tables
Pages
Tuples
Solution: New Lock Modes, Protocol
• Allow Xacts to lock at each level, but with a
special protocol using new “intention” locks:
Before locking an item, Xact
must set “intention locks”
on all its ancestors.
 For unlock, go from specific
to general (i.e., bottom-up).
 SIX mode: Like S & IX at
the same time.

--
IS IX S
X





IS 



IX 





--
S
X

Examples
• T1 scans R, and updates a few tuples:
– T1 gets an SIX lock on R, and occasionally
upgrades to X on a tuple.
• T2 uses an index to read only part of R:
– T2 gets an IS lock on R, and repeatedly
gets an S lock on tuples of R.
• T3 reads all of R:
-– T3 gets an S lock on R.
IS
– OR, T3 could behave like T2; can
IX
use lock escalation to decide which.
S
X
--
IS IX S
X
















Logging and Recovery: Motivation
• Atomicity:
– Transactions may abort (“Rollback”).
• Durability:
– What if DBMS stops running? (Causes?)

Desired Behavior after
system restarts:
– T1, T2 & T3 should be
durable.
– T4 & T5 should be
aborted (effects not seen).
T1
T2
T3
T4
T5
crash!
Assumptions
• Concurrency control is in effect.
– Strict 2PL, in particular.
• Updates are happening “in place”.
– i.e. data is overwritten on (deleted from) the disk.
• A simple scheme to guarantee Atomicity &
Durability?
Handling the Buffer Pool
• Force write to disk at
commit?
No Steal
– Poor response time.
Force Trivial
– But provides durability.
• Steal buffer-pool frames
from uncommited Xacts?
– If not, poor throughput. No Force
– If so, how can we ensure
atomicity?
Steal
Desired
More on Steal and Force
• STEAL (why enforcing Atomicity is hard)
– To steal frame F: Current page in F (say P) is
written to disk; some Xact holds lock on P.
• What if the Xact with the lock on P aborts?
• Must remember the old value of P at steal time (to
support UNDOing the write to page P).
• NO FORCE (why enforcing Durability is hard)
– What if system crashes before a modified page is
written to disk?
– Write as little as possible, in a convenient place, at
commit time,to support REDOing modifications.
Basic Idea: Logging
• Record REDO and UNDO information, for every
update, in a log.
– Sequential writes to log (put it on a separate disk).
– Minimal info (diff) written to log, so multiple updates
fit in a single log page.
• Log: An ordered list of REDO/UNDO actions
– Log record contains:
<XID, pageID, offset, length, old data, new data>
– and additional control info
Write-Ahead Logging (WAL)
• The Write-Ahead Logging Protocol:
 Must force the log record for an update before
the corresponding data page gets to disk.
 Must write all log records for a Xact before
commit.
• #1 guarantees Atomicity.
• #2 guarantees Durability.