Rekursive Abfrage über semantisch angereicherte Datenbestände

Die Komplexität von Informationssystemen hat in den letzten Jahren bemerkenswert zugenommen, und mächtigere Werkzeuge sind nötig, um in vielen Anwendungsbereichen auf Daten zuzugreifen und diese zu verwalten. In diesem Zusammenhang ist speziell die Verwendung von Ontologien zur Beschreibung von komplexen konzeptuellen Schemata möglicherweise verteilter und heterogener Datenquellen sowie zum Zugriff auf die darin enthaltenen Daten ein sehr aktives Forschungsgebiet. Die meisten Anstrengungen zur Erreichung des Ziels gebrauchen Abfragesprachen für den Datenzugriff, die von Datenbanken inspiriert sind, und verwenden Beschreibungslogiken (DLs) zur formalen Beschreibung von Ontologien. Insbesonders wurden maßgeschneiderte ,,leichte`` DLs entwickelt wie die DL-Lite and EL Familien, hinreichend ausdrucksstark für viele Anwendungs- bereiche sind und gleichzeitig eine effiziente Abfrageauswertung über Datenquellen erlauben. Bisher betrachtete Abfragesprachen erlauben jedoch keine Rekursion, die eine fundamentale, in vielen Anwendungen sehr erwünschte Eigenschaft ist. Rekursion ist nötig um so natürliche Anfrage wie "ist a von b aus erreichbar" ausdrücken zu können. Daten im Web sind meist in semi-strukturierten Datenquellen gespeichert (wie HTML oder XML Dokumente), und grundlegende Zugriffs-mechanismen für diese Arten von Datenquellen sind Abfragen, die Rekursion nutzen um flexibel durch die Informationsstruktur zu navigieren und Knoten zu selektieren. Mit (beschränkten) Formen der Rekursion sind flexible und mächtige Abfragesprachen wie XPath entwickelt und erfolgreich in Anwendungen gebracht worden. Es wird nicht möglich sein, die verschiedenen Datenformate im Web zu überbrücken und Ontologien zu verwenden, um einen uniformen Zugang zu heterogenen Datenquellen zu ermöglichen, solange wir nicht geeignete Abfragesprachen haben die es erlauben, flexibel semi- strukturierte Daten zu navigieren und die effizient über DL Ontologien evaluiert werden können. Rekursive Abfragen sind im Kontext von Beschreibungslogiken nicht weiter betrachtet worden, was zum Teil auf einige negative Resultate zurück zu führen ist, die zeigen dass populäre Klassen von rekursiven Abfragen bereits über sehr ausdrucksschwachen DLs unentscheidbar sind. Vor kurzem wurde jedoch gezeigt, dass bestimmte Abfragen mit eingeschränkter Rekursion, die allerdings für einen Datenzugriff ähnlich wie in XPath ausreichend ist, auch über sehr ausdrucksstarken Beschreibungslogiken entscheidbar sind. Die Komplexität der Beantwortung dieser Abfragen über ,,leichten" DLs ist jedoch unerforscht. Dies ergibt die ermutigende Perspektive von möglicherweise mächtigen and noch unbekannten entscheidbaren Familien von rekursiven Abfragen über Ontologien in ,,leichten" DLs, die das Potential haben, die momentan verfügbaren Datenzugriffs-technologien dramatisch zu verbessern. Das vorliegende Projekt zielt darauf ab, solche Familien zu finden, ihre Berechnungskomplexität zu untersuchen und Algorithmen für sie zu entwickeln.

In diesem Projekt ging es darum, navigatorische Anfragen mit Rekursion für Ontologie-basierten Datenzugriff (OBDA) zu studieren. Die Forschung zu Ontologien, also maschinenlesbare Domainkonzeptualisierungen, hat in den letzten Jahren enorme Fortschritte erfahren und zu hochwertigen Ontologien geführt, die das Fachwissen aus Bereichen der Wissenschaft und Industrie zuverlässig erfassen. Diese Ontologien bieten viele neue Möglichkeiten und machen moderne Informationssysteme intelligenter. Insbesondere im OBDA Paradigma sind Datenquellen mit einer Ontologie verbunden, welche den Nutzern eine klare, konzeptionelle Sicht auf die Daten, die selbst unvollständig und heterogen sein können, bietet um entsprechende Anfragen zu stellen. In OBDA können die Nutzer nicht nur die Fakten, die in den (möglicherweise unvollständigen) Daten gespeichert sind, sondern auch potenziell implizite Konsequenzen, die durch die Daten und das Domainwissen impliziert werden, abrufen, und somit umfassendere Antworten auf Abfragen zu erhalten. Sowohl die theoretischen Grundlagen des OBDA, als auch die bestehenden Systeme für den Einsatz in der Praxis, haben sich in den letzten zehn Jahren dramatisch entwickelt.Das Hauptziel dieses Projekts war es, das OBDA-Paradigma über die zuvor betrachteten einfachen Abfragesprachen, welche vorwiegend auf konjunktive Abfragen (also die bekannte Klasse von select-project-join relationalen Algebra-Abfragen) begrenzt waren, hinaus zu interpretieren. Insbesondere haben wir in diesem Projekt Abfragen untersucht, die eine bestimmte Form der Rekursion ermöglichen, um somit natürliche Begriffe wie "erreichbar" auszudrücken und die Art der Navigation, die für die Abfrage von Daten im Web und andere Formen von grafischen Daten benötigt wird, zu unterstützen. Das Hauptziel bestand darin, flexiblere OBDA durch Abfragen mit Rekursion, wie regelmäßige Pfadabfragen (RPQs) und deren Erweiterungen, zu ermöglichen. Wir konnte zahlreiche Resultate zur Entscheidbarkeit und Komplexität, unter Berücksichtigung unterschiedlicher Kombinationen von Abfrage-Sprachen, die Rekursion unterstützen, verschiedenen Familien von Ontologie-Sprachen, und verschiedenen Abfrage-processing Services, zeigen. Weiters wurden Techniken, die den Weg zu praktikablen Algorithmen ebnen können, mit Schwerpunkt auf Übersetzungen, die die Wiederverwendung bestehender Datenbanktechnologien ermöglichen, entwickelt.