Week 6-7. Relational Algebra

Week 6. Relational Algebra 1

Relational Algebra Principles

Relational Algebra

Relational algebra is the basic set of operations for the relational model. These operations enable a user to specify basic retrieval requests (queries). The result of an operation is a new relation, which may have been formed from one or more input relations. Hence can be further manipulated.

Relational Algebra Expression

A sequence of relational algebra operations forms a relational algebra expression.

We may choose to use single expressions or a sequence of operations:

• $${\pi }_{\text{FNAME, LNAME, SALARY}}({\sigma }_{DNO=5}(EMPLOYEE))$$
• $$\begin{array}{rl}DEP5\_EMPS& \leftarrow {\sigma }_{DNO=5}(EMPLOYEE)\\ RESULT& \leftarrow {\pi }_{\text{FNAME, LNAME, SALARY}}(DEP5\_EMPS)\end{array}$$

Link to original

Link to original

Unary Relational Operations

Unary Relational Operations

SELECT Statement ($\sigma$)

SELECT (Relational Algebra)

The SELECT operation, $\sigma$, is used to select a subset of tuples from a relation based on a selection condition. The condition acts as a filter and only keeps those tuples that satisfy the qualifying condition.

$${\sigma }_{<\text{selection condition}>}(R)$$

Where $\sigma$ denotes the SELECT operator. Where $R$ denotes the relation.

Example:

• Select the EMPLOYEE tuples whose department number if 4: ${\sigma }_{DNO=4}(EMPLOYEE)$
• Select the EMPLOYEE tuples whose salary is greater than £30,000: ${\sigma }_{SALARY>30,000}(EMPLOYEE)$

Properties:

• SELECT produces a relation $S$ that has the same schema as $R$.
• SELECT is commutative: ${\sigma }_{<1>}({\sigma }_{<2>(R)})={\sigma }_{<2>}({\sigma }_{<1>(R)})$.
• May be applied in any order.
• We can replace a cascade with a single conjunction. $${\sigma }_{<1>}({\sigma }_{<2>(R)})={\sigma }_{<1>\text{ AND }<2>}(R)$$

Link to original

PROJECT Statement ($\pi$)

PROJECT (Relational Algebra)

The PROJECT operation, $\pi$, is used to keep certain columns (attributes) from a relation and discard all others. PROJECT uses vertical partitioning, the list of specified columns is kept in each tuple, other attributes in each tuple are discarded. Duplicate rows are removed since relations are sets.

$${\pi }_{<\text{attribute list}>}(R)$$

Where $\pi$ denotes the PROJECT operator. Where $<\text{attribute list}>$ denotes the desired list of attributes from $R$. Where $R$ denotes the relation.

Example:

• Select the employee’s first name, last name, and salary: ${\pi }_{\text{LNAME, FNAME, SALARY}}(EMPLOYEE)$

Properties:

• The number of tuples in the result of a projection ${\pi }_{<\text{list}>}(R)$ is always less or equal to the number of tuples in $R$.

Link to original

RENAME Statement ($\rho$)

RENAME (Relational Algebra)

The RENAME operation, $\rho$, is used to rename attributes of a relation or the relation name or both. It is useful when a query requires multiple operations and is necessary in some cases. There are three possible cases:

• Change relation name to $S$: ${\rho }_S(R)$
• Change column (attribute) names to $B_1,B_2,\dots ,B_n$: ${\rho }_{(B_1,B_2,\dots ,B_n)}(R)$
• Change combined attribute and relation names: ${\rho }_{S(B_1,B_2,\dots ,B_n)}(R)$

Example:

• Apply multiple operations and rename (using $S\leftarrow R$): $TEMP\leftarrow {\sigma }_{DNO=5}(EMPLOYEE)$ $R(\text{First\_name, Last\_name, Salary})\leftarrow {\pi }_{\text{FNAME, LNAME, SALARY}}(TEMP)$

Link to original

Link to original

Relational Algebra Operations

Relational Algebra Operations

Relations are sets so we can apply set operators. However, we want the results to be relations.

The two operands $R$ and $S$ must be type-compatible (except for CROSS PROD.).

• Same number of attributes.
• Same domain for attributes.

Properties of operations:

• Both UNION (Relational Operation) and INTERSECTION (Relational Operation) are commutative: $$R\cup S=S\cup R$$
• They can also both be treated as $n$-ary operations applicable to any number of relations as both are associative operations: $$R\cup (S\cup T)=R\cup S\cup T$$

UNION

UNION (Relational Operation)

The binary operation UNION, denoted by $\cup$, creates a relation that includes all tuples that includes all tuples from either operand.

The result of $R\cup S$ is a relation that includes all tuples that are either in $R$, in $S$, or in both. Duplicate tuples are eliminated.

Examples:

• Retrieve the SSNs of all employees who work in dept 5. or directly supervise an employee who works in dept 5. $$\begin{array}{rl}DEP{5}_{EMPS}& \leftarrow {\sigma }_{DNO=5}(EMPLOYEE)\\ RESUL{T}_1& \leftarrow {\pi }_{SSN}(DEP{5}_{EMPS})\\ RESUL{T}_2(SSN)& \leftarrow {\pi }_{SUPERSSN}(DEP{5}_{EMPS})\\ RESULT& \leftarrow RESUL{T}_1\cup RESUL{T}_2\end{array}$$

Link to original

INTERSECTION

INTERSECTION (Relational Operation)

The binary operation INTERSECTION, denoted by $\cap$, creates a relation that includes all tuples that are in both operands.

The result of $R\cap S$ is a relation that includes all tuples that are both in $R$ and $S$.

Link to original

DIFFERENCE

DIFFERENCE (Relational Operation)

The binary operation SET DIFFERENCE (also called MINUS or EXCEPT), denoted by $-$, creates a relation that includes all the tuples in the first operand that are not in the second operand.

The result of $R-S$ is a relation that includes all tuples that are in $R$ but not $S$.

Link to original

CARTESIAN PRODUCT

CARTESIAN PRODUCT (Relational Operation)

The binary operation CARTESIAN PRODUCT (or CROSS PRODUCT), denoted by $\times$, creates a relation that combines tuples from two operands in a combinatorial fashion.

