M4L1-RelationalAlgebra.pdf

Relational Algebra Slides Modified by Dianne Foreback Database System Concepts, 7th Ed. ©Silberschatz, Korth and Sudarshan See www.db-book.com for conditions on re-use Relational Algebra Topics Section 2.6 in Database System Concepts, 7th Ed. By Silberschatz, Korth and Sudarshan 1 Relational A...

Relational Algebra Slides Modified by Dianne Foreback Database System Concepts, 7th Ed. ©Silberschatz, Korth and Sudarshan See www.db-book.com for conditions on re-use Relational Algebra Topics Section 2.6 in Database System Concepts, 7th Ed. By Silberschatz, Korth and Sudarshan 1 Relational Algebra Topics • Relational Algebra Definition • Basic Operators we are covering in this lecture ▪ select:  ▪ project:  ▪ union and intersection:  and ∩ ▪ set difference: – ▪ Cartesian product: x ▪ rename:  ▪ theta-join ⋈𝜃 Image accessed 1/28/2023 from https://medium.com/@sahirnambiar/relational-algebra-the-underpinnings-of-sql-74959481231a 2 Relational Algebra Definition • Relational Algebra - a procedural language consisting of a set of operations that take one or two relations as input and produce a new relation as their result. ▪ Operations that take one relation are unary operations ▪ Operations that take two relations are binary operations • Used in database theory for modeling data and defining queries on it Image accessed 1/28/2023 from https://medium.com/@sahirnambiar/relational-algebra-the-underpinnings-of-sql-74959481231a 3 Relational Algebra Topics • Relational Algebra Definition • Basic Operators we are covering in this lecture ▪ select:  ▪ project:  ▪ union and intersection:  and ∩ ▪ set difference: – ▪ Cartesian product: x ▪ rename:  ▪ theta-join ⋈𝜃 Image accessed 1/28/2023 from https://medium.com/@sahirnambiar/relational-algebra-the-underpinnings-of-sql-74959481231a 4 Select Operation • The select operation selects tuples that satisfy a given predicate. • In SQL the predicate corresponds to the where clause • Notation:  p (r) • p is called the selection predicate • Example: select those tuples of the instructor relation where the instructor is in the “Physics” department. ▪ Query  dept_name=“Physics” (instructor) ▪ Result ▪ SQL: select * from instructor where dept_name = 'Physics'; 5 Select Operation (Cont.) • We allow comparisons using =, , >, , <,  in the selection predicate. • We can combine several predicates into a larger predicate by using the connectives:  (and),  (or),  (not) • Example: Find the instructors in Physics with a salary greater $90,000, we write:  dept_name=“Physics”  salary > 90,000 (instructor) • SQL where: from instructor where dept_name = ‘Physics’ and salary > 90000 • The select predicate may include comparisons between two attributes. ▪ Example, find all departments whose name is the same as their building name: ▪  dept_name=building (department) ▪ SQL -- similar to : select * from department where dept_name = building 6 Project Operation • A unary operation that returns its argument relation, with certain attributes left out. • Notation:  A1,A2,A3 ….Ak (r) where A1, A2, …, Ak are attribute names and r is a relation name • The result is defined as the relation of k columns obtained by erasing the columns that are not listed • Duplicate rows removed from result, since relations are sets in relational algebra 7 Project Operation Example • Example: eliminate the dept_name attribute of instructor • Query: ID, name, salary (instructor) • Result: SQL: select ID, name, salary from instructor 8 Composition of Relational Operations • The result of a relational-algebra operation is relation and therefore of relational-algebra operations can be composed together into a relational-algebra expression. • Consider the query -- Find the names of all instructors in the Physics department. name( dept_name =“Physics” (instructor)) • Instead of giving the name of a relation as the argument of the projection operation, we give an expression that evaluates to a relation. Similar to SQL (but not exact): select name from instructor where dept_name = ‘Physics’ 9 Recall: Cartesian Product instructor teaches ID name dept_name 10101 Srinivasan Comp. Sci. 12121 Wu Finance 15151 Mozart Music salary 65000 90000 40000 ID course_id sec_id semester 10101 CS-101 10101 CS-315 10101 CS-347 12121 FIN-201 15151 MU-199 1 Fall 1 Spring 1 Fall 1 Spring 1 Spring year 2017 2018 2017 2018 2018 instructor X teaches ID name 10101 Srinivasan 10101 Srinivasan 10101 Srinivasan 10101 Srinivasan 10101 Srinivasan 12121 Wu 12121 Wu 12121 Wu 12121 Wu 12121 Wu 15151 Mozart 15151 Mozart 15151 Mozart 15151 Mozart 15151 Mozart dept_name Comp. Sci. Comp. Sci. Comp. Sci. Comp. Sci. Comp. Sci. Finance Finance Finance Finance Finance Music Music Music Music Music salary 65000 65000 65000 65000 65000 90000 90000 90000 90000 90000 40000 40000 40000 40000 40000 ID course_id sec_id semester 10101 CS-101 1 Fall 10101 CS-315 1 Spring 10101 CS-347 1 Fall 12121 FIN-201 1 Spring 15151 MU-199 1 Spring 10101 CS-101 1 Fall 10101 CS-315 1 Spring 10101 CS-347 1 Fall 12121 FIN-201 1 Spring 15151 MU-199 1 Spring 10101 CS-101 1 Fall 10101 CS-315 1 Spring 10101 CS-347 1 Fall 12121 FIN-201 1 Spring 15151 MU-199 1 Spring year 2017 2018 2017 2018 2018 2017 2018 2017 2018 2018 2017 2018 2017 2018 2018 Cartesian product not very helpful on its own select * from instructor, teaches 10 from Clause – Cartesian Product • • The from clause lists the relations involved in the query separated by a comma Find the Cartesian product of instructor and teaches select * from instructor, teaches ▪ generates every possible instructor – teaches pair, with all attributes from both relations. • Cartesian product not very useful directly, but useful combined with whereclause condition 11 Cartesian Product and Where Clause Examples teaches instructor ID name dept_name 10101 Srinivasan Comp. Sci. 12121 Wu Finance 15151 Mozart Music • salary 65000 90000 40000 Find the names of all instructors who have taught some course and the course_id select name, course_id from instructor, teaches where instructor.ID = teaches.ID • ID course_id sec_id semester 10101 CS-101 10101 CS-315 10101 CS-347 12121 FIN-201 15151 MU-199 name Srinivasan Srinivasan Srinivasan Find the names of all instructors in the Art department who have taught some course and theWu Mozart course_id 1 Fall 1 Spring 1 Fall 1 Spring 1 Spring year 2017 2018 2017 2018 2018 course_id CS-101 CS-315 CS-347 FIN-201 MU-199 select name, course_id name course_id from instructor, teaches where instructor.ID = teaches.ID and Srinivasan CS-101 instructor.dept_name = 'Comp. Sci.' Srinivasan CS-315 Srinivasan CS-347 12 Relational Algebra with Cartesian-Product Operation • The Cartesian-product operation (denoted by X) allows us to combine information from any two relations. • Example: the Cartesian product of the relations instructor and teaches is written as: instructor X teaches • We construct a tuple of the result out of each possible pair of tuples: one from the instructor relation and one from the teaches relation (see next slides) • Since the instructor ID appears in both relations, we distinguish between these attribute by attaching to the attribute the name of the relation from which the attribute originally came. ▪ instructor.ID ▪ teaches.ID 13 Cartesian Product Larger Example instructor teaches 14 Relational Algebra with CartesianProduct Operation instructor X teaches That is, the Cartesian product of the instructor and teaches tables How many tuples? 15 Cartesian Product Restricting Tuples • To get only those tuples of “instructor X teaches “ that pertain to instructors and the courses that they taught, we write:  instructor.id = teaches.id • (instructor x teaches ) We get only those tuples of “instructor X teaches” that pertain to instructors and the courses that they taught. ~SQL: select * from instructor, teaches where instructor.id = teaches.id 16 Theta-Join Operation • The theta-join operation allows us to combine a select operation and a Cartesian-Product operation into a single operation. • Consider relations r (R) and s (S) • Let “theta” be a predicate on attributes in the schema R “union” S. The join operation r ⋈𝜃 s is defined as follows: 𝑟 ⋈𝜃 𝑠 = 𝜎𝜃 (𝑟 × 𝑠) • Thus  instructor.id = teaches.id (instructor x teaches ) • Can equivalently be written as instructor ⋈ Instructor.id = teaches.id teaches 17 Union Operation • The union operation allows us to combine two relations • Notation: r  s • For r  s to be valid. 1. r, s must have the same arity (same number of attributes) 2. The attribute domains must be compatible (example: 2nd column of r deals with the same type of values as does the 2nd column of s) • Example: to find all courses taught in the Fall 2017 semester, or in the Spring 2018 semester, or in both course_id ( semester=“Fall” Λ year=2017 (section))  course_id ( semester=“Spring” Λ year=2018 (section)) See next slide for the relation section 18 Union Operation (Cont.) • Result on left of: course_id ( semester=“Fall” Λ year=2017 (section))  course_id ( semester=“Spring” Λ year=2018 (section)) section resulting relation is a set so no duplicates 19 • • • • The set-intersection operation allows us to find tuples that are in both the input relations. Notation: r  s Assume: ▪ r, s have the same arity (same number of attributes) ▪ attributes of r and s are compatible Example: Find the set of all courses taught in both the Fall 2017 and the Spring 2018 semesters. SetIntersection Operation course_id ( semester=“Fall” Λ year=2017 (section))  course_id ( semester=“Spring” Λ year=2018 (section)) Result section 20 • The set-difference operation allows us to find tuples that are in one relation but are not in another. • • Notation r – s Set differences must be taken between compatible relations. ▪ r and s must have the same arity ▪ attribute domains of r and s must be compatible • Set Difference Operation Example: to find all courses taught in the Fall 2017 semester, but not in the Spring 2018 semester course_id ( semester=“Fall” Λ year=2017 (section)) − course_id ( semester=“Spring” Λ year=2018 (section)) section 21 The Assignment Operation • It is convenient at times to write a relational-algebra expression by assigning parts of it to temporary relation variables. • The assignment operation is denoted by  and works like assignment in a programming language. • Example: Find all instructor in the “Physics” and Music department. Physics   dept_name=“Physics” (instructor) Music   dept_name=“Music” (instructor) Physics  Music 22 The Rename Operation • The results of relational-algebra expressions do not have a name that we can use to refer to them. The rename operator,  , is provided for that purpose • The expression: x (E) returns the result of expression E under the name x • Another form of the rename operation: x(A1,A2, .. An) (E) 23 The Rename Operation • The results of relational-algebra expressions do not have a name that we can use to refer to them. The rename operator,  , is provided for that purpose • The expression: x (E) returns the result of expression E under the name x • Another form of the rename operation: x(A1,A2, .. An) (E) Query below finds the ID and name of those instructors who earn more than the instructor whose ID is 12121. To reference resultant relations, the rename operation is used. 24 Equivalent Queries • There is more than one way to write a query in relational algebra. • Example: Find information about courses taught by instructors in the Physics department with salary greater than 90,000 • Query 1  dept_name=“Physics”  salary > 90,000 (instructor) • Query 2  dept_name=“Physics” ( salary > 90.000 (instructor)) • The two queries are not identical; they are, however, equivalent -they give the same result on any database. 25 Equivalent Queries • There is more than one way to write a query in relational algebra. • Example: Find information about courses taught by instructors in the Physics department • Query 1 dept_name=“Physics” (instructor ⋈ instructor.ID = teaches.ID teaches) • Query 2 (dept_name=“Physics” (instructor)) ⋈ instructor.ID = teaches.ID teaches • The two queries are not identical; they are, however, equivalent -- they give the same result 26 Study Guide 1. 2. 3. Be able to write a relational algebra and give a resulting relation From our course textbook, make certain you understand and are able to complete the Practice Exercises 2.5 – 2.9. Solutions to practice exercises are available https://www.db-book.com/Practice-Exercises/index-solu.html Make certain that you understand the relational algebra examples in Section 2.6 of our course textbook. 27 Thank You ! Questions ? 28