Intro to Database Systems - Part 4 & 5 : Relational Algebra

Let’s start by understanding what relational algebra is:

A query language allows manipulation and retrieval of data from a database. It is useful to explain how a SQL query is executed internally.

Understanding relational algebra is basically understanding SQL. Some basic operations from relational algebra are:

The select operation is an unary operation noted σc( R ). It returns a subset of rows from the input relation R, satisfying condition C. This constraint is expressed as the predicate. The predicate is a boolean expression whose operators are:

employees.png

Considering a table of employees E, this is an example of the select operation in SQL:

select1.PNG

select2.PNG

Under the relation algebra form, we’ll have:

It is important to notice that:

The project operation is an unary operation noted ∏L ( R ), where L is a list of attributes (A1, A2, A3, …, An) and R is the input relation. It extracts a subset of columns (the attributes) in a relation and discards the rest. If the user is interested in selecting the values of a few attributes, rather than selecting all attributes of the relation/table, one should go for the project operation.

This is an example of the project operation in SQL:

project1.PNG

project2.PNG

Under the relational algebra form, we’ll have:

Note that again, the process is simple:

We can also use operator composition: embed the result of one operation as an input to another relation. Example:

aaa.PNG

The rename operator is a unary operator noted ρ( X(x1,x2,…,xn), Y(y1, y2, …, yn)) where X is identical to the initial relation Y, but with a new relation name X and new attribute names (x1 to xn). Example:

The union operator takes as input two relations R and S.

As an example,

union.PNG

The intersection operator is applied when only rows shared by both A and B are included in the result. It has the same preconditions as the union operator (no duplicates, same number of attributes, domain compatibility).

intersect.PNG

The set difference operator between two relations A - B results in a relation containing rows that are in A but not in B.

diff.PNG

The cross product operator between two relations A X B is the set of pairs that can be formed by pairing each row of A with each row of B.

cross.PNG

If it happens that attributes have the same name in the resulting relation, we should prefix the similar attributes with the initial relation name (example : id is an attribute of relation school, but also of relation library. In the resulting relation, there should be an attribute for school id and another one for library id).

An easy way to implement the cross product operator is a nested loop. For each row from table A, pair it with a row from table B.

The condition join is just a cross product satisfying a condition. We apply the nested loop method in order to create the pairs, but only in the case where the condition is satisfied. It’s the selection operation applied to a cross product.

cond.PNG

In SQL we’ll have : SELECT * FROM Employee, Department WHERE dept = depNr

eq.PNG

The equi-join is simply a condition join where the condition is an equality.

The natural-join is an equi-join if values from columns with the same name are equal. If relation A has attribute (column) studID and relation B has attribute studID, rows will be paired only if their value are identical (relation A has a student with studID 99 and relation B has a student with stutID 99). In other words, we need 2 conditions to apply the paring:

As a conclusion, here are some properties of relational algebra:

1.PNG

2.PNG

3.PNG

4.PNG

5.PNG

 
63
Kudos
 
63
Kudos

Now read this

Install Windows 10 from USB

Here is a way to install Windows 10 from an USB key instead of a CD. What you need is: a PC running Windows an empty memory key with at least 8 GB the PC on which you want to install Windows 10. The first step is to make the USB key... Continue →