WWW.ABSTRACT.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Abstract, dissertation, book
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 |

«von Thomas Jörg Betreuer: Dipl.-Inf. Andreas Bühmann 21. Januar 2005 Inhaltsverzeichnis 1. Einleitung 2. Datenströme 3. Klassifizierung von ...»

-- [ Page 1 ] --

Seminar: Datenbanken und

Informationssysteme

Thema: Vorstellung des Streamkonzepts

von Thomas Jörg

Betreuer: Dipl.-Inf. Andreas Bühmann

21. Januar 2005

Inhaltsverzeichnis

1. Einleitung

2. Datenströme

3. Klassifizierung von Anfragen

4. Kontinuierliche Anfragen

4.1. Verwandte Konzepte

4.2. Kontinuierliche Anfragen in Aurora

4.3. Kontinuierliche Anfragen in STREAM

4.4. Kontinuierliche Anfragen gegen XML-Ströme

4.4.1. XPath Rewriter

4.4.2. SPEX

5. Anpassung an Überlast

6. Zusammenfassung

1. Einleitung In jüngster Zeit ist das Interesse an Anwendungen gestiegen, die große Mengen an Daten in Form von kontinuierlichen Strömen anstatt eines begrenzten Vorrats an persistent gespeicherten Datensätzen verarbeiten. Es gibt viele Beispiele für

solche Systeme:

Sensornetzwerke bestehen aus einer Vielzahl verteilter, autonomer Sensoren.

• Diese generieren Datenströme, die geeignet überwacht und analysiert werden müssen.

Systeme zur Finanzanalyse werten Anfragen gegen Ströme von Börsendaten • aus, die online und in Echtzeit eintreffen. Auf diese Weise lassen sich Trends erkennen und vorhersagen.

Tracking-Applikationen verfolgen die Position einer Vielzahl von physischen • Objekten. Ein Anwendungsszenario für solche Systeme ist die automatische Mauterhebung für LKWs auf Autobahnen.

Allen diesen Anwendungen ist gemein, dass sie Datenströme analysieren bzw.

überwachen. Diese Ströme stammen von zahlreichen autonomen Quellen, sie sind von potentiell unbegrenzter Länge und können unvorhersehbare Fluktuationen der Übertragungsrate aufweisen. Diese Umstände erfordern ein neues Modell der Datenverarbeitung, dass sich grundlegend von dem unterscheiden muss, das in traditionellen Datenbanksystemen zur Anwendung kommt. Der Grund hierfür ist, dass Daten nicht länger ausschließlich in Form persistenter Relationen in einem passiven Repository vorliegen, auf denen von Benutzern aktiv initiierte Operationen ausgeführt werden. Vielmehr findet eine datengetriebene Verarbeitung statt; die Nutzer werden kontinuierlich mit gewonnenen Ergebnissen versorgt. Daher spricht man hier von einem DBMS-Active-Human-Passive-Modell (DAHP) [CCC+02] in Abgrenzung zum Human-Active-DBMSPassive-Modell (HADP).

Das DAHP-Modell erfordert ein neues Verfahren zur Anfrageverarbeitung. Wie bereits angedeutet, werden einmal gestellte Anfragen kontinuierlich gegen die ankommenden Datenströme ausgewertet. Diese Anfragen müssen daher für längere Zeit im System verbleiben – man spricht von kontinuierlichen Anfragen [BaWi01]. Die Resultate von kontinuierlichen Anfragen können selbst die Form von Datenströmen haben.

Traditionelle DBMS speichern ankommende Daten zunächst und indizieren diese gegebenenfalls, bevor eine Verarbeitung bzw. eine Anfrage stattfinden kann. Dieser Ansatz ist für die Verarbeitung von Datenströmen ungeeignet. Hier müssen Algorithmen zur Anfrageauswertung mit einem einzigen sequentiellen Durchlauf der Daten auskommen. Das Speichern großer Mengen oder gar der gesamten Eingabedaten ist nicht praktikabel, da die Länge des Datenstromes potentiell unbegrenzt ist. Es werden Algorithmen angestrebt, die ankommende Daten sofort nach deren Eintreffen verarbeiten und anschließend verwerfen können.

