Databasteknik II: Lösningar till tentamen 2008-03-29

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 (6 p)

ODBC, ESQL, JDBC och ADO.NET är fyra olika tekniker för att kommunicera med en relationsdatabas från ett vanligt program.

a) (4p)

Ange en stor fördel med var och en av dessa, jämfört med de andra.

b) (2p)

Om du personligen skulle skriva ett tillämpningsprogram som arbetar mot databasen i scenariot ovan, vilken av dessa tekniker skulle du välja? Utgå från din egen tillgång till verktyg, och egna kunskaper inom programmeringsspråk med mera. Motivera varför du valde just den tekniken.

Uppgift 2 (6 p)

En temporal databas är en databas som innehåller minst en tidsdimension. Man brukar tala om två olika tidsdimensioner, som man kan använda i databaser: giltighetstid och transaktionstid.

a) (2p)

Vad är skillnaden mellan giltighetstid och transaktionstid? Förklara, med tabellen Personer från scenariot som exempel.

b) (1p)

De flesta databashanteraren har inget inbyggt stöd för tidsdimensioner, utan om man behöver hantera tidsdimensioner måste man göra det i form av vanliga tabeller (om det nu är en relationsdatabas). Hur skulle man implementera giltighetstid i Personer-tabellen?

c) (1p)

Hur skulle man implementera transaktionstid i Personer-tabellen?

d) (2p)

Visa med exempel från scenariodatabasen vilka problem med referensintegritet som man kan få, när man lägger till tidsdimensioner.

Uppgift 3 (6 p)

I en databashanterare körs fyra olika transaktioner (T1, T2, T2 och T4) enligt följande tidsschema. Transaktionerna arbetar med tre olika dataobjekt (X, Y och Z).

Tid T1 T2 T3 T4
1Start    
2Läs(X)    
3Skriv(X)    
4Commit    
5 Start   
6  Start  
7    Start
8 Läs(X)   
9 Läs(Y)    
10    Läs(Z)
11    Läs(X)  
12    Läs(Y) 
13 Skriv(X)   
14    Skriv(Y) 
15  Commit  
16 Commit   
17     Skriv(Z)
18     Commit

a) (2p)

Här användes ingen metod för att hålla transaktionerna isolerade från varandra. Vilket eller vilka fel kan ha uppstått i databasen på grund av detta?

b) (4p)

Välj någon av metoderna för isolering av transaktioner, förklara kort hur metoden fungerar, och visa hur tidsschemat ovan skulle förändras om den metoden användes.

Uppgift 4 (6 p)

Tabellen Personer i scenariot har 1 miljon rader. Pid är en nyckel. Här är en SQL-fråga som tar fram namn och adress på den person som har Pid 4711:
select Namn, Adress
from Personer
where Pid = 4711;
Gör rimliga antaganden om blockstorlek mm, och räkna ut hur lång tid det i genomsnitt tar att köra denna fråga, om tabellen är lagrad:

a) utan något index (eller annan sökväg) på Pid

b) med ett primärindex i form av ett B+-träd på Pid

c) med ett sekundärindex i form av ett B+-träd på Pid

Här är en SQL-fråga som tar fram namn och adress på de personer som Thomas Padron-McCarthy:

select Namn, Adress
from Personer
where Namn = 'Thomas Padron-McCarthy';
Med samma antaganden om blockstorlek mm som ovan, hur lång tid tar det i genomsnitt att köra denna fråga, om tabellen är lagrad:

d) utan något index (eller annan sökväg) på Namn

e) med ett sekundärindex i form av ett B+-träd på Namn

Ange antagandena, och visa hur du räknat!

Uppgift 5 (6 p)

(Klicka på bilderna för att se dem i större format.)

a) (1p)

Ett relationsalgebrauttryck

b) (1p)

Ett o-optimerad frågeträd

c) (4p)

Vi börjar med att dela upp selektionen i flera, och "trycker ner" varje del så långt det går i frågeträdet:

Ett steg i optimeringen av frågeträdet

Vi gör om varje kartesisk produkt som följs av en (lämplig) selektion, till en join:

Ett steg i optimeringen av frågeträdet

