Databaskonstruktion: Lösningar till tentamen 2005-05-28

Observera att detta är förslag på lösningar. Det kan finnas andra lösningar som också är korrekta, och det kan hända att en del av lösningarna är mer omfattande än vad som krävs för full poäng på uppgiften. En del av lösningarna är kanske inte fullständiga, utan hänvisar bara till var man kan läsa svaret.

Uppgift 1 (4 p)

create table sokord
(id integer not null,
ord varchar(40) not null,
primary key (id),
unique (ord));

create table webbsida
(id integer not null,
adress varchar(200) not null,
primary key (id),
unique (adress));

create table finns
(sokord integer not null,
webbsida integer not null,
primary key (sokord, webbsida),
foreign key (sokord) references sokord(id),
foreign key (webbsida) references webbsida(id));

Alternativ syntax:

create table sokord
(id integer not null primary key,
ord varchar(40) not null unique);

create table webbsida
(id integer not null primary key,
adress varchar(200) not null unique);

create table finns
(sokord integer not null references sokord(id),
webbsida integer not null references webbsida(id),
primary key (sokord, webbsida));

Några exempeldata:

insert into sokord values (1, 'apa');
insert into sokord values (2, 'bil');
insert into sokord values (3, 'Cecilia');
insert into sokord values (4, 'flogiston');
insert into sokord values (5, 'struts');
insert into sokord values (6, 'svamp');
insert into sokord values (7, 'Zorro');
insert into sokord values (8, 'och');
insert into sokord values (9, 'universitet');

insert into webbsida values (1, 'www.apbil.se');
insert into webbsida values (2, 'www.zorrosvamp.se');
insert into webbsida values (3, 'www.ingenting.se');
insert into webbsida values (4, 'www.flogiston.se');
insert into webbsida values (5, 'www.flogistonstruts1.se');
insert into webbsida values (6, 'www.flogistonstruts2.se');
insert into webbsida values (7, 'www.struts.se');
insert into webbsida values (8, 'http://www.oru.se/');

insert into finns values (1, 1);
insert into finns values (2, 1);
insert into finns values (6, 2);
insert into finns values (7, 2);
insert into finns values (4, 4);
insert into finns values (4, 5);
insert into finns values (5, 5);
insert into finns values (4, 6);
insert into finns values (5, 6);
insert into finns values (5, 7);
insert into finns values (9, 8);

insert into finns values (8, 1);
insert into finns values (8, 2);
insert into finns values (8, 5);
insert into finns values (8, 6);
insert into finns values (8, 7);
insert into finns values (8, 8);

Uppgift 2 (10 p)

a (1p)

Som en flat fråga, dvs utan någon underfråga i where-villkoret:

select webbsida.adress
from sokord, finns, webbsida
where sokord.id = finns.sokord
and finns.webbsida = webbsida.id
and sokord.ord = 'flogiston';

Alternativt kan man skriva frågan med nästlade underfrågor i where-villkoret:

select adress
from webbsida
where id in (select webbsida
             from finns
             where sokord in (select id
                              from sokord
                              where ord = 'flogiston'));

b (1p)

Det här är enklast med en nästlad fråga. Byt ut id in i a mot id not in:

select adress
from webbsida
where id not in (select webbsida
                 from finns
                 where sokord in (select id
                                  from sokord
                                  where ord = 'flogiston'));

Det är svårt att ställa den här typen av "finns inte"-frågor utan underfrågor. Följande försök är fel, och ger i stället alla webbsidor som innehåller åtminstone något ord som inte är flogiston:

select webbsida.adress
from sokord, finns, webbsida
where sokord.id = finns.sokord
and finns.webbsida = webbsida.id
and sokord.ord <> 'flogiston';

c (1p + 1p)

select adress
from webbsida
where id in (select webbsida
             from finns
             where sokord in (select id
                              from sokord
                              where ord = 'flogiston'))
  and id in (select webbsida
             from finns
             where sokord in (select id
                              from sokord
                              where ord = 'struts'));

Notera att vi söker efter två olika ord (flogiston och struts), och då måste vi söka två gånger i tabellerna sokord och finns. I lösningen ovan gör vi det med två separata underfrågor i where-villkoret, men om man vill skriva frågan utan underfrågor måste man ha två olika alias för såväl sokord som finns:

select adress
from webbsida, finns as f1, sokord as s1,
               finns as f2, sokord as s2
where webbsida.id = f1.webbsida and f1.sokord = s1.id and s1.ord = 'flogiston'
and webbsida.id = f2.webbsida and f2.sokord = s2.id and s2.ord ='struts';

Ett vanligt fel: Skriv inte en fråga som kräver att samma ord samtidigt är lika med både flogiston och struts, som till exempel det här felaktiga försöket:

select adress
from webbsida, finns, sokord
where webbsida.id = finns.webbsida and finns.sokord = sokord.id
and sokord.ord = 'flogiston'
and sokord.ord = 'struts';

Den frågan ger förstås alltid noll rader i svaret, eftersom samma ord aldrig samtidigt kan vara lika med både flogiston och struts.

d (1p)

Byt ut and id in i c mot or id in:

select adress
from webbsida
where id in (select webbsida
             from finns
             where sokord in (select id
                              from sokord
                              where ord = 'flogiston'))
  or id in (select webbsida
             from finns
             where sokord in (select id
                              from sokord
                              where ord = 'struts'));

e (1p)

Byt ut and id in i c mot and id not in:

select adress
from webbsida
where id in (select webbsida
             from finns
             where sokord in (select id
                              from sokord
                              where ord = 'flogiston'))
and id not in (select webbsida
               from finns
               where sokord in (select id
                                from sokord
                                where ord = 'struts'));

f (1p)

select sokord.ord
from sokord, finns, webbsida
where sokord.id = finns.sokord
and finns.webbsida = webbsida.id
and webbsida.adress = 'http://www.oru.se/';

eller

select ord
from sokord
where id in (select sokord
             from finns
             where webbsida in (select id
                               from webbsida
                               where adress = 'http://www.oru.se/'));

g (1p)

select ord
from sokord
where id not in (select sokord
                 from finns);

h (2p)

create view ordantal(sokord, antal) as
select sokord, count(*)
from finns
group by sokord;

select ord from sokord
where id = (select sokord from ordantal
            where antal = (select max(antal) from ordantal));

Uppgift 3 (3 p)

För att bestämma vilka index som behövs, måste man veta vilka frågor som ska köras. Vi antar att det är frågor som de i uppgift 2 som kommer att användas.

Skapa följande index:

create index si on sokord(id);
create index so on sokord(ord);
create index wi on webbsida(id);
create index wa on webbsida(adress);
create index fs on finns(sokord);
create index fw on finns(webbsida);

webbsida.adress är en bred textkolumn, så där skulle man kanske inte vilja ha ett index, men å andra sidan är det en stor tabell, så det blir långsamt att söka utan index.

Om man i stället (kanske mer realistiskt) antar att frågor som a-e är de vanligaste, och f-h inte behöver beaktas, ska webbsida.adress inte ha något index. Den kolumnen används ju i så fall inte i sökningar, bara i resultatet.

Motivering: Man bör skapa index på de kolumner som används i sökningar, vilket ungefär betyder i jämförelser i where-villkoren. Nästlade fågor bör "flatas ut" i analysen. Till exempel är en fråga som

select A1 from A where A2 in (select B1 from B)

ekvivalent (bortsett från dubbletter i svaret) med

select A.A1 from A, B where A2 = B1

vilket visar att både A.A2 och B.B1 används i jämförelsen, även om det kanske inte syns så tydligt i den nästlade frågan. (Inget poängavdrag om man missat detta.)

Uppgift 4 (2 p)

Alternativet hade varit att låta ordet självt (attributet Ord på entitetstypen Sökord) respektive webbsidans adress (attributet Adress på entitetstypen Webbsida) vara primärnycklar, och alltså refererat till dessa från tabellen finns:

create table sokord
(ord varchar(40) not null,
primary key (ord));

create table webbsida
(adress varchar(200) not null,
primary key (adress));

create table finns
(sokord integer not null,
webbsida integer not null,
primary key (sokord, webbsida),
foreign key (sokord) references sokord(ord),
foreign key (webbsida) references webbsida(adress));

Tabellen finns kommer därför att ta mycket plats, och på grund av de stora datamängderna blir sökningar långsamma.

Antag att det finns en miljard (10⁹) webbsidor, som var och en innehåller tusen ord. Då finns det en biljon (10¹²) rader i finns-tabellen. Med de numeriska id-nycklarna är varje värde kanske fyra byte stort (32 bitar), vilket ger att tabellen tar upp (4+4)*10¹² byte, dvs 8000 gigabyte eller 8 terabyte. (Viss overhead tillkommer.) De största hårddiskar jag hittar just nu är på 400 gigabyte, och det går alltså åt 20 sådana för att lagra tabellen.

Om orden och adresserna ska vara med i finns-tabellen, och vi antar att ett ord är i genomsnitt 10 tecken långt, och en webbadress 100 tecken, tar tabellen upp (10+100)*10¹² byte, dvs 110000 gigabyte eller 110 terabyte. (Viss overhead tillkommer.) Då går det åt 275 stycken 400-gigabytes-hårddiskar.

Indexen som vi skapas (automatiskt eller med create index-kommandon) på de två kolumnerna i finns kommer att växa i storlek på liknande sätt.

Det kan också vara krångligare att arbeta med textsträngar än med heltal i ett program som ska arbeta mot databasen, som PHP på en webbsida.

En fördel med lösningen är dock att man kan klara sig med en enda tabell, finns, eftersom den innehåller all information man behöver!

Uppgift 5 (5 p)

a (2p)

Lägg bara till ett attribut Antal på sambandstypen Finns:

ER-diagram med attributet Antal på sambandstypen Finns

Attributet ska sen också finnas med i tabellen finns:

create table finns
(sokord integer not null,
webbsida integer not null,
antal integer,
primary key (sokord, webbsida),
foreign key (sokord) references sokord(id),
foreign key (webbsida) references webbsida(id));

b (3p)

Det finns flera olika möjligheter:

Man kan göra om sambandstypen Finns till en entitetstyp, som kan kallas Förekomst. Den har en egen nyckel, den har ett attribut som anger radnummer, och den är kopplad både till Sökord och Webbsida med N:1-sambandstyper.
Man kan göra om Finns till en svag entitetstyp, med både Sökord och Webbsida som identifierande sambandstyper och radnumret som partiell nyckel.
Man kan ha ett flervärt attribut Radnummer på sambandstypen Finns.

Endast den första lösningen låter ett ord förekomma flera gånger på samma rad på en webbsida.

Den tredje lösningen är förmodligen enklast. Så här ser ER-diagrammet ut:

ER-diagram med ett flervärt attribut Antal på sambandstypen Finns

Tabellen finns ser likadan ut som ursprungligen, men det tillkommer en tabell radnummer som implementerar det flervärda attributet:

create table radnummer
(sokord integer not null,
webbsida integer not null,
radnummer integer not null,
primary key (sokord, webbsida, radnummer),
foreign key (sokord) references sokord(id),
foreign key (webbsida) references webbsida(id));

Uppgift 6 (4 p)

CGI
ASP, PHP eller annat integrerat skripspråk, med SQL-frågor
SQL-frågor direkt i HTML-koden på servern, som i Roxen
Någon lösning som kräver särskild programvara på klienten, till exempel en Java-applet som kopplar upp sig mot databashanteraren med JDBC

Uppgift 7 (4 p)

Som exempel:

Microsoft Access. Nej, inte avsedd för så stora datamängder och så tung belastning.
Microsoft SQL Server. Ja, det kan fungera.
DB2 från IBM. Ja, det kan fungera.
Oracle. Ja, det kan fungera.
Mimer. Ja, det kan fungera.
MySQL. Ja, det kan fungera.
ObjectStore. Nej, den är inte en relationsdatabashanterare.
Linux. Nej, Linux är ingen databashanterare, utan ett operativsystem.
En egenutvecklad speciallösning. Kan bli nödvändigt, om Gurgel vill indexera hela webben med alla dess miljarder sidor (vilket ger en mycket stor databas) och användas av människor i hela världen (vilket ger hård belastning).

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) 4 juni 2005