Relational Algebra

Relational algebra is a query language that defines relational algebra operations, binary operations that operate over instances of relations.

$S=$

Id	Name	Age	Rating
4312	Alex	43	3.4
3245	Jamey	23	4.1
5723	Lola	9	2
5435	Charlie	72	4
5674	J.J Jameson	60	5
^S

$T$ =

Id	Name	Age	Rating
3453	Fiona	25	0.5
3522	Ezekiel	88	4.5
5435	Charlie	72	4
4312	Alex	43	3.4
^T

Selection §

The selection operation is a unary operation that uses a selection criteria to essentially filter entries from a table/instance based on their fields/attributes. It uses the symbol sigma $\sigma$

$${\sigma }_{\text{Selection Criteria}}(S)$$

Note that the selection criteria is a boolean expression which can either involve fields or constants.

The selection operation allows changing the cardinality (number of rows) of the input instance, without affecting the degree (number of columns).

Example: Selection

$${\sigma }_{Age>30}(S):$$

Id	Name	Age	Rating
4312	Alex	43	3.4
5435	Charlie	72	4
5674	J.J Jameson	60	5

Projection §

The projection operation is a unary operation that allows tuples containing only specific fields to be obtained. Any other fields are ‘projected’ out. The symbol pi $\pi$ is used for projection.

$${\pi }_{fields}(S)$$

Duplicate Elimination

Relational algebra treats all relations as sets, so if we have any fields with duplicate values, they essentially ‘disappear’ from the final output. In real life, duplicate elimination is very expensive, and some software allow the concept of Multiset. However, relational algebra assumes sets i.e. no duplicate values. See query optimisation of projection to see how a real-time software eliminates duplicates, if needed.

The projection operation allows changing the degree of the input instance, without affecting the cardinality (assuming unique records).

Example: Projection

$${\pi }_{Name,Age}(S):$$

Name	Age
Alex	43
Jamey	23
Lola	9
Charlie	72
J.J Jameson	60

Set Operations §

Most of the common Set Operations apply to relational instances.

Union-Compatibility §

Two instances are union-compatible if they have the same number of fields and the domains (datatype).

Union §

$$A\cup B$$

%%🖋 Edit in Excalidraw, and the dark exported image%%

• Set union works the same way as normal sets, showing records that exist in either $A$ or $B$.
• Only works if both instances are union-compatible
• Only affects cardinality, degree is unchanged
• Schema is the same as that of $A$

Example: Union

$S=$ $T=$

$$S\cup T:$$

Id	Name	Age	Rating
4312	Alex	43	3.4
3245	Jamey	23	4.1
5723	Lola	9	2
5435	Charlie	72	4
5674	J.J Jameson	60	5
3453	Fiona	25	0.5
3522	Ezekiel	88	4.5

*Note how duplicate entries Alex & Charlie only appear once!

Set Difference §

$$A-B$$

%%🖋 Edit in Excalidraw, and the dark exported image%%

• Set difference has the same procedure as normal sets.
• Only works if both instances are union-compatible
• It is not symmetrical. $A-B\ne B-A$
• Only affects cardinality, degree is unchanged
• Schema is the same as that of $A$

Intersection §

$$A\cap B=A-(A-B)$$

%%🖋 Edit in Excalidraw, and the dark exported image%%

• In relational algebra, defined as a compound operator of two set differences.
• Only affects cardinality, degree is unchanged
• Requires both instances to be union-compatible

Example: Intersection

$S=$ $T=$

$$S\cap T:$$

Id	Name	Age	Rating
5435	Charlie	72	4
4312	Alex	43	3.4
* Notice how only the duplicate entries of both tables are kept.

Cartesian Product (Cross Product) §

$$A\times B$$

• Returns the cartesian product of both instances, i.e. every possible tuple of each row
• Output has every record having fields from both sets
• Cardinality is given by $|A|\cdot |B|$
• Resulting schema has fields from both sets
  • Naming conflicts may arise if $A$ and $B$ have the same names for fields
  • Need to use the renaming operation to handle such conflicts.

Renaming §

To avoid name conflicts where fields contain the same name, the renaming operator $\rho$ can be used. The syntax is as follows:

$$\rho (R(\bar{F}),E)$$

• $E$ is the original instance/tuple which we want to rename
• $R$ is the resultant instance/tuple which copies the same schema and values as $E$, and **then has the rename mapping, $\bar{F}$ applied
• $\bar{F}$ is the mapping function, which takes in renames of the forms:
  • $oldname\to newname$
  • $i\to newname$ where $i$ is the index of the field (STARTING FROM 1)

For example:

$$\rho (R(\text{1 → Last Name},\text{Age → Years}),S)$$

Renames the ‘Name’(index 1) field to ‘Last Name’, and the ‘Age’ field to ‘Years’

Joins §

A more complicated operation (which is a compound operation) which allows the ‘combination’ of tables are called joins.

Natural Join §

$$A\bowtie B$$

• The natural join operation returns a joined table of tables $A$ and $B$ only if there are any attribute names and values in common between them. The process of a natural join is:

1. Apply a cross product: $A\times B$
2. Select any records where common attribute names and values exist:
   1. The selection criteria would be: ${\sigma }_{A.i=B.j},$ where field $i$ in A has the same name as field $j$ in B
3. Project only unique attributes, and one copy of any duplicate attributes
   1. This ensures we don’t have naming conflicts, and every attribute only shows up once in the resultant table

• If the natural join exists, the degree is given by the number of unique attributes

Condition Join (Theta-Join) §

$$A{\bowtie }_{\text{cond}}B={\sigma }_{\text{cond}}(A\times B)$$

• A type of join that specifies one or more conditions ($c$) for joining. The conditions can be equalities or inequalities involving attributes of the relation, similar to the conditions applied in selection operation.
• Equivalent to applying a selection over the cross product of the instances
• Resultant schema is same as that of the cross product

Equi-Join §

$$A{\bowtie }_{\text{equality}}B={\sigma }_{\text{equality}}(A\times B)$$

• Similar to Condition Join, but the conditions can only be equalities involving attributes of the relation.
• Equivalent to applying a selection over the cross product of the instances
• Resultant schema is same as that of the cross product

Equivalences §

The selection operation has the following properties:

• Cascading: ${\sigma }_{a\wedge b\wedge c}(S)\equiv {\sigma }_a({\sigma }_b({\sigma }_c(S)))$
• Commutative: ${\sigma }_{a\wedge b}(S)\equiv {\sigma }_{b\wedge a}(S)$

The projection operation has the following properties:

• Cascading on subsets: ${\pi }_{a,b,c}(S)\equiv {\pi }_a({\pi }_{a,b}({\pi }_{a,b,c}(S)))$. Only when the ‘outer’ operator operates with columns that are a subset of inner operation.

Projection and selection commute only if the selection acts on attributes returned from the projection:

${\pi }_{a,b,c}({\sigma }_{f(a,b,c)}(S))\equiv {\sigma }_{f(a,b,c)}({\pi }_{a,b,c}(S))$Join equivalences allow us to change the order of join operations:

• Associative: $A\bowtie (B\bowtie C)=(A\bowtie B)\bowtie C$
• Commutative: $A\bowtie B=B\bowtie A$