Exercise 5.2.1n
A R.B 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 2 2 3 ┴ ┴ 1 3 4 4 ┴ ┴ S.B 2 2 3 3 2 2 3 3 ┴ ┴ ┴ 0 0 C 4 5 4 4 4 5 4 4 ┴ ┴ ┴ 1 2
Exercise 5.2.2a
Applying the δ operator on a relation with no duplicates will yield the same relation. Thus δ is idempotent.
Exercise 5.2.2b
The result of πL is a relation over the list of attributes L. Performing the projection again will return the same relation because the relation only contains the list of attributes L. Thus πL is idempotent.
Exercise 5.2.2c
The result of σC is a relation where condition C is satisfied by every tuple. Performing the
selection again will return the same relation because the relation only contains tuples that satisfy the condition C. Thus σC is idempotent.
Exercise 5.2.2d
The result of γL is a relation whose schema consists of the grouping attributes and the aggregated attributes. If we perform the same grouping operation, there is no guarantee that the expression would make sense. The grouping attributes will still appear in the new result. However, the aggregated attributes may or may not appear correctly. If the aggregated attribute is given a different name than the original attribute, then performing γL would not make sense because it contains an aggregation for an attribute name that does not exist. In this case, the resulting
relation would, according to the definition, only contain the grouping attributes. Thus, γL is not idempotent.
Exercise 5.2.2e
The result of τ is a sorted list of tuples based on some attributes L. If L is not the entire schema of relation R, then there are attributes that are not sorted on. If in relation R there are two tuples that agree in all attributes L and disagree in some of the remaining attributes not in L, then it is arbitrary as to which order these two tuples appear in the result. Thus, performing the operation τ multiple times can yield a different relation where these two tuples are swapped. Thus, τ is not idempotent.
Exercise 5.2.3
If we only consider sets, then it is possible. We can take πA(R) and do a product with itself. From this product, we take the tuples where the two columns are equal to each other.
If we consider bags as well, then it is not possible. Take the case where we have the two tuples (1,0) and (1,0). We wish to produce a relation that contains tuples (1,1) and (1,1). If we use the classical operations of relational algebra, we can either get a result where there are no tuples or four copies of the tuple (1,1). It is not possible to get the desired relation because no operation can distinguish between the original tuples and the duplicated tuples. Thus it is not possible to get the relation with the two tuples (1,1) and (1,1).
Exercise 5.3.1
a) Answer(model) ← PC(model,speed,_,_,_) AND speed ≥ 3.00
b) Answer(maker) ← Laptop(model,_,_,hd,_,_) AND Product(maker,model,_) AND hd ≥ 100
c) Answer(model,price) ← PC(model,_,_,_,price) AND Product(maker,model,_) AND maker=’B’
Answer(model,price) ← Laptop(model,_,_,_,_,price) AND Product(maker,model,_) AND maker=’B’
Answer(model,price) ← Printer(model,_,_,price) AND Product(maker,model,_) AND maker=’B’
d) Answer(model) ← Printer(model,color,type,_) AND color=’true’ AND type=’laser’
e) PCMaker(maker) ← Product(maker,_,type) AND type=’pc’
LaptopMaker(maker) ← Product(maker,_,type) AND type=’laptop’ Answer(maker) ← LaptopMaker(maker) AND NOT PCMaker(maker)
f) Answer(hd) ← PC(model1,_,_,hd,_) AND PC(model2,_,_,hd,_) AND model1 <> model2
g) Answer(model1,model2) ← PC(model1,speed, ram,_,_) AND PC(model2,_speed,ram,_,_) AND model1 < model2
h) FastComputer(model) ← PC(model,speed,_,_,_) AND speed ≥ 2.80
FastComputer(model) ← Laptop(model,speed,_,_,_,_) AND speed ≥ 2.80
Answer(maker) ← Product(maker,model1,_) AND Product(maker,model2,_) AND FastComputer(model1) AND FastComputer(model2) AND model1 <> model2
i) Computers(model,speed) ← PC(model,speed,_,_,_)
Computers(model,speed) ← Laptop(model,speed,_,_,_,_)
SlowComputers(model) ← Computers(model,speed) AND Computers(model1,speed1) AND speed < speed1
FastestComputers(model) ← Computers(model,_) AND NOT SlowComputers(model) Answer(maker) ← FastestComputers(model) AND Product(maker,model,_)
j) PCs(maker,speed) ← PC(model,speed,_,_,_) AND Product(maker,model,_)
Answer(maker) ← PCs(maker,speed) AND PCs(maker,speed1) AND PCs(maker,speed2) AND speed <> speed1 AND speed <> speed2 AND speed1 <> speed2
k) PCs(maker,model) ← Product(maker,model,type) AND type=’pc’ Answer(maker) ← PCs(maker,model) AND PCs(maker,model1) AND
PCs(maker,model2) AND PCs(maker,model3) AND model <> model1 AND model <> model2 AND model1 <> model2 AND (model3 = model OR model3 = model1 OR model3 = model2)
Exercise 5.3.2
a) Answer(class,country) ← Classes(class,_,country,_,bore,_) AND bore ≥ 16
b) Answer(name) ← Ships(name,_,launched) AND launched < 1921
c) Answer(ship) ← Outcomes(ship,battle,result) AND battle=’Denmark Strait’ AND result = ‘sunk’
d) Answer(name) ← Classes(class,_,_,_,_,displacement) AND Ships(name,class,launched) AND displacement > 35000 AND launched > 1921
e) Answer(name,displacement,numGuns) ← Classes(class,_,_,numGuns,_,displacement) AND Ships(name,class,_) AND Outcomes (ship,battle,_) AND battle=’Guadalcanal’ AND ship=name
f) Answer(name) ← Ships(name,_,_)
Answer(name) ← Outcomes(name,_,_) AND NOT Answer(name)
g) MoreThanOne(class) ← Ships(name,class,_) AND Ships(name1,class,_) AND name <> name1
Answer(class) ← Classes(class,_,_,_,_,_) AND NOT MoreThanOne(class)
h) Battleship(country) ← Classes(_,type,country,_,_,_) AND type=’bb’ Battlecruiser(country) ← Classes(_,type,country,_,_,_) AND type=’bc’ Answer(country) ← Battleship(country) AND Battlecruiser(country)
i) Results(ship,result,date) ← Battles(name,date) AND Outcomes(ship,battle,result) AND battle=name
Answer(ship) ← Results(ship,result,date) AND Results(ship,_,date1) AND result=’damaged’ AND date < date1
Exercise 5.3.3
Answer(x,y) ← R(x,y) AND z = z
Exercise 5.4.1a
Answer(a,b,c) ← R(a,b,c) Answer(a,b,c) ← S(a,b,c)
Exercise 5.4.1b
Answer(a,b,c) ← R(a,b,c) AND S(a,b,c)
Exercise 5.4.1c
Answer(a,b,c) ← R(a,b,c) AND NOT S(a,b,c)
Exercise 5.4.1d
Union(a,b,c) ← R(a,b,c) Union(a,b,c) ← S(a,b,c)
Answer(a,b,c) ← Union(a,b,c) AND NOT T(a,b,c)
Exercise 5.4.1e
J(a,b,c) ← R(a,b,c) AND NOT S(a,b,c) K(a,b,c) ← R(,a,b,c) AND NOT T(a,b,c) Answer(a,b,c) ← J(a,b,c) AND K(a,b,c)
Exercise 5.4.1f
Answer(a,b) ← R(a,b,_)
Exercise 5.4.1g
J(a,b) ← R(a,b,_) K(a,b) ← S(_,a,b)
Answer(a,b) ← J(a,b) AND K(a,b)
Exercise 5.4.2a
Answer(x,y,z) ← R(x,y,z) AND x = y
Exercise 5.4.2b
Answer(x,y,z) ← R(x,y,z) AND x < y AND y < z
Exercise 5.4.2c
Answer(x,y,z) ← R(x,y,z) AND x < y Answer(x,y,z) ← R(x,y,z) AND y < z
Exercise 5.4.2d
Change: NOT(x < y OR x > y) To: x ≥ y AND x ≤ y
The above simplifies to x = y
Answer(x,y,z) ← R(x,y,z) AND x = y
Exercise 5.4.2e
Change: NOT((x < y OR x > y) AND y < z) NOT(x < y OR x > y) OR y ≥ z (x ≥ y AND x ≤ y) OR y ≥ z To: x = y OR y ≥ z
Answer(x,y,z) ← R(x,y,z) AND x = y Answer(x,y,z) ← R(x,y,z) AND y ≥ z
Exercise 5.4.2f
Change: NOT((x < y OR x < z) AND y < z) NOT(x < y OR x < z) OR y ≥ z To: (x ≥ y AND x ≥ z) OR y ≥ z