CS348

Professor: Semih Salihoğlu | Term: Winter 2025

Lecture 1

Simplified Software Stack of Data-Intensive App

flowchart TB
APP <--> DBMS
DBMS <--> OS
OS <--> id[(Disks)]

Question

Why do app developers need a DBMS?

Productivity and safety

Productivity related features:

1. Logical (High-level) Data Model

Enterprise Amazon

App: Mobile checkout App: Product & Shipment Tracking & Logging App: Manager dashboards for analytics

Amazon needs to record

• Customers: names, addresses, ages
• Product: names, descriptions, prices
• Orders: who, what, when

Naive Approach: Use directly the file system

This has many problems (Physical Record Design):

Question

How to serialize records in the files?

Example:

Alice, 18
Bob, 21

Option 1: Special char

Alice, 18 \n
Bob, 21 \n

Could do Huffman encoding

Option 2: Variable length-encoding

5 Alice 18 3 Bob 21 ...

Option 3: Column-Oriented

Alice	Bob
18	21

Allows for better compression (easier to compress data of the same type)

This stuff has nothing to do with the app logic. Many design options, difficult for developers.

Logical (High-level) Data Model: Instead of interacting with data as bits and bytes $⟹$ allows you to interact with data using a higher-level logical data structure.

Second Productivity Benefit: 2. High-level Query Language

Question

App: Who are the top paying customers?

order.txt

oID	cID	pID
01	c1	BookA
02	c2	WatchA
03	c1	BookB

cust.txt

cID	name	age
c1	Alice	18
c2	Bob	21

product.txt

pID	price
BookA	20
WatchA	50

Need an algorithm to find the top paying customer. One option is a sequential nested loop-join algorithm (order and product) with a hash map aggregate.

Another option: Hash map of product and price first. Then hash map of total sum (product and customer). Slightly better than previous since not opening file multiple times.

This is still too low-level and somewhat detached from app logic $⟹$ Not the right abstraction to access the data.

Now assume the previous files are now tables.

SELECT cID, sum(price) as totalSum
FROM orders, products 
WHERE orders.pID = products.pID
GROUP BY cID
ORDER BY totalSum DESC
LIMIT 10

Much more high-level.

Safety Features

1. Integrity constraints protect against data corruption due to application bugs (i.e. primary keys)
2. Concurrent access to data
3. Protection against hardware failure

Information Systems

• Database
  • Dumb
  • Very fast, scalable, easy to use
• Symbolic AI
  • Intelligent

Tldr

DBMS abstract a lot of hard work that doesn’t have to do with specific apps themselves.

Lecture 2

Data Model: A formalism (notation) to describe 3 aspects of a database.

1. Structure
2. Constraints
3. Operations

First Data Model in History: Network Model $\to$ Charles Bachmann

1. Structure

Records (nodes) with field of data types. Modelling data as relations or tables, each storing logically related information together.

UserRecord

uid	name	age	pop
142	Bard	10	0.9
123	Milhouse	10	0.2

Group

gid	name
abc	A Book Club
dps	Dead Putting Society

Member

uid	gid
142	dps
123	abc

Constraint: Keys: each record needed to have a field that identified the record

Operations:

getRecordByKey(147, UserRecord)
record.getNext(members) --> record

Criticisms:

• Tuple at a time
• Physical dependence

Databases should be modelled to follow set theory.

Relational Model

Structure: A relational database consists of a set of tables/relations, where columns have names called attributes. Attributes have values from a particular domain.

Attributes within relations are unique. Relations are sets, columns are unique.

No duplicate tuples (two rows in a relation in the relational model cannot be the same). Same is to be defined as having equivalent attributes for all attributes.

Schema/Metadata

• Specifies the logical structure of the data
• Attributes & attributes types/domains

Instance

• Represents the actual data content
• Changes rapidly, but conforms to the schema.

Constraints (external to the database; they are application specific assumptions): Some constraints are very common, and have given names, others can be defined.

Tuple-level (domain restrictions; i.e. age cannot be negative) (not the focus)

Key constraints: By definition no two tuples in a relation can be the same on every attribute.

Definition

Super Key: A set of attributes on which no tuples can be the same.

Definition

Candidate Key: A minimal super key.

Definition

Primary Key: One of the candidate keys that the database designer identifies.

Example

Expedia Flights

Name	tripID	tripStartDateTime
Alice	123	01/01 12:00pm
Bob	123	01/01 12:00pm
Carl	456	02/02 4pm
Alice	789	7/15 5pm

We are assuming that names are unique. (Alice is the same Alice in both instances)

Name is not a key (since there can be duplicate names). tripID is not a key (since multiple trips booked at same time can have the same tripID). tripStartDateTime is obviously not a key.

Name and tripID are super keys. This is because a person cannot be on multiple flights at the same time (thus the name and tripID together will be unique).

Name and tripStartDateTime are super keys.

They are also both candidate keys (since they are minimal).

Name, tripID, tripStartDateTime are super keys but not candidate keys (since not minimal).

Primary Key has to be a candidate key.

Definition

Foreign Key Constraint: Specific instance of “Referential Constraints”.

An attribute $A$ of $R$ references the primary key $B$ of $S$.

It is the primary key of one relation appearing as the attribute of another relation.

$R(A_1,A_2,\dots ,A_k)⟶S(B_1,B_2,\dots ,B_k)$

Users

uid	name	age
142	Bart	10
123	Millhouse	10
857	Joe	8

Members

uid	gid
123	gov
857	abc

Group

gid	name
gov	Student Council
abc	Book Club

Anything that appears in Members, must appear in Group. Anything that appears in Members, must appear in User.

uid and gid are both foreign keys.

Operations: Relational Algebra

Operator of tuples

• Standard set operations
  • ($\cup ,\cap ,\setminus$)
• Remove parts operator
  • Selection, projections
• Relation widening operators
  • Cartesian Product
• Renaming

Core Operator 1: Selection/Filter ${\sigma }_p(R)⟹\{t\in R\text{ s.t }p(t)=True\}$

$p$, predicate, can contain constants, $\le =,\ge ,<,>,\wedge ,\vee$.

${\sigma }_{\text{ age }<0}(\text{Users})$ results in the following

uid	name	age
857	Joe	8

${\sigma }_{\text{age}=10\wedge \text{name}=\text{"Bart"}}$ results in

uid	name	age
142	Bart	10

Core operator 2: Projection ${\pi }_L(R)⟹$ output keeps only the columns of $R$ that appear in $L$.

$L$ is the projection list: a set of attributes that will be in the output.

${\pi }_{\text{uid, name}}(\text{Users})$ results in

uid	Name
142	Bart
123	Millhouse
857	Joe

${\pi }_{\text{age}}(\text{Users})$ results in

age
10
8

Duplicate rows are removed (by definition).

Core Operator 3: Cartesian Product: $R\times S$

$\forall r\in R,\forall s\in S⟹\underset{\text{concatenation}}{\underbrace{rs}}$

The schema of $R\times S$: contains every attribute in $R$ and every attribute in $S$.

If an attribute appears both in $R$ and $S$, we rename it as $R.A$ and $S.A$ in the output.

Example

Users $\times$ Members

Users.uid	name	age	Members.uid	gid
142	Bart	10	123	gov
142	Bart	10	857	abc
123	Millhouse	10	123	gov
123	Millhouse	10	857	abc
857	Joe	8	123	gov
857	Joe	8	857	gov

There should be $6$ rows since we are taking the Cartesian product (each row with each row).

Derived Operator 1: Theta Join: $R{\bowtie }_{p}S$

${\sigma }_p(R\times S)$

Take the cartesian product but only show the ones that satisfy $p$.

Derived Operator 2: Natural Join: $R\bowtie S$

Join $R$ and $S$ on equality of their common attributes and then keep only one copy of each common attribute.

Users $\bowtie$ Members

User.uid	name	age	Members.uid	gid
123	Millhouse	10	123	gov
857	Joe	8	857	abc

We then remove one of the duplicate columns and can then disambiguate.

name	age	uid	gid
Millhouse	10	123	gov
Joe	8	857	abc

This operator is shorthand for ${\pi }_L(R{\bowtie }_{p}S)$ where $p$ equates each pair of columns common to $R$ and $S$ and $K$ is the union of column names from $R$ and $S$.

Lecture 3

Core Operator 4: Union $R\cup S$

Input: Two tables $R$ and $S$.

Notation: $R\cup S$. $R$ and $S$ must have identical schema.

Output:

• Same scheme as $R$ and $S$.
• Contains all rows in $R$ and all rows in $S$ (duplicate rows removed)

Core Operator 5: Difference $R-S$

Notation: $R-S$. $R$ and $S$ must have identical schema.

Output:

• Has the same schema as $R$ and $S$
• Contains all rows in $R$ that are not in $S$

Derived Operator 3: Intersection $R\cap S$

Notation: $R\cap S$. $R$ and $S$ must have identical schema.

Output:

• Has the same schema as $R$ and $S$
• Contains all rows that are in both $R$ and $S$

Shorthand for $R-(R-S)$. This finds tuples in $R$ not in $S$, and removes those tuples from $R$.

This is also equivalent to $S-(S-R)$ and $R\bowtie S$.

Core Operator 6: Renaming

Input: A table (or an expression) $R$

Notation: ${\rho }_{S}R,{\rho }_{(A_1\to A_1^{\prime },\dots )}R$, or ${\rho }_{S(A_1\to A_1^{\prime },\dots )}R$

Purpose: “Rename” a table and/or its columns

Output: A table with the same row as $R$, but called differently.

Member

uid	gid
123	gov
857	abc

${\rho }_{M1(uid\to ui{d}_1,gid\to gi{d}_1)}Member$

M1

uid${}_1$	gid${}_1$
123	gov
857	abc

This does not modify the database (it is a renamed table as a copy of the original).

Example

Renaming: IDs of users who belong to at least two groups Member ${\bowtie }_{?}$ Member

$$\begin{array}{r}{\pi }_{ui{d}_1}\left({\rho }_{(uid\to ui{d}_1,gid\to gi{d}_1)}Member{\bowtie }_{ui{d}_1=ui{d}_2\wedge gi{d}_1\ne gi{d}_2}{\rho }_{(uid\to ui{d}_2,gid\to gi{d}_2)}Member\right)\end{array}$$

Example

Find the names of Users whose ages are greater than the User with ID 857

Users

uid	name	age	pop
102	Bert	10	0.8
123	Millhouse	10	0.8
857	Lisa	8	0.3

Members

uid	gid
102	gov
123	abc
857	gov

Groups

gid	name
gov	Student Gov
abc	Book Club

${\rho }_{{\text{Users}}_1}$(Users) $\times {\rho }_L{\sigma }_{\text{UID}=857}$(Users).

