Relational Algebra

• A procedural language that is evaluated like a mathematical expression
• Based on mathematical foundations of set theory
• We don’t care about relationships vs entities here—they are all sets

Core

• Operations
• Select: ${\sigma }_{c}A$
  • Picks rows that meet the condition
  • $C$ is a condition that refers to attributes
• Projection: ${\Pi }_{L}A$
  • Selects certain columns
  • $L$ is an ordered list of attributes from the schema
  • Alters the schema and data
  • Needs duplicate removal afterwards
• Product: $A\times B$
  • Cartesian product of two sets
    • Pair each tuple of A with each tuple of B
  • Schema is the attributes of A and then B, ie
    • Attributes with the same name will be A.name, B.name
• Theta-Join: $R1{\bowtie }_{c}R2$
  • Equivalent to ${\sigma }_c(R1\times R2)$
  • Common form of boolean condition: $A\theta B$ where $\theta$ is =, <, >, etc.
• Natural-Join: $R1\bowtie R2$
  • A frequent type of join
  • Connects two relations by equating attributes of the same name (ie key to foreign key)
  • Projects out one copy of the equated attributes (removes the duplicate key)
• Renaming: ${\rho }_{R1(A_1,\dots ,A_n)}(R2)$
  • Gives a new schema to a relation
  • Alternate notation: R1(A1,…An) := (R2)

Complex Expressions

• Parenthesis override order of operations (like normal algebra)
• Three representations
  • Sequences of assignments
  • Expressions with parenthesis
  • Trees
    • Leaves are operands (either variables of relations or constant relations)
    • Inner nodes are operators
• Precedence
  1. Unary (select, project, rename)
  2. Product, Join
  3. Intersection
  4. Union, Difference

Bag Semantics

• Bags (aka multiset) is like a set but an element can appear more than once
  • Sets are also bags that happen to be a set
• Used because deduplication is an expensive operation that requires sorting
• Most commercial databases use bags semantics unless the attribute is explicitly declared to be unique
  • SQL is implemented on top of bag semantics

Operators

• Union: Add counts
• Intersection: The minimum counts of elements that appear in both
• Difference: The number of times an object appears in A minus the number of times in B (without going negative)
• Selection: Same
• Projection: Do not eliminate duplicates
• Product and Joins: Same
• Bag laws != Set laws (some but not all hold)
  • Ex: commutative law for union holds for both (because addition is commutative)
  • Ex: Union idempotent law ($S\cup S=S$) does not hold because each element would be duplicated

Equivalence Laws

• #TODO

Extended

• Eliminate duplicates from bags: $\delta$
• Sort tuples: $\tau$
• Extended projection
  • Arithmetic, duplication of columns
  • $L$ can include arbitrary arithmetic
• Grouping and aggregation: ${\gamma }_L(R)$
  • $L$ is a list of elements that are either
    • Grouping from the base table
    • Aggregation
  • Ex: sum, average, min, max
• Outer Join
  • Include “dangling tuples” (tuples that do not join with anything) in the result