XML: Anfrage- und Transformationssprachen
Seminar
Sommersemester 2001

Veranstalter

Termin

Themenvorschläge

Grundlagen

XML.
XML (eXtensible Markup Language) entwickelt sich zu einem Standard zur Repräsentation von Daten im Web. Dies vor allem weil: XML [1] stellt Daten als Bäume dar. Baum-Knoten werden hierbei als Elemente bezeichnet und sind ggf. durch Attribute annotiert. Auch Textelemente sind möglich. Durch Document Type Definitions (DTDs) lässt sich die Struktur von XML-Dokumenten beschreiben. Dieser Vortrag soll als Einführung in XML dienen.
WML.
WAP ist der de-facto-Standard in den Bereichen Internetkommunikation, Telekommunikationdienste für digitale und mobile Anwendungen, Pager, PDAs (personal digital assistants) und weitere drahtlose Endgeräte. WML ist eine auf XML basierende Auszeichnungssprache, die speziell zur Spezifikation von Benutzerschnittstellen dieser Geräte sowie zur Darstellung des Inhalts von Nachrichten gedacht ist.
XML Schema.
XML Schemas [2] bieten die Möglichkeit ein verteiltes Vokabular auszudrücken. Mit XML Schema wurde neben den DTDs ein weiteres Mittel zur Auszeichnung bestimmter Klassen von XML-Dokumenten geschaffen. Dieses erlaubt die Definition der Struktur, des Inhalts und der Semantik von XML-Dokumenten mittels noch umfangreicheren Bedingungen. Außerdem geschieht die Formulierung in XML selbst. Die XML Schema-Spezifikation besteht aus zwei Teilen, Definition von Strukturen [3] und Definition von Datentypen (Komplexe Datentypen, Elemente und Attribute) [4].

Anfragesprachen

XSL.
Neben Cascading Style Sheets (CSS) gibt es eine weitere, flexiblere Möglichkeit, die Darstellung von XML-Dokumenten zu spezifizieren: mit Hilfe der Extensible Stylesheet Language (XSL) [5]. XSL besteht aus zwei Teilen -- der Sprache XSL Transformations (XSLT) [6][7] zur Transformation von XML-Bäumen und einem Vokabular XSL Formatting Objects (XSL FO) zur Spezifikation von Formatierungen.

XML-Dokument-Teile werden in XSLT durch die Teilsprache XPath [8] adressiert.

Quilt.
Quilt [9][10] ist ein Vorschlag für eine funktionale XML-Anfragesprache, die Konzepte von einigen früheren XML-Anfragesprachen vereinheitlicht, und die vielseitige Verwendbarkeit von XML ausnutzt. Es ermöglicht auch, Informationen von verschiedenen Datenquellen (strukturierte und semi-strukturierte Dokumente, relationale und objektorientierte Datenbanken) zu einem neustrukturierten Ergebnis zu kombinieren. Eingabe und Ausgabe sind XML-Dokumente, Teile von XML-Dokumenten oder eine Sammlung von XML-Dokumenten.
XQuery.
Mit einer Anfrage der Anfragesprache XQuery [11] ist es möglich, das Ganze oder Teile eines XML-Dokuments auszuwählen, so daß bestimmte Bedingungen in bezug auf den Inhalt oder die Struktur erfüllt sind -- genauso wie es mit SQL möglich ist, Anfragen an eine relationale Datenbank zu stellen.

Formal wurde ein Datenmodell für XML-Dokumente [12] festgelegt, das der Anfragesprache zugrunde liegen soll, und in bezug darauf eine Algebra von Anfrage-Operationen axiomatisiert [13][14].

TQL.
Die Ambient Logic ist eine Modallogik zur Beschreibung von strukturellen und funktionalen Eigenschaften des verteilten und mobilen Rechnens. Da die Ambient Logic von ihrer Struktur her eine Logik über Bäumen ist, kann sie ebenso als Grundlage für eine Anfragesprache auf Semistructured Data dienen -- vergleichbar mit der Prädikatenlogik als Grundlage für relationale Anfragesprachen. Die Anfragesprache TQL [15][16] für Semistructured Data, wie etwa XML, und ihr Ausführungsmodell wurden basierend auf der Ambient Logic entwickelt.

Transformationssprachen

