Introduction to Database Systems CSE 444 Lecture 18: Relational AlgebraOutline 2! Mo#va#on'and'sets'v.s.'bags' Rela#onal'Algebra' Transla#on'from'SQL'to'the'Rela#onal'Algebra' Read'Sec#ons'2.4,'5.1,'and'5.2' [Old'edi#on:'5.1'through'5.4]' These'book'sec#ons'go'over'rela#onal'operators'The WHAT and the HOW 3! In'SQL,'we'write'WHAT'we'want'to'get'from'the'data' The'database'system'needs'to'figure'out'HOW'to'get'the'data'we'want' The'passage'from'WHAT'to'HOW'goes'through'the'Rela%onal(Algebra(SQL = WHAT 4!SELECT'DISTINCT'x. name,'z.n ame'FROM'Product'x,'Purchase'y,'Customer'z'WHERE'x.pid'='y.pid'and'y.cid'='z.ci d'an d'''''''''''''''''x.price'>'100'and'z.city'='‘SeaZle’'Pro du ct(pid,'name,'price)'Purchase(pid,'cid,'store)'Customer(cid,'name,'city)'It’s'clear'WHAT'we'want,'unclear'HOW'to'get'it'Relational Algebra = HOW 5!Product(Purchase(pid=pid(price>100(and(city=‘Sea=le’(x.name,z.name(δ'cid=cid(Customer(π'σ'T1(pid,name,price,pid,cid,store)'T2('.'.'.'.)'T4(name,name)'Final'answer'T3(.'.'.')'Temporary'tables'T1,'T2,'.'.'.'Pro du ct(pid,'name,'price)'Purchase(pid,'cid,'store)'Customer(cid,'name,'city)'Relational Algebra = HOW 6!The'order'is'now'clearly'specified:' Iterate'over'PRODUCT…' …join'with'PURCHASE…' …join'with'CUSTOMER…' …select'tuples'with'Price>100'and'City=‘SeaZle’…' …eliminate'duplicates…' …and'that’s'the'final'answer'!'Relations 7! A'rela#on'is'a'set'of'tuples' Sets:'{a,b,c},'{a,d,e,f},'{'},'.'.'.' But,'commercial'DBMS’s'implement'rela#ons'that'are'bags'rather'than'sets'' Bags:'{a,'a,'b,'c},'{b,'b,'b,'b,'b},'.'.'.'Sets v.s. Bags 8!Rela#onal'Algebra'has'two'flavors:' Over'sets:'theore#cally'elegant'but'limited' Over'bags:'needed'for'SQL'queries'+'more'efficient' Example:'Compute'average'price'of'all'products'We'discuss'set'seman#cs' We'men#on'bag'seman#cs'only'where'needed'Outline 9! Mo#va#on'and'sets'v.s.'bags' Rela#onal'Algebra' Transla#on'from'SQL'to'the'Rela#onal'Algebra'Relational Algebra 10! Query(language(associated'with'rela#onal'model' Queries'specified'in'an'opera#onal'manner' A'query'gives'a'stepmbymstep'procedure' Rela#onal'op erators' Take'one'or'two'rela#on'i nstances'as'argument' Return'one'rela#on'instance'as'result' Easy'to'compose'into'rela#onal'algebra'expressions'Relational Algebra (1/3) 11!Five'basic'operators:' Union'(∪)'and'Set'difference'(–)' Selec#on:':'σcondi#on(S)' Condi#on'is'Boolean'combina#on'(∧,∨)'of'terms' Term'is:'aZribute'op'constant,'aZr.'op'aZr.' Op'is:'<,'<=,'=,'≠,'>=,'or'>'' Pro jec#on:'πlistmofmaZributes(S)' Crossmproduct'or'cartesian'product'(×)'Relational Algebra (2/3) 12!Derived'or'auxiliary'operators:' Intersec#on'(∩),'Division'(R/S)' Join:'R'⋈θ'S'='σθ(R'×'S)' Varia#ons'of'joins ' Natural,'equijoin,'thetamjoin'' Outer'join'and'semimjoin' Rename'ρ'B1,…,Bn'(S)'Relational Algebra (3/3) 13!Extensions(for(bags( Duplicate'elimina#on:'δ' Grou p 'by:''γ'[Same'symbol'as'aggrega#on]' Par##ons'tuples'of'a'rela#on'into'“groups”' Sor#ng:'τ'Other'extensions ' Aggrega#on:''γ'(min,'max,'sum,'average,'count)'Union and Difference 14! R1'∪'R2' Example:''' Ac#veEmployees'∪'Re#redEmployees' R1'–'R2' Example:' AllEmployees'–'Re#redEmployees'Be'careful'when'applying'to'b ags!'What about Intersection? 15! It'is'a'derived'operator' R1'∩'R2'='R1'–'(R1'–'R2)' Also'expressed'as'a'join'(will'see'later)' Example' UnionizedEmployees'∩'Re#redEmployees'Relational Algebra (1/3) 16!Five'basic'operators:' Union'(∪)'and'Set'difference'(–)' Selec#on:':'σcondi#on(S)' Condi#on'is'Boolean'combina#on'(∧,∨)'of'terms' Term'is:'aZribute'op'constant,'aZr.'op'aZr.' Op'is:'<,'<=,'=,'≠,'>=,'or'>'' Pro jec#on:'πlistmofmaZributes(S)' Crossmproduct'or'cartesian'product'(×)'Selection 17! Returns'all'tuples'that'sa#sfy'a'condi#on' Nota#on:' σc(R)' Examples' 'σSalary'>'40000'(Employee)' 'σname'='“Smith”'(Employee)' The'condi#on'c'can'be' Boolean'combina#on'(∧,∨)'of'terms' Term'is:'aZribute'op'constant,'aZr.'op'aZr.' Op'is:'<,'<=,'=,'≠,'>=,'or'>''Maps'to'the'WHERE'clause'in'SQL!'Selection example 18!σSalary'>'40000'(Employee)'SSN' Name' Salary'1234545' John' 20000'5423341' Smith' 60000'4352342' Fred' 50000'SSN' Name' Salary'5423341' Smith' 60000'4352342' Fred' 50000'xProjection 19! Eliminates'columns' Nota#on:'''π'A1,…,An'(R)' Example:'project'socialmsecurity'number'and'names:' π'SSN,'Name'(Employee)' Output'schema:'''Answer(SSN,'Name)'Seman#cs'differs'over'set'or'over'bags'Projection example 20!π Name,Salary (Employee) SSN' Name' Salary'1234545' John' 20000'5423341' John' 60000'4352342' John' 20000'Name' Salary'John' 20000'John' 60000'Set semantics: duplicate elimination automatic xExample 21!π Name,Salary (Employee) SSN' Name' Salary'1234545' John' 20000'5423341' John' 60000'4352342' John' 20000'Name' Salary'John' 20000'John' 60000'John' 20000'Bag semantics: no duplicate elimination; need explicit δ xSelection & Projection Examples 22!no' name' zip' disease'1' p1' 98125' flu'2' p2' 98125' heart'3' p3' 98120' lung'4' p4' 98120' heart'Pa#ent'σdisease=‘heart’(Pa#ent)'no' name' zip' disease'2' p2' 98125' heart'4' p4' 98120' heart'zip' disease'98125' flu'98125' heart'98120' lung'98120' heart'πzip,disease(Pa#ent)'πzip'(σdisease=‘heart’(Pa#ent))'zip'98120'98125'Relational Algebra (1/3) 23!Five'basic'operators:' Union'(∪)'and'Set'difference'(–)' Selec#on:':'σcondi#on(S)' Condi#on'is'Boolean'combina#on'(∧,∨)'of'terms' Term'is:'aZribute'op'constant,'aZr.'op'aZr.' Op'is:'<,'<=,'=,'≠,'>=,'or'>'' Pro jec#on:'πlistmofmaZributes(S)' Crossmproduct'or'cartesian'product'(×)'Cartesian Product 24! Each'tup le'in 'R1'with 'each'tupl e'in'R2' Nota#on:'R1'×'R2' Example:''' Employee'×'Dependents' Rare'in'prac#ce;'mainly'used'to'express'joins'Cartesian Product Example 25!Name'SSN John 999999999 Tony 777777777 EmployeeSSN'Dname 999999999 Emily 777777777 Joe Employee' Dependents'Name'SSN
View Full Document
Unlocking...