Verteiltes Heterogenes Stream Schliessen

Mit der Entwicklung des World-Wide Web und der resultierenden Verbindung von Daten ist verteilte Berechnung für Informationssysteme wichtig geworden. Um Anwendungen in verteilten, heterogenen Umgebungen zu ermöglichenwo Information oft unvollständig istbenötigen Agenten Komponenten zur intelligenten Entscheidungsfindung (IDMCs), die höhere und komplexe Schlussprobleme lösen können. Die zunehmende Vernetzung mit Sensoren und Mobilität erzeugen einen Trend zu Data-Pushing Systemen, wobei "Streamed Data" (schnelle Datenströme) wichtig geworden sind, die IDCMs effizient behandeln müssen. Stream Reasoning ist in verschiedener Hinsicht in das Interesse zweiser Forschungsgemeinden gerückt. Stream Processing konzentriert sich auf in hoher Rate eintreffende Daten der unteren Ebene, wobei Verknüpfung, Mustersuche u.a. im Vordergrund stehen. In Knowledge Representation and Reasoning wurden Schritte für Stream Reasoning unternommen, aber derzeitige Ansätze sind nicht auf hohe Datenraten eingestellt. Dabei gibt es wenige Arbeiten, die Stream Processing in verteilten Umgebungen betrachten; zudem gibt es keinen Rahmen, der die Zusammenarbeit von heterogenen Knoten unter Streaming unterstützt. Die Beziehungen einzelner Streaming Ansätze sind unklar, und deren verschiedene Grundsätze erschweren einen Vergleich. Dieses Projekt zielt darauf ab, höheres Schließen auf Streamed Data zu erweitern. Dies ist aufgrund hoher Datenraten eine Herausforderung, weil die Beantwortung von ausdrucksstarken Anfragen und die Lösung von komplexen Aufgaben viel Zeit in Anspruch nehmen können; es scheint jedoch erreichbar, weil (1) komplexe Aufgaben oft nur eine abstrakte Sicht der Daten auf höherer Ebene benötigen und keinen direkten Input auf niederer Ebene, und (2) auf höhereren Ebenen Datenänderungen wesentlich weniger oft erfolgen als auf niedrigeren. Unter dieser Hypothese sind unsere Ziele: (i) die Entwicklung einer formalen Semantik für Stream Reasoning, darunter eine "ideale Semantik", die Eigenschaften wie Behandlung unvollständiger Information und nichtmonotones Schließen aufweist, und eine adaptive Semantik mit einem Trade-off zwischen semantischer Feinheit und Häufigkeit der Datenänderung; (ii) Verteilung und Heterogenität einzubringen; (iii) die Grenze der Skalierbarkeit zu verstehen, um Algorithmen, Approximationen und Optimierungtechniken für die effiziente Evaluierung der Semantik zu entwickeln, und (iv) rigorose Mittel zum Vergleich verschiedener Stream Reasoning/Processing Ansätze aus theoretischer und praktischer Sicht zu schaffen. Die Projektergebnisse werden tiefgehende theoretische Resultate über verteiltes, heterogenes Stream Reasoning liefern, eine Implementierung eines experimentellen Prototypen der Skalierbarkeit erlaubt, und einen allgemeinen Vergleichsrahmen mit Werkzeugen für qualitative und systematische Vergleiche von Stream Reasoning bzw. Processing-Ansätzen. Wir glauben, dass unser Gesamtziel erreichbar ist, weil neben der Hypothese Techniken in verwandten Gebieten nützlich sind. Beispielsweise kann die Theorie hinter modell-orientierten Formalismen (SAT Solving, Anwer Set Programming) ein Startpunkt für die ideale Semantik sein; adaptive/inkrementelle Evaluierung bzw. Schließen untersucht werden; "load shedding" beim Stream Processing die Performanz verbessern; semantische Relaxation ein Kandidat für Approximation sein. Zudem kann der S2Gen Datengenerator Szenarien für die Evaluierung generieren, und vorläufige Resultate zum Vergleich von Linked Stream Engines sind ein Ausgang für die Entwicklung des Vergleichsrahmen. Unser System wird als Open Source zugänglich sein.

Dieses Projekt beschäftigte sich mit logik-orientierter Verarbeitung von Datenströmen. Der rasante Zuwachs an Daten hat in den letzten beiden Dekaden zu einer Vielzahl von neuen Entwicklungen geführt. Die auf strömenden Daten basierenden Anwendungen reichen von der kontinuierlichen Auswertung von Sensoren über die Echtzeit-Analyse von Log-Dateien von Servern bis hin zur Evaluierung laufender Einträge in sozialen Netzwerken. Bestehende Techniken konzentrieren sich dabei meist auf die Skalierbarkeit und um die effiziente, oft parallele oder verteilte Verarbeitung von relativ einfachen Berechnungen wie Aggregierungen. Insbesondere wurden auch Anfragesprachen für statische Daten, wie SQL oder SPARQL (für das Semantic Web), für strömende Daten erweitert, um einen Zugriff auf aktuelle Informationen über Fenster (wie z.B. Zeitfenster) zu ermöglichen.Gerade für deklarative Sprachen stellt sich die Frage ihrer exakten Semantik, die bisher oftmals nicht spezifiert wurde, weil dazu eine entsprechende formale Theorie gefehlt hat. Insbesondere gab es keine mathematische Grundlage, um logische Zusammenhänge über Datenströme unter Einsatz von Fenstern auszudrücken. Aus dem Forschungsbereich der Wissensrepräsentation etwa gibt es logik-orientierte Methoden für inhärent schwierig Probleme. Allerdings funktionieren diese fast ausschließlich auf rein statischen Daten; vergleichbare Sprachen und Techniken für strömende Daten waren nicht verfügbar.Das zentrale Ergebnis dieses Projekts ist genau so eine formale Sprache für das logische Schließen über Datenströme, die einerseits als formaler Rahmen für die Analyse und den Vergleich bestehender Formalismen zum Einsatz kommen kann, andererseits aber auch als eigener Formalismus. Beide Ansätze wurden im Projekt verfolgt: Zum einen wurde die informelle Semantik ausgewählter bestehender Sprachen exemplarisch konkretisiert, zweitens wurde die Sprache selbst genutzt, um weiteren grundlegenden Fragen auf formaler Basis nachzugehen, wie etwa der Möglichkeit zur Optimierung von Anfragen aufgrund ihrer semantischen Äquivalenz. Weiters haben wir eine neuartige verteilte Semantik untersucht, wie sich in einem beliebigen Netzwerk heterogener Knoten (wie z.B. Server) auftreten können, wenn diese laufend Daten untereinander austauschen.Da die Berechnung von Ergebnissen beim ständigen Einströmen neuer Daten zu lange dauern kann, stellt weiters die inkrementelle Auswertung eine zentrale Herausforderung dar, insbesondere bei nicht-monotonem Schließen, wo bisherige Ergebnisse unter Umständen zurückgezogen werden müssen. Die in diesem Projekt entwickelten Algorithmen für inkrementelles Schließen auf Basis von Datenströmen wurden in zwei prototypischen Implementierungen bereitgestellt und empirisch erprobt.