${\pi }_{{\text{Users}}_1.\text{name}}\left({\sigma }_{{\text{Users}}_1.\text{age}>L.age}\left({\rho }_{{\text{Users}}_1}(\text{Users}\times {\rho }_L{\sigma }_{\text{UID}=857}(\text{Users})\right)\right)$

Key Constraints

Example

$R(A,B,C)$, suppose $A$ is a key.

${\sigma }_{R1.A=R2.A\wedge (R1.B\ne R2.B\vee R1.C\ne R2.C)}$

In relational algebra, ${\rho }_{R_1}(R)\times {\rho }_{R_2}(R)=\varnothing$

Example

$R(A_1,A_2,\dots ),S(B_1,B_2,\dots )$

${\pi }_{A_1}(R)-{\pi }_{B_1}(S)=\varnothing$

Additional Constraints

Tuple-level constraints: Age of Users cannot be negative

${\sigma }_{\text{age}<0}$(Users) $=\varnothing$

Relation-level constraints: Key constraints

• uid should be unique in the User relation

DB-level constraints: Foreign key constraints

• A user cannot be a member of 3 groups or more

Name	Notation	Core/Derived	Monotone
Selection	$\sigma$	Core	Yes
Projection	$\pi$	Core	Yes
Cartesian product	$\times$	Core	Yes
Join, Natural Join	${\bowtie }_p,\bowtie$	Core	Yes
Union	$\cup$	Core	Yes
Intersection	$\cap$	Derived	Yes
Difference	$-$	Core	Monotone w.r.t. $R$, Non-monotone w.r.t. $S$

Example

IDs of groups Lisa belongs to?

${\pi }_{\text{gid}}{\sigma }_{\text{name=Lisa}}(\text{Members}\bowtie \text{Users})$

${\pi }_{\text{gid}}(\text{Members}\bowtie {\sigma }_{\text{name = Lisa}}(\text{Users}))$

Example

IDs of groups that Lisa does not belong to?

${\pi }_{\text{gid}}(\text{Group})-{\pi }_{\text{gid}}(Members\bowtie {\sigma }_{\text{name="Lisa"}}(\text{User}))$

Example

Find User with pop $>$ all other users.

${\pi }_{\text{uid}(\text{Users})}-{\pi }_{{\text{User}}_1.\text{uid}}{\sigma }_{{\text{User}}_1.\text{pop}<{\text{User}}_2.\text{pop}}{\rho }_{{\text{User}}_1}(\text{Users})\times {\rho }_{{\text{User}}_2}(\text{Users})$

Definition

Monotone Operators: An operator $O$ is monotone if inserting tuples to $O$‘s operands cannot remove tuples from $O$‘s output.

Any combination of monotone operations gives a monotone relational algebra expression.

If some old output rows may become invalid $⟹$ the operator is non-monotone.

The difference operator is non-monotone. Take $R-S$. If we add something to $S$, then it may change the output of $R-S$ (removing a tuple).

Question

Why is $-$ needed for highest?

Composition of monotone operators produces a monotone query.

• Old output rows remain correct when more rows are added to the input

The highest query is not monotone. The current highest becomes invalidated when the new highest joins.

Relational Calculus (Optional)

Relational Algebra: Procedural language

• Queries are expressed by applying a sequence of operations to relations

Relational Calculus: Declarative language

• A logical formalism in which queries are expressed as formulas of first-order logic. CS245

Theorem

Codd’s Theorem: Relational Algebra and Relational Calculus are essentially equivalent in terms of expressive power.

Example

User first-order logic formulae to specify properties of the query answer. Who are the most popular?

$\{u.uid|u\in \text{User}\wedge \neg (\exists u^{\prime }\in \text{User}:u.pop<u^{\prime }.pop)\}$

Relational algebra is safe relational calculus. A query is safe if, for all database instances conforming to the schema, the query results can be computed using only constants appearing in the database instance of the query itself.

Relational algebra does not have recursion.

SQL: Structured Query Language (supported by most DBMS)

Data-definition language (DDL): Define/modify schemas, delete relations.

Data-manipulation language (DML): Query information, and insert/delete/modify tuples

Lecture 4

DDL:

CREATE TABLE Users(uid INT, name varchar(30), age INT, pop FLOAT);
 
DROP TABLE Users;

DML: SFW statements (also called SPJ)

SELECT A_1, A_2, \ldots, A_n
FROM R_1, R_2, \ldots, R_m
WHERE condition;

Corresponds to (but not equivalent) to

${\pi }_{A_1,A_2,\dots ,A_n}\left({\sigma }_{\text{condition}}(R_1\times R_2\times \cdots \times R_m)\right)$

Example

Names of Users, younger than 18

SELECT name
FROM Users
WHERE age < 18

Example

What year was Lisa born in?

SELECT (2025-age)
FROM users
WHERE name = "Lisa"

Example

Join: IDs of groups Lisa belongs to?

SELECT gid
FROM Users, Members
WHERE name = "Lisa" AND User.uid = Members.uid

Example

Aliasing: Pairs of users who belong to at least one common group.

Both expressions in SELECT and tables in FROM

SELECT DISTINCT m1.uid, m2.uid
FROM Members AS m1, Members AS m2 -- cartesian product
WHERE m1.gid = m2.gid and m1.uid != m2.uid

This does not account for “duplicate” tuples (123, 857) and (857, 123).

SELECT DISTINCT m1.uid, m2.uid
FROM Members AS m1, Members AS m2
WHERE m1.gid = m2.gid and m1.uid < m2.uid

SQL relations are by default bags and not sets. I.e. they can contain duplicate tuples. To remove duplicates, we use SELECT DISTINCT.

The AS is optional. The below is equivalent.

SELECT DISTINCT m1.uid, m2.uid
FROM Members m1, Members m2
WHERE m1.gid = m2.gid and m1.uid < m2.uid

LIKE $\to$ for string pattern matching

SELECT * -- shortcut for everything
FROM Users
WHERE name LIKE "%l%" -- matches 0 or more arbitrary chars
WHERE name LIKE "%l" -- names that end with l
WHERE name LIKE "l%" -- names that start with l
WHERE name LIKE "_l%" -- match exactly one arbitrary char
-- all names whose second letter is l

Set Operations: By default SQL assumes bags semantics. i.e. base relations and outputs of operations return bags.

For Set operations: $\cup ,\cap ,-$ there are two versions.

UNION, INTERSECT, EXCEPT

These adopt set semantics.

UNION, INTERSECT, EXCEPT ALL

These assume bag semantics.

Fruits1

name
orange
apple
apple
apple
grape

Fruits2

name
orange
apple
apple

((SELECT * FROM Fruits1)
UNION ALL
(SELECT * FROM Fruits2))

The output is:

name
orange
orange
apple
apple
apple
apple
apple
grape
grape

((SELECT * FROM Fruits1)
UNION
(SELECT * FROM Fruits2))

Output:

name
orange
apple
grape

INTERSECT ALL of $R$ and $S$ means for each $t\in R$, take the minimum multiplicity of $t$ in $R$ and the minimum multiplicity of $t$ in $S$ and $t$ appears that many times in the output.

INTERSECT of $R$ and $S$ means turn $R$ and $S$ into sets first and then apply set intersect.

((SELECT * FROM Fruits1)
INTERSECT ALL
(SELECT * FROM Fruits2))

Output:

name
orange
apple
apple

((SELECT * FROM Fruits1)
EXCEPT ALL
(SELECT * FROM Fruits2))

Appear in Fruits1 but not Fruits2. Subtract multiplicities (negatives don’t exist).

name
grape
apple

EXCEPT ALL of $R$ and $S$ means for each $t\in R$, $t$ appears in the output “multiplicity of $t$ in $R$ $-$ the multiplicity of $t$ in $S$“.

EXCEPT of $T$ and $S$ means turn $R$ and by default $S$ into sets and then take set difference.

Subqueries/Query Composibility

In relational algebra and SQL, outputs of queries are relations, so they can be used as inputs to other queries.

Pokes

uid1	uid2	timestamp
123	857	Monday 12:00
857	457	Tuesday
857	123	Friday

Table Subqueries:

Example

Names of users who have poked others more than they were poked themselves

FROM Users, ((SELECT uid1 FROM Pokes)) 
EXCEPT ALL
((SELECT uid2 FROM Pokes)) AS T
WHERE Users.uid = T.uid1
SELECT DISTINCT names

Could also make the subquery distinct. But this code makes the final distinct.

Scalar Subqueries

If $Q$ returns a single value, i.e. a single row and a single column, then it can be used as a literal value in any expression. e.g. WHERE, SELECT, etc..)

SELECT *
FROM Users
WHERE age = (SELECT age 
			FROM Users
			WHERE uid = 123);

Select all users whose age is the same as User with uid of 123.

IN Subqeries

If $Q$ returns a single column, then $Q$ can be used in a boolean expression using IN.

SELECT *
FROM Users, 
WHERE age IN (SELECT age
			 FROM Users
			 WHERE name = 'Alice');

”Return me all the users whose ages are the same as some Alice.”

SELECT *
FROM Users, 
WHERE age NOT IN (SELECT age
			 FROM Users
			 WHERE name = 'Alice');

Exists Subqueries

Check if a subquery is empty or not, and can be used in boolean expressions.

SELECT *
FROM Users
WHERE EXISTS (SELECT *
			 FROM Members
			 WHERE Members.uid.= Users.uid)

All users who are members of some group (everything about that member).

Quantified Subqueries

Universal quantifier ($\forall$): All

SELECT *
FROM Users
WHERE pop >= ALL(SELECT pop FROM Users);

Returns true $⟺$ $\forall t$ in the result of subquery, $x\odot t$

Existential quantifier ($\exists$): Any

SELECT *
FROM Users
WHERE NOT (pop < ANY(SELECT pop FROM Users));

Lecture 5

Revisit SFW Semantics

SELECT [DISTINCT] E1, E2, ..., En
FROM R1, R2, ..., Rm
WHERE <condition>

for each tuple $t_1\in R_1,t_2\in R_2,\dots ,t_m\in R_m$, if each condition is true on $t_1,t_2,\dots ,t_m$, evaluate $E_1,E_2,\dots ,E_n$ each of which returns a scalar value and outputs 1 tuple.

SELECT name, EXISTS [SELECT age FROM Users u1 WHERE u1.uid = 143]
FROM Users
WHERE age > 18

Returns tuple of [name, boolean].

Aggregates

Standard aggregation functions: COUNT, SUM, AVG, MIN, MAX

Aggregating over entire relations

SELECT count(*) avg(pop)
FROM Users
WHERE age > 18

Output contains one tuple.

SELECT COUNT(DISTINCT age) -- counts disctinct number of age values that appear in the Users table
FROM Users

SELECT COUNT(DISTINCT uid)
FROM Members
-- number of users who have registered to at least one group

Members table contains [uid, gid].

Grouping

SELECT age, avg(pop) -- hundred tuples and one tuple. bad query
FROM Users

(3) SELECT age, avg(pop)
(1) FROM Users
(2) GROUP BY age

Users

uid	age	pop
143	10	1.0
457	8	0.2
854	10	0.2
555	8	0.2

Group 1: 143, 854

Group 2: 457, 555

Compute the average popularity for each age group.

Query returns the following table:

age	avg(pop)
10	0.6
8	0.2

avg(DISTINCT pop) may result in a different value if there are duplicate pop for the same age.

Notes:

• Queries with aggregate functions that don’t have GROUP BY means having a single group.
• Every expression in SELECT has to either appear in GROUP BY OR be an aggregation function.

HAVING: Syntactic sugar to apply a predicate over a group before outputting.

List average popularity of each age group, but only if the group contains $>100$ people. (i.e. if the group is large enough)

SELECT age, avg(pop), count(*) as cnt
FROM Users
GROUP BY age
HAVING cnt > 100 -- only output if this is true

Ordering

(4) SELECT
(1) FROM
(2) WHERE
(3) GROUP
(5) HAVING

Order By: Comes after optional {sql}GROUP BY and {sql} HAVING and sorts the output table according to some expressions

SELECT uid, name, pop
FROM Users
ORDER BY pop DESC, name ASC

By default [ASC, DESC] is ascending.

LIMIT: Specifies number of tuples to return and after and optional {SQL}ORDER BY. It is often useful to be used in conjunction with {sql} ORDER BY to answer top $k$ or bottom $k$ queries.

SELECT
FROM
WHERE
GROUP
HAVING
ORDER BY
LIMIT

SELECT name, pop
FROM Users
ORDER BY pop DESC 
LIMIT 3

Gives name and popularity of 3 most popular users.

OFFSET k lets you skip $k$ rows.

NULL: How to represent information that is not yet known or not yet applicable

Option 1: Use a special value

• integers: $-1$
• strings: N/A

$⟹$ not a very practical idea in general

Option 2: Special is_valid column

name	name_is_valid	age	age_is_valid
Bart	true	0	false

$⟹$ ruins the schema

Option 3: Decompose tables to each attribute

Users

uid	name	age

Situation: Bart’s age is 10 and Nelson’s age is not known.

UserAge

uid	age
143	10

UserName

uid	name
143	Bart
555	Nelson

$⟹$ complicates things

Special SQL solution for this situation: NULL

uid	name	age	pop
555	Nelson	NULL	NULL
143	Bart	10	0.8

Rules about NULL values:

Any comparison of any sort with a NULL value evaluates to NULL

$5=$ NULL $⟹$ NULL

In WHERE and HAVING if a boolean expression evaluates to NULL, we treat it as false.

SELECT count(*)
FROM Users
WHERE pop=pop

NULL$=$ NULL $⟹$ NULL

Boolean truth table with NULLS

$x$	$y$	$x\wedge y$	$x\vee y$
T	F	T	T
T	F	F	T
T	N	N	T
F	T	F	T
F	F	F	F
F	N	F	N
N	T	N	T
N	F	F	N
N	N	N	N

$x$	$\neg x$
T	F
F	T
N	N

Rules continued:

• Aggregation functions ignore NULL values, except count(*)

SELECT avg(pop) FROM Users -- Compute the average of non-NULL popularity values. 

uid	name	pop
-	-	1.0
-	-	0.8
-	-	NULL

The above query will return $0.9$.

This may not be equal to

SELECT sum(pop)/count(*) FROM Users -- sum sums non-nulls. count counts all tuples

This would evaluate to $0.6$.

SELECT age, avg(pop)
FROM Users
GROUP BY age

DuckDB will group NULLs and take their average.

uid	name	pop	age
-	-	1.0	NULL
-	-	0.8	10
-	-	NULL	8
-	-	0.2	NULL
-	-	0.5	8

age	avg(pop)
NULL	0.6
10	0.8
8	0.5

SELECT sum(pop)/count(*) FROM Users
WHERE pop is not NULL

Lecture 6

OUTER JOINS: Count the number of members in each group, including groups with no member

Users

uid	name	age	pop

Member

uid	gid
143	gov
857	dps
143	dps

Groups

gid	name
xyz	secret society
gov	student gov
dps	dead poet society

SELECT gid, count(*)
FROM Members, Groups
WHERE Members.gid = Groups.gid
GROUP BY Groups.gid

The above doesn’t work