HaXmL.
HaXmL [17] steht für eine Sammlung von Haskell-Programmen zur Verarbeitung von XML-Dokumenten. Hierzu gehören ein Parser für XML, eine spezieller Parser für HTML und ein Pretty-Printer zur Ausgabe von XML-Dokumenten. Darüber hinaus bietet HaXmL zwei Ansätze, um Dokumente zu verarbeiten.

Der erste Ansatz verwendet eine allgemeine Baumstruktur zur Darstellung von XML-Dokumenten. Zur Verarbeitung der XML-Bäumen wird eine Kombinator-Bibliothek bereitgestellt, die deren einfache Auswahl, Generierung und Transformation erlaubt.

Der zweite Ansatz übersetzt XML-DTDs in algebraische Datentypen für Haskell mit entsprechenden Ein- und Ausgabefunktionen.

XDuce.
XDuce [18] ist eine getypte Programmiersprache zur Verarbeitung von XML-Daten. XML-Dokumente lassen sich als XDuce-Werte einlesen, dann bearbeiten, und das Resultat wieder als XML-Dokument ausgeben. Da XDuce ein statisches Typsystem besitzt, können zur Laufzeit nie Typfehler auftreten -- jedes auftretende Dokument entspricht seinem spezifizierten Typ.

Besonderheiten der Sprache sind spezielle Typen, die den regulären Ausdrücken der DTDs entsprechen [19], ein mächtiger Subtypenbegriff und Musteranpassung (pattern matching) [20].

XMlambda.
XMlambda [21] ist eine kleine funktionale Programmiersprache mit XML-Dokumenten als Basis-Datentypen zur Generierung und Filterung von XML-Daten. Die Sprache besitzt ein statisches Typsystem mit Typinferenz. Das Typsystem garantiert, dass alle zur Laufzeit auftretenden Werte ihren DTDs entsprechen und viele Typannotationen unnötig werden. Viele Entwurfsmuster sind einfach ausdrückbar, da die Sprache Funktionen höherer Ordnung und polymorphe Funktionen unterstützt. Eine Form von Pattern matching ist ebenso vorhanden.

XMlambda basiert auf einer neuen Variante bekannter Record-Kalküle -- genannt type-indexed rows (TIR) [22] --, in der Typen anstelle von speziellen Feldnamen die Rolle von Record-Indizes übernehmen.

Speichersysteme

Der Hauptbeitrag in dieser Richtung ist in der Wiederverwendung vorhandener Datenbankverwaltungsysteme (relationale, objektorientierte) zu finden, mit dem Ziel die XML-Daten möglichst effizient abzuspeichern. Es gibt auch einige Versuche, um XML-Informationen in sogenannten XML-nativen Speichersystemen zu speichern, d.h., ohne sie in andere Formate umwandeln zu müssen. Wir schlagen folgende Speichersysteme als Themen für das Seminar vor:
Relational Storage of XML Data.
[23][24]
eXcelon.
[25]
TAMINO.
[26]
Oracle Support for XML.
[27]

References

 [1]
Tim Bray, Jean Paoli, C. M. Sperberg-McQueen, and Eve Maler. Extensible markup language (XML) 1.0 (second edition), W3C recommendation. http://www.w3.org/TR/REC-xml, October 2000.
 [2]
David C. Fallside. XML schema part 0: Primer, W3C candidate recommendation. http://www.w3.org/TR/xmlschema-0, October 2000.
 [3]
Henry S. Thompson, David Beech, Murray Maloney, and Noah Mendelsohn. XML schema part 1: Structures, W3C candidate recommendation. http://www.w3.org/TR/xmlschema-1, October 2000.
 [4]
Paul V. Biron and Ashok Malhotra. XML schema part 2: Datatypes, W3C candidate recommendation. http://www.w3.org/TR/xmlschema-2, October 2000.
 [5]
Sharon Adler, Anders Berglund, Jeff Caruso, Stephen Deach, Paul Grosso, Eduardo Gutentag, Alex Milowski, Scott Parnell, Jeremy Richman, and Steve Zilles. Extensible stylesheet language (XSL), version 1.0, W3C candidate recommendation. http://www.w3.org/TR/xsl, November 2000.
 [6]
James Clark. XSL transformations (XSLT), version 1.0, W3C recommendation. http://www.w3.org/TR/xslt, November 1999.
 [7]
