01relational algebra

Click to edit Master title style,Click to edit Master text styles,Second level,*,Relational Algebra,A relation is a set of tuples. Each,relational algebra operation,takes as input a list of relations and produces a single relation.,General form:,Operator,Arguments,(List of Relations), New Relation,After each operation, the remaining attributes are carried to the new relation. The attributes may be renamed, but their domain remains the same.,1,Relational Algebra Operations,UnionR, S,IntersectionR S,DifferenceR - S,AssignmentS(B,1,B,n,) := R(A,1,A,n,),SelectionR where C,ProjectionRA,1,A,n,Product R x S,JoinR,S,DivisionR, S,2,Set Theoretic Operations,Regular set operations on relations,A set operation requires two participating relations R and S to be,compatible,R and S should have the same attributes,R(Name:D1, Email:D2),S(Name:D1, Email:D2, Address:D3),T(Name:D1, Email:D4),V(Name:D1, Email:D2),Which relations above are union (set operation) compatible?,Union compatibility may require type conversion (casting).,3,Set Operations,4,Assignment and Alias,Alias S:=R,Given a relation R,head(R)=A,1,A,n,is the list of attributes in R.,For each attribute,dom(A),gives the domain of A,name(A),gives the name of the attribute,Suppose B,1,B,n,is a list of attributes such that for each i, dom(B,i,) = dom(A,i,),Then,assignment,(:=) changes the names of some or all of the attributes in R and results in a new relation S,S(B,1,B,n,) := R(A,1,A,n,),and dom(B,1,) = dom(A,1,) dom(B,n,) = dom(A,n,).,5,6,Set Operations,Consider the tales R and S:,A,B,C,a1,b1,c1,a1,b2,c3,a2,b1,c2,A,B,C,a1,b1,c1,a1,b1,c2,a1,b2,C3,a3,b2,c3,R,S,R, S = ?,R S = ?,R S= ?,S - R= ?,7,Projection,Select all tuples,from relation R,restrict each tuple,to the input attributes,written as,RA,1,A,n,or,for attributes A,1,A,n,from R,meaning,for each tuple in R,construct a new tuple containing,only attributes A,1,A,n,place the new tuple in the result,end-for,remove duplicate tuples to preserve,the,set property,8,Projection,Find all the id of customers and all cities the customers are located,CUSTOMERcity,CUSTOMERcid,9,Selection,Select certain tuples from a relation R based on a boolean condition C,written as,R where C,or,meaning:,for each tuple t in R,if t makes C true then,return t in the resulting relation,end-for,10,Selection condition,The selection condition C is built of,atomic conditions of the form,A,i,A,j,or,A,i,c,where,A,i, A,j,are attributes and c is a constant of the same domain of values, and,is a comparison predicate of the form: =, , = , etc.,If C,1, C,2,are selection conditions, then so are,C,1,AND C,2,C,1,OR C,2,NOT C,1,11,Selection,Find all the products stored in Dallas that cost more than 0.50$.,PRODUCT where city=Dallas” and price0.5,12,Product,|R|: the number of the elements in relation R,Multiply the relations R and S, producing |R|x|S| many tuples with attributes head(R)+head(S),product combines two relations into one “big” relation,Meaning,for each tuple r in R do,for each tuple s in S do,compute a new tuple containing,all attributes in r and s,end-for,end-for,13,Product - example,A,B,C,a1,b1,c1,a1,b2,c3,a2,b1,c2,B,C,D,b1,c1,d1,b1,c1,d3,b2,c2,d2,b1,c2,d4,R,S,R,x S,14,Relational Algebra - Join,For all pairs of tuples r and s from relations R and S where,Head(R)=A,1,A,n,B,1,B,k,and Head(S)=,B,1,B,k,C,1,C,m,such that rB,1,B,k, = sB,1,B,k,include a tuple in,R,S,with,attributes A,1,A,n,B,1,B,k,C,1,C,m,The attributes in common between the two relations (B,1,B,k,) are called the “,join attributes,”,The join is a,product,followed by a,selection,on the join attributes, and a,projection,to remove the duplication of the join attributes formally: you have to rename the join attributes in one relation so that you can express the selection/projection operations,15,Relational Algebra Join (Example-1),A,B,C,a1,b1,c1,a1,b2,c3,a2,b1,c2,B,C,D,b1,c1,d1,b1,c1,d3,b2,c2,d2,b1,c2,d4,R,S,R,S,A,R.B,R.C,S.B,S.C,D,a1,b1,c1,b1,c1,d1,a1,b1,c1,b1,c1,d3,a2,b1,c2,b1,c2,d4,16,Relational Algebra Join (Example-2),EXAMPLE： ORDERS JOIN CUSTOMERS,17,Relational Algebra Join (Example-3),Give all (cname, aname) pairs where the customer places an order through the agent.,(,C JOIN O JOIN A) cname, aname,?,* (,R JOIN S) JOIN T = R JOIN (S JOIN T),(,Ccid, cname JOIN O) JOIN A) cname, aname,18,Self-Join,Give (cid, cid) pairs of customers who live in the same city.,K:=CUSTOMERS,1.(,C JOIN K) C.cid, K.cid,?,2.(,C x K) where C.city = K.city)C.cid, K.cid,?,3. (,C x K) where C.city = K.city and C.cid 500.00) aid,2. O JOIN C where city = Kyoto and dollars 500.00 aid,?,4. (,C where city = Kyoto) JOIN (O where dollars 500.00)aid,3.(,O JOIN C) where city = Kyoto and dollars 500.00 aid,?,25,Problem 1,Find the names of customers who order at least one product priced at $0.50,(,P where price=0.50)pid,ORDERS),C)cname,26,Problem 2,Find cids of all customers who do not place any order through agent a03.,CUSTOMERScid (ORDERS where aid=a03)cid,?,or,ORDERScid, (ORDERS where aid=a03)cid,?,Q: Are the results of the two queries the same?,27,Problem 3,Find all customers who place orders only through agent a03,ORDERScid (ORDERS where aida03)cid,Q: Can the ORDERScid be replaced by CUSTOMERScid?,28,Problem 4,Get aids of agents who supply only product p02.,Oaid - (O where pid p02)aid,?,Aaid - (O where pid p02)aid,?,or,29,Problem 5,Find the products that have never been ordered by a customer based in New York through an agent based in Boston。,PRODUCTpid (C where city=New York)cid,ORDERS) ,AGENTS where city=Boston)pid,30,Problem 6,Get cids of customers who order all products that anybody orders.,ORDERScid, pid ORDERSpid,31,Outer Join,A,B,a1,b1,a2,b2,a3,b5,B,C,b1,c1,b2,c2,b3,c3,b4,c4,R,S,A,B,C,a1,b1,c1,a2,b2,c2,a3,b5,null,null,b3,c3,null,b4,c4,R outer join S,32,Theta Join,R theta Join S,(,R x S) where R.B,q,S.B, where,q,is =, , , =.,If,q,is =, it is called,equijoin,.,33,