What is relational algebra, and why is it useful for query processing?
A formal language used to query and manipulate relational databases (selection, projection, union, join, …); it is very useful for representing execution plans.
Name the five basic relational algebra operations.
Selection (σ), projection (π), cross-product (×), set-difference (−), union (∪).
Selection vs projection: which is horizontal and which vertical?
Selection (σ) selects a subset of rows — horizontal. Projection (π) retains the required columns — vertical.
Why can relational algebra operations be composed?
Because each operation returns a relation — the algebra is "closed".
What is the schema of the result of a selection?
The same as that of the input relation.
Does projection eliminate duplicates? Do real systems?
The projection operator has to eliminate duplicates; real systems typically don't do duplicate elimination unless the user explicitly asks for it.
S2(sid, sname, rating, age) = {(28, yuppy, 9, 35.0), (31, lubber, 8, 55.5), (44, guppy, 5, 35.0), (58, rusty, 10, 35.0)}. What are σ rating>8 (S2) and π age (S2)?
σ rating>8 (S2) = (28, yuppy, 9, 35.0), (58, rusty, 10, 35.0). π age (S2) = 35.0, 55.5.
Using S1 and S2, what are S1 − S2 and S2 − S1?
S1 − S2 = (22, dustin, 7, 45.0). S2 − S1 = (28, yuppy, 9, 35.0), (44, guppy, 5, 35.0).
What does the cross-product S1 × R1 produce?
Each row of S1 paired with each row of R1 (for the slide instances: 3 × 2 = 6 rows).
Natural join R ⋈ S conceptually: the three steps.
Compute R × S; select rows where attributes appearing in both relations have equal values; project all unique attributes and one copy of each common one.
Why are joins called compound operators?
They involve cross product, selection, and (sometimes) projection.
S1 = {(22, dustin, 7, 45.0), (31, lubber, 8, 55.5), (58, rusty, 10, 35.0)}; R1(sid, bid, day) = {(22, 101, 10/10/96), (58, 103, 11/12/96)}. What does the theta join S1 ⋈ S1.sid<R1.sid R1 return?
(22, dustin, …, 58, 103, 11/12/96) and (31, lubber, …, 58, 103, 11/12/96) — both sid columns are kept.
When are two relational algebra expressions equivalent?
When on every legal database instance they generate the same set of tuples (order of tuples is irrelevant).
Equivalence rule 1.
Conjunctive selection can be deconstructed into a sequence of individual selections: σ θ1∧θ2 (E) = σ θ1 (σ θ2 (E)).
Equivalence rule 3.
Only the last in a sequence of projection operations is needed: π L1 (π L2 (… (π Ln (E)))) = π L1 (E).
Equivalence rule 4.
Selections combine with Cartesian products and theta joins: σ θ (E1 × E2) = E1 ⋈ θ E2; σ θ1 (E1 ⋈ θ2 E2) = E1 ⋈ θ1∧θ2 E2.
Equivalence rules 5 and 6.
5: theta joins (and natural joins) are commutative: E1 ⋈ E2 = E2 ⋈ E1. 6: natural joins are associative: (E1 ⋈ E2) ⋈ E3 = E1 ⋈ (E2 ⋈ E3); theta joins too, if θ2 involves attributes from only E2 and E3.
Equivalence rule 7a.
When θ0 involves only the attributes of E1: σ θ0 (E1 ⋈ θ E2) = (σ θ0 (E1)) ⋈ θ E2 — selection distributes over the theta join.
Equivalence rule 8a.
If θ involves only attributes from L1 ∪ L2: π L1∪L2 (E1 ⋈ θ E2) = (π L1 (E1)) ⋈ θ (π L2 (E2)).
Which set operations are commutative, and which is not?
Union and intersection are commutative (rule 9); set difference is not commutative.
Equivalence rules 11 and 12.
11: selection distributes over ∪, ∩ and − (e.g., σ θ (E1 − E2) = σ θ (E1) − σ θ (E2)). 12: projection distributes over union: π L (E1 ∪ E2) = π L (E1) ∪ π L (E2).
Why perform the selection σ branch_city="Brooklyn" (branch) before the join?
Performing the selection as early as possible reduces the size of the relation to be joined (rule 7a).
In the Brooklyn / balance > 1000 example, which rule makes "selections early" possible?
Join associativity (rule 6a): regroup as (branch ⋈ account) ⋈ depositor, then apply σ branch_city="Brooklyn" (branch) ⋈ σ balance>1000 (account).
How do you choose between (r1 ⋈ r2) ⋈ r3 and r1 ⋈ (r2 ⋈ r3)?
They are equal; if r2 ⋈ r3 is quite large and r1 ⋈ r2 is small, choose (r1 ⋈ r2) ⋈ r3 so a smaller temporary relation is computed and stored.