Transcript Document

Prof. Kedem’s changes, if any, are
marked in green, they are not
copyrighted by the authors, and the
authors are not responsible for them.
Prof. Shasha’s are marked in blue.
!Chapter 3: Relational Model
 Structure of Relational Databases
 Relational Algebra
 Brief Introduction toTuple Relational Calculus
and Domain Calculus
Database System Concepts
3.2
©Silberschatz, Korth and Sudarshan
Example of a Relation
Database System Concepts
3.3
©Silberschatz, Korth and Sudarshan
Basic Structure
 Formally, given sets D1, D2, …. Dn a relation r is a subset of
D1 x D2 x … x Dn The x represents cross-product (all possible ntuples). Thus a relation is a set of n-tuples (a1, a2, …, an) where
ai  D i
 Example: if
customer-name = {Jones, Smith, Curry, Lindsay}
customer-street = {Main, North, Park}
customer-city = {Harrison, Rye, Pittsfield}
Then r = { (Jones, Main, Harrison),
(Smith, North, Rye),
(Curry, North, Rye),
(Lindsay, Park, Pittsfield)}
is a relation over customer-name x customer-street x customer-city
Database System Concepts
3.4
©Silberschatz, Korth and Sudarshan
Attribute Types
 Each attribute of a relation has a name
 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
• E.g. multivalued attribute values are not atomic
• E.g. composite attribute values are not atomic
 The special value null is a member of every domain (not in pure
relational algebra, and therefore we will not talk about it in this
chapter)
Database System Concepts
3.5
©Silberschatz, Korth and Sudarshan
Relation Schema
 A1, A2, …, An are attributes
 R = (A1, A2, …, An ) is a relation schema
E.g. Customer-schema =
(customer-name, customer-street, customer-city)
 r(R) is a relation on the relation schema R
E.g.
Database System Concepts
customer (Customer-schema)
3.6
©Silberschatz, Korth and Sudarshan
Relation Instance
 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
attributes
customer-name customer-street
Jones
Smith
Curry
Lindsay
Main
North
North
Park
customer-city
Harrison
Rye
Rye
Pittsfield
tuples
customer
Database System Concepts
3.7
©Silberschatz, Korth and Sudarshan
Relations
 Order of tuples is irrelevant (tuples may be stored in an arbitrary order)
 Tuple may appear several times (textbook is wrong)
 E.g. account relation with unordered tuples
Database System Concepts
3.8
©Silberschatz, Korth and Sudarshan
Relations in Relational Algebra
 Relational algebra deals with relations. Relations are sets of tuples
(rows) drawn from suitable domains.
 The order of rows and whether a row appears once or many times
does not matter
 The order of columns matters, but as our columns will generally be
labeled, we will be able to reconstruct the order even if the columns are
permuted.
 The following two relations are equal (in pure relational algebra though
not in SQL databases)
•
A
1
2
B
10
20
•
B
20
10
20
20
A
2
1
2
2
Database System Concepts
3.9
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
Database
 A database consists of multiple relations
 Information about an enterprise is broken up into parts, with each
relation storing one part of the information
E.g.: account : stores information about accounts
depositor : stores information about which customer
owns which account
customer : stores information about customers
 Storing all information as a single relation such as
bank(account-number, balance, customer-name, ..)
results in
• repetition of information (e.g. two customers own an account)
• the need for null values (e.g. represent a customer without an
account)
 Normalization theory (Chapter 7) deals with how to design
relational schemas. Or use entity-relationship diagrams.
Database System Concepts
3.10
©Silberschatz, Korth and Sudarshan
The customer Relation
Database System Concepts
3.11
©Silberschatz, Korth and Sudarshan
The depositor Relation
Database System Concepts
3.12
©Silberschatz, Korth and Sudarshan
Query Languages
 Language in which user requests information from the database.
 Categories of languages
• procedural
• non-procedural
 “Pure” languages:
• Relational Algebra
• Tuple Relational Calculus
• Domain Relational Calculus
 Pure languages form underlying basis of query languages that
people use.
Database System Concepts
3.13
©Silberschatz, Korth and Sudarshan
Relational Algebra
 Procedural language
 Six basic operators (not all independent)
• select
• project
• union
• set difference
• Cartesian product
• rename
 The operators take two or more relations as inputs and give a
