The minimum requirement for active attendance: 3 tasks done
1. The relation WORKS_ON is implemented as a heap file. In addition, we have a hash-based secondary index to this relation, the index key being ESSN.
a) How this solution relates to the hash file used in task 2.2 (last week)? Is it better or worse? Why?
b) How the relation WORKS_ON should be implemented if we need grouping on projects (PNO) as well as on employees (ESSN)? (See task 2.3.)
2. Assume that the relation EMPLOYEE is implemented as a heap file and
we have the following indexes:
- an ISAM index based on the attribute pair (LNAME, FNAME),
- an ISAM index based on attribute SSN,
- a hash-based index based on attribute DNO.
a) Describe the file structure (data file + indexes) with example values. (See E&N, Figs. 6.4-5)
b) Explain how the indexes can be used. Are there some typical situations (e.g. typical queries) for which this index structure is not sufficient?
3. Assume that relation EMPLOYEE has the indexes given in task 2. Explain all operations (record fetches and record updates; both for the indexes and for the data file) when the following queries are executed:
insert into EMPLOYEE values (...);
delete from EMPLOYEE where SSN = '123456789' or SSN = '333445555';
update EMPLOYEE set SALARY = SALARY * 1.1 where SSN = '123456789';
update EMPLOYEE set DNO = 4 where FNAME = 'John' and LNAME = 'Smith';
4. In a B+-tree of order 5 there are 2 to 4 index keys in every node. Assume that the following keys are inserted into an empty B+-tree in that order: 23, 65, 37, 60, 46, 92, 48, 71, 56, 59, 18, 21, 10, 74, 78, 15, 16, 20, 24.
a) Describe how the B+-tree structure is formed (stepwise). (See E&N, Fig. 6.12; the essential changes are of course sufficient.)
b) How the structure is changed when the keys 20, 18 and 37 are deleted?
5. What is the size of an ISAM index and of an B+-tree index in the following situation: A fill-factor of 70 % is used both in the nodes of B+-tree and on the lowest level of the ISAM index. Indexing key is 10 bytes, file size 1000000 records, record length 40 bytes and block size (page size) 4 KB. You can estimate the lengths of pointers (links) yourself. Also, if you need other assumptions you are free to do so.
6. For the file of task 5, estimate the size and the number of disk accesses of two dynamic hash indexes: extendible hashing (E&N, 145-146) and dynamic hashing. The latter is not included in E&N, 3rd edition. It can be found on page 29 of the chapter 3 lecture material or in E&N's older version (E&N2, p. 93). (The 'dynamic hashing' case is optional in this task.)
The Finnish lecture notes are available via the Finnish course page ('Luentokalvot') in pdf-format or in a course folder in room A412 (on paper).