CS157A: Introduction to Database Management Systems
Chapter 1: Introduction Chapter 2: The Relational Model of Data
Suneuy Kim
CS157A: Chapter 2 1
I. Database Management System (DBMS)
• Database is a collection of data that is managed by a DBMS.
• DBMS is specially designed software applications that interact with the user, other applications, and the database itself to capture and analyze data.
• Features of DBMS
– Data definition – defining schema for the database, removing
schema from the database, and altering an existing schema
– Data modification – inserting, deleting, and updating data
– Data retrieval – obtaining information from the database for user queries
– Administration – Registering and monitoring users, enforcing data security, monitoring performance, maintaining data integrity, dealing with concurrency control, and recovering
information in case of failures
CS157A Chapter 1 2
Terminology
• A database schema of a database system is its structure described in a formal language supported by the DBMS and refers to the organization of data as a blueprint of how a database is constructed – Wikipedia
• SQL (Structured Query Language) – RDBMS
– DataDefinitionLanguage(DDL)fordeclaringdatabaseschemas
e.g.) CREATE, DROP, ALTER
– DataManipulationLanguage(DML)forqueryingandformodifying databases
e.g.) SELECT, INSERT, DELETE, UPDATE
– DataControlLanguage(DCL)forcontrollingaccesstodatastoredina database
e.g.) GRANT, REVOKE
CS157A Chapter 1 3
CS157A: Chapter 2
4
DBMS components
Database Designer
Database People
Database Application Programmer
defines schema
queries/modifies data
Database Administrator
– executes DDL – loads data,
– monitors and maintains databases
builds system
DBMS Implementer
CS157A Chapter 1
5
II. Data Model
• Data model consists of – Structure of the data
– Operations on the data – Constraints on the data
• Representative data models – Relational data model
– Semi-structured data model – NoSQL data model
CS157A: Chapter 2 6
Relational Data Model
• Structure: tables (relations)
• Operations – relational algebra, table-oriented
e.g.) select, project, join, etc. • Constraints
e.g.) referential integrity constraints, key constraints
CS157A: Chapter 2 7
Example: Table Movies
title
year
length
genre
Gone with the Wind
1939
231
drama
Star Wars
1977
124
sciFi
Wayne’s World
1992
95
comedy
CS157A: Chapter 2 8
Semi-structured Data Model
• Structure: trees or graphs e.g.) XML data
• Operations involve following paths in the implied tree
•
e.g.) /Movies/Movie/Version
Constraints involve the data type of values associated with a tag
e.g.)
CS157A: Chapter 2 9
Example: XML data
CS157A: Chapter 2 10
Relational vs. Semi-structured data models
• Semi-structured models: flexible
• Relational models:
– Used by major commercial database systems – Efficient access and modification of data
– Easy of use
– SQL allows us to program at high level
CS157A: Chapter 2 11
DB-engines Ranking http://db-engines.com/en/ranking
CS157A: Chapter 2 12
III. Relation Model
• Relation: two dimensional table to represent data
• Attributes: columns of relation
• Tuples: rows of a relation
• Domains: data type for each attribute
• RelationSchema:nameofarelationandtheset of attributes (attribute names and associated domains) for a relation
• Database schema – a set of schemas for the relations of a database.
CS157A: Chapter 2 13
Relational Model
• Instances: actual contents at given point in time
• Key: attribute whose value is unique in each tuple (Or set of attributes whose combined values are unique)
e.g.) Movies(title, year, length, genre) • Note:
– The attributes in a relation schema are a set, not a list
– Relations are sets of tuples, not lists of tuples
CS157A: Chapter 2 14
Example: Schema Database Schema about Library
BOOK (
title: string, author:string, copies:integer
) USER (
uID:integer, uNAME:string, age:integer, loaned:integer,
)
LOAN (
uID:integer, title:string, loanDate:date, overdue: boolean
)
CS157A: Chapter 2 15
IV. Relational Algebra
• An algebra whose operands are relations or variables that represent relations.
CS157A: Chapter 2 16
Core relational operations • Union, intersection, and difference.
– both operands have the same number of attributes and the domains of the corresponding attributes are the same.
• Selection: selecting certain rows.
• Projection: projecting certain columns.
• Products and joins: combining two relations. • Renaming of relations and attributes
CS157A: Chapter 2 17
Running Example
Book(title, author, copies)
User (uID, uName, age, loaned) Loan (uID, title, loanDate, overdue)
Notes:
• copies means the number of copies left
• loaned means the number of books the user loaned.
CS157A: Chapter 2 18
Set operations
• R∪S
Relation with tuples from R and S with duplicates
removed.
• R∩S
Relation with tuples that appear in both R and S.
• R−S
Relation with tuples from R but not from S
Difference operation is NOT commutative. That is, R- S is not equal S-R.
CS157A: Chapter 2 19
Example: Set operations Book1
title
author
copies
Faraway Child
Amy Maida Wadsworth
3
Evening in the Ashes
Dorothy Love
20
The Sage and the Lace
James Dove
4
Book2
title
author
copies
Faraway Child
Amy Maida Wadsworth
3
Silent Wife
A.S.A. Harrison
10
Cloud of Unknown
Carl McColman
17
CS157A: Chapter 2 20
Books1 U Books2
title
Evening in the Ashes Faraway Child
The Sage and the Lace Cloud of Unknown Silent Wife
author
Dorothy Love
Amy Maida Wadsworth James Dove
Carl McColman
A.S.A. Harrison
copies
20 3 4 17 10
CS157A: Chapter 2
21
title
Faraway Child
Book1 ∩ Book2 author copies
Amy Maida Wadsworth 3
Book1 − Book2
title
Evening in the Ashes The Sage and the Lace
author
Dorothy Love James Dove
copies
20 4
CS157A: Chapter 2
22
Select • R1:=σC(R2)
– C is a condition that involves attributes of R2. – R1 is all those tuples of R2 that satisfy C.
CS157A: Chapter 2 23
Example: Select
• Users who loaned more than 20 books.
σloaned >20 (User)
• Users who loaned more than 20 books with age > 10.
σ loaned >20 ^ age > 10 (User)
• Loans of book ‘Bambi’ being overdue
σtitle=‘Bambi’ ^ overdue=true (Loan)
CS157A: Chapter 2 24
Projection
R1 := πL (R2)
• L is a list of attributes from the schema
of R2.
• R1 is constructed by looking at each tuple
of R2, extracting the attributes on list L, in the order specified, and creating from those components a tuple for R1.
• Eliminate duplicate tuples, if any
CS157A: Chapter 2 25
Example: Projection • Ids and #of loaned books of all users
πuID,loaned(User)
• Ids and names of users who loaned more than
20 books πuID,uName(σloaned >20 (User) )
CS157A: Chapter 2 26
Different ways of handling duplicates
Titles and overdue information of all loans πtitle,overdue(Loan)
Relational Algebra: Sets
SQL: Bags
title
Bambi
Bambi
Lion King
Eye of Sierras
title
Bambi
Lion King
Eye of Sierras
overdue
TRUE FALSE FALSE
overdue
TRUE TRUE FALSE FALSE
CS157A: Chapter 2
27
Quiz
Are the following relational algebra expressions useful ?
• σloaned>20(σage>10 (User) ) • πtitle(πtitle,author(Book))
CS157A: Chapter 2 28
•
–
–
Extended Projection Using the same πL operator, where the
projection list L can have:
an expression x->y where x and y are attributes. x is
renamed to y.
an expression E->z, where E involves operations and z is the name of the results of the expression
e.g.) a+b-> x represents sum of the attributes a and b,
renamed x
– duplicate occurrences of the same attribute
CS157A: Chapter 2 29
Example: Extended Projection R=
A
B
10
20
30
40
C
A1
A2
30
10
10
70
30
30
πA+BàC, A, A(R) =
CS157A: Chapter 2 30
Cartesian Product (= Cross Join)
R3 := R1 Χ R2
– Pair each tuple t1 of R1 with each tuple t2 of R2.
– Concatenation t1t2 is a tuple of R3.
– Schema of R3 is the attributes of R1 and then R2,
in order.
– But beware attribute A of the same name in R1
and R2: use R1.A and R2.A.
CS157A: Chapter 2 31
Example: Cartesian Product
R1 R2
Xà
R3
A
R1.B
R2.B
C
D
1
2
2
5
6
1
2
4
7
8
1
2
9
10
11
3
4
2
5
6
3
4
4
7
8
3
4
9
10
11
A
B
1
2
3
4
B
C
D
2
5
6
4
7
8
9
10
11
CS157A: Chapter 2
32
Example: Cartesian Product Ids and #of loaned books of users who loaned
“Bambi” being overdue.
πUser.uID,loaned(σUser.uID=Loan.uID ^ title=”Bambi” ^overdue = true (User X Loan))
CS157A: Chapter 2 33
Theta-Join
• R3 := R1 ⋈C R2
– Take the product R1 Χ R2.
– Then apply σC to the result, where C can be any boolean-valued condition.
• User names that happen to be the same as one of the book titles.
πuName(User⋈uName = title Book)
CS157A: Chapter 2 34
Example: Theta Join
⋈ D%A=0
A
B.1
B.2
C
D
1
2
2
5
6
1
2
4
7
8
1
2
9
10
11
3
4
2
5
6
B
C
D
2
5
6
4
7
8
9
10
11
A
B
1
2
3
4
à
CS157A: Chapter 2 35
Natural Joins • R3:=R1⋈R2.
– Equating attributes of the same name, and
– Projecting out one copy of each pair of equated
attributes.
⋈
à
B
C
D
2
5
6
4
7
8
9
10
11
A
B
1
2
3
4
A
B
C
D
1
2
5
6
3
4
7
8
CS157A: Chapter 2 36
Example: Natural Join
Ids and #of loaned books of users who loaned
“Bambi” being overdue. πuID,loaned(σtitle=”Bambi”^ overdue = true (User ⋈ Loan))
CS157A: Chapter 2 37
Joins
• A theta join allows for arbitrary comparison relationships (such as ≥).
• An equijoin is a theta join using the equality operator.
• A natural join is an equijoin on attributes that have the same name in each relations . The resulting relation will contain only one column for each pair of the same named columns.
CS157A: Chapter 2 38
Renaming
• The ρ operator gives a new schema to a relation.
• ρS(A1,…,An)(R) makes S be a relation with attributes A1,…,An and the same tuples as R.
CS157A: Chapter 2 39
Example: Renaming
R(A,B)
S(B,C,D)
(1) R x ρS(X,C,D)(S)
(2) ρRS(A,B,X,C,D)(RxS)
(1) and (2) are the same except for that resulting relation of (1) doesn’t have any name while that of (2) has a name RS.
CS157A: Chapter 2 40
Division (R ÷ S)
The DIVISION operation is useful for a special
kind of query involving all. For example,
• Retrieve the names of employees who work
on all the projects that ‘Jonh Smith’ works on.
• Find all pizzerias that serve every pizza eaten by people over 30.
CS157A: Chapter 2 41
Division !(#) = &(‘) ÷ )(*)
!(#) = &(‘) ÷ )(*), where
• the Z and X are schemas of R and S, respectively,
• the attributes of S are a subset of the attributes of R; that is *+ ‘, and
• Y=Z-X(YisthesetofattributesofRthatarenot attributesofS;thatis,Y= Z–X(andhence’= *⋃#)
CS157A: Chapter 2 42
• For a tuple t to appear in the result T of the Division, the values in t must appear in R in combination with every tuple in S.
• Example: b1 and b4 appear in R in combination with all three tuples in S.
RST ÷=
!(#) = &(‘) ÷ )(*)
A
B
a1
b1
a2
b1
a3
b1
a4
b1
a1
b2
a3
b2
a2
b3
a3
b3
a4
b3
a1
b4
a2
b4
a3
b4
A
a1
a2
a3
B
b1
b4
CS157A: Chapter 2
43
Division using
a sequence of p, ×, and – operators
• T1 := pY (R )
• T2:=pY((S×T1)–R) • T:=T1–T2
T1 S × T1 (S ×T1 ) – R T2
RST
=
A
B
a1
b1
a2
b1
a1
b2
A
a1
a2
B
b1
÷
T
B
b1
b2
A
B
a2
b2
B
b2
B
b1
A
B
a1
b1
a1
b2
a2
b1
a2
b2
CS157A: Chapter 2
44
Independent operators
•∪ •−
• s (select)
• p (project) • x (product)
• ρ (renaming)
Operators that can be expressed in terms of other R.A operators
• R∩S = R-(R-S)
• R⋈C S=σC (RXS)
• R⋈S=πL(σC (RXS))
– C is R.A1=S.A1^R.A2=S.A2 … where A1, A2, … are shared attributes by R and S.
– L is list of attributes of R followed by attributes of S that are not also in R.
Relationships among Operations
CS157A: Chapter 2 45
• • •
Expressing Complex Queries
Relational algebra expressions Expression trees
Linear Notations
46
R.A.
Movies(title, year, length, genre, studioName, producerC#)
“What is the titles and years of movies made by Fox that are at least 100 minutes long ?”
R.A. Expression:
Πtitle,year(σ length≥ 100(Movies) Ç σ studioName=’Fox’ (Movies))
Πtitle,year(σ length≥ 100 AND studioName=‘Fox’ (Movies))
CS157A: Chapter 2 47
Expression Trees Πtitle,year
Ç
σ length≥ 100 Movies
σ studioName=‘Fox’ Movies
48
Linear Notations
• R(t,y,l,g,s,p) := σ length≥ 100(Movies)
• S(t,y,l,g,s,p) := σ studioName=’Fox’ (Movies) • T(t,y,l,g,s,p) := RÇ S
• Answer(title, year) := Πt,y(T)
or
• Answer(title, year) := Πt,y(RÇ S)
CS157A: Chapter 2 49
Constraints on Relations
A referential integrity constraint asserts that a value appearing in one context will also appear in another related context.
Example
Movies (title,year, length, genre,
stuidoName, producerC#)
MovieExec(name, address,cert#,netWorth)
ΠproducerC#(Movies) ∈Πcert#(MovieExec)
CS157A: Chapter 2 50
Constraints on Relations
Key constraints
A key uniquely identifies each tuple in a relation.
Any two tuples in a relation must not have the same key.
CS157A: Chapter 2 51
Relational Algebra Exercise 2.4.1
Product (maker, model, type)
PC(model, speed, ram, hd, price) Laptop(model, speed, ram, hd, screen, price) Printer(model, color, type, price)
CS157A: Chapter 2 52
(a) What PC models have a speed of at least 3.00 ?
(b) Which manufacturers make laptops with a hard disk of at least 100GB ?
(c) Find the model number and price of all products (of any type) made by manufacturer B.
(d) Find the model numbers of all color laser printers.
(e) Find those manufacturers that sell Laptops, but not PCs.
CS157A: Chapter 2 53
(f) Find those hard disk sizes that occur in two or more PC’s
(g) Find those pairs of PC models that have both the same speed and RAM. A pair should be listed only once; e.g., list(i,j) but not (j,i)
(h) Find the manufacturers of at least two different computers (PC’s or laptops) with speeds of at least 2.80.
CS157A: Chapter 2 54
(i) Find the manufacturer(s) of the computer (PC or laptop) with the highest available speed.
(j) Find the manufacturers of PC’s with at least three different speeds.
(k) Find the manufacturers who sell exactly three different models of PC.
CS157A: Chapter 2 55
(a) What PC models have a speed of at least 3.00 ?
π model (σ speed ≥ 3.0 PC)
CS157A: Chapter 2 56
(b) Which manufacturers make laptops with a hard disk of at least 100GB ?
πmaker (σ hd ≥ 100 (Product ⨝ Laptop))
CS157A: Chapter 2 57
(c)Find the model number and price of all products (of any type) made by manufacturer B.
π model,price (
σ maker = ‘B’ (Product ⨝
(π model,price (PC) ∪ π model,price (Laptop) ∪ πmodel,price (Printer)) )
)
CS157A: Chapter 2 58
(d) Find the model numbers of all color laser printers
π model (σ color = true and type = ‘laser’ Printer)
CS157A: Chapter 2 59
(e) Find those manufacturers that sell Laptops, but not PCs.
π maker (σ type=’laptop’ Product) – π maker (σ type=’pc’ Product)
CS157A: Chapter 2 60
(f) Find those hard disk sizes that occur in two or more PC’s
π PC.hd
(PC ⨝ PC.model≠ PC2.model and PC.hd = PC2.hd ρ PC2 PC)
CS157A: Chapter 2 61
(g) Find those pairs of PC models that have both the same speed and RAM. A pair should be listed only once; e.g., list(i,j) but not (j,i)
π PC.model, PC2.model
(PC ⨝ PC.model < PC2.model and PC.speed =PC2.speed and PC.ram=PC2.ram ρ PC2 PC)
CS157A: Chapter 2 62
(h) Find the manufacturers of at least two different computers (PCs or laptops) with speeds of at least 2.80.
π maker
σ model≠model2 (
π maker,model (Product ⨝ ((π model σ speed ≥2.80 PC)∪(π model σ speed ≥2.80 Laptop)))
⨝
ρ model2<-model
π maker,model (Product ⨝ ((π model σ speed ≥2.80 PC)∪(π model σ speed ≥2.80 Laptop)))
)
CS157A: Chapter 2 63
(i) Find the manufacturer(s) of the computer (PC or laptop) with the highest available speed.
π maker
(
Product ⨝ (
π model
σ type = 'pc' or type = 'laptop' (Product) -
π model
((π model,speed PC ∪ π model, speed Laptop)
⨝ speed < speed2
ρ model1<- model, speed2<-speed
(π model,speed PC ∪ π model, speed Laptop)) )
)
CS157A: Chapter 2 64
(j) Find the manufacturers of PCs with at least three different speeds.
πmaker (σs1≠s2ands1≠s3ands2≠s3 (
( ρ s1←speed π maker,speed ( Product ⨝ PC )
⨝
ρ s2←speed π maker,speed ( Product ⨝ PC ) ) ⨝
ρ s3←speed π maker, speed ( Product ⨝ PC )) )
Product.maker 'A'
'D'
'E'
CS157A: Chapter 2
65
(k) Find the manufacturers who sell
exactly three different models of PC.
π maker
σ m1≠m2 and m2≠m3 and m1≠m3
((ρm1<-model π maker,model σ type='pc' Product) ⨝
(ρm2<-model π maker,model σ type='pc' Product) ⨝
(ρm3<-model π maker,model σ type='pc' Product)) -
π maker
(σm1≠m2 and m1≠m3 and m1≠m4 and m2≠m3 and m2≠m4 and m3≠m4 ((ρm1<-model π maker,model σ type='pc' Product) ⨝ (ρm2<-model π maker,model σ type='pc' Product) ⨝ (ρm3<-model π maker,model σ type='pc' Product)⨝ (ρm4<-model π maker,model σ type='pc' Product)
))
CS157A: Chapter 2 66