Databases
Relational algebra 1
ERD 3
Normalisation 4
SQL 7
Indexing 10
Transaction processing 11
Concurrency 11
Recovery 13
Two-Phase-Commitment Protocol 16
Query processing 19
EXtended RA 19
Access strategy 20
,Relational algebra
Super key A set of attributes that uniquely defines every tuple of the table
Candidate key A minimal super key; Super key of which no proper subset exists that itself is
also a super key
Primary key A specific candidate key, usually one attribute in the form of a number
Foreign key Reference to the primary key of one table in another table
Unary operators
- σ, selection: reduces the number of tuples in the table
- π, projection: reduces the number of attributes in the table
- composition: combines multiple operations
- :=, assignment: assigns an expression (a table) to a name T ( T := <expr> )
- renaming attributes: also renames attributes ( T[A1, … , An] := <expr> )
- ρ, rename: renames the expression to a name T ( ρ(T)(<expr>) )
- Also rename attributes: ρ(T, A1, … , An)(<expr>)
Binary operators
- ∪, union: combines two tables (duplicates are eliminated)
- -, difference: deletes elements from the left operand that also occur in the right operand
- ∩, intersection: retains only the elements that occur in both operands
- ×, cartesian product: all possible combinations of tuples from both operands
- Number of combinations is number of tuples on the left × number of tuples right
R S R×S
A B C D A B C D
a 11 b 25 → a 11 b 25
b 43 c 41 a 11 c 41
b 43 b 25
b 43 c 41
- ⨝θ, theta-join: all possible combinations of tuples under condition theta (θ)
R S R ⨝θ S
A B C D A B C D
a 11 b 55 → b 43 b 21
b 43 c 31 c 37 c 31
c 37 b 21
θ : (R.A = S.C) ∧ (R.B > S.D)
1
, - ⨝, natural join: all possible combinations of tuples that form a match on some attribute
- Order of operands doesn’t matter
- If there are no matching attributes, natural join is equivalent to cartesian product
R S R⨝S
A B A D A B D
a 11 b 55 → b 43 55
b 43 c 31 b 43 21
c 37 b 21 c 37 31
d 17
- ÷, division: all values under attribute A that are associated with at least the values from
the other operand under attribute B
R S R÷S
A B B A
1 1 1 → 1
1 3 3 8
2 2
2 3
8 1
8 3
8 7
Examples
- Names of the readers who loaned at least one Dickens book:
πname(Reader ⨝ Loan ⨝ (σauthor = “Dickens” Book))
- Names of the readers who have never loaned a Dickens:
πname(Reader) - πname(Reader ⨝ Loan ⨝ (σauthor = “Dickens” Book))
- Names of the readers who have loaned only Dickens books:
πname(Reader) - πname(Reader ⨝ Loan ⨝ (σauthor != “Dickens” Book))
- Names of the readers who have loaned all Dickens books:
πname(Reader ⨝ (πrid, bid(Loan) ÷ πbid(σauthor = “Dickens” Book)))
- Assign a table to a variable with and without changing the attribute names:
OldMovies := πid, title(σyear < 1930 Movie)
OldMovies[omid, omtitle] := πid, title(σyear < 1930 Movie)
- Renaming a variable in-line:
… ⨝ ρ(OldMovies, omid, omtitle)(πid, title(σyear < 1930 Movie))
2
Relational algebra 1
ERD 3
Normalisation 4
SQL 7
Indexing 10
Transaction processing 11
Concurrency 11
Recovery 13
Two-Phase-Commitment Protocol 16
Query processing 19
EXtended RA 19
Access strategy 20
,Relational algebra
Super key A set of attributes that uniquely defines every tuple of the table
Candidate key A minimal super key; Super key of which no proper subset exists that itself is
also a super key
Primary key A specific candidate key, usually one attribute in the form of a number
Foreign key Reference to the primary key of one table in another table
Unary operators
- σ, selection: reduces the number of tuples in the table
- π, projection: reduces the number of attributes in the table
- composition: combines multiple operations
- :=, assignment: assigns an expression (a table) to a name T ( T := <expr> )
- renaming attributes: also renames attributes ( T[A1, … , An] := <expr> )
- ρ, rename: renames the expression to a name T ( ρ(T)(<expr>) )
- Also rename attributes: ρ(T, A1, … , An)(<expr>)
Binary operators
- ∪, union: combines two tables (duplicates are eliminated)
- -, difference: deletes elements from the left operand that also occur in the right operand
- ∩, intersection: retains only the elements that occur in both operands
- ×, cartesian product: all possible combinations of tuples from both operands
- Number of combinations is number of tuples on the left × number of tuples right
R S R×S
A B C D A B C D
a 11 b 25 → a 11 b 25
b 43 c 41 a 11 c 41
b 43 b 25
b 43 c 41
- ⨝θ, theta-join: all possible combinations of tuples under condition theta (θ)
R S R ⨝θ S
A B C D A B C D
a 11 b 55 → b 43 b 21
b 43 c 31 c 37 c 31
c 37 b 21
θ : (R.A = S.C) ∧ (R.B > S.D)
1
, - ⨝, natural join: all possible combinations of tuples that form a match on some attribute
- Order of operands doesn’t matter
- If there are no matching attributes, natural join is equivalent to cartesian product
R S R⨝S
A B A D A B D
a 11 b 55 → b 43 55
b 43 c 31 b 43 21
c 37 b 21 c 37 31
d 17
- ÷, division: all values under attribute A that are associated with at least the values from
the other operand under attribute B
R S R÷S
A B B A
1 1 1 → 1
1 3 3 8
2 2
2 3
8 1
8 3
8 7
Examples
- Names of the readers who loaned at least one Dickens book:
πname(Reader ⨝ Loan ⨝ (σauthor = “Dickens” Book))
- Names of the readers who have never loaned a Dickens:
πname(Reader) - πname(Reader ⨝ Loan ⨝ (σauthor = “Dickens” Book))
- Names of the readers who have loaned only Dickens books:
πname(Reader) - πname(Reader ⨝ Loan ⨝ (σauthor != “Dickens” Book))
- Names of the readers who have loaned all Dickens books:
πname(Reader ⨝ (πrid, bid(Loan) ÷ πbid(σauthor = “Dickens” Book)))
- Assign a table to a variable with and without changing the attribute names:
OldMovies := πid, title(σyear < 1930 Movie)
OldMovies[omid, omtitle] := πid, title(σyear < 1930 Movie)
- Renaming a variable in-line:
… ⨝ ρ(OldMovies, omid, omtitle)(πid, title(σyear < 1930 Movie))
2