new relation as a result.
Database System Concepts
3.14
©Silberschatz, Korth and Sudarshan
Select Operation – Example
(choice of tuples based on conditions)
• Relation r
• A=B ^ D > 5 (r)
Database System Concepts
A
B
C
D


1
7


5
7


12
3


23 10
A
B
C
D


1
7


23 10
3.15
©Silberschatz, Korth and Sudarshan
Select Operation
 Notation:
 p(r)
 p is called the selection predicate
 Defined as:
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:
<attribute> op <attribute> or <constant>
where op is one of: =, , >, . <. 
 Example of selection:
 branch-name=“Perryridge”(account)
Database System Concepts
3.16
©Silberschatz, Korth and Sudarshan
Project Operation – Example
(choice of attributes by listing)
 Relation r:
 A,C (r)
Database System Concepts
A
B
C

10
1

20
1

30
1

40
2
A
C
A
C

1

1

1

1

1

2

2
=
3.17
©Silberschatz, Korth and Sudarshan
!Project Operation
 Notation:
A1, A2, …, Ak (r)
where A1, A2 are attribute names and r is a relation name.
 The result is defined as the relation of k columns, not necessarily
distinct
 Whether you remove duplicate rows from result or not, it is
up to you since relations are sets, and could have contained
duplicate rows themselves
 E.g. To eliminate the branch-name attribute of account
account-number, balance (account)
 Comment: better to use lower case  instead of upper case ,
just as we use  and not 
Database System Concepts
3.18
©Silberschatz, Korth and Sudarshan
Union Operation – Example
 Relations r, s:
A
B
A
B

1

2

2

3

1
s
r
r  s:
Database System Concepts
A
B

1

2

1

3
3.19
©Silberschatz, Korth and Sudarshan
Union Operation
 Notation: r  s
 Defined as:
r  s = {t | t  r or t  s}
 For r  s to be valid.
1. r, s must have the same arity (same number of attributes)
2. The attribute domains must be compatible (e.g., 2nd column
of r deals with the same type of values as does the 2nd
column of s)
 E.g. to find all customers with either an account or a loan
customer-name (depositor)  customer-name (borrower)
Database System Concepts
3.20
©Silberschatz, Korth and Sudarshan
Set Difference Operation – Example
 Relations r, s:
A
B
A
B

1

2

2

3

1
s
r
r – s:
Database System Concepts
A
B

1

1
3.21
©Silberschatz, Korth and Sudarshan
Set Difference Operation
 Notation r – s
 Defined as:
r – s = {t | t  r and t  s}
 Set differences must be taken between compatible relations.
• r and s must have the same arity
• attribute domains of r and s must be compatible
Database System Concepts
3.22
©Silberschatz, Korth and Sudarshan
Cartesian-Product Operation-Example
Relations r, s:
A
B
C
D
E

1

2




10
10
20
10
a
a
b
b
r
s
r x s:
Database System Concepts
A
B
C
D
E








1
1
1
1
2
2
2
2








10
10
20
10
10
10
20
10
a
a
b
b
a
a
b
b
3.23
©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, in an obvious way.
• If c is a column in both R and S then it would be referred to as R.c in
R and perhaps left as c in S.
Database System Concepts
3.24
©Silberschatz, Korth and Sudarshan
Composition of Operations
 Can build expressions using multiple operations
 Example: A=C(r x s)
 rxs
 A=C(r x s)
Database System Concepts
A
B
C
D
E








1
1
1
1
2
2
2
2








10
19
20
10
10
10
20
10
a
a
b
b
a
a
b
b
A
B
C
D
E



1
2
2
 10
 20
 20
a
a
b
3.25
©Silberschatz, Korth and Sudarshan
!Rename Operation
 Allows us to name, and therefore to refer to, the results of
relational-algebra expressions.
 Allows us to refer to a relation by more than one name.
Example:
 x (E)
returns the expression E under the name X
If a relational-algebra expression E has arity n, then
x (A1, A2, …, An) (E)
returns the result of expression E under the name X, and with the
attributes renamed to A1, A2, …., An. It is better to think of it as
another copy of the relation and not as an alternative new name
for the original relation
Database System Concepts
3.26
©Silberschatz, Korth and Sudarshan
Alternative notation for renaming
 We introduce it by means of an example:
 Let E have two columns, A, B. We want to rename them to C and
