11Relational AlgebraOperatorsExpression Trees2What is an “Algebra”Mathematical system consisting of:Operands --- variables or values fromwhich new values can be constructed.Operators --- symbols denoting proceduresthat construct new values from givenvalues.3What is Relational Algebra?An algebra whose operands arerelations or variables that representrelations.Operators are designed to do the mostcommon things that we need to do withrelations in a database. The result is an algebra that can be usedas a query language for relations.24RoadmapThere is a core relational algebra thathas traditionally been thought of as therelational algebra.But there are several other operatorswe shall add to the core in order tomodel better the language SQL --- theprincipal language used in relationaldatabase systems.5Core Relational AlgebraUnion, intersection, and difference. Usual set operations, but require bothoperands have the same relation schema.Selection: picking certain rows.Projection: picking certain columns.Products and joins: compositions ofrelations.Renaming of relations and attributes.6SelectionR1 := SELECTC (R2)C is a condition (as in “if” statements) thatrefers to attributes of R2. R1 is all those tuples of R2 that satisfy C.37ExampleRelation Sells:bar beer priceJoe’s Bud 2.50Joe’s Miller 2.75Sue’s Bud 2.50Sue’s Miller 3.00JoeMenu := SELECTbar=“Joe’s”(Sells):bar beer priceJoe’s Bud 2.50Joe’s Miller 2.758ProjectionR1 := PROJL (R2)L is a list of attributes from the schema ofR2. R1 is constructed by looking at each tupleof R2, extracting the attributes on list L, inthe order specified, and creating fromthose components a tuple for R1. Eliminate duplicate tuples, if any.9ExampleRelation Sells:bar beer priceJoe’s Bud 2.50Joe’s Miller 2.75Sue’s Bud 2.50Sue’s Miller 3.00Prices := PROJbeer,price(Sells):beer priceBud 2.50Miller 2.75Miller 3.00410ProductR3 := R1 * R2 Pair each tuple t1 of R1 with each tuple t2 ofR2. Concatenation t1t2 is a tuple of R3. Schema of R3 is the attributes of R1 and R2,in order. But beware attribute A of the same name inR1 and R2: use R1.A and R2.A.11Example: R3 := R1 * R2R1( A, B )1 23 4R2( B, C )5 67 89 10R3( A, R1.B, R2.B, C )1 2 5 61 2 7 81 2 9 103 4 5 63 4 7 83 4 9 1012Theta-JoinR3 := R1 JOINC R2 Take the product R1 * R2. Then apply SELECTC to the result.As for SELECT, C can be any boolean-valued condition. Historic versions of this operator allowedonly A theta B, where theta was =, <, etc.;hence the name “theta-join.”513ExampleSells( bar, beer, price ) Bars( name, addr )Joe’s Bud 2.50 Joe’s Maple St.Joe’s Miller 2.75 Sue’s River Rd.Sue’s Bud 2.50Sue’s Coors 3.00 BarInfo := Sells JOIN Sells.bar = Bars.name Bars BarInfo( bar, beer, price, name, addr )Joe’s Bud 2.50 Joe’s Maple St.Joe’s Miller 2.75 Joe’s Maple St.Sue’s Bud 2.50 Sue’s River Rd.Sue’s Coors 3.00 Sue’s River Rd.14Natural JoinA frequent type of join connects tworelations by: Equating attributes of the same name, and Projecting out one copy of each pair ofequated attributes.Called natural join.Denoted R3 := R1 JOIN R2.15ExampleSells( bar, beer, price ) Bars( bar, addr )Joe’s Bud 2.50 Joe’s Maple St.Joe’s Miller 2.75 Sue’s River Rd.Sue’s Bud 2.50Sue’s Coors 3.00 BarInfo := Sells JOIN BarsNote Bars.name has become Bars.bar to make the naturaljoin “work.” BarInfo( bar, beer, price, addr )Joe’s Bud 2.50 Maple St.Joe’s Milller 2.75 Maple St.Sue’s Bud 2.50 River Rd.Sue’s Coors 3.00 River Rd.616RenamingThe RENAME operator gives a newschema to a relation.R1 := RENAMER1(A1,…,An)(R2) makes R1 bea relation with attributes A1,…,An andthe same tuples as R2.Simplified notation: R1(A1,…,An) := R2.17ExampleBars( name, addr )Joe’s Maple St.Sue’s River Rd. R( bar, addr )Joe’s Maple St.Sue’s River Rd.R(bar, addr) := Bars18Building Complex Expressions Algebras allow us to expresssequences of operations in a naturalway. Example: in arithmetic --- (x + 4)*(y - 3). Relational algebra allows the same. Three notations, just as in arithmetic: Sequences of assignment statements. Expressions with several operators. Expression trees.719Sequences of AssignmentsCreate temporary relation names.Renaming can be implied by givingrelations a list of attributes.Example: R3 := R1 JOINC R2 can bewritten:R4 := R1 * R2R3 := SELECTC (R4)20Expressions in a Single Assignment Example: the theta-join R3 := R1 JOINC R2can be written: R3 := SELECTC (R1 * R2) Precedence of relational operators: Unary operators --- select, project, rename --- havehighest precedence, bind first. Then come products and joins. Then intersection. Finally, union and set difference bind last. But you can always insert parentheses toforce the order you desire.21Expression TreesLeaves are operands --- either variablesstanding for relations or particular,constant relations.Interior nodes are operators, applied totheir child or children.822ExampleUsing the relations Bars(name, addr)and Sells(bar, beer, price), find thenames of all the bars that are either onMaple St. or sell Bud for less than $3.23As a Tree:Bars SellsSELECTaddr = “Maple St.”SELECT price<3 AND beer=“Bud”PROJECTnameRENAMER(name)PROJECTbarUNION24ExampleUsing Sells(bar, beer, price), find the barsthat sell two different beers at the sameprice.Strategy: by renaming, define a copy ofSells, called S(bar, beer1, price). Thenatural join of Sells and S consists ofquadruples (bar, beer, beer1, price) suchthat the bar sells both beers at this price.925The TreeSells SellsRENAMES(bar, beer1, price)JOINPROJECTbarSELECTbeer != beer126Schemas for Interior NodesAn expression tree defines a schema forthe relation associated with eachinterior node.Similarly, a sequence of assignmentsdefines a schema for each relation onthe left of the := sign.27Schema-Defining Rules 1For union, intersection, and difference,the schemas of the two operands mustbe the same, so use that schema forthe result.Selection: schema of the result is thesame as the schema of the operand.Projection: list of attributes tells us theschema.1028Schema-Defining Rules 2Product: the schema is the attributes ofboth relations. Use R.A, etc., to distinguish two