Relational algebra

Relational algebra
Objectives
• How to form queries in relational algebra
Introduction
• Similar to normal algebra (as in 2+3*x-y), except we use
relations as values instead of numbers, and the
operations and operators are different.
• Not used as a query language in actual DBMSs. (SQL
instead.)
• The inner, lower-level operations of a relational DBMS
are, or are similar to, relational algebra operations. We
need to know about relational algebra to understand
query execution and optimization in a relational DBMS.
• Some advanced SQL queries requires explicit relational
algebra operations, most commonly outer join.
• Relations are seen as sets of tuples, which means that
no duplicates are allowed. SQL behaves differently in
some cases. Remember the SQL keyword distinct.
• SQL is declarative, which means that you tell the
DBMS what you want, but not how it is to be
calculated. A C++ or Java program is procedural, which
means that you have to state, step by step, exactly how
the result should be calculated. Relational algebra is
(more) procedural than SQL. (Actually, relational
algebra is mathematical expressions.)
Relational Algebra
• Relational algebra is high level procedural
language
• Relational algebra operations work on one or
more relations to define another relation with
out changing original relations
• Both operands and results are relations
– Output from one relation can be input to another
• Allows nested expressions
– Closure property
Review of concepts and operations from set theory
• set
• element
• no duplicate elements (but: multiset = bag)
• no order among the elements (but: ordered set)
• subset
• proper subset (with fewer elements)
• superset
• union
• intersection
• set difference
• cartesian product
Relational Algebra
• Basic operations
– Selection, Projection, Union, Set difference,
Cartesian product and Rename
• Perform most required data retrieval
operations
• Additional operations
– join, set intersection, Division and assignment
– Can be expressed in terms of the basic operations.
Basic Operations
• Unary operators: operate on one relation

– Selection, Projection, Rename
• Binary operators: operate on pairs of relations
– Union, Set Difference, Cartesian product
• The result of an operation is a new relation.
Selection(or Restriction)
• We use the Greek letter sigma () for the operator.
• The predicate has a comparison operator (>, <, =,  (not

equal), ,  ).
• You can compare values in different attributes or compare an
attribute to a constant value.
• It can also include logical AND, OR and NOT operators: , , .
Example –Selection(or restriction)
Projection
• We use the greek letter Pi for the operand
()
Example- Projection
How selection and projection are used in
SQL ?
Select *
From Staff
Where Salary >10,000;
• What part is equivalent to a relational algebra
select operation – can you see an argument
relation and a predicate?
• What part is equivalent to the project operation?
SELECT staffNO, fName,lName,Salary
From Staff;
Union
• When doing a union operation:

– Must use compatible relations – it must make sense to union the 2 relations. For
example, it does not make sense to union the student and course relations.
– The relations being union-ed must have the same number of attributes – we say
that the relations have the same arity.
– The domains of the corresponding attributes must be the same. In other words:
for r  s, the domain of the ith attribute of r must be the same domain as that for
the ith attribute of s.
Exercise- Union
• list of all student and teacher names, along with their
email addresses
Teacher-Schema (teacherid, teacher_firstname,
teacher_fathersname, teacher_email)
Student-schema = (student_id, student_firstname,
student_fathersname, programme_code, student_email)
student_firstname, student_fathersname, student_email (student)

teacher_firstname, teacher_fathersname, teacher_email (teacher)
Set-Difference
Example-Set difference
• find students who are taking the ICT252
course but who are not taking the ICT231
course ?
• get a relation showing students taking ICT252 – just get the
student ID
student_id (course_code=”ICT252” (studentCourse))
• get a relation showing students taking ICT231 – should be
compatible with the first relation:
• Now we can get the difference between these two:

student_id (course_code=”ICT252” (studentCourse)) –
Cartesian Product
• The result is a relation that has all the

attributes from both relations and whose
tuples are all the possible combinations of the
tuples from each of the 2 relations.
• so if we have n tuples in R and m tuples in S,
r(RxS) contains (n x m) tuples.
Example-Cartesian Product
r=Student X Programme
• The attributes in r are:
(student.stud_id, student.stud_firstname,
student.stud_fathersname,
student.prog_code, programme.prog_code,
programme.prog_name,
programme.prog_desc)
Example-on Cartesian product, selection
and projection
Get name of all students on the Computer
Science Degree programme ?
R= stud_firstname,stud_fathersname
(student.prog_code=programme.prog_code (
prog_name=”Computer Science Degree” (student x
programme)
))
• Cartesian product and selection can be used
to reduced to single operation join
• Write an expression to get a list of all students
taking the course ICT252 – the list should
show each student’s full name.
R = stud_firstname,stud_fathersname
(student.stud_id=studentCourse.stud_id (
course_code=”ICT252” (student x studentCourse)
))
Rename
• x(E)
• To rename the relation given by an expression
E to the name x:
Example- Rename
• csdeg_students (programme_code=”CSDEG” (student))
– The operation returns the relation given by the expression, and the relation
is named csdeg_students. Can now use that name in further operations.
• To find any students named Solomon who are on the CSDEG
programme:
– stud_firstname=”Solomon” ( csdeg_students (programme_code=”CSDEG” (student)))
• Or, can simply rename a relation, as a relation is itself a trivial
relational algebra expression:
– student2(student)
• We can also rename the attributes in the relation, using syntax like
this: x (A1,A2,….An)(E)
– If the expression E has arity n (n attributes); A1 is a name for the first
attribute, An is a name for the nth attribute.
Example- Rename
find a course with highest credit hours
• course.credit_hours (course) –
• course.credit_hours (course.credit_hours < c.credit_hours (course
x c(course)))
Additional Operations
• The basic relational algebra operators that we have just

looked at are sufficient to express any relational algebra
query.
• But even with these, some types of common query that we
make on relations become complex and lengthy to express.
• To make some of these easier, there some additional
operations that simplify some common types of query. These
are:
– Set intersection
– Join
– Division
– Assignment
Intersection
• (r – s) gives tuples that are in r but not in s.

• If we take those tuples away from r, we are left
with only tuples that are in r and in s.
• It is easier just to use .
Example- Intersection
• Write an expression which will find students
are taking the course ICT252 and ICT231.
This can be viewed as the intersection of 2 sets
or relations:
stud_id (course_code=”ICT252” (studentCourse))

stud_id (course_code=”ICT231” (studentCourse))
Join Operations
Various forms of join operations
• Inner Joins: only those tuples that satisfy the matching criteria
are included, while the rest are excluded.
– Theta join
– EQUI join(a particular theta join)
– Natural join
• Outer join: along with tuples that satisfy the matching criteria,
we also include some or all tuples that do not match the criteria.
– Left Outer Join
– Right Outer Join
– Full Outer Join
– Semi join

Relational algebra

Uploaded by

Copyright:

Available Formats

Relational algebra

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Relational algebra

Uploaded by

Copyright:

Available Formats

Relational algebra

• Unary operators: operate on one relation

• The predicate has a comparison operator (>, <, =,  (not

• When doing a union operation:

• Now we can get the difference between these two:

• The result is a relation that has all the

• The basic relational algebra operators that we have just

• (r – s) gives tuples that are in r but not in s.

You might also like