D
AC, B  D(E)
So this projecting all the columns of E but using the arrow symbol to
rename them
Database System Concepts
3.27
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
A Small Example
 You may find this example useful to look at some queries
 The example consists of 3 relations:
• PERSONAL(PERSON,SEX,AGE).
• This relation, whose key is PERSON, gives SEX and AGE for
each PERSON.
• BIRTH(PARENT,CHILD).
• This relation, whose key is the pair PARENT,CHILD, gives
information about who is a parent of whom. (Both mother and
father would be generally listed).
• MARRIAGE(HUSBAND,WIFE,DATE).
• This relation whose key is the pair HUSBAND,WIFE, gives
information about the DATE that the marriage took place.
Database System Concepts
3.28
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
A Sample Instance



PERSONAL:
PERSN
Albert
Dennis
Evelyn
John
Mary
Robert
Susan
SEX
M
M
F
M
F
M
F
BIRTH:
PARNT
Dennis
John
Mary
Robert
Susan
Susan
CHILD
Albert
Mary
Albert
Evelyn
Evelyn
Richard
MARRIAGE:
HSBND
Dennis
Robert
WIFE
Mary
Susan
Database System Concepts
AGE
20
40
20
60
40
60
40
DATE
4/3/68
1/1/70
3.29
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
A Query
 Produce the relation ANSWER(PERSON) consisting of all
women who are less or equal than 32 years old.
 Note that all the information required can be obtained from
looking at a single relation, PERSONAL.
 ANSWER:=  PERSON  AGE  32  SEX='F' ( PERSONAL) .
PERSON
Evelyn
Database System Concepts
3.30
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
A Query
 Produce a relation ANSWER(PARENT, DAUGHTER ) with the obvious
meaning.
 Here, even though the answer comes only from the single relation
BIRTH, we still have to check in the relation PERSONAL what the SEX
of the CHILD is. To do that, we create the Cartesian product of the two
relations: PERSONAL and BIRTH. This gives us “long tuples,''
consisting of a tuple in PERSONAL and a tuple in BIRTH.
 For our purpose, the two tuples matched if PERSON in PERSONAL is
CHILD in BIRTH and the SEX of the PERSON is F.
 ANSWER:= 
PARENT, CHILD  DAUGHTER
(PERSONAL  BIRTH ) .
PARNT
John
Susan
Robert
Database System Concepts
CHILD = PERSON  SEX = 'F’
DAUGHTER
Mary
Evelyn
Evelyn
3.31
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
A Query
 Produce a relation ANSWER(FATHER, DAUGHTER) with the obvious
meaning.
 Here we have to simultaneously look at two copies of the relation
PERSONAL, as we have to determine both the SEX of the PARENT and
the SEX of the CHILD.
 We need to have two distinct copies of PERSONAL. So we first do:
• PERSONAL1:=PERSONAL
 Then, the answer is:
 ANSWER:=  PARENT  FATHER, CHILD  DAUGHTER f (PERSONAL  BIRTH
 PERSONAL1)
where f is the formula:
PARENT = PERSONAL.PERSON  CHILD = PERSONAL1.PERSON
 PERSONAL.SEX = 'M'  PERSONAL1.SEX = 'F'
FATHR DAUGHTER
John
Mary
Robert Evelyn
Database System Concepts
3.32
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
A Query
 Produce a relation: ANSWER(FATHER_IN_LAW,SON_IN_LAW).
 This is an exercise for you. Hint: you need to compute the
Cartesian product of “many” relations, if you start with the ones
originally given. Or you can use one or more of the relations you
have computed already
FIL
John
Database System Concepts
SIL
Dennis
3.33
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
A Query
 Produce a relation:
ANSWER(FATHER_IN_LAW,CHILD_IN_LAW).
 Solution: this is the union of