Derartige Algorithmen werden als One-Pass-Algorithmen bezeichnet. In Abschnitt 4.4.2 wird der One-Pass-Algorithmus SPEX zur Auswertung von XPathAusdrücken über XML-Strömen vorgestellt.

Der direkte Vergleich zwischen traditioneller Anfrageauswertung auf Datenbanken und derjenigen auf Datenströmen zeigt interessante Unterschiede auf: Während die Anfragen in Datenbanken transient und die Daten persistent und umfangreich sind, ergibt sich bei Datenströmen ein umgekehrtes Bild: Hier sind die Anfragen persistent und zahlreich, die Daten jedoch transient. Diese müssen aus zuvor genannten Gründen nach der Verarbeitung in der Regel verworfen werden.

Dies führt insbesondere dann zu Problemen, falls sich eine Anfrage auf Datensätze aus der Vergangenheit bezieht, diese jedoch bereits verworfen wurden. Es ist unmöglich, im Voraus zu bestimmen, welche Daten zu einem späteren Zeitpunkt benötigt werden. Will man die Vergangenheit referenzierende Anfragen nicht gänzlich verbieten, muss man sich mit einem angenäherten Ergebnis begnügen. Eine exakte Anfrageauswertung wäre nur dann möglich, wenn alle relevanten Daten zur Verfügung stünden. Zur Approximation von Anfrageresultaten können Datenreduktions- und Zusammenfassungstechniken eingesetzt werden.

So lässt sich das nötige Datenvolumen zur Anfrageauswertung stark reduzieren, jedoch auf Kosten der Genauigkeit der Resultate.

Es gibt eine weitere Anforderung bei der Anfrageauswertung auf Datenströmen, welche eine Reduzierung der Präzision unausweichlich macht: Applikationen, die Datenströme überwachen, müssen in der Regel Echtzeitanforderungen erfüllen, d.h. ihre Antwortzeit darf eine gewisse obere Schranke nicht überschreiten.

Es ist offensichtlich, dass bei einem System zur Überwachung eines Kernreaktors oder eines Intensivpatienten keine Verspätung bei der Meldung eines kritischen Zustandes zu tolerieren ist. Datenströme können, wie bereits erwähnt, unvorhersehbare Fluktuationen in ihrer Übertragungsrate aufweisen; daher kann ein System kurzzeitig von einer Flut eintreffender Daten überfordert werden. Um mit derartigen Überlastsituationen fertig zu werden und weiterhin Echzeitanforderungen zu erfüllen, müssen einzelne Datensätze verworfen werden, bevor sie vollständig verarbeitet werden konnten. Dieses Verfahren wird als Load Shedding bezeichnet und führt dazu, dass die Anfrageauswertung ungenauer wird, da eventuell nicht alle Datensätze berücksichtigt werden. Es ist von großer Bedeutung, Load-Shedding-Strategien zu verwenden, die die Präzision der Resultate möglichst wenig senken. In Abschnitt 5 wird ein solch ein Verfahren vorgestellt.





Es gibt Projekte mit dem Ziel, generische Systeme zur Verarbeitung von Datenströmen zu entwickeln. An der Universität Stanford wurde ein System namens STREAM1 (STanford stREam datA Management) [BBD+02] entwickelt, das mittlerweile als Prototyp-Implementierung bereitsteht. Aurora2 [CCC+02] entstand in Zusammenarbeit der Brandeis Universität, der Brown Universität und des MIT. Dieses Projekt ist mittlerweile abgeschlossen und wird kommerziell weiterentwickelt. Das Nachfolgeprojekt mit dem Namen Borealis übernimmt die Kernfunktionalität von Aurora und strebt eine Verteilung des Systems und eine Erweiterung des Datenmodells an. Im Verlauf dieser Ausarbeitung wird häufiger auf STREAM und Aurora eingegangen. Der Vergleich dieser Projekte ist interessant, da trotz ähnlicher Ziele recht verschiedene Herangehensweisen gewählt wurden.

