Fakultät für Mathematik, Informatik und Statistik - Digitale Hochschulschriften der LMU - Teil 01/02

The emergence of event-driven architectures, automation of business processes, drastic cost-reductions in sensor technology, and a growing need to monitor IT systems (as well as other systems) due to legal, contractual, or operational considerations lead to an increasing generation of events. This development is accompanied by a growing demand for managing and processing events in an

automated and systematic way. Complex Event Processing (CEP) encompasses the (automatable) tasks involved in making sense of all events in a system by deriving higher-level knowledge from lower-level events while the events

occur, i.e., in a timely, online fashion and permanently.

At the core of CEP are queries which monitor streams of "simple" events for so-called complex events, that is, events or situations that manifest themselves in certain combinations of several events occurring (or not occurring) over time and that cannot be detected from looking only at single events. Querying events is fundamentally different from traditional querying and reasoning with database or Web data, since event queries are standing queries that are evaluated permanently over time against incoming streams of event data. In order to express complex events that are of interest to a particular application or user in a convenient, concise, cost-effective and maintainable manner, special purpose Event Query Languages (EQLs) are needed.

This thesis investigates practical and theoretical issues related to querying complex events, covering the spectrum from language design over declarative semantics to operational semantics for incremental query evaluation. Its central topic is the development of the high-level event query language XChangeEQ.

In contrast to previous data stream and event query languages, XChangeEQ's language design recognizes the four querying dimensions of data extractions, event composition, temporal relationships, and, for non-monotonic queries involving negation or aggregation, event accumulation. XChangeEQ deals with complex structured data in event messages, thus addressing the need to query events communicated in XML formats over the Web. It supports deductive rules as an abstraction and reasoning mechanism for events. To achieve a full coverage of the four querying dimensions, it builds upon a separation of concerns of the four querying dimensions, which makes it easy-to-use and highly expressive.

A recurrent theme in the formal foundations of XChangeEQ is that, despite the fundamental differences between traditional database queries and event queries, many well-known results from databases and logic programming are, with some importance changes, applicable to event queries. Declarative semantics for XChangeEQ are given as a (Tarski-style) model theory with accompanying fixpoint theory. This approach accounts well for (1) data in events and (2) deductive rules defining new events from existing ones, two aspects often neglected in previous work of semantics of EQLs.

For the evaluation of event queries, this work introduces operational semantics based on an extended and tailored form of relational algebra and query plans with materialization points. Materialization points account for storing and maintaining information about those received events that are relevant for, i.e., can contribute to, future query answers, as well as for an incremental evaluation that avoids recomputing certain intermediate results. Efficient state maintenance in incremental evaluation is approached by "differentiating" algebra expressions, i.e., by deriving expressions for computing only the changes to materialization points. Knowing how long an event is relevant is a prerequisite for performing garbage collection during event query evaluation and also of central importance for developing cost-based query planners. To this end, this thesis introduces a notion of relevance of events (to a given query plan) and develops methods for determining temporal r

Infrastrukturen wie Verkehrs- und Energienetze bilden das Rückgrat unserer Gesellschaft und Wirtschaft.

Präzises Wissen über den aktuellen technischen Zustand der Infrastrukturkomponenten gilt als Grundvoraussetzung zur Befriedigung des ständig wachsenden Kapazitätsbedarfs und zur Erhöhung der Kosteneffizienz, insbesondere bei der Instandhaltung. Zwar liefern Fernüberwachungssysteme verschiedener Organisationen bereits heute unterschiedlichste Statusinformationen. Es fehlt jedoch ein generischer Ansatz zur integrierten Auswertung dieser Daten, um komplexe Gesamtzustände der Infrastrukturkomponenten abzuleiten.

Diese Arbeit versteht die Zustandsüberwachung für Infrastrukturnetze als ein kontextsensitives System im Sinne der Ambient Intelligence (Umgebungsintelligenz): Fernüberwachungssysteme liefern Kontextinformationen}, und anstelle der Situation einer Entität soll damit der Zustand eines Überwachungsobjekts ermittelt werden. Da sich hierfür bei kontextsensitiven Systemen wissensbasierte Ansätze bewährt haben, überträgt diese Arbeit einen solchen Ansatz auf die Zustandsüberwachung in Infrastrukturnetzen.

Damit sollen generische Verfahren sowohl zur Integration als auch zur Auswertung (Reasoning) von Kontextinformationen in Infrastrukturnetzen konzipiert und umgesetzt werden.

