Scribd
Upload
41 views8 pages

Relational Algebra Assignment Solutions

Uploaded by

doanviethong123
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
41 views8 pages

Relational Algebra Assignment Solutions

Uploaded by

doanviethong123
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Solution to the

Assignment 2
Dirk Van Gucht & Mo

Zhou September 29, 2008

Relational Algebra
- We write r(ABC) for a relational schema with relation name r and
attributes (or fields) A, B, and C. The underlined attribute is the
primary key.

Basic Algebra
1. Given following relational schema, write expressions of relational
algebra to answer the following queries.

Relational schema of question 1.


Product(model, maker, type)
PC(model, speed, ram, hd, price)
Laptop(model, speed, ram, hd, screen, price)
Printer(model, color, type, price)

1
The sample data for relations of question 1. These data are not used
to calculate results of following questions.

Product:
model maker type
1001 A PC
3001 B Printer
2001 C laptop
PC:
model speed ram hd price
1001 2.66 1024 250 2114
1002 1.42 512 250 955
1003 3.20 2048 160 1049

Laptop:
model speed ram hd screen price
2001 2.00 1024 250 15 2114
2002 1.73 512 80 24 955
2003 1.83 2048 60 20 1049

Printer:
model color type price
3001 true ink-jet 99
3002 false laser 239
3003 true laser 899

2
(a) What PC models have a speed of at least 3.00?
πmodel(σmodel≥3.00(P C))
(b) Find the model numbers of all color laser printers.
πmodel(σtype=laser∧color=true(P rinter))
(c) Which manufacturers make laptops with a hard disk of at least
100GB?
πmaker (P roduct Da σhd≥100 (Laptop))
(d) Find the model number and price of all products (of any type)
made by manufacturer B.
πmodel,price (σmaker=B (P roduct)) Da
(πmodel,price(P C) ∪ πmodel,price(Laptop) ∪ πmodel,price(P rinter))
(e) Find those manufacturers that sell Laptops, but not PC’s.
πmaker(σtype=Laptop(P roduct)) − πmaker(σtype=P C (Product))
(f) Find those manufacturers that sell all models of PCs and lazer
Printers.
πmaker(Product/(πmodel(PC) ∪ πmodel(σtype=lazer(Printer))))
(g) Find those manufacturers whose laptops have all ram sizes that
manufacturer B’s laptops have.
(πmaker,ram (P roduct Da Laptop)) / (πram (σmaker=B (P roduct) Da
Laptop))
(h) Find those manufacturers of at least two different computers
(PC’s or laptops) with speeds of at least 2.80. ρ(TEMP
1, πmodel(σspeed≥2.80(PC)) ∪
πmodel (σspeed≥2.80 (Laptop)))
ρ(T EM P 2, P roduct Da T EM P
1)
πmaker(σT EMP [Link]=T EMP [Link]∧T EMP [Link] TEMP [Link](T EMP 2×
ρ(TEMP 3, TEMP 2)))
(i) Find the manufacturers of PC’s with at least two different
speeds.
π[Link] (σ[Link] [Link]∧[Link]=[Link] ((ρ(R1, (P roduct Da
P C)) × ρ(R2, (P roduct Da P C)))))
(j) Find the manufacturers who sell exactly two different models of
PC.
π[Link] (σ[Link] [Link]∧[Link]=[Link] (ρ(R1, (P roduct Da
P C)) × ρ(R2, (P roduct Da P C)))) −
π[Link] (σ[Link]ƒ=[Link]∧[Link]ƒ=[Link]∧[Link]ƒ=[Link]
∧[Link]=[Link]∧[Link]=[Link]
3
(ρ(R1, (P roduct Da P C)) × ρ(R2, (P roduct Da
P C)) × ρ(R3, (P roduct Da P C))))
(k) Find those pairs of PC models that have both the same speed
and RAM. A pair should be listed only once; e.g., list (i, j) but
not (j, i).
Hint: The model numbers can be compared.
π[Link],[Link]
(σ[Link]=[Link]∧[Link]=[Link]∧[Link]>[Link]
(ρ(PC1, PC) × ρ(PC2, PC)))
(l) Find the manufacturer(s) of the computer (PC or laptop) with
the highest available speed.
Hint: the highest speed means that it is not smaller than any
other speeds. If you can find all the speeds which are
smaller than some speed, you can solve this problem.
ρ(Computer, (πmodel,speed(PC) ∪ πmodel,speed(Laptop)))

