Tenttitehtävät 4. 9. 1995

1. Relaatiossa R olevat T_R monikkoa on pakattu B_R levyjaksoon ja relaatiossa S olevat T_S monikkoa B_S levyjaksoon. Johda lauseke karteesisen tulon R x S tulostekustannukselle.

2. Hajautustiedosto on organisoitu käyttämällä lineaarista hajautusta. Kuhunkin jaksoon mahtuu 2 tietuetta. Hajautusfunktio muodostetaan jakojäännösmenetelmällä. Tarkastele rakenteen muuttumista, kun alussa tyhjään rakenteeseen talletetaan avainarvoilla 12, 53, 5, 15, 2, 19, 43 varustetut tietueet tässä järjestyksessä.

3. Selvitä piirroksin, miten avain 17 poistetaan alla olevasta B-puusta, jossa kukin lehti voi sisältää 2-4 avainta ja kukin haarasolmu 2-4 viitta-osoitin -tietuetta. (Osa puun haaroista on korvattu alipuita kuvaavira kolmioilla; tyhjiä linkkejä ei ole merkitty.)

4. Tarkastellaan datalog-ohjelmaa

1. A (X, Y) :- F (X, Y),

2. A (X, Y) :- A (X, Z) & F(Z, Y),

3. query (X) :- A (X,"Paavo").

Tässä F on tietokantarelaatio (EDB-relaatio). Anna ohjelman säiintö-maaliverkko ja sen vahvasti yhtenäiset komponentit sekä niiden mukainen naiivi (tai puolinaiivi) kokoava laskenta-algoritmi. Algoritmin tulee sisältää sääntöjen laskemisessa tarvit-

tavat relaatioalgebran lausekkeet.

5. Tarkastellaan seuraavia tapahtumia:

T_0 : read(A);

read(B);

if A = 0 then B :=B + 1;

write(B).

T_1 : read(B);

read(A);

if B = 0 then A:= A + 1;

write(A).

tietokannassa on erityisehto A=0 V B = 0, kun alussa A = B = 0.

(a) Näytä, että mikä tahansa TO:n ja Tl:n sarjallinen suoritus säilyttää eheysehdon.

(b) Kirjoita T_0:n ja T_1:n sarjallistumaton rinnakkainen ajoitus.

(c) Lisää tapahtumiin lock- ja unlock-käskyt siten, että ne noudattavat 2-vaiheluki-

tusta ja selvitä, miten 2-vaihelukinta estää kohdan (b) epäsarjallistuvan ajoituksen.