UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-1UnionUnion-compatible- two relations are union-compatible if they have thesame # of attributes and each attribute must be fromthe same domain- to compute R1R2, R1and R2must beunion-compatibleOrder of relations unimportantR1R2= R2R1R1R2= {r R1r R2}<ex> R1(A, B) = {a1b1, a2b1}R2(A, B) = {a1b1, a4b2}R3= R1R2= {a1b1, a2b1, a4b2}UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-2Set DifferenceR1and R2must be union-compatibleR1R2= {r r R1r R2}Order of relation is important<ex> R1(A, B) = {a1b1, a2b1}R2(A, B) = {a1b1, a4b2}R3= R1R2= {a2b1}UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-3IntersectionR1and R2must be union-compatibleR1R2= {r r R1r R2}Order of relation is unimportant<ex> R1(A, B) = {a1b1, a2b1}R2(A, B) = {a1b1, a4b2}R3= R1R2= {a1b1}UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-4Cartesian ProductR1R2= {<r1, r2> r1R1r2R2}<ex> R1(A, B) = {a1b1, a2b1}R2(A, B) = {a1b1, a4b2}R3= R1R2= {a1b1a1b1,a1b1a4b2,a2b1a1b1,a2b1a4b2}<ex>Course = (C#, Cname, Dept)Class = (C#, Semester, Prof)Course Class = (C#, Cname, Dept, C#, Semester, Prof)UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-5SelectionF- F: formula (or predicate)- selection criteria can be either logical or arithmetic-F(R) creates a relation consisting of tuples in Rfor which F(t) is trueF(R) = {t t R F(t)}Selection is commutativeA=a(B=b(R)) =B=b(A=a(R))=A=a,B=b(R)Selection is distributive over binary operatorsF(R1R2) =F(R1)F(R2)F(R1R2) =F(R1)F(R2)F(R1R2) =F(R1)F(R2)UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-6SelectionTheorem:F(R1R2) =F(R1)F(R2)<Proof>F(R1R2) = {t t R1R2F(t)}= {t t R1t R2F(t)}= {t t R1F(t) t R2F(t)}=F(R1)F(R2)UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-7ProjectionA vertical subset of a relationEliminates some attributes from a relation and theneliminate duplicate tuples, if any.<ex> Class (C#, Semester,Dept)--------------------------------------PH1 F93 PHILPH1 S94 PHILCS662 S94 CSCS662 S93 CSC#(Class) = C# {PH1, CS662}Projection commutes with selection, if attributes for selectionare among attributes in the set unto which is taking placeX(F(R)) =F(X(R))if X R and F is a valid expression in XUVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-8JoinCentral to relational database theory- used to combine related tuples from two relationsinto single tuplesGeneral formR |<join condition>Swhere R=(A1, ..., An) and S=(B1, ..., Bm)will result in Q=(A1, ..., An, B1, ..., Bm)- Q has one tuple for each combination of tuples (onefrom R and one from S), whenever the combinationsatisfy the join conditionDifference from Cartesian products- in join, only combinations of tuples satisfying thejoin condition appear in the result- in Cartesian product, all combinations of tuples appearUVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-9JoinTheta join- a join condition is of the form AiBjwhere Aiis an attribute of R and Bjof S,and Aiand Bjhave the same domain- is one of the comparison operators:{ =, , <, >, }- R | S = (R S): selection predicateEquijoin- if only comparison operator used is "=", it is equijoin- results of an equijoin always have one or more pairs ofattributes that have identical values in every tuple- get rid of the second attribute: natural joinUVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-10Natural JoinAn equijoin on all attributes with the same name in tworelations, followed by removal of superfluous attributes1) compute r s2) for each attribute A named in both R and S, selectthose tuples from r s where r.A = s.A(they are called join attributes)3) for each attribute, project out s.AJoin selectivity- if no combination of tuples satisfies the join condition,it results in an empty relation with 0 tuples- if r has n tuples and s has m tuples, the result ofa join will be between 0 and n m tuples- join selectivity = expected size of result / n m- if no join condition to satisfy, join becomesa Cartesian product (also called a cross join)UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-11Properties of JoinJoin has a selecting power- to findA=a(r),define s(A) with a single tuple t such that t(A)=aand perform r s =A=a(r)- to findA=a,B=b(r),create a singleton selection relation swith schema (A, B) such that s = {ab}then r s =A=a,B=b(r)Join is commutativer s = s rJoin is associativer (s q) = (r s) qUVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-12Properties of JoinJoin and projection operators are not inverse ofeach other, but perform complementary functions- let q = r s and r’ =R(q)thenR(q) =R(r s) r<ex> r: A B---------------a1 b1a1 b2s: B C---------------b1 c1q: A B C---------------------a1 b1 c1AB(q) = r’: A B---------a1 b1UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-13Properties of JoinWhat if we reverse the order of and ?- let r =R(q) and s =S(q)where q is a relation with Q = R Sthen q r s =R(q)S(q)UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-14Properties of Join: Exampler: A B s: B C--------------- ---------------a1 b1 b1 c1a2 b1 b1 c2r s: A B C----------------------a1 b1 c1a1 b1 c2a2 b1 c1a2 b1 c2q: A B C---------------------a1 b1 c1a2 b1 c2r=R(q): A B s=S(q): B C--------- ---------a1 b1 b1 c1a2 b1 b1 c2UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-15Lossless DecompositionRelation q decomposes losslessly into schemas R and Sif q =R(q)S(q)<ex>r: A B s: B C--------------- ---------------a1 b1 b1 c1a2 b2 b2 c2r s = q: A B C----------------------a1 b1 c1a2 b2 c2r’=AB(q): A B---------a1 b1a2 b2UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-16DivisionThe relation r s is a relation with schema R Ssuch that a tuple t q = r s, if for every tuple Tss,there is a tuple Trr satisfyingtr(S) = ts(S)tr(R S) = t((R S)Suitable for queries that include the phrase "for all"Division is seldom implemented in practicer s =R S(r)R S((R S(r) s) r)UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-17Examples of DivisionFind all customers who have an account at all brancheslocated in BrooklynBranch-schema (B-name, Assets, B-city)Deposit-schema (B-name, A#, C-name, Balance)1) All branches in Brooklynr1=B name(B city=Brooklyn (branch))2) All (C-name, B-name) pairs from depositr2=B name,C name(deposit)3) Customers in r2with every branch name in r1r3= r2r1=B name,C name(deposit)B name(B city=Brooklyn(branch))UVA DEPARTMENT OF COMPUTER SCIENCEAlgebra-18Examples of DivisionGiven the relation showing the faculty-student relationships,find the faculty who teaches every students in the given set.r: Faculty# Student#-----------------------18 10518 10618 10824 10524 10624 107s: Student# s’: Student# s": Student#----------- ----------- -----------105 106 105108 106107108r s: Faculty# r s’: