Adapted for SEN2104 – DBMS course

Week 5-6: Relational Algebra (Part III)

and Relational Calculus

Database System Concepts

©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 are expressed using the assignment
operator.

2
 Deletion
▪ A delete request is expressed similarly to a query, except instead
of displaying tuples to the user, the selected tuples are removed
from the database.
▪ Can delete only whole tuples; cannot delete values on only
particular attributes
▪ A deletion is expressed in relational algebra by:
rr–E
where r is a relation and E is a relational algebra query.

3
Banking Enterprise Schema Diagram

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)

4
4
 Deletion Examples
▪ Delete all account records in the Perryridge branch.
account  account –  branch_name = “Perryridge” (account )

▪ Delete all loan records with amount in the range of 0 to 50

loan  loan –  amount  0 and amount  50 (loan)

▪ Delete all accounts at branches located in Needham.

r1   branch_city = “Needham” (account branch )

r2   account_number, branch_name, balance (r1)
r3   customer_name, account_number (r2 depositor)
account  account – r2
depositor  depositor – r3

5
 Insertion

▪ To insert data into a relation, we either:

▪ specify a tuple to be inserted
▪ write a query whose result is a set of tuples to be inserted
▪ in relational algebra, an insertion is expressed by:
r r  E
where r is a relation and E is a relational algebra expression.
▪ The insertion of a single tuple is expressed by letting E be a constant
relation containing one tuple.

6
 Insertion Examples
▪ Insert information in the database specifying that Smith has $1200 in
account A-973 at the Perryridge branch.

account  account  {(“A-973”, “Perryridge”, 1200)}

depositor  depositor  {(“Smith”, “A-973”)}

▪ Provide as a gift for all loan customers in the Perryridge branch, a

$200 savings account. Let the loan number serve as the account
number for the new savings account.
r1  (branch_name = “Perryridge” (borrower loan))
account  account  loan_number, branch_name, 200 (r1)
depositor  depositor  customer_name, loan_number (r1)

7
 Updating

▪ A mechanism to change a value in a tuple without charging all values in

the tuple
▪ Use the generalized projection operator to do this task

▪ Each Fi is either
▪ the I th attribute of r, if the I th attribute is not updated, or,
▪ if the attribute is to be updated Fi is an expression, involving only
constants and the attributes of r, which gives the new value for the
attribute

8
 Update Examples

▪ Make interest payments by increasing all balances by 5 percent.

account   account_number, branch_name, balance * 1.05 (account)

▪ Pay all accounts with balances over $10,000 6 percent interest

and pay all others 5 percent

account   account_number, branch_name, balance * 1.06 ( balance  10000 (account))

  account_number, branch_name, balance * 1.05 ( balance  10000 (account))

9
 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

10
 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

11
Banking Enterprise Schema Diagram

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)

12
12
 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 [loan_number ] is implicitly defined by

the query

13
 Example Queries

▪ Find the names of all customers having a loan, an account, or both at

the bank

{t | s  borrower ( t [customer_name ] = s [customer_name ])

 u  depositor ( t [customer_name ] = u [customer_name ])

▪ Find the names of all customers who have a loan and an account at the
bank

{t | s  borrower ( t [customer_name ] = s [customer_name ])

 u  depositor ( t [customer_name ] = u [customer_name] )

14
 Example Queries

▪ Find the names of all customers having a loan at the Perryridge branch

{t | s  borrower (t [customer_name ] = s [customer_name ]

 u  loan (u [branch_name ] = “Perryridge”
 u [loan_number ] = s [loan_number ]))}

▪ Find the names of all customers who have a loan at the Perryridge branch,
but no account at any branch of the bank

{t | s  borrower (t [customer_name ] = s [customer_name ]

 u  loan (u [branch_name ] = “Perryridge”
 u [loan_number ] = s [loan_number ]))
 not v  depositor (v [customer_name ] = t [customer_name ])}

15
 Example Queries

▪ Find the names of all customers having a loan from the Perryridge
branch, and the cities in which they live

{t | s  loan (s [branch_name ] = “Perryridge”

 u  borrower (u [loan_number ] = s [loan_number ]
 t [customer_name ] = u [customer_name ])
  v  customer (u [customer_name ] = v [customer_name ]
 t [customer_city ] = v [customer_city ])))}

16
 Example Queries

▪ Find the names of all customers who have an account at all branches
located in Brooklyn:

{t |  r  customer (t [customer_name ] = r [customer_name ]) 

(  u  branch (u [branch_city ] = “Brooklyn” 
 s  depositor (t [customer_name ] = s [customer_name ]
  w  account ( w[account_number ] = s [account_number ]
 ( w [branch_name ] = u [branch_name ]))))}

The set of all customers (that is, tuples t) such that, for all tuples u in the
branch relation, if the value of u on attribute branch-city is Brooklyn, then
the customer has an account at the branch whose name appears in the
branch-name attribute of u.
17
 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.
▪ 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
▪ 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.

18
 Domain Relational Calculus

▪ A nonprocedural query language equivalent in power to the tuple

relational calculus
▪ 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

19
 Example Queries

▪ Find the loan_number, branch_name, 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”))}

Alternative:
{ c, a  |  l ( c, l   borrower   l, “ Perryridge”, a   loan)}

20
 Example Queries

▪ Find the names of all customers having a loan, an account, or both at

the Perryridge branch:
{ c  |  l (  c, l   borrower
  b,a ( l, b, a   loan  b = “Perryridge”))
  a ( c, a   depositor
  b,n ( a, b, n   account  b = “Perryridge”))}

▪ Find the names of all customers who have an account at all branches
located in Brooklyn:
{ c  |  s, n ( c, s, n   customer) 
 x, y, z ( x, y, z   branch  y = “Brooklyn”) 
 a, x ( a, x, m   account   c, a   depositor)}

21
 Safety of Expressions

The expression:
{  x1, x2, …, xn  | P (x1, x2, …, xn )}

is safe if all of the following hold:

1. All values that appear in tuples of the expression are values
from dom (P ) (that is, the values appear either in P or in a tuple of a
relation mentioned in P ).
2. For every “there exists” subformula of the form  x (P1(x )), the
subformula is true if and only if there is a value of x in dom (P1)
such that P1(x ) is true.
3. For every “for all” subformula of the form x (P1 (x )), the subformula is
true if and only if P1(x ) is true for all values x from dom (P1).

22