数据库管理系统概述英文版课件：5 relational Algebra

1、COMP2311COMP231Relational AlgebraCOMP2312IntroductionQuery languages are specialized languages for asking questions or queries, that involve the data in a databaseRelational algebra: queries in terms of operatorsEvery operator in relational algebra accepts (one or two) relation instances as argument

2、s and returns a relation instance as the result. (1 + 2 = 3)A relational algebra expression is recursively defined to be a relation.Relational algebra is a procedural query languageDefines a step-by-step procedure for computing the answerCOMP2313Relational AlgebraBasic operations:ProjectionSelection

3、Set-differenceUnionCross-productRenameAdditional operations:Intersection, join, division: Not essential, but (very!) useful.Each operation returns a relation, and operations can be composed! COMP2314Projection L(R)Deletes attributes that are not in projection list L.Schema of result contains exactly

4、 the fields in the projection list, with the same names that they had in the (only) input relation.Projection operator eliminates duplicates! MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340MDDC10MDDC9Maker(Plane)PlaneMakerAirbusMDCOMP2315Selection c(R)Selects rows (records/tuples) that satisfy

5、 a selection condition c.Schema of result identical to schema of (only) input relation. A condition c has the form: Term Op Termwhere Term is an attribute name or a constantOp is one of , =, , etc.Different conditions can be linked together with a boolean expression.(C1 C2), (C1 C2), ( C1) are condi

6、tions where C1 and C2 are conditions. means AND means OR means NOTCOMP2316Selection exampleThe resulting relation can be the input for another relational algebra operation! (Operator composition)MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340MDDC10MDDC9PlaneMaker=“MD”(Plane)MakerModel_NoMDDC10

7、MDDC9MakerModel_NoAirbusA310AirbusA320A320AirbusA330AirbusA340MDDC10MDDC9PlaneModel_No(Maker=“MD”(Plane)Model_NoDC10DC9COMP2317Set OperationsUnion, Intersection, Set-Difference These three operations take two input relations, which must be union-compatible:Same number of fields.Corresponding fields

8、have the same type.Output is a single relation (that does not contain duplicates)COMP2318Set operations - UnionPlane1 Plane2MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340MDDC10MDDC9MakerModel_NoBoeingB727BoeingB747BoeingB757MDDC10MDDC9=MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340Boei

9、ngB727BoeingB747BoeingB757MDDC10MDDC9COMP2319Set operations Set differencePlane1 Plane2MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340MDDC10MDDC9MakerModel_NoBoeingB727BoeingB747BoeingB757MDDC10MDDC9=MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340COMP23110Set operations - IntersectionPla

10、ne1 Plane2MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340MDDC10MDDC9MakerModel_NoBoeingB727BoeingB747BoeingB757MDDC10MDDC9=MakerModel_NoMDDC9MDDC10COMP23111Cartesian ProductCombines each row of one table with every row of another tableCan_fly PlaneEmp_NoModel_No1001B7271001B7471001DC101002A320

11、1002A3401002B7571002DC91003A3101003DC9MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340BoeingB727BoeingB747BoeingB757MDDC10MDDC981 t-uples!Emp_NoModel_NoMakerModel_No1001B727AirbusA3101001B727AirbusA3201001B727AirbusA3301001B727AirbusA3401001B727BoeingB7271001B727BoeingB7471001B727BoeingB7571001

12、B727MDDC101001B727MDDC91001B747AirbusA3101001B747AirbusA3201001B747AirbusA3301001B747AirbusA3401001B747BoeingB7271001B747BoeingB7471001B747BoeingB7571001B747MDDC101001B747MDDC91001B727AirbusA3101001B727AirbusA320=COMP23112JoinGenerating all possible combinations of tuples is not usually meaningful.

13、In the previous example, it makes more sense to combine each tuple of Can_Fly with the corresponding record of the Plane. Join is a cartesian product followed by a selection: R1 R2 = R1.model_no = R2.model_no(R1 R2)Emp_noModel_NoMakerModel_NoCOMP23113Natural Join ExampleCan_fly Plane Emp_NoModel_No1

14、001B7271001B7471001DC101002A3201002A3401002B7571002DC91003A3101003DC9MakerModel_NoAirbusA310AirbusA320AirbusA330AirbusA340BoeingB727BoeingB747BoeingB757MDDC10MDDC9=Emp_NoModel_NoMaker1003A310Airbus1002A320Airbus1002A340Airbus1001B727Boeing1001B747Boeing1002B757Boeing1001DC10MD1002DC9MD1003DC9MDCOMP2

15、3114-Join ExampleWe have a Flight table that records the Flight Number, Origin, Destination, Departure Time and Arrival Time. We join this table with itself (self-join) using the condition:(Flight1.Dest = Flight2.Origin) ( Flight1.Arr_Time Flight2.Dept_Time)What should we get? NumOriginDestDep_TimeA

16、rr_Time334ORDMIA12:0014:14335MIAORD15:0017:14336ORDMIA18:0020:14337MIAORD20:3023:53394DFWMIA19:0021:30395MIADFW21:0023:43NumOriginDestDep_TimeArr_Time334ORDMIA12:0014:14335MIAORD15:0017:14336ORDMIA18:0020:14337MIAORD20:3023:53394DFWMIA19:0021:30395MIADFW21:0023:43 COMP23115-Join Example (cont)Flight

17、1.Dest = Flight2.Origin Flight1.Arr_Time N1, Nn - Nn), R)The new relation R has the same instance as R, but its schema has attribute Ni instead of attribute NiE.g., (Staff(Name - Family_Name, Salary - Gross_salary), Employee)Necessary if we need to perform a cartesian product or join of a table with

