Databasteknik II: Inlämningsuppgift 7 - Frågeoptimering i Amos II

Mål

Att förstå mer om hur en kostnadsbaserad frågeoptimerare fungerar.
Att förstå dynamisk programmering, som är en algoritm som gör uttömmande sökning i sökrymden av exekveringsplaner, men inte bryr sig om att undersöka planer som den vet är långsammare.

Lisp

Lisp är enkelt. Här är grunderna:

Alla funktionsanrop skrivs som listor, som man skriver med hjälp av parenteser. I stället för
sin(x)
för att räkna ut sinus av x, skriver man
(sin x).
I stället för
pow(x, 3)
skriver man
(pow x 3).
Notera att det inte behövs några kommatecken.
Alla operationer är funktionsanrop. I stället för
2 + 3
med infix plus-operator, tänker man sig att man anropar funktionen +, så här:
+(2, 3).
Men det är ju Lisp, så det anropet skrivs som en lista:
(+ 2 3).
Tips: Man kan skriva
(+ 2 3 4 5 6).
Lisp har ingen operatorprioritet. I stället för
2 * 3 + 4 * 5,
som ju ska räknas ut som
(2 * 3) + (4 * 5),
skriver man
(+ (* 2 3) (* 4 5)).
Även kontrollstrukturer som if skrivs som funktionsanrop i form av listor: I stället för
if (a < b) f(a); else g(a, b, c);
skriver man
(if (< a b) (f a) (g a b c))).
Variabeltilldelningar skrivs inte med = utan med funktionen setq. I stället för
a = 3;
skriver man
(setq a 3).
I stället för
x = y + z + 3 * t
skriver man
(setq x (+ y z (* 3 t)).

Mer avancerad Lisp:

Lokala variabler skapar man med let, som är ungefär som ett block i C.
(let (a b c (d 14) (e 15) f) (setq a 17) (print a))
motsvarar
{ int a, b, c, d = 14, e = 15, f; a = 17; printf("%d\n", a); }
(förutom att variablerna inte har några bestämda typer i Lisp).
I Amos-lispen skapar man funktioner med defun:
(defun xplusyz (x y z) (+ x (* y z)))
motsvarar
int xplusyz(int x, int y, int z) { return x + y * z; }
(förutom att parametrarna, och funktionen, inte har några bestämda typer).
Observera att return i Amos-lispen inte används för att returnera från en funktion, som i C och Java, utan för att hoppa ur en loop. I Lisp skriver man bara de värden som ska returneras, utan något return:
(defun xdivy (x y) (if (equals (y 0) x (/ x y))))
motsvarar
int xdivy(int x, int y) { if (y == 0) return x; else return x / y; }

Uppgift

Skriv en uttömmande ("exhaustive") kostnadsbaserad optimerare för Amos II. Följ den här labbinstruktionen (PDF), från databaskursen i Linköping. Ignorera föråldrade saker, som till exempel var kodskelettet "kodskelett.lsp" finns.

Kodskelett för Lisp-funktionen dynprogsort: kodskelett.lsp

Vi måste använda den äldre versionen av Amos II från inlämningsuppgift 4.

För att Lisp-debugging ska fungera, ersätt den gamla amos2.dmp med den här: amos.dmp

Lästips

Den gamla labbinstruktionen, från Linköping (PDF)
ALisp User's Guide (PDF, samma lösenord som ovan). Det där är en lite nyare version än den ALisp User's Guide som finns på webben i Uppsala.
Amos II Release 8 User's Manual (HTML)
En introduktion till Common Lisp, som visserligen är en annan dialekt än Alisp, men ganska lik.

Redovisning

Visa optimeringsfunktionen. Diskutera gärna med läraren.

Arbeta i grupper om en eller två studenter. I undantagsfall kan man arbeta i grupper om tre, men fråga läraren först.

Det är tillåtet att samarbeta i större grupper än så, men varje grupp om 1-3 studenter måste fortfarande redovisa separat, och det måste också tydligt framgå (i rapporten eller på annat sätt) vilka som deltog i samarbetet.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 12 januari 2012