Second set of mandatory exercises in INF3100/INF4100 Spring 2005

Formalities

All students are to hand in an individual assignment. If two students want to hand in an assignment together, they have to make arrangements with their group teacher regarding this in advance.

The assignment is to be delivered by email to the group you have been accepted to. (The email addresses for the groups can be found on the semester pages for INF3100.)

The email to the group is to have the following subject field:

Subject: Oblig 2 inf3100 (<username student >)

Students that have had their assignment accepted and still choose to withdraw from the exam, have to deliver a paper copy of the assignment to their group teacher to get a written statement from the group teacher that it has been accepted. This only regards students that withdraw before the 14-day limit.

This mandatory exercise is due: Friday 13^th of May at 10:00 am.

It is a good idea to start working on this as early as possible.

Exercise 1

Given the following data structure for a relational database (Primary keys are printed in bold face, other candidate keyes are printed in italics, foreign keys are given by the attribute �names):

PERSON (Ssn, Surname, Forename, Address)
MARRIAGE (Ssn-w, Ssn-m, Date, Surname-w, Surname -m)
NAME-CHANGE (Ssn, Date, Surname, Forename)

The current name is stored in PERSON. Hence, in NAME-CHANGE we store the name a person had immediately prior to changing his/her name. The names in MARRIAGE are the surnames after the wedding.

Solve the following task both using relational algebra and SQL:

1. Find name and address of all women which in the years 1968-72 on their wedding day changed their last name to a name different from their groom�s last name.
2. Find the name and address of all women who by a wedding in 2003 have swapped surname with their bridegroom. Wedded couples having the same surname should not be listed.

Exercise 2

Using Exercise 1 as basis, make an OO-data structure. It is obvious that the table PERSON have to be replaced with a class Person. It is also fairly obvious that the table NAME-CHANGE is to be replaced with a local list in each person object. (We could very well have chosen a set or bag instead of a list, but the name changes for a person are ordered in time.)

For the table MARRIAGE, it is not such a clear cut case. We can choose to replace it with a separate class Marriage, or to replace it with local data in each person object.

Exercise 2 a

Write a complete ODL definition for each of the alternatives above (having respectively two and one classes). Do not forget the methods, and remember it is only the method signature that is a part of ODL!

Exercise 2 b

Use OQL to answer both questions in Exercise 2 for each of the ODL definitions in 2 a.�

Exercise 3

Assume we have a storage system using (modified) Seagate Cheetah X15 disks. Some of the specifications are as follows:

Disk platters:���������������� 8�������� ���� 

Tracks:������������������������ 20000���� ��� 

Number of sectors per track:�� 700 (not zoned disk)

Bytes per sector:����� ���������512����� 

Bytes per gap/checksum/...:��  64������������ 

Average seek time:������� ���� 3.6 ms� 

Track-to-track seek:����������� 0.3 ms������� 

Rotation speed:��������������� ������ 15.000 RPM���� 

Further, assume that the storage system uses blocks of 4 KB, and that we may neglect delays like processing queries, transfer over buses, waiting for turn, etc.

Exercise 3 a

1. What is the total capacity of the disk if the platters are used on both sides?
2. What is the average rotation delay?
3. What is the average access time for an arbitrary block?

We create a customer database on the storage system above. Each block has a header of 12 B, and each record has a header of 20 B. We have 1.000.000 customers, where each record has the following fields (number of bytes):��

navn��� (30) � 

fnr�� ��(9)��� 

adresse (30)�� 

tlf���� (8)��� 

email�� (30)�� 

Exercise 3 b�

1. What is the block factor?
2. How much time does it take to read the whole table (continuously) if we assume unspanned storage and arbitrary placing of blocks on the disk?
3. Instead of arbitrary placing, we try continuous placing on the disk � we fill one track first, if full, we take the next track in the same cylinder, if full again, the next cylinder. Assume that the table starts in the first sector in the first track in a cylinder. How much time does it take now to read the whole table (continuously), if we still assume unspanned storage and that change of� disk head does not take any time (we can start reading directly)?

Assume again that the blocks are arbitrarily placed on the disk, and that the time it takes to process a block in memory is close to zero.

Exercise 3 c

1. What is the average time for accessing an arbitrary record without indexes?
2. We add a dense index with binary search. Unique search key is fnr, and the pointer takes 8 B. How much space does the index take if each block in average is 80% full?
3. What is the average time (assume a maximum number of lookups in the index) needed to access an arbitrary record using an index like this?
4. Now, we replace our index with a B⁺-tree. How much space does the B⁺-tree need if each node uses a disk block of its own which in average is 80 % full?�
5. What is the time now needed to access an arbitrary record?�

Exercise 4

Consider the following schedule where we use binary locks:

Exercise 4 a

Draw the precedence graph (serializability graph), and decide if the plan is conflict-serializable.�

Exercise 4 b

Explain/show why the plan does not obey the two-phase locking protocol (2PL).

Exercise 4 c

Make a schedule for the three transactions that satisfy 2PL, draw the precedence graph for the new schedule, and show that it is conflict-serializable.�

Exercise 5

Solve the Exam in INF3100 given spring 2004 (you will find a link to the exam on the INF3100 semester page).

End of mandatory exercise set 2.