0.4 Relational algebra  (Page 3/3)

1. JOIN Operation

The JOIN operation is used to combine related tuples from two relations into a single tuple. The Theta-JOIN is a specialized product containing only pairs that match on a supplied condition called join-condition.

• Notation: $r⊲{⊳}_{\text{join}-\text{condition}}s$

• $r⊲{⊳}_{C}s=\{(\mathrm{t1},\mathrm{t2})\mid \mathrm{t1}\in r\wedge \mathrm{t2}\in s\wedge C(\mathrm{t1},\mathrm{t2})\}$ where r(R) , s(S)
• Similar to PRODUCT, each tuple in the result of JOIN operation contains all attributes from two original relations. However, in this operation one tuple in R and one tuple in S can be combined together to form a tuple in the result if the combination satisfies the join condition.
• Join condition is of the form:

<condition>AND<condition>AND …AND<condition>

where<condition>is a comparision between one attribute in R and one attribute in S, provided that these two attributes have the same domain.

• Result size:
• Result schema: If we have R(A1, A2, …, An) and S(B1, B2, …, Bm) then the list of attributes in Result is (A1, A2, …, An, B1, B2, …, Bm)
• Producing the result of JOIN operation:
  • For each tuple in r, form new tuples by pair it with each tuple in s
  • If the new tuple satisfies the specified condition, then place it in the result set.
• Example:

Variations of JOIN

EQUI-JOIN: A JOIN where the only comparision operator used in the join condition is “=” is called EQUI-JOIN. The result of Equi Join always has one or more pairs of attributes that have identical values in every tuple.

Example:

NATURAL JOIN: The Natural Join operation is a specialised product where the result tuple contains only pairs of tuples that match on their common attributes with one of each pair of common attributes is eliminated. The standard definition of Natural Join requires that the two join attributes have the same name. Therefore, we can see that Natural Join is created to get rid of the duplicate columns in an Equi Join.

• Notation: r * s
• Natural Join can be defined using other operation $r\ast s={\pi }_{R\cup S}({\sigma }_{\text{condition}}(r\times s))$

where r(R) and s(S) and condition is boolean expression (A1 = B1) AND (A2 = B2 ) AND … AND (Ak = Bk) with Ai is the attribute in r , Bi is the attribute in s and (Ai, Bi) is a pair of common attributes.

Producing the result of Natural Join

• For each tuple in relation r, compare common attributes with those in each tuple of s
• If two tuples match in their common attributes then combine tuples, remove duplicate attributes and add to the result.

• Example: From the example of Equi Join, assume that the attribute list in s now is ( E, F,B) instead of (E, F, G) then we can have the expression r * s .

• Retrieve the information of student who enrols in at least one course.

1. DIVISION Operation

The Divition Operation is defined on two relation r(U1) and s(U2) where U2 is the subset of U1 and s is not an empty relation: $r÷s=\{t\mid t\in r(U_1-U_2)\wedge \text{satisfy}\}$ where $\text{satisfy}=\forall t_s\in s(\exists t_r\in r(t_r[U_2]=t_s\wedge t_r[U_1-U_2]=t))$

This means that for a tuple t to appear in the result of Division, the values in t must appear in r in combination with every tuple in s.

The Division is very useful for a special kind of query such as “ Retrieve the name of the student who enrolls in all course teach by Professor Ba”

• Producing the result of the Division operation
  • Consider each subset of tuple in r that match on t[U1 – U2]
  • For this subset of tuples, take the values t[U2] from each. If this covers all tuples in s then add t[U1 – U2]in the result.
• Example: Retrieve the name of subject that is taught in all courses

Data manipulation with relational algebra expression

Sample Database

In this session, we use the COMPANY database in the examples for illustrating the use of Relational Algebra for answering several queries.

The relational database schema for the COMPANY database is specified as below

EMPLOYEE (EID, Name, Bdate, Address, Salary, DeptId)

DEPARTMENT(DeptId, Dname, Office, Mng-EID)

PROJECT(Code, Name, Budget, DeptId)

JOIN(EID, PCode, StartDate)

EMP-DEPENDENT(EID, Dependent-Name, Bdate, Relationship)

Sample Queries

Query 1: Find all employees whose salary is greater than 30.000

${\sigma }_{\text{salary}>\text{30000}}(\text{EMPLOYEE})$

Query 2: Find the name, address of employees who works for department number 1

${\pi }_{\text{Name},\text{Address}}({\sigma }_{\text{DeptId}=1}(\text{EMPLOYEE}))$

Query 3: Find the name of the department that employee John Smith works for.

${\pi }_{\text{Dname}}({\sigma }_{\text{Name}=\text{'}\text{John}\text{Smith}\text{'}}(\text{EMPLOYEE}\ast \text{DEPARTMENT}))$

Query 4: Find the EID, start date of the employees who works for project number P1 or project number P2

${\pi }_{\text{EID},\text{StartDate}}({\sigma }_{\text{PCode}=1\vee \text{PCode}=2}(\text{JOIN}))$

Query 5: Find the name, relationship of all the dependents of employees who works for Department Human Resource

$\begin{array}{}{\pi }_{\text{Dependent}-\text{Name}\text{,Re}\text{lationship}}({\sigma }_{\text{DName}=\text{'}\text{Human}\text{Re}\text{source}\text{'}}\\ (\text{EMP}-\text{DEPENDENT}\ast \text{EMPLOYEE}\ast \text{DEPARTMENT}))\end{array}$

Query 6: Finds the name of the employees who join in every project.

${\pi }_{\text{Name}}(\text{EMPLOYEE}\ast ({\pi }_{\text{EID},\text{PCode}}(\text{JOIN})÷{\pi }_{\text{Code}}(\text{PROJECT})))$

Query 7: Finds the names of the employees who have no dependent

$\begin{array}{}\\ {\pi }_{\text{Name}}(\text{EMPLOYEE}\ast ({\pi }_{\text{EID}}(\text{EMPLOYEE}){}_{\text{EID}}(\text{EMP}-\text{DEPENDENT})))\end{array}$

Query 8: Find the name of employees who works for both project number 1 and project number 2

${\pi }_{\text{Name}}(\text{EMPLOYEE}\ast ({\pi }_{\text{EID}}({\sigma }_{\text{PCode}=1}\text{JOIN})\cap {\pi }_{\text{EID}}({\sigma }_{\text{PCode}=2}\text{JOIN})))$

Query 9: Find the name of the manager who has at least one dependent

${\pi }_{\text{Name}}(\text{EMPLOYEE}\ast ({\pi }_{\text{EID}}(\text{EMP}-\text{DEPENDENT}⊲{⊳}_{\text{EID}=\text{Mng}-\text{EID}}\text{DEPARTMENT})))$