Phil Wadler. A formal semantics of patterns in XSLT. In Markup Technologies '99 Conference Proceedings (Philadelphia). GCA, 1999.
 [8]
James Clark and Steve DeRose. XML path language (XPath), version 1.0, W3C recommendation. http://www.w3.org/TR/xpath, November 1999.
 [9]
Don Chamberlin, Daniela Florescu, and Jonathan Robie. Quilt: An XML query language for heterogeneous data sources. In Proceedings of WebDB, Dallas, TX, May 2000.
 [10]
D. Chamberlin. Quilt description site. Available at http://www.almaden.ibm.com/cs/people/chamberlin/quilt.html, 2000.
 [11]
Don Chamberlin, Daniela Florescu, Jonathan Robie, Jérôme Siméon, and Mugur Stefanescu. XQuery: A query language for XML. http://www.w3.org/TR/xquery, February 2001.
 [12]
Mary Fernandez and Jonathan Robie. XML query data model, W3C working draft, May 2000. http://www.w3.org/TR/query-datamodel.
 [13]
Peter Fankhauser, Mary Fernández, Ashok Malhotra, Michael Rys, Jérôme Siméon, and Philip Wadler. The XML query algebra, W3C working draft, December 2000. Working Draft, http://www.w3.org/TR/query-algebra.
 [14]
Mary Fernandez, Jérôme Siméon, and Philip Wadler. A semi-monad for semistructured data. In Jan Van den Bussche and Victor Vianu, editors, Database Theory - ICDT 2001, 8th International Conference, Proceedings, volume 1973 of Lecture Notes in Computer Science, pages 263-300, London, UK, January 2001. Springer-Verlag.
 [15]
Luca Cardelli. Semistructured computation. In Proceedings of the Seventh International Workshop on Data Base Programming Languages (DBPL), Kinloch Rannoch, Scotland, September 1999.
 [16]
Luca Cardelli and Giorgio Ghelli. A query lamguage for semistructured data based on the ambient logic. Draft, Preliminary Version, April 19, 2000, ftp://ftp.di.unipi.it/pub/Papers/ghelli/TQLFullDraft.ps.
 [17]
Malcolm Wallace and Colin Runciman. Haskell and XML: Generic combinators or type-based translation? In Peter Lee, editor, Proc. International Conference on Functional Programming 1999, pages 148-259, Paris, France, September 1999. ACM Press, New York.
 [18]
Haruo Hosoya and Benjamin C. Pierce. XDuce: A typed XML processing language (preliminary report). In Proceedings of Third International Workshop on the Web and Databases (WebDB2000), pages 111-116, 2000.
 [19]
Haruo Hosoya, Jérôme Vouillon, and Benjamin C. Pierce. Regular expression types for XML. In Philip Wadler, editor, Proc. International Conference on Functional Programming 2000, pages 11-22, Montreal, Canada, September 2000. ACM Press, New York.
 [20]
Haruo Hosoya and Benjamin C. Pierce. Regular expression pattern matching for XML. In POPL2001 [28], pages 67-80.
 [21]
Erik Meijer and Mark Shields. XMlambda: A functional language for constructing and manipulating XML documents. (Draft), http://www.cse.ogi.edu/ mbs/pub/xmlambda/xmlambda.ps, 1999.
 [22]
Mark Shields and Erik Meijer. Type-indexed rows. In Nielson [28], pages 261-275.
 [23]
Albrecht Schmidt, Martin Kersten, Menzo Windhouwer, and Florian Waas. Efficient relational storage and retrieval of xml documents. In Proceedings of WebDB, Dallas, TX, May 2000.
 [24]
D. Florescu and D. Kossmann. Storing and querying xml data using an rdbms. D. Florescu and D. Kossmann. Storing and querying XML data using an RDBMS. Data Engineering Bulletin, 22(3), 1999., 1999.
 [25]
Excelon Corporation. Objectstore. ObjectStore, Excelon Corporation, http://www.odi.com.
 [26]
Software AG. Tamino - an internet database system. Number 1777 in Lecture Notes in Computer Science, pages 383-387. Springer, 2000. http://www.tamino.com/.
 [27]
Oracle Corporation. Xml-enabled oracle. http://www.oracle.com/xml/.
 [28]
Hanne Riis Nielson, editor. Proc. 28th Annual ACM Symposium on Principles of Programming Languages, London, England, January 2001. ACM Press.