The Relational Model | Course Paper

4

RELATIONAL ALGEBRA AND

CALCULUS

Exercise 4.1 Explain the statement that relational algebra operators can be com–

posed. Why is the ability to compose operators important?

Answer 4.1 Every operator in relational algebra accepts one or more relation in-

stances as arguments and the result is always an relation instance. So the argument

of one operator could be the result of another operator. This is important because,

this makes it easy to write complex queries by simply composing the relational algebra

operators.

Exercise 4.2 Given two relations R1andR2, where R1 contains N1 tuples, R2con–

tains N2 tuples, and N2 >N1 >0, give the minimum and maximum possible sizes (in

tuples) for the resulting relation produced by each of the following relational algebra

expressions. In each case, state any assumptions about the schemas for R1andR2

needed to make the expression meaningful:

(1) R1∪R2, (2) R1∩R2, (3) R1−R2, (4) R1×R2, (5) σa=5(R1), (6) πa(R1),

and (7) R1/R2

Answer 4.2 Answer omitted.

Exercise 4.3 Consider the following schema:

Suppliers(sid: integer,sname: string,address: string)

Parts(pid: integer,pname: string,color: string)

Catalog(sid: integer,pid: integer,cost: real)

The key fields are underlined, and the domain of each field is listed after the field

name. Therefore sid is the key for Suppliers, pid is the key for Parts, and sid and pid

together form the key for Catalog. The Catalog relation lists the prices charged for

parts by Suppliers. Write the following queries in relational algebra, tuple relational

calculus, and domain relational calculus:

28

Relational Algebra and Calculus 29

1. Find the names of suppliers who supply some red part.

2. Find the sids of suppliers who supply some red or green part.

3. Find the sids of suppliers who supply some red part or are at 221 Packer Street.

4. Find the sids of suppliers who supply some red part and some green part.

5. Find the sids of suppliers who supply every part.

6. Find the sids of suppliers who supply every red part.

7. Find the sids of suppliers who supply every red or green part.

8. Find the sids of suppliers who supply every red part or supply every green part.

9. Find pairs of sids such that the supplier with the first sid charges more for some

part than the supplier with the second sid.

10. Find the pids of parts supplied by at least two different suppliers.

11. Find the pids of the most expensive parts supplied by suppliers named Yosemite

Sham.

12. Find the pids of parts supplied by every supplier at less than $200. (If any supplier

either does not supply the part or charges more than $200 for it, the part is not

selected.)

Answer 4.3 In the answers below RA refers to Relational Algebra, TRC refers to

Tuple Relational Calculus and DRC refers to Domain Relational Calculus.

1. RA

πsname(πsid ((πpid σcolor=redParts) C a t a l o g ) Suppliers)

TRC

{T|∃T1∈Suppliers(∃X∈Parts(X.color =red∧∃Y∈Catalog

(Y.pid =X.pid ∧Y.sid =T1.sid)) ∧T.sname =T1.sname)}

DRC

{Y|X, Y, Z∈Suppliers ∧∃P, Q, R(P, Q, R∈Parts

∧R=red∧∃I,J,K(I,J,K∈Catalog ∧J=P∧I=X))}

SQL

30 Chapter 4

SELECT S.sname

FROM Suppliers S, Parts P, Catalog C

WHERE P.color=’red’ AND C.pid=P.pid AND C.sid=S.sid

2. RA

πsid(πpid (σcolor=red∨color=greenParts) c a t a l o g )

TRC

{T|∃T1∈Catalog(∃X∈Parts((X.color =‘red∨X.color =‘green)

∧X.pid =T1.pid)∧T.sid =T1.sid)}

DRC

{X|X, Y, Z∈Catalog ∧∃A, B, C(A, B, C∈Parts

∧(C=red∨C=green)∧A=Y)}

SQL

SELECT C.sid

FROM Catalog C, Parts P

WHERE (P.color = ‘red’ OR P.color = ‘green’)

AND P.pid = C.pid

3. RA

ρ(R1,π

sid((πpidσcolor=redParts) C a t a l o g ))

ρ(R2,π

sidσaddress=221P ackerStreetSuppliers)

R1∪R2

TRC

{T|∃T1∈Catalog(∃X∈Parts(X.color =‘red∧X.pid =T1.pid)

∧T.sid =T1.sid)

∨∃T2∈Suppliers(T2.address =221P ackerStreet∧T.sid =T2.sid)}

DRC

{X|X, Y, Z∈Catalog ∧∃A, B, C(A, B, C∈Parts

∧C=red∧A=Y)

∨∃P, Q(X, P, Q∈Suppliers ∧Q=221P ackerStreet)}

SQL

Relational Algebra and Calculus 31

SELECT S.sid

FROM Suppliers S

WHERE S.address = ‘221 Packer street’

OR S.sid IN (SELECT C.sid

FROM Parts P, Catalog C

WHERE P.color=’red’ AND P.pid = C.pid )

4. RA

ρ(R1,π

sid((πpidσcolor=redParts) C a t a l o g ))

ρ(R2,π

sid((πpidσcolor=greenParts) C a t a l o g ))

R1∩R2

TRC

{T|∃T1∈Catalog(∃X∈Parts(X.color =‘red∧X.pid =T1.pid)

∧∃T2∈Catalog(∃Y∈Parts(Y.color =green∧Y.pid =T2.pid)

∧T2.sid =T1.sid)∧T.sid =T1.sid)}

DRC

{X|X, Y, Z∈Catalog ∧∃A, B, C(A, B, C∈Parts

∧C=red∧A=Y)

∧∃P, Q, R(P, Q, R∈Catalog ∧∃E,F,G(E,F,G∈Parts

∧G=green∧E=Q)∧P=X)}

SQL

SELECT C.sid

FROM Parts P, Catalog C

WHERE P.color = ‘red’ AND P.pid = C.pid

AND EXISTS (SELECT P2.pid

FROM Parts P2, Catalog C2

WHERE P2.color = ‘green’ AND C2.sid = C.sid

AND P2.pid = C2.pid )

5. RA

(πsid,pid Catalog)/(πpidParts)

TRC

{T|∃T1∈Catalog(∀X∈Parts(∃T2∈Catalog

(T2.pid =X.pid ∧T2.sid =T1.sid)) ∧T.sid =T1.sid)}

32 Chapter 4

DRC

{X|X, Y, Z∈Catalog ∧∀A, B, C∈Parts

(∃P, Q, R∈Catalog(Q=A∧P=X))}

SQL

SELECT C.sid

FROM Catalog C

WHERE NOT EXISTS (SELECT P.pid

FROM Parts P

WHERE NOT EXISTS (SELECT C1.sid

FROM Catalog C1

WHERE C1.sid = C.sid

AND C1.pid = P.pid))

6. RA

(πsid,pid Catalog)/(πpidσcolor=redParts)

TRC

{T|∃T1∈Catalog(∀X∈Parts(X.color =‘red