SQL is a Programming Language

SQL ist die Anfragesprache für das relationale Datenmodell, mit der sich Daten aus verschiedenen Tabellen zusammenführen, filtern, gruppieren und filter lassen. Aber SQL ist deutlich mehr als das. Die Geschichte von SQL reicht bis in die 1970er Jahre zurück und seitdem hat sich die Sprache stetig weiter entwickelt, transformiert und erweitert. Heutiges, modernes SQL ist deklarativ, ausdrucksstark, oft sehr kompakt und auch elegant. Seit der Einführung von Rekursion in SQL ist die Sprache zudem berechnungsvollständig: es gibt kein Problem, das man mit SQL nicht knacken kann.

In diesem Master-Seminar bearbeiten die Teilnehmer/Innen jeweils ein in sich geschlossenes Programmierproblem und konstruieren eine Lösung ausschließlich in SQL. (Wir raten zu PostgreSQL, aber das können wir individuell vereinbaren.) Wir wählen dazu Probleme aus, die zu einem interessanten Algorithmus führen, Puzzles verschiedener Art lösen, Simulationen durchführen, ansprechend visualisierbar sind, etc. Spaß und Aha-Effekte stehen im Vordergrund. Auf jeden Fall werden die Probleme nicht “typisch relational” sein und zu SELECT * FROM table führen: SQL hat viel mehr auf dem Kasten und in diesem Seminar werdet ihr dazu zahlreiche Beweise liefern.

Jede/r Teilnehmer/in wird im 30-minütigen Seminarvortrag das bearbeitete Problem vorstellen und eine SQL-basierte Lösung präsentieren. Kurz-Demos während des Vortrags bieten sich natürlich ideal an. Falls es beim Lösen/Implementieren des Problems “haken” sollte, ist das kein Show Stopper: wir geben dazu gerne Tipps — niemand muss deshalb dieses Seminar nicht bestehen. Euer Folienmaterial und die Ausarbeitung zum Problem und seiner Lösung erstellt ihr in Englisch.

📅 Vorbesprechung

Eine Vorbesprechung zu diesem Master-Seminar zu

  • Problemstellungen
  • Terminen im Semester (nach Absprache mit euch)

führen wir am Freitag, den 20. April, 11:00-11:30 Uhr im Raum B305.1 durch.

Teilnehmer

Die folgende Liste beinhaltet alle Teilnehmer an diesem Master-Seminar.

Vortragstermin1. Vortrag2. Vortrag
Fr, 15.06.2018
11:00 Uhr
Denis Hirn (Dynamic Time Warping)Dennis Zimmer (Pfadfindung mit dem A*-Algorithmus auf einem 2D-Grid)
Fr, 22.06.2018
11:00 Uhr
Noah Doersing (Handschrifterkennung)Eugen Ljavin (Sichtbarkeit in 3D-Terrain)
Fr, 06.07.2018
11:00 Uhr
Mathias Jenter (Levenshtein Distanz)Denis Heid (2D-Karten aus Bruchstücken erstellen (Merging Maps))
Fr, 13.07.2018
11:00 Uhr
Artjom Besuschkow (Tracing von 2D-Objekten mittels Marching Squares)

Die Termine finden auf dem Sand in Raum B305.1 statt und sind auf 30 Minuten pro Teilnehmer angesetzt.

Es gilt für alle Teilnehmer, an allen Terminen anwesend zu sein! Weitere interessierte Hörer sind herzlich willkommen.

Themen

