+1(978)310-4246 credencewriters@gmail.com
  

COP 4710
Database Management
Instructor: Lenis Hernandez
Relational Algebra
Topics covered:
• Relational Algebra
• Unary Relational Operations
• Relational Algebra Operations From Set Theory
• Binary Relational Operations
• Additional Relational Operations
• Examples of Queries in Relational Algebra
Relational Algebra Overview
• Relational algebra is the basic set of operations for the relational
model
• These operations enable a user to specify basic retrieval requests (or
queries)
• The result of an operation is a new relation, which may have been
formed from one or more input relations
• This property makes the algebra “closed” (all objects in relational algebra are
relations)
Relational Algebra Overview (continued)
• The algebra operations thus produce new relations
• These can be further manipulated using operations of the same algebra
• A sequence of relational algebra operations forms a relational
algebra expression
• The result of a relational algebra expression is also a relation that
represents the result of a database query (or retrieval request)
Brief History of Origins of Algebra
• Muhammad ibn Musa al-Khwarizmi (800-847 CE) – from Morocco wrote a book
titled al-jabr about arithmetic of variables
• Book was translated into Latin.
• Its title (al-jabr) gave Algebra its name.
• Al-Khwarizmi called variables “shay”
• “Shay” is Arabic for “thing”.
• Spanish transliterated “shay” as “xay” (“x” was “sh” in Spain).
• In time this word was abbreviated as x.
• Where does the word Algorithm come from?
• Algorithm originates from “al-Khwarizmi”
• Reference: PBS (http://www.pbs.org/empires/islam/innoalgebra.html)
Relational Algebra Overview
• Relational Algebra consists of several groups of operations
• Unary Relational Operations
• SELECT (symbol:  (sigma))
• PROJECT (symbol:  (pi))
• RENAME (symbol:  (rho))
• Relational Algebra Operations From Set Theory
• UNION (  ), INTERSECTION (  ), DIFFERENCE (or MINUS, – )
• CARTESIAN PRODUCT ( x )
• Binary Relational Operations
• JOIN (several variations of JOIN exist)
• DIVISION
• Additional Relational Operations
• OUTER JOINS, OUTER UNION
• AGGREGATE FUNCTIONS (These compute summary of information: for example, SUM, COUNT,
AVG, MIN, MAX)
Database State for COMPANY
• All examples discussed below refer to the COMPANY database shown here.
Unary Relational Operations: SELECT
• The SELECT operation (denoted by  (sigma)) is used to select a subset of the tuples from a
relation based on a selection condition.
• The selection condition acts as a filter
• Keeps only those tuples that satisfy the qualifying condition
• Tuples satisfying the condition are selected whereas the other tuples are discarded
(filtered out)
• Examples:
• Select the EMPLOYEE tuples whose department number is 4:
 DNO = 4 (EMPLOYEE)
• Select the employee tuples whose salary is greater than $30,000:
 SALARY > 30,000 (EMPLOYEE)
Unary Relational Operations: SELECT
• In general, the select operation is denoted by  (R)
where
• the symbol  (sigma) is used to denote the select operator
• the selection condition is a Boolean (conditional) expression specified on the attributes
of relation R
• tuples that make the condition true are selected
• appear in the result of the operation
• tuples that make the condition false are filtered out
• discarded from the result of the operation
Unary Relational Operations: SELECT (continued)
• SELECT Operation Properties
• The SELECT operation  (R) produces a relation S that has the same
schema (same attributes) as R
• SELECT  is commutative:
•  ( < condition2> (R)) =  ( < condition1> (R))
• Because of commutativity property, a cascade (sequence) of SELECT operations may be
applied in any order:
• ( ( (R)) =  ( ( ( R)))
• A cascade of SELECT operations may be replaced by a single selection with a conjunction
of all the conditions:
• (< cond2> ((R)) =  AND < cond2> AND < cond3>(R)))
• The number of tuples in the result of a SELECT is less than (or equal to) the number
of tuples in the input relation R
The following query results refer to this database state
Unary Relational Operations: PROJECT
• PROJECT Operation is denoted by  (pi)
• This operation keeps certain columns (attributes) from a relation and
discards the other columns.
• PROJECT creates a vertical partitioning
• The list of specified columns (attributes) is kept in each tuple
• The other attributes in each tuple are discarded
• Example: To list each employee’s first and last name and salary, the
following is used:
LNAME, FNAME,SALARY(EMPLOYEE)
Unary Relational Operations: PROJECT (cont.)
• The general form of the project operation is:
(R)
•  (pi) is the symbol used to represent the project operation
• is the desired list of attributes from relation R.
• The project operation removes any duplicate tuples
• This is because the result of the project operation must be a set of tuples
• Mathematical sets do not allow duplicate elements.
Unary Relational Operations: PROJECT (contd.)
• PROJECT Operation Properties
• The number of tuples in the result of projection (R) is always less or
equal to the number of tuples in R
• If the list of attributes includes a key of R, then the number of tuples in the result of
PROJECT is equal to the number of tuples in R
• PROJECT is not commutative
•  ( (R) ) =  (R) as long as contains the attributes in
Examples of applying SELECT and PROJECT operations
Relational Algebra Expressions
• We may want to apply several relational algebra operations one after
the other
• Either we can write the operations as a single relational algebra expression
by nesting the operations, or
• We can apply one operation at a time and create intermediate result
relations.
• In the latter case, we must give names to the relations that hold
the intermediate results.
Single expression versus sequence of relational operations
(Example)
• To retrieve the first name, last name, and salary of all employees who work in
department number 5, we must apply a select and a project operation
• We can write a single relational algebra expression as follows:
• FNAME, LNAME, SALARY( DNO=5(EMPLOYEE))
• OR We can explicitly show the sequence of operations, giving a name to each
intermediate relation:
• DEP5_EMPS   DNO=5(EMPLOYEE)
• RESULT   FNAME, LNAME, SALARY (DEP5_EMPS)
Unary Relational Operations: RENAME
• The RENAME operator is denoted by  (rho)
• In some cases, we may want to rename the attributes of a relation or
the relation name or both
• Useful when a query requires multiple operations
• Necessary in some cases (see JOIN operation later)
Unary Relational Operations: RENAME (continued)
• The general RENAME operation  can be expressed by any of the
following forms:
• S (B1, B2, …, Bn )(R) changes both:
• the relation name to S, and
• the column (attribute) names to B1, B1, …..Bn
• S(R) changes:
• the relation name only to S
• (B1, B2, …, Bn )(R) changes:
• the column (attribute) names only to B1, B1, …..Bn
Unary Relational Operations: RENAME (continued)
• For convenience, we also use a shorthand for renaming attributes in
an intermediate relation:
• If we write:
• RESULT   FNAME, LNAME, SALARY (DEP5_EMPS)
• RESULT will have the same attribute names as DEP5_EMPS (same
attributes as EMPLOYEE)
• If we write:
• RESULT (F, M, L, S, B, A, SX, SAL, SU, DNO)
 RESULT (F.M.L.S.B,A,SX,SAL,SU,
DNO)(DEP5_EMPS)
• The 10 attributes of DEP5_EMPS are renamed to F, M, L, S, B, A, SX,
SAL, SU, DNO, respectively
Note: the  symbol is an assignment operator
Example of applying multiple operations and RENAME
Relational Algebra Operations from Set Theory: UNION
• UNION Operation
• Binary operation, denoted by 
• The result of R  S, is a relation that includes all tuples that are either in R or
in S or in both R and S
• Duplicate tuples are eliminated
• The two operand relations R and S must be “type compatible” (or UNION
compatible)
• R and S must have same number of attributes
• Each pair of corresponding attributes must be type compatible (have same or
compatible domains)
Relational Algebra Operations from Set Theory: UNION
• Example:
• To retrieve the social security numbers of all employees who either work in department
5 (RESULT1 below) or directly supervise an employee who works in department 5
(RESULT2 below)
• We can use the UNION operation as follows:
DEP5_EMPS  DNO=5 (EMPLOYEE)
RESULT1   SSN(DEP5_EMPS)
RESULT2(SSN)  SUPERSSN(DEP5_EMPS)
RESULT  RESULT1  RESULT2
• The union operation produces the tuples that are in either RESULT1 or RESULT2 or both
Figure 8.3 Result of the UNION
operation RESULT ← RESULT1 ∪ RESULT2.
Relational Algebra Operations from Set Theory
• Type Compatibility of operands is required for the binary set operation UNION ,
(also for INTERSECTION , and SET DIFFERENCE –, see next slides)
• R1(A1, A2, …, An) and R2(B1, B2, …, Bn) are type compatible if:
• they have the same number of attributes, and
• the domains of corresponding attributes are type compatible (i.e. dom(Ai)=dom(Bi)
for i=1, 2, …, n).
• The resulting relation for R1R2 (also for R1R2, or R1–R2, see next slides) has
the same attribute names as the first operand relation R1 (by convention)
Relational Algebra Operations from Set Theory: INTERSECTION
• INTERSECTION is denoted by 
• The result of the operation R  S, is a relation
that includes all tuples that are in both R and S
• The attribute names in the result will be the
same as the attribute names in R
• The two operand relations R and S must be
“type compatible”
Relational Algebra Operations from Set Theory: SET DIFFERENCE
• SET DIFFERENCE (also called MINUS or EXCEPT) is
denoted by –
• The result of R – S, is a relation that includes all tuples
that are in R but not in S
• The attribute names in the result will be the
same as the attribute names in R
• The two operand relations R and S must be
“type compatible”
Example to illustrate the result of UNION, INTERSECT, and
DIFFERENCE
Some properties of UNION, INTERSECT, and DIFFERENCE
• Notice that both union and intersection are commutative operations; that is
• R  S = S  R, and R  S = S  R
• Both union and intersection can be treated as n-ary operations applicable to any
number of relations as both are associative operations; that is
• R  (S  T) = (R  S)  T
• (R  S)  T = R  (S  T)
• The minus operation is not commutative; that is, in general
• R–S≠S–R
Relational Algebra Operations from Set Theory: CARTESIAN
PRODUCT
• CARTESIAN (or CROSS) PRODUCT Operation
• This operation is used to combine tuples from two relations in a combinatorial
fashion.
• Denoted by R(A1, A2, . . ., An) x S(B1, B2, . . ., Bm)
• Result is a relation Q with degree n + m attributes:
• Q(A1, A2, . . ., An, B1, B2, . . ., Bm), in that order.
• The resulting relation state has one tuple for each combination of tuples—one from
R and one from S.
• Hence, if R has nR tuples (denoted as |R| = nR ), and S has nS tuples, then R x S will
have nR * nS tuples.
• The two operands do NOT have to be “type compatible”
Relational Algebra Operations from Set Theory: CARTESIAN
PRODUCT (cont.)
• Generally, CROSS PRODUCT is not a meaningful operation
• Can become meaningful when followed by other operations
• Example (not meaningful):
• FEMALE_EMPS   SEX=’F’(EMPLOYEE)
• EMPNAMES   FNAME, LNAME, SSN (FEMALE_EMPS)
• EMP_DEPENDENTS  EMPNAMES x DEPENDENT
• EMP_DEPENDENTS will contain every combination of EMPNAMES and
DEPENDENT
• whether or not they are actually related
Relational Algebra Operations from Set Theory: CARTESIAN
PRODUCT (cont.)
• To keep only combinations where the DEPENDENT is related to the
EMPLOYEE, we add a SELECT operation as follows
• Example (meaningful):
• FEMALE_EMPS   SEX=’F’(EMPLOYEE)
• EMPNAMES   FNAME, LNAME, SSN (FEMALE_EMPS)
• EMP_DEPENDENTS  EMPNAMES x DEPENDENT
• ACTUAL_DEPS   SSN=ESSN(EMP_DEPENDENTS)
• RESULT   FNAME, LNAME, DEPENDENT_NAME (ACTUAL_DEPS)
• RESULT will now contain the name of female employees and their dependents
Figure 8.5 The CARTESIAN PRODUCT (CROSS
PRODUCT) operation.
continued on next slide
Figure 8.5 (continued)
.
The CARTESIAN PRODUCT (CROSS
PRODUCT) operation
continued on next slide
Figure 8.5 (continued)
PRODUCT) operation.
The CARTESIAN PRODUCT (CROSS
Binary Relational Operations: JOIN
• JOIN Operation (denoted by
)
• The sequence of CARTESIAN PRODECT followed by SELECT is used quite commonly to
identify and select related tuples from two relations
• A special operation, called JOIN combines this sequence into a single operation
• This operation is very important for any relational database with more than a single
relation, because it allows us combine related tuples from various relations
• The general form of a join operation on two relations R(A1, A2, . . ., An) and S(B1, B2,
. . ., Bm) is:
R S
• where R and S can be any relations that result from general relational algebra
expressions.
Binary Relational Operations: JOIN (cont.)
• Example: Suppose that we want to retrieve the name of the
manager of each department.
• To get the manager’s name, we need to combine each
DEPARTMENT tuple with the EMPLOYEE tuple whose SSN value
matches the MGRSSN value in the department tuple.
• We do this by using the join
operation.
• DEPT_MGR  DEPARTMENT MGRSSN=SSN EMPLOYEE
• MGRSSN=SSN is the join condition
• Combines each department record with the employee who
manages the department
• The join condition can also be specified as DEPARTMENT.MGRSSN=
EMPLOYEE.SSN
Figure 8.6 Result of the JOIN operation
DEPT_MGR ← DEPARTMENT|X| Mgr_ssn=SsnEMPLOYEE.
Some properties of JOIN
• Consider the following JOIN operation:
• R(A1, A2, . . ., An)
S(B1, B2, . . ., Bm)
R.Ai=S.Bj
• Result is a relation Q with degree n + m attributes:
• Q(A1, A2, . . ., An, B1, B2, . . ., Bm), in that order.
• The resulting relation state has one tuple for each combination of tuples—r from R
and s from S, but only if they satisfy the join condition r[Ai]=s[Bj]
• Hence, if R has nR tuples, and S has nS tuples, then the join result will generally have
less than nR * nS tuples.
• Only related tuples (based on the join condition) will appear in the result
Some properties of JOIN
• The general case of JOIN operation is called a Theta-join: R
S
theta
• The join condition is called theta
• Theta can be any general boolean expression on the attributes of R
and S; for example:
• R.Ai
Purchase answer to see full
attachment

  
error: Content is protected !!