Eine Analyse von Schienen- und Stromnetzen identifiziert als Anforderungen unter anderem die Interoperabilität der Kontextinformationen zwischen Systemen und Betreibern sowie die Möglichkeit, auch komplexe Zustände ableiten zu können.

Die Standards des Semantic Web auf Basis der Beschreibungslogik SHIN bieten hierfür eine attraktive Grundlage und gewährleisten sowohl die Umsetzbarkeit als auch die Zukunftstüchtigkeit.

Für die automatisierte Auswertung (Reasoning) müssen die Besonderheiten von Infrastrukturnetzen berücksichtigt werden: Einerseits fallen Kontextinformationen von Überwachungssystemen räumlich verteilt und bei verschiedenen Organisationen an.

Deshalb werden Verfahren entwickelt, die konjunktive Anfragen auch bei verteilten Wissensbasen korrekt und vollständig beantworten. Dies wird theoretisch gezeigt und praktisch evaluiert.

Andererseits müssen topologiebezogene Anfragen beantwortet werden, wie die Suche nach optimalen Pfaden und k-nächsten Nachbarn. Dazu wird eine hierarchische Modellierung des Infrastrukturnetzes entwickelt. Ein generisches Konzept ermöglicht es, damit verschiedene Verfahren für topologiebezogene Anfragen umzusetzen.

Zur praktischen Umsetzung dieser Konzepte in einem Zustandsüberwachungssystem wird eine geschichtete Systemarchitektur spezifiziert. Ein Fallbeispiel aus dem europäischen Schienenverkehr zeigt ihre Realisierung: Mehrere Organisationen stellen unter anderem Achslast-, Gleisgeometrie- und Schienenprofilmessungen als Kontextinformationen zur Verfügung. Unabhängig von deren Verteilung über ganz Europa werten die entwickelten Reasoningverfahren die Semantik der Systemontologie aus und demonstrieren so die zustandsorientierte Wartung des Schienennetzes.

When web engineering methods are used for the development of web applications, models are created during the development process which describe the website. Using the information present in these models, it is possible to create usability tool support that is more advanced than current approaches, which do not rely on the presence of models.

This dissertation presents ideas for tool support during different phases of the development, such as the implementation phase or the testing phase. For example, if a tool knows from a model that the audience of a website are teenagers, it can examine whether the words and sentences used on the website are likely to be understood by teenagers.

An approach is presented to augment existing web engineering models with the additional information ("age" in this case) and to make it available to tools, e.g. via embedding it in HTML code.

Two prototypes demonstrate the concepts for integrating usability tool support into web engineering.

In dieser Arbeit untersuchen wir Perelmans Ricci-Fluss mit Chirurgie auf geschlossenen 3–Mannigfaltigkeiten, deren Ausgangsmetrik invariant unter einer vorgegebenen glatten Wirkung einer endlichen Gruppe ist. Eine solche Metrik kann stets durch Mittelung einer beliebigen Riemannschen

Metrik erzeugt werden, und wegen der Eindeutigkeit des Ricci-Flusses bleibt dieser bis zum Auftreten von Singularitäten invariant unter der Gruppenwirkung. Die technische Schwierigkeit besteht nun darin, Symmetrien

der evolvierenden Metrik zu kontrollieren, wenn sich der Fluss einer Singularität nähert.

Zu diesem Zweck konstruieren wir eine invariante singuläre S²–Blätterung auf dem Bereich der Mannigfaltigkeit, der von der Chirurgie betroffen ist. Insbesondere ermöglicht es diese, den Chirurgieprozess äquivariant durchzuführen und die Gruppenwirkung auf solchen Komponenten zu analysieren, die bei der Chirurgie komplett entfernt werden. Darüber

hinaus lässt sich mit Hilfe der Blätterung beschreiben, wie die Gruppenwirkungen vor und nach der Chirurgie zusammenhängen. Dadurch lassen sich aus dem Langzeitverhalten des Ricci-Flusses und der Gruppenwirkung

Rückschlüsse auf die ursprüngliche Wirkung ziehen.

Als Anwendung zeigen wir, dass jede glatte endliche Gruppenwirkung auf einer geschlossenen geometrischen 3–dimensionalen Mannigfaltigkeit mit sphärischer, hyperbolischer oder (S²×R)–Geometrie verträglich mit