Unten findet ihr eine Liste der Aufgabenstellungen, die in diesem Seminar mittels SQL realisiert werden. Die genauen Details hier zu (bspw. in welchem Format stehen Eingabedaten bereit) oder Hinweise zur Realisierung erhaltet ihr von eurem Betreuer.

  • Sichtbarkeit in 3D-Terrain

    Welche Punkte eines hügeligen Terrains sind von einer gegebenen Betrachterposition aus sichtbar? Während nahe gelegene Hügel die Sicht auf dahinter liegende Punkte versperren, können höhere Gipfel noch sichtbar sein, auch wenn diese weit enternt sind. Dieses Sichtbarkeitsproblem lässt sich sehr elegant mit sog. max scans lösen, die ihr in dieser Aufgabe einsetzen werdet.

  • Markov Decision Process Visualisierung

    Gegeben sei ein 2D-Grid in dem zufällig ein Roboter platziert wurde. Der Roboter kann sich nun entscheiden in eine von vier Richtungen zu laufen. jedoch kann es sein, dass er eine Fehlfunktion hat und trotz seiner Entscheidung in eine ganz andere Richtung läuft. Zusätzlich erhält oder verliert der Roboter mit jedem Schritt Punkte, je nachdem auf welchem Feld er landet. Das Ziel des Roboters ist es aber, seine Punktzahl zu maximieren. Dank dem Markov Decision Process erhalten wir eine policy mit dieser der Roboter exakt entscheiden kann, welche Richtung er als nächstes gehen muss, um mit dem geringsten Risiko seine Punktzahl (reward) zu maximieren.

  • Tracing von 2D-Objekten mittels Marching Squares

    Der Algorithmus Marching Squares kann die Form (Kontur) zwei-dimensionaler Objekte erschliessen. Das Verfahren verwendet dabei lediglich eine sehr kleine Umgebung des aktuell untersuchten Konturpunktes, um sich sehr effizient aber dennoch robust am Objekt “entlang zu tasten”.

  • 2D-Karten aus Bruchstücken erstellen (Merging Maps)

    Satellitenaufnahmen der Erde nehmen jeweils nur ein kleines Fenster der Oberfläche auf. Wie lassen sich aus solchen Teilaufnahmen konsistent größere Oberflächenkarten erstellen (siehe etwa Google Maps)? Diese Aufgabe wird auf einer textuellen abstrakten Version solcher Aufnahmen arbeiten — aber das Problem bleibt spannend und lässt sich klasse visualisieren.

  • Levenshtein Distanz

    Wie quantifizieren wir den Unterschied zwischen zwei beliebigen strings s und t? Die Levenshtein-Distanz berechnet eine Distanz die uns erlaubt zu bestimmen, welche Änderungen an dem string s notwendig sind, um diesen in den string t zu transformieren.

  • Pfadfindung mit dem A*-Algorithmus auf einem 2D-Grid

    Um den kürzesten Pfad zwischen zwei Punkten zeitnah auf einem 2D-Grid finden, gibt es viele Möglichkeiten. Ein möglicher Weg ist die Berechnung dieses Pfads mit der Hilfe des A*-Algorithmus. Eure Aufgabe ist es, diesen Algorithmus zu implementieren.

  • Textmuster-Erkennung mittels endlicher Automaten

    Bei der Analyse von Zeichenketten kann es interessant sein, ob diese einem bestimmten Muster entsprechen (etwa: befindet sich das Wort “Fotografie” in einer anderen Variante, “Photographie”, “Photografie” oder “Fotographie” in einem Text?). Eine solche Mustererkennung kann mittels endlicher Automaten ermittelt werden, welche sich in SQL auf unterschiedliche Arten darstellen lassen.

  • Dynamic Time Warping

    Die Methode des DTW erlaubt es, Ähnlichkeiten zwischen zwei Zeitmessungen festzustellen. Je größer das Ergebnis, desto unterschiedlicher die Daten. Würde beispielsweise ein langsamer und ein schneller Läufer den gleichen Weg ablaufen und dabei zu den gleichen Zeitpunkten (offensichtlich) unterschieldiche Höhenposition messen, so würde der DTW dennoch erkennen, dass es sich bei diesen beiden Messungen um sehr ähnliche Messdaten handelt.

  • Handschrifterkennung

    Buchstaben werden in Handschrift auf ein Tablett gezeichnet. Wie lassen sich aus den entstandenen Schriftlinen die zugehörigen Buchstaben bestimmen? Ein einfaches Vorgehen ist, diese so weit zu vereinfachen, dass sich bestimmte Charakteristika ermitteln und mit bekannten Buchstabenmustern abgleichen lassen. Diese Aufgabe zeigt eindrucksvoll, wie mit Hilfe einfacher Methoden, Handschrift und andere Zeichnungen erkannt und als Eingabe für Computerprogramme verwendet werden können.

