Regular Rooted Graph Grammars

In dieser Arbeit wir ein pragmatischer Ansatz zur Typisierung,
statischen Analyse und Optimierung von Web-Anfragespachen, speziell
Xcerpt, untersucht. Pragmatisch ist der Ansatz in dem Sinne, dass
dem Benutzer keinerlei Einschränkungen aus Entscheidbarkeits- oder
Effizienzgründen auf modellierbare Typen gestellt werden. Effizienz
und Entscheidbarkeit werden stattdessen, falls nötig, durch
Vergröberungen bei der Typprüfung erkauft. Eine Typsprache zur
Typisierung von Graph-strukturierten Daten im Web wird eingeführt.
Modellierbare Graphen sind so genannte gewurzelte Graphen, welche
aus einem Spannbaum und Querreferenzen aufgebaut sind. Die
Typsprache basiert auf reguläre Baum Grammatiken, welche um
typisierte Referenzen erweitert wurde. Neben wie im Web mit XML
üblichen geordneten strukturierten Daten, sind auch ungeordnete
Daten, wie etwa in Xcerpt oder RDF üblich, modellierbar. Der dazu
verwendete Ansatz---ungeordnete Interpretation Regulärer
Ausdrücke---ist neu. Eine operationale Semantik für geordnete wie
ungeordnete Typen wird auf Basis spezialisierter Baumautomaten und
sog. Counting Constraints (welche wiederum auf
presburgerarithmetische Ausdrücke) basieren. Es wird ferner
statische Typ-Prüfung und -Inferenz von Xcerpt Anfrage- und
Konstrukttermen, wie auch Optimierung von Xcerpt Anfragen auf Basis
von Typinformation eingeführt.