Relational Algebra (CB Chapter 5.1)Relational AlgebraExample Relation (PhoneBook)Another Relation (Dept)Selection (condition )Valid ConditionsPseudocode for SelectionProjection (attributes)Relations Have No DuplicatesPseudocode for ProjectionCombining Select & ProjectRemember: A Relation is a SetBasic Set OperationsApplying to RelationsBasic Operation ExamplesAnother Set OperationCartesian Product (X)Pseudocode for Cartesian ProductJoin Combines X and SelectNaïve Pseudocode for JoinLet’s Try Some Examples:First and last names of all professors who don’t work in HinsdaleTelephone extensions of people who work in HinsdaleBuildings with phone numbers between 5000 and 5300Dept. Name, Building, and phone numbers for all departmentsAggregationGroupingGrouping ExamplesRelational Algebra (CB Chapter 5.1)CPSC 356 DatabaseEllen WalkerHiram CollegeRelational Algebra•Mathematical language for operating on relations•Each operator takes one or more relations as input, and produces one relation as output•Relational algebra operators can be implemented as functions in a programming language•A relational algebra expression indicates which operators to use, in which orderExample Relation (PhoneBook)First Last Dept Email Phone TitleLouis Oliphant CPSC Louis 5275 AsstEllen Walker CPSC WalkerEL 5250 ProfLaura VanWormer PHYS VanwormerLA 5249 ProfCathy Mansor WEC MansorCN 5957 DeanBrad Goodner BIOL GoodnerBW 5260 ProfAnother Relation (Dept)Name BuildingCPSC ColtonWEC HinsdalePHYS GerstackerBIOL GerstackerMGMT HinsdaleSelection (condition )•The output relation has all rows of the input relation that satisfy the condition(Title=“prof”) PhonebookFirst Last Dept Email Phone TitleLaura VanWormer PHYS VanwormerLA 5249 ProfEllen Walker CPSC WalkerEL 5250 ProfBrad Goodner BIOL GoodnerBW 5260 ProfValid Conditions•Basic condition–Dept = ‘CS’ attribute compare to const–First < Last attribute compare to attribute•Combination of conditions using AND, OR, or NOT •Note: All attributes must come from the relation in the selectionPseudocode for SelectionSelect (input relation, condition, &output rel)Do for every tuple in the input relation If the tuple satisfies the condition Copy the tuple to the output relationTime = O(number of tuples in input relation)Projection (attributes)•Create a new relation with only the listed attributes in it.last, phone PhoneBookLast PhoneOliphant 5275Walker 5250VanWormer 5249Mansor 5957Goodner 5260Relations Have No Duplicatesdept PhoneBook•Only 4 rows, even though PhoneBook had 5!DeptCPSCPHYSWECBIOLPseudocode for ProjectionProject (input relation, attribute-list, &output rel)Do for every tuple in the input relation Do for every attribute in the input relation If the attribute is in the attribute-list copy the value to the output relationRemove duplicates in the output relationTime = O(number of tuples in relation + time for duplicate-removal)Combining Select & Projectfirst, last ( title=prof PhoneBook )First LastLaura VanWormerEllen WalkerBrad GoodnerRemember: A Relation is a Set •A set is an unordered collection of unique elementsSet S = {1,2,3} “1 is an element of S”{a,b,c} = {a,c,b}•A subset of a set is another set whose elements all come from the original set.{a,b} is a subset of {a,c,b}{1,2,3} is a subset of {1,2,3}{1,2,4} is not a subset of {1,2,3}{} (the empty set) is a subset of every set!Basic Set Operations•Union: the set of all elements in either or both original sets–{1,2} union {2,3} = {1,2,3}•Intersection: the set of all elements in both original sets (only)–{1,2} intersect {2,3} = {2}•Set Difference: the set of all elements in the first but not the second set–{1,2} – {2,3} = {1}Applying to Relations•Relations must be “comparable”–Same set of attributes in each relation!•Union = all tuples•Intersection = all matching tuples•Set Difference = all tuples from first but not secondBasic Operation Examples•R1 = dept PhoneBook•R2 = name as “dept” Dept–Rename attribute to be same•R1  R2 = R2 (in this case)•R1  R2 = R1 (in this case)•R1 – R2 = { } (empty set)•R2 – R1 = DeptCPSCPHYSWECBIOLDeptCPSCPHYSWECBIOLMGMTR1 R2DeptMGMTAnother Set Operation•Cartesian product: a set of ordered pairs, where each contains one element from each original set{1,2,3} x {a, b} = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}•For Relations: create a new relation with every combination of tuplesCartesian Product (X)dept, last PhoneBook X DeptLast Dept Name BldgOliphant CPSC CPSCColtonWalker CPSCCPSC ColtonVanWormer PHYSCPSC ColtonMansor WECCPSC ColtonGoodner BIOLCPSC ColtonOliphant CPSCWEC HinsdaleWalker CPSCWEC HinsdaleVanWormer PHYSWEC HinsdaleMansor WECWEC HinsdaleGoodner BIOLWEC HinsdaleOliphant CPSCPHYS ColtonWalker CPSCPHYS ColtonEtc….Pseudocode for Cartesian ProductProduct (relation1, relation2, &output rel)Do for every tuple in relation1 Do for every tuple in relation2 Build a row with all attributes from both relations Add it to the output relationTime = O(number of tuples in relation1 * number of tuples in relation 2)This is the most expensive operation in relational algebra!Join Combines X and Select•Theta Join: any condition R1 X R2•Equijoin: equality condition R1 X R2 •Natural Join:equality condition R1 X R2 –Project to remove one copy of each equal attribute•Left or Right Outer Join: –Include all tuples from (left or right) side, even if they don’t have a matchNaïve Pseudocode for Join•Join (rel1, rel2, condition, output rel)• product (rel1, rel2, tmp)• select (tmp, condition, output rel)•Time: Same as Cartesian Product•To keep time down, keep the size of the relations down -- we’ll look at this later!Let’s Try Some Examples: •What are the first and last names of all professors who don’t work in Hinsdale?•What are the telephone extensions of people who work in Hinsdale?•Which buildings contain people whose phone numbers are between 5000 and 5200?•List the Dept. Name, Building Name, and phone numbers for All departments (even those without phone numbers).First and last names of all professors who don’t work in Hinsdale•Select “all professors”Title=“Prof” (Phonebook)•Select “Departments not in Hinsdale” Bldg != “Hinsdale” (Dept)•Connect these relations where depts match–(Title=“Prof”