Der Rest dieser Ausarbeitung gliedert sich wie folgt: Nachdem in diesem Ab

<

1 http://www-db.stanford.edu/stream/2 http://www.cs.brown.edu/research/aurora/

schnitt die Charakteristika von Datenströmen bereits angedeutet wurden, fasst Abschnitt 2 diese prägnant zusammen. Abschnitt 3 untersucht Eigenschaften von Anfragen in Allgemeinen und nimmt eine Klassifizierung vor. Der Schwerpunkt dieser Ausarbeitung liegt auf dem Gebiet der kontinuierlichen Anfragen. Eine Übertragung herkömmlicher Verfahren zur Anfrageauswertung auf das Strommodell ist in vielen Fällen nicht möglich. Abschnitt 4 erläutert auftretende Probleme und beschreibt Lösungsansätze. Die praktische Umsetzung von kontinuierlichen Anfragen wird am Beispiel von Aurora, STREAM und SPEX geschildert. Abschnitt 5 zeigt Möglichkeiten auf, die es einem Datenstromsystem erlauben sich dynamisch an Überlastsituationen anzupassen und weiterhin Echtzeitanforderungen gerecht zu werden. Den Abschluss dieser Ausarbeitung bildet die Zusammenfassung in Abschnitt 6.

2. Datenströme Unter einem Datenstrom versteht man eine potentiell unbegrenzte Folge kontinuierlich übertragener Datensätze hohen Aufkommens und ohne zeitliche Regelmäßigkeit [BBD+02].

Es besteht kein wahlfreier Zugriff auf die Stromdaten. Algorithmen zur Anfrageauswertung gegen Ströme müssen mit einem einzigen sequentiellen Durchlauf der Daten auskommen. Es ist natürlich möglich, Datensätze zu archivieren, die zu einem späteren Zeitpunkt benötigt werden. Dabei muss jedoch garantiert werden, dass der Speicherbedarf nicht ohne Schranken wächst. Selbst in Anbetracht der Tatsache, dass Speicherplatz beinahe unbegrenzt auf Tertiärspeichern zur Verfügung steht, verbieten Performanzanforderungen extrem speicherintensive Algorithmen.

Im Strommodell treffen Daten unvorhersehbar beim Empfänger ein, ohne zuvor angefordert worden zu sein. Dieses Kommunikationsmodell wird als Push-Kommunikation bezeichnet [BrFO04]. Der Name veranschaulicht, dass ankommende Daten gewissermaßen von außen in ein System „hineingedrückt“ werden. Das komplementäre Modell wird als Pull-Kommunikation bezeichnet und findet beispielsweise im Web Verwendung. In diesem Fall fordert der Empfänger die gewünschten Daten explizit von einer Quelle an. Push-Kommunikation macht es erforderlich, dass ankommende Daten sofort konsumiert und verarbeitet werden.

Abhängig von der Datenquelle und dem eingesetzten Netzwerk, können Datenströme ein unvorhersehbares Verhalten zeigen, mit Auswirkungen auf die Ordnung und die zeitliche Abfolge von Datensätzen [BBC+04]. Diese können verspätetet oder in vertauschter Reihenfolge beim Empfänger ankommen oder gänzlich verloren gehen.