(FATHER_IN_LAW,SON_IN_LAW) and
(FATHER_IN_LAW,DAUGHTER_IN_LA
Database System Concepts
3.34
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
A Query
 We use the symbol “” to denote renaming of attributes
 We use the symbol “” to denote assignment of relational
expression to a relation
You may find the above notation more convenient, I do
 Produce a relation: ANSWER(GRANDPARENT,GRANDCHILD).
 We need to have two distinct copies of BIRTH because we need
to correlated BIRTH with itself. So we first do:
• BIRTH1  BIRTH
 ANSWER:=
 BIRTH.PARENT  GRANDPARENT, BIRTH1.CHILD  GRANDCHILD
BIRTHCHILD = BIRTH1.PARENT (BIRTH  BIRTH1 )
GP
John
Database System Concepts
GC
Albert
3.35
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
Relational Algebra Is Not Universal
 Can compute: ANSWER(GREATGRANDPARENT,




GREATGRANDCHILD)
But, it is impossible in relational algebra to compute the relation
ANSWER(ANCESTOR, DESCENDANT).
Why?
The proof is a reasonably simple, but uses cumbersome
induction.
The general idea is:
• Any relational algebra query is limited in how many relations or
copies of relations it can refer to
• Computing arbitrary (ancestor,descendant) pairs cannot be done, if
the query is limited in advance in such way—limited number of
relations and copies of relations
Database System Concepts
3.36
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
!Transitive closure
 Looking at this another way, we cannot do transitive closure of a
graph
 A directed graph, is just a relation consisting of pairs of nodes
with a schema, say, Arc(From,To): set of all arcs.
 Cannot create in relational algebra a query returning
Reachable(From,To): set of all paths.
 Not a big deal. Either using a stored procedure language or an
external programming language can form loops.
To compute ancestor of some set X given a parent relation,
simply do breadth first search.
Database System Concepts
3.37
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
Transitive Closure Through Loops







insert temp1”prince william of wales")
Delete from ancestor
WHILE EXISTS(SELECT * FROM Temp1)
BEGIN
INSERT Ancestor
SELECT * FROM Temp1;

INSERT Temp2
SELECT * FROM Temp1;

DELETE Temp1 FROM Temp1;


INSERT Temp1
SELECT Parental.parent
FROM Parental, Temp2
WHERE Parental.child = Temp2.parent;

DELETE Temp2 FROM Temp2;



END
Database System Concepts
3.38
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
Transitive Closure Through Loops
 Result in ancestor:
prince william of wales
charles
diana
earl of spencer
elizabeth II
philip of edinburgh
prince andrew of greece
 Reference: http://www.infoplease.com/spot/royal3.html
Database System Concepts
3.39
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
Keys
 Let K  R
 K is a superkey of R if values for K are sufficient to identify a
unique tuple of each possible relation r(R) by “possible r” we
mean a relation r that could exist in the enterprise we are
modeling.
Example: {customer-name, customer-street} and
{customer-name}
are both superkeys of Customer, if no two customers can
possibly have the same name.
 In other words: any two tuples that are equal on K are equal
(identical on all fields)
 K is a candidate key if K is minimal
Example: {customer-name} is a candidate key for Customer,
since it is a superkey {assuming no two customers can possibly
have the same name), and no subset of it is a superkey.
Database System Concepts
3.40
©Silberschatz, Korth and Sudarshan
!Banking Example (marked keys)
branch (branch-name, branch-city, assets)
customer (customer-name, customer-street, customer-only)
account (account-number, branch-name, balance)
loan (loan-number, branch-name, amount)
depositor (customer-name, account-number)
borrower (customer-name, loan-number)
Database System Concepts
3.41
©Silberschatz, Korth and Sudarshan
Example Queries
 Find all loans of over $1200
amount > 1200 (loan)
 Find the loan number for each loan of an amount greater than
$1200
loan-number (amount > 1200 (loan))
Database System Concepts
3.42
©Silberschatz, Korth and Sudarshan
Example Queries
 Find the names of all customers who have a loan, an account, or
both, from the bank
customer-name (borrower)  customer-name (depositor)
 Find the names of all customers who have a loan and an account
at bank.
customer-name (borrower)  customer-name (depositor)
Database System Concepts
3.43
©Silberschatz, Korth and Sudarshan
Example Queries
 Find the names of all customers who have a loan at the Perryridge
branch.
customer-name (branch-name=“Perryridge”
(borrower.loan-number = loan.loan-number(borrower x loan)))
 Find the names of all customers who have a loan at the Perryridge
branch but do not have an account at any branch of the bank.
customer-name (branch-name = “Perryridge”
(borrower.loan-number = loan.loan-number(borrower x loan)))
– customer-name(depositor)
 Can combine “cascading” selection conditions, as shown above:
A(B) = A  B
Database System Concepts
3.44
©Silberschatz, Korth and Sudarshan
!Example Queries
 Find the names of all customers who have a loan at the Perryridge
branch.
 Query 1
customer-name(branch-name = “Perryridge”
(borrower.loan-number = loan.loan-number(borrower x loan)))
 Query 2
customer-name(loan.loan-number = borrower.loan-number(
(branch-name = “Perryridge”(loan)) x
borrower)
)
If you hand-optimize queries, you may improve the
performance substantially.
Database System Concepts
3.45
©Silberschatz, Korth and Sudarshan
Formal Definition
 A basic expression in the relational algebra consists of either one
of the 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
• E1 x E2
• 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
3.46
©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
 Division (We will ignore because Dennis has never seen this
used.)
 Assignment
Database System Concepts
3.47
©Silberschatz, Korth and Sudarshan
Set-Intersection Operation
 Notation: r  s
 Defined as:
 r  s ={ t | t  r and t  s }
 Assume:
• r, s have the same arity
• attributes of r and s are union compatible
 Note: r  s = r - (r - s)
Database System Concepts
3.48
©Silberschatz, Korth and Sudarshan
Set-Intersection Operation - Example
 Relation r, s:
A
B



1
2
1
A


r
 rs
Database System Concepts
A
B

2
B
2
3
s
3.49
©Silberschatz, Korth and Sudarshan
Natural-Join Operation
 Notation: r
s
 Let r and s be relations on schemas R and S respectively.The result is a
relation on schema R  S which is obtained by considering 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, a tuple t
is added 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)
 Result schema = (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
3.50
©Silberschatz, Korth and Sudarshan
Natural Join Operation – Example
 Relations r, s:
A
B
C
D
B
D
E





1
2
4
1
2





a
a
b
a
b
1
3
1
2
3
a
a
a
b
b





r
r
s
Database System Concepts
s
A
B
C
D
E





1
1
1
1
2





a
a
a
a
b





3.51
©Silberschatz, Korth and Sudarshan
Division Operation
(Prof. Shasha has never seen this used in practice so we will skip this in 2006.)
rs
 Suited to queries that include the phrase “for all”. (not
quite right, its translation to standard operations teaches
you how to handle “for all” in more general way)
 Let r and s be relations on schemas R and S respectively
where
• R = (A1, …, Am, B1, …, Bn)
• S = (B1, …, Bn)
The result of r  s is a relation on schema
R – S = (A1, …, Am)
r  s = { t | t   R-S(r)   u  s ( tu  r ) }
Database System Concepts
3.52
©Silberschatz, Korth and Sudarshan
Division Operation – Example
Relations r, s:
r  s:
A
A
B
B











1
2
3
1
1
1
3
4
6
1
2
1
2
s
r


Database System Concepts
3.53
©Silberschatz, Korth and Sudarshan
Another Division Example
Relations r, s:
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
s
r
r  s:
Database System Concepts
A
B
C


a
a


3.54
©Silberschatz, Korth and Sudarshan
Division Operation (Cont.)
 Property
• Let q – r  s
• Then q is the largest relation satisfying q x s  r
 Definition in terms of the basic algebra operation
Let r(R) and s(S) be relations, and let S  R
r  s = R-S (r) –R-S ( (R-S (r) x s) – R-S,S(r))
IGNORE THIS, see my explanation following
To see why
• R-S,S(r) simply reorders attributes of r
• R-S(R-S (r) x s) – R-S,S(r)) gives those tuples t in
R-S (r) such that for some tuple u  s, tu  r.
Database System Concepts
3.55
©Silberschatz, Korth and Sudarshan
What does division mean
 Assume for simplicity that attributes of S are the “last” attributes
