RELATIONAL ALGEBRA (II)Unary Relational Operations: SELECT and PROJECTRelational Algebra Operations from Set TheoryBinary Relational Operations: JOIN and DIVISIONAdditional Relational OperationsSPECIAL RELATIONAL OPERATORSJOIN OPERATORSSlide 8Slide 9DIVISIONEXAMPLES OF DIVISIONSlide 12Slide 13FORMAL DEFINITION OF DIVISIONEXAMPLES OF ALGEBRA QUERIESQUERY Q1QUERY Q1 (cont’d)QUERY Q2QUERY Q3QUERY Q4QUERY Q5QUERY Q6QUERY Q7QUERY 8QUERY 9QUERY Q10Slide 27Cartesian ProductSlide 29Examples of Queries in Relational AlgebraNatural-JoinDivisionDivision (Cont’d)Relational AlgebraSlide 35Slide 36Slide 37Slide 38Rename operationRename operation (contd)Slide 41Slide 42Slide 43Slide 44RELATIONAL ALGEBRA (II)Prof. Sin-Min LEEDepartment of Computer ScienceUnary Relational Operations: SELECT and PROJECTThe PROJECT OperationSequences of Operations and the RENAME OperationThe SELECT OperationRelational Algebra Operations from Set TheoryThe UNION, INTERSECTION, and MINUS OperationsThe CARTESIAN PRODUCT (or CROSS PRODUCT) OperationBinary Relational Operations: JOIN and DIVISIONThe JOIN OperationThe EQUIJOIN and NATURAL JOIN Variations of JOINA Complete Set of Relational Algebra OperationsThe DIVISION OperationAdditional Relational OperationsAggregate Functions and GroupingRecursive Closure OperationsOUTER JOIN OperationsThe OUTER JOIN OperationSPECIAL RELATIONAL OPERATORSThe following operators are peculiar to relations:- Join operatorsThere are several kind of join operators. We only consider three of these here (others will be considered when we discuss null values):- (1) Condition Joins- (2) Equijoins- (3) Natural Joins- DivisionJOIN OPERATORS Condition Joins: - Defined as a cross-product followed by a selection: R ⋈c S = σc(R S) (⋈ is called the bow-tie)where c is the condition.- Example:Given the sample relational instances S1 and R1The condition join S ⋈S1.sid<R1.sid R1 yieldsEquijoin:Special case of the condition join where the join condition consists solely of equalities between two fields in R and S connected by the logical AND operator (∧).Example: Given the two sample relational instances S1 and R1The operator S1 R.sid=Ssid R1 yieldsNatural Join- Special case of equijoin where equalities are implicitly specified on all fields having the same name in R and S.- The condition c is now left out, so that the “bow tie” operator by itself signifies a natural join.- N. B. If the two relations have no attributes in common, the natural join is simply the cross-product.DIVISION- The division operator is used for queries which involve the ‘all’qualifier such as “Find the names of sailors who have reserved all boats”.- The division operator is a bit tricky to explain, and perhaps best approached through examples as will be done here.EXAMPLES OF DIVISIONDIVISIONInterpretation of the division operation A/B:- Divide the attributes of A into 2 sets: A1 and A2.- Divide the attributes of B into 2 sets: B2 and B3.- Where the sets A2 and B2 have the same attributes.- For each set of values in B2:- Search in A2 for the sets of rows (having the same A1 values) whose A2 values (taken together) form a set which is the same as the set of B2’s.- For all the set of rows in A which satisfy the above search, pick out their A1 values and put them in the answer.DIVISIONExample: Find the names of sailors who have reserved all boats:(1) A = sid,bid(Reserves). A1 = sid(Reserves) A2 = bid(Reserves)(2) B2 = bid(Boats) B3 is the rest of B. Thus, B2 ={101, 102, 103, 104}(3) Find the rows of A such that their A.sid is the same and their combined A.bid is the set B2. Thus we find A1 = {22}(4) Get the set of A2 corresponding to A1: A2 = {Dustin}FORMAL DEFINITION OF DIVISION The formal definition of division is as follows: A/B = x(A) - x((x(A) B) – A)EXAMPLES OF ALGEBRA QUERIESIn the rest of this chapter we shall illustrate queries using the following new instances S3 of sailors, R2 of Reserves and B1 of boats.QUERY Q1Given the relational instances:(Q1) Find the names of sailors who have reserved boat 103sname((σbid=103 Reserves) ⋈ Sailors)The answer is thus the following relational instance{<Dustin>, <Lubber>, <Horatio>}QUERY Q1 (cont’d)There are of course several ways to express Q1 in relational algebra.Here is another:sname(σbid=103(Reserves⋈ Sailors))Which of these expressions should we use?That is a question of optimization. Indeed, when we describe how to state queries in SQL, we can leave it to the optimizer in the DBMS to select the nest approach.QUERY Q2(Q2) Find the names of sailors who have reserved a red boat.sname((σcolor=‘red’Boats) ⋈ Reserves ⋈ Sailors)QUERY Q3(Q3) Find the colors of boats reserved by Lubber.color((σsname=‘Lubber’Sailors)Sailors ⋈ Reserves ⋈ Boats)QUERY Q4(Q4) Find the names of Sailors who have reserved at least one boatsname(Sailors ⋈ Reserves)QUERY Q5 (Q5) Find the names of sailors who have reserved a red or a green boat. (Tempboats, (σcolor=‘red’Boats) ∪ (σcolor=‘green’Boats)) sname(Tempboats ⋈ Reserves ⋈ Sailors)QUERY Q6(Q6) Find the names of Sailors who have reserved a red and a green boat.It seems tempting to use the expression used in Q5, replacing simply ∪ by ∩. However, this won’t work, for such an expression is requesting the names of sailors who have requested a boat that is both red and green! The correct expression is as follows:(Tempred, sid((σcolor=‘red’Boats) ⋈ Reserves)) (Tempgreen, sid((σcolor=‘green’Boats) ⋈ Reserves)) sname ((Tempred ∩ Tempgreen) ⋈ Sailors)QUERY Q7(Q7) Find the names of sailors who have reserved at least two boats.(Reservations, sid,sname,bid(Sailors ⋈ Reserves))(Reservationpairs(1sid1, 2sname, 3bid1, 4sid2,5sname, 6bid2), ReservationsReservations)sname1σ(sid1=sid2)(bid1bid2)Reservationpairs)QUERY 8(Q8) Find the sids of sailors with age over 20 who have not reserved a red boat.sid(σage>20Sailors) - sid((σcolor=‘red’Boats) ⋈ Reserves ⋈ Sailors)QUERY 9(Q) Find the names of sailors who have reserved all boats.(Tempsids, (sid,bidReserves) / (bidBoats))sname(Tempsids ⋈ SailorsQUERY Q10(Q10) Find the names of sailors who have reserved all boats called Interlake.(Tempsids,
View Full Document