Continuous queries over data streams [Elektronische Ressource] : semantics and implementation / vorgelegt von Jürgen Krämer

Juergen Kraemer

Sujets

• Informatik

Informations

• Publié par: philipps-universitat_marburg
• Publié le: 01 janvier 2007
• Nombre de lectures: 17
• Langue: Deutsch
• Poids de l'ouvrage: 5 Mo

Extrait

CQDS
–SI
Dissertation
zurErlangungdesDoktorgrades
derNaturwissenschaften
(Dr. rer. nat.)
demFachbereichMathematikundInformatik
derPhilipps Universit at¨ Marburg
vorgelegtvon
Jurgen¨ Kramer¨
ausAlsfeld Leusel
MarburganderLahn2007VomFachbereichMathematikundInformatik
derPhilipps Universit at¨ Marburg
alsDissertationam18.Juni2007angenommen.
Erstgutachter: Prof.Dr.BernhardSeeger
Zweitgutachter: Prof.Dr.BerndFreisleben
¨Drittgutachter: Prof.Dr.M.TamerOzsu
Tagdermundlichen¨ Prufung¨ am22.Juni2007Abstract
Recenttechnologicaladvanceshavepushedtheemergenceofanewclassofdata intensive
applicationsthatrequirecontinuousprocessingoversequencesoftransientdata,called
data streams, in near real time. Examples of such applications range from online
monitoringandanalysisofsensordatafortrafficmanagementandfactoryautomation
to financial applications tracking stock ticker data. Traditional database systems are
deemed inadequate to support high volume, low latency stream processing because
queriesareexpectedtoruncontinuouslyandreturnnewanswersasnewdataarrives,
withouttheneedtostoredatapersistently. Thegoalofthisthesisistodevelopasolid
andpowerfulfoundationforprocessingcontinuousqueriesoverdatastreams. Resource
requirementsarekeptinboundsbyrestrictingtheevaluationofcontinuousqueriesto
slidingwindowsoverthepotentiallyunboundeddatastreams. Thistechniquehasthe
advantagethatitemphasizesnewdata,whichinthemajorityofreal worldapplications
is considered more important than older data. Although the presence of continuous
queriesdictatesrethinkingthefundamentalarchitectureofdatabasesystems,thisthesis
pursuesanapproachthatadaptsthewell establisheddatabasetechnologytothedata
streamcomputationmodel,withtheaimtofacilitatethedevelopmentandmaintenance
ofstream orientedapplications. Basedonadeclarativequerylanguageinheritingthe
basic syntax from the prevalent SQL standard, users are able to express and modify
complexapplicationlogicinaneasyandcomprehensiblemanner,withoutrequiringthe
useofcustomcode. Theunderlyingsemanticsassignsanexactmeaningtoacontinuous
queryatanypointintimeandisdefinedbytemporalextensionsoftherelationalalgebra.
By carrying over the well known algebraic equivalences from relational databases to
streamprocessing,thisthesispreparesthegroundforpowerfulqueryoptimizations. A
uniquetime intervalbasedstreamalgebraimplementedwithe fficientonlinealgorithms
allows for processing data in a push based fashion. A performance analysis, along
withexperimentalstudies,confirmsthesuperiorityofthetime-intervalapproachover
comparative approaches for the predominant set of continuous queries. Based upon
thisstreamalgebra,thisthesisaddressesarchitecturalissuesofanadaptiveandscalable
runtimeenvironmentthatcancopewithvaryingqueryworkloadandfluctuatingdata
stream characteristics arising from the highly dynamic and long-running nature of
streamingapplications. Inordertocontroltheresourceallocationofcontinuousqueries,
noveladaptationtechniquesareinvestigated,tradingoffanswerqualityforlowerresource
requirements. Moreover, a general migration strategy is developed that enables the
query processing engine to re optimize continuous queries at runtime. Overall, this
thesisoutlinesthesalientfeaturesandoperationalfunctionalityofthestreamprocessing
infrastructurePIPES(PublicInfrastructureforProcessingandExploringStreams),whichhas
alreadybeenappliedsuccessfullyinavarietyofstream orientedapplications.
iiiivZusammenfassung
DerrapidetechnologischeFortschrittdervergangenenJahrehatdieEntwicklungeiner
neuenKlassevonAnwendungenbegunstigt¨ ,diesichdadurchauszeichnen,dassenorme
DatenmengeninFormvonDatenstromen¨ bereitgestelltundkontinuierlichverarbeitet
werden mus¨ sen, um zeitnah wichtige Informationen und Kennzahlen zu ermitteln.
Beispielefur¨ AnwendungenfindensichindenunterschiedlichstenBereichen,diesich
¨von der Uberwachung und Auswertung von Sensordaten im Verkehrsmanagement
oder der Fabrikautomation bis hin zur Trenderkennung in Borsen¨ kursen erstrecken.
KonventionelleDatenbanksystemesindfur¨ dieerforderlichekontinuierlicheAnfrage
verarbeitung, beiderdieeintreffendenDatenmoglich¨ stdirektundohnevollstandige¨
Zwischenspeicherung verarbeitet werden mus¨ sen, nicht ausgelegt. Das Ziel dieser
Arbeitbestehtdarin,einesolideGrundlagezuradaquatenVerarbeitungkontinuierlicher¨
AnfragenaufDatenstrom¨ enbereitzustellen. UmdieRessourcenanforderungenbeider
Verarbeitungzubegrenzen,beziehensichkontinuierlicheAnfragenaufgleitendeFenster
uber¨ den potentiell unbeschrankt¨ großen Datenstrome¨ n. Dieses Vorgehen bietet den
Vorteil, dass sich die Ergebnisse einer Anfrage stets auf die aktuellen Daten beziehen,
dieubl¨ icherweisefur¨ dieAnwendungenvonhoher¨ erRelevanzsind. DamitAnwender
eineneinfachenZugangzudenneuentwickeltenVerfahrenfindenkonn¨ en,orientiert
sichdieseArbeitanbewahr¨ terDatenbanktechnologieundadaptiertdieseaufdasDaten-
strommodell. Einedeklarative,engandenweitverbreitetenSQL Standardangelehnte
AnfragespracheerlaubtesAnwendern,komplexeApplikationslogikaufeinfacheWeise
auszudrucken¨ . DiezuGrundeliegende,aussagekraft¨ igeAnfragesemantikbasiertauf
temporalenErweiterungenderrelationalenAlgebra. Daraufaufbauendistesgelungen,
¨die aus Datenbanken bekannten algebraischen Aquivalenzen auf kontinuierliche An-
fragenuber¨ Datenstromen¨ zuubertragen,¨ wodurcheinehervorragendeGrundlagezur
Anfrageoptimierunggeschaffenwurde. Fur¨ diedatengetriebeneVerarbeitungsorgteine
bislangeinzigartigezeitintervallbasierteDatenstromalgebraumgesetztdurcheffiziente
Online Algorithmen. Mittels einer Performanzanalyse gest utzt¨ durch experimentelle
Studien wird belegt, dass der Zeitintervall Ansatz f ur¨ einen Großteil der Anfragen
konkurrierendenAnsatze¨ ndeutlichuberl¨ egenist. Daruber¨ hinauswidmetsichdieArbeit
architekturellenGesichtspunkteneineradaptivenundskalierbarenLaufzeitumgebung,
dieinderLageist,sicheinervariierendenAnfragelastsowiesichuber¨ dieZeitande¨ rnden
Datenstromcharakteristikaanzupassen. InsbesonderewerdenneueVerfahrenvorgestellt,
umdieRessourcenallokationvonAnfragenzusteuernundAnfragenzurLaufzeitzu
optimieren. DieimRahmendieserArbeitentwickelteFunktionalitat¨ bildetdenKernder
SoftwareinfrastrukturPIPES(PublicInfrastructureforProcessingandExploringStreams),die
sichbereitsindiversenAnwendungsgebietenalseinmacht¨ igesundnutzl¨ ichesWerkzeug
zurVerarbeitungvonDatenstromen¨ bewahrt¨ hat.
vviAcknowledgments
First of all, I am extremely grateful to my adviser, Prof. Dr. Bernhard Seeger, for his
invaluable guidance throughout my doctoral studies. In spite of a busy schedule, he
has been readily available for advice, reading, or simply a word of encouragement. I
learnedalotfromhimaboutgoodresearchpracticeandwhatittakestoachievethisgoal.
Iwouldalsoliketothankallthemembersofmycommitteeforthetimeandenergythey
havedevotedtoreadingmywork.
I express my gratitude to all the database group members for their great interest in
thetopicofmythesis,theircriticalfeedbackandsuggestions,andthepleasantworking
atmosphere. Inparticular,IamgratefultoMichaelCammert,ChristophHeinz,Tobias
Riemenschneider, and Sonny Vaupel for all the help and encouragement they have
givenme,includingthemanyfruitfuldiscussionsonreasonablequerysemanticsand
implementationdesign. SpecialthanksalsogotoMichaelCammert,HeikeandPatrick
Seitz,andBenMillsforproof readingthisthesis.
IamgratefultohavehadtheopportunitytoworkwithYinYangandProf.Dr.Dimitris
Papadias on the dynamic plan migration problem. In addition, I would like to thank
Prof.Dr.ThomasPenzelandProf.Dr.RichardLenzfortheinspiring,multidisciplinary
discussions about data stream processing in sleep medicine. I am thankful to Ralph
Langnerandhisteamforprovidinguswiththecommerciali Plantenterpriseversion,
alongwithprofessionalsupportatnocharge,sothatweareabletoemployourstream
processinginfrastructurePIPESinhighlyautomatedmanufacturingenvironments.
Finally,Iwouldnothavereachedthispointinmyacademiccareerwithoutthesupport
and unconditional love of my parents and my sister. I am forever indebted to my
wonderful wife Birgit and my son Julian for their love, understanding, patience, and
encouragementwhenitwasmostrequired. Last,butnotleast,Iowemythankstoallmy
friendswhobelievedinmeandkeptmesmiling.
The research described in this thesis was part of the project “Anfrageverarbeitung
aktiverDatenstrome¨ ”supportedbygrantsNo.SE 553 /4 1andSE 553/4 3fromtheGerman
ResearchFoundation.
viiviiiContents
ListofFigures xvii
ListofTables xix
ListofAlgorithms xxi
I Introduction 1
1 ANewClassofDataManagementApplications 3
1.1 DataStreamModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 DifferencesbetweenDBMSsandDSMSs . . . . . . . . . . . . . . . . . . . . 5
2 ResearchChallenges 9
2.1 QueryFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 SemanticsforContinuousQueries . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 StreamAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 AdaptiveQueryExecution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Contributions 13