程序代写代做 graph C finance database AI Chapter 2: 
 Introduction to the Relational Model

Chapter 2: 
 Introduction to the Relational Model
Database System Concepts, 6th Ed.
©Silberschatz, Korth and Sudarshan

See www.db-book.com for conditions on re-use

Example of a Relation
attributes (or columns)
tuples (or rows)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.2 ©Silberschatz, Korth and Sudarshan

Attribute Types
■ The set of allowed values for each attribute is called the domain of the attribute
■ Attribute values are (normally) required to be atomic; that is, indivisible
■ The special value null is a member of every domain
■ The null value causes complications in the definition of many
operations
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.3 ©Silberschatz, Korth and Sudarshan

Relation Schema and Instance
■ A1, A2, …, An are attributes
■ R = (A1, A2, …, An ) is a relation schema Example:
instructor = (ID, name, dept_name, salary)
■ Formally, given sets D1, D2, …. Dn a relation r is a subset of 
 D1 x D2 x … x Dn

Thus, a relation is a set of n-tuples (a1, a2, …, an) where each ai
■ The current values (relation instance) of a relation are specified by
a table
■ An element t of r is a tuple, represented by a row in a table
∈ Di
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.4 ©Silberschatz, Korth and Sudarshan

Relations are Unordered
■ Order of tuples is irrelevant (tuples may be stored in an arbitrary order) ■ Example: instructor relation with unordered tuples
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.5 ©Silberschatz, Korth and Sudarshan

Database
■ A database consists of multiple relations
■ Information about an enterprise is broken up into parts
instructor 
 student 
 advisor
■ Bad design: 

univ (instructor_ID, name, dept_name, salary, student_ID, ..)

results in
● repetitionofinformation(e.g.,twostudentshavethesameinstructor) ● the need for null values (e.g., represent an student with no advisor)
■ Normalization theory (Chapter 7) deals with how to design “good” relational schemas
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.6 ©Silberschatz, Korth and Sudarshan

Keys
■ LetK⊆R
■ K is a superkey of R if values for K are sufficient to identify a unique
tuple of any possible relation r(R)
● Example: {ID} and {ID, name} are both superkeys of instructor. ● However:{name}isnotasuperkey.(Why?)
■ Superkey K is a candidate key if K is minimal
 Example: {ID} is a candidate key for Instructor
■ One of the candidate keys is selected to be the primary key.
● whichone?
■ Foreign key constraint: Value in one relation must appear in another
● Referencingrelation ● Referencedrelation
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.7 ©Silberschatz, Korth and Sudarshan

Keys and Foreign Keys: Example
■ E-Commerce Database with customers, products, and purchases: CUSTOMER
CID
CNAME
CADDRESS
PURCHASE
CID
PID
TIMEDATE
PRICE
PRODUCT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.8 ©Silberschatz, Korth and Sudarshan
PID
PNAME
PDESCRIPTION
PPRICE

Keys and Foreign Keys: Example
■ E-Commerce Database with customers, products, and purchases: CUSTOMER
CID
CNAME
CADDRESS
PURCHASE
CID
PID
TIMEDATE
PRICE
PRODUCT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.9 ©Silberschatz, Korth and Sudarshan
PID
PNAME
PDESCRIPTION
PPRICE

Keys and Foreign Keys: Example
■ E-Commerce Database with customers, products, and purchases: CUSTOMER
CID
CNAME
CADDRESS
PURCHASE
CID
PID
TIMEDATE
PRICE
PRODUCT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.10 ©Silberschatz, Korth and Sudarshan
PID
PNAME
PDESCRIPTION
PPRICE

Schema Diagram for University Database
student
ID
name dept_name tot_cred
section
course
course_id
title dept_name credits
department
dept_name
building budget
advisor
s_id
i_id
course_id sec_id semester year building room_no time_slot_id
instructor
ID
name dept_name salary
prereq
course_id
prereq_id
classroom
building
room_no capacity
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.11 ©Silberschatz, Korth and Sudarshan
ID
course_id sec_id semester year
takes
ID
course_id sec_id semester year grade
time_slot
time_slot_id
day start_time end_time
teaches

