[dbis logo]

.Forschung.Projekte
[Institut fuer Informatik] [Leerraum] [Humboldt-Universitaet zu Berlin]

Verweisbasierte Anfrageausführung - Ein neuartiger Ansatz für Anfragen über dem Web of Linked Data

Derzeit befindet sich des World Wide Web in einer Transformationsphase von einem Hypertext-Web zu einem Web des Hypertext und der Daten. Web-Dokumente werden im Rahmen dieses Prozesses nicht verschwinden. Stattdessen werden sie, neben ihrer bisherigen Rolle, Texte und andere Medieninhalte in einer für menschliche Nutzung aufbereiteten Form zu übermitteln, zukünftig auch der standardisierten Veröffentlichung von Daten auf Basis eines einheitlichen Datenmodells dienen. Die Veröffentlichungsprinzipien, welche auf etablierten Web-Technologien wie HTTP (Hypertext Transfer Protocol) und URIs (Uniform Resource Identifier) beruhen, verlangen, die jeweils angebotenen Daten mit weiteren Daten im Web zu verknüpfen. Die hierfür angewandten Datenverweise sind vergleichbar mit den bekannten Verweisen zwischen Web-Dokumenten, erlauben es jedoch, auf einer konzeptionell tieferen Ebene in die Daten einer Web-Datenquelle direkt auf deren Daten über eine bestimmte Entität zu verweisen. Entsprechend entsteht mit dem Web der Daten ist ein riesiger Datenraum, welcher Daten verschiedenster Anbieter miteinander verbindet. Auf Basis dieses Datenraums entstehen faszinierende, neuartige Möglichkeiten für Web-basierte Anwendungen. Daten verschiedenster Anbieten können miteinander kombiniert werden, lückenhafte Informationen unterschiedlicher Quellen können zu einer vollständigeren Sicht integriert werden, scheinbar widersprüchliche Informationen können gemeinsam analysiert und weiterverarbeitet werden.

 

Um das Potential des Web der Daten in Anwendungen nutzbar zu machen, beschäftigen wir uns in diesem Projekt mit einer Möglichkeit, deklarative (SQL-ähnliche) Anfragen über dem Web auszuführen. Hierbei steht die Frage im Mittelpunkt, wie das Web der Daten als eine riesige, global verteilte Datenbank aufgefasst und angefragt werden kann. Aus dieser Sichtweise ergeben sich neuartige Herausforderungen, welche in existierenden Ansätzen der Anfragebearbeitung in verteilten Szenarien keine Rolle spielen. Der grundlegendste Unterschied besteht in dem fehlenden Wissen über die Existenz und den Inhalt von Daten, welche potentiell zur Beantwortung einer Anfrage herangezogen werden können. Deshalb beruht der, im Rahmen des Projektes angewandte, verweisbasierte Ansatz zur Anfrageausführung nicht auf traditionellen Ansätzen der Anfrageverteilung. Stattdessen werden explizit die Charakteristika des Web -insbesondere die Existenz von Datenverweisen- ausgenutzt.

 

Die Idee der verweisbasierten Anfrageausführung (engl.: link traversal based query execution) ist es, die Anfrageauswertung mit dem Verfolgen von Datenverweisen zu kombinieren und somit potentiell relevante Daten während der Ausführung zu entdecken. Hierbei werden jeweils abwechselnd Teile der Anfrage über einer lokalen Datenmenge ausgewertet und die, durch entsprechend bestimmte Zwischenergebnisse repräsentierten Datenverweise zur Erweiterung der lokalen Datenmenge genutzt. Während so die Anfrageergebnisse aus der sukzessiven Ergänzung von Zwischenergebnissen um Teillösungen für die verschiedenen Anfrageteile entstehen, wächst die Menge der heruntergeladenen, potentiell relevanten Daten und damit ergibt sich die Möglichkeit weitere Teillösungen zu bestimmen. Ein grundlegendes Merkmal der Idee ist, dass während des skizzierten Vorgangs nicht beliebige Datenverweise in den entdeckten Daten verfolgt werden. Stattdessen wird das Web mittels der, durch Zwischenergebnisse repräsentierten Verweise gezielt traversiert. Aufgrund der rekursiven Natur des Ansatzes ist jedoch nicht immer eine zumutbare Zeit bis zum Abschluss der vollständigen Abarbeitung garantiert. Unter einer Unendlichkeitsannahme für das Web der Daten, kann für einige Anfragen nicht einmal garantiert werden, ob die Bearbeitung terminiert. Weiterhin ist es selbst im Fall der vollständigen Rekursion möglich, dass korrekte Anfrageergebnisse nicht gefunden werden, da auf Grund fehlender Verweise relevante Daten nicht entdeckt werden. Entsprechend stellt sich bei der verweisbasierten Anfragebearbeitung die Frage nach Ansätzen möglichst vollständige Ergebnismengen mit einem möglichst geringen Aufwand zu finden.

 

Im Rahmen der Entwicklung des Anfragesystems SQUIN untersuchen wir einen Ansatz die verweisbasierte Anfragebearbeitung umzusetzen und dabei eine eingeschränktere Ergebnismenge zu Gunsten einer vorhersagbaren und möglichst effizienten Realisierung zu tolerieren. Dieser Ansatz beruht auf der Idee einer iteratorbasierten Pipeline, wie sie auch im Rahmen klassischer Anfragebearbeitung häufig eingesetzt wird. Hierbei kommt eine Kette von Iteratoren zur Anwendung, bei der jeder Iterator für einen Anfrageteil zuständig ist, wodurch sich explizit eine feste Auswertungsreihenfolge ergibt.

ERROR: Content Element type "page_php_content_pi1" has no rendering definition!

Publikationen

ERROR: Content Element type "page_php_content_pi1" has no rendering definition!



[Punkt]  DFG-Forschergruppe Stratosphere

[Punkt]  DFG-Graduate School SOAMED

[Punkt]  DFG-Graduate School METRIK

[aktiver Punkt]  Verweisbasierte Anfrageausführung

[Punkt]  Web of Trusted Data

[Punkt]  Query Optimization in RDF Databases

[Punkt]  DBnovo - Datenbankgestützte Online Sequenzierung



Ansprechpartner