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.

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.

📅 Vorbesprechung

Eine Vorbesprechung zu diesem Seminar zu

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

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

Bei Fragen zu diesem Seminar könnt ihr euch gerne an Daniel O’Grady wenden.

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.

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

• Unequal

  In Unequal, wie in Sudoku, geht es darum eine bestimmte Verteilung von Zahlen auf einem quadratischen Gitter zu finden. Der fundamentale Unterschied: Als Hinweis wird auf dem Gitter markiert, ob ein Feld im Gitter größer oder kleiner als ein angrenzendes Feld ist. Eure Aufgabe ist es, einen Unequal Solver zu schreiben. Weitere informationen über Unequal findet ihr hier.

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

Seminartermine

Die Termine finden auf dem Sand in Raum B305 statt, beginnen jeweils um 11:00 Uhr und sind auf 90 min angesetzt.

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

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.