Rundgespräch "Theorie und Anwendung semistrukturierter Daten"

Zusammenfassungen

Stephan Kepser: Ein Beweis für die Turing-Vollständigkeit von XSLT

XSLT entstand ursprünglich aus XSL, um eine Möglichkeit zur Anzeige von XML Dokumenten zu schaffen. Eines der Designziele von XML war die Trennung der Struktur von Daten von der Art und Weise, wie diese präsentiert werden. Entsprechend beinhaltet XML nur strukturelle Information, keine Formatierungsanweisungen. Um ein solches Dokument nun in einem Standardbrowser anzuzeigen, ist es natürlich notwendig, die Strukturinformation in Formatierungskommandos (in HTML) zu übersetzen. Dies ist der ursprüngliche Zweck von XSL(T). XSLT wuchs jedoch schrittweise zu einer allgemeinen XML-Transformationssprache heran, die heute hauptsächlich zur Abfrage und Transformation von XML Dokumenten verwendet wird. Daher ist es eine interessante und wichtige Frage, die Ausdrucksstärke von XSLT zu bestimmen. Das Resultat, daß XSLT Turing-vollständig ist, scheint in der XSLT-Programmierergemeinde Folklore zu sein. Es gibt aber wohl keinen einschlägigen Beweis dafür. Unser Beitrag besteht damit darin, einen (hoffentlich) simplen und durchsichtigen Beweis zu liefern und das Resultat dadurch abzusichern.

Stephan Kepser: Linguistische Datenbanken

Man kann grob drei große Abteilungen von linguistischen Datenbanken unterscheiden: Relationale Datenbanken, Lexika und Corpora. Relationale Datenbanken kommen in der Linguistik etwa bei typologischen Projekten zum Einsatz, sind aber natürlich vollstrukturierte Daten. Lexika weisen oft große Variationen zwischen den einzelnen Einträgen auf, sind zunehmend multimodal und multimedial und insofern ein Paradebeispiel für semistrukturierte Daten. Doch Corpora bilden den Schwerpunkt der semistrukturierten Daten in der Linguistik. Ein Corpus ist eine Sammlung elektronisch verfügbarer Texte (ein- und mehrsprachig), etwa Zeitungen, Bücher oder auch Transkriptionen von Tonbandaufnahmen. Die Annotation eines Corpus ist die Anreicherung der "Rohdaten" mit Informationen wie z.B. der Dokumentanstruktur, den Wortarten oder gar kompletten syntaktischen Analysen. Sie erfolgt heute oft noch von Hand, da sich insbesondere komplexere Aufgaben wie korrekte syntaktische Annotation (noch) nicht automatisieren lassen. Die Annotation der Dokumentenstruktur und der Wortarten erfolgt dagegen schon häufig automatisch. Zur Vereinheitlichung von Annotationen gibt es viele Standarisierungsinitiativen. Als Format setzt sich mehr und mehr XML durch, wenn auch zu beobachten ist, das Microsoft Word mangels weiterreichender Erfahrung der Linguisten vielfach noch Verwendung findet. Die Abfrage der Annotationen in Corpora steckt noch in den Kinderschuhen. Zum Teil werden Werkzeuge, die Baumstrukturen abfragbar machen erst heute entwickelt. Auch fehlt den Linguisten als Benutzern noch die Übung damit. So wird vielfach einfach nur nach Strings gesucht. Der Mehrwert der Annotation muß also erst noch erreichbar gemacht werden.

Michael Kraus: Stylesheets for Context Adaption

Context adaptation of web contents is nowadays necessary because of the various devices used (especially mobile phones and PDA) and the advanced applications (such as contextual web services) the market is seeking for. Adaptation of web contents to various devices (such as standard size screens vs. PDA) and adaptation to various contexts (such as user profile, time, or location) do not differ in the techniques they require. In the following, proposals are made for enhancing existing standards with adaptation capabilities that consist in minimal conservative changes of the existing standards.

(Joint work with François Bry)

Henning Lobin: Dokumentgrammatiken und die Semantik generischer Dokumente

Abstract in PDF

Wolfgang May: Dokumentmanipulation und -integration in XML

