Relational algebra

Content

1. Introduction
2. Union
3. Intersect
4. Difference
5. Product (Cartesian Product)
6. Restrict
7. Project
8. Join
9. Divide

INTRODUCTION

Relational database systems are expected to be equipped with a query language that can assist its users to query the database instances.
There are two kinds of query languages − relational algebra and relational calculus.
Here we are going to talk about relational algebra and its operators.

Relational Algebra

The relational algebra is a collection of operators that take relations as their operands and return a relation as their result.
It was first developed by E. F. Codd at IBM and was formally introduced in 1970. Codd's work became the basis for database query languages, such as SQL and MySQL.
That original algebra had eight operators, two groups of four each:
1. The traditional set operators union, intersection, difference, and Cartesian product (all of them modified somewhat to take account of the fact that their operands are, specifically, relations instead of arbitrary sets).
2. The special relational operators restrict (also known as select), project, join, and divide. (see below how each operator works).

Relational algebra uses those operators to perform queries.
An operator can be either unary(operate on one operand) or binary(operate on two operands). They accept relations as their input and yield relations as their output. Relational algebra operators are performed recursively on a relation. The output of these operations is a new relation, which might be formed from one or more input relations.
Relational algebra uses some operators from set theory, but adds additional constraints to these operators.

Difference between Set and Relation :

1. A set is a collection of distinct elements that can be of differents types.
2. A relation is a kind of set, is a collection of TUPLES that must be of the same type.
3. A tuple is a set of ordered triple elements. Why triple ? because each element contain 3 attributes : Name, Type, Value.
4. Any query that we write on existing relations, wil produce a new relation as a result.
5. we can pose queries on that relation, or combine it with our previous relations.

some operators of relational algebra are as follows:

img: The original eight operators

UNION

In mathmatics, the union of two sets is the set of all elements belonging to either or both of the given sets. The result will be a set containing all the tuples appearing in either or both of the given relations.
However, In relational algebra, the union of two input relations must to be of the SAME TYPE ("tuple-homogeneous"). The result will be obviously a relation with attributes of the same type. In relational algebra, the result never contain duplicate tuples.

Example :

We can notice that Result will have same column names as first query. Duplicate record – 104 from EMP_TEST and EMP_DESIGN are showed only once in the result set. Records are sorted in the result.

UNION ALL

This operation is also similar to UNION, but it does not eliminate the duplicate records. It shows all the records from both the tables. All other features are same as UNION. We can have conditions in the SELECT query. It need not be a simple SELECT query.

Example :

Look at the same example below with UNION ALL operation.

INTERSECT

The intersection of two sets or of two relations is a new set containing only the tuples that appearing in both sets. Like union, the two inputs relations must be of the SAME TYPE and the result doesn't contain duplicate elements.

Example :

Same example above when used with INTERSECT operator, gives below result.

DIFFERENCE

Like union and intersection, the relational difference operator also requires its operands to be of the same type. The difference of two sets is a new set containing only the tuples that appears in the first set and not in the second set,It basically subtracts the first query results from the second.

Example :

We can notice in the above result that only the records that do not exists in EMP_DESIGN are displayed in the result. The record which appears in both the tables is eliminated. Similarly, the records that appear in second query but not in the first query are also eliminated.

PRODUCT (OR CARTESIAN PRODUCT)

The cartesian product of two sets is the set of all ordered pairs such that, in each pair, the first element comes from the first set and the second element from the second set. The result won't be the ordered pairs of each pair of tuples as in mathematics but a single tuple which is the union of the two tuples in question.

Example :

Let's suppose you are a Shoes Shop Manager and you want to order new merchandise. The warehouse gave You 2 lists , one for shoes brands and one for shoes color. You want to know all the possible Shoes/color combinations in order to choose which merchandise you will order, You will do a CARTESIAN PRODUCT as follow:

RESTRICT (or SELECT)

The RESTRICT operation is used for selecting a subset of the tuples according to a given selection condition. Sigma(σ)Symbol denotes it. It is used as an expression to choose tuples which meet the selection condition. Select operation selects tuples that satisfy a given predicate.
(some refer to "restrict" as "select", we chose to use restrict not to confuse with SQL select).

Example :

let's break it down.
in this example we want to list all the staff members with a a salary greater than 10,000. to do that we first write the SIGMA SIGN (select), and then a CONDITION (salary > 10000), and lastly, the relation (staff).
this will output a new relation with all the staff members who's salaries are greater then 10000.

PROJECT

The PROJECT operation is used to select a subset of the attributes of a relation by specifying the names of the required attributes.

Example :

here we can see that we specify the name of the attribute (Suburb), and we get as a result a (projection) list of all Suburbs with elimination of the duplicate.

difference between RESTRICT and PROJECT:
Restrict Operation : This operation is used to select rows from a table (relation) that specifies a given logic, which is called as a predicate. The predicate is a user defined condition to select rows of user's choice.
Project Operation : If the user is interested in selecting the values of a few attributes, rather than selecting all attributes of the Table (Relation), then one should go for PROJECT Operation.

JOIN

Let relation 'a' have attributes X,Y and relation 'b' have attributes Y,Z so the Y attribute is common to the two relations. The join of 'a' and 'b'('a' JOIN 'b') is a relation with heading {X,Y,Z} and body consiting of all tuples {Xx, Yy, Zz} such that a tuple appears in 'a' with X value x and Y value y and a tuple appears in 'b' with Y value y and Z value z. In the case where the two relations have no attribute names in common, the join becomes a cartesian product. In the case where 'a' and 'b' are of the same type, the join becomes an INTERSECT.

Example :

Let's back to the Shoes Shop manager. You have the historical list of all the sold brand shoes order by sales number for the last 3 months. You have a second list of all the customers who bought in your store these last three months with the corresponding sales number . You want to make an inventory list of the last 3 month sales in order to analyse and know which brand is the most sold, from which city do the majority of customers come in order to make publicity in those place. You will make a JOIN From the two list, taking as a reference point the sales number.

DIVIDE

There are two types of divide operators, one with "per" and one without "per"
A "per" is a third relation that will be a sort of reference when dividing A by B It is called also the "Mediator".
Let's first explain the Division without "per".
A relation "A" can be divisible by a relation "B" only if "A" have more attributes than "B".
Takes two relations A{X,Y} and B{Y}, one binary (A) and one unary (B).
When we divide A by B, we are building a new relation consisting of all distinct values of one column {X} of the binary relation (A) in such a way that the associated column {Y} in A is matching values of column {Y} in the unary relation (B).
The divide operator can be applied if and only if:
- attributes of 'b' is proper subset of Attributes of 'a'
- the relation returned by division operator will have attributes = (all attributes of 'a' – All Attributes of 'b')
- the relation returned by division operator will return those tuples from relation 'a' which are associated to every 'b'’s tuple.

Example :

The employer want to know which of his employees is speaking english and have at least 2 years of work experience. He will make a DIVISION without mediator (Employees DIVIDE BY Attributes {english,5 monts})

DIVIDE WITH PER

Now let's explain the division with "per" (Mediator). Takes three relations A{X}, B{Y} and C{X,Y}. "A" and "B" are unary and "C" is Binary. When dividing "A" By "B" per "C", we build a new relation with all the values of A{X} in such a way that when we associate A{X} and B{Y} it match with C{X,Y}.

Example :

Go back to the Shop manager example, You have a list of possible Shoes/color combinations from the warehouse and a list of all shoes brands that you want to order. And you need to find all the shoes that are from color in the third list :