Tietokannan hallinta, syksy 2004, Harjoitus 4 (22.11. - 26.11.2004)

• Kuvassa on laajenevaa hajautusta käyttäen toteutettu rakenne.

  

  Piirrä rakenne kun siihen on lisätty tietueet, joiden avaimet ovat 68, 17 ja 69.
• Kuvassa on lineaarista hajautusta käyttäen toteutettu rakenne.

  

  Nykytaso on 0, ja h(0) eristää avaimen 2 viimeistä bittiä, h(1) vastaavasti 3 bittiä. Tietueen joutuminen ylivuotosivulle käynnistää laajennuksen. Piirrä rakenne kun siihen on lisätty tietueet, joiden avaimet ovat 4 ja 15.
• Tarkastellaan ulkoista lomitusjärjestämistä ja seuraavia tiedostoja
  • Tiedosto, jossa on 10,000 sivua ja viisi puskurisivua
  • Tiedosto, jossa on 20,000 sivua ja 9 puskurisivua
  • Tiedosto, jossa on 2,000,000 sivua ja 33 puskurisivua
  Vastaa kunkin tiedoston osalta seuraaviin kysymyksiin:
  • Kuinka monta järjestettyä jonoa (runs) syntyy jononmuodostusvaiheessa (= järjestettyjen osatiedostojen muodostus)?
  • Kuinka monta lomituskierrosta vaaditaan koko tiedoston järjestämiseen?
  • Kuinka monta levyoperaatiota tiedoston järjestäminen kokonaisuudessaan vaatii?
  • Kuinka monta puskurisivua tarvitset koko tiedoston järjestämiseen kahdella läpikäynnillä (jononmuodostus + yksi lomituskierros).
• Tietokantojen perusteet kurssilla käytetyn harjoitustietokannan rakenne on kuvattu sivulla http://www.cs.helsinki.fi/u/laine/tkpv/pizza2sql.html. Tarkastellaan seuraavaa kyselyä

  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
  

  • Tee kyselystä kyselypuu (pura relaatioalgebran operaatioiksi ja laita ne järjestykseen, ei tarvitse optimoida - mutta voit yrittää sitäkin)
  • Arvioi välitulosten ja tuloksen kokoa, kun tiedetään, että taulussa itemordered on 100000 riviä jakautuen 25000 tilaukseen (taulu ordered, jota ei tässä käytetä), taulussa product on 100 riviä ja taulussa objectname 600 riviä jakautuen kolmelle kielelle.
• Tehtävän 4 tietokannassa taulut itemordered ja product on toteutettu kasarakenteina. Sivukoko on 4 KB. Product rivejä mahtuu sivulle keskimäärin 30 ja itemordered rivejä keskimäärin 150. Puskuritilaa on käytettävissä 40 sivua. Taululla product on avainperustainen (productid, modelid) B+-puu indeksi. Millä tekniikalla toteuttaisit näiden kahden taulun viiteavainpohjaisen (productid, modelid) liitoksen. Montako levyhakua silloin tarvitaan?