The Relational Algebra

• The relational algebra is a procedural query language.




• It consists of a set of operations that take one or two relations as input and produce a new relation as their result.




• The fundamental operations in the relational algebra are :




1. select

2. project

3. union

4. set difference

5. Cartesian product

6. rename




• The select, project, and rename operations are called unary operations, because they operate on one relation. The other three operations operate on pairs of relations and are, therefore, called binary operations.




• Additional operations:




1. set intersection

2. natural join

3. assignment

The Select Operation

• The select operation selects tuples that satisfy a given predicate. We use the lowercase Greek letter sigma (σ) to denote selection.




• The predicate appears as a subscript to σ.




• The argument relation is in parentheses after the σ.




• In general, we allow comparisons using =, ≠, <, ≤, > and ≥ in the selection predicate. Furthermore, we can combine several predicates into a larger predicate by using the connectives and (∧), or (∨), and not (¬).




• In relational algebra, the term select corresponds to what we refer to in SQL as where.

Q . To select those tuples of the instructor relation where the instructor is in the “Physics” department. [ Hint : instructor (ID, name, dept_name, salary) ]

• σ_{dept_name = "Physics"}(instructor)

Q . To find all instructors with salary greater than $90,000. [ Hint : instructor (ID, name, dept_name, salary) ]

• σ_{salary > 90000}(instructor)

Q . To find the instructors in Physics with a salary greater than $90,000. [ Hint : instructor (ID, name, dept_name, salary) ]

• σ_{dept_name = "Physics" ∧ salary > 90000}(instructor)

The Project Operation

• The project operation is a unary operation that returns its argument relation with certain attributes left out.




• Since a relation is a set, any duplicate rows are eliminated.




• Projection is denoted by the uppercase Greek letter pi (∏).




• We list those attributes that we wish to appear in the result as a subscript to ∏. The argument relation follows in parentheses.

Q . To Find the id, salary, name of all instructors. [ Hint : instructor (ID, name, dept_name, salary) ]

• ∏ _{ID, name, salary} (instructor).

Q . Find the name of all instructors in the Physics department. [ Hint : instructor (ID, name, dept_name, salary) ]

• ∏ _name (σ _{dept_name =“Physics”}(instructor))

The Union Operation :

• When we need the union of these two sets; that is, we need all tuples that appear in either or both of the two relations.




• Binary operation union, is denoted, as in set theory, by ∪




• Therefore, for a union operation r ∪ s to be valid, we require that two conditions hold:




1. The relations r and s must be of the same arity. That is, they must have the same number of attributes.




2. The domains of the i^th attribute of r and the i^th attribute of s must be the same, for all 'i'.

Q . To Find the set of all courses taught in the Fall 2009 semester, the Spring 2010 semester, or both. [ Hint : section ( course_id, sec_id, semester, year, building, room_number, time_slot_id ) ]

• ∏ _{course_id} (σ _{semester =“Fall”} ∧ _{year = 2009} (section)) ∪ ∏ _{course_id} (σ _{semester =“Spring”} ∧ _{year = 2010} (section))

The Set-Difference Operation

• The set-difference operation, denoted by −, allows us to find tuples that are in one relation but are not in another.




• The expression r − s produces a relation containing those tuples in r but not in s.




• As with the union operation, we must ensure that set differences are taken between compatible relations.




• Therefore, for a set-difference operation r − s to be valid, we require that the relations r and s be of the same arity, and that the domains of the ith attribute of r and the ith attribute of s be the same, for all 'i'.

To find all the courses taught in the Fall 2009 semester but not in Spring 2010 semester [ Hint : section ( course_id, sec_id, semester, year, building, room_number, time_slot_id ) ]

• ∏ _{course_id} (σ _{semester =“Fall”} ∧ _{year = 2009} (section)) - ∏ _{course_id} (σ _{semester =“Spring”} ∧ _{year = 2010} (section))

The Cartesian-Product Operation

• The Cartesian-Product Operation denoted by ✕ allows us to combine information from any two relations. We write the Cartesian product of relations r₁ ✕ r₂.




• Suppose we have teaches(ID, course_id, sec_id, semester, year) as r₁ and instructor(ID, name, dept name, salary) as r₂.




• Then r₁ ✕ r₂ gives a relation with rows equal to n₁ * n₂ where n₁ is rows in r₁ and n₂ is rows in r₂.

To find the names of all instructors in the Physics department together with the course id of all courses they taught. [ Hint : instructor ( ID, name, dept name, salary ) and teaches ( ID, course id, sec id, semester, year ) ]

• σ_{dept_name = "Physics"} (instructor ✕ teaches)

To find the names of all instructors in the Physics department together with the course id of all courses they taught. [ Hint : instructor ( ID, name, dept name, salary ) and teaches ( ID, course id, sec id, semester, year ) ]