Left/Right/Full Outer joins

$R{⟕}_{p}S\to$ left outer join

$R{\bowtie }_{p}S$ union with all tuples in $R$ that did not participate (i.e. did not produce any outputs) in the $R{\bowtie }_{p}S$, append with nulls for each attribute coming from $S$.

Groups ${⟕}_{\text{Group.gid = Members.gid}}$ Members

gov	student gov	143	gov
dps	dead poet	857	dps
dps	dead poet	143	dps
xyz	secret society	null	null

$R{⟖}_{p}S\to$ right outer join $\to$ keeps dangling tuples from $S$ (appended with nulls for attributes from $R$).

$R{⟗}_{p}S\to$ full outer $\to$ keeps dangling tuples from both $R$ and $S$

SELECT gid, count(*)
FROM Members RIGHT OUTER JOIN GROUP ON Members.gid = Groups.gid
GROUP BY Groups.gid

However we probably want the null to be 0 instead.

SELECT gid, count(uid)
FROM Members RIGHT OUTER JOIN GROUP ON Members.gid = Groups.gid
GROUP BY Groups.gid

SQL Syntax: Two different decisions you have to make to figure out your join:

• Join Predicate

  • Natural ($\bowtie$) (discards rows that don’t match) vs Theta (${\bowtie }_p$) (only keeps rows that satisfy $p$) (default)
    • If you want to do natural join, you have to use NATURAL JOIN keyword. If you omit $⟹$ THETA JOIN

• Dangling tuples

  • Outer Join (keep unrelated tuples) vs Inner join (removes unrelated tuples) (default)

For each group, output the names of the members. If a group has no members, still output with null values.

SELECT *
FROM (Users NATURAL JOIN Members) RIGHT OUTER JOIN Groups ON Members.gid = Groups.gid

INSERT/DELETE/UPDATE

INSERT INTO Members VALUES (789, 'gov')
INSERT INTO Users(uid, name) VALUES (789, 'Alice')
INSERT INTO Members VALUES (SELECT uid, 'dps' as gname -- see table below
					FROM Users)

Constant expression

uid	gnames
143	dps
857	dps
789	dps

Pick every uid in user table, and give it the dps gid in Members.

DELETE

DELETE FROM Members -- removes all tuples
DELETE FROM Members 
		WHERE uid = 143

UPDATES

UPDATE Users Set name = 'Bob' -- will set every users name to Bob
UPDATE Users Set name = 'Bob'
			Where name = 'Bart' -- set all Barts to Bob

UPDATE Users
SET pop = (SELECT avg(pop)
			FROM Users) -- the subqueries in updates run on the older version of the tables

Constraints Declared as part of table definitions.

CREATE TAVLE Users (
	uid INT
	name varchar(30) NOT NULL, 
	SIN INT,
	PRIMARY KEY(name, SIN))

Referential Integrity Constraints

CREATE TABLE Members (
	uid INT REFERENCES Users(uid), 
	gid varchar(30) REFERENCES Groups(gid) )
)
 
CREATE TABLE MemberBenefits(
	uid INT, 
	gid INT, 
	benefit1 varchar(100);
	FOREIGNKEY (uid, gid) REFERENCES Members(uid, gid)
)

Note on Terminology: IN SQL, the referenced attributes do not have to be primary keys of the referenced table. They can also be attributes that have uniqueness constraints.

Member is the referencing table (where uid is the referencing attributes). User is the referenced key where uid is the reference attribute).

Users

uid	name
143	joe

Members

uid	gid
143	dps

Question

What happens if we insert into members (555, dps)

It is rejected

Question

What about deletions from Users

Users

uid	name
143	joe

Members

uid	gid
143	dps

Several options:

1. Reject
2. Cascade (delete the items it refers to in Members)
3. Set the referring address to NULL (if the referring attribute can store nulls)

Lecture 7

Database Modifications order Referential Integrity Constraint

Question

What happens when the referencing and referenced tables are modified?

Insertions into Users

Deletions from Members

Insertions into members - need to check if the referencing after is dangling

Delete from Users need to check if there are any referencing tuples ion Members and if so, there are three options

1. By default, the deletion will be rejected
2. ON DELETE CASCADE: cascade the delete to referencing tuples
3. ON DELETE SET NULL: Set the referencing dangling attributes to nullable (only if the referencing attributes can be NULL) (Updates = delete + insert) $⟹$ (we can still cascade)

CREATE TABLE Members (
	uid INT REFERENCES Users(uid) ON CASCADE DELETE
)

Tuple or Attribute level constraints: CHECK

$check(\underset{\text{bool predicate}}{\underbrace{P}})$ that the system will enforce and holds on every tuple. If the predicate evaluates to NULL, it is treated as not violates the constraint.

CREATE TABLE Users(
	age INT CHECK (age > 10)
)

Users

uid	name	age
142	Bart	11
857	Millhouse	12

We cannot add tuples with age below 10. For each tuple inserted, the check predicate will run.

CREATE TABLE Products (
	Price INT, 
	discPrice INT, 
	CHECK(discPrice < price)
)

SQL Standard allows more “general check” constraints

CREATE TABLE Members (
	uid
	gid
	CHECK (uid IN ( SELECT uid 
					FROM Users))
)

This is allowed, but not recommended. If Users is joined with more things, then it has to be checked anytime one of those other tables is checked. Very expensive and hard to enforce.

Naming constraints $⟹$ you can name your constraints as follows.

CREATE TABLE Products (
	price INT CONSTRAINT highPriceConst CHECK(price > low)
)

We can drop constraints easily this way.

Schema Changes: {sql} ALTER TABLE