der geometrischen Struktur ist, dass also eine invariante vollständige lokalhomogene Riemannsche Metrik existiert. Dies löst eine von William Thurston aufgestellte Frage zu Gruppenwirkungen auf geometrischen 3–Mannigfaltigkeiten, die für die übrigen fünf Geometrien bereits von Meeks und Scott gelöst wurde.

Die Arbeit behandelt verschiedene Modelle der

Quantenelektrodynamik aus Sicht der Mathematik.

Zunächst wird die Fortsetzung der Douglas-Kroll-Heß-Transformation für

Systeme mit mehr als einem Teilchen diskutiert. Anschließend

folgt eine ausführliche Untersuchung verschiedener

Eigenschaften komplex dilatierter Dirac-Operatoren.

Insbesondere werden positive und negative Spektralprojektionen

sowie entsprechende Transformationsfunktionen eingeführt.

Ferner wird der nicht-relativistische Limes solcher Operatoren untersucht. Diese Ergebnisse dienen als technische Vorbereitung zur Behandlung eines relativistischen Modells der Quantenelektrodynamik, sind jedoch auch von unabhängigem

Interesse.

In einem weiteren Kapitel wird das Dirac-Fock-Funktional im

Falle schwacher Elektron-Elektron-Wechselwirkung

behandelt. Insbesondere wird die Existenz von Lösungen der

Dirac-Fock-Gleichungen mit bestimmten zusätzlichen

Eigenschaften gezeigt. Es wird bewiesen, dass diese Lösungen

gewisse Minimierungseigenschaften bezüglich des

Dirac-Fock-Funktionals aufweisen.

Schließlich wird die Wechselwirkung von Materie mit dem

quantisierten elektromagnetischen Feld untersucht. Im

Pauli-Fierz-Modell sowie in einem relativistischen Modell

werden dabei obere und untere Schranken an die Lebensdauer

angeregter Zustände bewiesen.

Due to the increase in CPU power and the ever increasing data storage

capabilities, more and more data of all kind is recorded, including temporal

data. Time series, the most prevalent type of temporal data are derived in a

broad number of application domains. Prominent examples include stock price data

in economy, gene expression data in biology, the course of environmental

parameters in meteorology, or data of moving objects recorded by traffic

sensors.

This large amount of raw data can only be analyzed by automated data mining

algorithms in order to generate new knowledge. One of the most basic data

mining operations is the similarity query, which computes a similarity or

distance value for two objects. Two aspects of such an similarity function are

of special interest. First, the semantics of a similarity function and second,

the computational cost for the calculation of a similarity value. The semantics

is the actual similarity notion and is highly dependant on the analysis task at

hand.

This thesis addresses both aspects. We introduce a number of new

similarity measures for time series data and show how they can

efficiently be calculated by means of index structures and query

algorithms.

The first of the new similarity measures is threshold-based. Two

time series are considered as similar, if they exceed a user-given

threshold during similar time intervals. Aside from formally

defining this similarity measure, we show how to represent time

series in such a way that threshold-based queries can be efficiently

calculated. Our representation allows for the specification of the

threshold value at query time. This is for example useful for data

mining task that try to determine crucial thresholds.

The next similarity measure considers a relevant amplitude range.

This range is scanned with a certain resolution and for each

considered amplitude value features are extracted. We consider the

change in the feature values over the amplitude values and thus,

generate so-called feature sequences. Different features can finally

be combined to answer amplitude-level-based similarity queries. In

contrast to traditional approaches which aggregate global feature

values along the time dimension, we capture local characteristics

and monitor their change for different amplitude values.

Furthermore, our method enables the user to specify a relevant range

of amplitude values to be considered and so the similarity notion

can be adapted to the current requirements.

Next, we introduce so-called interval-focused similarity queries. A

user can specify one or several time intervals that should be

considered for the calculation of the similarity value. Our main

focus for this similarity measure was the efficient support of the

corresponding query. In particular we try to avoid loading the

complete time series objects into main memory, if only a relatively

small portion of a time series is of interest. We propose a time

series representation which can be used to calculate upper and

lower distance bounds, so that only a few time series objects have

to be completely loaded and refined. Again, the relevant time

intervals do not have to be known in advance.

Finally, we define a similarity measure for so-called uncertain time series,

where several amplitude values are given for each point in time. This can be

due to multiple recordings or to errors in measurements, so that no exact value

can be specified. We show how to efficiently support queries on uncertain time

series.

The last part of this thesis shows how data mining methods can be used to

discover crucial threshold parameters for the threshold-based similarity

measure. Furthermore we present a data mining tool for time series.