Nach [BrFO04] lassen sich drei verschiedene Klassen von Datenströmen identifizieren, die derzeit von Bedeutung für die Forschung sind: Punkt-, Tupel- und XML-Ströme. Punktströme bestehen aus einer Folge von skalaren Werten wie Zahlen oder Zeichen. Die Elemente eines Tupelstroms entsprechen denjenigen Tupeln, die aus herkömmlichen, flachen Relationen bekannt sind. Ein XMLStrom übermittelt XML-Fragmente, die in ihrer Gesamtheit der Struktur eines XML-Dokuments entsprechen. Die Reihenfolge, in der die Elemente im XMLStrom auftauchen, entspricht einer Traversierung des XML Document Tree in Vorordung.

Punkt- und Tupelströme bestehen aus Datensätzen, die keine Schachtelung zulassen und daher stets dieselbe Struktur aufweisen. Diese Eigenschaft erleichtert die Verarbeitung dieser Arten von Strömen. Punktströme können als Sonderfall von Tupelströmen angesehen werden.

Die Verwendung von XML zur Repräsentation von Stromdaten ermöglicht die Definition von Bäumen beliebiger Größe und Schachtelungstiefe. Diesen kann eine rekursiv definierte Struktur zu Grunde liegen. XML eignet sich insbesondere für semi-strukturierte Daten weitaus besser als flache, relationale Tupel. Semistrukturierte Daten sind für bestimmte Anwendungen von großer Bedeutung, beispielsweise für Publish-Subscribe-Systeme. Ein weiterer Grund für das Forschungsinteresse an XML-Strömen ist die große Bedeutung von XML als Standard zum Datenaustausch im Internet. Die Verarbeitung von XML-Strömen stellt eine besondere Herausforderung dar, da beliebig geschachtelte Datenstrukturen auftreten können.

3. Klassifizierung von Anfragen Anfragen im allgemeinen Sinne, gleichgültig ob sie sich auf Relationen oder Ströme beziehen, lassen sich nach [BBD+02] anhand zweier Eigenschaften klassifizieren: Die erste Einteilung betrifft die Art, wie die Anfragen ausgewertet werden. Man unterscheidet einmalige Anfragen und kontinuierliche Anfragen.

Einmalige Anfragen werden über einem Schnappschuss des Zustandes der zugrunde liegenden Daten zu einem bestimmten Zeitpunkt ausgewertet und kommen in traditionellen Datenbanksystemen zum Einsatz. Kontinuierliche Anfragen sind im Hinblick auf Datenströme die interessanteren. Ausgelöst von ankommenden Daten, findet die Anfrageauswertung kontinuierlich über einen längeren Zeitraum statt. Das Resultat einer kontinuierlichen Anfrage kann in Form von Datenströmen oder persistenten Relation bereitgestellt werden; beide Möglichkeiten lassen sich in verschieden Anwendungsszenarien sinnvoll einsetzten.

Die zweite Unterscheidung betrifft die Zeit, zu der eine Anfrage in ein System eingebracht wird: Vordefinierte Anfragen sind dem System bekannt, bevor relevante Daten eintreffen. Ad-hoc-Anfragen können zu jedem beliebigen Zeitpunkt an ein System gestellt werden. Im Hinblick auf die Datenstromverarbeitung stellt diese Klasse von Anfragen eine gewisse Herausforderung dar. Zum einen sind Ad-hoc-Anfragen nicht im Voraus bekannt, was deren Optimierung erschwert.

Zum anderen werden für eine präzise Anfrageauswertung eventuell Daten benötigt, die zum Zeitpunkt der Ad-hoc-Anfrage nicht mehr zur Verfügung stehen.

4. Kontinuierliche Anfragen Verfahren zur Auswertung von einmaligen Anfragen in herkömmlichen Datenbanksystemen sind gründlich erforscht und lassen sich zum Teil auf kontinuierliche Anfragen übertragen. Traditionell wird für jede Anfrage ein geeigneter Anfragegraph erstellt, der in einen konkreten Ausführungsplan überführt wird.

Ein Netzwerk von Operatoren, dass große Ähnlichkeit mit einem herkömmlichen Ausführungsplan hat, lässt sich auch zur Verarbeitung von kontinuierlichen Anfragen einsetzen. Die Datenquellen sind in diesem Fall jedoch kontinuierliche Ströme anstatt persistenter Relationen, daher muss eine datengetriebene Verarbeitung stattfinden. Die Operatoren im Netzwerk konsumieren ankommende Datensätze, sobald diese zu Verfügung stehen, verarbeiten diese und leiten das Resultat auf ihren ausgehenden Kanten weiter.

Die aus der Relationenalgebra bekannten Operationen Selektion, Projektion sowie Vereinigung fügen sich ohne Probleme in diese neue Architektur ein. Andere Operatoren werfen im Kontext des Strommodells interessante Probleme auf.

Man bezeichnet Operatoren als blockierend, falls diese kein Ergebnis liefern können, bevor die gesamten Eingabedaten verarbeitet wurden. Beispiele für blockierende Operationen sind die Berechnung von Summen, Minimal-, Maximal-, und Durchschnittswerten sowie Sortierfunktionen. Unbegrenzte Datenströme sind als Eingabe für blockierende Operatoren offensichtlich nicht sinnvoll, da deren Berechnung in diesem Fall niemals zu einem Ende kommt.

Auch Join-Operationen sind im Strommodell problematisch, da deren Speicherbedarf im Verlauf der Verarbeitung ohne Schranken wächst. Jeder ankommende Datensatz ist potentiell ein passender Join-Partner für einen zukünftigen Datensatz und muss daher für unbegrenzte Zeit vorgehalten werden.



Pages:   || 2 | 3 | 4 |


Similar works:

«PAP SMEARS: DO OLDER WOMEN REALLY NEED THEM? Cervical cancer a concern for midlife and older women Cervical cancer can be prevented in the vast majority of women. Yet it remains the 9th leading cause of cancer deaths among U.S. women and 12th in Canada.¹ Significantly, as women age, their rate of death from cervical cancer steadily increases. And elderly women are more likely to be diagnosed at a late stage.² Why is this happening? The simple explanation is that while the Pap smear is still...»

«July 6th 2015 – The Sincura Group Weekly Newsletter Welcome to our weekly newsletter giving you information of the hottest events in the capital. For a day to day highlight guide follow us on twitter at @Sincura, for a comprehensive 2015 schedule visit www.thesincuragroup.com/Calendar.html. Please contact your concierge to arrange attendance. FEATURED EVENT: CricketThe Ashes We love beating Australia, and this summer should be no different as we host the Ashes cricket against our old rivals....»

«Die Fusion UBS-SBV aus der Sicht der Wettbewerbspolitik* Thomas von Ungern-Sternberg und Damien Neven Universität Lausanne *Diese Arbeit ist das Ergebnis eines intensiven Gedankenaustausches zwischen den beiden Autoren. Für die vorliegende Deutsche Fassung der Arbeit übernimmt der erste Autor die Verantwortung für die Formulierung und Gewichtung der Argumente. In Kürze wird eine französische Fassung erscheinen, in welcher der zweite Autor das letzte Wort hat. Zusammenfassung...»

«Eduard Mörike: Gebet von Karl Heinz Weiers Herr! schicke was du willt, Ein Liebes oder Leides; Ich bin vergnügt, daß beides Aus deinen Händen quillt. Wollest mit Freuden Und wollest mit Leiden Mich nicht überschütten! Doch in der Mitten Liegt holdes Bescheiden. Gebete sind im allgemeinen Dankesworte, Lobpreisungen oder Bitten von nicht allzu persönlicher, nicht allzu privater Natur. Nur so finden sie Eingang in das Leben einer Kirchengemeinde und werden, sollte ihr Text komponiert...»

