Relational Algebra

Query language

Two types of query language :

Procedural query language: Non procedural query language :
What to retrieve from database and how to retrieve. What to retrieve from database.
Example : Relational Algebra. For example : Tuple Relational Calculus.
π , × , σ , etc. Use First Order Logic :
∈ , ∃ , ∧ , ∨ , ¬ , → , etc.

Relational algebra

Relational algebra is a procedural language. It provides operators which performs operations on existing relation to derive results relations. It results always distinct tuple.

Types of Relational Algebra Operators :

Operator

Symbol

Operator Name Basic/Derived

 Operators

Unary/Binary/

Logical

 Π Projection Operator Basic Unary
 σ Selection Operator Basic Unary
 ρ Rename Operator Basic Unary
 ∪ Union Operator Basic Binary
 × Cross Product Operator Basic Binary
 − Minus or Set Difference Operator Basic Binary
  Intersection Derived Binary
 ⋈ Join Derived Binary
 / or ÷ Division Derived
 ← Assignment Operator
 ∧ Logical And Logical Logical
 ∨ Logical OR Logical Logical
 ¬ Logical NOT Logical Logical
ρ Rename Operator

Relational Algebra - Outer Joins

Characteristics of relational operators :

  • Relational operators always work on one or more relational table.
  • Relational operators always produce another relational table.
  • The result table produced by a relational operator has all the properties of relational model.
  • Union, intersection and difference operation, the two operand relations must be Union compatible.
Meaning of Union compatible property :
  • Number of attributes should be same between R and S
  • Range of attributes should be similar where Range = Type of values accepted by attributes.
    Relational Algebra - Union Compatibility Property
Union, Intersection and Difference Operators are also called Set Theory
Operators

Union (∪) : The union of two relations a and b, A ∪ B is the set of all
             the tuples t belongs to either a or b or both.

Intersection (∩) : The intersection of two relations a and b, a  b, is
                   the set of all tuples t belonging to a and b.

Difference (-): The difference between two relations a and b in that
                order, a - b, is the set of all tuples t belonging to a 
                and not to B.

Relational Algebra
Example of Union, Intersection and Difference :

Consider the two relations A and B:

A :
SID Sname Subject
100 Ankit English
200 Pooja Math
300 Komal Science
(Table 1)
B :
ID Name Interest
100 Ankit English
400 Karishma Sanskrit
(Table 2)
Results :
Union : A ∪ B
SID Sname Subject
100 Ankit English
200 Pooja Math
300 Komal Science
400 Karishma Sanskrit
(Table 3)
Intersection :A ∩ B
SID Sname Subject
100 Ankit English
(Table 4)
Difference : A – B
SID Sname Subject
200 Pooja Math
300 Komal Science
(Table 5)

Product or Cross Product (×):

The product of two relations is a cartesian product and it is the concatenation of every tuple of one relation with every tuple of a second relation.
If the relation A has m tuples and the relation B has n tuple then A × B have m times n tuples.
If any one of R and S is empty, R × S ⇒ Φ

Example :

Consider the two relations Student and Enrollment :

Student :
SID Sname Subject Age
100 Ankit English 25
200 Pooja Math 24
300 Komal Science 19
(Table 6)
Enrollment :
SID CID EID
200 C001 2
300 C002 3
400 C004 4
(Table 7)

Student × Enrollment will have 3*2 = 6 tuples, which are :

Student × Enrollment
SID Sname Subject Age SID CID EID
100 Ankit English 25 200 C001 2
100 Ankit English 25 300 C002 3
100 Ankit English 25 400 C004 4
200 Pooja Math 24 200 C001 2
200 Pooja Math 24 300 C002 3
200 Pooja Math 24 400 C004 4
300 Komal Science 19 200 C001 2
300 Komal Science 19 300 C002 3
300 Komal Science 19 400 C004 4
(Table 8)
Need of Cross Product :
  1. In order to compare data of 2 tables like Student.SID>Enrollment.RollID
  2. To compare data within a table. (Student × Student).

Projection :

Projection is an operation that select specified attributes from a relation. It is used to filter the column . The result of the projection is a new relation having the selected attributes. It can also be used to change the order of attributes in a relation.

Syntax :

π<attribute list>(R)

Where π is the symbol of project operation, <attribute list> is a list of attributes from the relation R.

Example :

Consider the relation Student(SID,Sname,Subject,Age) in (Table 6).