The result of $R(A_1,A_2,\dots ,A_n)\times S(B_1,B_2,\dots ,B_m)$ is a relation with degree $n$ + $m$ attributes: $Q(A_1,A_2,\dots ,A_n,S(B_1,B_2,\dots ,B_m)$. The resulting relation state has one tuple for each combination of tuples - one from $R$ and one from $S$.

Operands do not have to be type-compatible.

Generally, cross product is not meaningful but it can precede other operations. To keep only combinations where the DEPARTMENT is related to the EMPLOYEE, we can add a SELECT operation:

$$\begin{array}{rl}FEMAL{E}_{EMPS}& \leftarrow {\sigma }_{SEX{=}^{\prime }{F}^{\prime }}(EMPLOYEE)\\ EMPNAMES& \leftarrow {\pi }_{\text{FNAME, LNAME, SSN}}(FEMAL{E}_{EMPS})\\ EM{P}_{DEPENDENTS}& \leftarrow EMPNAMES\times DEPENDENT\\ ACTUAL\_DEPS& \leftarrow {\sigma }_{SSN=ESSN}(EM{P}_{DEPENDENTS})\\ RESULT& \leftarrow {\pi }_{FNAME,LNAME,DEPENDEN{T}_{N}AME}(ACTUAL\_DEPS)\end{array}$$Link to original

Link to original

Binary Relational Operations

JOIN Statement

JOIN (Relational Operation)

We can simplify the sequence of CARTESIAN PRODUCT followed by SELECT into a single operation JOIN.

The general form of a join operation on two relations $R(A_1,A_2,\dots ,A_n)$ and $S(B_1,B_2,\dots ,B_m)$ is:

$$R{\bowtie }_{<\text{join condition}>}S$$

Where $R$ and $S$ can be any relations that result from general relational algebra expressions.

Examples:

• Suppose we want to retrieve the name of the manager of each department. $$DEPT\_MGR\leftarrow DEPARTMENT{\bowtie }_{MGRSSN=SSN}EMPLOYEE$$ The join condition is MGRSSN=SSN or DEPT.MGRSSN = EMPLOYEE.SSN.

Theta JOIN

Theta JOIN (Relational Operation)

The general case of the JOIN operation is called a Theta-join:

$$R\underset{\text{theta}}{\bowtie }S$$

The join condition is called theta. Theta can be any general boolean expression on the attributes of $R$ and $S$, e.g.:

$$R.Ai<S.Bj\text{ and }(R.Ak=S.Bi\text{ or }R.Ap<S.Bq)$$Link to original

EQUIJOIN

EQUIJOIN (Relational Operation)

The most common use of join involves join conditions with equality comparisons only, in this case, it is called an EQUIJOIN.

In the result of an EQUIJOIN, we have one or more pairs of attributes that have identical values in the tuple.

$$DEPT\_MGR\leftarrow DEPARTMENT{\bowtie }_{MGRSSN=SSN}EMPLOYEE$$Link to original

NATURAL JOIN

NATURAL JOIN (Relational Operation)

The NATURAL JOIN operation, denoted by ${}^{\ast }$, was created to get rid of the second attribute in an EQUIJOIN condition.

To apply aw natural join on the DNUMBER attributes of DEPARTMENT and DEPT_LOCATIONS, it is sufficient to write:

$$\text{DEPT\_LOCS}\leftarrow \text{DEPARTMENT }{}^{\ast }\text{ DEPT\_LOCATIONS}$$Link to original

Link to original

DIVISION Statement

DIVISION (Relational Operation)

The DIVISION operation, identified by $÷$, is the inverse of Cartesian Product (SQL). An intuitive property of the operator is that you can consider that:

$$\begin{array}{rl}U& =R\times S\\ U÷R& =S\\ U÷S& =R\end{array}$$

For a tuple $t$ to appear in the result $T$ of the DIVISION, the values in $t$ must appear in $R$ in combination with every tuple in $S$.

Link to original

Additional Relational Operations

Aggregate Functions

Aggregate Function (Relational Operation)

A type of request that cannot be expressed in basic relational algebra is to specify mathematical aggregate functions on collections of values from the database.

We use the Aggregate Functional operation $\mathcal{F}$ for common aggregations:

• ${\mathcal{F}}_{\text{MAX Salary}}(\text{EMPLOYEE})$: retrieves maximum salary value from the relation
• ${\mathcal{F}}_{\text{MIN Salary}}(\text{EMPLOYEE})$: retrieves minimum salary value from the relation
• ${\mathcal{F}}_{\text{SUM Salary}}(\text{EMPLOYEE})$: retrieves the sum of the Salary from the relation
• ${\mathcal{F}}_{\text{COUNT Ssn, AVERAGE Salary}}(\text{EMPLOYEE})$: computes the count of employees and their average salary

We can also use a variation of the aggregate operation:

• Grouping attribute placed to the left.
• Aggregate functions placed to the right.

Hence, we can use ${}_{\text{DNO}}{\mathcal{F}}_{\text{COUNT Ssn, AVERAGE Salary}}(\text{EMPLOYEE})$ in order to group employees by their department number and compute the count of employees and average salary per department.

Link to original

OUTER JOIN

OUTER JOIN (Relational Operation)

In NATURAL JOIN (Relational Operation) and EQUIJOIN (Relational Operation), tuples without a matching tuple are eliminated from the join result.

• Tuples with null in the join attributes are also eliminated. We can use outer joins to conditionally keep certain data we may want.

• LEFT OUTER JOIN: $R\text{ ⟕}S$
  Keeps every tuple in the left relation $R$. If no matching tuple is found in $S$, then the attributes of $S$ in the join result are filled with null values.

• RIGHT OUTER JOIN: $R\text{ ⟖}S$
  Keeps every tuple in the right relation $S$. Attributes of $R$ are filled with null values in unlatching tuples.

• FULL OUTER JOIN: $R\text{ ⟗}S$
  Keeps every tuple in both relations. When no matching tuples are found, pad with null values.

Link to original

OUTER UNION

OUTER UNION (Relational Algebra)

The OUTER UNION operation was developed to take the union of tuples from two relations if the relations are not type compatible. This operation will take the union of tuples in two relations $R(X,Y)$ and $S(X,Y)$ that are partially compatible, meaning only some of their attributes (i.e. $X$) are type compatible.

Attributes not type compatible are kept in the result relation, e.g. $T(X,Y,Z)$.

Link to original