of R, as indeed done by the authors see the slide with the title
“Division Operation”, therefore, R = R-S,S(r)
 Let R be (customer-name,branch-name), listing for each
customer all the branches in which that customer has a deposit
 Let S be (branch-name), listing all branches of interest.
 To shorten the notation, we will write: R(A,B) and S(B).
 We want to answer the following query:
Find all customers listed in R who have deposits in all the
branches in S (call them “good,” other in R will be “bad.”)
In other words, find all A in R, s.t. for every B in S, the tuple
(A,B) is in R
Database System Concepts
3.56
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
What does division mean
 We want to understand what this is
r  s = R-S (r) –R-S ( (R-S (r) x s) – r)
 And using our specific (but essentially very general) example:
r  s = A (r) –A ( (A (r) x s) – r)
 t = A (r) This is the set of all customers who have a deposit
 u = t x s This simply lists all possible pairs of customer of
interest with branch of interest, it does not provide any “real
information.”
 v=u–r
This lists for each customer (who has a deposit) the
branches of interest in which s/he does not have a deposit
 w = A (v) This lists all the bad customers
 x=t–w
This lists all the good customers; and answers the
query
Database System Concepts
3.57
©Zvi
M. Kedem Korth and Sudarshan
©Silberschatz,
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.
 Example: Write r  s as
