Cs501 trc drc

DBMS

1. CS501: D
ATABASE AND
D
ATA
M
INING
TRC and DRC

2. T
UPLE
R
ELATIONAL
C
ALCULUS

A non
p
rocedural
q
uer
y
lan
g
ua
g
e
,
where each
pqygg,
query is of the form
{t| P(t ) }

It is the set of all tuples tsuch that predicate
P
is
true for t

tis a tuple variable, t [A ] denotes the value of tuple t
on attribute A

trdenotes that tuple tis in relation r

P
is a
formula
similar to that of the predicate

P
is a
formula
similar to that of the predicate
calculus
2

3. P
REDICATE
C
ALCULUS
F
ORMULA

Set of attributes and constants

Set of comparison operators: (e.g., , , , , , )

Set of connectives: and(), or(v)‚ not()

Implication (): x y, if x is true, then y is true
xyxv y

Set of quantifiers:



t 

r (Q (t ))

“there exists” a tuple in tin relation r
such that
p
redicate
Q
(
t

)
is true
p
Q
(
)

t r(Q (t )) Q(t)is true “for all” tuples tin relation
r
3

4. B
ANK
E
XAMPLE
4

5. E
XAMPLE
Q
UERIES

Find the loan number
,
branch name
,
and
_
,
_
,
amount for loans of over Rs1200

{t| t

loan

t[amount]> 1200}
Fid h l b f h l f

Fi
n
d
t
h
e
l
oan

num
b
er
f
or

eac
h l
oan

o
f
an

amount

greater than Rs1200

{
t
|

s


loan
(
t
[
loan
_
numbe
r
]
= s
[
loan
_
numbe
r
]

{|
([
_
][
_
]
s [amount ]

1200)}

Find the names of all customers having a loan, an account or both at the bank an account
,
or both at the bank

{t |s borrower ( t [customer_name] = s
[customer_name])


di
(

[
]



u


d
epos
i
tor

(
t

[
customer_name
]
=

u

[customer_name])}
5

6. E
XAMPLE
Q
UERIES
(2)

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
])
[
customer
_
name
])
u depositor ( t [customer_name] = u
[customer_name] )}
Fi d th f ll t h i l t

Fi
n
d th
e

names

o
f
a
ll
cus
t
omers
h
av
i
ng

a
l
oan

a
t
the Patliputrabranch