Hinweise zu den Vorträgen

  • Wichtig: Spätestens ein bis zwei Wochen vor eurem Vortrag solltet ihr einen Termin mit eurem Betreuer ausmachen, um euren kompletten Foliensatz durchzusprechen. Das sich daraus Änderungen an den Folien ergeben, ist die Regel (nicht die Ausnahme). Stellt also bitte sicher, dass ihr euch ein ausreichend grosses Zeitfenster für nötige Änderungen einräumt.

  • Die Länge der eigentlichen Vorträge beträgt jeweils maximal 30 Minuten. An die Vorträge schließt sich eine kurze offene Diskussion an, die sich auf den Inhalt des Vortrages aber auch auf den Vortrag an sich (Folien, Sprache) beziehen kann.

  • Ihr findet weitere wertvolle Hinweise zum Aufbau eines Vortrages, zum Layout von Folien und dem Halten des Vortrages selbst, auf den folgenden Seiten:

  1. Simon Peyton-Jones (Microsoft Research, Cambridge): How to give a good research talk
  2. Andreas Zeller (U Saarland): Der perfekte Seminarvortrag
  • Der Inhalt des Vortrags sollte das gestellte Problem genau erläutern und vielleicht an 1–2 Beispielen demonstrieren. Dabei solltet ihr betonen, was das Problem interessant und/oder knifflig macht. Den Rest des Vortrages solltet ihr (1) auf die Diskussion möglicher Lösungsansätze (es kann ja durchaus mehrere denkbare Lösungen geben) und (2) die Darstellung der Realisierung der von euch gewählten und implementierten Lösung verwenden.

  • Eure Programm zur Lösung des Problems wird typischerweise einen algorithmischen Kern — oft wenige Zeilen — beinhalten. Diesen Kern, evtl. gekürzt und vereinfacht falls angebracht, könnt und sollt ihr während des Vortrags zeigen und erklären. Wenn sich der Code selbst nicht eignet, ist ein Flussdiagramm oder ähnliches vielleicht eine bessere Alternative. Routinen oder Code-Teile, die Eingabe/Ausgabe implementieren sind oft sekundär und gehören nicht in Ihren Vortrag.

  • Die tatsächliche Demonstration eures lauffähigen Programmes gehört ebenfalls zu einem gelungenen Vortrag. Sie kann nicht zuletzt sehr motivierend für eure Zuhörer sein. Auch hier gilt aber: kleine Beispiele, die den common case zeigen und nicht die vielleicht eher esoterischen Randfälle des Problems und seiner Lösung zum Inhalt haben.

  • Generell gilt: vermittelt das Prinzip eurer Lösung — eine genaue Studie des Code ist nicht angebracht. Es ist auch denkbar, (Ausschnitte des) Code ausschliesslich ganz am Ende des Vortrages, auf sog. Backup-Folien in den Foliensatz aufzunehmen. Diese Folien zeigt man nur, wenn die Diskussion nach dem Vortrag oder spezifische Nachfragen dazu führen sollten. Wenn der Weg zur Lösung (nicht die Lösung selbst) systematisch war und einen eye opener enthält, dann kann das sehr zum Verständnisbildung beitragen. Die eher wahllose Darstellung von ‘‘hab’s mal probiert, ging dann aber doch schief’’-Versuchen verwirrt jedoch eher.

  • Zur Erstellung eurer Folien können wir euch die LaTeX-Class Beamer empfehlen.

Hinweise zu den Ausarbeitungen

  • Die Ausarbeitung zu euren Themen erfolgt ausnahmslos in LaTeX. Hierfür soll die zweispaltige Formatvorlage SIGCONF Proceedings der ACM verwendet werden. Ihr könnt die Original-Vorlage herunterladen oder diese reduzierte Version benutzen. Die Ausarbeitung soll insgesamt vier Seiten umfassen.

  • Für Bilder empfehlen wir euch im Weiteren das LaTeX-Paket TikZ zu verwenden.