• First query is to create all combinations of teachers and courses




• σ_{dept_name = "Physics"} (instructor ✕ teaches)




• Second query selects only instructors and the courses that they have taught



• σ _{instructor.ID = teaches.ID}(σ_{dept_name = "Physics"} (instructor ✕ teaches))




• Project only names and course_id of the second query.




• ∏_{name, course_id}(σ _{instructor.ID = teaches.ID}(σ_{dept_name = "Physics"} (instructor ✕ teaches)))

The Rename Operation

• Unlike relations in the database, the results of relational-algebra expressions do not have a name that we can use to refer to them.




• It is useful to be able to give them names; the rename operator, denoted by the lowercase Greek letter rho (ρ)




• Given a relational-algebra expression E, the expression returns the result of expression E under the name x.




1. ρ_x(E)

Additional Relational - Algebra Operations

• Additional operations do not add any power to the algebra, but simplify common queries.




• The Set-Intersection Operation (∩):




1. To find the set of all courses taught in both the Fall 2009 and the Spring 2010 semesters.




2. ∏ _{course_id} (σ _{semester =“Fall”} ∧ _{year = 2009} (section)) ∩ ∏ _{course_id} (σ _{semester =“Spring”} ∧ _{year = 2010} (section))




• The Natural-Join Operation (⨝):




1. The natural join is a binary operation that allows us to combine certain selections and a Cartesian product into one operation.




2. The natural-join operation forms a Cartesian product of its two arguments, performs a selection forcing equality on those attributes that appear in both relation schemas, and finally removes duplicate attributes.




3. Computing instructor natural join teaches considers only those pairs of tuples where both the tuple from instructor and the tuple from teaches have the same value on the common attribute ID.




4. ∏_{name, course_id}(instructor ⨝ teaches)




• The Assignment Operation (←)




1. The assignment operation, denoted by ←, works like assignment in a programming language




2. temp1 ← R ✕ S
   result = ∏ R ∪ S(temp1)




3. For relational-algebra queries, assignment must always be made to a temporary relation variable. Assignments to permanent relations constitute a database modification.




• Outer join Operations :




1. There are three forms of the operation: left outer join, denoted by [⟕] ; right outer join, denoted by [⟖] ; and full outer join, denoted by [⟗] .

Find the names of all instructors in the Comp. Sci. department together with the course titles of all the courses that the instructors teach. [ Hint : instructor ( ID, name, dept name, salary ) , teaches ( ID, course id, sec id, semester, year ) , course ( course_id, title, dept_name, credits ) ]

• ∏_{name, title}(σ _{dept_name = "Comp.Sci"} (instructor ⨝ teaches ⨝ course))




• Note: Natural join is associative and so (instructor ⨝ teaches) ⨝ course and instructor ⨝ (teaches ⨝ course) are equivalent.

Demonstrate Outer join Operations.

• instructor ⟕ teaches takes all tuples in the left relation that did not match with any tuple in the right relation, pads the tuples with null values for all other attributes from the right relation, and adds them to the result of the natural join.




• instructor ⟖ teaches pads tuples from the right relation that did not match any from the left relation with nulls and adds them to the result of the natural join.




• instructor ⟗ teaches padding tuples from the left relation that did not match any from the right relation, as well as tuples from the right relation that did not match any from the left relation, and adding them to the result of the join.

Extended Relational-Algebra Operations

• These operations provide the ability to write queries that cannot be expressed using the basic relational-algebra operations.




• Generalized Projection :




1. It extends the projection operation by allowing operations such as arithmetic and string functions to be used in the projection list.




2. Example : ∏_{F1, F2, ... , Fn}(E)




3. ∏_{ID, name, salary + 100}(instructor). It provides addition of 100 to the salaries of the instructors.




• Aggregation (G) i.e. "calligraphic G":




1. It permits the use of aggregate functions such as min or average, on sets of values.




2. They take a collection of values and return a single value as a result.




3. Types of aggregate functions are :




1. sum : G_sum(salary)(instructor)

2. average : G_{average(salary)}(instructor)

3. count : G_{count(dept_name)}(instructor)

4. count-distinct : G_{count-distinct(ID)}(σ_{semester = "spring" ∧ year = 2009}(teaches))

5. min : G_min(salary)(instructor)

6. max : G_max(salary)(instructor)

The general form of the aggregation operation G is as follows:

• _{G1, G2,...,Gn}G_{F1(A1), F2(A2),...,Fn(An)}(E)




• E is any relational-algebra expression;




• G1, G2,...,Gn constitute a list of attributes on which to group.




• all F's are aggregate functions and all A's are attribute names.

Q. Find the average salary in each department [ Hint : instructor ( ID, name, dept_name, salary ) ]

• _{dept_name}G_{average(salary)}(instructor)

Previous

Next