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 (Pro-)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.

Voraussetzungen

Vorkenntnisse in SQL — etwa aus den Vorlesungen DB1, DB2 oder Avdanced SQL — sind natürlich hilfreich. Solltet ihr anderweitig Erfahrungen mit SQL gesammelt haben, ist das ebenfalls OK.

Das Seminar richtet sich primär an Master-Studenten der Informatik. Auch Bachelor-Studenten können teilnehmen. Laut Prüfungsskretariat gilt (mit Stand Oktober 2020):

• Master: “Advanced Topics in Database-Systems” (Prüfungsnr. 1080), Seminar, 3 LP, anrechenbar in den Bereichen “Praktische Informatik” und “Informatik”

Vorbesprechung

In der Vorbesprechung werden wir über

• Problemstellungen und
• Termine im Semester

sprechen. Sie findet statt am 6.11.2020 in Form eines Zoom-Meeting.

Bei Fragen könnt Ihr Euch gerne an Tobias wenden.

Aufgrund sehr hoher Nachfrage ist die Anmeldung zur Vorbesprechung bereits geschlossen (Stand: 26.10.2020). Wer sich angemeldet hat, wird bis zum 26. Oktober eine E-Mail mit den weiteren Details zum Ablauf bekommen.

Vortragstermine

Pro Termin finden zwei Vorträge statt. Der Beginn ist jeweils um 11:00 Uhr und die Veranstaltungen dauern ca. 90 Minuten.

Die Vorträge sollen bestehen aus mindestens

• der Problembeschreibung,
• einer Erläuterung der Implementierung,
• und einer Live-Demo.

Eine Live-Demo mit Visualisierung ist hilfreich, um die berechneten Ergebnisse übersichtlich und optisch ansprechend darzustellen.

Pro Vortrag gilt ein Zeitlimit von 25 Minuten. Bitte nicht überziehen. Anschließend wird es eine kurze Fragerunde von ca. 5 Minuten geben. Bitte haltet einen Texteditor bereit, um ggf. Fragen zum Code beantworten zu können.

Es gilt grundsätzlich Anwesenheitspflicht, da es sich um ein Seminar handelt. Außerdem muss jeder seine/ihre Kamera eingeschaltet haben.

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.
• Für das Zeichnen von Figures können wir das LaTeX-Paket TikZ empfehlen. Hochwertige Figures zu erstellen ist ähnlich aufwendig wie das Schreiben von Text.
• Die Ausarbeitung soll mindestens 4 und höchstens 6 Seiten umfassen.

Abgabefrist für die Ausarbeitungen ist der 31. März 2021. Bitte per E-Mail an den jeweiligen Betreuer schicken. Darüberhinaus sollen der Code und die Folien auch abgegeben werden.

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.

• 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.

• Generierung von Pixelgrafiken aus Braille-Zeichen

  Der Unicdode-Zeichensatz enthält den vollen Satz an Braille-Zeichen, die eigentlich entworfen wurden, um Blinden über den Tastsinn den Zugang zu Gedrucktem zu erschliessen. Diese Zeichen ordnen 2 × 4 Pixel rechteckig an (Beispiele für Braille-Zeichen sind ⠝ ⡞ ⡿ ⣠ ⣿). Da Unicode alle möglichen 2⁸ = 256 Pixelkombinationen als Zeichen enthält, lassen sich so beliebige Pixelgrafiken in reiner Textform repräsentieren, siehe auch das Drawille-Projekt. Dieses Seminarthema baut diese Konversion von Pixelgrafiken in Braille-Textform in SQL nach.

• Distance-Vector Routing

  Wenn sich die Verbindungen in einem Netzwerk von Hosts stark (bzgl. Durchsatz, Performance) unterscheiden, dann kann Distance-Vector Routing dennoch Routen guter Qualität effizient berechnen. Die Hosts nutzen dazu die sog. Distance-Vector Routing-Tabellen. Dieses Seminarthema vollzieht die Konstruktion (und vielleicht sogar dynamische Updates?) dieser Routing-Tabellen in SQL nach und berechnet darauf basierend effiziente Routen durch ein Netzwerk.

• 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.