18、 itselfNameSalaryEmp_NoClark1500001006Gates50000001005Jones500001001Peters450001002Phillips250001004Rowe350001003Warnock5000001007Family_NameGross_SalaryEmp_NoClark1500001006Gates50000001005Jones500001001Peters450001002Phillips250001004Rowe350001003Warnock5000001007EmployeeStaffCOMP23117DivisionLet

19、A have two attributes x and yLet B have one attribute yA/B contains all x tuples, such that for every y tuple in B there is a xy tuple in Axys1p1s1p2s1p3s1p4s2p1s2p2s3p2s4p2s4p4Ap4p2yBs4s1xA/B/=COMP23118DivisionFind all student IDs (sids) of the students who took all courses in table Coursesidcid123

20、111701111100122312001317042314170170231cid41sid/=TakeCourseTake / CourseCOMP23119DivisionFind all student IDs (sids) of the students who took all courses provided by CSEsidcid123111701111100122312001317042314170TakeCourseTake / cid(dept = “COMP” (Course)ciddept231CSE170CSE001LANG111ECE123ECECOMP2312

21、0Additional Operators - Outer JoinAn extension of the join operation that avoids loss of information.Computes the join and then adds tuples from one relation that do not match tuples in the other relation to the result of the join.COMP23121Outer Join - Example Relation loan Relation borrowerbranch-n

22、ameloan-numberamountDowntownRedwoodPerryridgeL-170L-260L-230300017004000cust-nameloan-numberJonesHayesSmithL-170L-230L-155COMP23122Outer Join - Exampleloanbranch-nameloan-numberamountDowntownRedwoodPerryridgeL-170L-260L-230300017004000borrowercust-nameloan-numberJonesHayesSmithL-170L-230L-155branch-

23、nameloan-numberamountDowntownRedwoodL-170L-23030004000cust-nameJonesSmithLoan Borrower Join returns only the matching (or “good”) tuplesThe fact that loan L-260 has no borrower is not explicit in the resultHayes has borrowed an non-existent loan L-155 is also undetectedCOMP23123Left Outer Join -Exam

24、ple Left outer join: Loan borrowerKeep the entire left relation (Loan) and fill in informationfrom the right relation, use null if information is missing. branch-nameloan-numberamountDowntownRedwoodPerryridgeL-170L-260L-230300017004000cust-nameJonesSmithnullloanbranch-nameloan-numberamountDowntownRedwoodPerryridgeL-170L-260L-230300017004000borrowercust-nameloan-numberJonesHayesSmithL-170L-230L-155COMP23124Right Outer Join - exampleRight outer join: Loan Bo