Relational Algebra and SQL - Cornell University

1 Database Management Systems, R. Ramakrishnan and J. Gehrke1 Relational Algebra and SQLJ ohannes fromDatabase Management Systems, 3rdEdition,Ramakrishnan and Management Systems, R. Ramakrishnan and J. Gehrke2 Relational Query LanguagesvQuery languages: Allow manipulation and retrieval of data from a model supports simple, powerful QLs: Strong formal foundation based on logic. Allows for much Languages !=programming languages! QLs not expected to be Turing complete . QLs not intended to be used for complex calculations. QLs support easy, efficient access to large data Management Systems, R. Ramakrishnan and J. Gehrke3 Formal Relational Query LanguagesvTwo mathematical Query Languages form the basis for real languages ( SQL), and for implementation: Relational Algebra : More operational, very useful for representing execution plans. Relational Calculus: Lets users describe what they want, rather than how to compute it. (Non-operational, declarative.)Database Management Systems, R.

2 Ramakrishnan and J. Gehrke4 PreliminariesvA query is applied to relation instances, and the result of a query is also a relation instance. Schemasof input relations for a query are fixed (but query will run regardless of instance!) The schema for the resultof a given query is also fixed!Determined by definition of query language vs. named-field notation: Positional notation easier for formal definitions, named-field notation more readable. Both used in SQLD atabase Management Systems, R. Ramakrishnan and J. Gehrke5 Example 10/10/9658103 11/12/96R1S1S2v Sailors and Reserves relations for our ll use positional or named field notation, assume that names of fields in query results are `inherited from names of fields in query input Management Systems, R. Ramakrishnan and J. Gehrke6 Relational AlgebraDatabase Management Systems, R. Ramakrishnan and J. Gehrke7 Relational AlgebravBasic operations: Selection( ) Selects a subset of rows from relation. Projection( ) Deletes unwanted columns from relation.

3 Cross-product( ) Allows us to combine two relations. Set-difference( ) Tuples in reln. 1, but not in reln. 2. Union( ) Tuples in reln. 1 and in reln. operations: Intersection, join, division, renaming: Not essential, but (very!) each operation returns a relation, operationscan be composed! ( Algebra is closed .) Database Management Systems, R. Ramakrishnan and J. Gehrke8 Projectionsnameratingyuppy9lubber8guppy5 rusty10 sname ratingS,() ageS()2vDeletes attributes that are not in projection result contains exactly the fields in the projection list, with the same names that they had in the (only) input operator has to eliminate duplicates! (Why??) Note: real systems typically don t do duplicate elimination unless the user explicitly asks for it. (Why not?)Database Management Systems, R. Ramakrishnan and J. Gehrke9 Selection ratingS>82() sname ratingratingS,(())>82vSelects rows that satisfy selection duplicates in result! (Why?)vSchemaof result identical to schema of (only) input relation can be the input for another Relational Algebra operation!

4 (Operatorcomposition.)Database Management Systems, R. Ramakrishnan and J. Gehrke10 Union, Intersection, Set-DifferencevAll of these operations take two input relations, which must be union-compatible: Same number of fields. `Corresponding fields have the same is the schemaof result? SS12 Database Management Systems, R. Ramakrishnan and J. Gehrke11 Cross-ProductvEach row of S1 is paired with each row of schema has one field per field of S1 and R1, with field names `inherited if possible. Conflict: Both S1 and R1 have a field called sid. ((,),)CsidsidSR115 211 (sid)snameratingage(sid) 10/10 11/12 10/10 11/12 10/10 11/12/96 Renaming operator: Database Management Systems, R. Ramakrishnan and J. Gehrke12 JoinsvCondition Join:vResult schema same as that of tuples than cross-product, might be able to compute more efficientlyvSometimes called a theta-join. RcScRS = ()(sid)snameratingage(sid) Rsid1111 ..<Database Management Systems, R. Ramakrishnan and J.

5 Gehrke13 JoinsvEqui-Join: A special case of condition join where the condition ccontains only schema similar to cross-product, but only one copy of fields for which equality is Join: Equijoin on allcommon Database Management Systems, R. Ramakrishnan and J. Gehrke14 DivisionvNot supported as a primitive operator, but useful for expressing queries like: Find sailors who have reserved Ahave 2 fields, xand y; Bhave only field y: A/B = , A/B contains all xtuples (sailors) such that for everyytuple (boat) in B, there is an xytuple in A. Or: If the set of yvalues (boats) associated with an x value (sailor) in Acontains all y values in B, the x value is in general, xand ycan be any lists of fields; yis the list of fields in B, andx yis the list of fields of A.{}AyxByx ,| Database Management Systems, R. Ramakrishnan and J. Gehrke15 Examples of Division A/Bsnopnos1p1s1p2s1p3s1p4s2p1s2p2s3p2s4p 2s4p4pnop2pnop2p4pnop1p2p4snos1s2s3s4sno s1s4snos1AB1B2B3A/B1A/B2A/B3 Database Management Systems, R.

6 Ramakrishnan and J. Gehrke16 Expressing A/B Using Basic OperatorsvDivision is not essential op; just a useful shorthand. (Also true of joins, but joins are so common that systems implement joins specially.)vIdea: For A/B, compute all xvalues that are not `disqualified by some yvalue in B. xvalue is disqualifiedif by attaching y value from B, we obtain an xytuple that is not in xvalues:A/B:Database Management Systems, R. Ramakrishnan and J. Gehrke17 Find names of sailors who ve reserved boat #103vSolution 1: snamebidservesSailors((Re))=103 Solution 2: (,Re )Tempservesbid1103= (,)TempTempSailors21 snameTemp()2 Solution 3: snamebidservesSailors((Re))=103 Database Management Systems, R. Ramakrishnan and J. Gehrke18 Find names of sailors who ve reserved a red boatvInformation about boat color only available in Boats; so need an extra join: snamecolor redBoatsservesSailors(('')Re)= A more efficient solution: snamesidbid colorredBoatssSailors((('')Re))= A query optimizer can find this, given the first solution!

