Relational Algebra
COMP 421 @ Mc Query Languages
• Querylanguages:allowmanipulationandretrievalofdata from a database
• Relationalmodelsupportssimple,powerfulQLs: – Strong formal foundation
Copyright By PowCoder代写 加微信 powcoder
– Allows for much optimization
• QuerylanguagesareNOTprogramminglanguages
– QLs not expected to be “turing complete”
– QLs not intended to be used for complex calculations
– QLs support easy, efficient and sophisticated access to large data sets
COMP 421 @ Mc Relational Query Languages
• Mathematical query languages form the basis for “real” languages (e.g. SQL) and for implementation:
– Relational Algebra:
• Operational – a query is a sequence of operations on data
• Very useful for representing execution plans, i.e., to describe how a SQL query is executed internally
– Relational Calculus:
• descriptive – a query describes how the data to be
retrieved looks like
• Understanding Relational Algebra is key to understanding SQL, PigLatin, OQL, Xquery,….
COMP 421 @ Mc
Used in all Database courses But really BAD
Participates
Example Relations
Competitions
COMP 421 @ McGill
12/13/2015
01/12/2016
01/20/2016
Comes from… E/R
rank rating
Competitions
Participation
COMP 421 @ Mc Algebra: Basics
• RA consists of a set of basic operators – Input: one or two relations
• schema of each relation is known
• instance can be arbitrary – Output:arelation
• schema of output relation depends on operator and input relations
• Relational algebra is closed:
– since each operation has input relation(s), and returns a relation, operations can be composed
• Does not assume special primary key attributes in the relation
• Assumes a relation is a set
– No two tuples have the same values in all attributes COMP 421 @ Mc Algebra: Operations
• Singlerelationasinput
– Selection s: Selects a subset of tuples from a relation
– Projection ∏: projects to a subset of attributes from a relation
– Renaming ρ: of relations or attributes; useful when combining several operators
• Tworelationsasinput
– Cross Product X: Combines two relations
– Join : Combination of Cross product and selection – (Division): not covered in class
• Setoperatorswithtworelationsasinput
– Intersection (Ç)
– Union (È)
– Set Difference -: Tuples that are in the first but not the second relation
COMP 421 @ Mc : ∏L(Rin)
• thatareintheprojectionlistL
• Schemaofresultrelationcontainsexactlytheattributesof the projection list, with the same attribute names as in Rin
∏ sname,rating(Skaters)
COMP 421 @ Mc : ∏L(Rin)
• Operational Semantics:
– Imagine a tuple variable ranging over all tuples in the relation
– for each tuple: extract the projected attributes and output the reduced tuple in result relation
– eliminate duplicates
• Note: real systems typically do NOT eliminate duplicates unless the user explicitly asks for it; eliminating duplicates is a very costly operation!
∏ age (Skaters)
COMP 421 @ Mc : sC(Rin) – Schema of result relation identical to schema of Rin
• Selection: sC(Rin)
– Returns the subset of the rows of the input relation Rin that fulfill the
condition C
– Condition C involves the attributes of Rin
– No duplicates (obviously)
• Operational Semantics
– Imagine a tuple variable ranging over all tuples in the relation
– foreachtuple:checkwhetherconditionCissatisfied.Ifso,outputthetuple into the result relation
s (Skaters) rating > 8
COMP 421 @ McGill
Operator Composition
• result relation of one operation can be input for another relational algebra operation
∏ (s (Skaters)) sname,rating rating > 8
sname sname
rating rating
yuppy yuppy
• Operational Semantics:
– Stepwise one operator at a time:
• build intermediate temporary relations
– Consecutive operators on the fly: one scan through the relation
• Not always possible
COMP 421 @ Mc , Intersection, Set-Difference
• Notation:
– Rin1 È Rin2 (Union),
– Rin1 Ç Rin2 (Intersection),
– Rin1 – Rin2 (Difference),
• Usual operations on sets
• Rin1 and Rin2 must be set-compatible,
– same number of attributes
– corresponding attributes must have the same type – no need for same name
• Result schema
– same as the schema of the input relations – possibly renamed attributes
COMP 421 @ Mc Tables
Skaters (Table of DB of the Glacier Club)
OurSkaters (Table of DB of the Icy Club)
COMP 421 @ McGill
COMP 421 @
OurSkaters
Skaters È OurSkaters
Intersection
OurSkaters
Skaters Ç OurSkaters
COMP 421 @ McGill
Difference
OurSkaters
Skaters – OurSkaters
COMP 421 @ McGill
COMP 421 @ Mc
OurSkaters
Concatenation of operators
∏sname, rating, age (Skaters) Ç ∏name, rating, age (OurSkaters)
Operational Semantics
• Takeyourfavoriteset-operatoralgorithmdiscussedin COMP 250/251, MATH 240
• Intersection
– For each tuple in first relation
• For each tuple in second relation – If tuples are equal: output
• Difference
– For each tuple in first relation
• For each tuple in second
– If tuples are equal: exit loop / no output
• Ifnoearlyexit:output
COMP 421 @ Mc Algebra Quiz
COMP 421 @ Mc -Product
• Cross-Product: Rin1 X Rin2
• Each row of Rin1 is paired with each row of Rin2
• Result schema
– one attribute per attribute of Rin1
– one attribute per attribute Rin2 – field names inherited
• if both have attribute with same name: prefix with relation name
• Operational semantics
– Consider a tuple variable t1 for first relation;
– Consider a tuple variable t2 for second relation for each assignment of t1
for each assignment of t2
combine all attribute values of t1 and t2 and output them as one tuple into result relation; prefix attribute names with relation nameCOMP 421 @ Mc -Product
Skaters Participates
Skaters X Participates
yuppy yuppy
COMP 421 @ McGill
Cross-Product +
Selection with attributes from both relations
It’s what makes an advanced query language
— the way to relate tables
COMP 421 @ McGill
• Result schema the same as for cross-product Skaters
• Condition Join (Theta-Join): Rout = Rin1 C Rin2 = sC(Rin1 X Rin2)
OurSkaters
Skaters Skaters.rating > OurSkaters.rating OurSkaters COMP 421 @ McGill
• Condition Join (Theta-Join): Rout = Rin1 C Rin2 = sC(Rin1 X Rin2) • Result schema the same as for cross-product
OurSkaters
Skaters .rating
Skaters. age
COMP 421 @ McGill
13 27 willy
OurSkaters. rating
OurSkaters. age
Operational Semantics
Consider a tuple variable t1 for first relation; Consider a tuple variable t2 for second relation
for each assignment of t1
for each assignment of t2
if condition C is true, combine all attribute values of t1 and t2 and output them as one tuple into result relation; prefix attribute names with relation name
COMP 421 @ Mc -Join
• Equi-Join: Rout = Rin1 Rin1.a1 = Rin2.b1 ∧ … Rin1.an = Rin2.bn Rin2
• A special case of condition join where the condition C contains
only equalities.
• Result schema similar to cross-product,
– only one copy of attributes for which equality is specified
COMP 421 @ McGill
Skaters. age
OurSkaters. age
OurSkaters
Skaters Skaters.rating = OurSkaters.rating OurSkaters
There is only one rating attribute in the output relation.
COMP 421 @ Mc Join
• Natural Join: Equijoin on all common attributes, i.e., on all attributes with the same name
– Attributes do not need to be indicated in index of join symbol
Participates
Skaters Participates
MP 421 @ Mc
• Renaming: r(Rout(B1,…Bn),Rin(A1,…An)) – Produces a relation identical to Rin
– Output relation is named Rout
– Attributes A1, … An of Rin renamed to B1, … Bn
r(Temp, Skaters), r(Temp1(sid1,rating1),Skaters(sid,rating)))
COMP 421 @ Mc s (discussed in class)
• Relations
– Skaters(sid,sname,rating,age) – Participates(sid,cid,day)
– Competition(cid,date,type)
– Find names of skaters who have participated in competition #103 (three
solutions)
– Find names of skaters who have participated in a local competition (2 solutions)
– Find sids of skaters who have participated in a local or regional competition (1 solution)
– Find name of skaters who have participated in a local or regional competition
– Find sids of skaters who have participated in a local and regional competition (2 solutions)
COMP 421 @ Mc
– Find names of skaters who have participated in competition #101 (three solutions)
12/13/2014
01/12/2015
01/20/2015
COMP 421 @ Mc
– Find names of skaters who have participated in a local competition (2 solutions)
12/13/2014
01/12/2015
01/20/2015
COMP 421 @ Mc
– Find sids of skaters who have participated in a local or regional competition (1 solution)
12/13/2014
01/12/2015
01/20/2015
COMP 421 @ Mc
– Find names of skaters who have participated in a local or regional competition (1 solution)
12/13/2014
01/12/2015
01/20/2015
COMP 421 @ Mc
– Find sids of skaters who have participated in a local AND a regional competition (2 solution)
12/13/2014
01/12/2015
01/20/2015
COMP 421 @ Mc ome rules and definitions
• Equivalence: Let R, S,T be relations; C, C1, C2 conditions; L projection lists of the relations R and S
– Commutativity:
• ∏L(sC(R)) = sC(∏L(R))
– But only if C only considers attributes of L •R1 R2=R2 R1
– Associativity:
• R1 (R2 R3) = (R1
– Idempotence:
• ∏L2 (∏L1(R)) = ∏L2 (R)
– Only ifL2ÍL1
• sC2(sC1(R)) = sC1ÙC2(R))
COMP 421 @ Mc ummary
• The relational model has rigorously defined query languages that are simple and powerful
• Relational algebra is operational; useful as internal representation for query evaluation plans
• Several ways of expressing a given query; a query optimizer should choose the most efficient version.
• Relational Completeness of a query language:A query language (e.g., SQL) can express every query that is expressible in relational algebra
COMP 421 @ McGill
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com