ICOM 5016 Database Systems Relational Algebra Dr. Amir H. Chinaei Department of Electrical and Computer Engineering University of Puerto Rico, Mayagez Slides are adapted from: Database System Concepts, 5th Ed. Silberschatz, Korth and Sudarshan See www.db-book.com for conditions on re-use Relational Algebra Introduction. one of the two formal query languages associated with the relational model. Fundamental Property Operands: relations Operators: the most required functions in relational model Unary or Binary Result is also a relation 2 Roadmap

Core R.A. includes basic operators Advanced R.A. includes additional operators (that mostly can be defined in terms of Core R.A.) Extended R.A. Extends R.A. to support more features of SQL 3 R.A. Operators Basic Selection Projection Union

Difference (Cross-)product, Additional Intersection Rename Joins Division 4 Selection Selection extracts some rows from a relation R2 ::= C (R1)

R2 includes only those rows of R1 that satisfy C C is a Boolean condition 5 Example: Selection Provides R2 ::= price<6.50 (Provides) R2 Foodservice Food Price Brubakers Brubakers Brubakers Bon Appetite Bon Appetite Sushi Stroganoff Meatball Sushi Meatball 7.50

6.00 5.00 8.00 5.00 Foodservice Food Price Brubakers Brubakers Bon Appetite Stroganoff Meatball Meatball 6.00 5.00 5.00 6 Projection Projection extracts some columns from a relation R2 := A (R1)

A consists of some attributes of R1 R2 includes only those columns of R1 that are in A. Eliminate duplicate tuples, if any. 7 Example: Projection Foodservice Food Price Brubakers Brubakers Brubakers Bon Appetite Bon Appetite Sushi Stroganoff Meatball Sushi Meatball 7.50 6.00 5.00

8.00 5.00 Provides R2 R2 ::= Foodservice, Food (Provides) 8 Foodservice Food Brubakers Brubakers Brubakers Bon Appetite Bon Appetite Sushi Stroganoff Meatball Sushi Meatball Set-Based Operators R.A. borrows the following standard operators on sets: Union. R3 ::= R1 U R2

Intersection. R3 ::= R1 R2 Difference. R3 ::= R1 - R2 Cross-Product (Cartesian product). R3 ::= R1 R2 9 Union Union puts together all tuples that are in R1 or R2 or both R3 ::= R1 U R2 R1 and R2 must be union-compatible: They have the same number of attributes Corresponding attributes have the same domains 10 Intersection

Intersection puts together all tuples that are in both relations R1 and R2 R3 ::= R1 R2 R1 and R2 must be union-compatible 11 Difference Difference consists of those tuples of first relation which do not appear in the other R3 ::= R1 - R2 R1 and R2 must be union-compatible 12 Product Product pairs each tuple t1 of R1 with each tuple t2 of R2 R3 ::= R1 R2 Schema of R3 is the attributes of R1 and R2, in order

If an attribute name A is repeated in both R1 and R2, it is represented by R1.A and R2.A 13 Example: Product R1 FS F P a1 a2 a3 b1 b2 b3 c1 c2 c3 R3 ::= R1 R2 R3 R2 N F

d1 d2 b1 b2 14 FS R1.F P N R2.F a1 a1 a2 a2 a3 a3 b1 b1 b2 b2 b3 b3 d1 d2 d1 d2

d1 d2 b1 b2 b1 b2 b1 b2 c1 c1 c2 c2 c3 c3 Renaming Renaming is useful to resolve possible name conflicts R2 ::= (R2(F ), R1) F is a list of terms of the form AO AN Returns R1 with columns renamed according to F

Simplified notation: R2 ::= R1 (F) 15 Example: Renaming Student ID 083920 183280 Students Name Adam Saniya Major ID Math CS 083920 183280 Fullname Adam Saniya Students ::= (Name Fullname, Major Plan) Student 16 Plan

Math CS Joins One of the most useful operators in R.A. The most commonly used way to combine several relations Condition Joins (Theta-join) Equijoin Natural Join Outer join 17 Theta-Join Theta-join joins two relations and extracts some rows from the result R3 ::= R1 Common special case: C consists solely of equalities (Equijoin)

C R2 = C (R1 R2) The schema of the result consists of attributes of R1 followed by those attributes of R2 that do not appear in C. 18 Example: Theta-Join Food Name Sushi Meatball Mofongo CheapFood Cuisine Foodservice Food Price Japanese Global Puerto Rican Bon Appetite Brubakers Bon Appetite Mofongo

Meatball Meatball 4.50 5.00 5.50 R1 ::= Food R1 Price<5.50 Name=Food CheapFood Name Cuisine Foodservice Food Price Meatball Mofongo Global Puerto Rican Brubakers Bon Appetite Meatball

Mofongo 5.00 4.50 19 Natural Join A further special case R3 ::= R1 An Equijoin in which equalities are specified on all common attributes of R1 and R2 R2 = A ( C (R1 R2) ) The result is guaranteed not to have attributes with the same name 20 20 Example: Natural Join Food1 CheapFood Food Sushi Meatball