7 Database Management Systems, R. Ramakrishnan and J. Gehrke19 Find sailors who ve reserved a red or a green boatvCan identify all red or green boats, then find sailors who ve reserved one of these boats: (,(''' '))TempboatscolorredcolorgreenBoats= = snameTempboatsservesSailors(Re) Can also define Tempboats using union! (How?) What happens if is replaced by in this query? Database Management Systems, R. Ramakrishnan and J. Gehrke20 Find sailors who ve reserved a red anda green boatvPrevious approach won t work! Must identify sailors who ve reserved red boats, sailors who ve reserved green boats, then find the intersection (note that sidis a key for Sailors): (,(('')Re))Tempredsidcolor redBoatsserves= snameTempredTempgreenSailors(()) (,(('')Re))Tempgreensidcolor greenBoatsserves= Database Management Systems, R. Ramakrishnan and J. Gehrke21 Find the names of sailors who ve reserved all boatsvUses division; schemas of the input relations to / must be carefully chosen: (,(,Re) / ())Tempsidssid bidservesbidBoats snameTempsidsSailors() To find sailors who ve reserved all Interlake boats:/('') bidbname InterlakeBoats=.

8 Database Management Systems, R. Ramakrishnan and J. Gehrke22 SQLD atabase Management Systems, R. Ramakrishnan and J. Gehrke23 Basic SQL Query Default is that duplicates are noteliminated! Need to explicitly say DISTINCT SELECT [DISTINCT] target-listFROM relation-list[WHERE condition]SELECT SWHERE > 25 SELECT DISTINCT SWHERE > 25 Database Management Systems, R. Ramakrishnan and J. Gehrke24 SQL Querysidsnameratingage22 Sailors S, Reserves bid day 22 101 10/10/96 58 103 11/12/96 SailorsReservesDatabase Management Systems, R. Ramakrishnan and J. Gehrke25 Conceptual Evaluation Strategy Semantics of an SQL query defined in terms of the following conceptual evaluation strategy: Compute the cross-product of relation-list Discard resulting tuples if they fail condition. Delete attributes that are not in target-list If DISTINCTis specified, eliminate duplicate rows. This strategy is probably the least efficient way to compute a query!

9 An optimizer will find more efficient strategies to compute the same Management Systems, R. Ramakrishnan and J. Gehrke26 Example of Conceptual Sailors S, Reserves (sid)snameratingage(sid) 10/10 11/12/9631 10/10/9631 11/12/9658 10/10 Management Systems, R. Ramakrishnan and J. Gehrke27A Slightly Modified Query Would adding DISTINCTto this query make a difference? S, Reserves Management Systems, R. Ramakrishnan and J. Gehrke28 Find sid s of sailors who ve reserved a red ora green S, Boats B, Reserves RWHERE ( red green ) Sailors S, Boats B, Reserves red Sailors S, Boats B, Reserves green Database Management Systems, R. Ramakrishnan and J. Gehrke29 What does this query compute? S, Boats B1, Reserves R1, Boats B2, Reserves R2 WHERE red green Database Management Systems, R. Ramakrishnan and J. Gehrke30 Find sid s of sailors who ve reserved a red anda green Sailors S, Boats B, Reserves red Sailors S, Boats B, Reserves green Key field!

10 What if INTERSECT were replaced by EXCEPT? EXCEPTis set differenceDatabase Management Systems, R. Ramakrishnan and J. Gehrke31 Expressions and Strings Find triples (of ages of sailors and two fields defined by expressions) for sailors whose names begin and end with B and contain at least three characters. ASis used to name fields in result. LIKEis used for string matching `_ stands for any one character `% stands for 0 or more arbitrary characters. , ASage2, 2* B_%B Database Management Systems, R. Ramakrishnan and J. Gehrke32 Nested Queries (with Correlation)SELECT SWHERE EXISTS(SELECT*FROMR eserves )Find names of sailors who have reserved boat #103:Database Management Systems, R. Ramakrishnan and J. Gehrke33 Nested Queries (with Correlation)SELECT SWHERE NOTEXISTS(SELECT*FROMR eserves )Find names of sailors who have notreserved boat #103:Database Management Systems, R. Ramakrishnan and J. Gehrke34 Division in SWHERE NOT EXISTS (( Boats B)EXCEPT( ))Find sailors who ve reserved all boatsDatabase Management Systems, R.