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

Det här borde ändras så det använder den senaste versionen av Amos. Men tills vidare använder vi detta.

Mål

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 en äldre version av Amos II: older-amos2.zip.

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

Lästips

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), 25 februari 2015