Rekursive Abfrage über semantisch angereicherte Datenbestände

01.01.2012 - 30.09.2016
Forschungsförderungsprojekt
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.

Personen

Projektleiter_in

Institut

Förderungsmittel

  • Fonds zur Förderung der wissenschaftlichen Forschung (FWF) (National) Fonds zur Förderung der wissenschaftlichen Forschung (FWF) Fördergeber Typ Forschungsförderungsinstitutionen

Forschungsschwerpunkte

  • Information and Communication Technology

Schlagwörter

DeutschEnglisch
AnfragesprachenQuery Languages
Wissensrepräsentation und SchliessenKnowledge Representation and Reasoning
KomplexitaetComputer Complexity
Logik und DatenbankenLogic and Databases