«Masked Priming Treatment for Anomia – A Phase 1 Study Abstract This Phase 1 single-subject study explored the use of masked repetition priming to improve word retrieval for picture naming in anomia. Masked priming is one means of activating the implicit language processes that typically support rapid, accurate use of language, and that may be impaired in aphasia. This study used computer-based presentation of masked primes repeatedly paired with pictures to encourage re-establishment of...»

«Some Considerations on Sub-national Spatial Data Infrastructures Hartmut MÜLLER, Falk WÜRRIEHAUSEN, GERMANY Key words: SDI, City, Citizen Interface, Geoportal SUMMARY Nowadays the need for the development of feasible Spatial Data Infrastructures (SDI) in general is widely recognised. Due to its complexity this subject experienced a subdivision into several narrower terms like Regional SDI, National SDI, Sub-national SDI etc. in order to address the topics under consideration more...»

«On Annulling a Conversion Obtained by Deceit A Concurring Opinion RABBI AVRAM I. REISNER This paper represents a concurring opinion to Rabbi Steven Saltzman's responsum, May a Conversion Obtained Through Deceit be Annulled? which was passed by the CJLS on 6/14/89 with eleven votes in favor, and eight opposed. I reach the same specific conclusion as Rabbi Saltzman, that there is no valid mikveh ceremony without proper intentionality. Where it can be clearly demonstrated... (that) the...»

«Air Passenger Rights Commission's initiative on Passengers' protection in the event of airline insolvency for standalone air tickets External study Stakeholder workshop 30 March 2011 Brussels 1040, Borschette Building (CCAB), rue Froissart 36, room 1D Minutes Executive Summary On 30 March 2011, stakeholders related to air transport had the opportunity to present their views on the final report of a preparatory study in view of a Commission's initiative on Passengers' protection in the event of...»

«Cantabrian Sea purse seine anchovy fishery REVIEW FINAL REPORT 26th of February 2015 Client Group: OPEGUI & OPESCAYA Fishermen: COFRADIA SAN MARTIN DE LAREDO FEDERACIÓN COFRADÍAS PESCADORES DE GIPUZKOA FEDERACIÓN COFRADÍAS DE PESCADORES BIZKAIA BUREAU VERITAS CERTIFICATION FRANCE AUTHORS: Lisa Maria Pontes Coelho Borges Luis Ambrosio Blazquez Macarena García Silva Cantabrian Sea purse seine anchovy fishery: FR (review) Page 1 of 174 Date of issue: 26th February 2015 © Marine Stewardship...»

«Würzburger UNTERSTÜTZER JungChemikerForum Chem-SyStM Chemie-Symposium der Studierenden Mainfrankens Vernetze dein Wissen! Abstractband 07. Dezember 2010 www.jcf-wuerzburg.de INHALTSVERZEICHNIS Inhalt des Abstractbandes  Grußwort  Unterstützer  Abstracts der Arbeitskreise  Vortragende Appetithäppchen  Abstracts der Teilnehmer  Teilnehmerliste nach Fachbereichen aufgeschlüsselt  Notizen  Programm (Rückseite) Organisationskomitee Matthias Beyer, Nicolas Brockmann,...»

«Московский центр карнеги евразийская история РОССПЭН Москва УДк 94(470+571) ББк 63.3(2рос) т66 Dmitri Trenin. Post-imperium: a Eurasian story. Электронная версия: http://www.carnegie.ru/publications. книга подготовлена в рамках программы, осуществляемой некоммерческой неправительственной исследовательской...»

«CASE IN HINDI Andrew Spencer University of Essex Proceedings of the LFG05 Conference University of Bergen Miriam Butt and Tracy Holloway King (Editors) CSLI Publications http://csli-publications.stanford.edu/ Abstract I argue that Hindi clitic postpositions are not markers/realizations of case. Hindi has a genuine case system represented by the direct, oblique and vocative inflected forms of nouns. So-called case markers such as ne ‘Ergative’ or ko ‘Accusative/Dative’ are better thought...»





 
<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.