Web|代做Project|Assignment|Sql代写|Database: 这是一个典型的综合了web涉及、数据库设计、sql语言代写的任务
Relational Algebra
Abdu Alawini
University of Illinois at Urbana-Champaign
CS411: database Systems
1
Announcements
Use this HW break to work on your project
2
Some slides adapted from Lois Delcambre, David Maier with permission
Relational Database Ecosystem
Plan Executor
Files & Access
Methods
Buffer Manager
Disk Space Manager
Parser
Optimizer Operator Evaluator
Lock
Manager
Transaction
Manager Recovery
Manager
Index Files
Data Files
System
Catalog
web Forms Application front ends sql interface
####### SQL
Query
Execution
Log
Files
####### DBMS
- Performance is affected by many factors
- Locking and concurrency control isolation levels
- How the data is stored physical layout, partitioning
- Auxiliary structures indices
- Different algorithms for operations query execution
- Different orderings for execution query optimization
- Reuse of materialized views, merging of query subexpressions answering queries using views; multi-query optimization
DBMS Performance
4
Todays lecture
- Relational Algebra
- Introduction
- Unary Operations
- Binary Operations
- Building Complex RA expressions
- The Big Picture
5
Why study the relational algebra?
- SQL is complicated!
- We need a simpler language of mathematical operations whose properties (e.g. commutativityand associativity) allow us to explore a space of equivalent expressions and find the one which is the fastest to execute – different ways of executing operations using different access methods, e.g. indexing – using statistics gathered about the size of relations, the distribution of attribute values, etc.
6
Recall the Relational Data Model
It all began with a breakthrough paper, by E.F. Codd in 1970: "A relational model of data for large shared data banks". Communications of the ACM 13 (6): 377
Coddsinsights:
- Separate physical implementation from logical
- Model the data independentlyfrom how it will be used (accessed, printed, etc.) – Describe the data minimallyand mathematically – A relation describes an association between data items tupleswith attributes – Use standard mathematical (logical) operations over the data these are the relational algebraor relational calculus
7
Codds Relational Algebra
- An algebra whose:
- Operands are relations or variables that represent relations.
- Operators are designed to do common things that we need to do with relations in a database.
- Relational algebra operations operate on relations and produce relations
- Unary: f: Relation Relation
- Binary: g: Relation x Relation Relation
- The result is an algebra that can be used as a query languagefor relations.
Codds Logical Operations: The Relational
Algebra
- Six basic operations:
- Projection (R)
- Selection (R)
- (Rename) (R)
- Union R 1 UR 2
- Difference R 1 R 2
- Product R 1 xR 2
- And some other useful ones:
- Join R 1 R 2
- Intersection R 1 R 2
Outline
- Relational Algebra
Introduction
- Unary Operations
- Binary Operations
- Building Complex RA expressions
- The Big Picture
10
Example Relational Instance (again)
sid name
1 Jill
2 Bo
3 Maya
fid name
13 Ives
09 Guha
34 Tannen
66 Faust
sid exp-
grade
cid sem
1 A 550-001 F
1 C 502-001 F
3 A 555-001 S
3 B 550-001 F
cid subj sem
550-001 DB F
502-001 Algo F
555-001 I&W S
666-001 Ethics S
fid cid sem
34 550-001 F
09 502-001 F
13 555-001 S
STUDENT Takes COURSE
PROFESSOR Teaches
11
Projection,
- Given a list of column names and a relation R, (R) extracts the columns in from the relation. Example:
Takes sid,exp-gradeTakes
####### 1 C
####### 3 B
####### A
####### A
exp-grade
####### 3
####### 1
sid
Note: duplicate elimination.
What does this operator correspond to in SQL? SELECT.
sid exp-
grade
cid sem
1 A 550-001 F
1 C 502-001 F
3 A 555-001 S
3 B 550-001 F
2018 A. Alawini & A. Parameswaran
Selection,
Always applied to a single relation a unary operator
exp-grade=A Account
the select operator
the predicate:
a comparator (, >, , =, , <)
an attribute or a constant
AND, OR, NOT
a relation name
(or a relational expression)
Maier
Example
- Selection R takes a relation R and extracts those rows from it that satisfy the condition . Example:
Takes exp-grade=A sid=1Takes
####### A
exp-grade
1 550-
sid cid
Can the result have duplicates? No.
What does this operator correspond to in SQL? WHERE
sid exp-
grade
cid sem
1 A 550-001 F
1 C 502-001 F
3 A 555-001 S
3 B 550-001 F
sem
F
Select and project can be combined
1. Owner(Balance < 3000Account)
2. Balance < 3000(Owner, BalanceAccount)
3. Owner(Balance < 3000(Owner, BalanceAccount))
Account
Number Owner Balance Type
101 J. Smith 1000.00 checking
102 W. Wei 2000.00 checking
103 J. Smith 5000.00 savings
104 M. Jones 1000.00 checking
105 H. Martin 10,000.00 checking
Which of these queries are
equivalent?
Maier
- Does not change the relational instance
- Changes the relational schema only
- Notation: S(B1,…,Bn)(R)
- Input schema: R(A1, …, An)
- Output schema: S(B1, …, Bn)
- Example: rename Student(sid, name)
RenamedStudent(UIN, lastname) (Student)
Renaming
Outline
- Relational Algebra
Introduction
Unary Operations
- Binary Operations
- Building Complex RA expressions
- The Big Picture
17
Cartesian Product X
- Join is a generic term for a variety of operations that connect two relations. The basic operation is the product, RxS, which concatenates every tuple in R with every tuple in S. Example:
2 Bo
1 Jill
sid name
####### STUDENT
STUDENT x SCHOOL
Cornell
Cornell
UPenn
UPenn
school
2 Bo
1 Jill
2 Bo
1 Jill
sid name
Cornell
UPenn
school
####### SCHOOL
What if the attribute school of SCHOOL was called name?
The result schema will have two names (sid, name:1, name:2)
What does this operator correspond to in SQL?
Join, : A Combination of Product
and Selection
- Products are hardly ever used alone; they are typically used in conjunction with a selection. Example:
####### 3
####### 3
####### 1
####### 1
sid:
Maya
Maya
Jill
Jill
name
####### 3 A 555-
####### B
####### C
####### A
exp-grade
####### 3 550-
####### 1 502-
####### 1 550-
sid:1 cid sem
F
F
S
F
Union
- If two relations have the same structure (Database terminology: are union-compatible. Programming language terminology: have the same type) we can perform set operations. STUDENT STUDENT U POSTDOC
18 Roger
12 Susan
1 Jill
sid name
####### POSTDOC
18 Roger
12 Susan
3 Maya
2 Bo
1 Jill
sid name sid name
1 Jill
2 Bo
3 Maya
Difference
- Another set operator. Example:
STUDENT
18 Roger
12 Susan
1 Jill
sid name
####### POSTDOC STUDENT POSTDOC
3 Maya
2 Bo
sid name sid name
1 Jill
2 Bo
3 Maya
Natural Join,
- The most common join to do is an equality join of two relations on commonly named fields, and to leave one copy of those fields in the resulting relation. Example:
Marty
Nitin
Nitin
Jill
Jill
name
####### 3 A 700-1003
####### 4 C 500-0103
####### C
####### A
####### A
exp-grade
####### 3 500-0103
####### 1 700-1003
####### 1 550-0103
sid cid
STUDENT Takes =
sid:1sid(sid:1,name, exp-grade, cid(STUDENT STUDENT.sid=Takes.sidTakes))
What if all the field names are the same in the two relations?
What if the field names are all disjoint?
Exercise
Try writing queries for these:
- The ids of students named Bo
- The names of students expecting an A
- The names of students in Ivess classes
- The sidsand names of students not enrolled
Example Relational Instance (again)
sid name
1 Jill
2 Bo
3 Maya
fid name
13 Ives
09 Guha
34 Tannen
66 Faust
sid exp-
grade
cid sem
1 A 550-001 F14
1 C 502-001 F14
3 A 555-001 S15
3 B 550-001 F14
cid subj sem
550-001 DB F14
502-001 Algo F14
555-001 I&W S15
666-001 Ethics S66
fid cid sem
34 550-001 F14
09 502-001 F14
13 555-001 S15
STUDENT Takes COURSE
PROFESSOR Teaches
24
Outline
- Relational Algebra
Introduction
Unary Operations
Binary Operations
- Building Complex RA expressions
- The Big Picture
25
Building Complex Expressions
- Algebras allow us to express sequences of operations in a natural way.
- Example
- in arithmetic algebra: (x + 4)*(y -3)
- Relational algebra allows the same.
- Three notations:
1. Sequences of assignment statements.
2. Expressions with several operators.
3. Expression trees.
1. Sequences of Assignments
- Create temporary relation names.
- Renaming can be implied by giving relations a list of
attributes.
- R3(X, Y) := R1
- Example: R3 := R1 c R2 can be written:
R4 := R1 x R2
R3 := c(R4)
2. Expressions with Several Operators
Precedence of relational operators:
1. Unary operators —select, project, rename —have highest
precedence, bind first.
2. Then come products and joins.
3. Then intersection.
4. Finally, union and set difference bind last.
But you can always insert parentheses to force the order you desire.
3. Expression Trees
- Leaves are operands (relations).
- Interior nodes are operators, applied to their child or children.
Example
- Given Cafes(name, addr), Sells(cafe, drink, price), find the names of all the cafes that are either on Maple St. or sell Mocha for less than $3.
As a Tree:
Cafes Sells
SELECTaddr = Maple St. SELECT price<3 AND drink=Mocha
PROJECTname
RENAMER(name)
PROJECTcafe
####### UNION
Q: How would we do this?
- Using Sells(cafe, drink, price), find the cafes that sell two different drinks at the same price.
More Queries
Product ( pid, name, price, category, maker-cid)
Purchase (buyer-ssn, salesperson-ssn, store, pid)
Company (cid, name, stock price, country)
Person (ssn, name, phone number, city)
Find phone numbers of people who bought gizmos from Fred.
Outline
- Relational Algebra
Introduction
Unary Operations
Binary Operations
Building Complex RA expressions
- The Big Picture
34
The Big Picture: SQL to Algebra to
Query Plan to Web Page
####### SELECT *
FROM STUDENT, Takes, COURSE WHERE STUDENT.sid = Takes.sID AND Takes.cID = cid
####### STUDENT
Takes COURSE
Merge
Hash
by cid by cid
Optimizer Execution
Engine
Storage
Subsystem
Web Server /
UI / etc
Query Plan an operator tree
Hint of Future Things: Optimization
Is Based on Algebraic Equivalences
- Relational algebra has laws of commutativity, associativity, etc. that imply certain expressions are equivalent in semantics.
- Some examples:
cd(R) = c(R) Ud(R)
c(R 1 xR 2 ) = R 1 cR 2
cd(R) =c (d(R))
They may be different in cost of evaluation!
Query optimization finds the most efficient representation to evaluate (or
one thats not bad)
a1(R) =a1(...(an(R))))
R (S T) = (R S) T
(R S) = (S R)
Selections:
Projections:
Joins:
Outline
- Relational Algebra
Introduction
Unary Operations
Binary Operations
Building Complex RA expressions
The Big Picture
37
Summary
- The relational algebra is a set of mathematical operators that compose, modify, and combine tuples within different relations – Basic SQL expressions can be expressed in this form
- Relational algebra has laws of commutativity, associativity, etc. that imply certain expressions are equivalent in semantics
- This is used in query optimization to find the most efficient representation to evaluate (or one thats not bad)
38