Course: Datenbanken II

Master of Computer Science

Datenbanken II Advanced Database Concepts TU Clausthal, Institut fr Informatik Due date: 24 January 2023, 13:00 Please read carefully This assignment is about Linear Hashing. For more information on this topic recall the lecture slides on Database Indexing and the readings on Disk Storage, Basic File Structures, and Hashing as well as on Indexing Structures for Files. In addition to your answer to a question also include all essential ideas and steps that are necessary to derive the solution. Write your solution in an understanding form or draw the respectively structure with some tool you might find fitting. You may need to format your files into .pdf! - The assignments have a total of 10 marks. In this task we will get first experience with Linear Hashing. We want to store a sequence of elements into a hash-structure and afterwards delete some of the entries. Before you start, you have to add another index at the end of the list. Convert your own birthday into an index, by building the checksum between day, month and year, where you add the day, the month and the checksum of the year like it is shown in the 3 examples below: f(27.01.2021):=27+01+2+0+2+1=33f(01.10.1995):=01+10+1+9+9+5=35f(31.12.2000):=31+12+2+0+0+0=45 Afterwards add the new created index to the end of the following sequence: 22,8,17,55,65,78,23,30,1 Hint: If the index of your birthday is the same as an already existing value in the sequence, you can add 1 until you get a new value! (a) Explain why using the scheme described in task 1 could lead to errors, when calculating the index value for different birthdays! (b) Start with M=2 and level =0 and use the hash function h0(k)=k%M, to insert the sequence into a linear hash structure: Show the hash structure after each insertion! (c) Delete the following sequence of indexes from your hash structure: ,17,22,30 Show the hash structure after each deletion