Definition
Relational algebra is the set of operations on tables T = ( C , D , R ) T = (C, D, R) T = ( C , D , R ) Relational Model that an RDBMS implements internally. Each operation takes one or two tables and returns a single table, so operations compose. The three basic operations, for T T T k k k
Projection Π c o l s , d i s t i n c t ( T ) \Pi_{\mathit{cols},\,\mathit{distinct}}(T) Π cols , distinct ( T ) c o l s = ( j 1 , … , j m ) \mathit{cols} = (j_1, \ldots, j_m) cols = ( j 1 , … , j m ) j i ∈ { 1 , … , k } j_i \in \{1, \ldots, k\} j i ∈ { 1 , … , k } d i s t i n c t ∈ { true , false } \mathit{distinct} \in \{\text{true}, \text{false}\} distinct ∈ { true , false } C ′ = ( c j 1 , … , c j m ) C' = (c_{j_1}, \ldots, c_{j_m}) C ′ = ( c j 1 , … , c j m ) D ′ = ( D j 1 , … , D j m ) D' = (D_{j_1}, \ldots, D_{j_m}) D ′ = ( D j 1 , … , D j m ) R ′ = { ( r j 1 , … , r j m ) : r ∈ R } R' = \{(r_{j_1}, \ldots, r_{j_m}) : r \in R\} R ′ = {( r j 1 , … , r j m ) : r ∈ R } d i s t i n c t \mathit{distinct} distinct R ′ R' R ′ Selection σ φ ( T ) \sigma_\varphi(T) σ φ ( T ) φ : D 1 × ⋯ × D k → { true , false } \varphi : D_1 \times \dots \times D_k \to \{\text{true}, \text{false}\} φ : D 1 × ⋯ × D k → { true , false } ( C , D , { r ∈ R : φ ( r ) } ) (C, D, \{r \in R : \varphi(r)\}) ( C , D , { r ∈ R : φ ( r )}) Cartesian Product T 1 × T 2 T_1 \times T_2 T 1 × T 2 ( ( C 1 , C 2 ) , ( D 1 , D 2 ) , { ( r 1 , r 2 ) : r 1 ∈ R 1 , r 2 ∈ R 2 } ) ((C_1, C_2), (D_1, D_2), \{(r_1, r_2) : r_1 \in R_1, r_2 \in R_2\}) (( C 1 , C 2 ) , ( D 1 , D 2 ) , {( r 1 , r 2 ) : r 1 ∈ R 1 , r 2 ∈ R 2 }) Here r [ j ] = r j r[j] = r_j r [ j ] = r j r r r j j j ( r 1 , r 2 ) (r_1, r_2) ( r 1 , r 2 )
Properties# SQL ↔ operations# Every query SELECT cols FROM T1, …, Tk WHERE φ equals Π c o l s ( σ φ ( T 1 × ⋯ × T k ) ) \Pi_{\mathit{cols}}(\sigma_\varphi(T_1 \times \dots \times T_k)) Π cols ( σ φ ( T 1 × ⋯ × T k ))
SQL Operation SELECT [DISTINCT] colsprojection Π c o l s , d i s t i n c t \Pi_{\mathit{cols},\,\mathit{distinct}} Π cols , distinct WHERE φselection σ φ \sigma_\varphi σ φ FROM T1, T2Cartesian product T 1 × T 2 T_1 \times T_2 T 1 × T 2 FROM T1 JOIN T2 ON T1.a = T2.bJoin T 1 ⋈ a , b T 2 T_1 \bowtie_{a,b} T_2 T 1 ⋈ a , b T 2 GROUP BY … HAVING …Grouping group-by (VL05)ORDER BY, LIMITOrdering (by example only, VL05)
A sequence of operations can be written as a list of assignments, as one nested expression, or as a tree (leaves = input tables, inner nodes = operations, root = result); see Query Plan .
Derived operation: natural join# T 1 ⋈ T 2 = Π shared cols once ( σ T 1 . c = T 2 . c ∀ c ∈ C 1 ∩ C 2 ( T 1 × T 2 ) ) T_1 \bowtie T_2 = \Pi_{\text{shared cols once}}\big(\sigma_{T_1.c = T_2.c\ \forall c \in C_1 \cap C_2}(T_1 \times T_2)\big) T 1 ⋈ T 2 = Π shared cols once ( σ T 1 . c = T 2 . c ∀ c ∈ C 1 ∩ C 2 ( T 1 × T 2 ) ) More generally, a Join is a selection on a Cartesian product that is computed without materialising the product (hash join, Merge Join ).
Cost and size estimates# Let T T T n n n k k k T i T_i T i n i n_i n i k i k_i k i k ′ = ∣ c o l s ∣ k' = |\mathit{cols}| k ′ = ∣ cols ∣
Operation cost rows cols Π c o l s , d i s t i n c t ( T ) \Pi_{\mathit{cols},\,\mathit{distinct}}(T) Π cols , distinct ( T ) ∼ n ⋅ k ′ \sim n \cdot k' ∼ n ⋅ k ′ ∼ n \sim n ∼ n k ′ k' k ′ σ φ ( T ) \sigma_\varphi(T) σ φ ( T ) ∼ n ⋅ k \sim n \cdot k ∼ n ⋅ k ∼ n / 2 \sim n/2 ∼ n /2 k k k T 1 × T 2 T_1 \times T_2 T 1 × T 2 ∼ n 1 ⋅ n 2 ⋅ ( k 1 + k 2 ) \sim n_1 \cdot n_2 \cdot (k_1 + k_2) ∼ n 1 ⋅ n 2 ⋅ ( k 1 + k 2 ) n 1 ⋅ n 2 n_1 \cdot n_2 n 1 ⋅ n 2 k 1 + k 2 k_1 + k_2 k 1 + k 2
The cost is proportional to the number of values read or written. Assumptions: tables stored in row order; φ \varphi φ
! Total cost of a sequence
The cost of a sequence is the sum over all its operations, each computed from the estimated size of its input. Propagate row and column estimates from the leaves up the tree.
Equivalences used in query planning# Push selections down: σ φ 1 ∧ φ 2 ( T 1 × T 2 ) ≡ σ φ 1 ( T 1 ) × σ φ 2 ( T 2 ) \sigma_{\varphi_1 \wedge \varphi_2}(T_1 \times T_2) \equiv \sigma_{\varphi_1}(T_1) \times \sigma_{\varphi_2}(T_2) σ φ 1 ∧ φ 2 ( T 1 × T 2 ) ≡ σ φ 1 ( T 1 ) × σ φ 2 ( T 2 ) φ i \varphi_i φ i T i T_i T i T 1 T_1 T 1 n 1 n 2 ( k 1 + k 2 ) n_1 n_2 (k_1 + k_2) n 1 n 2 ( k 1 + k 2 ) Project early: dropping unneeded columns before a product reduces k 1 + k 2 k_1 + k_2 k 1 + k 2 Order of products: × \times × Products → joins: σ r [ a ] = r [ b ] ( T 1 × T 2 ) ≡ T 1 ⋈ a , b T 2 \sigma_{r[a] = r[b]}(T_1 \times T_2) \equiv T_1 \bowtie_{a,b} T_2 σ r [ a ] = r [ b ] ( T 1 × T 2 ) ≡ T 1 ⋈ a , b T 2 Note Why select first helps
If a selection reduces T 1 T_1 T 1 n 1 n_1 n 1 n 1 / 2 n_1/2 n 1 /2 ( n 1 / 2 ) ⋅ n 2 ⋅ ( k 1 + k 2 ) (n_1/2) \cdot n_2 \cdot (k_1 + k_2) ( n 1 /2 ) ⋅ n 2 ⋅ ( k 1 + k 2 ) n 1 ⋅ n 2 ⋅ ( k 1 + k 2 ) n_1 \cdot n_2 \cdot (k_1 + k_2) n 1 ⋅ n 2 ⋅ ( k 1 + k 2 ) n 1 k 1 n_1 k_1 n 1 k 1
Example# Example Projection and selection (Slides 04, p. 10–12)
people(id, first, last) with rows (Q36301, Anne, Hathaway), (Q237251, Anne, Hathaway), (Q106514, River, Phoenix), (Q185140, Joaquin, Phoenix).
SELECT DISTINCT first, last FROM people = Π ( 2 , 3 ) , true ( people ) = \Pi_{(2,3),\,\text{true}}(\text{people}) = Π ( 2 , 3 ) , true ( people ) SELECT * FROM people WHERE first = 'Anne' = σ r [ 2 ] = "Anne" ( people ) = \sigma_{r[2] = \text{"Anne"}}(\text{people}) = σ r [ 2 ] = "Anne" ( people ) Example Cost comparison (WS 23/24, Task 2.2)
A A A B B B
Plan 1 (select first): σ ( A ) , σ ( B ) , × , Π \sigma(A), \sigma(B), \times, \Pi σ ( A ) , σ ( B ) , × , Π
10 ⋅ 4 ⏟ 40 + 20 ⋅ 2 ⏟ 40 + 5 ⋅ 10 ⋅ 6 ⏟ 300 + 50 ⋅ 6 ⏟ 300 = 680 \underbrace{10 \cdot 4}_{40} + \underbrace{20 \cdot 2}_{40} + \underbrace{5 \cdot 10 \cdot 6}_{300} + \underbrace{50 \cdot 6}_{300} = 680 40 10 ⋅ 4 + 40 20 ⋅ 2 + 300 5 ⋅ 10 ⋅ 6 + 300 50 ⋅ 6 = 680 Plan 2 (product first): × , σ , σ , Π \times, \sigma, \sigma, \Pi × , σ , σ , Π
10 ⋅ 20 ⋅ 6 ⏟ 1200 + 200 ⋅ 6 ⏟ 1200 + 100 ⋅ 6 ⏟ 600 + 50 ⋅ 6 ⏟ 300 = 3300 \underbrace{10 \cdot 20 \cdot 6}_{1200} + \underbrace{200 \cdot 6}_{1200} + \underbrace{100 \cdot 6}_{600} + \underbrace{50 \cdot 6}_{300} = 3300 1200 10 ⋅ 20 ⋅ 6 + 1200 200 ⋅ 6 + 600 100 ⋅ 6 + 300 50 ⋅ 6 = 3300 Plan 1 is cheaper. Plan 2 only wins when one input table is empty: then the product costs 0, while Plan 1 still pays for selecting the non-empty table.
Sources# Slides 04, p. 5–8 (operations, notation), p. 9–14 (definitions), p. 15–18 (translation), p. 23–29 (cost estimates)Slides 05, p. 9 (Cartesian product + select vs. join)DBIS_VL04 > Basic Operations , DBIS_VL04 > Translating SQL into operations , DBIS_VL04 > Cost and size estimates , DBIS_VL04 > Cost estimates for the examples , DBIS_VL05 > Join operation DBIS_VL13 > Example Task: Query Plan Costs (WS 23/24, Task 2.2, 8 points) , DBIS Exam WS2324 (not published) (Task 2.2), DBIS Exam WS2324-2 (not published) (Task 2.2)