Relational Query Languages
■ Procedural vs.non-procedural, or declarative ■ “Pure” languages:
● Relational algebra (procedural)
● Relational calculus (non-procedural)
! Domain relational calculus (DRC)
! Tuple relational calculus (TRC) ■ Non-pure, real languages:
● SQL
● Query By Example (QBE)
■ But first we introduce relational operators
● Selection, projection, cross product, …
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.12 ©Silberschatz, Korth and Sudarshan

■ Relation r
Selection of tuples
■ Select tuples with A=B and D>5
l σA=BandD>5 (r)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.13 ©Silberschatz, Korth and Sudarshan

Selection of Columns (Attributes)
■ Relation r:
■ Select A and C l Projection
l Π A, C (r)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.14 ©Silberschatz, Korth and Sudarshan

Joining two relations – Cartesian Product
■ Relations r, s:
rxs
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.15 ©Silberschatz, Korth and Sudarshan

Union of two relations
■ Relations r, s:
■ r∪s
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.16 ©Silberschatz, Korth and Sudarshan

■ Relations r, s:
Set difference of two relations
■ r–s
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.17 ©Silberschatz, Korth and Sudarshan

Set Intersection of two relations
■ Relation r, s:
■ r∩s
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.18 ©Silberschatz, Korth and Sudarshan

Joining two relations – Natural Join
■ Let r and s be relations on schemas R and S respectively. 

Then, the “natural join” of relations R and S is a relation on schema R ∪ S obtained as follows:
● Consider each pair of tuples tr from r and ts from s.
● If tr and ts have the same value on each of the attributes in R ∩ S, add a tuple t to the result, where
! t has the same value as tr on r ! t has the same value as ts on s
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.19 ©Silberschatz, Korth and Sudarshan

■ Relations r, s:
■ Natural Join l r s
Natural Join Example
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.20 ©Silberschatz, Korth and Sudarshan

Overview of Operators
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.21 ©Silberschatz, Korth and Sudarshan

Database Design Example
■ Suppose you want to design a database for a bakery selling cakes
■ The bakery makes certain cakes: Apple Pie, Chocolate Cake, etc ■ Cakes have a price and also need certain ingredients
■ Customer can order cakes, and then pick them up on some date
■ Bakery also wants to keep track of how much ingredients they have ■ Customers may want to search by ingredient
(e.g., “cakes with chocolate but without peanuts”) ■ Let’s design a relational schema for this problem …
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.22 ©Silberschatz, Korth and Sudarshan

Database Design Example
■ Let’s design a relational schema for this problem …
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.23 ©Silberschatz, Korth and Sudarshan

Database Design Example
■ Possible schema:
CUSTOMER (cid, name, phone, ccn)

CAKE (cname, price, slices)

ORDER (oid, cid, cname, pickupdate, orderdate, oprice) INGREDIENT (iname, price, amountleft)
USED_IN (cname, iname, amount)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.24 ©Silberschatz, Korth and Sudarshan

Database Design Example
■ Possible schema:
CUSTOMER (cid, name, phone, ccn)

CAKE (cname, price, slices)

ORDER (oid, cid, cname, pickupdate, orderdate, oprice) INGREDIENT (iname, price, amountleft)
USED_IN (cname, iname, amount)
■ Foreign keys:
cid cname cname iname
CUSTOMER
ORDER
CAKE
USED_IN
INGREDIENT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.25
©Silberschatz, Korth and Sudarshan

Database Design Example
■ Possible schema:
CUSTOMER (cid, name, phone, ccn)

CAKE (cname, price, slices)

ORDER (oid, cid, cname, pickupdate, orderdate, oprice) INGREDIENT (iname, price, amountleft)
USED_IN (cname, iname, amount)
■ Possible queries:
● IDs of customers with name “J. Smith”
● Names of cakes containing more than 12oz of chocolate
● Names of customers who bought “apple pie”
● IDs of customers who have never bought a cake with peanuts
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.26 ©Silberschatz, Korth and Sudarshan

Chapter 6: Formal Relational Query Languages
Relational Algebra Domain Relational Calculus (Tuple Relational Calculus) Query By Example
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.27 ©Silberschatz, Korth and Sudarshan

