Relational Algebra & CalculusRelational Query LanguagesFormal Relational Query LanguagesPreliminariesExample InstancesRelational AlgebraProjectionSelectionProperties of SelectionUnion, Intersection, Set-DifferenceCross-Product (Cartesian Product)Joins: used to combine relationsJoinProperties of joinDivisionExamples of Division A/BExample of DivisionSlide 18Expressing A/B Using Basic OperatorsSummary of Relational AlgebraExercise #3Slide 22Relational CalculusDomain Relational CalculusDRC FormulasFree and Bound VariablesFind all sailors with a rating above 7Find sailors rated > 7 who have reserved boat #103Find sailors rated > 7 who’ve reserved a red boatFind sailors who’ve reserved all boatsFind sailors who’ve reserved all boats (again!)Unsafe Queries, Expressive PowerSummary of Relational Calculus1Relational Algebra & CalculusChapter 4, Part A (Relational Algebra)2Relational Query LanguagesQuery languages: Allow manipulation and retrieval of data from a database.Relational model supports simple, powerful QLs:Strong formal foundation based on logic.Allows for much optimization.Query 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 sets.3Formal Relational Query LanguagesTwo mathematical Query Languages form the basis for “real” languages (e.g. SQL), and for implementation:Relational Algebra: More operational (procedural), useful for representing execution plans.Relational Calculus: Allows users to describe what they want, rather than how to compute it: Non-operational, declarative.4PreliminariesA query is applied to relation instances, and the result of a query is also a relation instance.Schemas of input relations for a query are fixed.The schema for the result of a given query is also fixed! - determined by definition of query language constructs.Positional vs. named-field notation: Positional notation easier for formal definitions, named-field notation more readable. Both used in SQL5Example Instancessid sname rating age22 dustin 7 45.031 lubber 8 55.558 rusty 10 35.0sid sname rating age28 yuppy 9 35.031 lubber 8 55.544 guppy 5 35.058 rusty 10 35.0sid bid day22 101 10/10/9658 103 11/12/96R1S1S2“Sailors” and “Reserves” relations for our examples.We’ll use positional or named field notation, assume that names of fields in query results are `inherited’ from names of fields in query input relations.6Relational AlgebraBasic operations:Selection ( ) Selects a subset of rows from relation.Projection ( ) Deletes unwanted columns from relation.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. 2.Additional operations:Intersection, join, division, renaming: Not essential, but (very!) useful.Since each operation returns a relation, operations can be composed: algebra is “closed”.7Projectionsname ratingyuppy 9lubber 8guppy 5rusty 10sname ratingS,( )2age35.055.5ageS( )2Deletes attributes that are not in projection list.Schema of result contains exactly the fields in the projection list, with the same names that they had in the input relation.Projection operator has to eliminate duplicates! Why?Note: real systems typically don’t do duplicate elimination unless the user explicitly asks for it (by DISTINCT). Why not?8SelectionratingS82( )sid sname rating age28 yuppy 9 35.058 rusty 10 35.0sname ratingyuppy 9rusty 10 sname ratingratingS,( ( ))82Selects rows that satisfy selection condition.No duplicates in result! Why?Schema of result identical to schema of input relation.What is Operator composition?9Properties of Selection)2(8)1(8)21(8SratingSratingSSrating ))2(20(8))2(8(20SageratingSratingage Selection is distributive over binary operatorsSelection is commutativeSelection commutes with projection, if attributes for selection are among the attributes in the set unto which projection is taking place))2(,(8))2(8(,SratingageratingSratingratingage10Union, Intersection, Set-DifferenceAll of these operations take two input relations, which must be union-compatible:Same number of fields.`Corresponding’ fields have the same type.What is the schema of result?sid sname rating age22 dustin 7 45.031 lubber 8 55.558 rusty 10 35.044 guppy 5 35.028 yuppy 9 35.0sid sname rating age31 lubber 8 55.558 rusty 10 35.0S S1 2S S1 2sid sname rating age22 dustin 7 45.0S S1 211Cross-Product (Cartesian Product)Each row of S1 is paired with each row of R1.Result 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.( ( , ), )C s id sid S R1 1 5 2 1 1  (sid) sname rating age (sid) bid day22 dustin 7 45.0 22 101 10/ 10/ 9622 dustin 7 45.0 58 103 11/ 12/ 9631 lubber 8 55.5 22 101 10/ 10/ 9631 lubber 8 55.5 58 103 11/ 12/ 9658 rusty 10 35.0 22 101 10/ 10/ 9658 rusty 10 35.0 58 103 11/ 12/ 96 Renaming operator:12Joins: used to combine relationsCondition Join:Result schema same as that of cross-product.Fewer tuples than cross-product, might be able to compute more efficientlySometimes called a theta-join. RcScR S  ( )(sid) sname rating age (sid) bid day22 dustin 7 45.0 58 103 11/ 12/ 9631 lubber 8 55.5 58 103 11/ 12/ 96S RS sid R sid1 11 1. .13JoinEqui-Join: A special case of condition join where the condition c contains only equalities.Result schema similar to cross-product, but only one copy of fields for which equality is specified.Natural Join: Equijoin on all common fields.sid sname rating age bid day22 dustin 7 45.0 101 10/ 10/ 9658 rusty 10 35.0 103 11/ 12/ 96S Rsid1 114Properties of joinSelecting power: can join be used for selection?Is join commutative? = ?Is join associative?Join and projection perform complementary functionsLossless and lossy decomposition11 RS 11 SR ?1)11()11(1 CRSCRS  15DivisionNot supported as a primitive operator, but useful for expressing queries like: Find sailors who have reserved all boats.Let A have 2