1. {sql}ALTER TABLE tablename ADD COLUMN colName colType
2. {sql} ALTER TABLE tablename DROP COLUMN columnname
3. `{sql} ALTER TABLE tablename RENAME COLUMN oldName TO newName
4. {sql} ALTER TABLE tablename ALTER Column oldName newDataType needs to be castable to new data type
5. {sql}ALTER TABLE ADD CONSTRAINT rk_users FOREIGN KEY uid REFERENCES User(uid)
6. {sql} ALTER TABLE tablename DROP CONSTRAINT highPriceConst

Definition

VIEWS: Virtual derived tables that are defined as arbitrary SQL queries (by default completely virtual but part of the database schema)

• Base tables
• Views $\to$ virtual tables
• Temporary tables

CREATE VIEW XYZGroupMembers(uid, name, age) AS 
	(SELECT Users.uid, name, age
	FROM Users, Members
	WHERE Users.uid = Members.uid and Members.gid = 'xyz')
 
DROP VIEW XYZGroupMembers
 

Selecting all the users in the xyz group. We can treat this as if it was a base table in our queries (but it is completely virtual).

SELECT * from XYZGroupMembers

Pros: Simplified your queries e.g. can reduce sub-queries you have to write. Often, many users of the database will only care about different derived tables and not the raw base tables. Good for authorization.

Definition

Materialized View: Tuples of the view is computed and stored in the database

Pros: Very good idea because no query is faster than a simple lookup in an already computed table.

Cons: Hard to keep them fresh as base tables change.

Incremented view maintenance $\to$ how to automatically meep views updated.

Very challenging problem.

Question

Should views be udpatable?

Generally no, but SQL Standard defined a set of restricted views (basically on a single table) that can be updatable $⟹$ but generally supported by systems.

CREATE VIEW AvgPopTable(avgpop) AS 
		(SELECT avg(pop)
		FROM Users)
-- Single column, single value. 

If we materialize this:

CREATE MATERIALIZE VIEW AvgPopTable(avgpop) AS 
		(SELECT avg(pop)
		FROM Users)
UPDATE AvgPopTable SET avgPop = 0.5; -- ambiguous how to propagate the base tables -> not allowed

Definition (WITH)

Temp Tables: Defined within the scope of a single query, not part of the database schema

WITH tmp(uid) AS (
	SELECT uid FROM Users
	WHERE age > 10)
)
SELECT gid from Members, tmp
WHERE Members.uid = tmp.uid

Note: You need to use them as tables and not string substitutions

WITH tmp as (...)
SELECT *
FROM Members 
WHERE Members.uid IN tmp;
-- THIS IS NOT VALID SYNTAX

WITH tmp as (...)
SELECT *
FROM Members 
WHERE Members.uid IN (SELECT *
					 FROM tmp);

Lecture 8

Motivating example of using indexes.

SELECT * FROM User WHERE name = 'Bart';

Question

Can we go directly to rows with name=‘Bart’ instead of scanning the entire table?

An index is an auxiliary persistent data structure that helps with efficient searches.

CREATE [UNIQUE] INDEX indexname ON tablename(col1,..., coln);

With UNIQUE, the DBMS will enforce that $\{co{l}_1,\dots ,co{l}_n\}$ is a key of tablename.

An index on $R.A$ can speed up accesses of the form

• $R.A=$ value
• $R.A>$ value

An index on $(R.A_1,\dots ,R.A_n)$ can speed up

• $R.A_1=$ value${}_1\wedge \cdots \wedge R.A_n=$value${}_n$

The ordering of index columns is important. (The first/major column is ordered, and tiebreaks are broken by the second/minor column).

Programming Applications with SQL

Challenge of using SQL on real app:

• Not intended for general-purpose computation

Solutions

• Augment SQL with constructs from general-purpose programming languages
• Use SQL together with general-purpose programming languages
  • Through an API
  • Embedded SQL e.g. in C
• SQL generating approaches: Web Programming Frameworks (e.g., Django)

1. Augmenting SQL: SQL/PSM

An ISO standard to extend SQL to an advanced programming language

Several systems adopt this partially (e.g. MySQL, PostgreSQL)

PSM = Persistent Stored Modules

2. Working with SQL through an API

E.g.: Python psycopg2, JDBC, ODBC

The application program sends SQL commands to the DBMS at runtime. Gets back a “cursor” that can iterate over results.

• Based on the SQL/CLI standard

Application program sends SQL commands to the DBMS at runtime. Gets back a “cursor” that can iterate over results.

Results are converted to objects in the application program.

Functionalities provided:

• Connect/Disconnect to a DBMS ⇒ get a connection object
• Execute SQL queries
• Iterate over result tuples

conn.set_session(autocommit=True)
bar = input('Enter the bar to update: ').strip() 
beer = input('Enter the beer to update: ').strip() 
price = float(input('Enter the new price: ')) 
try: 
	cur.execute('" 
		UPDATE Serves 
		SET price = %s 
		WHERE bar = %s AND beer = %s'", (price, bar, beer)) 
	if cur.rowcount != 1: 
		print('{} row(s) updated: correct bar/beer?'\
		.format(cur.rowcount)) 
except Exception as e: 
	print(e)

A lot of overhead.

Prepared statements: Example

cur.execute('"# Prepare once (in SQL).
			PREPARE update_price AS # Name the prepared plan,
			UPDATE Serves SET price = $1 # and note the $1, $2, … notation for
			WHERE bar = $2 AND beer = $3'") # parameter placeholders. 
			while true: # Input bar, beer, price… 
				cur.execute(‘ 
					EXECUTE update_price(%s, %s, %s)',\ # Execute many times. 
					(price, bar, beer))…. # Check result...

https://xkcd.com/327/

The school probably had

cur.execute("SELECT * FROM Students " + \
			"WHERE (name = " + name + "')")

This is an SQL injection attack.

Pros of augmenting SQL:

• More processing features for DBMS
• More application logic can be pushed closer to data

Cons of augmenting SQL:

• SQL is already too big
• Complicate optimization and make it impossible to guarantee safety

3. Embedding SQL in a host language

Can be thought of as the opposite of SQL/PSM

Extends a host language e.g., C or Java, with SQL-based features

Can compile host language together with SQL statement sand catch SQL errors during application compilation time

4. Web Programming Frameworks

A web development “framework” e.g., Django or Ruby on Rails

Very frequent approach to web apps that need a DB.

For most parts, no explicit writing of SQL is needed.

SQL Recursion: of of the main shortcomings of relational algebra is $\to$ no recursion

Need to extend SQL when we need to perform some recursive computation

Flights

from	to	cost
A	C	…
A	B	…
B	D	…
D	F	…
C	E	…
C	D	…
E	F	…

$$\begin{array}{rl}& A\to C\to E\\ & \downarrow \downarrow \downarrow \\ & B\to D\to F\end{array}$$

Question

Find all pairs of cities $x,y$ such that there is a direct or indirect flight path from $x$ to $y$

This is a transitive closure query.

If you knew the “depth” of your flight graph, one approach would be to write a query for each depth and union/

SELECT fr, to
FROM Flights UNION 
 

This is for length of 2.

SELECT F1.from, F2.to
FROM Flights F1, Flights F2
WHERE F1.to = F2.from

We would need to $\cup$ this with length of 3, 4, etc.

This won’t work if you don’t know the depth, and often we won’t know the depth. Also very error prone code if depth is large.

SQL’s solution: Recursive Common Table Expressions (CTEs) that are “fixed points” of recursively defined temporary relations using the WITH RECURSIVE clause.

In math, fixed of a function $x_{n+1}=f(x_n)$ starting from $x$. It means the value the following sequence converges to:

$$\begin{array}{r}{x}_i=x_{i+1}=f(x_i)x_{i+1}\text{ is called the fixed point}\end{array}$$

$\frac{1}{2}(\frac{a}{x}+x)$ If $a$ is a positive number, and you start from an arbitrary positive number $>0$, this converges to $\sqrt{a}$.

WITH RECURSIVE T AS Q

means $T$ is the fixed point of $Q(T)$ starting from $T_0=\varnothing$ where $Q$ refers to $T$.

$T_0=\varnothing ,T_1=Q(T_0),T_2=Q(T_1),\dots ,T_i=T_{i+1}=Q(T_i)\to$ fixed point, and so that is $T$.

Overall syntax:

WITH Recursive T as Q -- Q = SELECT * FROM T, Flights..
-- from recursive table
Q* -- that refers to T
-- Q* = SELECT * FROM T
-- actual table

WITH RECURSIVE AP(fr, to) AS  (
	SELECT AP.fr, F.to
	FROM AP, Flights F
	WHERE AP.to = Fr.fr
)

This is wrong. The fixed point of a recursive relation is defined as the fixed point from the empty set. $A{P}_0$ is the empty set, and $A{P}_1$ will be the empty set because $A{P}_0=\varnothing$ and the join will be empty.

Fix: Write $Q$ as a union of $\underset{\text{base case}}{\underbrace{Q_B}}\cup \underset{\text{recursive case}}{\underbrace{Q_R}}$

WITH RECURSIVE AP(fr, to) AS (
	(SELECT fr, to FROM Flights) -- Qb
	UNION
	(SELECT AP.fr, F.to
	FROM AP, Flights F
	WHERE AP.to = F.from))

Very easy to write queries that won’t converge. In practice, it is the users responsibility to ensure that recursive relations will converge.

Question

When do recursive relations converge?

Lecture 9

SQL Reursive Relation

$T$ is defined as fixed points of a query $Q(T)$, starting from $T_0=\varnothing$.

$$\begin{array}{rl}& A\to C\to E\\ & \downarrow \downarrow \downarrow \\ & B\to D\to F\\ & \downarrow \\ & Q\end{array}$$

Example: All pairs of cities $x,y$ such that $x$ can reach $y$ through 1 or more flights

WITH RECURSIVE AP(fr, to) AS (
--Qb
(SELECT DISTINCT(*) FROM Flights) 
UNION
--Qr
(SELECT DISTINCT AP.fr, F.to 
FROM AP, Flights F
WHERE AP.to = F.fr))
--the entirety of the above is Q(AP)

$Q^{\ast }$ that refers to AP and this is the final query $Q^{\ast }$ will use AP.

$A{P}_0=\varnothing$

$A{P}_1$ (This is just flights)

fr	to
A	B
A	C
B	D
C	D
C	E
D	F
E	F
F	G

This is all pairs reachable with $\le$ 1 hops

$A{P}_2$ - Flights $\cup$

A	D
B	F
A	E
C	F
D	G
F	G

All flights reachable with $\le 2$ hops

$A{P}_3$ - Flights $\cup$ (every pair that is reachable with 2 or 3 hops)

Together, this is all pairs reachable with $\le 3$ hops

$A{P}_4$ - Flights $\cup$ (every pair that is reachable with 2 or 3 or 4 hops)

$A{P}_4=A{P}_5$.

SELECT fr
FROM AP
WHERE to='F'

Not every $T=Q(T)$ will converge. $R=1,2$

SWITH RECURSIVE T AS (
	(SELECT *FROM R)
	UNION 
	(SELECT SUM(*) FROM T)
)

$T_0=1$

$T_1=1,2$

$T_2=1,2,3$

$T_3=1,2,6$

$T_4=1,2,9$

Question

What guarantees convergence?

In general, if $Q$ is monotone on $T$, and is limited to core relational algebra, $Q$ will converge.

Key takeaway: Something being monotone (with some caveats) is a sufficient condition, but not necessary. That is, we can write non-monotone queries that also converge.

It is your responsibility to ensure that your recursive queries converge. Systems will not help much.

Recall: $Q$ is monotone on a relation $R$, if we compute $OUT=Q(R)$ and we add tuples to $R$, i.e. $OU{T}^{\prime }=Q(R+\Delta R)$, then $OU{T}^{\prime }\supseteq OUT$

Argument per why $Q$ being monotone on $T$ guarantees convergence (if you limit $Q$ to core relational algebra).

Any tuple that is output by $Q$ contains values that came from the base relations, which are finite.

Therefore $Q(T)$ can contain a finite number of tuples.

So if $Q(T)$ is monotone on $T$ at some finite number of iterations it has to converge.

WITH REC T
SELECT * FROM R
UNION
(SELECT * FROM T)

Don’t do this.

WITH REC T
SELECT * FROM R
UNION
(SELECT * FROM T)
UNION 
(SELECT x+1 FROM R)

This is no longer finite.

Linear vs non-linear recursion

Linear: $Q(T)$ refers to $T$ once

Non-linear: Refers to $T$ > 1

WITH RECURSIVE AP AS
()
UNION
(SELECT AP1, AP2
FROM AP AP1, AP, AP2
WHERE AP1.to AP2.fr

$A{P}_0$

$\varnothing$

$A{P}_1$

Flights

$A{P}_2$

Flights $\cup$ Pairs of exactly 2 hops

$A{P}_3$

Flights $\cup$ pairs of exactly 2, 3, or 4 hops

In fact: SQL Standard does not allow non-linear recursive queries and won’t allow many operations such as aggregations that might lead to non-monotoness.

Mutually recursive relations:

WITH RECURSIVE 
T1 as Q1,
T2 as Q2,
...
T1 as Qi

Natural: n: 1, 2, $\dots$ 100

WITH RECURSIVE
EVEN AS (SELECT n FROM Natural) 
 
ODD AS ( SELECT * FROM Natural 
	WHERE n = 1)
	UNION
	(SELECT n FROM Natural
	WHERE n+1 IN (SELECT *
					(FROM Even)))

$OUT=R\bowtie S$

Question

If we add $\Delta R$ to $R\to$R’ = R \cup \Delta R$.Whatarethenewtuplesin$OUT$,i.e.$\Delta OUT$?

$OUT=(R\cup \Delta R)\bowtie S$

$\Delta OUT=OU{T}^{\prime }-OUT\to \Delta OUT=\Delta R\bowtie S$

When $Q(T)$ is linearly recursive

$Q=R_1\bowtie R_2\bowtie T\bowtie R_k$

Advantage of linear recursion is if $Q$ is monotone, a system can only use $\Delta T_i$ at each step of the fixed point computation instead of $T_i$, to compute and determine if $T$ converged.

$(R\cup \Delta R)\bowtie (S\cup \Delta S)$

$\Delta OUT=\Delta R\bowtie S,R\bowtie \Delta S,\Delta R\bowtie \Delta S$

Lecture 10

Theory of Normal Forms:

Goal: How do we formally tell apart good database designs from bad ones.

Inst Dep

iID	name	salary	depName	bldg	budget
111	Alice	5k	CS	DC	20k
222	Bob	4k	Phy	Ph	30k
333	Carl	7k	CS	DC	20k
111	Alice	5k	Phy	Ph	30k

Informally: Bad designs have avoidable redundancy.

Why avoid redundancy:

1. Hard to maintain databases and keep ihpo consistent
2. Your database size goes up and system slows down.

Note: To understand redundancy, you need information about application constraints and application constraints are external information.

Upshots:

flowchart LR
x[DB] ---> a[DB Design Theory]
y[Ext App Constraints - FD] ---> a[DB Design Theory]
a ---> b[Good vs Bad Design - normal form]

flowchart LR
a[DB bad design] ---> b[Decomposition Tool]
c[App Constraints] ---> b[Decomposition Tool]
b ---> e[Good Design]

Designdata for decomposition:

1. Lossless: If $R$ is decomposed into $R_1,\dots ,R_k$ we want $R_1\bowtie R_2\cdots \bowtie R_k=R$

iID	Name	Salary	Dept
111	Alice	5k	CS
222	Bob	4k	Phy
333	Carl	3k	CS
111	Alice	5k	Phy

depName	Bldg	Budget
CS	DC	20k
Phy	Ph	30k

This is lossless.

2. Locality of Constraints: If the app has a constraint $C$, that we could check directly on $R$, then we ideally want to check $C$ still on one relation.

Constraint: Each student can align with advisor(s) from one department.

sID	iID	idepName
s1	i1	d1
s2	i2	d2

sid	iID
s1	i1
s2	i2

iID	idep
i1	d1
i2	d2

We can’t check directly when the relation is split.

Expressing app Constraints: Functional dependencies $⟹$ generalized uniqueness constraints

Definition

A FD $X\to Y$, where $X$ and $Y$ are sets of attributes, holds in $R⟺$ for each possible $X$ value, there is only one possible $Y$ value.

More formally: If $t_1,t_2\in R$ and $t_1[X]=t_2[X]$ then $t_1[Y]=t_2[Y]$

You can express key constraints as FDs.

depName $\to$ (bldg, budget)

(iID, depName) $\to$ (name, salary, bldg, budget)

If $X\to Y$ holds and $XY$ i.e., $X\cup Y$, is all the attributes in $R$, then $X$ is a super key of $R$.

Implied FDs: Armstrong’s Axioms:

1. Reflexivity: If $Y\subseteq X$ then trivially $X\to Y$.
2. Augmentation: If $X\to Y$, then $XZ\to YZ$
3. Transitivity: If $X\to Y$, and $Y\to Z$, then $X\to Z$

Derived Rules based on Armstrong’s axioms: 4. Decomposition: If $X\to YZ$, then $X\to Y$ and $X\to Z$

Proof:

Assume $X\to YZ$

$$\begin{array}{rl}& X\to YZ\\ & XZ\to Y\text{by reflexivity}\\ & X\to Y\end{array}$$

5. Union: If $X\to Y$ and $X\to Z$, then $X\to YZ$
6. Pseudo-Transitivity: If $X\to Y$ and $YZ\to T$, then $XZ\to T$

Close of a set of FDs $\mathcal{F}$: (${\mathcal{F}}^{+}$) is all FDs implied by $\mathcal{F}$

Example:

1. iID $\to$ (name, depName)
2. depName $\to$ bldg

These are both in $\mathcal{F}$

${\mathcal{F}}^{+}=\mathcal{F}\cup$ iID $\to$ iID, iID.name $\to$ iID.name $\cup$ iID $\to$ bldg (by transitivity)

InstProj

iID	name	projID	projName	projDep	hours	funds

$\mathcal{F}=$

1. iID $\to$ name
2. projID $\to$ projName, projDep
3. (iID, projID) $\to$ hours
4. (projDep, hours) $\to$ funds

Question

Prove (iid, projID) $\to$ funds

Proof:

$$\begin{array}{rl}(iID,projID)& \to hours\text{by 3}\\ projID& \to (projName,projDep)\text{by 2}\\ (iID,projID)& \to iID,projName,projDep\text{by Augmentation}\\ (iID,projID)& \to iID,projName,projDep,hours\text{by }\cup \text{ of first and third}\\ (iId,projID)& \to funds\text{by transitivity with 4}\end{array}$$

Algorithm for computing ${\mathcal{F}}^{+}$ (see slides) set ${\mathcal{F}}^{+}=\mathcal{F}$ and in iterations using one or two FDs in ${\mathcal{F}}^{+}$ and Amrstrong’s axioms, try to derive new DFs until convergence.

Boyce - Codd Normal Form (BCNF):

Definition

Given FDs $\mathcal{F}$ and a relation $R$, $R$ is in BCNF $⟺\forall X\to Y\in {\mathcal{F}}^{+}$ such that $XY\subseteq R$ (meaning $R$‘s attributes contain $X\cup Y$). One of the two following conditions hold:

1. $X\to Y$ is trivial, i.e. $Y\subseteq X$ or
2. $X$ is a super key in $R$

Consider the following FDs on InstDep

1. iID $\to$ (name, salary)
2. depName $\to$ (bldg, budget)

Question

Is InstDep in BCNF?

No, because iID $\to$ (name, salary). iID is not a key.

R1

iID	name	salary	depName

R2

depName	bldg	budget

Divide $R1$ into more

Decompose this more into

iID	name	salary

and

iID	depName

Lecture 11

iid	name	salary	depName	bldg	budget
111	Alice	5k	CS	DC	20k
111	Alice	5k	Phy	Phy	30k
222	Bob	4k	CS	DC	20k
333	Carl	3k	CS	DC	20k

iID $\to$ (name, salary)

depName $\to$ (bldg, budget)

Greedy Top-Down BCNF Algorithm:

Input: $R,{\mathcal{F}}^{+}$

rels = $\{R\}$

1. Find a FD $X\to Y$ violating BCNF in some relation $R_i\in$ rels
2. $R_{i1}=X\cup Y$, $R_{i2}=X\cup RST$ ($RST$ is $R-\{X\cup Y\}$). rels $=$ rels $-R_i\cup \{R_{i1},R_{i2}\}$
3. Repeat until no such FD exists

Note 1: Need to consider ${\mathcal{F}}^{+}$ and just $F$, because there can be non-trivial direct or implied FDs to consider

Note 2: BCNF decompositions are not unique

Note 3: Lossless. At each split, $XY$ is one side of the split and $X$ is a key in $XY$. Therefore, the join of $R_{i1}\bowtie R_{i2}$ on $X$ is $1-1$ and gives back exactly $R_i$

Note 4: Note dependency preserving.

DeptAdvisor

FDs

• (sID, depName) $\to$ iID. In English, you can only have at most one advisor from each faculty.
• iID $\to$ depName

sID	depName	idID
S1	CS	i1
S1	Phy	I2

Can break this down into

iID	depName
i1	CS
i2	Phy

sID	iID
s1	i1
s1	i2
s2	i2

Can’t tell the functional dependencies from these separated tables.

BCNF is not dependant preserving because of two reasons

1. BCNF definition is too strict
2. BCNF decomposition algorithm, which is top-down, can break FDs $⟹$ need a new decomposition algorithm

Note that it is fine for some functional dependencies to not be locally preserved as long as they are implied by other locally preserved functional dependencies.

DepAdvisor

FDs

• iID $\to$ depName
• sID $\to$ iID
• Transitive: sID $\to$ depName

sID	iID	depName

We can break this down into:

iID	depName

and

sID	iID

Restriction: Let $\mathcal{F}$ be a set of FDs in $R$. The restriction of $\mathcal{F}$ to and $R_i$ is the set of FDs in ${\mathcal{F}}^{+}$ $X\to Y$ such that $X\cup Y\subseteq$ of attribute($R_i$)

Dependency Preservation: Let $D=\{R_1,R_2,\dots ,R_k\}$ be a decomposition of $R$. Let $\mathcal{F}$ be a set of functional dependencies in $R$. Let ${\mathcal{F}}_1^{\prime },{\mathcal{F}}_2^{\prime },\dots ,{\mathcal{F}}_k^{\prime }$ be the restrictions of $\mathcal{F}$ onto $R$, for $i=1,\dots ,k$. Then $D$ is dependency preserving if (${\mathcal{F}}_1^{\prime }\cup {\mathcal{F}}_2^{\prime }\cup \cdots \cup {\mathcal{F}}_k^{\prime })={\mathcal{F}}^{+}$.

Definition (3NF)

A relation $F$ is in 3NF, given $\mathcal{F}$ and ${\mathcal{F}}^{+}$ of FDs $\forall$ FDs $X\to Y$ that are in $R$. One of 3 conditions hold

1. $X\to Y$ is trivial
2. $X$ is a superkey
3. all possibly duplicates attributes, which have $Y-X$, are part of some candidate key.

DeptAdv

FDs

• (sID, depname) $\to$ iID
• iID $\to$ depName

sID	depName	iID
S1	CS	111
S1	Phy	222
S2	CS	111

This is $\notin$ BCNF because iID $\to$ depName.

However this is $\in$ 3NF.

3NF Decomposition Algorithm: Bottom up algorithm

Minimal/Canonical Covers of FDs $F$: $F$ is minimal if $\forall X\to Y\in F$.

1. $Y$ consists of a single attribute
2. $(\mathcal{F}-\{x\to y\}{)}^{+}\ne f^{+}$
3. There is no Z $\subset$ X such that $(F-\{X\to Y\}\cup \{Z\to Y\}{)}^{+}=f^{+}$

Let $f_c$ be a minimal cover of $f$.

$D=\{\}$

For each $X\to Y\in f_c.D=D\cup \{XY\}$

Fix 1. If $D$ does not contain a relation $R_i$ such that $R_i$ contains a candidate key for $R\to$ add to $D$ a relation $R^{\ast }$ that consists of a candidate key of $R$.

Fix 2: If there any redundant $R_i$ remove them.

4NF: MVDs are generalizations of FDs

$X\to Y$

$RST=R-\{X\cup Y\}$

An MVD: $X\to Y$ holds in $R$ if given tuples $t_1,t_2$ if $t_1[x]=t_2[x]$ and $t_1[y]\ne t_2[y]$. Then, $\exists t_3,t_4$ such that $t_3[x]=t_4[x]=t_1[x]=t_2[x]$ and $t_3[y]=t_1[y]$ and $t_3[RST]=t_2[RST]$ and $t_4[Y]=t_2[Y]$ and $t_4[RST]=t_1[RST]$

iID	email	dep
111	alice@gmail	CS
111	alice@hotmail	CS
111	alice@yahoo	Phy
111	alice@gmail	Phy

Lecture 12

MVDs: An MVD $X\twoheadrightarrow Y$ holds in $R$ if given some values for $X$ ($x_1,\dots ,x_k)$ the set of $Y$ values that appear in $R$ are “conditionally independent” of the $RST=R-\{X\cup Y\}$ values

Claim: Every FD $X\to Y$ is also an MVD

iid	email	dept
111	alice@gmail	CS
111	alice@hotmail	Phy
111	alice@gmail	Phy
111	alice@hotmail	CS

iid $\twoheadrightarrow$ email. $\in$ BCNF, $\notin$ 4NF

Definition

4NF: $R$ is in 4NF, if $\forall X\twoheadrightarrow Y$, $X$ is either a key or $X\twoheadrightarrow Y$ is trivial.

iid	email

iid	dpt

trivial MVD because $RST$ is empty.

Entity/Relationship DB Design Model:

Humans think of the world in object-oriented manner instead of flat tables

• Objects/entities/things
• Relationships between objects
• Attributes on relationships and objects

Upshots:

flowchart TD
a[DB Design] --> b[DB Logical Record Model]
b --> c[Physical Record Design]

flowchart TD
a[E/R] --- b[Relations]
a --- c[Network Records]

Ingredients of the E/R Model: Relationships between entity sets are always explicitly drawn

• Entity Sets
• Relationship sets
• Attributes on entities and relationships

Attributes are as ovals from the groups.

$n$-ary relationships:

Rules:

Primary Keys: For entities are explicitly defined by underlining some attributes.

For relationship sets: are the union of the Primary Keys of the participating attribute sets.

Consequence: Cannot have parallel relationships between two objects/entities.

The “trick” to model parallel relationships is to turn them into entity sets (reification).

Multiplicities of binary relationship sets

Many-to-many:

Each $E$ can be related to $\ge 0$ different $F$‘s. Each $F$ can be related to $\ge 0$ different $E$‘s.

Many-to-one:

Each $E$ can be related to $0$ or $1$ $F$. Each $F$ can be related to $\ge 0$ $E$‘s.

Each user $u_i$ can be part of at most one group.

One-to-one:

Each $E$ can be related to $0$ or $1$ $F$‘s and vice versa.

In the original E/R model, there is a general multiplicity constraint.

Each User can be in 2-5 groups. Each Group can have between 1-100 Users.

Weak Entity Sets

Primary key for isIn: (bID, rNo) is already the same primary key as Rooms.

Option 1: Remove bID from Rooms $⟹$ not ideal because need a new primary key attribute for Rooms.

Option 2: Remove isIn completely $⟹$ not ideal because it makes the relationship between Rooms and Buildings implicit.

Weak Entity Set: Captures such scenarios, when a “weak” entity set has an identifier as dominant entity set it depends on.

Primary key of a weak entity set is the union of attributes of its dominant entity set and the discriminator attributes of the weak entity set.

IsA relationship: The tool to construct class hierarchies.

Aggregations: Tool to link entities to relationships (covered above).

Questions about what are my entities $\to$ which are weak etc. This is more an art.

Lecture 13

ISA Relationships:

2 constraints:

1. Overlapping vs Disjoint

Overlapping: A superclass entity can be a member of multiple subclasses

Disjoint: A superclass entity can be a member of at most 1 subclass

2. Partial vs Total

Partial: Every superclass entity does not have to be a member of any subclass entity

Total: Every superclass entity has to be a member of some subclass entity.

Translating ER Diagram into Relational DB Schemas

Not every information in an ER diagram may be translatable. e.g. general multiplicities

Sometimes there are multiple options $⟹$ there is not right/wrong answer, there are tradeoffs

(Strong) Entity Set (ES): Direct translation, where each strong ES is its own relation with the same attributes and primary keys. For composite attributes, take the lowest-level attribute.

Relationship Sets (RS): IsMember(uid, gid, fromDate) (PK is {uid, gid})

By default (when each participating entity set is in a many-to-many multiplicity), a new table with attributes: PKs of participating entity sets $\cup$ any attributes of the relationship set

PK: PKs of the participating entity set

FKs: To the PKs of participating entity sets

However, if one of the participating Entity Sets ($E^{\ast }$) has a $(0,1)$ multiplicity then you can simplify the PK of IsMember to just the PK of $E^{\ast }$.

Users(uid*, name) or can do $\to$ Users(uid, name, gid, fromDate)

Group(gid*, gname)

IsMember(uid*, gid, fromDate)

* $⟹$ Primary key

Roles:

Person(pid, name)

ParentOf(parent_id, child_pid)

Only affect the names of the attributes in the translated relation.

Weak ES (WES)

Make them a table of their own

• Attributes: PK of its dominating ES $+$ its differentiator attribute $+$ any other attrbiute
• PK: PK of its dominating ES $+$ its differentiators
• FK: FKs to the PK of its dominating ES

Building(name*, year)

Rooms(b_name*, rnumber*, capacity)

FK between b_name in Rooms and name in Building

Seats(b_name*, rnumber*, snumber*, size) (differentiator is snumber)

FK between b_name, rnumber in Seats to b_name, rnumber in Rooms

Question

How about supporting relationships?

We can forget about them.

ISA Relationships: Upshots: There are multiple options, each offering different tradeoffs. Use your judgement but some options may not work in some cases.

Option 1: Entity-in-all-superclasses:

Each entity set translates to a separate table. Info about a single entity can appear in multiple tables.

Students(sid*, name)

Undergrads(sid*, major)

Grads(sid*, advisor)

Option 2: Entity-in-most-specific subclass:

Only have tables for most-specific child subclass. $⟹$ can only work in Total ISA relationships.

Undergrads(sid*, name, major)

Grads(sid*, name, advisor)

Pro: An entity’s attributes are always in one table (if the relationship is disjoint)

However, not a very elegant solution. Removes the abstraction of a Student.

Option 3: Single top-most table:

Students(sid*, name, major, advisor)

Pro: simple in terms of number of relations in the schema.

Cons: Setting yourself up for NULL values (don’t want this)

We can be between these three options:

Students(sid*)

Undergrads(sid*, name, major)

Grads(sid*, name, advisor)

Aggregation

Question

How to translate $A^{\ast }$ to a table?

You don’t translate $A^{\ast }$ into its own table.

Question

How to translate eval_for RS?

Same as translating any RS except for the PK of $A^{\ast }$ just use the PK of projGuide

eval_for(eID*, iID*, pID*, sID*, rating)

Lecture 14

High-level DBMS Architecture

Transformation of Query’s structure

• Text
• An in-memory representation
• Logical plan
• Physical plan

The parser takes the query and turns it into an abstract syntax tree based on SQL grammar. Performs syntactic check. This is similar to the process in CS241.

We take this element of parsing into a tree from linguistics.

After we create the tree, we bind.

The binder binds type information to columns and expressions. Uses a system component called Database Catalog. This is where we can see type errors.

We then move to a normalizer. This converts comparisons, performs constant arithmetic, simplifies boolean expression etc.

Then moves to the logical plan translator. This maps the normalized abstract syntax tree to an initial unoptimized logical query plan. These are high-level operator.

flowchart TD
a[Project cid] --- b[Filter name=BookA]
b --- c[Join C.cid=O.cid]
c --- d[Join P.pid=O.pid]
c --- e[Scan Customer Table]
d --- f[Scan Table Product]
d --- g[Scan Table Order]

The optimizer then takes this initial plan and uses a set of rules and estimated cost to optimize. For example we may pushdown the filter.

flowchart TD
a[Project cid] --- b[Join C.cid=O.cid]
b --- c[Join C.cid=O.cid]
b --- d[Filter name=BookA]
c --- e[Scan Table Order]
c --- f[Scan Table Customer]
d --- g[Scan Table Product]

Next step is the physical plan translator. This translates the logical operators into physical operators. Logical operators are placeholders to describe overall algorithm, and physical operators are classes in the implementation language of the DBMS that have functions that operate on tuples.

flowchart TD
a[Project cid] --- b[HashJoin L.$3=R.$3]
b --- c[HashJoin L.$3=R.2]
b --- d[IndexScan Product name=BookA]
c --- e[FileScan Order]
c --- f[FileScan Customer]

The query executor then executes physical plans. Could be single threaded but all modern systems parallelize queries. They implement a task scheduling mechanism. A pool of worker threads execute plans in parallel and coordinate.

Storage Manager and Physical Organization Designs

DBMS store data persistently on durable storage devices. Hard disks or flash disks or more recently non-volatile memory. Hence our drawing of DBMSs as disks.

But query processing is computation and all computation ultimately happens in memory.

RDBMSs store data in table/index files on disk. Several physical operators access data in files. Most importantly scans but sometimes also joins.

File accesses happen via classes implemented in StorageManager component.

Physical Operator/Storage interface

Class ScanTable : public PhysicalOperator { 
 
string tableFilename; 
DBFileHandle* dbFH; // Interface
int nextRecordID;
// Assume parent operator has access to outTuple as well
Tuple* outTuple;
 
void init() {
	dbFH = new DBFileHandle(tableFilename); // e.g. order.db
	nextRecordID = 0;
}
 
// each op in the tree calls its child to get next Tuple
Tuple* getNextTuple() {
	if (nextRecordId < dbFH.maxRecordID) {
		dbFH.readRecord(&outTuple, nextRecordID);
		nextRecordID++;
		return &tuple;
	}
}}

Functions such as readRecord in DBFileHandle-like classes that form the operator/storage interface know about physical data organizations.

1. Record layout in files
2. Page/Block layout of records in files

Question

Why is there another unit of data called page/block?

Question

Potential goals of DBMS implementors when designing physical layouts?

Question

Common record and page layouts?

Potential goals of physical data design

1. Minimize I/O
   1. Pack records into few number of pages
   2. Keep related data close in storage devices
   3. Cache pages of data that is likely to be used
2. Maximize sequential reads/writes from storage devices
3. Simplicity/speed of accessing values

Operating System reads/writes data from and to disk in pages. DBMS should also read/write data in pages.

Random I/O is slow, sequential I/O is much faster. Reading 1GB of 64bit ints randomly in RAM vs sequentially and you might get ~80x difference.

Question

Why is Random I/O Slow on Disks?

Time to read $\times$ bytes: Seek time + rotational delay + transfer time. Explained further in What Every Programmer Should Know About Memory

Lecture 15

Thank you to https://eugenezhang.me/ for Lecture 15 notes.

Row-Oriented $N$-ary Storage Model (NSM)

We assume:

• Each page is of fixed size $H$ (4, 8, 16KB)
• Each record consists of fixed size fields of total size $T<H$
• Assume no compression, or if there is compression, does not isolate fixed size assumption

Customer

cid	name	isGoldMember
uint64	varchar(60)	bool
8 bytes	60 bytes	1 byte	$⟹T=69$ bytes

The advantage of making each field the same size in the design is we can use some arithmetic to find the beginning of each record.

Pros: Good for queries that access/write all or many fields

SELECT * FROM Customer WHERE cID = 203
INSERT INTO Customer VALUES (505, 'Dan', 1) -- only one I/O needed, good throughput

Cons: Queries that access/write few fields force you to read entire table, with $1/69$ valid scans (since only $1/69$ bytes used to check isGoldMember)

SELECT Count(*) FROM Customer WHERE isGoldMember = true

DBMS have a buffer manager (BM) component that keeps a set of file pages in memory to reduce I/O.

Goal of BM: keep pages that are likely to be accessed in memory (i.e. LRU).

Column Record Design

cid

101	203	107

Name columns

Alice1011$\cdots$	Bob1010$\cdots$	Carl1011$\cdots$

isGoldMember columns

1	0	1

Pros:

• Good for queries that access few columns
• Easier to apply compression
• Easier to insert/remove columns from records

For SELECT *, must do 3 I/Os (cid, name, isGoldMember)

Cons: Queries that access many columns

Variable-Length Fields

More complex than fixed-length fields. This assume row-oriented NSM storage.

Option 1: Delimiters

Assume records only have 1 variable length field.

If there are multiple variable length fields.

Option 2: Overflow fields, turn variable length fields into fixed length fields (8 bytes) pointers to an overflow.

Every field is fixed length (so no page level offsets) but variable length fields are pointers.

Question

So what do we do with NULLS?

Several options, but the common strategy is to store null bits.

Lecture 16

Indices: Primary mechanism to provide sorted access to records in a relation. Speed up lookups and range queries but several other queries as well. They are persistent data structures stored alongside the table files to speed up search.

WHERE R.A = v -- lookup on v
WHERE R.A > 50
WHERE R.A > 50 AND R.A < 100
 
SELECT X
FROM R, S -- merge join operations that access data through indices
WHERE R.A = S.B -- could benefit from indices on R.A and S.B

SELECT age, avg(salary)
FROM Employee
GROUP BY on age

Index on (salary, age). (Salary is the major sum, age is the minor sum). Or (age, salary) (assuming row-oriented DBMS).

Upshot: 5 designs that progressively improve on each other and lead to $B/B+$ trees.

Question

How can you provide sorted access to the tuples of a relation?

Naïve Approach: Keep the relation pages in sorted order and seven sequentially on disk based on shifting.

Con: Very expensive in terms of I/O to keep pages sorted.

2nd Approach: Single-level dense index

Relation pages are not sorted. A dense index level pages are sorted and maintained by shifting. Dense $⟹$ every key appears in the index.

3rd Approach: Single-level sparse index with overflows.

Could be a practical implementation if the application bulk ingests as lot of data and the relations remain relatively stable.

Upon insertions we put records into overflow pages.

There are two problems.

Problem 1: Index pages can still be quite large.

Problem 2: If the assumptions fail, can create very long overflow pages that make the approach degenerate to the naïve approach.

4th Approach: Multiple levels of sparse indices.

In multi-level sparse indices, instead of (key${}_1$, ptr${}_1$), (key${}_2$, ptr${}_2$), $\dots$ we can store sparse index pages as

$$\begin{array}{rl}& (pt{r}_1,ke{y}_1,pt{r}_2,ke{y}_2,\dots ,ke{y}_{k-1},pt{r}_k)\\ & \downarrow \downarrow \downarrow \\ & <ke{y}_1[ke{y}_1,ke{y}_2)\ge ke{y}_{k-1}\end{array}$$

$B/B+$ trees (5th Approach)

Clustered: The dense layer contains relation pages in sorted order. Unclustered: The dense layer is dense index larger on top of

Common properties of both clustered and unclustered:

• $k$-ary balance tree
  • $k$ pointers that are kept in the node
• multi-level sparse indices on top of some dense layer.

Clustered $B+$ tree

The relation pages are not necessarily stored consecutively on disk. That’s why they are changed.

Whereas unclustered $B+$ tree has (starting from bottom) relation pages, dense index levels, sparse levels.

Lecture 17

Difference between $B$ and $B+$ tree

$B$-tree stores pointers to records in non-leaf nodes too (and does not store these search keys in other non-leaf or leaf nodes).

Pro: These records can be accessed with fewer I/O’s.

Cons: Storing more data in nodes decrease fan-out and increase $h$. Records in leaves require more I/O’s to access. Vast majority of the records live in leaves.

CREATE INDEX Employee Age on Employee age

Creates an unclustered $B+$ tree index.

RDBMS either provide:

• No support clustering records based on the index (Postgres)
• Automatically cluster a table based on its PK index, which is built automatically (SQL Server and MySQL)

Postgres has a CLUSTER command: clusters pages according to an index, but clustering is not maintained upon updates.

Takeaway: No way to create explicit “clustered indices” except in some systems on the PKs of a table.

Every index created with CREATE INDEX command is unclustered.

Primary keys are clustered, secondary indices are unclustered.

There are two classes of indices overall.

Tree-based: Can do both lookups and range queries.

Examples include $B/B+$ trees, $R$ trees, Radix trees.

Hash-based: Can only do look ups. Cannot do range queries. In practice: handle collisions.

Query Processing

SELECT R.X
FROM R, S
WHERE R.A = S.B

QP Paradigms:

Interpreted vs Compiled

Materialized vs Pipelined

Materialized: All ops are “blocking”. Materialize all their inputs to disk. Simple to implement but now obsolete.

Pipelined: When possible, ops take 1 or more tuples-at-a-time, process, and pass to parent ops. This is much more efficient but not always possible. This leverages hierarchies of memory, fast access to the same data.

Volcano vs Block-at-a-time

Query Processing: Algs

I/O Model of Computation: cost metric is I/O and not runtime.

$|R|\to$ # tuples in $R$.

$B(R)\to$ # of blocks of $R$.

$r,s\to$ individual tuples in $R,S$.

$M\to$ # available memory blocks.

Setting is $B(R)\gg M$.

Criticisms

• Does not capture runtime
• Does not capture the difference between sequential and random I/O (for simplicity)

Full Table Scan

Can be used as the only operator for simple queries.

SELECT R.X
FROM R
WHERE R.A >= 10 or R.X <= 50

$⟹$ I/O cost $(B(R))$.

Index-scan cost depends on many factors. Will discuss later, but just a lookup on R.A = x when A is a key when there is an index on R. Is $O(h)$ I/O where $h$ is the height if the $B+$ tree.

Nested Loop Join

One of the most generic join algorithms that can evaluate arbitrary theta joins

$R{\bowtie }_{p}S$

for each $b_R\in B(R)$: for each $r\in b_R$: for each $b_s\in B(S)$: for each $s\in b_S$: check if $r\cdot s$ pass $p$

$R$ is called the outer table; $S$ is called the inner table.

I/O’s: $B(R)+|R|\cdot B(S)$

We can improve upon this with a Block-Nested-loop join operator.

Block Nested Loop Join

for each $b_r\in B(R)$: for each $b_s\in B(S)$ cartesian product of $b_R\times b_S$ and check if those tuples pass $p$

I/O’s: $B(R)+B(R)\cdot B(S)$

Uses 3 blocks of memory and “wastes” $M\cdot 3$ blocks.

Can optimize by scanning $M-2$ many $R$ blocks and streaming $S$ blocks. Read into memory as many blocks of $R$ as possible, stream $S$ by one-block at a time, and join every $S$ tuples with all $R$ tuples in memory.

I/O’s: $B(R)+\lceil \frac{B(R)}{M-2}\rceil \cdot B(S)$

Lecture 18

At a high-level, majority of DBMS operators require sorting or hashing of input tables. If you have a DBMS that has these core operators implemented $⟹$ a solid query processing foundation.

Merge Sort Operator

Sort progressively larger runs, 2, 4, 8, $\dots$, $|R|$ by merging consecutive “runs”.

Phase 0: Read $M$ blocks of $R$ at a time, sort them, and write out a level-0 run

Phase 1: Merge $(M-1)$ level-0 runs at a time, and write out a level-1 run

Phase 2: Merge $(M-1)$ level-1 runs at a time, and write out a level-2 run.

Final phase produces one sorted run

I/O Cost Analysis

Phase 0: $2\times B(R)$ I/Os. There are $\lceil \frac{B(R)}{M}\rceil$ level-0 sorted runs.

Phase $i$: Merge $(M-1)$ level-$(i-1)$ runs at a time, and write out a level-$i$ run: $2\times B(R)$ I/Os as well.

Total I/O: $2B(R)\times$ number of phases. The number of phases: $1+\lceil {\log }_{M-1}\lceil \frac{B(R)}{M}\rceil \rceil$

Total I/O: $2B(R)\cdot \left(1+\lceil {\log }_{M-1}\lceil \frac{B(R)}{M}\rceil \rceil \right)\approx 2B(R){\log }_M(B(R))$

As $M$ increases, cost decreases.

ORDER BY, Set union, difference, intersection, and Join all use sorting.

Sort-merge Join

$R{\bowtie }_{R.A=S.B}S$

Sort $R$ and $S$ b their join attributes; then merge. The I/O’s depend on how many tuples match. In the common case, sorting $+O(B(R)+B(S))$, but in the worst case $B(R)\cdot B(S)$

Hashing-based Operators

Hashing is a common primitive used in many operators (e.g. DISTINCT).

Hash Join: For equality joins: $R{\bowtie }_{R.A=S.B}S$

Observation: Let $h$ be a hash function mapping $A,B$ values to $1,\dots ,k$. Then if $r\in R$ and $s\in S$ are such that $r.A=s.B$, then $h(R.A)=h(S.B)$

Question

Why is this useful?

We can partition $R$ by hashing its tuples on $A$ into $R_1,\dots ,R_k$

We can partition $S$ by hashing its tuples on $B$ into $S_1,\dots ,S_k$

for each $i=1\dots k$ pull $R_i$ and $S_i$ into memory and run an in-memory join algorithm. If we use an in-memory hash join as well, the system will pick the smaller table as hash build size and the larger one as probe side.

Analysis: If $R_i$ and $S_i$ fit into memory: Total $I/O$ cost excluding output writing is

$\underset{\text{partition}}{\underbrace{2(B(R)+B(S))}}+\underset{\text{join}}{\underbrace{B(R)+B(S)}}$

If the assumption fails and $R_i$, $S_i$ do not fit into memory, systems try to repartition with another has function or they fail and default to another join algorithm.

Query optimization: Optimizer is the “brain” of a DBMS

Given a query

SELECT cid
FROM Cust c, Order o, Product p
WHERE c.cid = o.cid AND o.pid = p.pid AND p.name = 'BookA'

Many logical plans $L_1,\dots ,L_k$ correctly evaluate.

flowchart TD
a[Project c.cid] --- b[Filter p.name='bookA']
b --- c[Join o.cid = c.cid]
c --- d[Join o.pid = p.pid]
d --- e[Product]
d --- f[Order]
c --- g[Customer]

flowchart TD
a[Project c.cid] --- b[Join o.pid = p.pid]
b --- c[Join o.cid = c.cid]
b --- d[Filter p.name='bookA']
c --- e[Order]
c --- f[Customer]
d --- g[Product]

Each $L_i$ can be mapped to multiple physical plan $P_{i_1},\dots ,P_{i_k}$. The goal is to pick the best plan.

General optimization paradigms:

1. Mix of rule-based/cost-based optimization/transformations
2. Rule-based mapping

Rule-based transformations: Rules that transform Exp${}_1\to$ Exp${}_2$ based on relational algebraic laws that guarantee that Exp${}_2$ is “equivalent” to Exp${}_1$ (i.e. Exp${}_2$ always gives the same answers as Exp${}_1$, often as db-agnostic law)

R1: $G_p⇝{\bowtie }_p$

${\sigma }_{\text{User.uid = Members.uid}}(\text{User}\times \text{Members})\equiv \text{User}{\bowtie }_{\text{User.uid = Members.uid}}\equiv \text{User}\bowtie \text{Members}$

R2: Merging/Splitting consecutive $\sigma$‘s

${\sigma }_{P_1}({\sigma }_{P_2}(R))\to {\sigma }_{P_1\wedge P_2}(R)$

R3: Merging/Splitting of $\pi$‘s

${\pi }_{L_1}({\pi }_{L_2}(R))\to {\pi }_{L_1}$

R4: Pushing down filters $\sigma$:

${\sigma }_{P\wedge P_R\wedge P_S}(R{\bowtie }_{P}S)\equiv {\sigma }_{P_R}(R){\bowtie }_{P^{\prime }\wedge P}{\sigma }_{P_S}(S)$

Cannot always push $\sigma$ through any operation.

For example: Outer Join

${\sigma }_{R.A>100}(R{\text{ ⟕}}_{R.B=S.C}S)\equiv {\sigma }_{R.A>100}(R)\text{⟕}S$

${\sigma }_{S.D.>10}(R\text{ ⟕}S)=\varnothing$ but $R\text{ ⟕}{\sigma }_{S.D>10}(S)\ne \varnothing$

Lecture 19

R5: Pushing down projections

${\pi }_L({\sigma }_P(R))\equiv {\pi }_L({\sigma }_P({\pi }_{L{L}^{\prime }}(R)))$ where $L^{\prime }$ contains attributes of $R$ accessed by $p$ that are not already in $L$.

Example

${\pi }_{\text{age}}({\sigma }_{\text{pop}>0.8}(User))\equiv {\pi }_{\text{age}}({\sigma }_{\text{pop}>0.8}({\pi }_{\text{age,pop}}(User)))$

Cost-based Optimization: 3 components of cost-based optimizations.

1. An algorithm to enumerate plans (specifically different join orders)

For example, dynamic programming or greedy based algorithms.

2. Cost function (cost$(p)$): Takes a plan $P$ and outputs a number as a proxy for how expensive $P$ is

$cost(P)={\sum }_{o_p\in P}cost(o_p)$

We usually assume that $cost(S{P}_L\bowtie S{P}_R)=cost(S{P}_L)+cost(S{P}_R)+cost(S{P}_L+S{P}_R)$

3. Cardinality estimation function: Given estimated inputs to an operator, estimates the output of the operator part of any cost function.

Given each enumerated logical/physical plan, the cost is the estimate of the system for how good/bad $L_i$ is. We pick the minimum cost plan.

Naturally: cost definition is broken into cost operators.

i.e. Cost($L_i$) = ${\sum }_j$ cost($o_j\in L_i$)

Example cost metrics or components:

• # I/Os a plan will make
• # tuples that will pass through operators
• # runtime of algorithm $o_j$ is running
• Combination of above

For any reasonable metric, we need to estimate cardinality. This is a notoriously difficult problem.

Question

How do we estimate cardinality of tables processed by each op?

We need a cardinality estimation technique to estimate cardinality.

Given a database

1. $D:R_1(A_{1,1},\dots ,A_{1,m1}),\dots ,R_n(A_{n,1},\dots ,A_{n,mn})$
2. A sub-query $Q$ (a relational algebra expression). What is the $|Q|$?

E.g.:

• ${\sigma }_{name=BookA}(Product)$?
• $Product\bowtie Order$?

Widely adopted join order optimizer:

Recall:

Enumerate a logical plan space $L_1,L_2,\dots ,L_k$

A widely used optimization algorithm is to use dynamic programming CS341.

Restrictions and Assumptions:

$Q$ is a “binary chain query”, i.e. $Q$ looks like: $R_1(A_1,A_2)\bowtie R_2(A_2,A_3)\bowtie \cdots \bowtie (A_n,A_{n+1})$

Restrict to not contain cartesian products.

Thought experiment: Let $J_{1,n}^{\ast }$ be the lowest cost plan to join $R_1\bowtie R_2\bowtie \cdots \bowtie R_n$

There are several possible high-level structures $J_{1,n}^{\ast }$ can have:

Case 1: $(R_1)\bowtie (R_2\bowtie \cdots \bowtie R_n)$

Case 2: $(R_1\bowtie R_2)\bowtie (R_3\bowtie \cdots \bowtie R_n)$

$⋮$

Case $n-1$: $(R_1\bowtie \cdots \bowtie R_{n-1})\bowtie (R_n)$

Claim: If $J_{1,n}^{\ast }$ splits at $k$, then $S{P}_L$ that it uses must be the lowest cost plan to join $R_1\bowtie \cdots \bowtie R_k$ because of the “additive” nature of the cost function we are assuming. If this were not true, we could replace $S{P}_L$ with the optimal plan for $R_1\bowtie \cdots \bowtie R_k$ which is a contradiction (since $J_{1,n}^{\ast }$ is optimal).

Algorithm outline:

Base case: $J_{i,i}^{\ast }=R_i\to$ optimal plan to join $R_i$. $J_{i,i+1}^{\ast }=R_i\bowtie R_{i+1}$

Let $J_{i,j}^{\ast }$ be the optimal plan to join $R_i\bowtie R_{i+1}\bowtie \cdots \bowtie R_j$ such that $j-i=\ell -1$

$$\begin{array}{rl}& P_1=J_{i,i}^{\ast }\bowtie J_{i+1,j}^{\ast }\\ & P_2=J_{i,i+1}^{\ast }\bowtie J_{i+2,j}^{\ast }\\ & ⋮\\ & P_{j-i}=J_{i,j-i}^{\ast }\bowtie J_{j,j}^{\ast }\\ & \\ & J_{i,j}^{\ast }=P_1,P_2,\dots ,P_{j-i-1}\end{array}$$

Lecture 20

Example Statistics-based Estimation Techniques

Q: ${\sigma }_{A=v}R$

Suppose the following information is available

Size of $R$: $|R|$ and number of distinct $A$ values in $R$: ${\pi }_{A}R|$

Assumptions:

1. Values of $A$ are uniformly distributed in $R$
2. $v\in |{\pi }_{A}R|$

$|Q|\approx \frac{|R|}{|{\pi }_{A}R|}$

Selectivity factor of $(A=v)$ is $\frac{1}{|{\pi }_{A}R|}$

Example: $|Product|=1000,|{\pi }_{name}(Product)|=50$

${\sigma }_{name=BookA}Product$: $1000/50=20$

Q: ${\sigma }_{A=u\wedge B=v}R$

Additional assumption: 3. $(A=u)$ and $(B=v)$ are independent

$|Q|\approx \frac{|R|}{|{\pi }_{A}R|\cdot |{\pi }_{B}R|}$

Reduce total size by all selectivity factors. Directly derived from standard probability rules STAT230.

Q: ${\sigma }_{A\ne v}R$

$|Q|\approx |R|\cdot (1-\frac{1}{|{\pi }_{A}R|})$

Selectivity factor of $\neg p$ is (1 - selectivity factor of $p$)

Q: ${\sigma }_{A=u\vee B=v}R$

$|Q|\approx |R|\cdot (\frac{1}{|{\pi }_{A}R|}+\frac{1}{|{\pi }_{B}R|})$

NO! Tuples satisfying $(A=u)$ and $(B=v)$ are counted twice.

$|Q|\approx |R|\cdot (\frac{1}{|{\pi }_{A}R|}+\frac{1}{|{\pi }_{B}R|}-\frac{1}{|{\pi }_{A}R||{\pi }_{B}R|})$

${\sigma }_{A>u}R$

Case 1: Suppose the DBMS knew actual projection values:

Then range queries are a generalization of ${\sigma }_{A=u\vee A=v}R$

${\sigma }_{A>u}R=|Q|\approx |R|\cdot (\frac{|\#vals>u|}{|{\pi }_{A}R|})$

Case 2: We don’t know the actual values.

Then there is not enough information, we can just pick a magic constant, e.g., $|Q|\approx |R|\cdot \frac{1}{3}$

With more information:

• Largest $R.A$ value: $high(R.A)$
• Smallest $R.A$ value: $low(R.A)$

$|Q|\approx |R|\cdot \frac{high(R.A)-v}{high(R.A)-low(R.A)}$

In practice, sometimes the second highest and lowest are used.

Q: $R(A,B)\bowtie S(A,C)$

Assumption: Containment of value sets:

Every tuple in the smaller relation (one with fewer distinct values for the join attribute) joins with a tuple in the other relation.

That is, if $|p{i}_{A}R|\le |{\pi }_{A}S|$ then ${\pi }_{A}R\subseteq {\pi }_{A}S$

Not true in general, but holds in the common case of foreign key joins.

$|Q|\approx \frac{|R|\cdot |S|}{\max (|{\pi }_{A}R|,|{\pi }_{A}S|)}$

Transactions: Mechanism to obtain separate guarantees from the DBMS.

1. Atomicity and Durability: all-or-nothing visibility and durability guarantee when users want to modify multiple data elements at the same time.

Example

Bank money transfer from account1 to account2

UPDATE Accounts SET balance=balance-100
WHERE aID = 'acc1'
 
UPDATE Accounts SET balance=balance+100
WHERE aID = 'acc2'
 
SELECT * FROM Accounts
WHERE aID='acc1' or aID='acc2'

We want to make sure either both of them happened, or none of them happened.

BEGIN TRANSACTION
UPDATE Accounts SET balance=balance-100
WHERE aID = 'acc1'
 
UPDATE Accounts SET balance=balance+100
WHERE aID = 'acc2'
COMMIT TRANSACTION
--now an atomic unit
 
SELECT * FROM Accounts
WHERE aID='acc1' or aID='acc2'

Can need the same guarantee even if you issue a single SQL statement

UPDATE Customer
SET membership='Gold'
WHERE CID IN (SELECT *
			FROM Orders
			WHERE price >= 20)
 
-- don't want to favour some customers

2. Isolation under concurrency: users want two features when developing apps that will run concurrently on the same database. When there are multiple transactions running, $T_1,\dots T_k$, we want the database state at the end to be “equivalent” to as if $T_1,\dots T_k$ ran in some serial order.
   1. They want “genuine” concurrency. They don’t want other apps blocking them
   2. They want to write apps “under the illusion” that their app is the only app accessing the database

User 1

UPDATE balance=balance-100
 
UPDATE balance=balance+100

User 2

SELECT *
FROM Accts
WHERE aID = 'acct1' or aid = 'acct2'

aID	bal
acc1	1000
acc2	500

or

aid	bal
acc1	900
acc2	600

A simple model of transactions.

Simplifying assumptions:

• No failures or aborts
• Just updates (no inserts or deletes)
• No SQL $\to$ simple read and write operations
• Concurrency is achieved by context switching CS350.

Ingredients:

• DB consists of data items ($x,y,z$) that are stored on disk (source of truth)
• 2 operations:
  • read($x$): $T$ copies the disk version into a local buffer.
  • write($x$): $T$ writes its local copy back to disk
• Before $T$ writes $x$, we will assume that it has an arbitrary computation on $x$ before writing $x$ (and we cannot predict this value)

Note: $T$ can write to $x$ without reading.

$T_1$
read(x)
x=100
read(y)
x=y-50
write(x)

We will omit $x=100$ and $x=y-50$.

This table becomes read($x$), read($y$), write($x$) $\to$ $r_1(x),r_1(y),w_1(x)$

Execution history of a set of transactions $T_1,\dots T_k$

Example

$T_1:w_1(x),w_1(y),T_2:r_2(x),r_2(y)$

$T_1$	$T_2$
$w_1(x)$
	$r_2(x)$
$w_1(y)$
	$r_2(y)$

$w_1(x),r_2(x),w_1(y),r_2(y)$

The above is a possible interleaved ordering of the ops of $T_1,\dots T_k$ without re-ordering any ops within any $T_i$

$T_1$	$T_2$
$w_1(x)$
$w_1(y)$
	$r_1(x)$
	$r_2(y)$

$w_1(x),w_1(y),r_2(x),r_2(y)$

$T_1$	$T_2$
$w_1(y)$
	$r_2(x)$
$w_1(x)$
	$r_2(y)$

This is not valid.

Question

Given an execution history $H$, is it “equivalent” to a serial execution history $H_S$?

Lecture 21

Possible definitions of equivalence:

Option 1: If the record in $H$ and $H^{\prime }$ are guaranteed to be the same and the order of the writes to any data item in $H$ and $H^{\prime }$ are also the same.

Option 2: Same read guarantee, but only the final writes need to be the same.

Option 3: Only the final writes are the same

We will go with option 1.

Serial history: No interleaving of operations from different transactions

Initially $x=3,y=1$

$H_A$ (not serial since operations interleave between transactions)

$T_1$	$T_2$
$w_1(x)$ (x=4)
	$r_2(x)$ (x=4)
$w_1(y)$ (y=5)
	$r_2(y)$ (y=5)

$H_b$ (serial)

$T_1$	$T_2$
$w_1(x)$ (x=4)
$w_1(y)$ (y=5)
	$r_2(x)$ (x=4)
	$r_2(y)$ (y=5)

$H_c$

$T_1$	$T_2$
$w_1(x)$
	$r_2(x)$
	$r_2(y)$
$w_1(y)$

$H$ is equivalent to $H^{\prime }$ if values read by each $T_i$ in $H$ and $H^{\prime }$ is the same, and the order of write operations on each item is the same.

Conflict: Two operations $o_i$ and $o_j\in H$ conflict if

1. $o_i$, $o_j$ belong to different transactions $T_i,T_j$
2. $o_i$ and $o_j$ operate on the same data item
3. One of them is a write

Therefore there are two types of conflicts: Read-write, and write-write

Conflict equivalence: Two instances $H$ and $H^{\prime }$ are “conflict equivalent” if

1. They contain the same transactions
2. The ordering of each pair of conflicting operations is the same in $H$ and $H^{\prime }$

In $H_A$, $w_1(x)$ and $r_2(x)$ conflict, and $w_1(y)$ and $r_2(y)$ conflict.

	$H_a$	$H_b$
$w_1(x),r_2(x)$	$<$	$<$
$w_2(y),r_2(y)$	$<$	$<$

$⟹H_a$ is conflict equivalent to $H_b$. Thus, $H_a$ is conflict serializable (because they operate over the same set of transactions and all conflicting pairs are in the same order).

Theorem/Intuition

If $H$ and $H^{\prime }$ are conflict equivalent, then we can take $H$ and through a sequence of swaps of consecutive non-conflicting operations, make it exactly equal to $H^{\prime }$

$H$ and $H^{\prime }$

	$T_1$	$T_2$	$T_1$	$T_2$
$t_0$		$x$	$x$
$t_1$	$x$		$x$
$t_2$		$x$		$x$
$⋮$	$x$

	$T_1$	$T_2$	$T_1$	$T_2$
$t_0$	$x$	$\downarrow$	$x$
$t_1$	$\uparrow$	$x$	$x$
$t_2$		$x$		$x$
$⋮$	$x$

Conflict serializability: An execution history $H$ is conflict serializable if $H$ is conflict equivalent to some serial execution of the same transactions in $H$.

Question

How to check if an execution history is serializable?

Check that it is conflict equivalent to any serial executions.

$H_b^{\prime }$

$T_1$	$T_2$
	$r_2(x)$
	$r_2(y)$
$w_1(x)$
$w_1(y)$

	$H_c$	$H_b$	$H_b^{\prime }$
$w_1(x)r_2(x)$	$<$	$<$	$>$
$w_1(y)r_2(y)$	$>$	$<$	$>$

$H_c$ is not conflict serializable. This table is an easy way to check serializability of the number of transactions are small.

More practical tests of (conflict) serializability: Serialization graph

$S{G}_H(V,E)$:

• $V=\{T\text{ s.t. }T\in H\}$
• $E:\{T_i\to T_j\text{ if }\exists o_i\text{ and }{o}_j\text{ s.t. }{o}_i\in T_i\text{ and }{o}_j\in T_j\text{ and }{o}_i,o_j\text{ conflict and }{o}_i<o_j\}$

$S{G}_{H_a}:T_1\to T_2$

$S{G}_{H_c}:T_1\to T_2$ and $T_2\to T_1$

Intuition: Given $S{G}_H$, if $H$ is conflict serializable, and $T_i\to T_j$ exists in $S{G}_H$, then in that serial order that $H$ is equivalent to, $T_i$ must execute before $T_j$.

Theorem

If $S{G}_H$ is acyclic, then $H$ is (conflict) serializable because $H$ can be made equivalent to any topological order of $S{G}_H$

Question

How does a system ensure that it generates serializable execution histories?

Locking CS350.

Rule:

• To read a data item $x$, a transaction must update a shared lock $S(x)$ on $x$
• To write to $x$, transactions need to obtain an exclusive lock lock-$X(x)$

	$S$	$X$
$S$	Y	N
$X$	N	N

Naïve locking: grab a lock on $x$, right before the first operation on $x$, and release immediately after the last operation.

Fail

This does not work.

$T_1$	$T_2$
acquire lock $x$
$w_2(x)$
unlock $x$
	acquire lock $x$
	$r_2(x)$
	unlock $x$
	acquire lock $y$
	$r_2(y)$
	unlock $y$
acquire lock $y$
$w_1(y)$
unlock $y$

Wrapping each operation with a lock does not solve our issue.

2PL: All lock requests of $T_i$ must happen before all unlock requests of $T_i$.

Theorem

Strict 2 Phase Locking guarantees that if there are no deadlocks, then the generated execution history is serializable.

Strict phase locking $⟹$ all exclusive lock releases happen at commit time.

$T_1$	$T_2$
lock $X(x)$
$w_1(x)$
lock(y)	lock(x) - blocked
$w_2(y)$
unlock(x)
unlock(y)
	$r_2(x)$
	lock(y)
	$r_2(y)$
	commit
commit

$T_1$	$T_2$
lock $X(x)$
$r_1(x)$
$w_1(x)$
	lock $S(y)$
	$r_2(y)$
	lock $X(x)\leftarrow$ blocked
lock $X(y)\leftarrow$ blocked

This is a deadlock.

Lecture 22

Guaranteeing serializability has performance overheads.

Question

Why does 2PL lead to serializable exceution histories?

Claim: $H$ is conflict equivalent to executing the transactions serially in the order of the lock points of transactions.

Why? For the operations of $T_1$, before the lock part of $T_1$, any such operation of $T_1$ cannot conflict with ops from $T_2$ or $T_3$ because all transactions are in their locking phases, so $T_2$ and $T_3$ would have blocked $T_1$‘s operations.

For operations of $T_1$ in unlock phase, similar argument, that any operation $o$ of $T_1$ in the unlock phase holds the necessary lock needed by $o$.

Another observation: The claim about 2PL is not that every serializable history can be generated by some execution of 2PL.

$H_a$

$T_1$	$T_2$
lock-$X(x)$
$w(x)$
	lock-$S(x)$ (blocked)
	$r(x)$
$w(y)$
	$r(y)$

SQL Transaction isolation levels:

Serializability is the strongest guarantee a DBMS can give. This strength comes at a performance cost.

SQL offers weaker isolation levels for transactions:

SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;

Every BEGIN TRANSACTION command begins at repeatable read level.

Isolation Levels in SQL Standard
Read Uncommitted
Read Committed
Repeatable Read
Serializable

As we go down, there are stronger isolation guarantees. As we go up, performance goes up.

Isolation levels are per transactions.

Question

What does it mean for $T_j$ to be serializable/read uncommitted etc?

Each transaction $T_i$ gets a per transaction guarantee for the read operations it makes

For serializability in particular: You can assume the following happened. If $T_i$ is set to serializable, it means some set of transactions executed before $T_i$ (and not necessarily in a serializable manner) and left the database in a state $D_i$, then you can assume as a user that $T_i$ ran complete in isolation.

$D_{<i}{⟶}_{T_i}{D}_i$

READ UNCOMITTED: Can read dirty data, item written by an uncommitted transactions.

READ COMMITTED: Does not read dirty data, but reads of same item may not be repeatable (if commit happens in $T_1$ and $T_2$ transaction reads same again)

REPEATABLE READ: No unrepeatable reads, but phantom reads may appear (insert/deletion commit in $T_1$, same queries in $T_2$ may differ).

SERIALIZABLE: No dirty reads, every read is repeatable, no scan of any relation can be phantom.

Atomicity $\to$ “nothing” behaviour if a transaction fails or roll back

Consistency $\to$ if every transaction $T_i$ is written such that if $D$ is a consistent database then $D{⟶}_{T_i}{D}^{\prime }$ leads to a consistent $D^{\prime }$, then serializability guarantees that $D$ remains consistent under concurrency.

Isolation $\to$ serializability is supported in the system.

Durability $\to$ “all” behaviour if a transactions commits successfully, then all operations in the transaction will be reflected in the database even if the system crashes.

Atomicity and Durability are achieved through logging and handled by recovery manager.

$T_1$
$w(x,20)$
abort

Disk
$x=10\to 20$

Log
<$T_1$, start>
<$T_1,x,10,20$>
<$T_1$ commit/abort>

Need a log to bookkeep the changes that transactions are making (need mechanism to undo operation). Logs have to be conservative i.e. write-ahead, before data items are changed on disk.

Lecture 23

Write-ahead logging: Log of any update on $x$ must be written before the update on $x$ on disk

Log Records
<$T_i$ start>
(Update records) <$T_i,x,$ prevVal, newVal>
(Compensation record) <$T_i,x$, oldval>
<$T_i$, abort/commit>

Log
<$T_1$, start>
<$T_1,A$, 800, 700
<$T_2$, start>
<$T_2,c$, 1000, 1200>
CRASH

Disk
A	800 700
C	1000

Undo Algorithm: For any data item $x$, that has been updated by an uncommitted transaction, undo the updates.

Log
<$T_1$, start>
<$T_1$, B, 50, 60>
<$T_1$, commit>
CRASH

Disk
B	50 60

Force-policy: any update happens directly to disk version of data items.

No-Force policy: DBMS first writes changes to in-mem copy of pages, and later to disk.

Let $L$ be the set of uncommitted and aborted transactions.

Scan log in reverse order from the end

for each $\ell \in$ log in reverse order:

if $\ell$ is an update record <$T_i,x$, prevVal, newVal> such that $T_i\in L$,

1. Write a compensation record: <$T_i,x,$ prevVal>
2. Update $x$ to prevVal on disk

else if $\ell$ is <$T_i$, start> and $T_i\in L$

1. Write <$T_i$, abort> to the log
2. Remove $T_i$ from $L$

Log
<$T_1$, start>
<$T_1,A,800,700$>
<$T_2$, start>
<$T_2,c,1000,1200$>
CRASH
<$T,A,700$>
<$T_2,C,1000$>
<$T_2$, abort>
<$T_1,A$, 800>
<$T_1$, abort>

Disk
A	800 700 600 700 800
C	1000 1000

Redo must happen first in the forward direction. Then we do undo in the backward direction.

Checkpointing shortens the amount of log that needs to be undone or redone when a failure occurs.

Courses to take after CS348

• CS448 $\to$ database implementation (programming heavy)
• CS451 $\to$ more on data systems

Question

What is RDF?

First, motivation.

Example

Amazon product catalogue

An apple watch is a smart watch, watch, wearable, electronic.

A normal watch is a wearable and watch, but not electronic or smart.

We need a more object oriented/graph-based model. This will include type hierarchies.

RDF Component 1: Resources and International Resource Identifiers (IRI’s)

Resources are objects to represent entities, types and properties.

All objects have an IRI.

RDF Component 3: Triples

Subject, verb, predicate, object, sentences

(Levis511)(is a type of)(LooseJeans) follows the format: subject verb object

<gc: Levis511, rdf:type, gc:LooseJeans>

Everything is a triple in RDF.

We can model irregular properties across resources (good flexibility).

SELECT ?p
WHERE {
	?p rdf:type gc:Jeans
}

Inference rule: $(x$ rdf:type $A)$ and $(A$ rdf: subclass of $B)$ $⟹(x$ rdf:type $B)$

OWL inference example

select ?m
where {
	gc:Levis511 md:merchant ?m
}

https://arxiv.org/abs/2308.04445