Optimierung der Verarbeitung von Dokumenten

Abstract

Wir haben Verfahren zur statischen und dynamischen Optimierung von Quellen und Transformationen entwickelt. Einige davon erforderten neue Umsetzungen dieser Grundbausteine, andere arbeiten mit bestehenden Umsetzungen zusammen. Durch Spezialisierung der Grammatik für wohlgeformtes XML anhand eines statisch bekannten Schemas gelingt es uns, die bisher separat erfolgenden Prüfungen auf korrekte Klammerung und Typkonformität in der Zerteilung zu subsumieren. Nach unserem Verfahren erzeugte Grammatiken sind mit verbreiteten Zereilergeneratoren kompatibel. Abstrakte Interpretation von Pfadausdrücken über einem statisch bekannten Eingabeschema kann die auftretenden Knotenmengen mit Hilfe von Kontexten einschränken. Diese Einschränkungen helfen uns, semantisch äquivalente, aber schneller ausführbare Ausdrücke zu bestimmen, die mit existierenden Umsetzungen ausgeführt werden können. Unsere Anwendung monotoner Datenflußrahmen auf Transformationen erlaubt Gesamtprogrammanalysen, welche sowohl den Datenfluß zwischen Teilausdrücken als auch den Kontrollfluß zwischen Regeln berücksichtigen. Die darauf aufbauende Optimierung liefert schnellere semantisch äquivalente Transformationen für bestehende Umsetzungen. Fauler Baumaufbau spart bei teilweisem Zugriff auf eine Quelle Speicherplatz und Re- chenzeit, indem nur die tatsächlich betretenen Teile als Datenstrukturen im Hauptspeicher aufgebaut werden. Schlüssel dazu sind die Schachtelungseigenschaften von XML. Analog berechnen faule Transformationen nur die jeweils dynamisch zugegriffenen Teile ihres Ergebnisses. Schlüssel dazu sind die Konfluenz von Transformationen und das Vorhandensein alternativer Auswertungsreihenfolgen. Wie beim faulen Baumaufbau sind auch hier neue Umsetzungen von Transformationen nötig. Wie erzielten wir diese Fortschritte? Unsere formalen Modelle schlagen eine Brücke zwischen dem Anwendungsgebiet XML und den Disziplinen der Programmanalyse, der Optimierung und der formalen Sprachen. Aber erst unsere neuartigen Analyserepräsentationen machen sie auch tragfähig. Die ausführliche Version dieser Arbeit zeigt, daß die Brücke zweispurig ist. Ich hoffe, diese kurze Zusammenfassung hat Appetit auf mehr geweckt. Literatur [ASU86] Aho, A. V., Sethi, R., und Ullman, J. D.: Compilers: Principles, Techniques, and Tools. Addison Wesley. 1986. [NNH99] Nielson, F., Nielson, H. R., und Hankin, C. L.: Principles of Program Analysis. Springer- Verlag. 1999. [Sc02] Schmelzer, R.: Breaking xml to optimize performance. Technical report. ZapThink LLC.