Seminar Logik und XML
Veranstalter: Prof. Carsten Lutz
S2, Modulbereich Theorie
Vorbesprechung: Mittwoch, 7.4., 14:00-16:00 MZH 3150
Ohne Teilnahme an der Vorbesprechung kann das Seminar nicht belegt werden.
Wer Interesse an dem Seminar hat, aber nicht zur Vorbesprechung kommen kann, meldet sich bis spätestens 9.4. per email.
Kurzbeschreibung
XML hat sich in den letzten Jahren zum dominierenden Standard für
den Datenaustausch im Web und darüber hinaus entwickelt. Im
Zusammenhang mit dieser Entwicklung wurde auch der theoretische
Hintergrund von XML eingehend untersucht. Wichtige Fragestellungen
sind z.B.:
- Wie groß ist die Ausdrucksstärke von Anfragesprachen (query languages) wie XPath und XQuery und wie kann sie charakterisiert werden?
- Wie schwierig ist das Auswertungsproblem für XPath/XQuery-Ausdrücke (gegeben einen XPath-Audruck und ein XML-Dokument, finde alle Knoten, die der XPath-Ausdruck selektiert) und mittels welcher Algorithmen kann es gelöst werden?
- Dieselben Fragen für andere Standardprobleme wie Query Containment und Query Equivalence (gegeben zwei XPath-Ausdrücke, entscheide ob sie für alle XML-Dokumente dieselbe Knotenmenge zurückliefen)
- Was sind die theoretischen Eigenschaften von Transformationssprachen wie XSLT?
Da ein XML-Dokument in natürlicher Weise als Baum aufgefasst
werden kann, stellt es aus der Sicht der theoretischen Informatik ein
wohlbekanntes Objekt dar. Diese Sicht erlaubt es insbesondere,
Sprachen wie XPath und XQuery als Logiken auf Bäumen aufzufassen.
Ein Großteil der Theorie zu XML und verwandten Formalismen basiert
auf dieser Sichtweise.
Das Ziel dieses Seminars ist es, die fundamentalen theoretischen
Grundlagen von XML, XPath und Co zu diskutieren und zu verstehen.
Dabei wird die Sichtweise als Logik auf Bäumen eine zentrale
Rolle spielen.
Voraussetzungen / Vorkenntnisse
Für viele (aber nicht alle) der Themen sind Grundkenntnisse in
Logik notwendig, wie sie etwa in der Logik-Vorlesung im WS09/10
vermittelt wurden.
Grundlegende Vorkenntnisse in Komplexitätstheorie, wie sie z.B.
in der Grundvorlesung Theoretische Informatik II vermittelt werden,
sind von Vorteil.
Organisation
Die Teilnehmer wählen während der Vorbesprechung ein Thema,
dass sie in einer 2er Gruppe bearbeiten. Zu jedem Thema gibt es einen
oder mehrere (englischsprachige) Aufsätze, die von den
bearbeitenden Teilnehmern zunächst gelesen und verstanden werden
sollen, wobei ihnen ein Betreuer zur Seite steht. Jede Gruppe fertigt
eine ca. 15-seitige, lesbare Ausarbeitung an, deren Form den Standards
wissenschaftlichen Arbeitens genügt. Am Ende des Semesters findet
ein Blockseminar statt, in dem jede Gruppe ihr Thema in einem Vortrag
den anderen Teilnehmern in verständlicher Weise darstellt. Die
Zeitplanung und das Vereinbaren von Terminen mit dem Betreuer
gehört zu den Aufgaben der Teilnehmer.
Ein Teil der Betreuung wird auf Englisch stattfinden.
Terminplan
| bis 16.4. |
Erstes Treffen mit dem Betreuer |
16.4.-9.5. |
Literatur lesen und verstehen, Unklarheiten mit dem Betreuer
diskutieren |
|
spätestens 10.5. |
Beginnen, an der Hausarbeit zu schreiben |
| 1.6. |
Abgabe der fertigen Hausarbeit |
| 9.6. |
Rückgabe der korrigierten Hausarbeit durch den Betreuer |
| 23.6. |
Abgabe der endgültigen Hausarbeit und Vorlage der ersten Version der
Folien für den Vortrag
|
| 7.7. | Vortrag |
Themenvorschläge
Im folgenden die Liste der vorgeschlagenen Themen. Die dazugehörige
Literatur findet sich in Stud.IP.
- Query Containment in Fragmenten von XPath
- Der Zusammenhang von XPath und FOL
- Ausdrucksstärke und Abschlusseigenschaften von XML
- Die Verarbeitung von XML-Datenströmen mit endlichen Automaten
- XML Publishing: von SQL nach XML
AG Theorie der künstlichen Intelligenz