temp1  R-S (r)
temp2  R-S ((temp1 x s) – R-S,S (r))
result = temp1 – temp2
• The result to the right of the  is assigned to the relation variable on
the left of the .
• May use variable in subsequent expressions.
Database System Concepts
3.58
©Silberschatz, Korth and Sudarshan
Example Queries
 Find all customers who have an account from at least the
“Downtown” and the Uptown” branches.
• Query 1
CN(BN=“Downtown”(depositor
account)) 
CN(BN=“Uptown”(depositor
account))
where CN denotes customer-name and BN denotes
branch-name.
• Query 2
customer-name, branch-name (depositor account)
 temp(branch-name) ({(“Downtown”), (“Uptown”)})
Database System Concepts
3.59
©Silberschatz, Korth and Sudarshan
Example Queries
 Find all customers who have an account at all branches located
in Austin.
customer-name, branch-name (depositor account)
 branch-name (branch-city = “Austin” (branch))
Database System Concepts
3.60
©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
3.61
©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
5. Set of quantifiers:

 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
Database System Concepts
3.62
©Silberschatz, Korth and Sudarshan
Banking Example
 branch (branch-name, branch-city, assets)
 customer (customer-name, customer-street, customer-city)
 account (account-number, branch-name, balance)
 loan (loan-number, branch-name, amount)
 depositor (customer-name, account-number)
 borrower (customer-name, loan-number)
Database System Concepts
3.63
©Silberschatz, Korth and Sudarshan
Example Queries
 Find the loan-number, branch-name, and amount for loans of
over $1200
{t | t  loan  t [amount]  1200}
 Find the loan number for each loan of an amount greater than
$1200
{t |  s  loan (t[loan-number] = s[loan-number]
 s [amount]  1200}
Notice that a relation on schema [customer-name] is implicitly
defined by the query
Database System Concepts
3.64
©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.
 For completeness, (we will not dwell on this): An expression {t |
P(t)} in the tuple relational calculus is safe if every component of
t appears in one of the relations, tuples, or constants that appear
in P
Database System Concepts
3.65
©Silberschatz, Korth and Sudarshan
Domain Relational Calculus
 A nonprocedural query language equivalent in power to the tuple
relational calculus (remember that tuples are made up of
elements from domains)
 Each query is an expression of the form:
{  x1, x2, …, xn  | P(x1, x2, …, xn)}
• x1, x2, …, xn represent domain variables
• P represents a formula similar to that of the predicate calculus
Database System Concepts
3.66
©Silberschatz, Korth and Sudarshan
Example Queries
 Find the branch-name, loan-number, and amount for loans of over
$1200
{ l, b, a  |  l, b, a   loan  a > 1200}
 Find the names of all customers who have a loan of over $1200
{ c  |  l, b, a ( c, l   borrower   l, b, a   loan  a > 1200)}
 Find the names of all customers who have a loan from the
Perryridge branch and the loan amount:
{ c, a  |  l ( c, l   borrower  b( l, b, a   loan 
b = “Perryridge”))}
or { c, a  |  l ( c, l   borrower   l, “Perryridge”, a   loan)}
Database System Concepts
3.67
©Silberschatz, Korth and Sudarshan