CO526 Databases: Exercises
2018
In family history database, there is a person table, where people are identified by their name,
and always have their gender, date of birth (dob) and place of birth (born in) recorded. In addition,
each person may optionally have recorded the name of their father, and the name of their mother.
If the person has died, then the date of death dod must be present. Note that only a fragment of
the data held in the database is listed below.
person
name gender dob dod? father? mother? born in
Alice F 1885-02-25 1969-12-05 null null Windsor
Andrew M 1960-02-19 null Philip Elizabeth II London
Andrew of Greece M 1882-02-02 1944-12-03 George I of Greece null Athens
Anne (Princess) F 1950-08-15 null Philip Elizabeth II London
Charles M 1948-11-14 null Philip Elizabeth II London
Elizabeth II F 1926-04-21 null George VI Elizabeth London
…
person(father)
fk
⇒ person(name)
person(mother)
fk
⇒ person(name)
Questions
In the following questions you can test for a value v being null using the predicate isNull(v), and
v being not null using isNotNull(v). You may use subcripts on relation names to creat aliases of
relations, such that persona, personb, etc are aliases for person.
1. Describe how you would enhance the database schema (with additonal tables, columns,
primary keys or foreign keys) to allow the storage of which person is a monarch, and ensure
that we record for just monarchs (i) the year of succession to the throne as succ year, and
(ii) the name of the country which they are monarch of as cname.
2. Write a query in each of the following languages that returns the scheme (name,born in)
containing the name and place of birth of all people known to have been born in the same
place as their mother.
(a) RA
(b) Datalog
3. Write a query in each of the following languages that returns the scheme (name) containing
names of all people known to be parents.
(a) RA
(b) Datalog
4. Write a query in each of the following languages that returns the scheme (name) containing
the names of all men not known to be fathers.
(a) RA
(b) Datalog
5. Write a query in each of the following languages returning the scheme (name) listing those
people that have had at least one child of each gender that appears in the database.
(a) RA
Note that the above answer does make the assumption that each person can be just
a father, or just a mother. If you want to capture the concept of a person sometimes
being a mother, and sometimes being a father, you would need a union on the LHS of
each division.
(b) Datalog
6. Suppose the following RA query q has been executed:
πpersonb.name,persona.father σpersona.name=personb.mother∧isNotNull(persona.father)(persona × personb)
(a) If the query has been executed at one point in time, since which ∆ row have been
inserted into person to give person′ = person ∪∆p, give an RA query that returns any
additional answers to the original query.
(b) If the enhancements requested in Question 1(a) have been added, how could your answer
be improved?
7. Write an SQL query that returns the scheme (name,born in) ordered by name containing the
name and place of birth of all people known to have been born in the same place as their
mother.
8. Write an SQL query that returns the scheme (name) ordered by name containing the name
of all people known to be parents.
9. Write an SQL query that returns the scheme (name) ordered by name that lists parents for
whom all known children are of the same sex.
10. Suppose you have to design a new database to hold the following information about the com-
panies that do business with ACME Computing Ltd. These companies may be customers,
suppliers, or both. For all companies we record their name and contact email address, and
for companies that are VAT registered, we must record their VAT number.
For suppliers, we record the purchasing manager that deals with the supplier, and record a
number of types of product that the supplier can supply. We associate to each supplier all the
stock items currently being supplied. It is company policy that each stock item may come
from only one supplier, and some stock items are manufactured by ACME Computing Ltd
itself, and therefore have no supplier. Each stock item has a part number and description,
and some stock items have their colour recorded.
For customers, we record the sales manager that deals with the customer, and a credit limit.
We also record all orders made by the customer. Each order is on a particular date, is given
an order number, and has a reference number given by the customer. An order may have
any number of stock items, with the quantity and price for each stock item recorded.
When orders are sent, we record the tracking number of each parcel the order was sent in,
and the date on which the parcel was sent. We also wish to record how much of each stock
item was put in each parcel, in case the parcel gets lost and an insurance claim must be
made. We record the delivery address for each order, from a record of delivery addresses, for
which we record the customer name, postcode and address. We identify an address record
by the combination of the customer name and postcode.
(a) Design an ERADHKLMNOSVW schema to represent this new database.
(b) Map the ER schema you designed in (i) into a relational schema.
11. Suppose that a relation R(A,B,C,D,E, F,G,H) has the functional dependency set S =
{A → BE,AC → G,AFG → E,B → ACG,CF → D,D → G,DEG → FCD,G → H}
(a) Compute a minimum cover Sc of S.
(b) Identify and justify all the candidate keys of R.
(c) Decompose the relation R into 3NF.
(d) Decompose the relation R into BCNF.
12. The following histories describe the sequence of operations performed respectively by four
transactions T1–T4.
H1 = r1[cCZ ], r1[cR], r1[cB], r1[cGB], c1
H2 = r2[cB], r2[cR], r2[cCZ ], w2[cCZ ], c2
H3 = r3[cB], w3[cB], r3[cCZ ], w3[cCZ ], c3
H4 = w4[cR], w4[cB], w4[cGB], c4
(a) Briefly explain if the following concurrent execution is serialisable and recoverable. If
non-serialisable, explain what anomaly occurs.
Ha = r1[cCZ ], r1[cR], r3[cB], w3[cB ], r3[cCZ ], w3[cCZ ],
r1[cB], r1[cGB], c1, c3,
(b) Briefly explain if the following concurrent execution is serialisable and recoverable. If
non-serialisable, explain what anomaly occurs.
Hb = r3[cB], w4[cR], w4[cB], w4[cGB], w3[cB],
r3[cCZ ], w3[cCZ ], c4, c3
(c) Briefly explain if the following concurrent execution is serialisable and recoverable. If
non-serialisable, explain what anomaly occurs.
Hc = r1[cCZ ], w4[cR], r1[cR], w4[cB ], r1[cB], w4[cGB], c4, r1[cGB], c1
(d) Briefly explain which (if any) pair of the transactions taken from T1–T4 will be serialis-
able for all concurrent executions of the pair, and also briefly explain which (if any) pair
of the transactions taken from T1–T4 will be recoverable for all concurrent executions
of the pair.
(e) Give a concurrent execution of the four transactions, which produces a deadlock involv-
ing all four transactions, and draw a waits-for graph for the deadlock state.
13. The table below lists the contents of a database log, which keeps only UNDO records on a
table country.
UNDO w1[cR, population = 148, 179, 000]
UNDO w4[cTR, population = 62, 481, 123]
UNDO w2[cCH, population = 7, 392, 444]
UNDO w2[cGB, population = 58, 543, 111]
UNDO w3[cCH, population = 7, 312, 222]
UNDO w5[cCH, population = 7, 210, 000]
LOG c4
UNDO w3[cB, population = 11, 020, 000]
LOG c3
country
name code capital area population
Czech Republic CZ Prague 78,703 10,321,120
Switzerland CH Bern 41,290 7,207,060
Russia R Moscow 17,075,200 148,178,487
Belgium B Brussels 30,510 10,170,241
Turkey TR Ankara 780,580 62,484,478
United Kingdom GB London 244,820 58,489,975
Egypt ET Cairo 1,001,450 63,575,107
.
.
.
(a) If the country table has the contents illustrated above, describe the actions performed
by the recovery procedure using the above log, and what population figures will be left
after recovery.
(b) If an additional LOG record were added for a5 to record the completion of aborting T5,
would your answer to (a) change, and if so, how does it change?
(c) Considering the time just after when c4 occurs, describe and justify which updates from
the above log must have been written to disc, which might have been written to disc,
and which must not have been written to disc.