《數(shù)據(jù)庫系統(tǒng)》英文教學(xué)課件

《數(shù)據(jù)庫系統(tǒng)》英文教學(xué)課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),英文,教學(xué),課件 Relational AlgebraGuifeng ZhengSchool of SoftwareSUN YAT-SEN UNIVERSITYcourtesy of Joe Hellerstein for some slides2Recap:You are herenFirst part of course is done:conceptual foundationsnYou now know:qE/R ModelqRelational ModelqRelational Algebra(a little)nYou now know how to:qCapture part of world as an E/R modelqConvert E/R models to relational modelsqConvert relational models to good(normal)formsnNext:qCreate,update,query tables with R.A/SQLqWrite SQL/DB-connected applications33-minute Normalization Review1.Q:Whats required for BCNF?2.Q:How do we fix a non-BCNF relation?3.Q:If AsBs violates BCNF,what do we do?4.Q:Can BCNF decomposition ever be lossy?5.Q:How do we combine two relations?6.Q:Can BCNF decomp.lose FDs?7.Q:Why would you ever use 3NF?Relational Query LanguagesnQuery languages:manipulation and retrieval of datanRelational model supports simple,powerful QLs:qStrong formal foundation based on logic.qAllows for much optimization.nQuery Languages!=programming languages!qQLs not expected to be“Turing complete”.qQLs not intended to be used for complex calculations.qQLs support easy,efficient access to large data sets.(Actually,I no longer believe this.But its the standard viewpoint)4Formal Relational Query LanguagesRelational Algebra:More operational,very useful for representing execution plans.Relational Calculus:Describe what you want,rather than how to compute it.(Non-procedural,declarative.)*Understanding Algebra&Calculus is key to understanding SQL,query processing!56What is relational algebra?nAn algebra for relationsn“High-school”algebra:an algebra for numbersnAlgebra=formalism for constructing expressionsqOperationsqOperands:Variables,Constants,expressionsnExpressions:qVars&constantsqOperators applied to expressionsqThey evaluate to valuesAlgebraVars/constsOperatorsEval toHigh-schoolNumbers+*-/etc.NumbersRelationalRelations(=sets of tupes)union,intersection,join,etc.Relations7Why do we care about relational algebra?1.The exprs are the form that questions about the data take（有關(guān)數(shù)據(jù)的問題采用的形式?。﹒The relations these exprs cash out to are the answers to our questions（其表示的關(guān)系正是我們的問題的答案）2.RA more succinct rep.(簡潔表示)of many SQL queries3.DBMS parse SQL into something like RA.nFirst proofs of concept for RDBMS/RA:qSystem R at IBMqIngress at Berkeleyn“Modern”implementation of RA:SQLqBoth state of the art,mid-70sPreliminariesnA query is applied to relation instancesnThe result of a query is also a relation instance.qSchemas of input relations for a query are fixedqSchema for the result of a query is also fixed.ndetermined by the query language constructsnPositional vs.named-field notation:qPositional notation easier for formal definitionsqNamed-field notation more readable.qBoth used in SQLnThough positional notation is discouraged8Relational Algebra:5 Basic OperationsnSelection (s s)qSelects a subset of rows(horizontal)nProjection (p p)qRetains only desired columns(vertical)nCross-product ()qAllows us to combine two relations.nSet-difference ()qTuples in r1,but not in r2.nUnion ()qTuples in r1 or in r2.pSince each operation returns a relation,operations can be composed!(Algebra is“closed”.)9R1S1S2BoatsExample Instances10Projection()nExample:nRetains only attributes that are in the“projection list”.nSchema of result:qthe fields in the projection listqwith the same names that they had in the input relation.nProjection operator has to eliminate duplicatesqNote:real systems typically dont do duplicate elimination qUnless the user explicitly asks for it.q(Why not?)11Projection()S2snameratingyuppy9lubber8guppy5rusty1012Selection()snameratingyuppy9rusty10nSelects rows that satisfy selection condition.nResult is a relation.Schema of result is same as that of the input relation.nDo we need to do duplicate elimination?sid sname rating age 28 yuppy 9 35.0 31 lubber 8 55.5 44 guppy 5 35.0 58 rusty 10 35.0 13Union and Set-DifferencenBoth of these operations take two input relations,which must be union-compatible:qSame number of fields.qCorresponding fields have the same type.nFor which,if any,is duplicate elimination required?14Union S1S215Set Difference S1S2S2 S116Guifeng Zheng,DBMS,SS/SYSU17Rename opnChanges the schema,not the instancenNotation:rB1,Bn(R)nr is spelled“rho”,pronounced“row”nExample:qEmployee(ssn,name)qrE2(social,name)(Employee)qOr just:rE(Employee)Cross-ProductnS1 R1:qEach row of S1 paired with each row of R1.nQ:How many rows in the result?nResult schema has one field per field of S1 and R1,qField names inherited if possible.qNaming conflict:S1 and R1 have a field with the same name.qCan use the renaming operator:Output relation nameRenaming list18Cross Product ExampleR1S1S1 x R1=19););Division OperationnNotation:r s nSuited to queries that include the phrase“for all.”nLet r and s be relations over schemas R and S respectively,whereR =(A1,Am,B1,Bn)S =(B1,Bn)The result of r s is a relation over the schema(R S)=(A1,Am)r s =t|(t R-S(r)(u s,tu r)School of Software,SYSUSlide 20School of Software,SYSUSlide 21rsr sThe result consists of attribute A only but not all of the 5 values.How to find out?u=1,2 Check if:u s(tu r)Division Operation-exampler s =t|(t R-S(r)(u s,tu r)B12Is,1 and,2 tuples in r?Is,1 and,2 tuples in r?Is,1 and,2 tuples in r?check and A12311134612BA t R-S(r)A School of Software,SYSUSlide 22Relations r,s:Another Division Exampler sABCAASchool of Software,SYSUSlide 23Relation r,s:rsqProperties of Division OperationLet q =r sThen q is the largest relation satisfying:q s rCompound Operator:IntersectionnOn top of 5 basic operators,several additional“Compound Operators”qThese add no computational power to the languageqUseful shorthandqCan be expressed solely with the basic operators.nIntersection takes two input relations,which must be union-compatible.nQ:How to express it using basic operators?R S=R (R S)24Intersection S1S225Compound Operator:JoinnInvolve cross product,selection,and(sometimes)projection.nMost common type of join:“natural join”qR S conceptually is:nCompute R SnSelect rows where attributes appearing in both relations have equal valuesnProject all unique attributes and one copy of each of the common ones.nNote:Usually done much more efficiently than this.26Natural Join ExampleR1S1S1 R1=27Guifeng Zheng,DBMS,SS/SYSU28Natural JoinnR SnR S=?nUnpaired tuples called danglingABXYXZYZZVBCZUVWZVGuifeng Zheng,DBMS,SS/SYSU29Natural JoinnGiven the schemas R(A,B,C,D),S(A,C,E),what is the schema of R S?nGiven R(A,B,C),S(D,E),what is R S?nGiven R(A,B),S(A,B),what is R S?Other Types of JoinsnCondition Join(or“theta-join”):nResult schema same as that of cross-product.nMay have fewer tuples than cross-product.nEqui-Join:Special case:condition c contains only conjunction of equalities.(sid)snameratingage(sid)bidday22dustin745.05810311/12/9631lubber855.55810311/12/9630ExamplesReservesSailorsBoats31Find names of sailors whove reserved boat#103nSolution 1:nSolution 2:32Find names of sailors whove reserved a red boatnInformation about boat color only available in Boats;so need an extra join:v A more efficient solution:*A query optimizer can find this given the first solution!33Find sailors whove reserved a red or a green boatnCan identify all red or green boats,then find sailors whove reserved one of these boats:34Find sailors whove reserved a red and a green boatnCut-and-paste previous slide?35Find sailors whove reserved a red and a green boatnPrevious approach wont work!Must identify sailors whove reserved red boats,sailors whove reserved green boats,then find the intersection(note that sid is a key for Sailors):36SummarynRelational Algebra:a small set of operators mapping relations to relationsqOperational,in the sense that you specify the explicit order of operationsqA closed set of operators!Can mix and match.nBasic ops include:,nImportant compound ops:,37