{
t

|s

borrower

(
t

[
customer_name
]
= s

{
(
[
]
[customer_name]
u loan (u [branch_name] = “Patliputra”
u [loan_number] = s [loan_number]))}
6

7. E
XAMPLE
Q
UERIES
(3)

Find the names of all customers who have a loan
at the Patliputrabranch, but no account at any
branch of the bank
{
t
|


b
(
t
[
t
]


{
t
|

s


b
orrower

(
t
[
cus
t
omer_name
]
=

s

[customer_name ]
u loan (u [branch_name] = “Patliputra”

u
[
loan number
] =
s
[
loan
number
]))

u
[
loan
_
number
] =
s
[
loan
_
number
]))
notv depositor (v [customer_name] =
t [customer_name])}
7

8. E
XAMPLE
Q
UERIES
(4)

Find the names of all customers havin
g
a loan
g
from the Patliputrabranch, and the cities in
which they live
{
t
|


l
(

[
bh
] “
Ptli t
”

{
t
|

s


l
oan

(
s

[
b
ranc
h
_name
]
=
“
P
a
tli
pu
t
ra
”
u borrower (u [loan_number] = s [loan_number]
t [customer_name] = u [customer_name]


v

customer
(
u
[
customer name
] =
v


v

customer
(
u
[
customer
_
name
] =
v
[customer_name]
t [customer_city] = v
[
customer city
])))}
[
customer
_
city
])))}
8

9. E
XAMPLE
Q
UERIES
(5)

Find the names of all customers who have an account at all branches located in branch_city=
“Dhanbad”:
{
t
|


bh
(

[
bhit
] “
Dh b d
”




{
t
|

u


b
ranc
h
(
u

[
b
ranc
h
_c
it
y
]
=
“
Dh
an
b
a
d
”


v

account (v [branch_name] = u [branch_name] 
w depositor( w[account_number] = v
[
account number
]

(
t
[
customer name
] =
w
[
account
_
number
]

(
t
[
customer
_
name
] =
w
[customer_name])))}
9

10. S
AFETY OF
E
XPRESSION

It is
p
ossible to write tu
p
le calculus ex
p
ressions
ppp
that generate infinite set

For example, { t | tr } results in an infinite set if the domain of any attribute of relation
r
is infinite
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
10

11. S
AFE
E
XPRESSION

Let’s consider an ex
p
ression
{
t
|
P

(
t

)}
in the
p{
|
(
)}
tuple relational calculus

dom(P): the set of all values referenced by P i.e., the relations tuples or constants that appear in
P
relations
,
tuples
,
or constants that appear in
P

The expression is said to be safeif every
component of tappears from the dom(P)

E.g. { t|t r| t [A] = 5

true} is not safe --- it
defines an infinite set with attribute values that do
not a
pp
ear in an
y
relation or tu
p
les or constants in
P
.
pp y p
11

12. D
OMAIN
R
ELATIONAL
C
ALCULUS

A non
p
rocedural
q
uer
y
lan
g
ua
g
e e
q
uivalent in
pqyggq
power to the tuple relational calculus

Each query is an expression of the form:
{ x
1
, x
2
, …, x
n
| P (x
1
, x
2
, …, x
n
)}

x
1
, x
2
, …, x
n
represent domain variables

Prepresents a formula similar to that of the predicate calculus
12

13. B
ANK
E
XAMPLE
13

14. E
XAMPLE
Q
UERIES

Find the loan_number,

branch_name,

and
amount

for loans of over Rs1200

{l, b, a | l, b, a loana > 1200}

Find the names of all customers who have a loan

Find the names of all customers who have a loan of over Rs1200

{c| l, b, a (c, l borrower l, b, a 
loan
a
> 1200)}

loan

a
> 1200)}

Find the names of all customers who have a loan
from the Patliputrabranch and the loan amount:

{c, a| l(c, lborrower b (l, b, a loan
b= “Patliputra”))}

{
c, a| 
l
(

c,
l


borrower



l, “

Patli
p
utra”, a



{
(
p
loan)}
14

15. E
XAMPLE
Q
UERIES
(2)

Find the names of all customers havin
g
a loan
,

g,
an account, or both at the Patliputrabranch:

{c| l ( c, lborrower

b
(
l b
l
b
“
Ptli t
”))


b
,a
(

l
,
b
,

a



l
oan

b
=
“
P
a
tli
pu
t
ra
”))
a (c, adepositorb,n(a,
b, n accountb= “Patliputra”))}
15

16. E
XAMPLE
Q
UERIES
(3)

Find the names of all customers who have an account at all branches located in Dhanbad:

{c| x,y,z(x, y, z branchy= “Dhanbad”) 

ab
(

a x b


account


ca


depositor
)}

a
,
b
(

a
,
x
,
b


account


c
,
a


depositor
)}
16

17. S
AFETY OF
E
XPRESSION
The ex
p
ression:
p
{ x
1
, x
2
, …, x
n
| P (x
1
, x
2
, …, x
n
)}
is safe if -
all values that appear in tuples of the expression
are values from
dom
(
P
)
are values from
dom
(
P
)
17

18. E
XPRESSIVE
P
OWER OF
L
ANGUAGES

The followin
g
lan
g
ua
g
es are e
q
uivalent
ggg q

The basic relational algebra (without extended
relational algebra operation) 
The tuple relational calculus (restricted to safe

The tuple relational calculus (restricted to safe expression)

The domain relational calculus (restricted to safe
i)
express
i
on
)
18

19. R
ELATIONAL
A
LGEBRA TO
TRC

Let the followin
g
relation schemas be
g
iven:
gg

r<A,B,C>

s<D,E,F>
Gi i i h l l i l

Gi
ve

an

express
i
on
i
n

t
h
e

tup
l
e

re
l
at
i
ona
l
calculus that is equivalent to each of the
followin
g
:
g
i.
π
A
(r)
ii.
σ
B=17
(r)
iii

iii
.
r

x

s
iv.
Π
A,F
(σ
C=D
(r x s))
19

20. R
ELATIONAL
A
LGEBRA TO
DRC

Let R=
(
A
,
B
,
C
)
and let r
1
and r
2
both be relations
(,,)
1
2
on schema R. Give an expression in the DRC that
is equivalent to each of the following:
i
Π
(
)
i
.
Π
A
(
r
1
)
ii.
σ
B=17
(r
1
)
iii.
r
1
∩ r
2
iv.
r
1
–r
2
v.
Π
A,B
(r
1
) Π
B,C
(r
2
)
20