ρ(HighestSpeedM odel, πmodel(Computer) −


πmodel(σP [Link]<P [Link](ρ(P 1, Computer) × ρ(P 2, Computer))))

πmaker (P roduct Da HighestSpeedM odel)

4
Constraints

2. Express the following constraints about the relations below.


Product(model,maker, type)
PC(model, speed, ram, hd, price)
Laptop(model, speed, ram, hd, screen, price)
Printer(model, color, type, price)

(a) A PC with a processor speed less than 2.00 must not sell for
more than $500.
σspeed<2.00∧price>500(P C) = ∅

(b) No manufacturer of PC’s may also make laptops.


πmaker(Product Da PC) ∩πmaker(Product Da Laptop) = ∅
OR
πmaker(σtype=P C (Product)) ∩ πmaker(σtype=Laptop(Product)) = ∅

(c) A manufacturer of a PC must also make a laptop with at least


as great a processor speed.
Find the highest speed of PC for each manufacturer.

ρ(T emp, πmaker,speed (P roduct Da P C))


ρ(T emp2, T emp −
πT [Link],T [Link](σT [Link]<T [Link]∧T [Link]=T [Link](ρ(T 1, T emp) ×
ρ(T 2, T emp))))

Find the highest speed of Laptop for each manufacturer

ρ(T emp3, πmaker,speed (P roduct Da Laptop))


ρ(T emp4, T emp3 −
πT [Link],T [Link](σT [Link]<T [Link]∧T [Link]=T [Link](ρ(T 3, T emp) ×
ρ(T 4, T emp))))

For the same manufacturer, the highest speed of the laptop


must as great as the one of the PC.

σT [Link]=T [Link]∧T [Link]≥T [Link](T emp2 ×


T emp4) = ∅

5
3. Express the following constraints in relational algebra. The
constraints are based on the following relations.
Classes(class, type, country, numGuns, bore, displacement)
Ships(shipname, class, launched)
Battles(battlename, date)
Outcomes(shipname, battlename, result)

(a) No country may have both battleships and


battlecruisers.(battleship and battlecruiser are values of
attribute type in relation Classes)
πcontry(σtype=battlecruiser(Classes)) ∩
πcontry(σtype=battleship(Classes)) = ∅
(b) No ship with more than 9 guns may be in a battle with a ship
having fewer than 9 guns that was sunk. (sunk is a value of
attribute result in relation Outcomes)
πbattlename((σnumGuns>9(Classes) Da Ships) Da Battles) ∩
πbattlename((σnumGuns<9(Classes) Da Ships) Da (σresult=sunk(Battles)))
=∅

6
Special algebra

4. Suppose relations R and S have n tuples and m tuples, respectively.


Give the minimum and the maximum numbers of tuples that the
results of the following expressions can have.

(a) R ∪ S
(b) R Da S
(c) σC (R) × S, for some condition C.
(d) πL(R) − S, for some list of attributes L.

Expression Max Min


R ∪S n+m max(m,n)
R Da S min(m,n) 0
σC (R) × S m×n
0 πL(R) − S
n 0
5. The semijoin of relations R and S is the set of tuples t in R such that
there is at least one tuple in S that agrees with t in all attributes
that R and S have in common. Give three different expressions of
relational algebra equivalent to semijoin.
Suppose that R has n domains and S has m domains. And the first k
domains are the same for both R and S.

(a) π1,. ,n(R Da S)


(b) π1,...,n(σR.1=S.1∧. .∧R.k=S.k(R × S))
(c) R Da π1,. ,k (S)

