Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

Automaten und semistrukturierte Daten (XML)

Aktuelles   Einführung   Zeit & Raum   Literatur   Vortragsthemen   Vorträge   Programm   Ausarbeitungen

Aktuelles

An dieser Stelle finden Sie im Laufe des Seminars aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.

Programm

Das Seminar findet in Raum 1'308 des Erwin-Schrödinger-Zentrums statt und beginnt um 9:00 Uhr s.t.
Für jeden Vortrag sind 45 Minuten plus 10-15 Minuten für die anschließende Diskussion eingeplant.
Die Ausarbeitungen der einzelnen Vortragsthemen finden Sie hier.

Donnerstag, 24.02.05

Freitag, 25.02.05

Einführung

Automatentheoretische Methoden spielen eine vielfältige und sehr nützliche Rolle bei der Bearbeitung von semistrukturierten Daten. Zum einen lassen sich Schemainformation (d.h. Information über die Struktur), wie sie für XML etwa in Form von DTDs oder XML-Schema Spezifikationen vorliegen, mit Baumautomaten beschreiben und algorithmisch bearbeiten. Zum anderen bieten automatentheoretische Techniken vor allem speichereffiziente Verfahren zur Ausführung von Anfragen an sehr große XML-Dokumente.

Im Seminar werden Originalarbeiten und Buchabschnitte zum Thema behandelt. Vorausgesetzt werden gute Kenntnisse der theoretischen Informatik. Grundlegende Kenntnisse der Datenbanktheorie oder die Teilnahme an einer der Vorlesungen "Logik und Komplexität" oder "Logiken, Spiele und Automaten" sind sicherlich hilfreich, aber nicht unbedingt erforderlich.

Zeit und Raum

Das Seminar ist als Blockseminar organisiert und findet am 24.2 und 25.2.2005 jeweils ab 9:00 Uhr in Raum 1'308 des Erwin-Schrödinger-Zentrums statt.
Eine Vorbesprechung findet in der ersten Semesterwoche am Freitag, dem 22.10.2004, um 13:00 im Raum 4.410, Johann von Neumann Haus (RUD 25) statt.

Einführende Literatur

Der folgende Artikel ist obligatorischer Lesestoff für alle Seminarteilnehmer/innen:
[KSS] Nils Klarlund, Thomas Schwentick and Dan Suciu.
XML: Model, Schemas, Types, Logics, and Queries.
In Logics for Emerging Applications of Databases, Springer-Verlag, 2004, Seite 1-41.
Weitere Informationen finden sich (neben den u.g. Artikeln zu den einzelnen Vorträgen) in:
[Nev02] Frank Neven.
Automata, Logic, and XML.
Proceedings CSL'02, pp 2-26.
[Th73] James W. Thatcher.
Tree automata: An informal survey.
In: A. Aho (Ed.), Comments in the theory of computing, Prentice-Hall, 1973, pp 143-172.
[CDG+] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi.
Tree Automata Techniques and Applications.
Verfügbar unter http://www.grappa.univ-lille3.fr/tata.
[ABS] S. Abiteboul, P. Buneman und D. Suciu.
Data on the Web.
Morgan Kaufmann, San Francisco, CA, 2000.

Vortragsthemen

I. Klassische Theorie der Baumautomaten und Logik (MSO-Logik)

I.1.
t.b.a.
I.2.
Anne Brüggemann-Klein, Makoto Murata, Derick Wood.
Regular tree and regular hedge languages over unranked alphabets.
HKUST Theoretical Computer Science Center Research Report, HKUST-TCSC-2001-05.

II. Anfragebearbeitung

II.1.
Frank Neven und Thomas Schwentick.
Query automata over finite trees.
Theoretical Computer Science 275(1-2): 633-674 (2002).
II.2.
Georg Gottlob und Christoph Koch.
Monadic datalog and the expressive power of languages for Web information extraction.
Journal of the ACM 51(1): 74-113 (2004).
II.3.
Christoph Koch.
Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach.
Proceedings VLDB'03: pp 249-260.

Zum Thema "STAs" auch den entsprechenden Abschnitt in der folgenden Arbeit beachten:

Markus Frick, Martin Grohe, Christoph Koch:
Query Evaluation on Compressed Trees.
Proceedings LICS'03.

Beispiele und den Programmcode gibt es unter http://www.dbai.tuwien.ac.at/staff/koch/arb/.
II.4.
Todd J. Green, Gerome Miklau, Makoto Onizuka, Dan Suciu:
Processing XML Streams with Deterministic Automata.
Proceedings ICDT'03: pp 173-189.

Für Details siehe auch die Zeitschriftenversion:

Todd J. Green, Ashish Gupta, Gerome Miklau, Makoto Onizuka, Dan Suciu.
Processing XML Streams with Deterministic Automata and Stream Indexes.
ACM TODS, vol. 29, no. 4, December 2004.
II.5.
Christoph Koch und Stefanie Scherzinger.
Attribute Grammars for Scalable Query Processing on XML Streams.
Proceedings DBPL'03: pp 233-256
II.6.
Geert Jan Bex, Sebastian Maneth, Frank Neven.
A formal model for an expressive fragment of XSLT.
Information Systems 27(1): 21-39 (2002).

III. Schema-Sprachen und Validierung

III.1.
Dongwon Lee, Murali Mani, Makoto Murata.
Reasoning about XML Schema Languages using Formal Language Theory.
Technical Report, IBM Almaden Research Center, RJ# 10197, Log# 95071, 37 Seiten, Nov. 2000.
III.2.
Luc Segoufin und Victor Vianu.
Validating Streaming XML Documents.
Proceedings PODS'02: 53-64.

IV. Typüberprüfung

IV.1.
Tova Milo, Dan Suciu, Victor Vianu.
Typechecking for XML Transformers.
J. Comput. Syst. Sci. 66(1): 66-97 (2003).
IV.2.
Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu.
XML with data values: typechecking revisited.
J. Comput. Syst. Sci. 66(4): 688-727 (2003).

V. Tree-Walking Automaten

V.1.
Frank Neven und Thomas Schwentick.
On the power of tree-walking automata.
Information and Computation 183 (2003), pp 86-103.
V.2.
Mikolaj Bojanczyk und Thomas Colcombet.
A Regular Tree Language Not Recognized by Any Tree-Walking Automaton.
Manuskript, Juli 2004, 51 Seiten.

Vorträge

Thema Vortragende/r Ansprechpartner
I.1 Bettina Hepp Martin Grohe
I.2 Stephan Seigewasser Martin Grohe
II.1 (erste Hälfte) Yvonne Fischer Nicole Schweikardt
II.1 (zweite Hälfte) Alexandra Rostin Nicole Schweikardt
II.2 Peter Laufer Martin Grohe
II.4 Evgeniya Ershova Nicole Schweikardt
II.5 Matthias Schmidt Nicole Schweikardt
II.6 Stefan Deumlich Nicole Schweikardt
III.2 Marco Oppel Nicole Schweikardt
IV.1 Andreas Müller Martin Grohe
V.1 Jakob Voß Martin Grohe
V.2 Andreas Meyer Martin Grohe

Last modified: Mon Feb 28 15:14:07 CET 2005
Nicole Schweikardt