Database Management, fall 04, Exercise 4 (25.11.2004)

• Extendible hashing has produced the file shown below

  

  Draw the file when records with hashed key values 68, 17 and 69 have been inserted.
• Linear hahing has produced the file shown below

  

  The current level is 0. h(0) picks up 2 last bits of the hashed key and h(1) 3 last bits. A cell is split each time a record is added into an overflow page. Draw the file after records with hashed keys 4 and 15.
• Consider external sorting and the following cases
  • A 10,000 page file and buffers for 5 pages
  • A 20,000 page file and buffers for 9 pages
  • A 2,000,000 page file buffers for 33 pages
  Answer the following question for each case
  • How many runs are constructed in the run construction phase?
  • How many merge steps are needed to sort the file?
  • How many disk operations are needed?
  • How many buffer pages make it possible to sort the file in two steps (run construction + one merge step).
• Consider the database described in http://www.cs.helsinki.fi/u/laine/tkpv/pizza2sql.html. and the following query

  select i.orderid, i.productid, pn.objectname, p.modelid, 
      p.price, i.amount
  from itemordered i, product p, objectname pn 
  where p.productid=i.productid and
  i.modelid=p.modelid and
  i.orderid=3019 and pn.language='english' and
  pn.objectid=i.productid
  

  • Construct a tree representation of this query (determine the operations of relational algebra and their sequence, the tree need not be optimized)
  • Estimate the sizes of the intermediate and final results.We know that table itemordered has 100000 rows. There are 25000 orders. Table product has 100 rows and table objectname has 600 rows that specify the names in 3 languages.
• Tables itemordered and product (of task 4) are implemented as piles. Page size is 4 KB. A page contains, in average, 30 product rows or 150 itemordered rows. There is buffer space available for 40 pages. Table product has a key based (productid, modelid) secondary index organized as a B+-tree. How would you implement the join of these two tables on colums (productid, modelid). How many disk accesses are needed?