πSname,Age(Student) and πSID,Subject(Student) :

 πSname,Age(Student)
Sname Age
Ankit 25
Pooja 24
Komal 19
(Table 9)
 πSID,Subject(Student) :
SID Subject
100 English
200 Math
300 Science
(Table 10)
Some points about projection operator :
  • The degree of output relation is equal to number of attributes mentioned in the attribute list.
  • Projection eliminates duplicates  automatically.
  • Commutative property cannot be applied for projection.

Select operator

Selection is an operation that select rows or tuples from a relation that satisfy a selection condition. The difference between the projection operator and the selection operator is that projection operator takes a vertical subset columns of a relation whereas the selection operator takes a horizontal subset of rows.

Syntax :

σ<Selection Condition>(R)

Where σ is the symbol of SELECT operation.
<Selection Condition> is a boolean expression specified on the attributes of relation R.

Characteristics of selection operator :
  • It is a unary operator.
  • Operation is applied to each tuple individually.
  • Degree of the relation from select operation is same as input relation.
  • It is commutative in nature.
  • The number of rows returned by selection operation is less than or equal to number of rows in original table.

Rename operator (ρ)

  • It is used to store the Intermediate result of any query.
  • Intermediate results are stored in a temporary table using assignment operator and it is renamed.
  • The rename operator can also be used to rename attributes.
  • Different Syntax of Rename Operator :
    Relational Algebra - Different Syntax of rename operator

Join operation

Join operation is used to join two tables. This operation is performed if both tables have similar column. The join operation is performed by doing the cartesian product, selection and possibly projection operations. Let us consider two relation A and B
The join of the relations A and B is as follows :

  • Form the product A, B i.e. A × B.
  • Do a selection to eliminate some tuples (the criteria for the selection are specified as part of the join).
  • Then optionally remove duplicate attributes with projection.
Syntax :
A⋈<Join Condition>B

Relational Algebra - Join

We join two tables based on conditions specified by the user.
Types of joins :
  • Inner Joins
    • Theta Join
    • Equi-join
    • Natural Join
  • Outer Joins
    • Left Outer Join
    • Right Outer Join
    • Full Outer Join
Inner Joins :

An inner join includes those tuples with matching attributes and the rest are discarded in the resulting relation.

Theta (θ) Join

Theta join combines tuples from different relations which satisfies the theta condition. Theta condition is denoted by the symbol θ.

Syntax :
R1 ⋈θ R2

where R1 is a relation having attributes (A1,A2,…,An) and R2 is another relation having attributes (B1, B2,.. ,Bn) such that the attributes don’t have anything in common, i.e. R1 ∩ R2 = Φ.

Relational Algebra - Theta Join

 

Theta join can use all kinds of comparison operators.

Equi-Join : Student⋈<Student.SID=Enrollment.SID>Enrollment

When Theta join uses only equality comparison operator, it is said to be equijoin. To form this Join, take the Cross Product of Student and Enrollment Relation which is calculated in (table  8)

Now, Selection of those tuples which satisfy the condition :

Student⋈<SID=RollID>Enrollment  : EQUI-JOIN
SID Sname Subject Age SID CID EID
200 Pooja Math 24 200 C001 2
300 Komal Science 19 300 C002 3
EQUI-JOIN
Natural Join (⋈)

The Natural Join is performed only if there is at least one common attribute exists between two relations. Also, the attributes must have the same name and domain. If we do the join operation as natural join, then eliminate one of the duplicate attributes in the Join Operation, So removing SID from Enrollment Table in performing the Join operation, we get :

Student⋈<SID=RollID>Enrollment  : NATURAL-JOIN
SID Sname Subject Age CID EID
200 Pooja Math 24 C001 2
300 Komal Science 19 C002 3
NATURAL-JOIN

It is possible to Join on condition other than equality; For example,

  • Student⋈<Student.SID<Enrollment.SID>Enrollment  : Greater-than-Join
  • Student⋈<Student.SID>Enrollment.SID>Enrollment  : Less-than-Join
Outer Joins :

An inner join includes only those tuples with matching attributes and the rest are discarded in the resulting relation. So, to include all the tuples from the participating relations in the resulting relation we need to use outer joins.

Left Outer Join (Left Outer Join)

Left Outer Join is equal to Natural Join except that all the tuples from the left side relation must include even if they are failed in join condition. The right side unmatched attributes of the resulting relation are made NULL.

Relational Algebra - Left Outer Join

Right Outer Join(Right Outer Join)

Right Outer Join is equal to Natural Join except that all the tuples from the right side relation must include even if they are failed in join condition. The left side unmatched attributes of the resulting relation are made NULL.

Relational Algebra - Right Outer Join

Full outer Join (Full Outer Join)

Full outer Join is equal to Left outer join as well as right outer join i.e. All the tuples from both relations are included in the resulting relation. If the tuples failed in the join condition for both relations, then their respective unmatched attributes are made NULL.

Relational Algebra - Full Outer Join

The DIVISION Operator

The division operator divides the dividend relation A of a degree m + n by a divisor relation B of degree n, and produces a result relation of degree m. The (m+i)th attribute of A and the ith attribute of B (i in the range 1 to n) must be define on the same domain. Consider the first m attribute of A as a single composite attribute X, and the last n as another Y; A may then B thought of as a set of pairs of values <x,y>. Similarly, B may be thought of as a set of single values . Then, the result of dividing A by B – i.e. A divide by B – is the set of values x S.T. the pair <x,y> appears in A for all values y appearacy in B. The attribute of the result have the same qualified names as the first m at attributed.

Example :

The division operator is applied basically where the phrase “for all” is used.

Consider two tables Enrolled(SID,CID) as E and Course(CID) as C.

SID CID
S1 C1
S1 C2
S1 C3
S2 C1
S2 C2
S3 C1
CID
C1
C2
C3

Query : Retrieve Students who are enrolled all courses.
Solution : E(SID,CID) / C(CID) : Result’s SID’s of the students who are enrolled all courses that specify in CID of ‘C’ table.

Relational Algebra - Division

The Assignment Operator :

  • The assignment operation (←) provides a convenient way to express complex queries.
  • Write query as a sequential program consisting of a series of assignments followed by an expression whose value is displayed as a result of the query.
  • Assignment must always be made to a temporary relation variable.
  • The result to the right of the ← is assigned to the relation variable on the left of the ←.
  • May use variable in subsequent expressions.
Example of Assignment Operator :

Consider the above DIVISION query :
Query : Retrieve students who are enrolled all courses.
Solution : E(SID,CID) / C(CID)

Step 1 : Taking Cross Product [πSID(E) × C] and assign the result to a
         temporary variable 'temp1' using assignment operator.
                Relational Algebra : Assignment Operator

Step 2 : 
Students who are not   =   Students enrolled -   Students who enrolled 
enrolled all courses         all courses       atleast one or any course 
         ⇓  
       temp2           ←       (temp1)                   (E)
(Storing the result
to another temporary
 variable 'temp2'
using assignment op.)
                     Relational Algebra : Assignment Operator

Step 3 : 
Students who are enrolled  = Students who enrolled - Students who are not
      all courses               every course            all courses
          ⇓
        temp3             ←      [π(E)]                   (temp2)
(Storing the result
to another temporary
 variable 'temp3'
using assignment op.)
                    Relational Algebra : Assignment Operator

A Complete Set of Relational Algebra Operations :

The set of operations {σ, π, ∪, -, ×} is a complete set. Hence, any of the other relational algebra operations can be expressed as a sequence of operations from this set.

For example:

  • ∩ : Intersection can also be written as :
    A∩B = A-(A-B) or
    A∩B = (A∪B) – ((A-B) ∪ (B-A))
  • ⋈ : The join operation can also be expressed as :
    A⋈<Join Condition>B =σ<Condition>(A × B)
  • The division ÷ operator can be expressed as (T ← A ÷ B) :
    T1 ←  πy(A)
    T2 ←  πy(B × T1) – A))
    T ← T1 – T2

Difference Between Relational Algebra and SQL

Relational Algebra SQL
It is a logical method to define a way to access data. It Is a database accessing language.
Operators allowed are : There are so many operators allowed including these three.
It do not supports GROUP BY and Aggregation Operation. It supports GROUP BY and Aggregation Operation.

Previous Home Next
Questions On SQL – Part 6 Questions on Relational Algebra (Part 1)

     

Incoming search terms:

  • difference between procedural and non procedural query language
  • difference between procedural and non procedural
  • procedural and non procedural dml
  • Procedural query language
  • difference between procedural and non procedural language
  • difference between procedural and non procedural dml in dbms
  • difference between procedural and non procedural DML
  • procedural language in dbms
  • difference between procedural dml and non procedural dml
  • difference between procedural and nonprocedural language in tabular form

Leave a Reply