Ívning om fysiska databaser (Databasteknik II)

A telecom database contains the tables Subscriber and Call. Subscriber contains one row for each subscriber, and Call contains one row for each call made from one subscriber to another.

Subscriber
SnrNameAddressCategory
7Tom2 Some StA
3Anne11 Any RdB
11Zeb4711 Sunset BlvdA
............
  Call
CnrCallerCalledStartEndDuration
171114:06:2214:06:4725
27314:09:2214:19:22600
..................

Expressed with the usual notation:

Subscriber(Snr, Name, Address, Category)
Call(Cnr, Caller, Called, Start, End, Duration)
The table Subscriber has 105 rows. The table Call has one million (106) rows.

Queries like these will be used fairly often:

  1. Anne has the address 11 Any Rd. What's her number?
    select snr
    from subscriber
    where name = 'Anne' and address = '11 Any Rd'
    
  2. What is the name and address of the subscriber that made call number 2001?
    select name, address
    from subscriber, call
    where subscriber.snr = call.caller
    and call.cnr = 2001
    
  3. What is the sum of call durations for subscriber 17?
    select sum(duration)
    from call
    where caller = 17
    
Exercise:

  1. Assume that we have no indexes and no specific sorting order. How long will the queries above take to execute? Assume a good query optimizer. Make realistic assumptions about block size, block access times, etc.
  2. Chose suitable indexes, i. e., which columns you will add indexes for.
  3. Assume that the database uses (suitably large) hash tables for all its indexes. How long will the queries take to execute? Assume a good query optimizer.
  4. Assume that the database uses B+ trees for all its indexes. How long will the queries take to execute? Assume a good query optimizer.
  5. The telecom company grows, and now has one million subscribers, who have made ten million calls. How will this affect the times in question 1, 3 and 4?
  6. Can you do something else to speed up the queries?

[Solutions]


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 11 februari 2007