6. The antisemijoin is the set of tuples t in R that do not agree with


any tuple of S in the attributes common to R and S. Give an
expression of relational equivalent to antisemijoin.
R − π1,. ,n (R Da S)

7. An operator on relations is said to be monotone if whenever we add


a tuple to one of its arguments, the result contains all the tuples that
it contained before adding the tuple, plus perhaps more tuples. Are
semijoin and antisemijoin monotone? For each, either explain why it
is monotone or give an example showing it is not.
7
Solution: Semijoin is monotone.
Antisemijoin is not monotone.

Common questions

Powered by AI

The operation πPC1.model,PC2.model (σPC1.speed=PC2.speed∧PC1.ram=PC2.ram∧PC1.model>PC2.model (ρ(PC1, PC) × ρ(PC2, PC))) finds pairs of PC models with identical speed and RAM by performing a self-join to match models with the same attributes while ensuring the relational order to prevent duplicate entries .

The constraint σspeed<2.00∧price>500(PC) = ∅ ensures no such PC exists by enforcing an empty result set condition. This expression verifies there is no overlap between PCs with the specified speed and price criteria, thus satisfying the constraint requirement .

The expression πcountry(σtype=battlecruiser(Classes)) ∩ πcountry(σtype=battleship(Classes)) = ∅ ensures that no single country has both battleships and battlecruisers by checking for an empty intersection between the sets of countries having these types. Any overlap would indicate a violation of the constraint .

The expression πR1.maker(σR1.model R2.model∧R1.maker=R2.maker(ρ(R1, (Product Da PC)) × ρ(R2, (Product Da PC)))) − πR1.maker(σR1.modelƒ=R2.model∧R1.modelƒ=R3.model∧R2.modelƒ=R3.model∧R1.maker=R2.maker∧R1.maker=R3.maker(ρ(R1, (Product Da PC)) × ρ(R2, (Product Da PC)) × ρ(R3, (Product Da PC)))) extracts manufacturers who have exactly two different PC models by first finding manufacturers with pairs of PCs and then subtracting those manufacturers who have a third different PC model .

To find manufacturers that sell both PCs and laser printers, you can use the following relational algebra expression: πmaker(Product/(πmodel(PC) ∪ πmodel(σtype=laser(Printer)))). This expression uses the division operation in relational algebra to retrieve manufacturers who sell all models of PCs and laser printers by ensuring all required models are covered in the product list .

The constraint can be expressed with the operation πmaker(Product Da PC) ∩ πmaker(Product Da Laptop) = ∅. It checks the set intersection of manufacturers of PCs and laptops and ensures there is no overlap, indicating no common manufacturers between the two product categories .

The expression πR1.maker(σR1.speed R2.speed∧R1.maker=R2.maker((ρ(R1, (Product Da PC)) × ρ(R2, (Product Da PC)))) finds manufacturers of PCs with at least two different speeds. It performs a self-join on the selection of PC data, ensuring that the speeds differ, thereby identifying those models associated with a manufacturer offering variability .

Semijoin is considered a monotone operator because when a tuple is added to the input tuples, the semijoin result either remains the same or includes more tuples. Adding a tuple to one of the relations cannot remove tuples from the semijoin result as it only extends the existing set with possible matches .

The relational algebra expression πmaker,ram(Product Da Laptop) / πram(σmaker=B(Product) Da Laptop) retrieves those manufacturers whose laptops have all the RAM sizes that manufacturer B's laptops possess. This is achieved using a division: it finds manufacturers whose range of RAM offerings in their laptop models matches completely with those offered by manufacturer B .

You use the expression (πmaker,ram(Product Da Laptop)) / (πram(σmaker=B(Product) Da Laptop)) to identify manufacturers whose laptops meet specific RAM size requirements by comparing against a baseline set of RAM sizes offered by manufacturer B, ensuring all required RAM sizes are matched in the offerings of other manufacturers .

You might also like