Mofongo Cuisine Foodservice Food Price Japanese Global Puerto Rican Bon Appetite Brubakers Bon Appetite Mofongo Meatball Meatball 4.50 5.00 5.50 R1 ::= Food1 R1 CheapFood Food Cuisine

Foodservice Price Meatball Meatball Mofongo Global Global Puerto Rican Brubakers Bon Appetite Bon Appetite 5.00 5.50 4.50 21 Division Division. R3 ::= R1 / R2 It is not needed as often

But sometimes simplifies a query significantly Find Foodservices that provide all foods Properties: R2s attributes R1s attributes R3s attributes = R1s attributes R2s attributes R3 contains all tuples (T3) s.t. for every tuple T2 R2, T3.T2 T1 (set of tuples of R1) In other words, R3 R2 R1 22 Examples: Division R1 A1 * 1 1 * 2

* 1 2 * R2 R3 A2 A3 A1 A3 1 2 1 3 3 1 1 1 1 1 1 2 * * * * 1

1 A2 * * 1 3 R4 R5 R6 A1 A3 A2 A1 A3 1 2 3 1 * 1 * 2 1 1 1

R3 ::= R1 / R2 R4 ::= R1 / R3 R6 ::= R1 / R5 23 Complex Expressions Expressions with several operators Example: R2 ::= Foodservice (price<6.0 (Provides Food1)) Precedence of operators: 1. Select, Project, Renaming 2. Products, Division, Joins 3. Intersection 4.

Union, Difference Therefore, we could write: R2 ::= Foodservice price<6.0 (Provides Food1) How about this? R2 ::= Foodservice price<6.0 Provides 24 Food1 Expression Trees Useful when writing complex queries Example: Find all Foodservice names that provide meatball for less that 6 bucks and their rate is over 6. Name Rate>6 Food=Meatball Price<6.0 Food1 Provides FoodService

25 Hands-on Example 1 Find all students who like Mofongo and frequent Pollo Tropical. (Contest 1) 26 Hands-on Example 2 Find names of all ICOM students who do not frequent a foodservice that its rate is greater than 8 (Contest 2) 27 Hands-on Example 3 Find all Foodservice names that provide at least two foods with the same price (Contest 3) 28 Relational Algebra on Bags Recall: SQL tables are multisets (bags) Bags are a more general data structure Some operations are more efficient on bags Following R.A. operators produce a different result on a bag than on a set Projection, Division, Union, Intersection, Difference

Bag projection and bag division do not eliminate duplicates from the result. 29 UB, B, B Bag Union. R3::= R1 UB R2 R3: all tuples of R1 and R2 Example: {1,1,2} UB {1,1,1,3}= {1,1,1,1,1,2,3} Bag Intersection. R3 ::= R1 B R2 R3: common tuples of R1 and R2 with the minimum show up Example: {1,1,2} B {1,1,1,3} = {1,1} Bag Difference. R3 ::= R1 B R3 R3: all tuples appear in R1 # of times appear in R2 Example: {1,1,2} B {1,1,1,3} = {2} Do sets laws hold for bags?

30 Extended R.A. Distinct eliminates duplicates from R1 R2 ::= (R1) Order sorts R1 based on list of attributes in A R2 ::= A (R1) Extended Projection R2 ::= A (R1) A consists of some attributes of R1, as well as (arithmetic) expressions and attribute renaming 31 Examples: , , R1 R2 = (R1) A1 A2 A1 A2

A1 A2 A3 A1 A2 A3 1 2 1 2 1 2 2 1 1 2 1 2 1 2 1 2 3 5

5 4 5 1 1 2 1 1 2 1 1 2 2 3 5 4 5 5 1 2 1 2 3 R3 2 1 3 NewA1

A1 A1+A2 A2 1 2 1 2 1 2 1 2 3 3 3 5 2 1 2 3 R4= R5 = 32 A1 NewA1, A1, A1+A2,A2

A2,A1 (R1) (R3) Extended R.A. contd Agg aggregates values of an attribute to compute a function Sum(A), Avg(A), Count(A), Min(A), Max(A) Not applicable on a relation, rather on an attribute Group groups tuples based on attributes R2 ::= A (R1) Where, A consists of some attributes of R1 may include some aggregate functions 33 Examples: Agg, R1 A1

A2 A3 1 1 2 1 2 1 2 3 2 3 5 5 4 5 1 Sum (A1) = 7 Count (A1) = 5 Avg (A3) = 4 R2 = A1,A2, Avg(A3), Sum(A2) (R1) A1 A2

Avg(A3) Sum(A2) 1 1 2 5 5 2.5 34 1 2 3 1 4 6 Extended R.A. contd Outer join R3 ::= R1 An extended natural join in which no tuple from R1 or R2 is omitted.

Example: O R2 R1 R1 R2 A1 A2 A2 A3 1 2 2 2 3 4 2 1 3 1 2 3 35 O

R2 A1 A2 A3 1 2 2 2 1 3 4 1 2 3 Relational Completeness Definition. A query language is at least as expressive as core relational algebra is said to be relationally complete. Examples Safe Relational Calculus R.A.

SQL (has additional expressive power) Recommended Exercise: from Ramakrishnans 4.14.7 (ignore Relational Calculus) 36