Diese Seite enthält einige Beispiele für mögliche Themen von Abschlussarbeiten. Im Moment handelt es sich eher um Themen für Bachelor-Arbeiten. Wenn Sie sich für eins der Themengebiete interessieren, können wir im gemeinsamen Gespräch auch modifizierte oder weitere Themen entwickeln. Die Liste ist also nicht als Katalog zu verstehen, von denen Sie sich ein Thema aussuchen müssen, sondern mehr als Anregung bzw. zum Einstieg in eine Diskussion.
Im Prinzip ist es auch möglich, dass Sie ganz eigene Themen vorschlagen. Es ist aber wichtig, dass ich sie auch betreuen bzw. am Ende bewerten kann. Das Thema muss also in einem Gebiet liegen, in dem ich mich gut auskenne. Außerdem macht mir die Betreuung natürlich Arbeit. Es wäre daher wüschenswert, dass ich Ihr Thema auch spannend finde, und ich mir für meine zuküftige Arbeit von der Beschäftigung mit der Thematik Vorteile verspreche.
Lernspiele (Game-Based Learning)
Ein Bereich, in dem man eine Bachelor-Arbeit schreiben kann, sind Lernspiele für Datenbanken. Wir hatten schon einige Arbeiten in diesem Bereich, in erster Linie Text-Adventurespiele mit Verwendung von SQL. Es wäre schön, wenn unser unfertiges Projekt über Abschluss-Arbeiten vorangebracht werden könnte. Wir sind aber auch offen für neue Ansätze.
Thema 1. Non-Player Characters [vergeben]
Es wäre möglich, in einer Bachelor-Arbeit die Implementierung von NPCs ("Non-Player Characters") zu studieren. Das sind computergesteuerte "Personen", denen man im Spiel begegnen kann (z.B. Händler). Dazu wäre zunächst zu recherchieren, wie NPCs in Autorensystemen für Textadventurespiele (z.B. Quest) spezifiziert werden (ggf. auch in konkreten Spielen). Dann wäre ein Vorschlag zu machen, wie interessante NPCs in unserem SQL-Lernspiel definiert werden können, also z.B. welche Tabellen man braucht und wie die Steuerung funktionieren soll. Dieser Vorschlag wäre dann in ein vorhandenes Programm einzubauen, wobei ggf. auch an dem vorhandenen Programm noch etwas Arbeit zu leisten wäre. Einen ganz neuen Prototyp zu entwickeln, würde vermutlich zu viel Zeit kosten. Es wäre aber denkbar, dass man dafür neue Ideen hat, die das doch möglich machen.
Thema 2. Steuerprogramm für SQL-Adventure-Spiel
Unser Ansatz für SQL-Lernspiele (insbesondere Text-Adventure-Spiele) ist, dass der Spieler Änderungen an einem Datenbank-Zustand vornehmen kann (z.B. seine Position in der Spielwelt ändern), und dann ein Steuerprogramm prüft, ob der Zug legal ist, und ggf. welche anderen Updates dadurch noch bewirkt werden. Wenn der Spieler z.B. in einen neuen Raum kommt, müssen wenigstens die Beschreibung des Raums und die Einträge für Verknüpfungen mit anderen Räumen aus der (geheimen) zentralen Datenbank in die Datenbank des Spielers übertragen werden. Oder wenn man in einem Laden ein Gebot für einen Gegenstand in eine Tabelle eingefügt hat, und der Verkäufer nimmt das Gebot an, bekommt man den Gegenstand und verliert das Geld. Wenn der verkäufer das Gebot zu niedrig findet, setzt er eine Antwort-Spalte in der Gebot-Tabelle auf einen Text (oder der Text wird in eine Protokoll-Tabelle eingetragen). Letztendlich wird die Spiel-Logik durch die Reaktionen auf Updates des Spielers definiert.
Ziel dieser Arbeit ist es, eine Sprache bzw. ein Datenformat zu definieren, in dem man die Reaktionen auf Updates des Spielers spezifizieren kann. Am liebsten wäre mir ein Datalog-änliches Format, aber vielleicht wäre auch eine Sequenz von "IF-THEN" Regeln mit SQL-Anfragen und Updates passend. Obwohl es recht ähnlich zu Triggern einer Datenbank ist, möchte ich doch eine spezielle Sprache für diese Adventurespiel-Anwendung. Sie soll auch deutlich einfacher sein als die allgemeine Programmiersprache, die viele DBMS für Trigger zur Verfügung stellen. Die Sprache im DBMS wäre ja auch sehr system-abhängig, was ich über die Indirektion einer eigenen Sprache vermeiden möchte. Durch die anwendungsspezifische Sprache soll natürlich auch die Programmierung erleichtert werden.
Es wären dann die Tabellen der zentralen Datenbank zu definieren (dafür gibt es schon Vorschläge), sowie die Sichten und Tabellen der Spieler-DB, und vor allem die Sprache für die Reaktionen zu implementieren. Natürlich wären auch die Regeln für ein einfaches Beispiel-Spiel zu definieren. Das Programm muss sich unbedingt in unser Projekt einpassen.
Thema 3. Adventurespiel-Parser mit SQL-Anwendung [vergeben]
Alternativ zu SQL-Kommandos sollen bei unserem SQL-Lernspiel auch klassische Textadventure-Befehle wie "go north" oder einfach "n" nutzbar sein. Es wäre frustrierend, wenn man sonst sehr häufig gleich strukturierte SQL-Anweisungen eingeben müsste. Allerdings sollen die letztendlich ausgeführten SQL-Anweisungen wenigstens angezeigt werden, so dass der Spieler auch durch das Lesen dieser Anweisungen etwas lernt.
Im Prinzip haben wir schon einen Prototyp, der so funktioniert, aber die Erfahrungen haben gezeigt, dass es noch viel zu verbessern gibt:
- Die Fehlerbehandlung ist sehr rudimentär. Es sollten spezifische Fehlermeldungen gegeben werden. Bisher war gefordert, dass jedes Kommando in eine SQL-Anweisung übersetzt wird. Das geht aber nicht, wenn man z.B. erst mit einer Abfrage prüfen muss, ob es überhaupt einen Weg in der Richtung gibt, und dann ggf. den Update für den aktuellen Raum des Spielers durchführen muss. Hier wäre also (in Absprache mit mir) auch ein neues Konzept zu entwickeln, vielleicht eine Art Mini-Sprache für eine Abfolge von SQL-Anweisungen für ein Verb mit der Möglichkeit zum Abbruch bei bestimmten Bedingungen.
- Wenn man schon mehrere SQL-Anweisungen erlaubt, bietet sich an, für das gleiche Verb unterschiedliche Implementierungen zu haben: Z.B. nur eine komplexe SQL-Anweisung für den Update, oder mehrere einfache Anweisungen mit der Zwischenspeicherung von Resultaten. So können die angezeigten SQL-Anweisungen passender für den Wissensstand des Spielers gemacht werden, bzw. man erreicht auch mehr Abwechselung.
- Der Parser sollte nicht schlechter sein als von klassischen Spielen. Unser bisheriger Prototyp hat einen sehr einfachen Parser. Z.B. müssen momentan Bezeichnungen von Objekten, die sich aus mehreren Worten zusammensetzen, immer vollständig eingegeben werden. Es sollte aber ausreichen, nur einen eindeutigen Teil anzugeben. Es sollte auch nicht nötig sein, beim "examine" den Typ des Objektes mit anzugeben (das hat sich auch aus der Forderung nach nur einer SQL-Anweisung pro Adventure-Befehl ergeben, zumindest wären sonst sehr komplexe Anfragen nötig).
- Für die Spezifikation der Ausgaben könnte es verschiedene "Ausgabefilter" geben: Z.B. listet der "help"-Befehl im Moment nur den Inhalt einer Tabelle auf, aber das Ausgabeformat ist etwas anders, als wenn man die entsprechende SQL-Anfrage eingeben würde.
- Der Spieler könnte vielleicht gezwungen werden, gelegentlich auch SQL-Befehle zu nutzen. Z.B. bekommt man für jeden SQL-Befehl 10 normale Adventure-Befehle.
- Auch eine intelligentere Hilfe-Funktion oder ein Tutorial stehen auf der Wunschliste. Alles sollte natürlich mit möglichst allgemeinen Mechanismen über eine Spezifikation in einer Konfigurationsdatei definierbar sein.
- Der neue Parser müsste in unseren web-basierten Prototyp integriert werden.
Thema 4. Zufällig generierte Daten [vergeben]
Mindestens zum Teil soll jeder Spieler eine eigene Version des Spiels bekommen. Es soll nicht zu leicht möglich sein, eine vorhandene Lösung einfach zu kopieren. Das gilt nicht nur für SQL-Spiele, sondern auch für normale Übungsaufgaben. Die generierten Daten müssen aber bestimmte Anforderungen erfüllen, so dass sich z.B. die Aufgabe im Spiel überhaupt lösen lässt. Gerade beim Spiel ist auch wichtig, dass sich ingesamt ein stimmiges Bild ergibt, so dass der Spieler in die Spielwelt eintauchen kann, und die automatische Generierung nicht zu sehr auffällt. Wenn man nur ein Labyrinth oder ein Lager einer Firma erzeugt, geht das vermutlich noch recht leicht, aber z.B. einen Wald aus vorgegebenen Stücken zusammenzusetzen, ist schon schwieriger. Auch hier wäre der Stand der Technik zu recherchieren, ein Vorschlag zu erarbeiten, und eine prototypische Implementierung zu entwickeln.
Thema 5. Neue Spielkonzepte
Bisher haben wir hauptsächlich Textadventurespiele studiert. Wenn Sie ganz anders geartete Spielkonzepte für ein SQL-Lernspiel verwenden wollen, wäre ich da auch sehr interessiert an Ihren Ideen und Vorschlägen. Man muss sich immer folgende Fragen stellen:
- Wie motiviert man die Spieler, wirklich SQL zu verwenden?
- Wie erreicht man, dass auch komplexere Anfragen im Spiel nützlich sind?
- Wie vermeidet man, dass ein schon bekannter Typ von SQL-Anweisung im Spiel sehr häufig verwendet werden muss? Wenn z.B. für die Bewegung in der Spielwelt ein SQL Update-Befehl verwendet werden muss, wird das sehr schnell langweilig und mühsam.
- Wie erreicht man, dass das Spiel selbst interessant ist, und sich deutlich von einem klassischen Tutorial mit einer fest vorgegebenen Folge von Aufgaben unterscheidet.
Automatische Korrektur von SQL-Aufgaben
Thema 6. Plagiatsprüfung für SQL
Plagiatsprüfung z.B. für Java-Programme ist Standard und wurde in der Vorlesung "Objektorientierte Programmierung" mehr oder weniger erfolgreich eingesetzt. Es wurde dort die Software JPlag verwendet. Wir würden das gerne auch für SQL-Anfragen machen. Wir haben schon eine Sammlung von Abgaben aus früheren Semestern. Damit könnte man Algorithmen testen. Leider ist es sehr schwierig, herauszufinden, ob wirklich ein Plagiat vorlag (man bekommt im allgemeinen keine "Geständnisse"). Man könnte vielleicht über Wahrscheinlichkeiten argumentieren, oder Befragungen zumindest vorbereiten, bei denen man erwarten kann, dass die Teilnehmer eine ehrliche Antwort geben werden. Da wir zuletzt auch eine elektronische Klausur geschrieben haben, hätten wir dort eine Sammlung von SQL-Anfragen, bei denen es ja keine Plagiate gegeben haben dürfte.
Thema 7. Vergleich von Resultaten von SQL-Anfragen [vergeben]
Zur Korrektur von SQL-Anfragen werden diese auf ein oder mehr Beispiel-Zuständen ausgeführt, und das Ergebnis mit dem Ergebnis einer Musterlösung verglichen. Wenn man viele Abgaben korrigieren muss, möchte man schnell sehen, was der Unterschied ist. Ein boolesches Ergebnis reicht sicher nicht. Z.B. könnte es ja sein, dass nur die Reihenfolge der Spalten nicht stimmt, aber das Ergebnis ansonsten korrekt ist. Oder der Name einer Ausgabespalte nicht stimmt. Oder die Reihenfolge der Zeilen nicht mit der verlangten Sorierung übereinstimmt, aber die Menge der Zeilen korrekt ist. Oder es fehlt eine Ausgabe-Spalte, aber sonst ist alles richtig. Auch wenn die Menge der Antwort-Tupel nicht stimmt, möchte man gern wissen, ob es eine Teilmenge oder eine Obermenge ist, oder sich die Fehler auf nur eine Spalte beziehen. Es wäre gewissermaßen die minimal nötige Änderung kompakt zu beschreiben, mit der man vom Ergebnis der abgegeben Anfrage zum Ergebnis der Musterlösung kommt. Bei großen Unterschieden muss man diese sinnvoll zusammenfassen (also eine verlustbehaftete Kompression durchführen). Der Korrekteur möchte ja möglichst schnell eine Idee bekommen, wo der Fehler liegen könnte.
Wenn die Anfrage auf mehreren Beispiel-Zuständen ausgeführt wird, wird es noch wichtiger, die Ergebnisse der Tests sehr kompakt zusammenzufassen.
Wünschenswert wäre auch eine Unterstützung der Tutoren beim Umgang mit der Übungsplattform. Momentan kann man zwar die ganzen abgegebenen Lösungen exportieren, aber die SQL-Anfragen stehen in Verzeichnissen mit Abgabenummern, die man dann mit einer CSV-Datei wieder den Studenten zuordnen muss. Mit einem entsprechenden Programm könnte man die Korrekturzeit pro Abgabe reduzieren, und auf die inhaltliche Auseinandersetzung mit der Lösung konzentrieren. Das Ergebnis der Tests sollte dabei natürlich angezeigt werden, und es sollte möglich sein, Fehlerbeschreibungen und Punktabzüge abzuspeichern und wieder zu verwenden.
Thema 8. Vergleich von Charakteristika von SQL-Anfragen
Wenn eine Anfrage nicht das richtige Ergebnis liefert, sollten zumindest nach dem zweiten oder dritten Versuch Tipps produziert werden. Wenn z.B. die Musterlösung NOT EXISTS enthält, und die Anfrage des Studenten kein nichtmonotones Konstrukt, wäre vielleicht ein entsprechender Hinweis angebracht. Natürlich sollte auch geprüft werden, ob die Tupelvariablen einander zugeordnet werden können. Die Hinweise sollten möglichst verständlich sein, aber erst nach und nach mehr verraten.
Ähnliche Untersuchungen mit etwas anderer Zielsetzung wäre die Erkennung von Anfragen, die zwar in einem Beispielzustand das erwartete Ergebnis liefern, aber nicht äquivalent zur Musterlösung sind.
Z.B. wäre es auch merkwürdig, wenn eine Anfrage Konstanten enthält, die in der Aufgabenstellung gar nicht vorkommen. Dabei wäre natürlich die Äquivalenz von z.B. < 9 und <= 8 zu berücksichtigen (wenn die Spalte nur ganze Zahlen erlaubt).
Git-Repository für unser Projekt "sql-checker":
Thema 9. Berechnung von Warnungen für semantische Fehler von SQL-Anfragen
Ein Forschungsprojekt des Lehrstuhls ist die Erkennung semantischer (logischer) Fehler in SQL-Anfragen. Dazu wurde ein Prototyp in der logische Programmiersprache Prolog entwickelt, siehe die SQLLint Webseite. Leider ist die unterstützte SQL-Teilmenge sehr klein. Man könnte den Parser von Apache calcite nehmen, und darauf aufbauend eine neue Version in Java entwickeln. Da wir inzwischen auch relativ viele Anfragen von Studierenden gesammelt haben, könnte man auch testen, wie viele semantische Fehler darin wirklich gefunden werden.
Thema 10. Test der logischen Äquivalenz von SQL-Anfragen
Um die Korrektheit einer SQL-Anfrage für eine Aufgabe zu entscheiden, müsste man die Äquivalenz zu einer Musterlösung prüfen. Diese Frage ist unentscheidbar, d.h. man kann kein Programm schreiben, das das für beliebige SQL-Anfragen leistet. Weil es also keine perfekte Lösung gibt, bleibt das Problem spannend. Es gibt das Programm Cosette von der University of Washington. Bisherige Tests in einer früheren Bachelorarbeit haben aber gezeigt, dass das Programm nicht so toll ist, wie man vielleicht nach dem Studium der wissenschaftlichen Arbeiten vermuten könnte. Ich hatte zusammen mit Herrn Goldberg einen Algorithmus für einen Konsistenztest für SQL veröffentlicht, der auch in meiner SQLLint-Implementierung enthalten ist. Ich würde gerne diesen Algorithmus neu implementieren lassen und dann auf reale Anfragen aus früheren Übungen anwenden und mit Cosette vergleichen.
Thema 11. Entwicklung personalisierter Aufgaben
Damit die Versuchung zum Kopieren von Hausaufgaben nicht zu groß ist, wäre es gut, personalisierte Aufgaben zu erstellen, die sich mindestens in Details unterscheiden. Dann könnte man nicht einfach eine Lösung kopieren, sonden müsste sie wenigstens soweit verstehen, dass man die Stellen findet, an denen sie sich die beiden Aufgaben unterscheiden.
Der entsprechende Algorithmus wäre in die Übungsplattform einzubauen, und mit der Software zu verknüpfen, die in der Arbeitsgruppe Datenbanken zur automatischen Korrektur von SQL-Aufgaben entwickelt wird.
Weitere Themen zu SQL
Thema 12. Untersuchung zu Unterschieden zwischen SQL-Dialekten [vergeben]
In den Vorlesungsmaterialien wird auf einige Unterschiede zwischen den von verschiedenen DBMS unterstützten SQL-Dialekten hingewiesen. Leider sind die Hinweise teilweise veraltet, und nur mühsam zu wiederholen, da ich manuell verschiedene Systeme getestet habe. Ich hätte gerne ein System, was SQL-Konstrukte automatisch testet, und leicht um weitere DBMS und weitere SQL-Tests zu erweitern ist. Ich habe schon mit Test-Skripten begonnen, aber für viele Tests (z.B. ca. 100) ist das noch zu umständlich. Ein Programm, dass das erledigt, sollte nicht besonders aufwändig sein, aber der interessante Punkt dieser Bachelorarbeit liegt auch im Aufspüren von Feinheiten, die in unterschiedlichen Systemen unterschiedlich geregelt sind.
Effiziente Implementierung einer deduktiven Datenbank
Thema 13. Parallele Implementierung des Push-Verfahrens zur Auswertung von Datalog
Deduktive Datenbanken verwenden die Sprache Datalog, eine kleine Teilmenge von der logischen Programmiersprache Prolog. Man kann Datalog schnell lernen, es sind nur einfache Wenn-Dann Regeln mit Variablen und Konstanten. Datalog ist nur ein kleiner Teil meiner Vorlesung Logische Programmierung und deduktive Datenbanken. Wir haben das "Push" Verfahren zur Bottom-Up Auswertung entwickelt bzw. wiederentdeckt und verbessert, und damit sehr gute Laufzeit-Ergebnisse erzielt: Push-Webseite, Neue Webseite: RBench.
Leider ist das bisherige Verfahren noch sequentiell. Wir haben Ideen für eine Parallelisierung, die jemand ausprobieren müsste, gern auch in Java statt der bisherigen Implementierungssprache C++. Hier wäre kein sehr umfangreiches Programm zu entwickeln, sonderen mehrere relativ kleine.
Anwendungen deduktiver Datenbanken
Thema 14. Anwendung von Datalog für SQL-Lernspiel
Ich hätte gerne eine Neu-Implementierung des Text-Adventure SQL-Lernspiels, bei dem große Teile in Datalog geschrieben sind. Die Behauptung ist ja, dass das zu wesentlich kompakterem Code führt.
Planung von Feuerwerken
Thema 15. Positionierung von Effekten in einem Musikstück [vergeben]
Ich plane und organisiere seit 2010 ein Großfeuerwerk zur Langen Nacht der Wissenschaften. Natürlich entwickle ich auch eine Planungs-Software. Ein Problem ist die exakte Positionierung von Effekten in einer Audio-Datei. Ich würde gerne nur ungefähr sagen, wo ein Effekt hingehört, und er sollte dann automatisch auf den Schlag "einrasten". Im Prinzip gibt es dazu "Onset-Detection", was nach meinen Informationen aber für klassische Musik nicht besonders gut funktioniert. Ich bin leider für diesen Bereich kein Experte, würde mich aber freuen, wenn jemand mir die Arbeit abnimmt, einige Verfahren zu testen. Wir hätten von den letzten Feuerwerken ja die Audio-Dateien und die manuell (von mir) bestimmten Zeitpunkte. Vielleicht könnte man auch Verfahren zum maschinellen Lernen mit diesen Daten testen.
| Prof. Dr. Stefan Brass | Impressum |