=Paper=
{{Paper
|id=None
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-733/proceedings.pdf
|volume=Vol-733
}}
==None==
Proceedings
23. GI-Workshop Grundlagen von Datenbanken
31.05.2011 - 03.06.2011
Obergurgl, Tirol, Österreich
Wolfgang Gassler, Eva Zangerle, Günther Specht (Hrsg.)
Vorwort
Liebe Teilnehmerinnen und Teilnehmer,
der 23. Workshop Grundlagen von Datenbanken (GvD) 2011 findet in Obergurgl,
Tirol, Österreich statt. Dieser viertägige Workshop wird vom GI-Arbeitskreis
Grundlagen von Informationssystemen im Fachbereich Datenbanken und
Informationssysteme (DBIS) veranstaltet und hat die theoretischen, konzeptionellen
und methodischen Grundlagen von Datenbanken und Informationssystemen zum
Thema. Organisiert wird der Workshop 2011 von der Forschungsgruppe
Datenbanken und Informationssysteme am Institut für Informatik an der Leopold-
Franzens-Universität in Innsbruck.
Der Workshop soll die Kommunikation zwischen Wissenschaftlern/-innen im
deutschsprachigen Raum fördern, die sich grundlagenorientiert mit Datenbanken und
Informationssystemen beschäftigen. Er ist insbesondere als Forum für
Nachwuchswissenschaftler/-innen gedacht, die ihre aktuellen Arbeiten in einem
größeren Forum vorstellen wollen. Mit der Kulisse der beeindruckenden Tiroler
Bergwelt bietet der Workshop auf 2000 Metern Meereshöhe einen idealen Rahmen
für die offenen und inspirierenden Diskussionen zu Datenbanken und
Informationssystemen. 18 Papiere wurde aus den Einsendungen ausgewählt und
werden in Obergurgl vorgestellt. Sie spannen ein weites Feld auf und zeigen, wie
aktiv und inspirierend die Datenbankforschung heute sein kann. Gerade das neue
Feld der Hauptspeicher- und NoSQL-Datenbanken hat die Auseinandersetzung mit
dem, was die eigentlichen Grundlagen der Datenbanken sind, neu beflügelt. Dabei
ist der Workshop über die Jahre, inzwischen 23 (!), längst von einem ursprünglich
eher theorie- und grundlagenlastigen Workshop auch zu einer Plattform für
anwendungsgetriebene und praktische Datenbankforschung geworden und hat sich
dabei auch dem damit verbundenen Gebiet der Informationssysteme geöffnet.
Wichtig ist die offene Atmosphäre in der man, diesmal zurückgezogen in der
Bergwelt, ohne Zeitzwang, intensiv diskutieren kann. Dies bedeutet insbesondere
nicht nur die üblichen drei Fragen nach dem Vortrag bevor der nächste kommt,
sondern sich die Zeit nehmen, vorgestellte neue Gedanken und Ansätze wirklich
gemeinsam zu diskutieren. Davon profitieren alle.
Hinzu kommen drei interessante Keynote-Vorträge von Harald Frick, Thomas
Neumann und Wolf-Tilo Balke. Ihnen sei an dieser Stelle für Ihre Bereitschaft und
Ihr Kommen gedankt.
Weiters danken wir dem Programmkomitee, das diesmal erstmals auf 18 Mitglieder
gewachsen ist und allen Gutachtern für ihre Arbeit. Das Organisations-Komitee und
dabei insbesondere Fr. Eva Zangerle und Hr. Wolfgang Gassler haben den Großteil
der Arbeit gestemmt. Ohne ihren unermüdlichen Einsatz und ihr Engagement wäre
der 23. Workshop nicht zustande gekommen. Herzlichen Dank! Besonderer Dank
gilt auch Eike Schallehn und dem GI-Arbeitskreis "Grundlagen von
Informationssystemen", der sich mit viel Einsatz um die erfolgreiche jährliche
Austragung des Workshops bemüht. Schließlich gilt mein Dank allen denen, die im
Hintergrund mitwirkten, dem ganzen DBIS-Team in Innsbruck, dem Haus in
Obergurgl und nicht zuletzt allen Autoren und Vortragenden. Sie machen den
Workshop erst zu dem, was er ist: Eine inspirierendes und motivierendes Forum für
offene Diskussionen über alle neuen Ideen rund um Datenbanken und
Informationssysteme. Sicher wird auch die gepflegte Hütten- und Bergatmosphäre
und der offene Kamin am Abend das seine dazu beitragen. Ich freue mich darauf.
Mit den besten Grüßen,
Günther Specht
Innsbruck am 26.05.2011
Komitee
Programm-Komitee
Wolf-Tilo Balke, Universität Braunschweig
Stefan Brass, Universität Halle
Erik Buchmann, Universität Karlsruhe
Stefan Conrad, Universität Düsseldorf
Johann-Christoph Freytag, Humboldt-Universität Berlin
Torsten Grust, Universität Tübingen
Andreas Henrich, Universität Bamberg
Hagen Höpfner, Universität Weimar
Harald Kosch, Universität Passau
Holger Meyer, Universität Rostock
Klaus Meyer-Wegener, Universität Erlangen
Bernhard Mitschang, Uni Stuttgart
Daniela Nicklas, Universität Oldenburg
Gunter Saake, Universität Magdeburg
Eike Schallehn, Universität Magdeburg
Ingo Schmitt, TU Cottbus
Holger Schwarz, Universität Stuttgart
Günther Specht, Universität Innsbruck
Organisations-Komitee
Eva Zangerle, Universität Innsbruck
Wolfgang Gassler, Universität Innsbruck
Günther Specht, Universität Innsbruck
Eike Schallehn, Universität Magdeburg, Speaker of the Working Group
Foundations of Information Systems
Weitere Reviewer
Eva Zangerle, Universität Innsbruck
Wolfgang Gassler, Universität Innsbruck
Wolfgang Pausch, Universität Innsbruck
Sebastian Schönherr, Universität Innsbruck
Robert Binna, Universität Innsbruck
Dominic Pacher, Universität Innsbruck
Inhaltsverzeichnis
Keynotes
Massive parallel In-Memory Database with GPU-based Query Co-Processor....................................................................... 1
(Harald Frick)
Efficient Query Processing on Modern Hardware .................................................................................................................. 3
(Thomas Neumann)
Conceptual Views for Entity-Centric Search.......................................................................................................................... 5
(Wolf-Tilo Balke)
Workshop-Beiträge
Ein Ansatz zu Opinion Mining und Themenverfolgung für eine Medienresonanzanalyse .................................................... 7
(Thomas Scholz)
Representing Perceptual Product Features in Databases ........................................................................................................ 13
(Joachim Selke)
Echtzeitüberwachung und Langzeitanalyse mittels eingebetteter Systeme ............................................................................ 19
(Tino Noack)
Analyse und Vergleich von Zugriffstechniken für funktionale Aspekte in RDBMS ............................................................. 25
(Matthias Liebisch)
Verbindung relationaler Datenbanksysteme und NoSQL-Produkte - Ein Überblick.............................................................. 31
(Andreas Göbel)
Ad-hoc Datentransformationen für Analytische Informationssysteme ................................................................................... 37
(Christian Lüpkes)
Wissensbasiertes Business Intelligence für die Informations-Selbstversorgung von Entscheidungsträgern .......................... 43
(Matthias Mertens)
Towards Efficiently Running Workflow Variants by Automated Extraction of Business Rule Conditions ........................... 49
(Markus Döhring, Christo Klopper und Birgit Zimmermann)
Vorschlag Hypermodelling: Data Warehousing für Quelltext................................................................................................ 55
(Tim Frey)
Die probabilistische Ähnlichkeitsanfragesprache QSQL2 ..................................................................................................... 61
(Sascha Saretz und Sebastian Lehrack)
Informationsanbieterzentrierte Spezifikation und Generierung von Informationssystem-Apps ............................................. 67
(Jonas Pencke, David Wiesner, Hagen Höpfner und Maximilian Schirmer)
XQuery Framework for Interoperable Multimedia Retrieval ................................................................................................. 73
(Mario Döller, Florian Stegmaier, Alexander Stockinger and Harald Kosch)
Workload Representation across Different Storage Architectures for Relational DBMS ...................................................... 79
(Andreas Lübcke, Veit Köppen und Gunter Saake)
Data Locality in Graph Databases through N-Body Simulation ............................................................................................. 85
(Dominic Pacher, Robert Binna und Günther Specht)
SpiderStore: A Native Main Memory Approach for Graph Storage ...................................................................................... 91
(Robert Binna, Wolfgang Gassler, Eva Zangerle, Dominic Pacher und Günther Specht)
Kriterien für Datenpersistenz bei Enterprise Data Warehouse Systemen auf In-Memory Datenbanken ............................... 97
(Thorsten Winsemann and Veit Koeppen)
Ein Verfahren zur automatischen Erstellung eines visuellen Wörterbuchs für die Bildsuche ................................................ 103
(Magdalena Rischka)
A feedback guided interface for elastic computing ................................................................................................................ 109
(Sebastian Schönherr, Lukas Forer, Hansi Weißensteiner, Florian Kronenberg, Günther Specht und Anita Kloss-Brandstätter)
Massive parallel in-memory
database with GPU based query co-
processor
Harald Frick
QuiLogic In-Memory DB Technology
ABSTRACT
This talk presents work on transforming SQL-IMDB, a commercial available in-
memory database system, into a massive parallel, array structured data processor
extending the “classic” query engine architecture with GPU based co-processing
facilities. The chosen approach is not just a simple re-implementation of common
database functionality like sorting, stream processing and joins on GPUs, instead we
take a holistic view and extend the entire query engine to work as a genuine, in-
memory, GPU supported database engine. We have partitioned the query engine so
that both CPU and GPU are doing what they are best at. The new SQL-IMDBg
query execution engine is a “Split-Work” engine which takes care to optimize,
schedule and execute the query plan simultaneous and in the most efficient way on
two (or more) different memory devices. The principal architecture of the engine,
based on simultaneous managing multiple memory devices (local/shared/flash-
memory ), was a natural fit to include the new GPU/video memory as just another
(high speed) memory device. All internal core engine data structures are now based
on simple array structures, for maximum parallel access support on multi- and many
core hardware. Data tables located on GPU video memory can always queried
together with CPU local- and shared-memory tables in “mixed” query statements.
Columns on GPU tables are also accessible through GPU based indexes. A special
index structure was developed based on sorted containers supporting both CPU and
GPU based index lookups. Table data can be manually and automatically split
between CPU and GPU and is held in vertically partitioned columns, which ease the
stream like processing for basic scan primitives and coalesced memory access
mechanism on GPU devices. Based on our experience gained, we see the GPU/video
memory as another important high speed memory device for in-memory database
systems, but which do not yet fit well into the architecture of current database
engines and therefore require a major effort in re-engineering the entire core
database architecture.
1
2
Efficient Query Processing on
Modern Hardware
Thomas Neumann
Lehrstuhl für Informatik III: Datenbanksysteme
Fakultät für Informatik
Technische Universität München
ABSTRACT
Most database systems translate a given query into an expression in a (physical)
algebra, and then start evaluating this algebraic expression to produce the query
result. The traditional way to execute these algebraic plans is the iterator model:
Every physical algebraic operator conceptually produces a tuple stream from its
input, and allows for iterating over this tuple stream. This is a very nice and simple
interface, and allows for easy combination of arbitrary operators,but it clearly comes
from a time when query processing was dominated by I/O and CPU consumption
was less important: The iterator interface causes thousands of expensive function
calls, degrades the branch prediction of modern CPUs, and ofter results in poor
code locality and complex book-keeping.
On modern hardware query processing can be improved considerably by processing
tuples in a data centric, and not an operator centric, way. Data is processed such that
it can be kept in CPU registers as long as possible. Operator boundaries are blurred
to achieve this goal. In combination with an code compilation framework this
results in query code that rivals the speed of hand-written code. When using these
techniques in the HyPer DBMS, TPC-H Query 1 for example can single-threaded
aggregated the scale factor 1GB data set in about 68ms on commodity hardware.
3
4
Conceptual Views for Entity-Centric
Search
Wolf-Tilo Balke
Databases and Informationsystems
University of Braunschweig
ABSTRACT
The retrieval of entity data has always been a core application of database systems
and querying an entity's attributes can be efficiently done using declarative
languages like SQL. But today's retrieval tasks more and more focus also on
conceptual aspects of entities, which often are not directly expressed by attributes.
For instance, users might want to find a 'thrilling' novel, unfortunately there is no
'suspense factor' attribute in today's online book stores. Consequently, entity-centric
search suffers from a growing semantic gap between the users’ intended queries and
the database’s schema. In the talk, we will propose the notion of conceptual views,
an innovative extension of traditional database views, which aim to uncover those
query-relevant concepts that are often only reflected by unstructured data related to
some entities. We will also take a look at promising techniques for mining
conceptual information and discuss open issues.
5
6
Ein Ansatz zu Opinion Mining und Themenverfolgung für
eine Medienresonanzanalyse
Thomas Scholz
Heinrich-Heine-Universität Düsseldorf pressrelations GmbH
Institut für Informatik Entwicklung
Universitätsstr. 1 Klosterstr. 112
D-40225 Düsseldorf, Deutschland D-40211 Düsseldorf, Deutschland
scholz@cs.uni-duesseldorf.de thomas.scholz@pressrelations.de
Zusammenfassung und Hörfunksender an. Im Bereich Soziale Netzwerke ha-
Heutzutage gibt es eine unüberschaubare Anzahl von Me- ben sich Dienstleister darauf spezialisiert, die Diskussionen
dien mit enorm vielen Artikeln und Beiträgen. Da in ih- und Kommentare aus Netzen wie Twitter, Facebook oder
nen neben vielen anderen potenziell nützlichen Informatio- bestimmte Foren automatisch zu erfassen und als Daten an-
nen wertvolle Meinungen zu Themen enthalten sind, ist eine zubieten.
automatische Beobachtung dieser Medien sehr interessant, Die Auswertung von einer großen Menge dieser Artikel
birgt aber zwei große Herausforderungen: eine automatisier- und Beiträge ist hingegen schwierig. Eine manuelle Auswer-
te Tonalitätsbestimmung (Opinion Mining) kombiniert mit tung ist nur mit erheblichen Aufwand möglich und für eine
einer Themenverfolgung. Diese zwei Aufgaben sind Teilge- automatische Auswertung gibt es erste Ansätze, aber längst
biete des Text Minings, auch Text Data Mining oder Know- noch keine allumfassende Lösung. Mit der Aufgabe diese Da-
ledge Discovery in Texten genannt. Diese Arbeit beschreibt ten zu erfassen und auszuwerten beschäftigt man sich beim
einen Ansatz für Opinion Mining und Themenverfolgung ba- Medienmonitoring bzw. bei der Medienresonanzanalyse. In
sierend auf einer Information Extraction Architektur. In der diesem Bereich arbeiten Ausschnittdienste.
Evaluation wird gezeigt, wie dieser Ansatz für Opinion Mi-
ning oder eine Themenverfolgung eingesetzt werden kann.
1.1 Medienmonitoring
Die riesigen Ströme aus Artikeln und Beiträgen enthalten
viele potenziell wertvolle Informationen zu Themen, Perso-
Kategorie nen, Firmen, Produkten, usw. Besonders die PR- und Marketing-
Data Mining and Knowledge Discovery Abteilungen von Unternehmen, Parteien und Verbänden in-
teressieren für diese Daten und deren Auswertung. Dabei in-
teressiert man sich besonders dafür, inwiefern sich das Image
Schlüsselwörter des Unternehmens oder das Image von bestimmten Pro-
Opinion Mining, Topic Tracking, Text Mining dukten, Marken und Dienstleistungen entwickelt. Aber auch
wie bestimmte Personen (Werbeträger, Vorstandsmitglieder,
1. EINLEITENDE MOTIVATION etc.) in diesen Medien wahrgenommen werden. Außerdem
von Bedeutung ist die Frage, auf welche Weise bestimmte
Das Internet, Printmedien, TV, Hörfunk und Soziale Netz-
Themen mit dem Unternehmen verknüpft sind. Beim Me-
werke sind eine Fundgrube von Meinungen zu bestimm-ten
dienmoitoring geht es darum Artikel zu erfassen und sam-
Themen in Form von Artikeln oder Beiträgen. Heutzutage
meln, die für PR- und Marketing Abteilungen interessant
ist es möglich diese in digitaler Form zu erfassen. Im Online
sind. Dazu werden von ihnen Themen oder Schlagwörter
Bereich können beispielsweise Crawler eingesetzt werden um
definiert. Dies ist auch interessant für Verbände, Vereine,
die Artikelseiten von Internetnachrichten zu erfassen. Durch
Parteien, Stiftungen, die teilweise zu klein sind um über ei-
Analyse des Seitenquelltextes und den Einsatz von Heuris-
ne eigene PR-Abteilung zu verfügen.
tiken kann der eigentliche Artikeltext gefunden werden. Ar-
tikel aus Printmedien können eingescannt und mit optischer
Zeichenerkennung (OCR) digitalisiert werden. Artikel und
1.2 Medienresonanzanalyse
Beiträge in digitaler Textform bieten auch teilweise die TV- Bei der Medienresonanz geht es darum zu bestimmten
Themen das mediale Echo zu analysieren.
Dies kann z. B. auf folgende Art und Weise geschehen:
Zunächst werden Themen definiert, die es zu untersuchen
gilt. Dies können beispielsweise Marken von Firmen sein
oder andere Begriffe wie Produktnamen, Personen oder ähn-
liches. Bei einem Medienbeobachter und einem Ausschnitt-
dienst würden die Kunden (meist PR-Abteilungen von Fir-
men oder Organisationen wie Parteien) Themen durch be-
23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 31.05.2011 - 03.06.2011, Obergurgl, Austria. stimmte Schlagwörter festlegen. Die Schlagwörter werden
Copyright is held by the author/owner(s). dann von Crawlern in den Medien gesucht, um die entspre-
7
chenden Artikel zu erfassen. • negativ: {bad, nasty, poor, negative, unfortunate, wrong,
Dann können diese Artikel bewertet werden, z.B. ob sie inferior}
wirklich relevant zu diesem Thema sind, wie exklusiv dieser
Diesen Aufbau durch einen Bootstrapping Algorithmus
Beitrag ist und am wichtigsten welche Tonalität er besitzt.
benutzt auch das bekannteste Wörterbuch: SentiWordNET
Die Tonalität beschreibt, ob ein bestimmter Artikel positi-
[5]. Als Quelle für neue Wörter benutzt es dazu Glossetexte
ve oder negative Meinungen zu einem Thema enthält. Es
und Wortbeziehungen in WordNET, dem bekanntesten eng-
ist auch beides möglich. Oft wird dies mit einem negativen
lischen, digitalen Wörterbuch. Mit diesen Wortbeziehungen
Zahlenwert für eine negative Tonalität und einem positiven
wie Synonym, Oberbegriff oder Unterbegriff werden neue
Zahlenwert für eine positive Tonalität festgehalten. Diese
Wörter gefunden, die dann die gleiche oder eine ähnliche
Bestimmung der Tonalität wird heutzutage bei den Medien-
Tonalität bekommen.
beobachtern noch rein manuell durch Medienanalysten aus-
Andere Ansätze benutzen nur WordNET oder ähnliche,
geführt, die die Texte lesen und meinungsbeinhaltende Pas-
allgemeine Wörterbücher [6, 7] oder Textsammlungen [2, 4]
sagen identifizieren und bewerten.
oder Suchanfragen [6]. Die Vorgehensweise ähnelt dabei oft
Allerdings stoßen solche Beobachtungsdienste aufgrund
der Vergrößerung der Wortmenge durch Bootstrapping.
der Menge der Artikel und Beiträge heute an ihre Grenzen,
Viele Ansätze [2, 3, 4, 13] beschränken sich auf das Gebiet
was manuell noch zu bearbeiten ist. Die Nachrichtenanzahl,
der Sentiment Analysis, also der Tonalitätsbestimmung in
die diese Dienste bearbeiten, nimmt stetig zu, aufgrund der
Kundenrezensionen. Einige Ansätze beschränken sich dabei
stärkeren Digitalisierung der Medien wie auch durch Entste-
nur auf Adjektive [3].
hen neuer Medien im Internet wie der Bereich Social Media.
Bei Kundenrezensionen ist eine Identifikation von Mei-
nungsblöcken nicht nötig. Eine Rezension besteht nur aus
1.3 Opinion Mining und Themenverfolgung als Meinungsblöcken. Um generell Meinungen zu finden, auch
Lösung wenn dies in einem langen Zeitungsartikel nur ein kleiner
Als Lösung für eine automatische Medienresonanzanalyse Absatz über ein bestimmtes Unternehmen ist, sind zunächst
bieten sich Opinion Mining und Themenverfolgung an, um noch anderere Schritte zuvor nötig. Ein satzbasierter Ansatz
die doch bisher meist manuell geleistete Arbeit zu unter- [7] bestimmt für jeden Satz einen Tonalitätswert basierend
stützen und perspektivisch zu ersetzen.. Mit Hilfe des Opi- auf den in ihm enthalten Wörtern. Dafür werden in zwei
nion Minings soll es gelingen meinungstragende Passagen Modellen einmal alle Wörter oder nur das stärkste Tonali-
innerhalb eines Textes zu finden und dann automatisch mit tätswort herangezogen. Überschreitet der Wert eine gewisse
einem Tonalitätswert zu versehen. Durch die Realisierung Grenze, dann enthält der Satz eine Meinung. Für einen an-
einer automatischen Themenverfolgung könnte die manuell deren Ansatz [1] enthält ein Satz eine Meinung, wenn er ein
vorgenommene Schlagwortverwaltung für die Themenzuord- Adjektiv enthält.
nung abgelöst werden. In der Kombination hätte man dann Auch kann man davon ausgehen, dass bei Sentiment Ana-
eine automatische Medienresonanzanalyse. lysis Ansätzen man schon mit einem kleineren Wörterbuch
Der Rest dieser Arbeit kann wie folgt zusammengefasst mit Tonalitätswerten zurecht kommt, da man es bei den Zie-
werden: Zunächst werden die Ansätze aufgezeigt, die schon len der Rezension nur mit Produkten und ähnlichem wie
zum Bereich des Opinion Minings und der Themenverfol- Filmen, Hotels usw. zu tun hat. Bei einer Medienresonan-
gung entwickelt wurden. Dann wird die Architektur ent- zanalyse werden aber gleichzeitig Entitäten wie Personen,
worfen, wodurch eine automatische Medienresonanzanalyse Organisationen, Produkte, Events oder Aktionen im Fokus
auf Basis von Natural Language Processing und Informati- stehen. Somit ändern sich auch die tonalitätsbildenen Wör-
on Extraction realisierbar wird. Anschließend wird in ersten ter, da nicht allein durch eine Beschreibung eines Produktes
Versuchen demonstriert, wie die Vorverarbeitung für Opi- etc. eine Tonalität ausgedrückt wird.
nion Mining und Themenverfolgung eingesetzt werden kön- In einer Rezension will der Autor seine Meinung dem Leser
nen. Abschließend werden dann aufgrund dieser Ergebnisse direkt vermitteln. In Zeitungsartikeln beschreibt der Autor
Schlussfolgerungen für das weitere Vorgehen gezogen. nicht nur direkte Meinungen, oft wird eher über Fakten und
Handlungen gesprochen, die sich auf bestimmte Personen
oder Organisationen beziehen, die dann eine Tonalität ent-
2. VERWANDTE ARBEITEN stehen lassen. Darum sollte ein solcher Ansatz auch nicht
nur Adjektive, sondern mehr Wortarten miteinbeziehen (z.
2.1 Opinion Mining B. Verben). Die meisten Ansätze [1, 2, 3] sind auf die eng-
Um die Tonalität eines Textes zu bestimmen, benutzen lische Sprache ausgerichtet. Darüber hinaus gibt es einige
viele Ansätze wie [2, 3, 9, 13] Wörterbücher, in denen Wörter Ansätze für die Chinesische Sprache, die allerdings nicht die
mit einem Tonalitätswert hinterlegt sind. Diese Wörterbü- Güte der Ergebnisse der auf Englisch arbeitenden Ansätze
cher werden meist so aufgebaut: Man beginnt mit einer klei- erreichen [4, 9].
neren Menge von positiven und negativen Wörtern. Dann
wird analysiert, ob neue Wörter oft mit positiven oder nega- 2.2 Themenverfolgung
tiven Wörtern auftauchen und entsprechend bekommt dann Wissenschaftliche Methoden [10, 14, 17, 18], die eine The-
das neue Wort einen positiven oder negativen Tonalitäts- menverfolgung realisieren, stellen ein Thema oft durch Schlag-
wert. wörter dar. Diese Schlüsselwörter werden dadurch extra-
Eine typische Menge von Saattonalitätswörtern sieht bei- hiert, dass die häufigsten Wörter eines Themas genommen
spielsweise so aus [16]: werden [14], die TF-IDF Methode zur Gewichtung benutzt
wird [10] oder die Wörter ausgewählt werden, die am wahr-
• positiv: {good, nice, excellent, positive, fortunate, cor- scheinlichsten in einem Thema vorkommen und am unwahr-
rect, superior} scheinlichsten in allen anderen Themen [17, 18].
8
Weiterhin gibt es einen Ansatz [8] einzelne Personen zu
verfolgen. In diesem Ansatz geht es dann später um eine Web Crawler Einheitliche
Dokumenten-
Visualisierung der Daten: Wie oft wurde die Person in den darstellung
beobachteten Medienquellen in einem bestimmten Zeitinter-
vall (beispielsweise an einem Tag) erwähnt.
Eine andere, sehr erfolgreiche Methode ist die Verfolgung Part-Of-Speech
von wörtlicher Rede [11] für ein bestimmtes Thema. Die Ar- Tagging
Satz Segmentierung Tokenisierung
beit beabsichtigt zu erforschen, wie sich Themen zwischen
Stemming
den verschieden Medien (in diesem Fall Onlinenachrichten
und Soziale Netzwerke) bewegen. Die Autoren untersuchen Natural Language Processing
nach welcher Zeit Themen in die sozialen Netzwerke gelan-
gen und ob es Themen gibt, die zuerst in den Sozialen Netzen
entstehen und dann erst in die herkömmlichen Nachrichten
gelangen. Hier werden Zitate aus wörtlicher Rede benutzt, Entity Recognition Ortho-Matching Pronomenauflösung
da diese laut den Autoren einfach zu verfolgen sind [11].
Ein Zitat steht dann für ein Thema. Durch einen graphba- Information Extraction
sierten Ansatz werden Zitate auch wieder erkannt, wenn sie
verkürzt oder leicht abgeändert werden.
Selten werden verschiedene Merkmale kombiniert [12], um Merkmale extrahieren
Lernverfahren Vorhersage-
Themen darzustellen oder zu verfolgen. Allerdings verlangt modell
dies auch größeren Aufwand, da man zunächst mittels Infor-
mation Extraktion Methoden viele Informationen im Vorlauf
erfassen muss, damit man daraus entsprechende Merkmale
generieren kann. Hier sind auch begrenzte Rechnerkapazitä- Abbildung 1: Ablauf der Verarbeitungsschritte
ten ein nicht zu vernachlässigender Aspekt.
auch nicht exakt die selbe Zeichenkette verwendet wird. Im
3. ANFORDERUNGEN FÜR DEN ANSATZ Falle einer Person könnte z.B. erst der komplette Name und
Die verschiedenen Arbeiten [1, 2, 3, 7, 12] zu diesen Berei- später im Text nur noch der Nachname benutzt werden.
chen zeigen oft, dass es sinnvoll ist, die Texte einer Vorver- Kommt eine Pronomenauflösung hinzu, dann wird eine En-
arbeitung zu unterziehen (s. Abbildung 1). Sehr vorteilhaft tität auch dann weiterverfolgt, wenn im Text für die Entität
erscheint der Einsatz von Natural Language Processing und nur noch Pronomen stehen wie “sie” oder “ihn”, die sich aber
Information Extraction. Wenn ein Ansatz diese Vorgaben auf die entsprechende Person beziehen.
für eine Vorverarbeitung erfüllt, dann entstehen neue Mög- Darüber hinaus kann es noch sehr nützlich sein, weitere
lichkeiten, die später aufgeführt werden. Informationen wie den grammatikalischen Fall oder das Ge-
schlecht von Wörtern zu bestimmen. Auch Textpassagen mit
3.1 Natural Language Processing wörtlicher Rede oder die Extraktion von Nomenphrasen sind
Gerade Natural Language Processing (NLP) wird in vie- weitere nützliche Informationsbausteine, die in einer weite-
len anderen Ansätzen benutzt, um unter anderem Adjektive ren Verarbeitung aufgegriffen werden können.
zu identifizieren [1, 2, 3]. Beim Natural Language Processing
ist nach dem simplen Aufteilen des Textes in Sätze und Wör- 3.3 Neue Möglichkeiten
ter das sogenannte Part-Of-Speech Tagging der wichtigs- Diese Vorverarbeitung lässt sich für das Opinion Mining
te Analyseschritt. Dabei werden die Wörter aufgrund von und die Themenverfolgung folgendermaßen einsetzen:
Wahrscheinlichkeitsmodellen wie Hidden Markov Modellen Durch die Bestimmung der verschiedenen Wortarten las-
grammatikalischen Wortarten wie Nomen, Verben, Adjekti- sen sich für das Opinion Mining Wörterbücher aus Adjekti-
ven usw. zugeordnet. Außerdem sollte ein Stemming durch- ven, Verben und Adverben extrahieren. Hier stellt sich noch
geführt werden, damit alle Wörter auch in Ihrer Grundform die Frage, wie man diesen Tonalitätswert bestimmt. Viele
verfügbar sind. Mit dieser Zurückführung werden viele Me- Ansätze bilden dazu Maße, die auf das Zusammenauftre-
thoden vereinfacht, die auf der Identifikation von bestimm- ten mit positiven bzw. negativen Tonalitätswörtern beruhen.
ten Wörtern beruhen oder einen Text als Wortlisten mit Wenn man viele annotierte Meinungsblöcke besitzt, kann
Häufigkeiten darstellen. man auch Standardansätze aus dem Information Retrieval
wie TF-IDF darauf anwenden. Ebenso kann man Bootstrap-
3.2 Information Extraction ping einsetzen.
Durch Information Extraction (IE) [15] ist es darüber hin- Auch Nominalphrasen können in dem Wörterbuch auf-
aus möglich, Entitäten im Text wie Personen, Organisatio- genommen werden. Diese können auch für die Darstellung
nen und Orte zu erkennen. Diese Named Entity Recognition eines Themas von großem Nutzen sein.
(NER) ist ein gutes Beispiel, wie IE auf NLP aufbaut: Zuerst Durch die Erkennung von Personen, Organisationen usw.
werden Nomen identifiziert und z.B. durch Listen genauer kann man bei der Tonalitätsbestimmung unterscheiden, ob
bestimmt, ob es eine Person ist und eventuell zusätzlich, ob nun eine Person oder ein Produkt besprochen wird. Dadurch
es nur ein Vorname, Vor- und Nachname ist usw. Diese En- kann man die Bewertung des Vokabulars darauf anpassen.
titäten werden dann über den Text verfolgbar, wenn weitere Bei der Themenverfolgung kann man Themen durch die
Techniken wie Ortho-Matching und eine Pronomenauflösung Anwesenheit von Entitäten beschreiben. Das Vorhandensein
durchgeführt wird. Ortho-Matching beschreibt das Erken- bzw. die Abwesenheit einer Entität kann ebenso wie Schlag-
nen der Entität im selben Text an mehreren Stellen, wenn wörter dazu benutzt werden ein Thema zu beschreiben und
9
damit auch zu verfolgen. Auch könnte man genauso wie bei Wortart Klassifikationsverfahren Genauigkeit
Schlagwörtern das Auftreten mit TF-IDF gewichten, was Adjektive
nun konkret bedeuten würde: Die Häufigkeit einer Entität Support Vector Machine 80,81 %
multipliziert mit der inversen Dokumentenfrequenz in der Naive-Bayes 68,34 %
sie vorkommt. Bei dieser Gewichtung ist noch zu klären, was k-Nearst-Neighbour 53,60 %
den gesamten Dokumentenkorpus darstellt. Dies könnte ein Verben
zeitlicher Ausschnitt sein (z. B. ein Monat). Support Vector Machine 82,07 %
Zusätzlich könnte diese Gewichtung interessante Informa- Naive-Bayes 72,29 %
tionen über die Entwicklung eines Themas liefern, weil es an- k-Nearst-Neighbour 56,05 %
zeigt welche Entitäten in welchen Themen eine starke Rolle Adverbien
spielen. Support Vector Machine 75,61 %
Dies kann man zusätzlich mit bisherigen Ansätzen für Naive-Bayes 66,08 %
Themendarstellung durch Schlagwörter sowie die Verfolgung k-Nearst-Neighbour 53,79 %
von wörtlicher Rede kombinieren.
Diese Vorverarbeitungsschritte benötigen natürlich auch Abbildung 2: Tonalitätsbestimmung
Rechenzeit. Da allerdings dazu auf einem riesigen Datenfeld
(den Texten) nur gelesen werden muss, ist eine Parallelisie-
rung der Vorverarbeitung durchführbar. 100
90
4. EVALUATION
80
Um zu überprüfen, wie dieser Ansatz mit NLP und IE
für Opinion Mining und eine Themenverfolgung eingesetzt 70
werden kann, wird evaluiert, wie mit bestimmten Wortar-
60
ten automatisch eine Tonalität bestimmt werden kann und
F-Score in %
ob mit Entitäten eine thematische Zuordnung möglich ist. 50
Dafür werden zuvor klassifizierte Daten benutzt.
40
Diese Evaluation soll erste Hinweise geben, ob es grund-
sätzlich mit diesen Merkmalen möglich ist, die fundamenta- 30
len Bausteine einer Medienresonanzanalyse maschinell
20
durchzuführen: Tonalitätsbestimmung und Themenzuordnung.
Dabei geht es auch weniger um die Bestimmmung des op- 10
timalen Lernverfahrens. Der Einfachheit halber wurden dazu
0
im ersten Schritt drei typische Klassifikationsverfahren ver-
wendet. Diese bieten sich an, weil die Daten schon vor der Personen Organisationen Orte Alle
Evaluation mit entsprechenden Klassen versehen sind.
4.1 Tonalitätsbestimmung Abbildung 3: Themenzuordnung
Für diesen Test wurden 1600 Nachrichtenmeldungen mit
800 positiven und 800 negativen Meldungen analysiert. Um
eine Tonalität zu erhalten, wurden mittels NLP Adjektive, schützer warnen vor der ’Umfrucht’-Falle” oder “Rekordjahr:
Adverbien und Verben aus dem Text extrahiert und mittels Audi belohnt Mitarbeiter mit Millionen”)2 .
Stemming auf ihre Stammform zurückgeführt. Danach wur- Das beste Klassifikationsverfahren der drei hier getesteten
den invertierte Listen von diesen Dokumenten erzeugt und Verfahren ist eindeutig die Support Vector Machine. Darum
die einzelnen Terme mittels TF-IDF gewichtet. wird sie nun auch im zweiten Teil der Evaluation angewen-
Nach der Erzeugung dieser Attribute wurden die Daten det.
in einer 10-fach-über-Kreuz-Validierung durch drei Klassifi-
kationsverfahren getestet: Support Vector Machine (SVM), 4.2 Themenzuordnung
Naive-Bayes und k-Nearest-Neigbours mit k=7. Im zweiten Test wurden 204 Texte zu zwei sehr allgemei-
Bei den Resultaten zeigte sich, das diese doch recht naive nen Themen gesammelt. Die Themen waren “Finanzmarkt”
Methode (es wird beispielsweise nicht betrachtet, ob irgend- und “Parteien”.
welche Negationen anwesend sind) tatsächlich erste brauch- Dann wurden aus diesen Texten die Entitäten Personen,
bare Hinweise geben kann. Organisationen und Orte extrahiert. Diese Entitäten wur-
Es zeigte sich, dass die Vermutung, nur Adjektive allein den dann wiederum als Terme genommen, die mittels TF-
würden die Tonalität bestimmen, nicht zutrifft. Die Grup- IDF gewichtet wurden. Abschließend wurde eine SVM be-
pe der Verben schneidet schon besser ab. Hier scheint der nutzt um die Daten in einer 10-fach-über-Kreuz-Validierung
Unterschied zwischen Sentiment Analysis bezogen auf Kun- zu evaluieren.
denrezensionen und Opinion Mining bezogen auf Nachrich- Die Ergebnisse veranschaulicht Abbildung 3. Interessant
ten deutlich zu werden. Kundenrezensionen beziehen ihre ist hier, dass bei den einzelnen Merkmalen die Organisatio-
Tonalität wohl eher durch Adjektive (“die Bildqualität ist nen das beste Resultat liefern (ca. 85,29 %). Dies kann aber
super” oder “der Autofokus ist zuverlässig”)1 , während in mit der Themenauswahl (“Finanzmarkt” und “Parteien”) zu
Nachrichten dies nicht unbedingt der Fall ist (“Verbraucher- tun haben, in der wahrscheinlich generell mehr Organisatio-
1 2
Beispiele aus einer Amazon.de Kundenrezension Beispiele von Spiegel.de am 4.3.2011
10
nen eine Rolle spielen bzw. die Organisationen das trennende darstellung mit Merkmalen dadurch? In der Evaluation kam
Kriterium sind. schon die Frage auf, ob Personen bei kleineren Themen nicht
Auch Orte scheinen charakteristisch für Themen zu sein eine wichtigere Rolle zur Themenbeschreibung spielen.
(ca. 81,37 %). Kaum überraschend spielt der Ort “Frankfurt” Insgesamt zeigt sich aber, dass die Vorverarbeitung durch
im ersten Thema eine wichtigere Rolle als im zweiten Thema Natural Language Processing und Information Extraction
und für “Berlin” ist es umgekehrt. von großem Vorteil ist, da sie für beide Aufgabenstellungen,
Das Merkmal Person ist nicht so erfolgreich (nur ca. 68,14 Opinion Mining und Themenverfolgung, viele neue Möglich-
%). Bei den hier vorliegenden Themen gab es hinsichtlich keiten eröffnet und diese im Ansatz für eine Medienresonan-
der Personen auch durchaus Überschneidungen, weil mehre- zanalyse funktionieren.
re Personen in beiden Themen auftauchten. Eine interessan-
te Frage stellt sich nun dahingehend, ob dies bei kleineren 6. LITERATUR
Themen vielleicht seltener der Fall ist.
[1] L. Dey and S. K. M. Haque. Opinion mining from
Insgesamt zeigt sich das wünschenswerte Resultat: Mit
noisy text data. In Proc. of the 2nd workshop on
allen Entitäten gemeinsam wird das beste Ergebnis erzielt
Analytics for noisy unstructured text data, AND ’08,
(ca. 85,78 %).
pages 83–90, 2008.
[2] X. Ding, B. Liu, and P. S. Yu. A holistic lexicon-based
5. SCHLUSSFOLGERUNG UND WEITER- approach to opinion mining. In Proc. of the
international conference on Web search and web data
FÜHRENDE FRAGESTELLUNGEN mining, WSDM ’08, pages 231–240, 2008.
Die Ergebnisse der Evaluation lassen darauf schließen, [3] X. Ding, B. Liu, and L. Zhang. Entity discovery and
dass sich aufbauend auf dem beschriebenen Anforderungs- assignment for opinion mining applications. In Proc.
profil eine automatische Tonalitätsbestimmung und Themen- of the 15th ACM SIGKDD international conference on
verfolgung realisieren lässt. Knowledge discovery and data mining, KDD ’09, pages
Zu dem Aspekt des Opinion Minings fehlen noch viele Be- 1125–1134, 2009.
standteile, die in einem Text die Tonalität verändern kön- [4] W. Du and S. Tan. An iterative reinforcement
nen. Es hat sich gezeigt, dass die Worte allein schon im An- approach for fine-grained opinion mining. In Proc. of
satz funktionieren, aber noch großes Verbesserungspotenzial Human Language Technologies: The 2009 Annual
vorhanden ist. Conference of the North American Chapter of the
Dazu ist zu erarbeiten, ob es noch bessere Methoden der Association for Computational Linguistics, NAACL
Gewichtung gibt als der Standardansatz über TF-IDF. Au- ’09, pages 486–493, 2009.
ßerdem muss überlegt werden, wie man die Tonalitätswör-
[5] A. Esuli and F. Sebastiani. Determining the semantic
ter beispielsweise in einem Wörterbuch verwalten kann. Als
orientation of terms through gloss classification. In
nächste Fragestellung schließt sich dann an, wie man mit
Proc. of the 14th ACM international conference on
semantischen Merkmalen wie Negation oder dem Bezug zu
Information and knowledge management, CIKM ’05,
Entitäten umgeht.
pages 617–624, 2005.
Darüber hinaus ist ein weiteres spannendes Problem die
[6] X. Huang and W. B. Croft. A unified relevance model
Identifizierung der Meinungsblöcke, also der Textpassagen,
for opinion retrieval. In Proc. of the 18th ACM
die eine Meinung beinhalten. Ein Tonalitätsgrenzwert für
conference on Information and knowledge
Abschnitte und Sätze ist denkbar, aber auch die Lokalisie-
management, CIKM ’09, pages 947–956, 2009.
rung durch die Entitäten im Text, für die man sich erstens
verstärkt interessiert und die sich zweitens mit ausreichend [7] S.-M. Kim and E. Hovy. Automatic detection of
vielen tonalitätsbildenen Wörtern umgeben. opinion bearing words and sentences. In Companion
Bei der Themenverfolgung haben die Experimente zunächst Volume to the Proceedings of the International Joint
nur den Wert von Entitätenerkennung in einem einfachen Conference on Natural Language Processing
Beispiel gezeigt. Hier müsste die Kombination mit klassi- (IJCNLP), 2005.
schen Schlagwortansätzen und neueren Ansätzen, wie die [8] M. Krstajic, F. Mansmann, A. Stoffel, M. Atkinson,
Einbeziehung von wörtlicher Rede, genutzt werden, um eine and D. A. Keim. Processing online news streams for
bessere Themendarstellung zu erhalten und zusätzlich inter- large-scale semantic analysis. In ICDE Workshops,
essante Fakten über ein Thema zu sammeln. Diese Fakten pages 215–220, 2010.
können Folgendes beinhalten: Wie stark sind welche Perso- [9] L.-W. Ku, Y.-T. Liang, and H.-H. Chen. Opinion
nen mit welchen Themen verbunden? Oder gibt es zentrale extraction, summarization and tracking in news and
Zitate/Aussagen, die immer wieder aufgegriffen werden. blog corpora. In AAAI Symposium on Computational
Allerdings muss zunächst die Frage beantwortet werden, Approaches to Analysing Weblogs (AAAI-CAAW),
wie man die Entitäten sinnvoll mit Ansätzen wie Schlagwör- pages 100–107, 2006.
tern und die Verfolgung von Zitaten verbinden kann. Dies [10] S. Lee and H.-J. Kim. News keyword extraction for
wird Gegenstand der zukünftigen Arbeit sein, wobei auch zu topic tracking. In Proc. of the 4th International
klären ist, wie man diese Kombination für die Verwaltung Conference on Networked Computing and Advanced
einer Themenverfolgung sinnvoll einsetzen kann. Information Management - Volume 02, pages 554–559,
Weiterhin ist dabei die Größe eines Themas zu beachten 2008.
(für die Defintion der Größe eines Themas gibt es viele Mög- [11] J. Leskovec, L. Backstrom, and J. Kleinberg.
lichkeiten, die Anzahl der Artikel zu einem Thema ist eine Meme-tracking and the dynamics of the news cycle. In
nahe liegende Lösung). Wie wirkt sich die Größe der Themen Proc. of the 15th ACM SIGKDD international
auf die Verwaltung aus? Und wie verhält sich die Themen- conference on Knowledge discovery and data mining,
11
KDD ’09, pages 497–506, 2009.
[12] B. Li, W. Li, Q. Lu, and M. Wu. Profile-based event
tracking. In Proc. of the 28th annual international
ACM SIGIR conference on Research and development
in information retrieval, SIGIR ’05, pages 631–632,
2005.
[13] M. M. S. Missen, M. Boughanem, and G. Cabanac.
Comparing semantic associations in sentences and
paragraphs for opinion detection in blogs. In Proc. of
the International Conference on Management of
Emergent Digital EcoSystems, MEDES ’09, pages
80:483–80:488, 2009.
[14] X. Tang, C. Yang, and J. Zhou. Stock price
forecasting by combining news mining and time series
analysis. In Proc. of the 2009 IEEE/WIC/ACM
International Joint Conference on Web Intelligence
and Intelligent Agent Technology - Volume 01,
WI-IAT ’09, pages 279–282, 2009.
[15] J. Turmo, A. Ageno, and N. Català. Adaptive
information extraction. ACM Comput. Surv., 38, July
2006.
[16] P. D. Turney and M. L. Littman. Measuring praise
and criticism: Inference of semantic orientation from
association. ACM Trans. Inf. Syst., 21:315–346,
October 2003.
[17] X. Wang, C. Zhai, X. Hu, and R. Sproat. Mining
correlated bursty topic patterns from coordinated text
streams. In Proc. of the 13th ACM SIGKDD
international conference on Knowledge discovery and
data mining, KDD ’07, pages 784–793, 2007.
[18] J. Zeng, C. Wu, and W. Wang. Multi-grain
hierarchical topic extraction algorithm for text
mining. Expert Syst. Appl., 37:3202–3208, April 2010.
12
Representing Perceptual Product Features in Databases
Joachim Selke
Institut für Informationssysteme
Technische Universität Braunschweig
Braunschweig, Germany
ABSTRACT summarize our own recent work towards solving this problem. In
Many modern goods have both factual and perceptual features. particular, we present a series of use cases illustrating the benefits
While factual features such as technical specifications can easily be of our approach.
handled by existing database technology, perceptual features such In this following, we use movies as a running example. Movies
as design or usage experience are very hard to deal with. However, are particularly suited for this task as they appeal to a wide range
with the huge success and growing market share of online shopping, of people and provide a large variety of both factual and perceptual
retailers face the need to provided detailed and structured informa- features. In addition, movies perfectly illustrate the problem of
tion about perceptual product features to their customers. In this lacking support for perceptual features in databases: It has been
paper, we analyze why dealing with perceptual product features in shown that, when selecting movies, consumers rely far more on
databases is difficult and summarize our current efforts on tackling perceptual movie features (funny, romantic, scary, . . . ) than factual
this problem. ones (actors, directors, release year, . . . ) [3]. However, the ideas
and results presented in this paper can easily be transferred to other
types of products.
1. INTRODUCTION
Marketing theory distinguishes between two types of product fea-
tures: Factual and perceptual ones [4, 8]. Factual features are those
2. EXISTING APPROACHES
that can easily be named and specified. Typical factual features In this section, we take a close look at existing approaches to
are technical specifications (e.g., length, height, and weight) and handling perceptual product features in information systems. We
traditional publication metadata (e.g., authors, number of pages and identified three different groups of approaches: those based on ex-
year of publication). Perceptual features are those that usually are plicit data provided by experts, those based on textual data provided
hard to describe and tend to involve an emotional reaction or phys- by users, and special-purpose approaches that implicitly deal with
ical contact to the respective product. Typical perceptual features perceptual product features. In addition, in domains where prod-
are artistic or stylistic properties such as the mood of songs, the ucts can be represented in digital form (e.g., music or movies),
sophistication of novels, and the character depth in movies. (low-level) features can be extracted automatically.
While factual product features can easily be represented and
managed by existing database technology (e.g., by introducing a 2.1 Explicit Modeling by Experts
database attribute per feature), working with perceptual product Besides the traditional classification of movies into a small num-
features is much more complicated. This is mainly because percep- ber of major genres [2, 9], many movie databases recently adopted
tual features tend to be vague and defy precise definitions (e.g. the more refined classification schemes. While some just introduced a
borders of literary genres). However, paradoxically, there are estab- larger number of possible genres (e.g., the rental service Netflix1
lished ways to express perceptual features using natural language expanded its simple genre list into a taxonomy covering 485 gen-
(e.g., sporty car or clunky cell phone), which surprisingly mostly are res), others decided to describe movies using generally applicable
not a matter of taste but are based on general agreement. Therefore, description attributes. Popular examples are the metadata provider
we strongly believe that established database technology is indeed AllMovie2 , which classifies its 440,000 movies with respect to more
able and suited to store, process, analyze, and answer queries based than 5,000 different moods, themes, tones, and types (e.g., Ensemble
on perceptual product features. We just have to find out how this Film, Haunted By the Past, and Intimate), and the recommendation
can be done in practice. service Clerkdogs3 , which rates each movie with respect to 37 dif-
In this paper, we survey existing approaches to handling percep- ferent attributes (e.g., Character Depth, Geek Factor, and Violence)
tual product features in databases, point out their limitations, and on a 12-point scale. Essentially, all these approaches try to cap-
ture a movie’s perceptual features by means of a set of predefined
databases attributes, which can either contain binary values (as in
AllMovie) or numbers (as in Clerkdogs).
Although this approach looks rather straightforward and seems
to be easy to implement in practice, it comes with many problems.
First of all, clearly identifying and narrowing down the most relevant
23rd GI Workshop on Foundations of Databases 1 http://www.netflix.com
(Grundlagen von Datenbanken), 2 http://www.allmovie.com
31.5.2011–3.6.2011, Obergurgl, Austria. 3 http://www.clerkdogs.com
Copyright is held by the author/owner(s).
13
individual perceptual features tends to be difficult. However, even if liked by most of these other users. In a way, movie features and user
a comprehensive and generally understandable classification system tastes are modeled implicitly when using collaborative filtering.
has been developed and experts have been trained how to use it Recently, a series of recommendation algorithms has been de-
correctly and consistently, manually classifying all movies is a huge veloped that try to decompose the rating matrix (movies are rows,
amount of work. users are columns, and ratings are entries) into the product of two
An even worse problem is the actual consistency of these movie smaller matrices [6]. These so-called factor models have an im-
classifications. We recently compared the genre judgments made by portant by-product, which usually is neglected by recommendation
three major movie databases and found that the agreement among algorithms: the representation of each movie as points in some
them is moderate at best, being just slightly less directed towards abstract coordinate space. Here, movies with similar coordinates
to completely random genre assignments than to perfect agreement tend to be rated similarly by different users, whereas users with very
[11, 12]. As we restricted our analysis only to the most popular different coordinates tend to be perceived very differently. From
movie genres, even worse results can be expected for less established this perspective, one can think of these coordinates as a embedding
and/or more complex classification schemes. of movies into some abstract semantic space.
Our own analysis of the semantic spaces produced by recent
2.2 Textual Descriptions by Users recommender algorithms showed that these spaces indeed capture
An alternative approach to making perceptual movie features major perceptual features of movies [10, 11, 12]. However, the main
available to movie databases has been adopted by movie portals problem of semantic spaces hindering their use for general purpose
such as the Internet Movie Database4 (IMDb) or Rotten Tomatoes5 database applications is the total lack of intuitive understandability.
(RT). Instead of trying to represent movies in a structured fashion To illustrate this problem, Table 1 show the first three dimensions of
by means of explicit database attributes, they focus on textual de- a 100-dimensional semantic space extracted from the Netflix Prize
scriptions, usually in the form of reviews provided by arbitrary users ratings data set7 (about 20k movies, 500k users, and 100M ratings).
(IMDb) or (semi-)professional critics (RT). For each dimension, we listed the those popular movies that received
Although textual descriptions give users a comprehensive and the five highest and five lowest scores with respect to this dimension.
helpful characterization of each individual movie, it is difficult Clearly, these axes do not offer any intuitive interpretation. However,
to search for movies or provide targeted movie recommendations the relative positions in semantic spaces are indeed meaningful. To
given only textual data. One the the rare services offering movie give an example, Table 2 shows the five nearest neighbors of three
search based on movie reviews is Nanocrowd6 , which applies in- popular movies.
formation retrieval methods to extract so-called nanogenres from
textual data. Each movie is characterized by a set of nanogenres, 2.4 Content-Based Feature Extraction
where each nanogenre is represented by a three-word group (e.g., In some domains, one can provide a (near-)complete description
sports/ballpark/loves or chemistry/adorable/formulaic). However, of each product in digital form. Prime examples are images, music,
these nanogenres tend to be much less informative and understand- and movies. In these cases, it is possible to automatically derive
able than explicit database attributes that have been manually created so-called low-level features from the products itself, thus avoiding
by experts. any dependence on external product descriptions. For example,
Another drawback of text-based movie descriptions is the lack common low-level features of images are color histograms, sym-
of data. While blockbusters are commented by a large number metry properties, and measures for contrast. Low-level features are
people, less popular movies often receive just a very small number contrasted by high-level features (concepts), which describe those
of reviews, which tend to provide only a partial movie description aspects of content objects a user is interested in.8 For example,
and are too short to effectively apply methods of text analysis. high-level features of images are the types of objects (sun, beach,
mother, child, . . . ), events (playing, talking, . . . ), or abstract con-
2.3 Implicit Modeling for Special Purposes cepts (family, fun, . . . ) associated with a photo. The multimedia
The third major approach is collaborative filtering as used in the content description standard MPEG-7 defines a large number of low-
area of recommender systems [1]. Here, the only data available level features and also provides a language to annotate multimedia
about movies are numerical ratings provided by users (e.g., on a content with custom-defined high-level features.
scale ranging from one to five stars), where each user assigns just a In state-of-the-art content-based multimedia retrieval systems,
single number to each movie he rated. As rating movies is an almost low-level features are usually extracted automatically from the avail-
effortless task, usually there is a large number of ratings from many able content, whereas the use of high-level features tends to require
different users available. For example, in IMDb, there are about a significant amount of human interaction. Although there are initial
a hundred times more ratings than reviews, while even relatively approaches to automatically derive selected high-level features from
unknown movies still receive a substantial number of ratings. low-level features, there is still a large discrepancy between the lim-
So far, this kind of data has only been used for special problems ited information that one can extract from the available multimedia
such as similarity search (finding those movies that are most similar data and the interpretation that the same data has for users [7]. This
to a given one) or recommendations (providing a list of movies problem is usually referred to as semantic gap.
that are likely to appeal to a given user). Here, the basic idea is to When comparing content-based feature extraction to the three ap-
analyze the ratings for systematic patterns indicating similar taste proaches discussed previously, we see that low-level features loosely
across a group of users or similar properties in a group of movies. correspond to semantic spaces and high-level features to explicitly
For example, to provide recommendations to some user u, one might modeled attributes. However, there are important differences:
first look for other users who rated most of the movies rated by u in
• As low-level features must be extracted by means of spe-
a similar way, and then recommend those movies to u that have been
7 http://www.netflixprize.com
4 http://www.imdb.com 8 Sometimes, the distinction into low-level and high-level features
5 http://www.rottentomatoes.com
is refined to a 10-layer pyramid structure for classifying different
6 http://www.nanocrowd.com feature types of multimedia content [5].
14
Axis Popular high-scoring movies Popular low-scoring movies
1 Indiana Jones and the Temple of Doom (1984), The Eternal Sunshine of the Spotless Mind (2004), Garden
Godfather (1972), American Pie (1999), Top Gun State (2004), Two Weeks Notice (2002), Bend It Like
(1986), The Silence of the Lambs (1991) Beckham (2002), Miss Congeniality (2000)
2 Twister (1996), Titanic (1997), Lost in Translation Ocean’s Twelve (2004), Mission: Impossible
(2003), Napoleon Dynamite (2004), Ghost (1990) (1996), Paycheck (2003), Anger Management (2003),
Ocean’s Eleven (2001)
3 The League of Extraordinary Gentlemen (2003), American Pie (1999), Big Daddy (1999), Mr. Deeds
Chicago (2002), Van Helsing (2004), Steel Magnolias (2002), The General’s Daughter (1999), Lethal
(1989), Ocean’s Twelve (2004) Weapon 4 (1998)
Table 1: Popular movies receiving high and low scores on the first three coordinate axes.
Rocky (1976) Dirty Dancing (1987) The Birds (1963)
Rocky II (1979) Pretty Woman (1990) Psycho (1960)
Rocky III (1982) Footloose (1984) Vertigo (1958)
Hoosiers (1986) Grease (1978) Rear Window (1954)
The Natural (1984) Ghost (1990) North By Northwest (1959)
The Karate Kid (1984) Flashdance (1983) Dial M for Murder (1954)
Table 2: Three popular movies and their respective five nearest neighbors in semantic space.
cialized extraction algorithms, they are tied to a particular • Semantic spaces created from a large number of user-provided
representation of the original content. Consequently, low- ratings capture major perceptual features of movies. However,
level features extracted from images cannot be compared to semantic spaces as such do not offer any intuitive interpreta-
low-level features extracted from songs. In contrast, semantic tion and thus cannot be used to communicate with users.
spaces are derived from user feedback which can be provided
for any product type in the same way, thus enabling the direct 3. PROPOSED SOLUTION
comparison of images and music. In addition, the design of
At first view, the result of our above analysis is rather disillu-
effective low-level extraction algorithms is a complex task,
sioning. Intuitively understandable models of perceptual movie
which must be hand-crafted for each product domain under
properties are expensive to create and lack data quality, semantically
consideration.
meaningful models cannot be understood, and the third option seems
• Semantic spaces are derived directly from human feedback to combine both disadvantages.
(e.g., star ratings), which is turn is based on the most rele- However, there is still hope. In [11] we introduced a data model
vant perceptual product properties. Low-level features only that tries to combine the strengths of the approaches mentioned
capture statistical properties of the data representation such above. To be more precise, we propose to represent each movie by
as color histograms. Therefore, the semantic gap between three different types of database attributes:
semantic spaces and user perception can be expected to be
A. attributes describing factual movie properties,
lower than the semantic gap present in current content-based
multimedia retrieval systems. B. attributes making a selected number of perceptual properties
For these reasons, we decided to put aside content-based fea- explicit (manual classification), and
ture extraction for the moment and focus on the three remaining C. attributes containing the movie’s coordinates in some seman-
approaches discussed above. However, in future work we plan to tic space.
compare the ideas presented in this paper to existing methods from
content-based multimedia retrieval where this is possible. This approach brings several advantages. Probably most impor-
tant is that the three different types of attributes can work together to
2.5 Conclusion reduce the weaknesses of each of them. In the following, we show a
We can draw the following conclusions from the findings pre- series of examples illustrating this idea (for technical details, please
sented in this section: see [11]).
• Modeling perceptual movie features by explicit attributes
requires a huge amount of manual work but still leads to data Enhancing the data quality in type-B attributes.
of questionable quality. However, users can easily understand By aligning the manual classification of movies as expressed in
the meaning of these attributes. type-B attributes to the semantic space, we are able to detect are
large number of possibly misclassified movies. The basic idea is
• Capturing perceptual movie features by means of textual de- that movies that are classified into the same category should also
scriptions is helpful for users when looking for information be located close together in the semantic space. If we find a movie
about each individual movie. However, this kind of data is m that has the same value with respect to some type-B attribute but
difficult to process automatically, cannot be understood as is very different from other movies having this value with respect
easily as explicit attributes, and the amount of available data to the semantic space, then m is likely to be misclassified by the
is scarce for less popular movies. experts. By identifying such movies and giving human experts
15
Sport
Drama Romance space (by identifying a small continuous region in space), and then
looking for other movies that are located close to the center to this
region. By applying a simple weighting scheme, we are able to
Action Adventure Sci-Fi Mystery produce a, say, top-10 list of the most Tarantino-ish movies. To
give an example, Table 3 shows our results for Tarantino and two
Figure 1: Genre clouds for Rocky (1976) and Star Trek (1979). popular actors. Here, we used a support vector machine to learn
where movies directed by Tarantino tend to be located in semantic
space and used this information to find very similar movies that have
a chance carefully re-check problematic movies, the data quality not been directed by Tarantino [11]. Apart from minor exceptions
can be increased. In our experiments on genre classifications [11], (in particular, The Professional and Dragon: The Bruce Lee Story),
we have been able to detect possibly misclassified movies with these results look very promising. In summary, we have been able to
a mean precision of about 55% and a mean recall of about 25%, understand users’ implicit concepts by of mapping type-A attributes
which is significantly better than drawing random samples (the only to the semantic space.
alternative approach available). In summary, with the help of type-C
attributes we are able to reduce a significant weakness of type-B 4. CONCLUSION AND OUTLOOK
attributes (data quality). In this paper, we have discussed the problem of representing
perceptual product features in databases. We concluded that each
Saving manual work in creating type-B attributes. existing approach alone does not provide an acceptable solution to
To significantly reduce the amount of work required to manually this problem as it comes with severe disadvantages. However, by
classify all movies with respect to the type-B attributes, automatic combining several methods into a joint data model, we have been
classification can be applied. Here, given a binary type-B attribute able to reduce the weaknesses of each individual approach and boost
(e.g., the genre Action), a human experts provides a small number its strengths. Our examples show promising results, which we are
(e.g., 10) of clearly positive examples (i.e., typical Action movies) going to analyze in detail in future work. In addition, as already
and the same number of clearly negative examples (i.e., obvious indicated in Section 2.4, we plan to compare our work to approaches
non-Action movies). Using a support vector machine classifier that from content-based multimedia retrieval. For example, for genre
categorizes all remaining movies based on the training data and the classification tasks, it would be interesting to compare semantic
type-C semantic space representation of movies, we have been able spaces derived from ratings to low-level features extracted from the
to produce results being only of slightly lower quality than those actual movies.
created by human experts [11]. By means of the method described
previously, the data quality can easily be increased incrementally. 5. REFERENCES
In summary, with the help of type-C attributes we are able to reduce [1] G. Adomavicius and A. Tuzhilin. Toward the next generation
another significant weakness of type-B attributes (amount of work).
of recommender systems: A survey of the state-of-the-art and
possible extensions. IEEE Transactions on Knowledge and
Enriching type-B attributes. Data Engineering, 17(6):734–749, 2005.
Again, by comparing type-B attributes to the semantic space rep- [2] D. Chandler. An introduction to genre theory, 1997. Available
resented by type-C attributes we are able to determine to what degree from
a type-B attribute value applies to each movie. For example, IMDb http://www.aber.ac.uk/media/Documents/intgenre.
only assigns binary genre judgments to its movies, which leads
[3] E. Cooper-Martin. Consumers and movies: Some findings on
to the classification Drama/Romance/Sport for the movie Rocky
experiential products. In Advances in Consumer Research,
(1976) and Action/Adventure/Mystery/Sci-Fi for the movie Star
volume 18, pages 372–378. 1991.
Trek (1976). Although this classification is justified, there are sev-
eral problems: Rocky contains romantic elements but it is a highly [4] E. C. Hirschman and M. B. Holbrook. Hedonic consumption:
Emerging concepts, methods and propositions. Journal of
untypical Romance movie. It is most well-known for being a typical
sports movie with dramatic activities. Similarly, Sci-Fi is widely Marketing, 46(3):92–101, 1982.
recognized as Star Trek’s most prominent genre, while it is a rather [5] C. Jörgensen, A. Jaimes, A. B. Benitez, and S.-F. Chang. A
untypical Mystery movie. By analyzing the semantic space for conceptual framework and empirical research for classifying
where typical movies of genre X are located, we are able to judge visual descriptors. Journal of the American Society for
how typical an assigned genre for each movie really is. To illustrate Information Science and Technology, 52(11):938–947, 2001.
this, Figure 1 depicts a “genre clouds” for the above two movies. We [6] Y. Koren and R. Bell. Advances in collaborative filtering. In
automatically generated it from IMDb’s binary genre assignments F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor, editors,
(type B) in combination with a semantic space extracted from ratings Recommender Systems Handbook, pages 145–186. Springer,
(type C) [11]. 2011.
[7] Y. Liu, D. Zhang, G. Lu, and W.-Y. Ma. A survey of
Enabling conceptual queries. content-based image retrieval with high-level semantics.
When describing their movie preferences, users often refer to Pattern Recognition, 40(1):262–282, 2007.
factual movie properties as means attributes that approximately [8] P. Nelson. Information and consumer behavior. Journal of
characterize an intuitive concepts that they are unable to express Political Economy, 78(2):311–329, 1970.
otherwise. For example, movies in the style typically associated [9] C. Preston. Film genres. In W. Donsbach, editor, The
with the director Quentin Tarantino could be called Tarantino-ish International Encyclopedia of Communication. Blackwell,
movies. In fact, Google counts 4530 Web pages mentioning this 2008.
term. We refer to database queries in this style as conceptual queries. [10] J. Selke and W.-T. Balke. Extracting features from ratings:
We are able to answer such queries by first finding out where movies The role of factor models. In Proceedings of M-PREF 2010,
directed by Quentin Tarantino are typically located in the semantic pages 61–66, 2010.
16
Stallone-ish Tarantino-ish Jim Carrey-ish
Universal Soldier (1992) True Romance (1993) EDtv (1999)
Commando (1985) GoodFellas (1990) Innerspace (1987)
Missing in Action (1984) The Usual Suspects (1995) Bedazzled (2000)
Red Heat (1988) Casino (1995) Cadillac Man (1989))
Raw Deal (1986) Desperado (1995) Pleasantville (1998)
Bloodsport (1988) The Professional (1994) Dragon: The Bruce Lee Story (1993)
The Last Boy Scout (1991) Killing Zoe (1994) Honey, I Shrunk the Kids (1989)
The Running Man (1987) Full Metal Jacket (1987) Alive (1993)
Kickboxer (1989) 2 Days in the Valley (1996) Shallow Hal (2001)
The Delta Force (1986) Go (1999) Punchline (1988)
Table 3: Top 10 results for three different conceptual queries.
[11] J. Selke and W.-T. Balke. T EAMWORK: A data model for
experience products. ifis technical report, Institut für
Informationssysteme at Technische Universität Braunschweig,
2011.
[12] J. Selke, S. Homoceanu, and W.-T. Balke. Conceptual views
for entity-centric search: Turning data into meaningful
concepts. In Proceedings of BTW 2011, pages 327–346, 2011.
Acknowledgments
I am very grateful to Prof. Dr. Wolf-Tilo Balke for providing valu-
able guidance and supervising my doctoral thesis, which will be
based partly on the work presented in this paper.
17
18
Echtzeitüberwachung und Langzeitanalyse
mittels eingebetteter Systeme
Tino Noack
TU Cottbus
Institut für Informatik, Informations- und Medientechnik
Lehrstuhl Datenbank- und Informationssysteme
Tino.Noack@tu-cottbus.de
Kurzfassung Überwachung technischer Systeme ist ein sehr weit verbrei-
Der vorliegende Beitrag skizziert ein interdisziplinäres For- tetes Forschungsfeld und bezieht sich auf viele heterogene
schungsvorhaben im Rahmen einer Doktorarbeit. Einer der Anwendungsdomänen. Häufig werden Überwachungssyste-
Forschungsbeiträge ist die Kombination von Echtzeitüber- me für spezielle Anwendungen entworfen, entwickelt und
wachung und Langzeitanalyse. Diese Kombination basiert implementiert. Dies führt zu erhöhten Entwicklungskosten
auf existierenden Ansätzen und umfasst Event-Condition- und gleichzeitig zur Abnahme der Flexibilität bzw. der Wie-
Action-Regeln (ECA-Regeln), Data-Mining-Technologien so- derverwendbarkeit. Bedeutende Anwendungen sind z.B. die
wie Complex Event Processing (CEP). Im vorliegenden Bei- Überwachung von Raumfahrzeugen [21], [22] oder die Über-
trag werden zunächst drei grundlegende Annahmen und fünf wachung von Schienenfahrzeugen [16]. Die Überwachung von
Überwachungsanforderungen erarbeitet. Darauf aufbauend Raumfahrzeugen ist besonders herausfordernd, da komplette
wird die Forschungsfrage detailliert betrachtet. Die Grundla- Systemtests in der vorgesehenen Systemumwelt (dem Welt-
ge für die vorgestellte Idee bildet ein mathematisches Modell raum) und kontinuierliche Wartung unpraktisch bzw. un-
(der Zustandsraum), welches das Wissen über das zu über- möglich sind.
wachende System repräsentiert. Mit Hilfe dieses Zustands- Aufgrund der steigenden Komplexität heutiger Produk-
raums werden durch die Anwendung von Data-Mining-Tech- te werden verbesserte Überwachungsansätze benötigt, die
nologien ECA-Regeln erzeugt und an eine CEP-Anwendung, heutige und zukünftige Anforderungen berücksichtigen. Im
die sich auf einem eingebetteten System befindet, übertra- vorliegenden Beitrag steht die Überwachung des zu überwa-
gen. Dieser Teilschritt bezieht sich auf die Langzeitanalyse. chenden Systems, welches im Weiteren als Produkt bezeich-
Die CEP-Anwendung wertet anschließend die übertragenen net wird, im Vordergrund. Das Produkt besteht aus einer
ECA-Regeln auf einem kontinuierlichen Strom von Sensor- Menge von Systemkomponenten. Nur aufgrund des Zusam-
daten aus und erzeugt Aktionen. Dieser Teilschritt bezieht menspiels der einzelnen Systemkomponenten untereinander
sich auf die Echtzeitüberwachung. Weiterhin wird eine Pro- genügt das Produkt einer vorher definierten Funktion bzw.
zesskette vorgestellt, die zyklisch durchlaufen wird und zur Aufgabe. Zusätzlich wirken externe Einflüsse aus der umge-
Kombination von Echtzeitüberwachung und Langzeitanaly- benden Produktumwelt auf das Produkt (vgl. [15], [17]). So-
se dient. Hier wird ein dynamischer und flexibler Überwa- mit bezieht sich die Überwachung des Produkts je nach An-
chungsansatz vorgestellt. wendungsdomäne und je nach Überwachungsziel zusätzlich
auf externe Einflüsse und auf die korrekte Arbeitsweise der
beteiligten Systemkomponenten. Eine strikte Trennung der
Schlüsselwörter Überwachung externer Einflüsse, des Produkts selbst und
Überwachung, Echtzeit, Langzeit, Eingebettete Systeme, der einzelnen Systemkomponenten, aus denen das Produkt
Datenströme, Data Mining, Complex Event Processing besteht, kann nicht immer vollzogen werden.
Der vorliegende Beitrag skizziert ein interdisziplinäres For-
schungsvorhaben im Rahmen einer Doktorarbeit. Einer der
1. EINLEITUNG Forschungsbeiträge ist die Kombination von existierenden,
Viele Produkte, in denen sich eingebettete Systeme ver- gut bekannten und bereits praktisch angewendeten Ansät-
bergen, sind sicherheitskritisch und unterliegen Echtzeitan- zen, die für die Kombination von Echtzeitüberwachung und
forderungen wie z.B. Kraft-, Schienen-, Luft- oder Raum- Langzeitanalyse eingesetzt werden können. Anhand des Ein-
fahrzeuge. Eingebettete Systeme werden oft für Regelungs-, satzes von existierenden Ansätzen sind Einsparungen im Be-
Kontroll- und Überwachungsfunktionalitäten eingesetzt. Die reich der Entwicklungskosten möglich. Das Forschungsvor-
haben umfasst die Erstellung von Event-Condition-Action-
Regeln (ECA-Regeln) [10], Data-Mining-Technologien [27]
sowie Complex Event Processing (CEP) [12]. Hier wird ein
dynamischer und flexibler Überwachungsansatz vorgestellt,
der auf den drei folgenden Annahmen basiert:
1. Anwendungsübergreifend werden ähnliche Methodiken
23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 31.05.2011 - 03.06.2011, Obergurgl, Austria. und Algorithmen für die Überwachung technischer Sys-
Copyright is held by the author/owner(s). teme eingesetzt.
19
2. Das Auftreten von Fehlern im laufenden Betrieb lässt
sich nicht ausschließen. Daher muss durch die Ände-
rung des Systemverhaltens so schnell wie notwendig
eine angemessene Aktion ausgelöst werden.
3. Teile des gesamten Überwachungsprozesses sind semi-
manuell. Informationssysteme werden nur zur Unter-
stützung des Überwachungsprozesses angewendet.
Der Rest des vorliegenden Beitrags ist wie folgt organi-
siert. Kapitel 2 beschreibt ein Anwendungsbeispiel. In Kapi-
tel 3 wird der Begriff eines eingebetteten Systems definiert,
so wie es für die Forschungsarbeit verwendet wird. Kapi-
tel 4 fasst Anforderungen an die Überwachung zusammen Abb. 1: Eingebettetes System
und aufbauend darauf wird in Kapitel 5 die Forschungsfrage
detailliert betrachtet. Kapitel 6 beschreibt das Systemmo- Sensoren und Aktoren mit dem Produkt und der Produk-
dell, welches dem vorgeschlagenen Überwachungsansatz zu tumgebung in Interaktion. Die elektronischen Baugruppen
Grunde liegt. In Kapitel 7 wird der vorgeschlagene Überwa- können mittels eines internen Netzwerkes miteinander ver-
chungsansatz detailliert beschrieben. Kapitel 8 fasst existie- bunden sein. Zusätzlich kann eine temporäre Verbindung zu
rende Lösungen zusammen und schließlich wird in Kapitel 9 einem externen Informationssystem vorhanden sein. Weitere
eine Zusammenfassung gegeben. Informationen zu eingebetteten Systemen finden sich u.a. in
[28], [20] und [23].
2. ANWENDUNGSBEISPIEL: ZUGUN- 4. ÜBERWACHUNGSANFORDERUNGEN
GLÜCK VOM ICE 884 IN ESCHEDE Entsprechend des vorgestellten Anwendungsbeispiels und
Das Zugunglück vom ICE 884 in Eschede ist ein sehr pra- in Anbetracht der abstrakten Architektur eines eingebette-
xisnahes Anwendungsbeispiel. Die Hauptursache des kata- ten Systems werden hier folgende fünf Überwachungsanfor-
strophalen Zugunglücks war der Bruch eines gummigefeder- derungen erarbeitet: Zeit, Lokalität, Wissen, Systemressour-
ten Radreifens. Dieser Bruch war die Folge von langfris- cen und Schärfe. Abbildung 2 fasst die genannten Anforde-
tigen Verschleißerscheinungen (z.B. Verringerung der Rad- rungen zusammen.
reifendicke und Korrosion). Bereits einige Monate vor dem Zeit: Diese Anforderung bezieht sich auf die zeitliche und
Unglück wurden während der Wartung anomale Messwer- kontinuierliche Veränderung der Bauteile.
te an dem besagten Radreifen festgestellt. Die detaillier-
te Bruchflächenanalyse stellte heraus, dass die langfristigen • kurzfristig: Es können plötzliche Änderungen der Bau-
Verschleißerscheinungen zu einem Riss in dem Radreifen, teile (z.B. Bruch des Radreifens) auftreten. Es ist not-
lange vor dem Unglück, führten. Der Bruch des Radreifens wendig, diese in Echtzeit zu erkennen.
führte zur Entgleisung des Zuges ([24], [13]). Der beschriebe-
• langfristig: Zur Erkennung langfristiger Einflussfakto-
ne Anwendungsfall deutet auf langfristige und auf kurzfristi-
ren und Veränderungen (z.B. Verschleiß und Alterung)
ge Einflussfaktoren hin. Verschleißerscheinungen sind lang-
sind Langzeitanalysen notwendig.
fristige Einflussfaktoren und der Bruch des Radreifes bzw.
die Zugentgleisung sind kurzfristige Einflussfaktoren. Lokalität: Diese Anforderung bezieht sich auf Wechselwir-
Durch die Langzeitanalyse können langfristige Verschleiß- kungen der Einflussfaktoren und die räumliche Lokalität der
erscheinungen erkannt, analysiert und bewertet werden. Der Überwachung.
Bruch des Radreifens und die nachfolgende Entgleisung des
• lokal : Fehler, die sich z.B. auf wenige Bauteile bezie-
Drehgestells haben zu einer plötzlichen und signifikanten
hen, müssen durch eine lokale Überwachung erkannt
Veränderung des Systemverhaltens geführt (bspw. Schlinger-
werden.
bewegung des entgleisten Drehgestells). Anhand der Anwen-
dung der Echtzeitüberwachung mittels eines eingebetteten • global : Aufgrund der steigenden Komplexität von Pro-
Systems kann diese plötzliche Veränderung des Systemver- dukten und eingebetteter Systeme korrelieren die Ein-
haltens erkannt und in einem angemessenen Zeitraum eine flussfaktoren zunehmend. Somit entstehen komplexe
Aktion (z.B. Notbremsung) durchgeführt werden. Zusammenhänge zwischen den Bauteilen, die durch ei-
ne globale Analyse erfasst und erkannt werden müssen.
3. EINGEBETTETES SYSTEM Wissen: Diese Anforderung bezieht sich auf das vorhandene
Abbildung 1 skizziert die abstrakte Architektur eines ein- Wissen über das eingebettete System, das Produkt und die
gebetteten Systems, wie sie hier Einsatz findet. Eingebettete Produktumwelt.
Systeme sind in ein umgebendes Produkt eingebettet. Das • bekannt: Es ist notwendig das bekannte Wissen über
Produkt ist in eine Produktumgebung eingebettet. Einge- das eingebettete System, das Produkt und die Produk-
bettete Systeme enthalten elektronische Baugruppen (Hard- tumwelt möglichst umfassend und zielorientiert für die
ware), die die Systemkomponenten repräsentieren. Zusätz- Überwachung einzusetzen.
lich sind diese elektronischen Baugruppen mit Software aus-
gestattet. Eingebettete Systeme unterliegen eingeschränkten • unbekannt: Aufgrund unbekannter bzw. unvorherseh-
Systemressourcen wie z.B. Prozessorleistung, Strom- und barer Umstände ist ein dynamischer und flexibler Über-
Speicherverbrauch. Das eingebettete System steht mittels wachungsprozess notwendig.
20
gesamte zu überwachende Produkt. Dabei ist die Anzahl der
Attribute je nach Anwendungsdomäne und Überwachungs-
ziel unterschiedlich. Diese Daten können zur Identifikation
von relevanten Wechselwirkungen Verwendung finden. Data-
Mining-Technologien werden eingesetzt, um das Wissen über
das Produkt mit der Zeit zu erhöhen.
In Bezug zum genannten Anwendungsbeispiel werden die
Daten mittels eines externen Informationssystems gesam-
melt. Diese persistent gespeicherten Daten werden einge-
setzt, um einen Klassifikator zu erlernen, der zwischen be-
kanntem und unbekanntem Verhalten des Zuges unterschei-
den kann. Dies wird in [8] als Anomalieerkennung bezeich-
Abb. 2: Überwachungsanforderungen net. Weiterhin können diese gespeicherten Daten zur Er-
kennung gradueller Änderungen der Systemkomponenten in
Bezug zur Zeit genutzt werden. Somit können langfristige
Systemressourcen: Diese Anforderung bezieht sich auf die Einflussfaktoren wie z.B. Verschleiß erkannt werden.
vorhandenen Ressourcen, die für die Überwachung zur Ver- Echtzeitüberwachung wird auf dem eingebetteten Sys-
fügung stehen. tem durchgeführt. Dieses unterliegt eingeschränkten System-
• uneingeschränkt: Die Überwachung von Systemen be- ressourcen. Die Echtzeitüberwachung wird automatisch, on-
nötigt äußerst viele Systemressourcen. Somit ist eine line und ohne Benutzerinteraktion durchgeführt. Plötzliche
Kombination von interner und externer Überwachung Änderungen des Systemverhaltens müssen so schnell wie not-
(hybrides Überwachungssystem [26]) notwendig, um wendig erkannt werden. Anschließend ist eine angemessene
ausreichend Ressourcen für die Überwachung zur Ver- Aktion notwendig. Die gelernten Klassifikatoren bzw. ECA-
fügung zu stellen. Regeln werden hier zum eingebetteten System übertragen
und anschließend zur Erkennung von Änderungen des Sys-
• eingeschränkt: Aufgrund der eingeschränkten System- temverhaltens bzw. zur Anomalieerkennung eingesetzt. CEP
ressourcen eingebetteter Systeme ist es notwendig, die- ist hier ein ausgewähltes Werkzeug, um die ECA-Regeln
se angemessen und zielführend für die Überwachung auf den kontinuierlichen Datenströmen anzuwenden. ECA-
einzusetzen. Regeln repräsentieren das Wissen über das Produkt. Ver-
halten, welches nicht zu diesen Regeln passt, kann als un-
Schärfe: Diese Anforderung bezieht sich auf die Auswertung
bekannt bzw. anomal gekennzeichnet werden. Dies ist ein
von Bedingungen (vgl. [25], [4]).
lokaler Aspekt, da nur eine Teilmenge der vorhandenen At-
• scharf : Systemzustände müssen exakt und zuverlässig tribute für die Definition eines speziellen Verhaltens mittels
durch eine exakte binäre Auswertung von Bedingungen ECA-Regeln Verwendung findet. Wie auch bei der Langzeit-
(Boolesches Modell) erkannt werden. analyse ist die Anzahl der Attribute je nach Anwendungsdo-
mäne und Überwachungsziel unterschiedlich, aber geringer
• unscharf : Diese scharfe Grenze zwischen Systemzu- als für die Anwendung der Langzeitanalyse.
ständen ist nicht immer gegeben. Um dies zu berück- In Bezug zum genannten Anwendungsbeispiel stellen das
sichtigen, wird die exakte binäre Auswertung mittels Brechen des Radreifens und die anschließende Entgleisung
Zugehörigkeitsgrade zwischen 0 und 1 verallgemeinert. signifikante und plötzliche Änderungen der Fahreigenschaf-
Der Wert 1 wird als volle Zugehörigkeit und der Wert ten des Zuges dar. Nachfolgend wird in Bezug zum Anwen-
0 als nicht zugehörig interpretiert. dungsbeispiel der ECA-Ansatz kurz erläutert. Ein Ereignis
(Event) ist hier das Verhalten des Zuges zu einer bestimmten
Zeit. Die Bedingung (Condition) bezieht sich auf die gelern-
5. FORSCHUNGSFRAGE ten Klassifikatoren bzw. die Regeln, die ermittelt wurden,
Es gibt eine Lücke zwischen Echtzeitüberwachung und um das Verhalten des Zuges zu einem bestimmten Zeitpunkt
Langzeitanalyse von Ereignissen, die die Zuverlässigkeit von zu klassifizieren. Eine Aktion (Action) kann bspw. die Ver-
Produkten beeinträchtigen. Dies ist die Motivation für un- ringerung der Geschwindigkeit des Zuges oder das Auslösen
sere Forschung an der Kombination von Echtzeitüberwa- der Notbremse sein, um materielle Schäden und menschliche
chung und Langzeitanalyse von Ereignissen. In dem ersten Opfer zu vermeiden.
Schritt werden hier alle Überwachungsanforderungen außer
der Schärfe betrachtet. Abbildung 3 fasst die Forschungsfra-
ge grafisch zusammen. 6. SYSTEMMODELL
Langzeitanalyse benötigt meist sehr viele Systemressour- Ein wesentlicher Punkt ist das Verständnis der Eingangs-
cen. Zusätzlich sind Data-Mining-Technologien semi-manu- daten. Sensoren erzeugen kontinuierliche Daten. Diese kon-
ell und müssen durch Fachpersonal betreut und gepflegt wer- tinuierlichen Sensordaten werden hier als Datenströme in-
den. Aus diesem Grund ist eine Offlineverarbeitung auf ei- terpretiert. Ein Datenstrom besteht aus einer Sequenz von
nem externen Informationssystem mit nahezu uneingesch- Datenelementen. Häufig ist diese Sequenz sehr lang. Ein Sys-
ränkten Systemressourcen notwendig. Data-Mining-Techno- tem, welches Datenströme verarbeitet, hat keine A-Priori-
logien werden hier für das Erlernen von Klassifikatoren ein- Kontrolle über die Reihenfolge der eintreffenden Datenele-
gesetzt, die anschließend durch ECA-Regeln repräsentiert mente. Die erneute Übertragung von verlorenen Datenele-
werden. Die persistent gespeicherten Daten umfassen alle ge- menten ist nicht möglich. Weitere Informationen über Da-
sammelten Attribute und geben eine globale Sicht über das tenströme finden sich u.a. in [1], [7], [3] und [14].
21
Abb. 3: Kombination von Echtzeitüberwachung und
Langzeitanalyse Abb. 4: Zustandsraum [8]
Die Menge von Eigenschaften, die das Zielsystem beschrei-
ben, wird hier als eine Menge von Attributen A1 , ... , An erlernen, der das Wissen über das Produkt repräsentiert.
interpretiert. Diese Attribute können u.a. nominal, ordinal Zunächst wird in diesem Kapitel eine Prozesskette für die
oder metrisch sein. Attributwerte sind Funktionen der Zeit, Überwachung beschrieben. Anschließend wird diese Prozess-
so dass Werte von Ai einer Funktion ai : T → R entsprechen. kette in eine abstrakte Überwachungsarchitektur überführt.
Dabei ist T die Zeit und R die Menge der reellen Zahlen. So- Die Prozesskette ist in Abbildung 5 grafisch verdeutlicht.
mit ist ein Zustand in Bezug zur Zeit ein Zustandsvektor Sie ist in zwei Teile gegliedert. Der obere Teil repräsen-
tiert die Echtzeitüberwachung auf dem eingebetteten Sys-
a1 (t) tem. Der untere Teil repräsentiert die Langzeitanalyse auf
a2 (t) einem externen Informationssystem. Zur besseren Übersicht-
~a(t) = . .
.. lichkeit ist die untere Teilkette in umgekehrter Reihenfolge
dargestellt.
an (t)
Im ersten Schritt startet die Prozesskette mit Ereignissen
Der Raum, der durch die Attribute aufgespannt wird, heißt bzw. Zustandsvektoren. Die Vorverarbeitung ist der zweite
Zustandsraum. Die Anzahl der Attribute definiert die An- Schritt. Dieser kann u.a. zur Filterung, zur Selektion oder
zahl der Dimensionen des Zustandsraums. Eine Menge von für Fensterfunktionen, zur Verringerung des Verarbeitungs-
Zustandsvektoren im Zustandsraum, die ähnliche Arten von aufwands, Verwendung finden. Die Ausführung der Regeln
Zuständen repräsentieren, können geometrisch interpretiert ist der dritte Schritt. In diesem dritten Schritt werden die
werden. Diese geometrische Interpretation wird im Rahmen im Voraus definierten Regeln auf dem Datenstrom angewen-
von Data-Mining-Technologien als Cluster bezeichnet ([27], det. Der vierte Schritt umfasst das Senden von Nachrichten
[8], [5], [2]). zu den Aktoren. Der fünfte Schritt wird für die temporäre
Abbildung 4 veranschaulicht den Zustandsraum in einem Speicherung verwendet. Das schließt Datenaggregation zur
Zeitfenster unter Berücksichtigung der zwei Attribute A1 Minimierung des Speicherbedarfs sowie angemessene Spei-
und A2 . Zur besseren Übersichtlichkeit sind die Zustands- cherstrategien wie z.B. Ringpuffer oder eingebettete Daten-
vektoren als Punkte dargestellt. Sei S die Menge aller mög- banken mit ein. Der letzte Schritt der obersten Teilkette be-
lichen Systemzustände bzw. der gesamte Zustandsraum, Ck zieht sich auf das Senden der Daten vom eingebetteten Sys-
die Menge der bekannten Cluster tem zum stationären System. Aufgrund der temporären Ver-
S und Cu die MengeT aller un-
bekannten Cluster, so dass Ck Cu = S und Ck Cu = ∅. bindung mittels des externen Netzwerkes können die Daten
Somit sind bekannte Cluster komplementär zu unbekann- nur von Zeit zu Zeit an das externe Informationssystem ge-
ten Clustern. In Abbildung 4 repräsentieren die Cluster Ck1 sendet werden. Die genannten Schritte sind automatisch. Es
und Ck2 Mengen von bekannten Systemzuständen. Der Clus- ist notwendig, dass jeder Teilschritt austauschbar und konfi-
ter Cu1 sowie die Punkte pu1 und pu2 stehen exemplarisch gurierbar (z.B. Plug-in-System) ist, um einen dynamischen
für unbekannte Systemzustände. In [8] werden diese unbe- und flexiblen Überwachungsansatz bereitzustellen. Somit ist
kannten Systemzustände als Anomalien bezeichnet. Das Ziel es möglich, das CEP-System auf die vorhandene Hardware
des gelernten Systemmodells ist die Klassifizierung eines Zu- und den beabsichtigten Überwachungszweck zuzuschneiden.
standsvektors zu einem Zeitpunkt t zu einem bekannten Der erste Schritt der Langzeitanalyse betrifft das Laden
Cluster. Kann dieser Zustandsvektor keinem bekannten Clus- der empfangenen Daten vom eingebetteten System in ein
ter zugeordnet werden, so ist dieser Zustandsvektor unbe- persistentes Datenverzeichnis wie z.B. ein Data Warehou-
kannt und wird als eine Anomalie gekennzeichnet. Somit re- se (DWH). Der zweite Schritt umfasst die Erstellung der
präsentieren die ECA-Regeln den Klassifikator, der mittels Regeln mittels Data-Mining-Technologien. Dazu gehört die
der Data-Mining-Technologien erlernt wurde. Integration der empfangenen Daten in den Zustandsraum.
Dabei steigt das Wissen über das Produkt durch die Inte-
7. KOMBINATION VON ECHTZEITÜBER- gration von neuen und noch unbekannten Zustandsvektoren
in den Zustandsraum. Aktuell werden hier folgende Algo-
WACHUNG UND LANGZEITANALYSE rithmen zur Klassifikation bzw. überwachtes Lernen einge-
Wie bereits beschrieben, liegt die Kombination von Echt- schlossen: Regelinduktion, Support Vector Machine und k-
zeitüberwachung und Langzeitanalyse im Fokus des Inter- nächste Nachbarn. In vielen Fällen müssen die genannten
esses. Ziel ist es, ein Modell bzw. einen Zustandsraum zu Algorithmen ebenfalls kombiniert werden, um einen ange-
22
8. EXISTIERENDE LÖSUNGEN
Zur Analyse von Datenströmen werden Datenstrom-Ma-
nagement-Systeme (DSMS), z.B. STREAM [1] oder Auro-
ra [6], eingesetzt. Aurora enthält ein Pfeil-Box-Architektur-
Modell, welches einem Plug-in-System ähnlich ist. Ein Über-
blick über DSMS wird u.a. in [14] gegeben. CEP-Systeme
wie CAYUGA [9] oder ESPER [11] werden für das Anwen-
Abb. 5: Prozesskette den von Regeln auf Datenströme mittels Anfragesprachen
verwendet. Ein Überblick über CEP-Systeme wird in [12]
gegeben. Die genannten DSMS und CEP-Systeme sind nicht
für Überwachung mittels Data-Mining-Technologien konzi-
piert.
NanoMon [29] ist eine sehr spezielle Überwachungssoftwa-
re für Sensornetzwerke. MobiMine [19] ist ein mobiles Data-
Mining-System für den Aktienhandel. Beide Überwachssys-
teme unterstützen die genannten Überwachungsanforderun-
gen nicht. Weiterhin enthalten NanoMon und MobiMine kei-
ne Anfragesprache.
VEDAS [18] ist ein Datenstrom-Mining-System, welches
einigen der hier erarbeiteten Überwachungsforderungen ent-
spricht. Die Erkennung von ungewöhnlichem Fahrerverhal-
ten ist eines der Hauptaugenmerke von VEDAS. Wie auch
Abb. 6: Überwachungsarchitektur
hier kommen bei VEDAS Data-Mining-Technologien zum
Einsatz. Der Unterschied liegt in der Verwendung von un-
messenen Klassifikator bereitzustellen ([8], [27]). Der dritte überwachtem Lernen für Datenstrom-Mining. Weiterhin gibt
Schritt dient zur Evaluierung der neu ermittelten Regeln es keine strikte Trennung zwischen Echtzeitüberwachung und
und zum Testen mit vorhandenen Regeln, um evtl. Seiten- Langzeitanalyse sowie zwischen automatischen und semi-
effekte auszuschließen. Der letzte Schritt der unteren Teil- automatischen Funktionen. Dieses Argument kann durch die
kette betrifft die Übertragung des so ermittelten Wissens interaktive Verbindung vom externen Informationssystem
zum eingebetteten System. Dies schließt die Anpassung und zum eingebetteten System untermauert werden. Weiterhin
die Rekonfiguration des bestehenden Überwachungssystems wird bei VEDAS die Evaluierung vernachlässigt. Zusätzlich
auf Basis des neuen Wissens mit ein. Die genannten Schritte wird die Überwachungsanforderung Lokalität nicht berück-
sind semi-manuell und werden durch Fachpersonal betreut. sichtigt. In VEDAS ist das eingebettete System so konfigu-
Die komplette Prozesskette wird zyklisch durchlaufen. So riert, dass alle Attribute für die Überwachung Verwendung
kann mit der Zeit das Wissen über das zu überwachende finden. Dies kann unter Umständen zu sehr hohem Rechen-
Produkt gesteigert werden. aufwand führen.
Die vorgeschlagene Überwachungsarchitektur ist in Abbil-
dung 6 grafisch verdeutlicht. Sie basiert auf der Prozesskette,
die bereits beschrieben wurde. Sensoren erzeugen kontinuier- 9. ZUSAMMENFASSUNG
lich Datenströme, die über das interne Netzwerk übertragen Es besteht ein Bedarf an neuen Lösungen für die Überwa-
werden. Es ist notwendig, diese Ereignisse bzw. Zustands- chung von Systemen, die heutige und zukünftige Anforde-
vektoren kontinuierlich unter Berücksichtigung von Echt- rungen in Betracht ziehen. Der vorliegende Beitrag skizziert
zeitbedingungen zu verarbeiten. Das CEP-System muss ent- ein interdisziplinäres Forschungsvorhaben im Rahmen einer
sprechend der festgelegten Regeln Aktionen auslösen. Wei- Doktorarbeit. Einer der Forschungsbeiträge ist die Kombi-
terhin wird der Datenstrom aggregiert und temporär gespei- nation von Echtzeitüberwachung und Langzeitanalyse mit-
chert, bevor er zum externen Informationssystem übermit- tels eingebetteter Systeme, ECA-Regeln, Data-Mining-Tech-
telt wird. Das externe Informationssystem wird für die Lang- nologien und CEP. Drei Annahmen bilden die Basis für
zeitanalyse und zur Ermittlung neuer bzw. zur Verfeinerung den beschriebenen Überwachungsansatz. Weiterhin wurden
bestehender Regeln eingesetzt. Anschließend ist die Evalu- hier fünf Überwachungsanforderungen erarbeitet. Die Ana-
ierung der Regeln und die Übertragung zum eingebetteten lyse bestehender Lösungen zeigt, dass die dargestellten Über-
System notwendig. wachungsanforderungen nur unzureichend in Betracht gezo-
Für das beschriebene Forschungsvorhaben können folgen- gen werden. Aufbauend darauf wurde hier ein dynamischer
de zwei Herausforderungen identifiziert werden. und flexibler Überwachungsansatz vorgestellt. Der hier vor-
gestellte Überwachungsansatz basiert auf einem mathema-
1. Übersetzung der erlernten Klassifikatoren in verfügba- tischen Modell, welches als Zustandsraum bezeichnet wird.
re Anfragesprachen bzw. Funktionen. Dieser Zustandsraum repräsentiert das Wissen über das Pro-
dukt, welches im laufenden Betrieb überwacht wird. Weiter-
2. Erstellung einer dynamischen und flexiblen CEP-An- hin wurde eine Prozesskette erläutert. Diese Prozesskette
wendung, die stetig an neue Anforderungen anpassbar wird zyklisch durchlaufen und somit das Wissen über das
ist. Weiterhin muss unter Berücksichtigung der einge- Produkt mit der Zeit gesteigert. Der Zustandsraum wird
schränkten Systemressourcen und Echtzeitanforderun- mit der Hilfe von Data-Mining-Technologien in ECA-Regeln
gen ein kontinuierlicher Strom von Zustandsvektoren übersetzt und an eine CEP-Anwendung, die sich auf einem
zuverlässig klassifiziert werden können. eingebetteten System befindet, übertragen. Durch die CEP-
23
Anwendung werden die ECA-Regeln verwendet, um die kon- [17] Imboden, D. M. ; Koch, S. : Systemanalyse. Springer,
tinuierlich eintreffenden Zustandsvektoren als bekannt oder 2003
unbekannt zu klassifizieren. [18] Kargupta, H. ; Bhargava, R. ; Liu, K. ; Powers,
M. ; Blair, P. ; Bushra, S. ; Dull, J. ; Sarkar, K. ;
Klein, M. ; Vasa, M. ; Handy, D. : VEDAS: A
10. LITERATUR Mobile and Distributed Data Stream Mining System
[1] Babcock, B. ; Babu, S. ; Datar, M. ; Motwani, R. ; for Real-Time Vehicle Monitoring. In: Proceedings of
Widom, J. : Models and Issues in Data Stream the Fourth SIAM International Conference on Data
Systems. In: PODS ’02: Proceedings of the twenty-first Mining, 2004
ACM SIGMOD-SIGACT-SIGART Symposium on [19] Kargupta, H. ; Park, B.-H. ; Pittie, S. ; Liu, L. ;
Principles of Database Systems, ACM, 2002, S. 1–16 Kushraj, D. ; Sarkar, K. : MobiMine: Monitoring
[2] Bellmann, R. : Adaptive Control Processes. Princeton the Stock Market from a PDA. In: SIGKDD Explor.
University Press, 1961 Newsl. 3 (2002), S. 37–46
[3] Bifet, A. ; Kirkby, R. : Data Stream Mining - A [20] Marwedel, P. : Eingebettete Systeme.
Practical Approach / Centre for Open Software Springer-Verlag, 2007
Innovation (COSI) - Waikato University. [21] Noack, E. ; Belau, W. ; Wohlgemuth, R. ;
Version: 2009. http://moa.cs.waikato.ac.nz/ Müller, R. ; Palumberi, S. ; Parodi, P. ;
wp-content/uploads/2010/05/StreamMining.pdf. – Burzagli, F. : Efficiency of the Columbus Failure
Forschungsbericht Management System. In: AIAA 40th International
[4] Borgelt, C. ; Klawonn, F. ; Kruse, R. ; Nauck, D. Conference on Environmental Systems, 2010
: Neuro-Fuzzy-Systeme: Von den Grundlagen [22] Noack, E. ; Noack, T. ; Patel, V. ; Schmitt, I. ;
künstlicher Neuronaler Netze zur Kopplung mit Richters, M. ; Stamminger, J. ; Sievi, S. : Failure
Fuzzy-Systemen. Vieweg, 2003 Management for Cost-Effective and Efficient
[5] Boslaugh, S. ; Watters, P. A.: Statistics in a Spacecraft Operation. In: Proceedings of the 2011
Nutshell. O’Reilly, 2008 NASA/ESA Conference on Adaptive Hardware and
[6] Carney, D. ; Çetintemel, U. ; Cherniack, M. ; Systems, IEEE Computer Society, 2011 (AHS ’11). –
Convey, C. ; Lee, S. ; Seidman, G. ; Stonebraker, To appear
M. ; Tatbul, N. ; Zdonik, S. : Monitoring Streams: A [23] Peckol, J. K.: Embedded Systems: A Contemporary
New Class of Data Management Applications. In: Design Tool. John Wiley & Sons, 2007
VLDB ’02: Proceedings of the 28th International [24] Richard, H. ; Fulland, M. ; Sander, M. ;
Conference on Very Large Data Bases, VLDB Kullmer, G. : Fracture in a rubber-sprung railway
Endowment, 2002, S. 215–226 wheel. In: Engineering Failure Analysis 12 (2005), Nr.
[7] Chakravarthy, S. ; Jiang, Q. : Stream Data 6, S. 986 – 999
Processing: A Quality of Service Perspective. Springer, [25] Schmitt, I. : QQL: A DB&IR Query Language. In:
2009 The VLDB Journal 17 (2008), S. 39–56
[8] Chandola, V. ; Banerjee, A. ; Kumar, V. : [26] Tsai, J. J. P. ; Yang, S. J. H.: Monitoring and
Anomaly detection: A survey. In: ACM Comput. Surv. Debugging of Distributed Real-Time Systems. IEEE
41 (2009), S. 15:1–15:58 Computer Society Press, 1995
[9] Demers, A. J. ; Gehrke, J. ; Panda, B. ; [27] Witten, I. H. ; Frank, E. ; Hall, M. A.: Data
Riedewald, M. ; Sharma, V. ; White, W. M.: Mining: Practical Machine Learning Tools and
Cayuga: A General Purpose Event Monitoring Techniques. Elsevier, 2011
System. In: CIDR, 2007, S. 412–422 [28] Wolf, F. : Behavioral Intervals in Embedded Software:
[10] Dittrich, K. R. ; Gatziu, S. ; Geppert, A. : The Timing and Power Analysis of Embedded Real-Time
Active Database Management System Manifesto: A Software Processes. Kluwer Academic Publishers, 2002
Rulebase of ADBMS Features. In: SIGMOD Rec. 25 [29] Yu, M. ; Kim, H. ; Mah, P. : NanoMon: An
(1996), Nr. 3, S. 40–49 Adaptable Sensor Network Monitoring Software. In:
[11] EsperTech: Esper. http://www.espertech.com/ IEEE International Symposium on Consumer
products/esper.php. Version: 2011. – Online: Electronics (ISCE), 2007
30.03.2011
[12] Etzion, O. ; Niblett, P. : Event Processing in
Action. Manning Publications Co., 2010
[13] Fischer, G. ; Grubisic, V. : Praxisrelevante
Bewertung des Radbruchs vom ICE 884 in Eschede.
In: Materialwissenschaft und Werkstofftechnik 38
(2007), Nr. 10, S. 789–801
[14] Golab, L. ; Özsu, M. T.: Data Stream Management.
Morgan & Claypool Publishers, 2010
[15] Gordon, G. : Systemsimulation. Oldenbourg, 1972
[16] Guo, Y. : Algorithmen zur On-Board-Diagnose von
Fahrwerksschäden an Schienenfahrzeugen, TU Berlin,
Diss., 2005. http://opus.kobv.de/tuberlin/
volltexte/2005/1120/
24
Analyse und Vergleich von Zugriffstechniken für
funktionale Aspekte in RDBMS
Matthias Liebisch
Friedrich-Schiller-Universität Jena
Lehrstuhl für Datenbanken und Informationssysteme
Ernst-Abbe-Platz 2
07743 Jena
m.liebisch@uni-jena.de
KURZFASSUNG wicklung derartiger Applikationen ist deswegen auch im-
Neben klassischen fachlichen Anforderungen existieren in mer mit dem Entwurf eines für den Einsatzzweck geeig-
Anwendungssystemen oft auch querschnittliche Belange, de- neten Datenmodells verbunden. Dieses sollte unter Beach-
ren Funktionalität sich nicht einfach kapseln bzw. modu- tung verschiedener Kriterien, wie beispielsweise Benutzbar-
larisieren lässt. Vertreter dieser sogenannten funktionalen keit und Wiederverwendbarkeit, die modularisierte Speiche-
Aspekte sind beispielsweise die mehrsprachige oder versio- rung der fachlichen Datenobjekte in relationalen Strukturen
nierte Darstellung und Verwaltung von Anwendungsdaten. optimal unterstützen. Neben dieser Abbildung existieren je-
Nachdem sich in der Software-Entwicklung seit einigen Jah- doch häufig zusätzlich anwendungsweite Anforderungen wie
ren die Aspektorientierte Programmierung als Lösung eta- beispielsweise die Unterstützung von Mehrsprachigkeit oder
bliert hat, bietet das neuartige Paradigma der Aspektorien- Versionierung, welche als sogenannte funktionale Aspek-
tierten Datenhaltung ein entsprechendes Konzept zur Ab- te[11] Einfluss auf das gesamte Datenmodell haben.
bildung querschnittlicher Belange in einem relationalen Da-
tenmodell. Dabei stehen vor allem die Unabhängigkeit vom Dieses Problem der cross-cutting concerns ist bereits aus
Prozess der fachlichen Modellierung und ein hoher Wieder- dem Umfeld der Objektorientierten Programmierung seit ei-
verwendungsgrad im Vordergrund. Basierend auf dem zu nigen Jahren bekannt und hat zur Entwicklung der Aspekt-
diesem Zweck entwickelten Referenzmodell untersucht der orientierten Programmierung[3] geführt. Im übertragenen
vorliegende Beitrag unterschiedliche Techniken für den Zu- Sinne stellt die Aspektorientierte Datenhaltung[11] ein Mo-
griff auf jene funktionalen Aspekte. Diese werden anschlie- dellierungsparadigma dar, um funktionale Aspekte in ei-
ßend anhand wesentlicher Bewertungskriterien einer Evalua- nem Datenmodell gekapselt und unabhängig von den fach-
tion unterzogen und miteinander verglichen. lichen Datenobjekten zu integrieren. Triviale Ansätze, wie
beispielsweise die Erweiterung relevanter Tabellen um eine
Kategorien und Themenbeschreibung zusätzliche Spalte zur Festlegung der Locale im Fall mehr-
sprachiger Datenhaltung, sind meist nur auf konkrete An-
H.4 [Information Systems Applications]: Miscellaneous;
wendungsfälle zugeschnitten und versagen zudem bei der
H.2.3 [Database Management]: Languages—Query lan-
Unterstützung beliebig vieler funktionaler Aspekte unter den
guages
Anforderungen des Paradigmas der Aspektorientierten Da-
tenhaltung [19]. Ein generischer Ansatz zur Lösung der an-
Allgemeine Bestimmungen gedeuteten Herausforderungen ist das in [12] beschriebene
Design, Languages, Performance Referenzmodell. Darauf basierend zeigt der vorliegende Bei-
trag verschiedene Alternativen für den Zugriff und die Nut-
1. EINLEITUNG zung funktionaler Aspekte aus Sicht der Anwendung auf.
Seit der Beschreibung des relationalen Modells[4] Anfang der
1970er Jahre ist die Bedeutung auf diesem Modell basie- Nachfolgend werden in Abschnitt 2 das erwähnte Referenz-
render Datenbankmanagementsysteme (RDBMS) als Per- modell sowie ein kleines Anwendungsbeispiel kurz vorge-
sistierungsebene stetig gewachsen. Heutzutage bilden rela- stellt. Die darauf aufbauenden Zugriffstechniken stehen im
tionale Datenbanksysteme die Grundlage für die vielfältig- Fokus von Abschnitt 3, bevor sie in Abschnitt 4 einer Be-
sten Anwendungssysteme und sind damit aus den meisten wertung unterzogen werden. Schließlich fasst Abschnitt 5 die
alltäglichen Prozessen nicht mehr wegzudenken. Die Ent- Ergebnisse der Arbeit nochmal zusammen.
2. REFERENZMODELL
Für die vom fachlichen Datenmodell unabhängige und ge-
kapselte Persistierung aspektspezifischer Daten wurde in [12]
ein Referenzmodell vorgestellt und beschrieben, welches mit
Copyright is held by the author/owner(s).
geringfügigen Anpassungen bezüglich der Fremdschlüsselde-
23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken) 31.5.-03.06.2011, Obergurgl, Austria. finitionen in den Tabellen zur Aspektverknüpfung auch in
diesem Beitrag zum Einsatz kommt.
25
Aspect.Assign Aspect.KeyValue Aspect.Datatype 3. ZUGRIFFSTECHNIKEN
PK AspAssID PK AspKeyID PK AspTypeID Dieser Abschnitt beschreibt verschiedene Möglichkeiten für
FK KeyValue FK Aspect TypeName den Zugriff auf funktionale Aspekte, welche mit Hilfe des
FK AspectValue KeyValue Length in Abbildung 1 präsentierten Referenzmodells in ein fachli-
Comment Scale
ches Datenmodell integriert werden. Aufgrund der Tatsache,
Aspect.Value Aspect.Definition Aspect.Table
dass das relationale Modell als Grundlage dient, ist der di-
rekte Zugriff mittels SQL auf die entsprechenden Strukturen
PK AspValID PK AspDefID PK AspTabID
RowID Name Schema
die naheliegendste Möglichkeit. Allerdings stellt die zentrale
FK Column Key TableName Tabelle Aspect.Value eine neue Herausforderung für die
Value FK Datatype Anfragegenerierung dar, weil darin enthaltene Daten durch
Aspect.Column das verwendete EAV-Prinzip[15] einer sogenannten unpivo-
Aspect.Additional tisierten ( gekippten“) Speicherungsform unterliegen. Dies
PK AspColID
”
PK AspAddID FK Table hat zur Konsequenz, dass zu jedem Attribut (Column) ei-
FK Aspect ColumnName nes traditionellen Tupels (identifizierbar über RowID) der
FK Table FK Datatype
jeweilige Wert (Value) in einer eigenen Zeile gespeichert
Aspektverknüpfung Aspektstammdaten Aspektmetadaten wird. Da jedoch die klassische relationale Verarbeitung von
PK/FK: Primär−/Fremdschlüssel Datensätzen mit zugehörigen Attributen als Tabellenspalten
ausgeht, ist eine Pivotisierung ( rows to columns“) notwen-
”
Abbildung 1: Referenzmodell dig, sobald in der Anfrage die Tabelle Aspect.Value invol-
viert wird. Die anschließenden Abschnitte beschreiben drei
Konstrukte in SQL sowie einen applikativen Ansatz, um die
Zentraler Bestandteil dieses in Abbildung 1 skizzierten Re- genannte Transformation zu unterstützen.
ferenzmodells sind die beiden Tabellen Aspect.Value und
Aspect.Assign, welche die Speicherung aspektspezifischer 3.1 SQL mit JOIN
Attributwerte sowie deren Zuordnung zu einer konkreten Bei einer Beschränkung auf normierte Sprachmittel ist die
Aspektausprägung (z.B. Locale ’en’ im Aspekt Mehrspra- erforderliche Transformation nur mittels JOIN-Operatoren
chigkeit) für eine Fachtabellenzelle realisieren. Daneben exis- realisierbar, da weder im SQL:92-Standard[6] als Grundlage
tieren weitere Tabellen zur Verwaltung von Metadaten, wie für das Paradigma der Aspektorientierten Datenhaltung[11]
beispielsweise Aspect.KeyValue für die Spezifikation von noch in der aktuellen SQL:2008-Norm[10] dedizierte Opera-
Ausprägungswerten zu allen im System definierten Aspek- toren zur Pivotisierung einer Tabelle existieren. Das prin-
ten oder Aspect.Column zur Hinterlegung aspektrelevan- zipielle Vorgehen ist exemplarisch für die in Abbildung 2
ter Attribute der Fachtabellen. formulierte Anfrage in Abbildung 3 dargestellt. Dabei wur-
de auf die Formatierung der Ergebnisattribute entsprechend
Die Anforderungen aus dem Paradigma der Aspektorientier- den zugeordneten Datentypen in Tabelle Aspect.Datatype
ten Datenhaltung werden insbesondere durch das Entity- verzichtet und zwecks Übersichtlichkeit die Kenntnis gewis-
Attribute-Value-Konzept[15] (EAV) gewährleistet, welches ser Metadaten wie Idents von Aspekten und Tabellenspalten
für Aspect.Value und Aspect.KeyValue zur Anwendung als bekannt vorausgesetzt.
kommt. Die damit verbundenen Konsequenzen[7] bezüglich
der Komplexität von direkten SQL-Anfragen im Referenz-
modell erfordern die Analyse alternativer Zugriffsarten. SELECT T1.Value AS Name, T2.Value AS Preis,
T5.KeyValue AS Locale
Demo.Modul Demo.Struktur FROM Aspect.Value T1
PK TeilNr PK,FK Oberteil INNER JOIN Aspect.Value T2
Mehrsprachigkeit
Name PK,FK Unterteil ON T1.RowID = T2.RowID
Preis Menge INNER JOIN Aspect.Assign T3
Flags
ON T1.AspValID = T3.AspectValue
PK/FK: Primär−/Fremdschlüssel INNER JOIN Aspect.Assign T4
ON T2.AspValID = T4.AspectValue
IAnfrage: Ermittle für das Modul mit TeilNr=4711 alle
INNER JOIN Aspect.KeyValue T5
mehrsprachigen Daten ( Name und Preis) sowie den jewei-
ON T3.KeyValue = T5.AspKeyID
ligen Aspektschlüsselwert als Locale.
WHERE T1.Column = 1 -- /* ’Name’ */
AND T2.Column = 2 -- /* ’Preis’ */
Abbildung 2: Beispiel für Datenmodell mit Anfrage
AND T3.KeyValue = T4.KeyValue
AND T5.Aspect = 1 -- /* ’Mehrsprachigkeit’ */
Zur Veranschaulichung der in Abschnitt 3 folgenden Techni-
AND T1.RowID = 4711
ken soll das in Abbildung 2 dargestellte Beispiel eines verein-
fachten Datenmodells zur Verwaltung von Stücklisten die-
nen, in dem der Aspekt Mehrsprachigkeit“ für die Attribute Abbildung 3: Anfrage mit JOIN
”
Demo.Modul.Name sowie Demo.Modul.Preis aktiviert
wurde. Darauf aufbauend soll jeweils die Beantwortung der Bereits für das simple in Abbildung 3 präsentierte Beispiel
zugehörigen Beispiel-Anfrage erläutert werden, welche das ist die Komplexität der Anfragegenerierung inklusive Pivo-
Prinzip für den Zugriff auf aspektspezifische Attributwerte tisierung der Tabelle Aspect.Value erkennbar. Insbeson-
in einem konkreten fachlichen Anwendungskontext verdeut- dere skalieren die notwendigen JOIN-Operatoren linear mit
lichen soll. den Attributen im Ergebnisschema. Dabei werden jeweils
26
die Tabellen Aspect.Value und Aspect.Assign miteinan- sicherzustellen, müssen die beiden genannten Tabellen zu-
der verbunden, welche für die Speicherung aller aspektspe- sammen mit der Tabelle Aspect.KeyValue verbunden wer-
zifischen Ausprägungen von Attributwerten in Fachtabellen den. Anschließend kann über die projezierte Attributmenge
zuständig sind und dadurch mit Abstand die umfangreichs- sinnvoll pivotisiert werden.
ten Mengengerüste aufweisen. Erwartungsgemäß haben der-
artige Anweisungen eine oft inakzeptable Verarbeitungszeit Zusätzlich ist bei der Nutzung des PIVOT-Operators zu be-
wie entsprechende Analysen gezeigt haben[13]. achten, dass für die IN-Klausel nur eine fest definierte Spal-
tenmenge angegeben werden kann. Ein Ausdruck der Form
3.2 SQL mit PIVOT SELECT Column FROM Aspect.Value ist beispielsweise nicht
Verlässt man die SQL-Norm auf der Suche nach adäqua- zulässig. Dies gilt sowohl für Microsoft SQL Server 20051 als
ter Unterstützung für die Pivotisierung von EAV-Tabellen, auch für Oracle 11g2 . Wird eine derartige Dynamik dennoch
dann zeigt sich, dass DBMS-Hersteller bereits produktspezi- benötigt, lässt sich diese nur über eine Stored Procedure,
fische SQL-Erweiterungen mit den Operatoren PIVOT und vorgeschalteten Anwendungscode oder im Fall von Oracle
UNPIVOT[20] anbieten. Unter anderem finden sich derar- unter Verwendung von XML realisieren.
tige Implementierungen in Datenbanksystemen wie Micro-
soft SQL Server 2005[18] oder Oracle 11g[14]. Ein typisches 3.3 SQL mit Spracherweiterung
Anwendungsgebiet für diese Transformationen sind OLAP- Aufgrund der fehlenden Normierung des PIVOT-Operators
Anfragen im Bereich Data Warehouse[17], deren Blickwinkel einerseits und dessen Nutzungs-Einschränkungen im Kon-
geändert werden soll (beispielsweise die Gruppierung nach text der Aspektorientierten Datenhaltung andererseits, ver-
Regionen statt Produkten in einer Umsatzübersicht). Durch folgt dieser Abschnitt die Idee einer SQL-Erweiterung für
Nutzung von PIVOT und UNPIVOT kann eine gezielte Op- einen adäquaten Zugriff auf funktionale Aspekte im Refe-
timierung auf Basis der klassischen Operatoren wie Verbund renzmodell. Die neuen Sprachelemente beeinflussen sowohl
oder Projektion erfolgen[5]. den DML-Teil als auch den DDL-Bereich, um beispielswei-
se für eine Tabellenspalte relevante Aspekte definieren zu
können. Hier soll jedoch aus Platzgründen nur das SELECT-
SELECT PivotedData.[1] AS Name, Statement im Fokus stehen.
PivotedData.[2] AS Preis,
PivotedData.KeyValue AS Locale
FROM