XPathLog ist eine Datalog-artige Erweiterung von XPath als Anfrage-, Datenmanipulations- und -integrationssprache für XML-Daten. Dabei wird XPath um Variablenbindungen erweitert, bei denen die im Zuge der Auswertung eines XPath-Ausdrucks durchquerten XML-Knoten etc. an Variablen gebunden werden können. Dabei können Variablen sowohl an Literale und Knoten, als auch an Namen gebunden werden, um Anfragen auf Daten- sowie Schemaebene stellen zu können. Variablenbindungen können entweder als Antworten ausgegeben werden, oder an den Regelkopf weitergegeben werden um Änderungen an der Datenbasis auszuführen. Im Gegensatz zu anderen Ansätzen wird dabei XPath-Syntax und Semantik auch zur deklarativen Spezifikation von Änderungen verwendet: XPath-Ausdrücke im Regelkopf erhalten eine konstruktive Semantik, indem sie als Beschreibung der Elemente und Attribute, die der Datenbank hinzugefügt werden sollen, interpretiert werden.

Die Einschränkung, dass XML auf einem baumartigen Datenmodell basiert hat dabei direkte Auswirkungen auf die Semantik von Änderungsoperationen: Wenn eine Änderung spezifiziert, dass ein (durch eine Anfrage) erhaltener Teilbaum einer XML-Instanz an einer bestimmten Stelle eingefügt werden soll, mu"s dieser Teilbaum kopiert werden. Damit ergibt sich die Frage, ob Referenzen, die in den originalen Teilbaum zeigen, angepasst werden sollen; es ist nicht möglich, denselben Teilbaum ein zweites Mal einzubinden (wie in graphbasierten Modellen wie z.B. OEM oder F-Logic). Wenn man Datenintegrationsprobleme, wie etwa die Restrukturierung von XML-Instanzen, das Verschmelzen von Knoten aus verschiedenen Bäumen, oder Synonyme betrachtet, wird dieses Problem noch deutlicher.

Aus diesem Grund verwendet XPathLog - und die Implementierung in LoPiX - intern ein graphbasiertes, an den Kanten markiertes Datenmodell, das als XTreeGraph bezeichnet wird. Der XTreeGraph erweitert das bekannte XML-Datenmodell indem mehrere überlappende Bäume modelliert werden können, und somit die skizzierten Änderungs- und Integrationsoperationen unterstützt werden. Zur Integration verschiedener XML-Bäume wird aus den Eingabebäumen ein interner XTreeGraph erzeugt, auf dem die Ergebnisbäume durch Projektion als XML-Sichten definiert werden.

Die "reine" XPathLog-Sprache bietet damit eine intuitive Datalog-artige Erweiterung von XPath zu einer Anfrage-, Datenmanipulations- und -integrationssprache, deren Syntax und Semantik eng an den bekannten XPath-Standard anknüpft. Spracherweiterungen bieten zusätzlich eine Klassenhierarchie (mit nichtmonotoner Wertvererbung), ein einfaches Konzept zur Beschreibung des Datenbankschemas (der zur Definition von XML-Views über dem XTreeGraph verwendet wird), sowie den Zugriff auf weitere Datenquellen im Web während der Auswertung eines Programms. Die Flexibilität und Ausdruckskraft der vollen XPathLog-Sprache erlaubt eine kombinierte Behandlung von Daten, Schemadaten, sowie semantischen Metadaten, wie z.B. Annotierungen und Ontologien.
Projektseite

Holger Meuss: Indexstrukturen für semistrukturierte Daten

Indexstrukturen dienen dem effizienten Auswerten von Anfragen an persistente Daten durch gezielten Zugriff auf relevante Teile der Datenbank. In diesem Vortrag werden speziell für semistrukturierte Daten entwickelte Indexstrukturen kurz vorgestellt und verglichen. Durch die besonderen Eigenschaften semistrukturierter Daten, ihre Irregularität und das zugrundeliegende Graphmodell, eignen sich die für relationale oder objektorientierte Speicherung entwickelten Indexstrukturen nicht direkt für semistrukturierte Daten.