För att slippa onödiga kolumner i delresultaten kan man lägga in projektioner. Här låter vi varje selektion och join följas av en sådan projektion, eftersom vi ändå går igenom alla raderna då. Däremot lägger vi inte in några projektioner direkt på de ursprungliga tabellerna, för arbetet med att gå igenom alla raderna och göra en extra operation är förmodligen mer än vad vi tjänar på att ha färre kolumner (men lika många rader) i de direkt efterföljande operationerna.

Ett optimerat frågeträd

Uppgift 6 (6 p)

(Klicka på bilderna för att se dem i större format.)

a) (2p)

Antal rader i det o-optimerade frågeträdet

b) (1p)

Antal rader i det optimerade frågeträdet

c) (3p)

Vilka saker finns i det optimerade uttrycket som en kostnadsbaserad frågeoptimerare (eller en heuristisk optimerare som bryr sig om datamängder och lagringsstrukturer) skulle kunna gjort bättre? (Alternativt, ifall det redan råkat bli helt perfekt, vad kunde den heuristiska optimeraren ha missat?)

Uppgift 7 (6 p)

Beskriv två olika algoritmer för att utföra join-operationen.
Vilken av dem är snabbast?
Varför använder man inte alltid den, om den nu är snabbast?

Uppgift 8 (6 p)

Vi gör om exempeldatabasen till i en distribuerad databas. Visa följande med exempel från tabellen Person:

a) (1p)

hur ett fragementeringsschema kan se ut

b) (1p)

hur rekonstruktionsprogrammet (även kallat återskapandeprogrammet) ser ut, givet fragementeringsschemat ovan

c) (2p)

hur en global fråga kan lokaliseras genom att globala relationer ersätts med med sina rekonstruktionsprogram

d) (2p)

hur detta relationsalgebrauttryck kan förenklas genom att man reducerar bort tomma deluttryck

Observera: Välj ut och besvara (högst) sju av åtta uppgifterna. (Skulle du svara på alla åtta, räknas den med högst poäng bort.)


.........................................

Uppgift 1 (6 p)

a) (1p) ODBC

ODBC. Står för Open Database Connectivity. En metod att låta program kommunicera med varandra med hjälp av SQL-frågor, och skicka data till varandra. Normalt är det ett applikationsprogram som kommunicerar med en databashanterare. Man lägger in SQL-satser i ett program skrivet i C eller C++. ODBC kommer från Microsoft men är en öppen standard och fungerar på många olika system och med många olika databashanterare. Nästan alla relationsdatabashanterare erbjuder möjligheter att ansluta till dem via ODBC. Man kan byta databashanterare genom att byta ODBC-drivrutin, vilket inte påverkar tillämpningsprogrammets källkod.

b) (1p) ESQL

ESQL, Embedded SQL. "Inbäddad SQL". En variant av SQL som är avsedd att stoppas in i ett program, kallat "värdprogram", skrivet i ett konventionellt programmeringsspråk som C eller Ada. På det viset kan man anropa en databashanterare från programmet. Embedded SQL är standardiserat, och gör det möjligt att lägga in SQL-satser i programmet på ett mer integrerat sätt än med vanliga CLI-API:er som ODBC. Man skriver SQL-koden mitt bland den vanliga C-koden, men markerad med orden EXEC SQL. EXEC SQL-satserna översätts sen av en preprocessor till C-kod, huvudsakligen funktionsanrop, som kan kompileras med en vanlig C-kompilator.

c) (1p) ADO.NET

ADO.NET. En uppsättning klasser i Microsofts .NET-miljö som kan användas för att låta ett program hantera data och kommunicera med databaser och andra datakällor.

d) (2p) Vilka är de största skillnaderna mellan ODBC och ADO.NET?

Uppgift 2 (4 p)

Giltighetstid, som anger när uppgifterna i databasen var giltiga i verkligeheten, till exempel att en viss abonnent fick ett visst telefonnummer 12 juni 2006, och abonnemanget avslutades 22 mars 2007.

I en relationsdatabas utanm inbyggt stöd för tidsdimensionen giltighetstid lägger man till två kolumner, ofta kallade VST (Valid Start Time) och VET (Valid End Time):

AbonnentnummerNamnAdressTelefonnummerVSTVET
1 Klas Vägen 3112590 13 mars 199212 juni 2006
1 Klas Vägen 32112590 12 juni 2006null
2 Lotta Torget 1113239 20 december 1993null

Transaktionstid, som anger när uppgifterna gällde i databasen, eller "vad databasen vid ett visst tillfälle trodde om verkligheten", till exempel att 24 mars 2007 la man in i databasen att en viss person hade en viss adress, men 27 mars 2007 ändrade man adressen, eftersom man kommit på att den först inlagda adressen var felaktig. (Inget hade ändrats ute i verkligheten, utan det var bara en ändring i databasen.)

Med transaktionstid tas aldrig några data bort fysiskt ur databasen, utan alla gamla felaktiga uppgifter finns kvar, men markerade som att de inte längre gäller.

I en relationsdatabas utanm inbyggt stöd för tidsdimensionen transaktionstid lägger man till två kolumner, ofta kallade TST (Transaction Start Time) och TET (Transaction End Time):

AbonnentnummerNamnAdressTelefonnummerTSTTET
1 Klas Blägen 32112590 23 mars 200727 mars 2007
1 Klas Vägen 32112590 27 mars 2007null
2 Lotta Torget 1113239 25 mars 2007null

Uppgift 3 (3 p)

I "objektorienterade databaser", ibland kallade "första generationens objektorienterade databaser", har har man tagit ett objektorienterat språk, som C++ eller Smalltalk, och lagt till databasfunktionalitet som persistens (att objekten finns kvar mellan programkörningar), transaktionshantering, och kanske ett (ganska primitivt) frågespråk.

I objekt-relationella databaser, ibland kallade "andra generationens objekt-orienterade databaser", har man i stället tagit en databashanterare, med all dess funktionalitet, och sen lagt till en objektorienterad datamodell med klasser, arv, objekt och kanske metoder. Det kan antingen vara en nyutvecklad databashanterare, som använder sig av en en helt objektorienterad datamodell (till exempel forskningssystemet Amos), med det kan också vara en relationsdatabashanterare där man, förutom relationsfunktionaliteten, lagt till möjligheter för objektorientering (till exempel nyare versioner av Oracle).

De objekt-relationella databaserna har därför mer databasfunktionalitet i form av deklarativt frågespråk, med mera, och fungerar mer likt en traditionell (relations-)databashanterare. Den objekt-relationella databasen blir mer dataoberoende (till följd av det deklarativa frågespråket), och därför blir det inte bara lättare att skriva frågor, utan också lättare att ändra i schemat.

Uppgift 4 (5 p)

Förklara kort följande termer:

a) datautvinning ("data mining")

Analyser av en databas eller ett datalager för att hitta samband och trender i datamängden. Ofta är datat insamlat för andra ändamål än datautvinning. Oftast menar man att analysen utförs med någon typ av automatiska verktyg. Brukar kräva komplexa frågor över väldigt stora mängder data.

b) datalager ("data warehouse")

En sorts databas (fast man kallar den datalager i stället för databas) som är avsedd för analyser (se datautvinning) snarare än enskilda sökningar. Innehåller stora mängde data, som kan ha överförts från de vanliga databaser som är avsedda för den dagliga driften i företaget eller organisationen. Uppdateras mer sällan än en vanlig databas, och kan hanteras med annan programvara och organiseras efter andra datamodeller.

c) dimensionsdatabas ("dimensional database")

En databas som organiserats enligt dimensionsmodellen, som är en datamodell som är vanlig i datalager. Det är inte en vanlig relationsdatabas med tabeller och godtyckliga kopplingar mellan dem, utan data betraktas som en kub med flera dimensioner. Dimensionerna kan vara till exempel tid, pris, varuslag eller ort.

d) faktatabell

Om en dimensionsdatabas ska lagras med en relationsdatabashanterare, lagras cellerna i datakuben i en faktatabell, och varje rad representerar en cell i datakuben. På raden finns dels de data som finns i cellen, och dessutom värdena på de olika dimensionerna för den cellen.

e) dimensionstabell

Om en dimensionsdatabas ska lagras med en relationsdatabashanterare, representeras varje dimension i datakuben av en dimensionstabell. Varje värde som kan förekomma på en dimension representeras som en rad i den motsvarande dimensionstabellen. Det kan vara fördelaktigt att inte normalisera dimensionstabellerna enligt tredje normalformen.

Uppgift 5 (4 p)

Det viktiga här är att:

Flera olika exempel, med två objekt (X och Y) och två transaktioner (T1 och T2):

Först visar vi ett exempel med (samtidiga) läslås på samma objekt:

Tid T1 T2 Kommentar
1 LäsLås(X), ok T1 skaffar sig ett läslås på X
2 Läs(X) T1 läser X
3 LäsLås(X), ok Nu har både T1 och T2 läslås på X
4 Läs(X)
5 Läs(X)
6 LåsUpp(X)
7 LåsUpp(X) Nu finns inga lås kvar

Ett exempel med ett skrivlås, som visar att man inte kan skrivlåsa ett objekt som en annan transaktion har ett (läs- eller skriv-)lås på. Skrivlås måste vara exklusiva, dvs det enda låset på objektet.

Tid T1 T2 Kommentar
1 LäsLås(X), ok T1 skaffar sig ett läslås på X
2 Läs(X)
3 SkrivLås(X)... T2 försöker skrivlåsa X, men måste vänta...
4 Läs(X)
5 LåsUpp(X) Nu släppte T1 sitt läslås...
6 ...ok ...och då kunde T2 få sitt skrivlås
7 Läs(X) Skrivlås innebär normalt att man också får läsa
8 Skriv(X)
9 LåsUpp(X) Nu finns inga lås kvar

Ett exempel till med ett skrivlås, som visar att man inte kan läslåsa ett objekt som en annan transaktion har ett skrivlås på. Skrivlås måste fortfarande vara exklusiva.

Tid T1 T2 Kommentar
1 SkrivLås(X), ok T1 skaffar sig ett skrivlås på X
2 Läs(X) Skrivlås innebär normalt att man också får läsa
3 Skriv(X)
4 LäsLås(X)... T2 försöker låsa, men måste vänta...
5 Skriv(X)
6 LåsUpp(X) Nu släppte T1 sitt skrivlås...
7 ...ok ...och då kunde T2 få sitt läslås
8 Läs(X)
9 LåsUpp(X) Nu finns inga lås kvar

Ett exempel med flera objekt, som visar de två faserna i tvåfaslåsning:

Tid T1 T2 Kommentar
1 LäsLås(X), ok T1 skaffar sig ett läslås på X
2 Läs(X) Sen är T1 klar med X, men låser inte upp låset!
3 LäsLås(X)... T2 försöker låsa, men måste vänta...
4 SkrivLås(Y), ok T1 skaffar sig ett skrivlås på Y
5 Skriv(Y)
6 LåsUpp(X) Först nu låser T1 upp X, och har därmed gått över i upplåsningsfasen
7 ...ok T2 får sitt läslås
8 Läs(X)
9 LåsUpp(X) Nu har även T2 gått över i upplåsningsfasen
10 LåsUpp(Y)
11 LäsLås(Y), ok Så får man inte göra! T2 har ju redan låst upp ett lås.

Ett exempel med uppgradering från läslås till skrivlås:

Tid T1 T2 Kommentar
1 LäsLås(X), ok
2 Läs(X)
3 LäsLås(X), ok Nu har både T1 och T2 läslås på X
4 Läs(X)
5 Läs(X)
6 SkrivLås(X)... T1 försöker uppgradera sitt lås, men måste vänta...
7 Läs(X)
8 LåsUpp(X) Nu släppte T2 sitt läslås...
9 ...ok ...och då kunde T1 få sitt skrivlås
10 Skriv(X)
11 LåsUpp(X) Nu finns inga lås kvar

Ett exempel till, bara för att visa att två olika objekt kan vara skrivlåsta samtidigt:

Tid T1 T2 Kommentar
1 SkrivLås(X), ok
2 SkrivLås(Y), ok Två olika objekt kan vara (skriv-)låsta samtidigt
3 Skriv(X)
4 Skriv(Y)
5 LåsUpp(X)
6 LåsUpp(Y) Nu finns inga lås kvar

Uppgift 6 (6 p)

Antaganden:

Vi antar att både heltal och flyttal lagras som 64 bitar (8 byte). En rad i tabellen kräver 5 * 8 byte, dvs 40 byte. Hela tabellens data blir 4 * 1014 byte, dvs 400000 gigabyte (med decimal-giga) eller 400 terabyte. (Så stora diskar finns inte idag, men om några år. Idag får vi dela upp databasen på ungefär tusen fysiska hårddiskar, men om vi inte läser parallellt från dem spelar det ingen roll för beräkningen.)

För att göra det lätt för oss att räkna antar vi att (logiska) diskblock är på 40 kilobyte, och att det går in 1000 dataposter i ett block (plus lite administrativ information). Blockningsfaktorn är alltså 1000, och det behövs 10 miljarder datablock, dvs 1010 stycken.

Vi räknar med att det tar 10 millisekunder att läsa ett godtyckligt diskblock, och 1 millisekund att läsa block som ligger i följd, vilket blocken i datafilen gör. (I synnerhet den andra tidsuppskattningen är nog väl pessimistisk.)

a) Utan index.

Det står inget om att id är deklarerad som nyckel, så vi antar att vi måste läsa alla posterna. Det finns 1010 block som ligger i följd, så varje läsning tar 1 millisekund, vilket ger 107 sekunder (knappt 4 månader).

Svar: 4 månader.

Alternativt, och kanske mer realistiskt, räknar vi så här: En modern SATA-disk kan överföra 300 megabyte per sekund. Om vi läser för fullt från disken tar det (4 * 1014) / (300 * 106) sekunder att läsa hela datamängden, dvs 1.33 * 106 sekunder, eller 15 dygn.

Ännu ett alternativ är att räkna med de där tusen diskarna ovan, och att databashanteraren faktiskt är smart nog att läsa parallellt från allihop, och att hårdvaran i övrigt gör det möjligt att läsa med full fart parallellt från tusen diskar. Då kan vi få ner tiden till en tusendel, dvs 22 minuter.

b) Med ett sekundärindex i form av ett B+-träd.

Vi antar att diskblockspekare är 8 byte (det räcker inte med 32-bitarspekare!), och att även indexblocken är 40 kilobyte. Ett indexblock kan då innehålla (40*1024-8)/(8+8)+1 = 2560 pekare till subträd. Det blir jobbigt, så vi antar i stället att indexblockens storlek är 16 kilobyte, vilket ger 1000 pekare till subträd.

Om man räknar med att indexet byggts upp dyamiskt, dvs allteftersom vi la in rader i tabellen, blir indexblocken inte fullpackade, och man bör räkna med en effektiv ordning på 2/3 av trädets verkliga ordning. För enkelhets skull tänker vi oss nu att man skapade indexet efter att tabellen fyllts, och att databashanteraren då fyllde indexblocken helt fulla.

Eftersom det är ett sekundärindex, behövs på indexets lägsta nivå en pekare till varje post i datafilen, vilket är 1013 stycken. Med 1000 pekare i varje block, behövs 1010 indexblock på lägsta indexnivån. På nästa nivå, den andra, behövs 107 indexblock. På nästa nivå, den tredje, behövs 104 indexblock (10000 stycken). På nästa nivå, den fjärde, behövs 101 indexblock (10 stycken). På nästa nivå, den femte, behövs ett enda indexblock, som blir rotblocket. Indexet innehåller alltså fem nivåer (inklusive rotblocket).

Alternativt räknar vi ut djupet på indexträdet genom att beräkna 1000-logaritmen för 1013, vilket är 4.33. Vi avrundar uppåt, och får indexdjupet 5.

Om vi antar att det bara finns ett enda sandkorn med id 1000000, krävs sex diskläsningar (fem indexblock plus datablocket), där varje diskläsning tar 10 millisekunder. Total tid alltså 60 millisekunder (0.06 sekunder).

Svar: 0.06 sekunder.

Uppgift 7: Relationsalgebra, frågeexekvering, frågeoptimering (15 p)

a) (2p)

PROJECTAnr, Pnamn(SELECTAP.P = P.Pnr and A.Lön > 30000 and P.Adress = "Gnesta" (A x AP x P))

(PROJECT ska egentligen vara grekiska bokstaven lilla pi, och SELECT ska egentligen vara grekiska bokstaven lilla sigma.) Frågan finns också uppritat som ett träd här nedan.

b) (1p)

Med materialiserade mellanresultat räknas varje mellanresultat ut och lagras i sin helhet (förmodligen på disk), innan det kan användas i efterföljande operationer. Operationerna utförs en i taget, utan någon parallellitet.

Med strömmande mellanresultat skickas tupler från en operation vidare till nästa operation så fort de producerats, så att flera operationer kan utföras parallellt. (Det behöver inte nödvänidgtvis förekomma någon parallellitet, vare sig äkta med flera processorer eller falsk med trådar som körs omväxlande, utan det kan fungera så att operationerna körs växelvis, till exempel genom att en operation efterfrågar tupler från en föregående operation, och då överlåter kontrollen till den så att den kan producera en eller flera tupler.)

c) (2p)

Nej, för mellanresultatet från de tre kartesiska produkterna blir mycket stort (miljarder rader). Om detta mellanresultatet ska materialiserats, tar det lång tid att producera och lagra, stort lagringsutrymme på disken, och sedan lång tid att läsa och bearbeta. Om det i stället strömmas, slipper vi tiden och utrymmet för lagringen, men det tar fortfarande lång tid att producera, och lång tid för de efterföljande operationerna att bearbeta det.

d) (1p)

En fråga i ett deklarativt frågespråk som SQL kan inte köras direkt, utan måste först översättas till en procedurell form, en så kallad exekveringsplan. En och samma deklarativa fråga kan normalt översättas till många olika möjliga exekveringsplaner, som alla ger samma resultat, men som kan variera kraftigt i effektivitet. Normalt betyder "effektivitet" i det här sammanhanget helt enkelt tiden det tar att köra exekveringsplanen. Frågeoptimering går ut på att välja en effektiv exekveringsplan.

e) (1p) Vad innebär heuristisk optimering?

Optimeraren använder några ganska enkla regler för hur man gör en effektiv exekveringsplan, till exempel att selektion bör utföras före join, eller att kartesiska produkter bör undvikas.

f) (5p)

Optimeraren utgår från den ooptimerade relationsalgebrarepresentationen av frågan:

Frågeträdet för den ooptimerade frågan

Vi delar upp villkoret i selektionsoperationen i flera, för att senare kunna flytta runt dem:

Frågeträdet med uppdelad selektion

Vi trycker ner varje selektionsoperation så långt det går i trädet:

Frågeträdet med nedtryckta selektioner

Där det går kombinerar vi en kartesisk produkt följd av en selektion till en join:

Frågeträdet med joinar

Vi trycker ner projektioner så långt det går i trädet:

Frågeträdet med nedtryckta projektioner

En del av dessa projektioner gör inget, eller är förmodligen onödiga, så dem tar vi bort:

Frågeträdet med en del borttagna projektioner

Om den usrpungliga frågan formulerats med tabellerna i ordningen A, P, AP i stället för A, AP, P, hade vi behövt ändra ordningen på de kartesiska produkterna från A X P X AP till exempelvis A X AP X P för att kunna åstadkomma joinen mellan A och AP.

Man vill också utföra den mest restriktiva selektionen först. Om optimeraren antar att en selektion med likhetsvillkor (Adress="Gnesta") är mer restriktiv än en storleksjämförelse (Lön>30000), så kan den ändra ordningen på de kartesiska produkterna från A X AP X P till P X AP X A.

g) (1p)

En kostnadsbaserad frågeoptimerare har en kostnadsfunktion, som givet en ekeveringsplan räknar ut den förväntade kostnaden för att köra den. Normalt betyder "kostnad" i det här sammanhanget helt enkelt tiden det tar att köra exekveringsplanen. Kostnadsfunktionen kan ta hänsyn till olika algoritmer för att utföra en operation, till vilka index som finns, och till statistik om innehållet i databasen. Den kostnadsbaserade frågeoptimeraren jämför den förväntade kostnaden (enligt kostnadsfunktionen) för olika exekveringsplaner (antingen för alla som är möjliga, eller för ett urval av dem), och väljer den billigaste.

Till skillnad från (normal) heuristisk optimerare kan en kostnadsbaserad optimerare ta hänsyn till olika algoritmer för att utföra operationer som join, till vilka index som finns, och till statistik om innehållet i databasen. Det gör att den kan generera bättre (dvs mer effektiva) exekveringsplaner. Den är å andra sidan mer komplicerad än en heuristisk optimerare, vilket gör att den blir svårare att implementera och även mer tidskrävande (för själva optimeringen).

h) (2p)

En kostnadsbaserad frågeoptimerare kan generera bättre (dvs mer effektiva) exekveringsplaner än en heuristisk optimerare. Den är å andra sidan mer komplicerad än en heuristisk optimerare, vilket gör att den blir svårare att implementera och även mer tidskrävande (för själva optimeringen).


Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) 17 mars 2008