1/54
Looks like no tags are added yet.
Selection Operator
R1 := σC (R2) (Sigma)
Projection Operator
R1 := πL(R2) (Pi)
Natural Join Operator
R3 := R1 ⋈ R2 (Bowtie)
Theta Join Operator
R3 := R1 ⋈C R2 (Bowtie + condition)
Bag algebra differs from set algebra because it allows ____
Duplicates
Union in Bag Algebra
Take the “sum” of times an entry appears in result

Intersection in Bag Algebra
Take the minimum amount of times an entry appears in either set

Difference in Bag Algebra
#Occurences in A - #Occurences in B

Duplicate Removal Operator (Bag Algebra)
δ(R) (Delta)
Sort Tuples to List Operator (Bag Algebra)
τA1,A2..(R) (Tau)
Important! Ties are broken by the order of columns listed after tau
Extended Projection Operator (Bag Algebra)
πA1,A2..(R) (Pi)

Grouping Operator (Bag Algebra)
γA1,A2..(R) (Gamma)
Can use SUM, AVG, COUNT, MIN, MAX

Natural Outer Join (Bag Algebra)
An outer join which includes nonmatching / dangling tuples as well

Theta Outer Join (Bag Algebra)
A theta join which includes nonmatching / dangling tuples (after joining matches)

How outer joins / theta outer joins notated in comparison to their set algebra counterparts
Dot above the bowtie:]
Update Anomaly
Updating certain records in a DB while failing to update other related records, leading to conflicts
Deletion Anomaly
The potential to lose information by deleting a tuple / value not stored anywhere else in a DB
Definition of a Functional Dependency
If two tuples of R agree on attributes A1, A2 … An, they must agree on B1, B2, … Bn
Attribute A determines B denoted A -> B (Leftside -> Rightside)
Armstrong Axioms of a Functional Dependency
Reflexivity
Augmentation
Transitivity
rat?
Is the Superkey Valid?
Relation Home = {address, owner, residents, floors, bedrooms, bathrooms, has_backyard, has_pool}
Key = {address, owner}
Superkey = {address, owner, bedrooms, bathrooms}
True
Is the Superkey Valid?
Relation Home = {address, owner, residents, floors, bedrooms, bathrooms, has_backyard, has_pool}
Key = {address, owner}
Superkey = {owner, residents, floors}
False
Is the Superkey Valid?
Relation Gamer = {username, platform, favorite_game, winrate, showers, peripherals_broken}
Key = {username, platform}
Superkey = {favorite_game, peripherals_broken}
False
Is the Superkey Valid?
Relation Gamer = {username, platform, favorite_game, winrate, showers peripherals_broken}
Key = {username, platform}
Superkey = {username, platform, favorite_game, winrate, showers, peripherals_broken}
True
Transitivity Rule of Functional Dependencies
If A → B, and B → C, then A → C
(A functionally determines B, B functionally determines C, thus A functionally determines C)
Augmentation Rule of Functional Dependencies
If A → B, then AX → BX for any set of attributes defined under X
Reflexivity Rule of Functional Dependencies
If B is a subset of A (B ⊆ A) then A → B
Splitting Rule of Functional Dependencies
If A → BC, we may say
A → B
A → C
Combining Rule of Functional Dependencies
If A → B and A → C, we may say
A → BC
Trivial Functional Dependency
The right side (determined) attributes are a subset of the left side (determining) attributes
Is the functional dependency trivial?
{A, Z, F} → A
True
Is the functional dependency trivial?
{A, Z, F} → C
False
Algorithmic Steps to Calculate Closure
Given set of FD, and value X, add X+ to closure of X
For each set of attributes X, compute X+
Add X→A for all A in X+ - X
Drop XY → A whenever we discover X → A
XY → A follow from X → A in any projection
Use only FD's involving projected attributes

Basis in Functional Dependencies
The minimum set of Functional Dependencies for a given relation.
Minimal basis for functional dependencies satisfies which attributes
All FD's in B have singleton right sides
Any FD removed from B, result is no longer a basis
Any FD in B, we remove one+ attributes from left side of F, result is no longer a basis

1NF (Normal Form 1) Requires
Atomic values (each cell contains only one value)
No repeating groups
No repeating tuples
2NF (Normal Form 2) Requires
Holding previous normal form requirements
Having no partial dependencies (all non-key attributes must depend on a primary key)
If X → Y, X should be entire key
3NF (Normal Form 3) Requires
Holding previous normal form requirements
Having no transitive dependencies: non-key attributes cannot depend on other non-key attributes, must depend on primary key
If X → Y, X should be a superkey OR prime attribute
Boyce Codd Normal Form (BCNF) Requires
For any X → Y, X is a superkey
Utilizes recursive algorithm to decompose
Recall the ACID properties of DBMS / transactions
Atomicity
Concurrency
Isolation
Durability
Atomicity
All or nothing transactions, every step passes or none do
Consistency
Each client and transaction must ensure all constraints hold when a transaction begins AND all constraints hold when a transaction ends
Isolation
Concurrent transactions should not interfere with each other
Durability
A transactions changes are permanent, and if interrupted they may be rolled back and started from the beginning
Order of isolation levels (least → most isoalted)
Read uncommitted
Read committed
Repeatable read
Serializable
Additionally, top to bottom:
Better → Worse performance, Lower → Higher consistency, Lower → Higher overhead
Dirty read
A data item can be written by uncommitted transactions (i.e., reading BEFORE external transaction modifying the read commits)
Non-Repeatable Read
Reading a tuple multiple times and getting different values due to a concurrent committ
Isolation levels are per ____
Transaction
Read Uncommitted Isolation Level
Permit dirty reads
Permit non-repeatable reads
Do NOT ensure global serialization

Read Committed Isolation Level
Do NOT permit dirty reads
Permit non-repeatable reads
Do NOT ensure global serialization

Repeatable Read Isolation Level
If a value is read more than once, ALWAYS use the same value as the initial read (Prevent non-repeatable read)
Do NOT permit dirty reads
Do NOT ensure global serialization
Permit phantom tuples

Serializable Isolation Level
Do NOT permit dirty reads
Ensure global serialization
Do NOT permit non-repeatable reads
Concurrent transactions are effectively the same as if they were ordered
Phantom Tuples
Tuples emerging during a transaction’s execution
Isolation levels that permit dirty reads
Read uncommitted
Isolation levels that permit non-repeatable reads
Read uncommitted, read committed
Isolation levels that permit phantom tuples
Read uncommitted, read committed, repeatable read