Relational Algebra
■ Procedural language
■ Based on relational operations introduced in chapter 2 ■ Three sets of RA operations
● Basic RA operations:
! select, project, union, set diff., cartesian product, rename
● Additional RA operations:
! Can be expressed using basic ones
! But make it easier to write queries ! intersection, assignment, joins, division
● Extended RA:
! Increases power of RA
! Cannot be expressed with basic RA ! Aggregation and group_by
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.28 ©Silberschatz, Korth and Sudarshan

Relational Algebra
■ Six basic operators
● select: σ
● project: ∏
● union: ∪
● set difference: –
● Cartesian product: x
● rename: ρ
■ Alloperatorstakeoneortworelationsasinputsandproduceanew
relation as a result
■ Additionaloperatorsdefinedontopofthese6later
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.29 ©Silberschatz, Korth and Sudarshan

■ Relation r
Select Operation – Example
¡ σA=B ^ D > 5 (r)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.30 ©Silberschatz, Korth and Sudarshan

Select Operation ■ p is called the selection predicate

σp(r) = {t | t ∈ r and p(t)}

Where p is a formula in propositional calculus consisting of terms connected by : ∧ (and), ∨ (or), ¬ (not)

Each term is one of:
op or whereopisoneof: =,≠,>,≥.<.≤
 Example of selection:
 σ dept_name=“Physics”(instructor) ■ Notation: σp(r) ■ Defined as:
 ■ 
 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.31 ©Silberschatz, Korth and Sudarshan ■ Relation r: Project Operation – Example ■ ∏A,C (r) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.32 ©Silberschatz, Korth and Sudarshan Project Operation ∏ A ,A ,...,A (r) 12k ■ Notation:
 where A1, A2 are attribute names and r is a relation name. ■ The result is defined as the relation of k columns obtained by erasing the columns that are not listed ■ Duplicate rows removed from result, since relations are sets ■ Example: To eliminate the dept_name attribute of instructor
 
 ∏ID, name, salary (instructor) 
 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.33 ©Silberschatz, Korth and Sudarshan ■ Relations r, s: ■ r∪s: Union Operation – Example Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.34 ©Silberschatz, Korth and Sudarshan ■ Relations r, s: Set difference of two relations ■ r – s: Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.35 ©Silberschatz, Korth and Sudarshan Cartesian-Product Operation – Example ■ Relations r, s: ■ rxs: Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.36 ©Silberschatz, Korth and Sudarshan Cartesian-Product Operation ■ Notation r x s ■ Defined as: r x s = {t q | t ∈ r and q ∈ s}
 ■ Assume that attributes of r(R) and s(S) are disjoint. (That is, R ∩ S = ∅). ■ If attributes of r(R) and s(S) are not disjoint, then renaming must be used. Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.37 ©Silberschatz, Korth and Sudarshan Composition of Operations ■ Can build expressions using multiple operations ■ Example: σA=C(r x s) ■ rxs ■ σA=C(rxs) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.38 ©Silberschatz, Korth and Sudarshan Rename Operation ■ Allowsustoname,andthereforetoreferto,theresultsofrelational- algebra expressions. ■ Allowsustorefertoarelationbymorethanonename. ■ Example: ρx(E)
 returns the expression E under the name X ■ If a relational-algebra expression E has arity n, then ρx(A ,A ,...,A )(E) 12n returns the result of expression E under the name X, and with the attributes renamed to A1 , A2 , ...., An . ■ E.g.. Given relation CAKE(cname, price, slices) ρ cheapcake(cakename, price, slices) ( σ price < 10 (CAKE) ) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.39 ©Silberschatz, Korth and Sudarshan Formal Definition ■ Abasicexpressionintherelationalalgebraconsistsofeitheroneofthe following: ● A relation in the database ● A constant relation ■ Let E1 and E2 be relational-algebra expressions; the following are all relational-algebra expressions: ● E1∪E2 ● E1–E2 ● E1xE2 ● σp (E1), P is a predicate on attributes in E1 ● ∏s(E1), S is a list consisting of some of the attributes in E1 ● ρ x (E1), x is the new name for the result of E1 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.40 ©Silberschatz, Korth and Sudarshan Additional Operations We define additional operations that do not add any power to the relational algebra, but that simplify common queries. ■ Set intersection ■ Natural join ■ Assignment ■ Outer join ■ Division Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.41 ©Silberschatz, Korth and Sudarshan Set-Intersection Operation – Example ■ Relation r, s: ■ r∩s Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.42 ©Silberschatz, Korth and Sudarshan Natural-Join Operation ■ Notation: r s ■ Let r and s be relations on schemas R and S respectively. 
 Then, r s is a relation on schema R ∪ S obtained as follows: ● Considereachpairoftuplestrfromrandtsfroms. ● IftrandtshavethesamevalueoneachoftheattributesinR∩S,add a tuple t to the result, where ! t has the same value as tr on r ! t has the same value as ts on s ■ Example: R = (A, B, C, D) S = (E, B, D) ● Resultschema=(A,B,C,D,E) ● r s is defined as:
 ∏r.A, r.B, r.C, r.D, s.E (σr.B = s.B ∧ r.D = s.D (r x s)) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.43 ©Silberschatz, Korth and Sudarshan ■ Relations r, s: ■ r s Natural Join Example Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.44 ©Silberschatz, Korth and Sudarshan Natural Join and Theta Join ■ Find the names of all instructors in the Comp. Sci. department together with the course titles of all the courses that the instructors teach ● ∏ name, title (σ dept_name=“Comp. Sci.” (instructor teaches course)) ■ Natural join is associative ● (instructor teaches) course is equivalent to
 instructor (teaches course) ■ Natural join is commutative ● instruct teaches is equivalent to
 teaches instructor ■ The theta join operation r θ s is defined as ● r θ s = σθ (r x s) where θ (theta) is an arbitrary condition Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.45 ©Silberschatz, Korth and Sudarshan Natural Join and Theta Join ■ Find the names of all instructors in the Comp. Sci. department together with the course titles of all the courses that the instructors teach ● ∏ name, title (σ dept_name=“Comp. Sci.” (instructor teaches course)) ■ Natural join is associative ● (instructor teaches) course is equivalent to
 instructor (teaches course) ■ Natural join is commutative ● instruct teaches is equivalent to
 teaches instructor ■ The theta join operation r θ s is defined as ● r θ s = σθ (r x s) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.46 ©Silberschatz, Korth and Sudarshan Careful: this assumes instructors only teach in “their” department! Assignment Operation ■ The assignment operation (←) provides a convenient way to express complex queries. ● Write query as a sequential program consisting of ! a series of assignments ! followed by an expression whose value is displayed as a result of the query. ● Assignment must always be made to a temporary relation variable. ● Motivation from algebra: suppose you want to compute y = (a+b+c)^2 + (a+b+c)^3 + (a+b+c)^4 Shorter: x = a+b+c y = x^2 + x^3 + x^4 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.47 ©Silberschatz, Korth and Sudarshan Outer Join ■ Anextensionofthejoinoperationthatavoidslossofinformation. ■ Computes the join and then adds tuples form one relation that does not match tuples in the other relation to the result of the join. ■ Uses null values: ● null signifies that the value is unknown or does not exist ● All comparisons involving null are (roughly speaking) false by definition. ! We shall study precise meaning of comparisons with nulls later Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.48 ©Silberschatz, Korth and Sudarshan ■ Relation instructor1 Outer Join – Example ID name dept_name 10101 12121 15151 Srinivasan Wu Mozart Comp. Sci. Finance Music ■ Relation teaches1 ID course_id 10101 12121 76766 CS-101 FIN-201 BIO-101 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.49 ©Silberschatz, Korth and Sudarshan ■ Join 
 
 instructor teaches Outer Join – Example ID name dept_name course_id 10101 12121 Srinivasan Wu Comp. Sci. Finance CS-101 FIN-201 ■ Left Outer Join instructor teaches ID name dept_name course_id 10101 12121 15151 Srinivasan Wu Mozart Comp. Sci. Finance Music CS-101 FIN-201 null Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.50 ©Silberschatz, Korth and Sudarshan Outer Join – Example ■ Right Outer Join instructor teaches ID name dept_name course_id 10101 12121 76766 Srinivasan Wu null Comp. Sci. Finance null CS-101 FIN-201 BIO-101 ■ Full Outer Join instructor teaches ID name dept_name course_id 10101 12121 15151 76766 Srinivasan Wu Mozart null Comp. Sci. Finance Music null CS-101 FIN-201 null BIO-101 ■ Outer join can be expressed using basic operations ● e.g.r scanbewrittenas (r s) U(r–∏R(r s) x{(null,...,null)}) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.51 ©Silberschatz, Korth and Sudarshan Theta vs. Natural vs. Outer Join ■ CUSTOMER (cid, cname, joindate) PURCHASE (cid, pid, buydate) ■ Theta Join: more general than Natural Join ■ Natural Join: special case, join on common attributes ■ Works 95% of time, but what if we use “date” in both? ■ Inner versus outer join is separate issue Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.52 ©Silberschatz, Korth and Sudarshan Null Values ■ It is possible for tuples to have a null value, denoted by null, for some of their attributes ■ null signifies an unknown value or that a value does not exist. ■ The result of any arithmetic expression involving null is null. ■ Aggregatefunctionssimplyignorenullvalues(asinSQL) ■ For duplicate elimination and grouping, null is treated like any other value, and two nulls are assumed to be the same (as in SQL) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.53 ©Silberschatz, Korth and Sudarshan Null Values ■ Comparisons with null values return the special truth value: unknown ● If false was used instead of unknown, then not (A < 5) 
 would not be equivalent to A >= 5 ■ Three-valued logic using the truth value unknown:
