Relational Algebra

What You'll Learn This Week

• Relational Algebra
  • Set Theoretic Operations
  • Union, Intersection and Difference
  • Union Compatible Relations
  • Cartesian Product
  • Selection and Projection
    • Selection Operator
    • Selection Examples
    • Projection Operator
    • Projection Examples
    • Combining Selection and Projection
  • Aggregate Functions
  • Join Operations
    • Join Examples
    • Natural Join
    • Outer Join
  • Outer Union
• How to make Relational Algebra Symbols in MS Word

Relational Algebra

Elmasri/Navathe (3rd) ed.	Kroenke (7th ed.)	Connolly/Begg (3rd Ed.)	Rob/Coronel (5th ed)	Hoffer, Prescott & McFadden (6th ed.)	Mata-Toledo / Cushman
Chapter 7	Chapter 8	Chapter 4	N/A	N/A	Shaum's Outlines Ch. 2

• Recall, the Relational Model consists of the elements: relations, which are made up of attributes.
• A relation is a set of attributes with values for each attribute such that:
  1. Each attribute value must be a single value only (atomic).
  2. All values for a given attribute must be of the same type (or domain).
  3. Each attribute name must be unique.
  4. The order of attributes is insignificant
  5. No two rows (tuples) in a relation can be identical.
  6. The order of the rows (tuples) is insignificant.

• Relational Algebra is a collection of operations on Relations.
• Relations are operands and the result of an operation is another relation.
• Two main collections of relational operators:
  1. Set theory operations:
     Union, Intersection, Difference and Cartesian product.
  2. Specific Relational Operations:
     Selection, Projection, Join, Division

Set Theoretic Operations

• Union: R S
  Result: Relation with tuples from R and S with duplicates removed.

• Difference: R - S
  Result: Relation with tuples from R but not from S

• Intersection: R S
  Result: Relation with tuples that appear in both R and S.

R S

First	Last	Age
Bill	Smith	22
Sally	Green	28
Mary	Keen	23
Tony	Jones	32
Forrest	Gump	36
DonJuan	DeMarco	27

R - S

First	Last	Age
Bill	Smith	22
Mary	Keen	23
Tony	Jones	32

R S

First	Last	Age
Sally	Green	28

Union Compatible Relations

• Attributes of relations need not be identical to perform union, intersection and difference operations.

• However, they must have the same number of attributes or arity and the domains for corresponding attributes must be identical.

• Domain is the datatype and size of an attribute.

• The degree of relation R is the number of attributes it contains.

• Definition: Two relations R and S are union compatible if and only if they have the same degree and the domains of the corresponding attributes are the same.

• Some additional properties:
  • Union, Intersection and difference operators may only be applied to Union Compatible relations.
  • Union and Intersection are commutative operations
    R S = S R
    R S = S R
  • Difference operation is NOT commutative.
    R - S not equal S - R
  • The resulting relations may not have meaningful names for the attributes. Convention is to use the attribute names from the first relation.

Cartesian Product

• Produce all combinations of tuples from two relations.
  

  R

  First	Last	Age
  Bill	Smith	22
  Mary	Keen	23
  Tony	Jones	32

  S

  Dinner	Dessert
  Steak	Ice Cream
  Lobster	Cheesecake

  R X S

  First	Last	Age	Dinner	Dessert
  Bill	Smith	22	Steak	Ice Cream
  Bill	Smith	22	Lobster	Cheesecake
  Mary	Keen	23	Steak	Ice Cream
  Mary	Keen	23	Lobster	Cheesecake
  Tony	Jones	32	Steak	Ice Cream
  Tony	Jones	32	Lobster	Cheesecake

Selection Operator

• Selection and Projection are unary operators.
• The selection operator is sigma:
• The selection operation acts like a filter on a relation by returning only a certain number of tuples.
• The resulting relation will have the same degree as the original relation.
• The resulting relation may have fewer tuples than the original relation.
• The tuples to be returned are dependent on a condition that is part of the selection operator.
• C (R) Returns only those tuples in R that satisfy condition C
• A condition C can be made up of any combination of comparison or logical operators that operate on the attributes of R.
  • Comparison operators:
  • Logical operators:
• Use the Truth tables (memorize these) for logical expressions:

  T F T T F F F F

  T F T T T F T F

  T F F T

Selection Examples

Name	Office	Dept	Rank
Smith	400	CS	Assistant
Jones	220	Econ	Adjunct
Green	160	Econ	Assistant
Brown	420	CS	Associate
Smith	500	Fin	Associate