Die vorgestellten Ansätze sind meist von Indexstrukturen aus dem Information Retrieval (IR) oder relationalen Datenbanken inspiriert. Für den Vortrag wurden sie nach dem "Indexanker" kategorisiert, d.h. geschieht der Zugriff primär über (1) Inhalt, (2) Struktur oder (3) beidem. Inhaltsbasierte Indexstrukturen knüpfen sehr eng an IR-Indexstrukturen wie invertierte Files oder Signaturfiles an und erweitern sie um strukturelle Information. Strukturbasierte Indexstrukturen (a) übertragen entweder im Datenbankbereich etablierte Sekundärspeichertopologien, wie z.B. B-Bäume, auf die Graph- oder Baumstruktur semistrukturierter Daten oder (b) extrahieren aus dem Datenbankgraph eine konzise Beschreibung, den Indexgraph, der als Grundlage bei der Anfrageauswertung genutzt wird. Bestehende Mischansätze zwischen text- und strukturbasierten Indexstrukturen erweitern entweder (a) invertierte Files oder (b) Ansätze, die auf Indexgraphen basieren.

Dan Olteanu: Rules for Efficient Streamed XPath Evaluation

The location path language XPath is of particular importance for XML applications since it is a core component of many XML processing standards such as XSLT or XQuery. This work shows how, based on axis symmetry of XPath, equivalences of XPath 1.0 location paths involving reverse axes, such as ancestor or preceding, are established. These equivalences are used as rewriting rules in an algorithm for transforming location paths with reverse axes into equivalent reverse-axis-free ones. The rules are classified into two rule sets, a general one and a specific one. The general rule set treats the removal of reverse axes in the same way, regardless of the specificity of each axis. Contrary, the specific set considers the interaction of each reverse axis with each forward axis. Using the general rules, the equivalent rewritten location path has the length and can be computed in a time linear in the length of the initial location path and it adds as many identity-based joins as reverse steps are in the initial location path. Using the specific rules, the equivalent rewritten location path has the length and can be computed in a time exponential in the length of the initial location path, in the worst case, but does not add any extra joins.

Furthermore, the class of XPath 1.0 location paths with reverse axes that can not be rewritten with the above mentioned rules is syntactically characterised and it is shown how it can be rewritten using variables within XPath 2.0 or XQuery 1.0.

Location paths without reverse axes, as generated by the presented rewriting algorithm, enable efficient SAX-like streamed data processing of XPath.

(Joint work with Holger Meuss, Tim Furche, and François Bry)

Sebastian Schaffert: XL: A Rule-Based Query and Transformation Language

The growing importance of XML as a data interchange standard demands languages for data querying and transformation. Since the mid 90es, several such languages have been proposed that are inspired from functional languages (such as XSLT) and/or database query languages (such as XQuery). This paper addresses applying logic programming concepts and techniques to designing a declarative, rule-based query and transformation language for XML and semistructured data.

The paper first introduces issues specific to XML and semistructured data such as the necessity of flexible "query terms" and of "construct terms". Then, it is argued that logic programming concepts are particularly appropriate for a declarative query and transformation language for XML and semistructured data. Finally, a new form of unification, called "simulation unification", is proposed for answering "query terms", and it is illustrated on examples.

(Joint work with François Bry)

Helmut Seidl: Automata Theory for Document Processing

In dem Vortrag gebe ich eine Übersicht über allgemeine automaten-theoretische Hintergründe für die Behandlung semi-strukturierter Daten. Insbesondere behandle ich verschiedene Klassen von Bäumen, zugehörige Automaten-Modelle und die Komplexität grundlegender Entscheidungs-Verfahren.

Christian Strohmaier: Wrapper Tools and Other Methods of Structure Acquisition

<?xml version="1.0" encoding="ISO-8859-1" ?>

<talk>
<title lang="en">Wrapper Tools and other Methods of Structure Acquisition</title>
<author>Christian M. Strohmaier</author>

Die Voraussetzung, um strukturierte Dokumente transformieren, weiterverarbeiten oder anfragen zu können ist, dass die Dokumente wie dieser Abstract in einem deskriptiven Format vorliegen. Da aber heute der Löwenanteil aller Dokumente (noch) nicht in dieser Form verfügbar ist, stehen Werkzeuge zur Strukturakquisition im Forschungsinteresse. Ausgehend von einer Formatklassifikation werde ich einen Überblick zu verschiedenen Werkzeugfamilien aus verschiedenen Communities geben. Im Zentrum dieses Vortrags stehen Wrapper-Tools, deren Zielsetzung die Überführung von HTML-Dokumenten in XML-Dokumente ist.

</abstract>
</talk>

Holger Meuss

Last modified: Wed Apr 10 11:12:26 MEST 2002