Tietokannan hallinta, syksy 2005, Harjoitus 5

1 Tutkitaan liitosta R JOINR.a=S.b S. Kustannusmittana käytetään levysivujen luku-/kirjoitusmäärää. Tuloksen kirjoitukseen vaadittavaa kustannusta ei oteta huomioon, jos erikseen ei ole mainittu. Sivunkoko on 4KB. Taulu R sisältää 10,000 tietuetta ja jokaisella sivulla on 10 tietuetta. Taulu S sisältää 2000 tietuetta ja jokaisella sivulla on 10 tietuetta. Sarake b on taulun S pääavain. Molemmat taulut on talletettu kasarakenteina, eikä niihin liity hakemistoja. Puskurisivuja on käytössä 52 ja puskurisivun koko on 4KB.

(a) Mikä on liitoksen kustannus käytettäessä jaksottaisten sisäkkäisten silmukoiden liitosmenetelmää? Mitä puskureiden määrän vähentäminen vaikuttaa kustannuksiin?

Puskureita 50 ulommalle taululle (=S), yksi sisemmälle ja yksi tulostaululle.
Kustannus: 200 + (200/50)*1000 = 4200.
Jos puskureiden määrä vähenee yhdelläkin niin jakaja 50 pienenee siten, että ylläolevan 4 kierroksen asemasta tarvitaan 5 kierrosta.

(b) Mikä on liitoksen kustannus käytettäessä lomitusliitosta. Miten paljon puskureiden määrää voitaisiin vähentää kustannuksia lisäämättä?

Tiedostot on ensin järjestettävä. Järjestämiseen liittyy jonojen muodostus ja lomitus. Jos jonojen muodostukseen käytetään 51 puskuria syötteelle saadaan S:lle 4 jonoa ja R:lle 20 jonoa. Puskuritilaa on riittävästi, jotta jonot voidaan lomittaa yhdellä kierroksella ja jopa rinnakkain, niin että lomitusliitos voidaan putkittaa järjestämisen perään. Tällöin tarvitaan vain 3*(200+1000) =3600 operaatiota. Ellei lomitusta putkiteta tarvitaan 5*(200+1000)=6000 levyoperaatiota.
Kriittinen tekijä on jonojen yhteismäärä, jonoja ei saa tulla niin paljon, ettei jokaiselle riitä puskuria, koska tällöin tarvitaan välikirjoitus roof(200/(B-1))+roof(1000/(B-1))<B-1 eli 36 puskuria riittää.
roof(200/35)= 6, roof(1000/35)= 29

(c) Mikä on liitoksen kustannus käytettäessä hajautusliitosta? Mitä on puskureiden määrän vähentäminen vaikuttaisi tässä menetelmässä?

Jokaiselle solulle tarvitaan puskurisivu, joten hajautus voidaan tehdä 51 soluun. Tällöin S:n soluun osuu noin 4 sivullista ja R:n soluun noin 20 sivullista. Koska 4 sivullista voidaan hajauttaa keskusmuistissa puskuritilan puitteissa tarvitaan 3*(200+1000)+(n.40) levyoperaatiota 3640.
Yhteen pienemmän tiedoston soluun tulevien tietueiden täytyy kokoamisvaiheessa mahtua keskusmuistiin joten sqrt(200) on teorettinen alaraja puskureiden määrälle.

2 Tarkastellaan tehtävän 1 liitosta.

(a) Mikä olisi levyoperaatioiltaan tehokkain mahdollinen liitostapa ja kuinka paljon puskuritilaa sen käyttö vaatisi?

Tehokkain olisi sisäkkäiset silmukat tai hajautusliitos kun pienempi taulu voidaan ladata kokonaan keskusmuistiin. Operaatioita on tällöin 200+1000=1200 ja puskuritilaa tarvitaan 200+2 sivullista.

(b) Kuinka monta tulostietuetta liitos tuottaa vähintään ja enintään ja kuinka monta sivua pitää kirjoittaa levylle?

Koska b on S:n avain löytyy jokaiselle R:n riville enintään yksi pari, välttämättä ei yhtään, eli tuloksessa on 0-10000 riviä. Koska kumpiakin tietueita mahtui sivulle 10, mahtuu liitostuloksen tietueita vain 5 ja sivuja tulee 0-2000.

(c) Muuttuisiko minkään edellisen kohdan vastauksessasi, jos tietäisit, että R:n sarake a on viiteavain, jolle ei sallita tyhjäarvoja ja jonka kohteena on S.b?