• Select only those Employees in the CS department:
  _{Dept = 'CS'} (EMP)
  Result:
  

  Name	Office	Dept	Rank
  Smith	400	CS	Assistant
  Brown	420	CS	Associate

• Select only those Employees with last name Smith who are assistant professors:
  _{Name = 'Smith' Rank = 'Assistant'} (EMP)
  Result:
  

  Name	Office	Dept	Rank
  Smith	400	CS	Assistant

• Select only those Employees who are either Assistant Professors or in the Economics department:
  _{Rank = 'Assistant' Dept = 'Econ'} (EMP)
  Result:
  

  Name	Office	Dept	Rank
  Smith	400	CS	Assistant
  Jones	220	Econ	Adjunct
  Green	160	Econ	Assistant

• Select only those Employees who are not in the CS department or Adjuncts:
  _{(Rank = 'Adjunct' Dept = 'CS')} (EMP)
  Result:
  

  Name	Office	Dept	Rank
  Green	160	Econ	Assistant
  Smith	500	Fin	Associate

Exercises

• Evaluate the following expressions:
  
  1. _{(Rank = 'Adjunct' Dept = 'CS')} (EMP)
     
  2. _{Rank = 'Associate'} ( _{Dept = 'CS'} EMP )
  3. _{Dept = 'CS'} ( _{Rank = 'Associate'} EMP )
  4. _{Rank = 'Associate' Dept = 'CS'} (EMP)
  5. _{Age > 26} (R S)

     For this expression, use R and S from the Set Theoretic Operations section above.

• Do expressions 2, 3 and 4 above all evaluate ot the same thing?

Projection Operator

• Projection is also a Unary operator.
• The Projection operator is pi:
• Projection limits the attributes that will be returned from the original relation.
• The general syntax is: _attributes R
  Where attributes is the list of attributes to be displayed and R is the relation.
• The resulting relation will have the same number of tuples as the original relation (unless there are duplicate tuples produced).
• The degree of the resulting relation may be equal to or less than that of the original relation.

Projection Examples

• Project only the names and departments of the employees:
  _{name, dept} (EMP)
  Results:
  

  Name	Dept
  Smith	CS
  Jones	Econ
  Green	Econ
  Brown	CS
  Smith	Fin

Combining Selection and Projection

• The selection and projection operators can be combined to perform both operations.

• Show the names of all employees working in the CS department:
  _name ( _{Dept = 'CS'} (EMP) )
  Results:

  Name
  Smith
  Brown

• Show the name and rank of those Employees who are not in the CS department or Adjuncts:
  _{name, rank} ( _{(Rank = 'Adjunct' Dept = 'CS')} (EMP) )
  Result:
  

  Name	Rank
  Green	Assistant
  Smith	Associate

Exercises

• Evaluate the following expressions:
  
  1. _{name, rank} ( _{(Rank = 'Adjunct' Dept = 'CS')} (EMP) )
     
  2. _{fname, age} ( _{Age > 22} (R S) )

     For this expression, use R and S from the Set Theoretic Operations section above.

  3. _{office > 300} ( _{name, rank} (EMP))

Aggregate Functions

• We can also apply Aggregate functions to attributes and tuples:
  
  • SUM
  • MINIMUM
  • MAXIMUM
  • AVERAGE, MEAN, MEDIAN
  • COUNT
• Aggregate functions are sometimes written using the Projection operator or the Script F character: as in the Elmasri/Navathe book.

Aggregate Function Examples

Name	Office	Dept	Salary
Smith	400	CS	45000
Jones	220	Econ	35000
Green	160	Econ	50000
Brown	420	CS	65000
Smith	500	Fin	60000

• Find the minimum Salary: _{MIN (salary)} (EMP)
  Results:
  

  MIN(salary)
  35000

• Find the average Salary: _{AVG (salary)} (EMP)
  Results:
  

  AVG(salary)
  51000

• Count the number of employees in the CS department: _{COUNT (name)} ( _{Dept = 'CS'} (EMP) )
  Results:
  

  COUNT(name)
  2

• Find the total payroll for the Economics department: _{SUM (salary)} ( _{Dept = 'Econ'} (EMP) )
  Results:
  

  SUM(salary)
  85000

Join Operation

• Join operations bring together two relations and combine their attributes and tuples in a specific fashion.
• The generic join operator (called the Theta Join is:
• It takes as arguments the attributes from the two relations that are to be joined.
• For example assume we have the EMP relation as above and a separate DEPART relation with (Dept, MainOffice, Phone) :
  EMP _{EMP.Dept = DEPART.Dept} DEPART

• The join condition can be
• When the join condition operator is   =   then we call this an Equijoin
• Note that the attributes in common are repeated.

Join Examples

• Find all information on every employee including their department info:
  EMP _{emp.Dept = depart.Dept} DEPART
  Results:
  

  Name	Office	EMP.Dept	Salary	DEPART.Dept	MainOffice	Phone
  Smith	400	CS	45000	CS	404	555-1212
  Jones	220	Econ	35000	Econ	200	555-1234
  Green	160	Econ	50000	Econ	200	555-1234
  Brown	420	CS	65000	CS	404	555-1212
  Smith	500	Fin	60000	Fin	501	555-4321

• Find all information on every employee including their department info where the employee works in an office numbered less than the department main office:
  EMP _{(emp.office < depart.mainoffice) (emp.dept = depart.dept)} DEPART
  Results:
  

  Name	Office	EMP.Dept	Salary	DEPART.Dept	MainOffice	Phone
  Smith	400	CS	45000	CS	404	555-1212
  Green	160	Econ	50000	Econ	200	555-1234
  Smith	500	Fin	60000	Fin	501	555-4321

Natural Join

• Notice in the generic (Theta) join operation, any attributes in common (such as dept above) are repeated.
• The Natural Join operation removes these duplicate attributes.
• The natural join operator is: *
• We can also assume using * that the join condition will be = on the two attributes in common.

• Example: EMP * DEPART
  Results:
  

  Name	Office	Dept	Salary	MainOffice	Phone
  Smith	400	CS	45000	404	555-1212
  Jones	220	Econ	35000	200	555-1234
  Green	160	Econ	50000	200	555-1234
  Brown	420	CS	65000	404	555-1212
  Smith	500	Fin	60000	501	555-4321

Outer Join

• In the Join operations so far, only those tuples from both relations that satisfy the join condition are included in the output relation.
• The Outer join includes other tuples as well according to a few rules.
• Three types of outer joins:
  1. Left Outer Join includes all tuples in the left hand relation and includes only those matching tuples from the right hand relation.
  2. Right Outer Join includes all tuples in the right hand relation and includes ony those matching tuples from the left hand relation.
  3. Full Outer Join includes all tuples in the left hand relation and from the right hand relation.

• Examples:

• PEOPLE _{people.food = menu.food} MENU

  Name	Age	people.Food	menu.Food	Day
  Alice	21	Hamburger	Hamburger	Tuesday
  Bill	24	Pizza	Pizza	Monday
  Carl	23	Beer	NULL	NULL
  Dina	19	Shrimp	NULL	NULL

• PEOPLE _{people.food = menu.food} MENU

  Name	Age	people.Food	menu.Food	Day
  Bill	24	Pizza	Pizza	Monday
  Alice	21	Hamburger	Hamburger	Tuesday
  NULL	NULL	NULL	Chicken	Wednesday
  NULL	NULL	NULL	Pasta	Thursday
  NULL	NULL	NULL	Tacos	Friday

• PEOPLE _{people.food = menu.food} MENU

  Name	Age	people.Food	menu.Food	Day
  Alice	21	Hamburger	Hamburger	Tuesday
  Bill	24	Pizza	Pizza	Monday
  Carl	23	Beer	NULL	NULL
  Dina	19	Shrimp	NULL	NULL
  NULL	NULL	NULL	Chicken	Wednesday
  NULL	NULL	NULL	Pasta	Thursday
  NULL	NULL	NULL	Tacos	Friday

Outer Union

• The Outer Union operation is applied to partially union compatible relations.
• Operator is: *

• Example: PEOPLE * MENU

  Name	Age	Food	Day
  Alice	21	Hamburger	NULL
  Bill	24	Pizza	NULL
  Carl	23	Beer	NULL
  Dina	19	Shrimp	NULL
  NULL	NULL	Hamburger	Monday
  NULL	NULL	Pizza	Tuesday
  NULL	NULL	Chicken	Wednesday
  NULL	NULL	Pasta	Thursday
  NULL	NULL	Tacos	Friday

How to make Relational Algebra Symbols in MS Word

Some symbols such as join and outer join are not available in this fashion. For these you can copy and paste the graphics in the MS Word file linked here. All of the relational algebra symbols are included.