● OR:(unknownortrue) =true,
 (unknown or false) = unknown
 (unknown or unknown) = unknown
● AND: (true and unknown) = unknown, (false and unknown) = false,

(unknown and unknown) = unknown
● NOT: (not unknown) = unknown

● InSQL“Pisunknown”evaluatestotrueifpredicatePevaluatesto unknown
■ Result of select predicate is treated as false if it evaluates to unknown
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.54 ©Silberschatz, Korth and Sudarshan

Division Operator
■ Given relations r(R) and s(S), such that S ⊂ R, r ÷ s is the largest relation t(R-S) such that 

txs⊆r
■ E.g. let r(ID, course_id) = ∏ID, course_id (takes ) and

s(course_id) = ∏course_id (σdept_name=“Biology”(course ) 
 then r ÷ s gives us students who have taken all courses offered by
the Biology department
■ Can writer÷sas
temp1 ← ∏R-S (r ) 

temp2 ← ∏R-S ((temp1 x s ) – ∏R-S,S (r ))
 result = temp1 – temp2
● See use of assignment: the result to the right of the ← is assigned to the relation variable on the left of the ←.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.55 ©Silberschatz, Korth and Sudarshan

Division Operation – Example
A
B
■ Relations r, s:
B
α α α β γ δ δ δ ∈ ∈ β
1 2 3 1 1 1 3 4 6 1 2
1 2
s
A
α β
■ r ÷ s:
r
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.56
©Silberschatz, Korth and Sudarshan

■ Relations r, s:
Another Division Example
A
B
C
D
E
D
E
α α α β β γ γ γ
a a a a a a a
a
α γ γ γ γ γ γ β
a a b a b a b
b
1 1 1 1 3 1 1 1
a b
1 1
■ r ÷ s:
r
s
A
B
C
α γ
a a
γ γ
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.57 ©Silberschatz, Korth and Sudarshan

Extended Relational-Algebra-Operations
■ Generalized Projection ■ AggregateFunctions
Generalized Projection
■ Extends the projection operation by allowing arithmetic functions to be used in the projection list.



∏F ,F ,…, F (E) 12n
■ E is any relational-algebra expression
■ Each of F1, F2, …, Fn are are arithmetic expressions involving constants
and attributes in the schema of E.
■ Given relation instructor(ID, name, dept_name, salary) where salary is annual salary, get the same information but with monthly salary
∏ID, name, dept_name, salary/12 (instructor)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.58 ©Silberschatz, Korth and Sudarshan

Aggregate Functions and Operations
■ Aggregation function takes a collection of values and returns a single
value as a result.
avg: average value

min: minimum value
 max: maximum value
 sum: sum of values
 count: number of values
■ Aggregate operation in relational algebra
G ,G ,…,G F (A ),F (A ,…,F (A )(E) 12n1122nn

E is any relational-algebra expression
● G1, G2 …, Gn is a list of attributes on which to group (can be empty) ● Each Fi is an aggregate function
● Each Ai is an attribute name
■ Note: Some books/articles use γ instead of (Calligraphic G) Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.59
©Silberschatz, Korth and Sudarshan

■ Relation r:
Aggregate Operation – Example
A
B
C
α α β β
α β β β
7 7 3 10
■ sum(c) (r)
sum(c )
27
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.60 ©Silberschatz, Korth and Sudarshan

Aggregate Operation – Example
■ Find the average salary in each department dept_name avg(salary) (instructor)
avg_salary
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.61 ©Silberschatz, Korth and Sudarshan

Aggregate Functions (Cont.)
■ Result of aggregation does not have a name
● Can use rename operation to give it a name
● For convenience, we permit renaming as part of aggregate operation

dept_name max(salary) as max_sal (instructor)
■ Suppose we want to find instructor who made highest salary ■ Do not nest inside selection operator as follows:
A max(salary) as max_sal (instructor) σsalary = A (instructor)
■ Aisatablewithonerowandonecolumn
■ No nested RA expressions (i.e., tables) inside selection condition
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.62 ©Silberschatz, Korth and Sudarshan

Aggregate Functions (Cont.)
■ Result of aggregation does not have a name
● Can use rename operation to give it a name
● For convenience, we permit renaming as part of aggregate operation

dept_name max(salary) as max_sal (instructor)
■ Suppose we want to find instructor who made highest salary ■ Do not nest inside selection operator as follows:
A max(salary) as max_sal (instructor) σsalary = A (instructor) — this is wrong!
■ Aisatablewithonerowandonecolumn
■ No nested RA expressions (i.e., tables) inside selection condition
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.63 ©Silberschatz, Korth and Sudarshan

Aggregate Functions (Cont.)
■ Result of aggregation does not have a name
● Can use rename operation to give it a name
● For convenience, we permit renaming as part of aggregate operation

dept_name avg(salary) as avg_sal (instructor) ■ Correct:
A max(salary) as max_sal (instructor) σsalary = A.max_sal (instructor X A)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.64 ©Silberschatz, Korth and Sudarshan

Modification of the Database
■ The content of the database may be modified using the following operations:
● Deletion ● Insertion ● Updating
■ All these operations can be expressed using the assignment operator
■ Compute new state of table, then assign it to table
■ But this does not give much insight …
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.65 ©Silberschatz, Korth and Sudarshan

Multiset Relational Algebra
■ Pure relational algebra removes all duplicates ● e.g. after projection
■ Multiset relational algebra retains duplicates, to match SQL semantics
● SQL duplicate retention was initially for efficiency, but is now a feature
■ Multiset relational algebra defined as follows
● selection: has as many duplicates of a tuple as in the input, if the
tuple satisfies the selection
● projection: one tuple per input tuple, even if it is a duplicate
● cross product: If there are m copies of t1 in r, and n copies of t2 in s, therearemxncopiesoft1.t2inr xs
● Other operators similarly defined
! E.g. union: m + n copies, intersection: min(m, n) copies

difference: min(0, m – n) copies
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.66 ©Silberschatz, Korth and Sudarshan

SQL and Relational Algebra
■ select A1, A2, .. An
 from r1, r2, …, rm
 where P
is equivalent to the following expression in multiset relational algebra ∏A1,..,An(σP(r1x r2 x..x rm))
■ select A1, A2, sum(A3)
 from r1, r2, …, rm
 where P

group by A1, A2
is equivalent to the following expression in multiset relational algebra A1, A2 sum(A3) (σP (r1 x r2 x .. x rm)))
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.67 ©Silberschatz, Korth and Sudarshan

Example Database
■ E-Commerce Database with customers, products, and purchases: CUSTOMER
CID
CNAME
CADDRESS
PURCHASE
CID
PID
TIMEDATE
PRICE
PRODUCT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.68 ©Silberschatz, Korth and Sudarshan
PID
PNAME
PDESCRIPTION
PPRICE

Example Database
■ CIDs of Customers named “John Smith”
■ Names of customers who have ordered something costing >$10
■ Names customers who have ordered an item called “IPhone 9”
■ CID of customers named “John Smith” who have ordered an “IPhone9”
■ For each customer, how much money they have spent.
■ For each product, how many items were bought.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.69 ©Silberschatz, Korth and Sudarshan

Tuple Relational Calculus
■ A nonprocedural query language, where each query is of the form
{t | P (t ) }
■ It is the set of all tuples t such that predicate P is true for t
■ t is a tuple variable, t [A ] denotes the value of tuple t on attribute A
■ t ∈ r denotes that tuple t is in relation r
■ P is a formula similar to that of the predicate calculus
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.70 ©Silberschatz, Korth and Sudarshan

Predicate Calculus Formula
1. Set of attributes and constants
2. Set of comparison operators: (e.g., <, ≤, =, ≠, >, ≥) 3. Set of connectives: and (∧), or (v)‚ not (¬)
4. Implication (⇒): x ⇒ y, if x if true, then y is true
x ⇒ y ≡ ¬x v y
„ ∃ t ∈ r (Q (t )) ≡ ”there exists” a tuple in t in relation r

such that predicate Q (t ) is true
„ ∀t ∈ r (Q (t )) ≡ Q is true “for all” tuples t in relation r
5. Set of quantifiers:
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.71 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the ID, name, dept_name, salary for instructors whose salary is greater than $80,000
{t | t ∈ instructor ∧ t [salary ] > 80000}
■ As in the previous query, but output only the ID attribute value
{t | ∃ s ∈ instructor (t [ID ] = s [ID ] ∧ s [salary ] > 80000)} Notice that a relation on schema (ID) is implicitly defined by
the query
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.72 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the names of all instructors whose department is in the Watson building
{t | ∃s ∈ instructor (t [name ] = s [name ] 

∧ ∃u ∈ department (u [dept_name ] = s[dept_name] “

∧ u [building] = “Watson” ))}
■ Find the set of all courses taught in the Fall 2009 semester, or in 

the Spring 2010 semester, or both
{t | ∃s ∈ section (t [course_id ] = s [course_id ] ∧ 

s [semester] = “Fall” ∧ s [year] = 2009) 

v ∃u ∈ section (t [course_id ] = u [course_id ] ∧ 

u [semester] = “Spring” ∧ u [year] = 2010)}
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.73 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the set of all courses taught in the Fall 2009 semester, and in 
 the Spring 2010 semester
{t | ∃s ∈ section (t [course_id ] = s [course_id ] ∧ 

s [semester] = “Fall” ∧ s [year] = 2009) 

∧ ∃u ∈ section (t [course_id ] = u [course_id ] ∧ 

u [semester] = “Spring” ∧ u [year] = 2010)}
■ Find the set of all courses taught in the Fall 2009 semester, but not in 
 the Spring 2010 semester
{t | ∃s ∈ section (t [course_id ] = s [course_id ] ∧ 

s [semester] = “Fall” ∧ s [year] = 2009) 

∧ ¬ ∃u ∈ section (t [course_id ] = u [course_id ] ∧ 

u [semester] = “Spring” ∧ u [year] = 2010)}
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.74 ©Silberschatz, Korth and Sudarshan

Safety of Expressions
■ It is possible to write tuple calculus expressions that generate infinite relations.
■ For example, { t | ¬ t ∈ r } results in an infinite relation if the domain of any attribute of relation r is infinite
■ To guard against the problem, we restrict the set of allowable expressions to safe expressions.
■ Anexpression{t|P(t)}inthetuplerelationalcalculusissafeif every component of t appears in one of the relations, tuples, or constants that appear in P
● NOTE: this is more than just a syntax condition.
! E.g. { t | t [A] = 5 ∨ true } is not safe — it defines an infinite set with attribute values that do not appear in any relation or tuples or constants in P.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.75 ©Silberschatz, Korth and Sudarshan

Universal Quantification
■ Find all students who have taken all courses offered in the Biology department
● {t | ∃ r ∈ student (t [ID] = r [ID]) ∧

(∀ u ∈ course (u [dept_name]=“Biology” ⇒ 

∃s∈takes(t[ID]=s[ID]∧ 

s [course_id] = u [course_id]))}
● Note that without the existential quantification on student, the above query would be unsafe if the Biology department has not offered any courses.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.76 ©Silberschatz, Korth and Sudarshan

Domain Relational Calculus
■ A nonprocedural query language equivalent in power to the tuple relational calculus
■ Each query is an expression of the form: {|P(x1,x2,…,xn)}

● x1, x2, …, xn represent domain variables
● P represents a formula similar to those in predicate
calculus
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.77 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the ID, name, dept_name, salary for instructors whose salary is greater than $80,000
● {| ∈instructor∧s>80000}
■ As in the previous query, but output only the ID attribute value
● { |∃n,d,s(∈instructor∧s>80000)} ■ Find the names of all instructors whose department is in the
Watson building
{| ∃i,d,s(∈instructor

∧∃b,a(∈department ∧ b=“Watson”))}
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.78 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the set of all courses taught in the Fall 2009 semester, or in 
 the Spring 2010 semester, or both
{| ∃a,s,y,b,r,t (∈section ∧ 
 s = “Fall” ∧ y = 2009 )

v∃a,s,y,b,r,t(∈section]∧ 
 s = “Spring” ∧ y = 2010)}
This case can also be written as

{| ∃a,s,y,b,r,t (∈section ∧ 

((s=“Fall”∧y=2009) v(s=“Spring”∧y=2010))} ■ Find the set of all courses taught in the Fall 2009 semester, and in 

the Spring 2010 semester
{| ∃a,s,y,b,r,t (∈section ∧ 
 s = “Fall” ∧ y = 2009 )

∧∃a,s,y,b,r,t(∈section]∧ 
 s = “Spring” ∧ y = 2010)}
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.79 ©Silberschatz, Korth and Sudarshan

Relative Expressive Power
■ Save TRC & DRC are as powerful as basic relational algebra ■ Extended relational algebra is
● More powerful than TRC/DRC
● useful for defining SQL semantics
● useful for designing SQL queries
● useful for understanding SQL execution
■ Relational calculus is
● useful for designing SQL queries (sometimes) ● The basis for QBE
■ Different viewpoints: relational calculus vs. relational algebra ■ Limitation for all three languages: transitive closure
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.80 ©Silberschatz, Korth and Sudarshan

Query By Example
■ A graphical query language which is based (roughly) on domain relational calculus
■ Two dimensional syntax – system creates templates of relations that are requested by users
■ Queries are expressed “by example” on skeleton tables (forms)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.81 ©Silberschatz, Korth and Sudarshan

Queries on One Relation
■ Find all loan numbers at the Perryridge branch.

● ● ●
_x is a variable (optional; can be omitted in above query since it is not used elsewhere in the query)
P. means print (display) duplicates are removed by default To retain duplicates use P.ALL
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.82 ©Silberschatz, Korth and Sudarshan

Queries on One Relation (Cont.)
■ Find the loan numbers of all loans made jointly to Smith and Jones.
■ Find all customers who live in the same city as Jones
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.83 ©Silberschatz, Korth and Sudarshan

Queries on Several Relations
■ Find the names of all customers who have a loan from the Perryridge branch.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.84 ©Silberschatz, Korth and Sudarshan

Negation in QBE
■ Find the names of all customers who have an account at the bank, but do not have a loan from the bank.
¬ means “there does not exist”
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.85 ©Silberschatz, Korth and Sudarshan

Example: Quantization and 3-Valued Logic
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.86 ©Silberschatz, Korth and Sudarshan

Three-Valued Logic and Quantization
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.87 ©Silberschatz, Korth and Sudarshan