Tulos on tällöin 10000 riviä ja sivuja 2000.

3. Seuraavan kaavion mukaisessa tietokannassa on informaatiota työntekijöistä, osastoista ja osastojen finanssitiedoista.

Emp(eid: integer,did: integer, sal: integer, hobby: char(2));
Dept(did: integer, dname: char(20), floor: integer, phone: char(10));
Finance(did: integer, budget: real, sales: real, expenses: real);

Tarkastellaan kyselyä:

SELECT D.dname, F.budget
FROM Emp E, Dept D, Finance F
WHERE E.did = D.did AND D.did = F.did AND D.floor = 1
AND E.sal >= 59000 AND E.hobby = 'yodeling';

(a) Piirrä kyselyä vastaava kyselypuu.

Hyvin suoraviivainen lähtötilannepuu:

(b) Optimoi kyselyä käyttäen luennoilla esiteltyjä sääntöjä ja piirrä optimoitu kyselypuu.

Valinnat alas, ristitulot liitoksiksi:

(c) Mitkä hakemistot tehostaisivat kyselyn suoritusta? Selvitä lyhyesti.

Emp.hobby voisi tehostaa. Pääavainhakemistot tauluille.

4. Tietokannasaa on tietoa tavaroista ja niiden toimittajista:

Suppliers(sid: integer, sname: char(20), city: char(20));
Supply(sid: integer ->Supplier, pid: integer->Parts);
Parts(pid: integer, pname: char(20), price: real);

Tarkastellaan kyselyä:

SELECT S.sname, P.pname
FROM Suppliers S, Parts P, Supply Y
WHERE S.sid = Y.sid AND Y.pid = P.pid AND
S.city = 'Madison' AND P.price <= 1,000;

Taulut on toteutettu järjestämättöminä peräkkäisrakenteina. Sivukoko on 4KB. Olkoon taululla Parts hajauttamalla toteutettu tiheä oheishakemisto sarakkeen pid perusteella ja taululla Supply hajauttamalla toteutetut tiheät oheishakemistot sarakkeiden pid ja sid perusteella. Oletetaan että toimittajia toimii 15 paikkakunnalla ja yli 2000 rahan hintaisia osia on 2% osista). Laadi suunnitelma kyselyn toteuttamiseksi.

Eräs mahdollinen suunnitelma alla. Ratkaisussa ei käytetä indeksejä.

5. Tarkastellaan tietokantakaaviota

Course(courseid: integer, name: char(40), taught_by:integer -> teacher, etc: char(200));
Material(courseid: integer->Course, bookid: integer ->Books);
Books(bookid: integer, name: char(40), etc: char(400));
Teacher(tid:integer, name:char(40),etc: char(200));

ja kyselyä SQL-kyselyä:

SELECT b.bookid,b.name, t.name
FROM Books b, Material m, Course c, teacher t
WHERE c.courseid = m.courseid AND b.name = 'Java Programming' AND
m.bookid = b.bookid and t.tid=c.taught_by;

Oletetaan, että taulussa Course on 6000 riviä. Material-taulussa on 12000 riviä ja Books-taulussa 24000 riviä. Books-taulun kirjoista on käytössä kursseilla n. 6000. Teacher taulussa on 2000 riviä. Sivukoko on 4KB.

(a) Arvioi kuinka monta riviä kysely palauttaa?

Tässä ei pystytä laskemaan vastauksen kokoa ilman lisäoletuksia. Jos oletetaan, että Java Programming -nimisiä kirjoja olisi kannassa 4 ja niistä yksi on käytössä kahdella kurssilla päädytään 2 riviin. Laskentaa voi lähteä tekemään muillakin järkevän tuntuisilla lähtötiedoilla (esim vain yksi tuon niminen kirja, joka olisi käytössä 3 kurssilla, yms.)

(b) Laadi kyselylle toteutussuunnitelma, kun taulut on tallennettu kasarakenteina ja niihin liittyvät tiheät B+ -puu hakemistot sarakkeille Course.name, Course.courseid, Material.courseid, Book.bookid ja Teacher.tid. Arvioi montako levyhakua tarvitaan? Voit olettaa laskelmissasi, että keskimääräinen hakemistotietueen koko kaikissa hakemistoissa on noin 20 tavua. Tee lisäoletuksia tarvittaessa.
Eräs mahdollisuus on alla olevassa kuvassa. Kirjan nimeen perustuva hakemisto tehostaisi tätä kyselyä oleellisesti.: