**Unformatted text preview:**

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 LanguagesQuery 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 languagesQLs 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 LanguagesTwo 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.4PreliminariesA 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 AlgebraBasic 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 10sname ratingS,( )2age35.055.5ageS( )2Deletes 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?8SelectionratingS82( )sid sname rating age28 yuppy 9 35.058 rusty 10 35.0sname ratingyuppy 9rusty 10 sname ratingratingS,( ( ))82Selects 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 operatorsSelection is commutativeSelection commutes with projection, if attributes for selection are among the attributes in the set unto which projection is taking place))2(,(8))2(8(,SratingageratingSratingratingage10Union, Intersection, Set-DifferenceAll 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 2S S1 2sid sname rating age22 dustin 7 45.0S S1 211Cross-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 relationsCondition Join:Result schema same as that of cross-product.Fewer tuples than cross-product, might be able to compute more efficientlySometimes 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. .13JoinEqui-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 114Properties of joinSelecting power: can join be used for selection?Is join commutative? = ?Is join associative?Join and projection perform complementary functionsLossless and lossy decomposition11 RS 11 SR ?1)11()11(1 CRSCRS 15DivisionNot supported as a primitive operator, but useful for expressing queries like: Find sailors who have reserved all boats.Let A have 2

View Full Document