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

《數(shù)據(jù)庫系統(tǒng)》教學(xué)課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),教學(xué),課件 Relational AlgebraJianlin FengSchool of SoftwareSUN YAT-SEN UNIVERSITYcourtesy of Joe Hellerstein for some slidesRelational 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)Formal 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!PreliminariesnA 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 discouragedRelational 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”.)R1S1S2BoatsExample InstancesProjection()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?)Projection()S2snameratingyuppy9lubber8guppy5rusty10Selection()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 Union 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?Union S1S2Set Difference S1S2S2 S1Cross-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 listCross Product ExampleR1S1S1 x R1=Compound 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)Intersection S1S2Compound 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.Natural Join ExampleR1S1S1 R1=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/96ExamplesReservesSailorsBoatsFind names of sailors whove reserved boat#103nSolution 1:n Solution 2:Find 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!Find sailors whove reserved a red or a green boatnCan identify all red or green boats,then find sailors whove reserved one of these boats:Find sailors whove reserved a red and a green boatnCut-and-paste previous slide?Find 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):SummarynRelational 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:,