=Paper= {{Paper |id=None |storemode=property |title=None |pdfUrl=https://ceur-ws.org/Vol-733/proceedings.pdf |volume=Vol-733 }} ==None== https://ceur-ws.org/Vol-733/proceedings.pdf
                       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                                                              ::=
  (                                                                   
[ ] SELECT T1.RowID, T1.Column, T1.Value, | T3.KeyValue | FROM Aspect.Value T1 | INNER JOIN Aspect.Assign T2 ON T1.AspValID = T2.AspectValue ::= INNER JOIN Aspect.KeyValue T3 ASPECTVIEW BASED ON
ON T2.KeyValue = T3.AspKeyID GROUP BY [{, } ... ] WHERE T3.Aspect = 1 -- /*’Mehrsprachigkeit’*/ AND T1.RowID = 4711 ::= ) AS JoinData ASPECTKEY() PIVOT AS ( MAX(JoinData.Value) Abbildung 5: SQL-Erweiterung ASPECTVIEW FOR JoinData.Column IN ([1], [2]) -- /* 1 und 2 = relevante Column-IDs */ Aufbauend auf dem SQL:92-Standard[6] wird das Nichtter- ) AS PivotedData minalsymbol
3 um eine weitere Alter- native ergänzt, deren Definition in Abbil- Abbildung 4: Anfrage mit PIVOT dung 5 dargestellt ist. Das neue Schlüsselwort ASPECTVIEW erzeugt dabei eine Sicht auf alle aspektspezifischen Daten Aber auch die Verarbeitung von EAV-Tabellen wie hier im der über BASED ON angegebenen (fachlichen) Basistabelle. Kontext der Aspektorientierten Datenhaltung ist mit Hilfe Da es möglich ist, einer Tabellenspalte verschiedene Aspekte des PIVOT-Operators möglich. Abbildung 4 demonstriert zuzuordnen, erfolgt die Aufbereitung der Daten in gruppier- dessen Verwendung unter Microsoft SQL Server 2005 für ter Form bezüglich des einattributigen Primärschlüssels[11] die Beispielanfrage in Abbildung 2. Auf den ersten Blick und der über spezifizierten Aspekte. Diese verwirrt dabei der Ausdruck MAX(JoinData.Value), welcher stehen anschließend im Rahmen der Anfrageformulierung als die notwendige Aggregatbildung bei der Pivotisierung über- reguläre Attribute der Sicht zur Verfügung, für eine Tabelle nimmt. Diese Funktion lässt das Ergebnis jedoch inhaltlich mit n Attributen und insgesamt k zugeordneten Aspekte er- korrekt, solange jede Gruppe bezüglich der gruppierten At- gibt sich also das in Abbildung 6 dargestellte Relationssche- tribute (T1.RowID, T3.KeyValue) und den zu Spalten um- ma. Voraussetzung hierfür ist eine im Referenzmodell ver- gewandelten Werten aus T1.Column nur einen Datensatz 1 http://msdn.microsoft.com/en-us/library/ms177634.aspx enthält. Um dies unter Beachtung der getrennten Speiche- 2 http://download.oracle.com/docs/cd/B28359_01/server.111/b28286/ rung der aspektspezifischen Werte (Aspect.Value) und den statements_10002.htm#CHDFAFIE 3 tatsächlichen Fachtabellen-Zuordnungen (Aspect.Assign) http://savage.net.au/SQL/sql-92.bnf 27 ankerte UNIQUE-Bedingung auf Aspect.Definition.Key, der Aspekte inklusive ihrer Metadaten als auch zur Abfrage dessen Werte über den Ausdruck ASPECTKEY() referenziert werden. achtung sogenannter Aspektfilter und Aspektkontexte. Basistabelle Aspekte Anwendungsprogramm z }| {z }| { JDBC−Schnittstelle (Att1 , . . . , Attn , Asp1 , . . . , Aspk ) DB (inkl. Referenz− Abbildung 6: Relationsschema von ASPECTVIEW Funktionsbaustein modell) ("Aspekt−API") Angewendet auf das in Abbildung 2 skizzierte Beispiel er- gibt sich eine gegenüber den bisherigen Zugriffstechniken Abbildung 8: Anwendungs-Integration der API sehr kompakte Anfrage, wie Abbildung 7 zeigt. Neben dem Aufwand zur Pivotisierung für die Aspektsicht T1 ist un- Um einen möglichst plattformunabhängigen und universel- abhängig von der Anzahl der Attribute oder Aspekte nur len Funktionsbaustein bereitstellen zu können, ist dieser in- noch eine JOIN-Operation erforderlich, um für die Idents klusive seiner API in Java spezifiziert. Da in den meisten in Aspi die eigentlichen Aspektschlüsselwerte anzeigen zu Fällen bei Verwendung einer Java-Bibliothek das umgeben- können. de Anwendungsprogramm ebenfalls auf Java basiert und für Datenbankzugriffe die JDBC-Schnittstelle genutzt wird, SELECT T1.Name, T1.Preis, T2.KeyValue AS Locale zeigt Abbildung 8 ein typisches Integrations-Szenario. Dabei FROM Aspect.KeyValue T2 INNER JOIN können in einer ersten Ausbaustufe über die API tatsächlich ( nur aspektspezifische Daten abgefragt und geändert werden, ASPECTVIEW ModulAspects die Verarbeitung der fachlichen Daten erfolgt unverändert BASED ON Demo.Modul über die bereits existierende Datenbank-Schnittstelle. Auf- GROUP BY ASPECTKEY(’Locale’) AS AspLoc gabe der Anwendung ist damit also die Zusammenführung ) T1 der Ergebnisse beider Datenquellen, abhängig natürlich von ON T2.AspKeyID = T1.AspLoc den inhaltlichen Anforderungen. WHERE T1.TeilNr = 4711 AND T2.Aspect = 1 -- /*’Mehrsprachigkeit’*/ 1 // Deklarationen AspectManager am = /* Verweis auf Instanz holen */ Abbildung 7: Anfrage mit ASPECTVIEW 3 AspectCatalogManager acm = am.getAspectCatalogManager(); 5 int aspLang = acm.lookupAspectID("Language"); Sollte sich eine derartige Spracherweiterung wie angedeu- int tID = acm.lookupTableID("Demo","Modul"); tet für alle Bereiche (DDL und DML) als geeignetes Aus- 7 int cNameID = acm.lookupColumnID(tID, "Name"); drucksmittel im Umgang mit funktionalen Aspekten bewei- int cPriceID = acm.lookupColumnID(tID, "Preis"); sen, bleibt die praktische Nutzung stark eingeschränkt, so- 9 lange eine Umsetzung in SQL-Norm oder DBMS-Produkten // Anfragespezifikation fehlt. In solch einem Szenario kann der Einsatz sogenann- 11 QueryStatement st = am.createQueryStatement(tID); ter Proxys[1] oder Query Transformation Layer[2] zwischen st.setRowIDs(new long[] {4711}); Anwendung und Datenbank eine Lösung darstellen. Im vor- 13 st.setColumnSet(am.createColumnSet( liegenden Fall müssten alle neu definierten SQL-Ausdrücke, new int[] {cNameID, cPriceID})); beispielsweise ASPECTVIEW, durch einen Parser auf effiziente 15 Art und Weise in genormte oder produktspezifische SQL- // Ergebnisverarbeitung Anweisungen transformiert werden. Damit wäre zumindest 17 ResultRows result = st.execute(); eine benutzerfreundliche Schnittstelle im Umgang mit funk- AspectSet aSet = st.getAspectSet(); tionalen Aspekten unter Nutzung der trivialen Umformung 19 ColumnSet cSet = st.getColumnSet(); (Anfrage mit JOIN, siehe Abschnitt 3.1) geschaffen. Die int aspLangIdx = aSet.getIndex(aspLang); nachfolgend beschriebene Zugriffstechnik ist ebenfalls ein 21 int cNameIdx = cSet.getIndex(cNameID); Vertreter dieser Kategorie, allerdings erfolgt die Anfrage- int cPriceIdx = cSet.getIndex(cPriceID); formulierung nicht auf Basis von SQL. 23 while (result.next()) { 3.4 Funktionsbaustein mit API 25 long rowID = result.getRowID(); Gegenüber den bisher vorgestellten Möglichkeiten, den Zu- AspectContextElement e = griff auf funktionale Aspekte allein mit SQL-Mitteln auf der 27 result.getContext().getElement(); Persistierungsebene zu realisieren, wird mit dem vierten An- String name = result.getValueString(cNameIdx); satz eine applikationsseitige Verarbeitung verfolgt. Analog 29 String price = result.getValueString(cPriceIdx); zum Konzept mit JDBC[9] eine einheitliche Schnittstelle für int localeID = e.getIndexKeyValue(aspLangIdx); relationale Datenbanken zu etablieren, ermöglicht der hier 31 } vorgestellte Funktionsbaustein den Zugriff auf funktionale Aspekte, welche im Referenzmodell persistiert sind. Die zu- gehörige API[16] umfasst Methoden sowohl zur Verwaltung Abbildung 9: Anfrage mit Funktionsbaustein 28 Eine Abfrage aspektspezifischer Daten wie für das Referenz- im Rahmen der Verarbeitung bekannt sein müssen oder ver- Beispiel wird prinzipiell durch das in Abbildung 9 dargestell- borgen bleiben können, zeigt sich in der Transparenz ei- te Code-Fragment realisiert. Der Einstieg erfolgt mit einer ner Technik. Weiterhin wird geprüft, ob im jeweiligen An- implementierungsspezifischen Instanz der zentralen Klasse satz auf die bereits vorhandene Mächtigkeit eines zu Grun- AspectManager (Zeile 2), welche im nächsten Schritt zur Er- de gelegten RDBMS in angemessener Weise zurückgegrif- zeugung einer AspectCatalogManager-Instanz benötigt wird fen wird (Funktionsadäquatheit) oder ob Funktionalität, und zudem auch für die Verwaltung einer Datenbank-Session wie beispielsweise das Parsen von Sprachausdrücken und zuständig ist. Schließlich werden zum Aspekt Mehrsprachig- das Caching von Daten, reimplementiert werden muss. Hier- keit sowie für die Attribute Name und Preis der Tabelle bei spielen auch prinzipielle Möglichkeiten zur Erweiter- Modul die Idents ermittelt (Zeilen 5-8). Hierfür können ent- barkeit des Funktionsumfangs eine Rolle, erwartungsgemäß sprechende Methoden an der Aspektkatalogmanager-Klasse werden diese durch Standardisierung beschränkt. Schließlich genutzt werden, damit sind alle für die Anfrage notwendigen soll noch mit der Benutzerfreundlichkeit beurteilt wer- Metadaten bekannt. den, wie sich letztlich die gesamte Auswertung funktionaler Aspekte für den Anwendungsentwickler darstellt. Für die Anfragespezifikation wird über den AspectManager eine Instanz der Klasse QueryStatement angelegt (Zeile 11). Da in der relevanten Fachtabelle Demo.Modul das Attri- 4.2 Bewertung Eine detaillierte Bewertung jeder einzelnen Zugriffstechnik but TeilNr bereits die Anforderung eines einattributigen bezüglich der zuvor aufgestellten Kriterien kann hier aus Primärschlüssels erfüllt, entspricht die Filterung mit der Me- Platzgründen nicht beschrieben werden. Stattdessen enthält thode setRowIDs in Zeile 12 genau der Einschränkung auf Tabelle 1 einen Überblick mit den Ergebnissen. das Modul mit TeilNr=4711 in einer WHERE-Klausel. Die zu projezierenden Spalten werden analog in Zeile 13 festge- Benutzerfreundlichkeit legt. Weitere zusätzliche aspektspezifische Beschränkungen Funktionsadäquatheit beispielsweise über die AspectFilter-Klasse entfallen, da al- Standardisierung le mehrsprachigen Daten für die Attribute Name und Preis Erweiterbarkeit Praxisrelevanz bereitzustellen sind. Performance Transparenz Kriterium Die Ausführung der Anfrage erzeugt ein ResultRows-Objekt (Zeile 17), welches analog zum entsprechenden Konstrukt in JDBC zeilenweise über den next-Iterator verarbeitet wer- den kann (Zeile 23). Zuvor sind für die korrekte Auswer- Zugriffstechnik tung der Ergebnisstruktur die darin enthaltenen Indexe des JOIN + + – – + – – Mehrsprachigkeits-Aspekts sowie der beiden angefragten At- PIVOT o1 o1 o o + – o tribute zu ermitteln (Zeilen 18-22). Mit Hilfe dieser Indexe ASPECTVIEW – o3 o + o3 + + kann nun auf die entsprechenden Informationen zugegrif- fen werden (Zeilen 25-29). Weiterführende Details zu Da- API o2 + + 4 + – + o tenstrukturen, Klassen und Methoden sowie zu deren Ver- + : ja/hoch o : neutral/mittel – : nein/niedrig wendung finden sich bei Pietsch[16]. 1 unterstützt durch Oracle 11g und MS SQL Server 2005 2 de-facto Standard[8] aufgrund enormer Verbreitung 4. VERGLEICH 3 nur bei Nutzung von Zwischenschichten[1, 2] Nachdem der vorangegangene Abschnitt 3 die unterschied- 4 begründet durch Ergebnisse in [7] lichen Zugriffstechniken präsentiert hat, dient dieser Ab- schnitt der Bewertung und dem Vergleich jener Techniken. Tabelle 1: Bewertung der Zugriffstechniken Zuerst werden die dafür notwendigen Kriterien im Folgenden beschrieben und anschließend für jeden Ansatz evaluiert. Dabei fällt auf, dass zwar der JOIN-Ansatz (Abschnitt 3.1) als einziger Vertreter auf standardisierte Sprachkonstruk- 4.1 Kriterien te zurückgreift und damit eine große Praxisrelevanz bzw. Ausgehend vom Paradigma der Aspektorientierten Daten- Produktunterstützung besitzt, allerdings weder performant haltung spiegelt sich die Forderung nach Universalität[11] noch benutzerspezifisch erweiterbar ist. Zudem erzwingt die bezüglich SQL:92 im Kriterium der Standardisierung wi- Nutzung des Verbund-Operators genaue Kenntnisse über die der, welches hier jedoch auch bezüglich der Existenz ei- Aspekt-Tabellen, wodurch die Transparenz und Benutzer- ner ISO-Norm erweitert werden soll. In direktem Zusam- freundlichkeit verloren geht. menhang dazu stellt sich die Frage der Praxisrelevanz eines Ansatzes, d.h. ob mit diesem der Zugriff auf funk- Dagegen verspricht die PIVOT-Methode (Abschnitt 3.2) tionale Aspekte unter den aktuellen Gegebenheiten über- sowohl den transparenteren Zugang als auch eine performan- haupt praktisch realisierbar ist. Eine große Bedeutung spie- tere Verarbeitung der aspektspezifischen Daten in den EAV- len natürlich auch Ausagen zur Performance, allerdings Tabellen[5]. Dennoch fehlt hier ebenfalls die Möglichkeit zur liegen nur für den ersten Ansatz (SQL mit JOIN) tatsächlich Erweiterbarkeit, zudem ist die Anwendbarkeit aufgrund der konkrete Messwerte[13] vor, sodass für alle anderen Varian- (noch) fehlenden Normierung an Hersteller wie Oracle oder ten nur eine qualitative Abschätzung möglich ist. Microsoft und deren DBMS-Produkte gekoppelt. Inwieweit die Strukturen des Referenzmodells zur Persistie- Ähnliche Charakteristik besitzt auch der ASPECTVIEW- rung funktionaler Aspekte dem Nutzer bzw. der Anwendung Vorschlag (Abschnitt 3.3), er soll jedoch als Erweiterung 29 von SQL die Konsequenzen der Aspektorientierten Daten- [5] C. Cunningham, G. Graefe, and C. A. haltung berücksichtigen. Daher ist der praktische Einsatz Galindo-Legaria. PIVOT and UNPIVOT: momentan nur über die genannten Zwischenschichten rea- Optimization and Execution Strategies in an RDBMS. lisierbar. Andererseits wird dem Anwendungsentwickler ein In (e)Proceedings of the 30th International Conference intuitives und adäquates Konstrukt zur Verfügung gestellt, on Very Large Data Bases (VLDB 2004), pages um transparent auf funktionale Aspekte von Fachtabellen 998–1009, 2004. zugreifen zu können. [6] C. Date and H. Darwen. SQL - Der Standard. SQL/92 mit den Erweiterungen CLI und PSM. Schließlich ergibt sich für den API-Ansatz (Abschnitt 3.4) Addison-Wesley, 1998. eine mindestens ebenso gute oder bessere Bewertung ge- [7] V. Dinu, P. Nadkarni, and C. Brandt. Pivoting genüber den anderen Zugriffstechniken in vielen Kriterien, approaches for bulk extraction of insbesondere ist ein performanter Aspekt-Zugriff möglich. Entity-Attribute-Value data. Computer Methods And Der fehlenden Standardisierung lässt sich z.B. durch Por- Programs in Biomedicine, 82(1):38–43, 2006. tierung auf die gängigsten Programmiersprachen begegnen. [8] T. Egyedi. Why Java Was Not Standardized Twice. Großer Aufwand ist zudem notwendig, um der Mächtigkeit Hawaii International Conference on System Sciences, von SQL auf Seiten der API gerecht zu werden. 5(1):5015–5025, 2001. [9] M. Fisher, J. Ellis, and J. Bruce. JDBC API Tutorial 5. ZUSAMMENFASSUNG and Reference (Java Series). Addison-Wesley, 2003. Der vorliegende Beitrag hat vier verschiedene Techniken für [10] ISO/IEC 9075-2:2008. Information technology – den Zugriff auf funktionale Aspekte aufgezeigt, welche im Database languages – SQL – Part 2: Foundation Kontext der Aspektorientierten Datenhaltung über ein eben- (SQL/Foundation). ISO, Geneva, Switzerland, 2008. falls kurz beschriebenes Referenzmodell auf relationalen Da- [11] M. Liebisch. Aspektorientierte Datenhaltung - ein tenbanken abgebildet werden können. Durch die Fokussie- Modellierungsparadigma. In Proceedings of the 22nd rung auf RDBMS und deren hohen Verbreitungsgrad ist die GI Workshop Grundlagen von Datenbanken (GvDB Grundlage für den praktischen Einsatz gewährleistet. Die 2010), pages 13–17, Bad Helmstedt, Germany, May anschließende Bewertung anhand zuvor aufgestellter Krite- 2010. rien sollte weitere Klarheit über die Potentiale der einzel- [12] M. Liebisch. Supporting functional aspects in nen Ansätze liefern. Dabei hat sich herausgestellt, dass vor relational databases. In Proceedings of the 2nd allem für eine performante und transparente Auswertung International Conference on Software Technology and funktionaler Aspekte die standardisierten Mittel von SQL Engineering (ICSTE 2010), pages 227–231, San Juan, nicht ausreichen. Puerto Rico, USA, Oct. 2010. [13] M. Liebisch and M. Plietz. Performance-Analysen für Unter den möglichen Alternativen erscheinen der Vorschlag Realisierungsansätze im Kontext der zur Erweiterung von SQL mit ASPECTVIEW und die ap- Aspektorientierten Datenhaltung. Institut für plikative Verarbeitung in einem Funktionsbaustein vielver- Informatik, Friedrich-Schiller-Universität Jena, Nov. sprechend. Dabei ist der Aufwand zur Erweiterung der SQL- 2010. Norm ungleich höher und nicht automatisch von Erfolg ge- [14] D. Lorentz. Oracle Database SQL Language Reference krönt bzw. wie bereits vorgeschlagen nur durch Implemen- 11g Release 1. Oracle, Aug. 2010. tierung einer transformierenden Zwischenschicht praktika- [15] P. Nadkarni, L. Marenco, R. Chen, E. Skoufos, bel. Aus diesem Grund werden sich nachfolgende Arbei- G. Shepherd, and P. Miller. Organization of ten vor allem der prototypischen Realisierung, quantitativen Heterogeneous Scientific Data Using the EAV/CR Performance-Vergleichen sowie funktionellen Weiterentwick- Representation. In JAMIA, 6, pages 478–493, 1999. lungen bezüglich aktueller Einschränkungen der vorgestell- [16] B. Pietsch. Entwurf einer Zugriffsschicht für ten API für funktionale Aspekte widmen. funktionale Aspekte in DBMS. Studienarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, 6. LITERATUR Mar. 2011. [1] A. Adam, S. Leuoth, and W. Benn. Nutzung von [17] A. B. Rashid and M. Islam. Role of Materialized View Proxys zur Ergänzung von Datenbankfunktionen. In Maintenance with PIVOT and UNPIVOT Operators. Proceedings of the 22nd GI Workshop Grundlagen von In Proceedings of the 1st IEEE International Advance Datenbanken (GvDB 2010), pages 31–35, Bad Computing Conference (IACC 2009), pages 915–955, Helmstedt, Germany, May 2010. Mar. 2009. [2] S. Aulbach, T. Grust, D. Jacobs, A. Kemper, and [18] T. Rizzo, A. Machanic, and J. Skinner. Pro SQL J. Rittinger. Multi-tenant databases for software as a Server 2005. Apress, 2005. service: schema-mapping techniques. In SIGMOD [19] T. Schilling. Realisierungskonzepte für die Conference, pages 1195–1206, 2008. Aspektorientierte Datenhaltung. Studienarbeit, [3] R. Chitchyan, I. Sommerville, and A. Rashid. An Institut für Informatik, Friedrich-Schiller-Universität Analysis of Design Approaches for Crosscutting Jena, Apr. 2011. Concerns. In Workshop on Aspect-Oriented Design [20] C. M. Wyss and E. L. Robertson. A formal (held in conjunction with the 1st Aspect Oriented characterization of PIVOT/UNPIVOT. In Proceedings Software Development Conference (AOSD 2002), 2002. of the 14th ACM international conference on [4] E. F. Codd. A relational model of data for large Information and knowledge management, pages shared data banks. CACM, 13(6):377–387, 1970. 602–608, 2005. 30 Verbindung relationaler Datenbanksysteme und NoSQL-Produkte Ein Überblick Andreas Göbel Friedrich-Schiller Universität Jena Lehrstuhl für Datenbanken und Informationssysteme Ernst-Abbe-Platz 2 07743 Jena, Germany andreas.goebel@uni-jena.de KURZFASSUNG 1. EINLEITUNG In den letzten Jahren entstanden verschiedene Open-Source- Die zunehmende Verbreitung von Unternehmensnetzwer- Systeme, die mit fundamentalen Konzepten und Regeln rela- ken, globalen Netzwerken wie dem Internet und mobilen tionaler Datenbanksysteme brachen, um die Verwaltung von Endgeräten gepaart mit dem Wunsch vieler Unternehmen Daten in speziellen Einsatzbereichen zu optimieren. Die we- nach Globalisierung führt vermehrt zur Nutzung zentraler sentlichen Gründe für die Entwicklung dieser so genannten (Datenbank-)Services für eine Vielzahl von Nutzern. Die un- NoSQL-Systeme sind jedoch nicht SQL oder das relationale ter dem Begriff Web 2.0 zusammengefassten Entwicklungen Datenbankmodell, sondern sie ist auf die Implementierung ermöglichen zunehmend Interaktion und Verknüpfungen in relationaler Datenbanksysteme zurückzuführen. Der Beitrag Netzwerken, was sowohl die Gestalt als auch die Menge der verdeutlicht durch eine Gegenüberstellung von Oracle Re- Daten auffallend beeinträchtigt. So werden Inhaber erfolg- al Application Cluster, IBM DB2 PureScale und MySQL reicher Web-Anwendungen mit beachtlichen Datenmengen Cluster die gegensätzlichen Implementierungen relationaler konfrontiert, die das Datenaufkommen in klassischen Anwen- Clusterlösungen. An die Motivation der NoSQL-Produkte dungen um ein Vielfaches übersteigen können. sowie einen Überblick ihrer Zielstellung, Vor- und Nachteile Relationale Datenbanksysteme sind zentraler Bestandteil schließt sich das Aufzeigen von Möglichkeiten an, um Kon- des Software-Stacks vieler Unternehmen und Behörden. Mit- zepte und Implementierungen beider Welten miteinander zu tels der Verbindung eines mathematischen Fundaments, der verbinden und so die Vorzüge zu vereinen. Gewährleistung der ACID-Eigenschaften und der standardi- sierten deskriptiven Abfragesprache SQL stellen sie die Ver- fügbarkeit, Korrektheit und Auswertbarkeit der Unterneh- Kategorien und Themenbeschreibung mensdaten sicher. Der vorliegende Beitrag motiviert, warum H.2.4 [Database Management]: Systems—Parallel data- Betreiber vieler Web-Anwendungen trotz der auf der Hand bases ; H.3.5 [Database Management]: Systems and Soft- liegenden Vorteile bewährter relationaler Produkte Eigenent- ware—Distributed systems wicklungen propietärer Spezialsysteme zur Datenverwaltung vorantreiben, die bewusst auf wesentliche Merkmale relatio- naler Systeme verzichten. Allgemeine Bestimmungen Nach einer Gegenüberstellung relevanter Implementierung Theory, Design, Reliability relationaler Clusterdatenbanken werden die Herausforderun- gen und Einschränkungen der zu dem Schlagwort NoSQL zu- sammengefassten Systeme herausgearbeitet, einige aktuelle Stichworte Entwicklungen zur Verbindungen von NoSQL und RDBMS Parallel Databases, NoSQL, Postrelational, Hybrid zusammengefasst und die Notwendigkeit flexiblerer Imple- mentierungen relationaler Datenbanksysteme aufgezeigt. 2. HERAUSFORDERUNGEN Die Charakteristika zu verarbeitender Daten bei Web-An- wendungen führen zu folgenden Kern-Herausforderungen an zu verwendende Datenbanksysteme bzw. Datenspeicher. Performance und Skalierbarkeit kennzeichnen die be- deutendsten Herausforderungen. Die damit verbundene Ver- ringerung der Latenzzeit in Web-Anwendungen steht häu- fig in direktem Zusammenhang mit der Nutzerzufriedenheit und ist insbesondere in Bereichen wie Suchmaschinen oder 23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 31.05.2011 - 03.06.2011, Obergurgl, Austria. dem E-Commerce-Sektor von essentieller Bedeutung. Die Copyright is held by the author/owner(s). Performance resultiert aus der Grundperformance für Anfra- 31 gen und der Verarbeitungsgeschwindigkeit für steigende Da- tenvolumina, welche allgemeinhin als Skalierbarkeit bezeich- net wird. Eine zunehmende Datenmenge kann hierbei die Dauer von Aufgaben, die Anzahl der Aufgaben oder beides erhöhen. Die Skalierbarkeit eines Rechensystems kann durch den Einsatz leistungsfähigerer Hardware (vertikale Skalier- barkeit) oder durch das Verteilen der Aufgaben auf weitere Rechenressourcen (horizontale Skalierbarkeit) erzielt werden. Die Vorgänge müssen jeweils transparent zur Anwendung ge- schehen. Ausfallsicherheit ist für jedes zentrale (Datenverarbei- tungs-)System eine wesentliche Herausforderung, um Nut- zern dauerhafte Verfügbarkeit zu bieten. Neben ungeplanten Ausfällen eines Systems in Folge von Hardwaredefekten oder Systemfehlern müssen auch geplante Ausfälle – beispielswei- se zur Aktualisierung des Systems – vermieden werden. Bei- de Ausfallarten können erheblichen wirtschaftlichem Scha- den durch Kundenverlust oder Pönalen bei Verstoß gegen Service Level Agreements nach sich ziehen. Um Hochverfüg- barkeit zu erreichen, sollten Single Points of Failure (SPoF) Abbildung 1: Architektur von Oracle RAC (nach in einem System vermieden sowie binnen kurzer Zeit und [12]) automatisiert auf jegliche Art von Fehlern reagiert werden. Schemaflexibilität bezeichnet den Verzicht auf ein vor- definiertes und stets omnipräsentes Datenbankschema, um 3. RELATIONALE DATENBANKCLUSTER den Umgang mit Datenbanken und -speichern flexibler zu Horizontale Skalierbarkeit und Hochverfügbarkeit unter gestalten. Dies ermöglicht die adäquate Verwaltung semi- Einsatz kostengünstiger Hardware bilden nach Abschnitt 2 strukturierter und dokumenten-orientierter Daten, die nicht die wesentlichen Herausforderungen an die Speicherung und zuletzt aufgrund von Web-Standards und Auszeichnungs- Verarbeitung der Daten von Web-Anwendungen. Beinahe al- sprachen wie XML oder RDF in Web-Anwendungen weit le relationalen Datenbanksysteme bieten Mittel, um ihre Sys- verbreitet sind. Schemaflexibilität spielt des Weiteren eine teme vor Ausfällen und Datenverlust in diversen Fehlersze- wichtige Rolle bei der Konsolidierung von heterogenen Nut- narien zu schützen und eine hohe Verfügbarkeit zu erzielen. zerdaten innerhalb eines Systems. Sie bieten für dieses Ziel neben Sicherungs- und Wiederher- stellungsmöglichkeiten von Datenbanken verschiedene Tech- Kosten: Für viele Betreiber von Web-Anwendungen ist niken zur Replikation. Zumeist erkennen sie ein Problem je- der Einsatz kostengünstiger Hard- und Software eine Grund- doch erst beim erfolglosen Datenzugriff statt unmittelbar voraussetzung. Lizenz-, Support- und Administrationskos- nach dem Auftreten und erfordern im Fehlerfall einen ma- ten für Datenbanksysteme sowie die Anschaffungs-, Admi- nuellen Eingriff zum Umleiten auf das Replikat. Zudem sind nistrations- und Betriebskosten von Datenbankservern ma- die Replikate bei einigen Systemen ausschließlich im Fehler- chen meist einen nicht unerheblichen Teil der IT-Gesamt- fall einsetzbar und dienen im Normalbetrieb nicht der Last- aufwendungen aus. Aus diesem Grund wird für Unterneh- balancierung. Im Folgenden werden die Eckpunkte vorherr- men die Nutzung von kostengünstigen Cloud-Services oder schender Hochverfügbarkeitslösungen gegenübergestellt, die -Storages stets lukrativer. Entsprechend sollte ein geeignetes diese Mängel nicht aufweisen und zudem horizontale Skalier- Lizenzierungskonzept angeboten und der Einsatz auf Com- barkeit in Mehrrechnersystemen ermöglichen. modity-Servern unterstützt werden. 3.1 Oracle Real Application Cluster Für viele Provider ist die Antwortzeit der Web-Anwen- Oracle Real Application Cluster (RAC) ermöglicht bis zu dung derart wichtig, dass sie Einschränkungen der Daten- 100 Datenbankinstanzen einen parallelen Zugriff auf den- konsistenz in Kauf nehmen oder gar auf die Realisierbarkeit selben Datenbestand und realisiert somit eine Shared-Disk- des Definierens von Konsistenzsicherungen verzichten, wenn Architektur. Wie Abbildung 1 verdeutlicht, greifen die Ap- diese einen Performance-Overhead mit sich bringen. Dies ist plication Server und Web Server über eine gemeinsame Ser- bemerkenswert, denn es kennzeichnet einen wahrnehmbaren vice-Schnittstelle auf das System zu, die u.a. der Lastba- Wandel der Anforderungen an Datenbanksysteme. In klassi- lancierung dient. Sämtliche Dateien für Daten, Verwaltung schen Unternehmensanwendungen stellt die Forderung nach und Konfigurationsparameter werden auf einem clusterfähi- Datenkonsistenz die oberste Prämisse dar und ist unentbehr- gen Storage-System gespeichert und sind von allen Servern lich. Die Herausforderung besteht hierbei im Wesentlichen in les- und schreibbar. Lediglich die Undo- und Redo-Logs bil- der Optimierung der Performance. Dementgegen verdeutli- den eine Ausnahme: Sie werden stets von der Besitzerinstanz chen die obigen Herausforderungen, dass die Hauptaufgaben geschrieben und können nur von deren Nachbarinstanzen ge- vermehrt in der Optimierung der Antwortzeit oder nach [3] lesen werden, um die Besitzerinstanz bei einem Ausfall auto- gar in der Minimierung der (Hardware-)Kosten und Erhö- matisch wiederherstellen zu können. Der Ausfall eines Kno- hung des Konsistenzniveaus bei gegebenen Performance-Vor- tens wird durch eine Heartbeat-Netzwerkverbindung in kür- gaben zu sehen ist. zester Zeit erkannt. Extended Distance Cluster bietet durch 32 Abbildung 2: Architektur von IBM DB2 PureScale (nach [9]) eine Systemspiegelung auf ein aktives System innerhalb we- niger Kilometer das Reagieren auf Fehlerszenarien, die zum Abbildung 3: Architektur von MySQL Cluster (nach Ausfall des kompletten Clusters führen. Oracle Data Guard [10]) ermöglicht darüber hinaus das Spiegeln auf ein weiter ent- ferntes Standby-System zur Realisierung einer Disaster Re- covery.[12, 5] des Caches (Group Buffer Pool, GBP), wodurch analog zum Oracle RAC bietet Skalierbarkeit durch das Hinzufügen GRD und GCS des Oracle RAC die Informationen der Da- neuer Nodes, einen automatischen Lastausgleich und die pa- tenblöcke verwaltet und allen Servern zur Verfügung gestellt rallelisierte Ausführung von Operationen auf mehreren Ser- werden. Die Server sind untereinander sowie mit der CF mit- vern. Für den parallelen Zugriff mehrerer Instanzen auf den- tels eines Hochleistungsnetzwerks verbunden, welches einen selben Datenbestand nutzt Oracle im Falle einer Datenmodi- direkten Fernzugriff auf den Arbeitsspeicher (RDMA) in we- fikation den Global Cache Service (GCS), um zu bestimmen, nigen Mikrosekunden ermöglicht. Bei einem Schreibvorgang in welchen lokalen Knotencaches die betroffenen Blöcke lie- ermöglicht diese schnelle Verbindung das synchrone Aktua- gen bzw. ob sie sich gegebenenfalls bereits auf dem Storage- lisieren der zentralen Sperrtabelle in Form von Zeilen- und System befinden. Nachdem die Position bekannt ist, werden Seitensperren und des zentralen wie auch anderer relevanter die Blöcke durch ein In-Memory-Blockinventar (Global Re- Caches. Beim Lesevorgang eines Nodes wird nach erfolgloser source Directory, GRD) und Global Enqueue Service auf ak- Suche im lokalen Cache im GBP nach den Blöcken gesucht. tive Schreibsperren und weitere wartende Instanzen geprüft, Werden die Daten vom Festspeicher in den lokalen Cache um anschließend eigene Schreibsperren zu setzen, die wieder- geladen, wird dies ebenfalls dem GBP bekannt gemacht. [9, um im GRD vermerkt und anderen Nodes bekannt gemacht 6] werden. Die verwendeten Komponenten werden unter dem Ein integrierter Watchdog-Prozess überwacht permanent Begriff Cache Fusion zusammengefasst und ermöglichen zu- die Verfügbarkeit sämtlicher Knoten. Wird der Ausfall eines dem beim Datenzugriff das direkte Versenden von Daten Knotens bemerkt, stehen bis zum Instanzneustart lediglich zwischen Buffer-Caches verschiedener Nodes. Oracle RAC die momentan von diesem Knoten aktualisierten Tupel nicht vermeidet somit Cache-Kohärenz und ein SPoF durch einen zur Verfügung. Logs werden im Gegensatz zu Oracle RAC globalen Cache, jedoch auf Kosten von sehr viel Kommuni- auf den gemeinsamen Festspeicher geschrieben und sind für kation.[12, 5] die Recovery von anderen Knoten lesbar. 3.2 IBM DB2 PureScale 3.3 MySQL Cluster MySQL Cluster basiert im Gegensatz zu den Lösungen Das Design der IBM-Clusterlösung DB2 pureScale basiert von IBM und Oracle auf einer Shared-Nothing-Architektur, auf der Architektur des bewährten Parallel Sysplex für Sys- weshalb die bis zu 255 Datenknoten nicht parallel auf einen tem z1 . Sie ermöglicht durch eine Shared-Disk-Architektur gemeinsamen Datenbestand zugreifen, sondern jeder Daten- den gemeinsamen Zugriff von bis zu 128 Datenbankservern knoten einen Teil des Gesamtdatenbestands verwaltet. Die auf einen gemeinsamen Datenbestand, der durch IBMs Ge- Tabellen werden bei diesem Ansatz horizontal partitioniert. neral Parallel File System zur Verfügung gestellt wird. Die MySQL Cluster stellt keine spezifischen Voraussetzungen an Abbildung 2 zeigt, dass der Cluster neben den Datenbank- zu verwendende Netzwerke oder Server und unterstützt In- servern aus Cluster Facilities (CF) besteht. Um einen SPoF Memory- als auch Festpeicher-Datenspeicherung. Auf das zu verhindern, ist diese Komponente meist doppelt ausge- System wird über vollwertige MySQL-Server zugegriffen. Sie legt. Sie kann ein eigenständiges System sein oder auf einem sind mit einer Schnittstelle zur NDB-Engine versehen und Clusterknoten betrieben werden. Die CF ermöglicht die zen- werden zudem für verschiedene Funktionen wie Views, Trig- trale Verwaltung der Sperren (Global Lock Table, GLT) und ger oder Volltext-Indizes verwendet, die von der NDB-En- 1 Auf eine gesonderte Beschreibung des Parallel Sysplex wird gine nicht unterstützt werden. Die Management-Server sind aufgrund analoger Konzepte verzichtet. für die Konfiguration des Clusters zuständig, während die 33 Datenknoten zur Speicherung der Daten und der Verwal- MySQL-Server ausgelagert werden, um deren Performance tung von Transaktionen dienen. Knoten, die deckungsgleiche und Verfügbarkeit manuell gesorgt werden muss. Daher bie- Inhalte verwalten, werden zu einer Datenknotengruppe zu- tet sich der MySQL Cluster vor allem in Szenarien mit ei- sammengefasst, in der die synchrone Replikation der Knoten ner Vielzahl simpler Anfragen und hohen Latenz- und Ver- dazu führt, dass der Ausfall von Knoten keine aufwändige fügbarkeitsanforderungen an, während die Einsatzmöglich- Instanz -Wiederherstellung nach sich zieht. Somit müssen keiten von Oracle RAC und DB2 pureScale kaum begrenzt Undo- und Redo-Dateien anderen Knoten nicht sichtbar ge- sind. macht werden und das System ist verfügbar, solange ein Da- tenknoten je Gruppe erreichbar ist. Da beim Ausfall eines 4. NOSQL-BEWEGUNG Knotens die Aktualisierung einer zentralen Sperr- und Puf- In den letzten Jahren gewinnen so genannte NoSQL-Sys- ferverwaltung nicht nötig ist, können sehr geringe Failover- teme zur Verwaltung von Daten zunehmend an Bedeutung. Zeiten erzielt werden. Zudem werden asynchron Checkpoints Einige Kritikpunkte bei der Verwendung relationaler (Clus- auf einen Festspeicher geschrieben, um auf den Ausfall kom- ter-)Systeme in der Welt der Services regten Unternehmen pletter Gruppen reagieren zu können bzw. einen System- zur Eigenentwicklung von Systemen zur Datenspeicherung Reboot zu ermöglichen. Durch den Einsatz der MySQL Clus- und -verarbeitung an, die bewusst auf Merkmale relatio- ter Carrier Grade Edition kann Hochverfügbarkeit durch die naler DBMS verzichten, um sich auf einen Anwendungsfall Realisierung geografischer Replikation erzielt werden.[10, 11, zu spezialisieren. Ausgehend von den technischen Beschrei- 5] bungen von Systemen bekannter Internetgrößen entstanden im Laufe der letzten Jahre eine Vielzahl von Open-Source- 3.4 Bewertung Systemen. Diese kopierten, kombinierten und erweiterten die Die vorgestellten Datenbankcluster ermöglichen Skalier- Konzepte der Ausgangssysteme mit dem Ziel, den Anfor- barkeit sowohl durch Einsatz leistungsstärkerer Server als derungen der Unternehmen gerecht zu werden. Der Begriff auch durch das Hinzufügen weiterer Server. Trotz verschie- NoSQL“ umfasst all jene Systeme und wird inzwischen übli- ” dener Realisierungen verfügen sie über effiziente Strategi- cherweise als Not only SQL“ ausgelegt. Das Ziel dieser Sys- ” en für die wesentlichen Herausforderungen im Kontext der teme besteht im Aufzeigen von Alternativen zu relationalen Skalierbarkeit: Logging, Locking und die Verwaltung von Datenbanksystemen und nicht in deren Ablösung. Zwischenspeichern[13]. Im Gegensatz zum Shared-Nothing- Ansatz von MySQL Cluster basieren Oracle RAC und DB2 4.1 Zielstellungen pureScale auf einer Shared-Disk-Architektur und benötigen Mangels einer anerkannten Definition des Begriffs NoS- ” wegen ihrer nahen Knotenkopplung schnelle Kommunikation QL“ werden im Folgenden entsprechend der in Abschnitt 2 mittels Hochleistungsnetzwerken. Diese ist für die aufwändi- beschriebenen Herausforderungen die wesentlichen Zielstel- ge Kommunikation der Sperr- und Cachingverwaltung bei lungen der NoSQL-Systeme zusammengefasst, wobei diese gegebener Performance notwendig. als Obermenge der Ziele jedes einzelnen NoSQL-Systems zu Alle Systeme bieten hohe Ausfallsicherheit bis hin zu Un- sehen sind. terstützung einer Disaster-Recovery über die Anbindung ent- Performance, Skalierbarkeit: Untersuchungen wie [14] fernter Standby-Systeme. Serverausfälle werden beinahe un- zeigen, dass die Performance moderner RDBMS in verschie- mittelbar erkannt, die Wiederherstellung ist in kürzester Zeit denen Bereichen um ein Vielfaches übertroffen werden kann. möglich und führt kaum zu wenig Einschränkungen. Wäh- Als Grund wird vor allem die nach wie vor auf System R rend bei Oracle RAC im Fehlerfall bis zum Neuaufbau des basierende und stets erweiterte Architektur gesehen, wel- CGS für einen Augenblick keine Datenmodifikation durchge- che in der Client-Server-Welt hervorragende Dienste leistet, führt werden können, stehen bei DB2 PureScale die vom aus- für die Welt der Services und die verschiedenden Leistungs- gefallenen Knoten aktuell veränderten Daten bis zur Instanz- und Kapazitätsverhältnisse von Prozessoren, Fest- und Ar- Wiederherstellung nicht zur Verfügung. MySQL Cluster be- beitsspeicher jedoch neuer Architekturansätze bedarf [16]. sitzt durch den Shared-Nothing-Ansatz in Verbindung mit Das Hauptziel der meisten NoSQL-Datenspeicher ist das synchroner Replikation der In-Memory-Daten im Fehlerfall Erreichen linearer horizontaler Skalierbarkeit zur Verarbei- kaum Einschränkungen. tung riesiger Datenmengen. Sie nutzen hierfür überwiegend Die wesentlichen Nachteile von Oracle RAC und DB2 pu- Shared-Nothing-Architekturen in Verbindung mit horizonta- reScale bestehen im Kontext der Anforderungen in Abschnitt ler Partitionierung der Daten. Das im Jahre 2002 bewiesene 2 vor allem in den enormen Kosten für Lizenzen, spezielle Eric Brewers CAP-Theorem besagt, dass nur zwei der drei Hardware und Wartung im Vergleich zu MySQL Cluster. folgenden Eigenschaften eines verteilten Systems erfüllt sein Insbesondere sind hier der vor Ausfällen zu schützende Sha- können [4]. red Storage, das Cluster-Dateisystem sowie leistungsstarke • Consistency: Zu jedem Zeitpunkt sehen alle Knoten Netzwerke für die Clusterkommunikation und Cache Fusion denselben Datenbestand. bzw. die Cluster Acceleration Facilities zu nennen. Oracle RAC wurde zudem in den vergangenen Jahren um diverse • Availability: Knoten können Datenbestände jederzeit Features ergänzt, die zu einer System-Komplexität führten, schreiben und lesen. die eine intensive Einarbeitungszeit unabdingbar macht. • Partition tolerance: Das System arbeitet trotz einer Ein wesentlicher Vorteile von Oracle RAC und DB2 pu- Zerteilung in Teilsysteme weiter. reScale ist hingegen die einfache Migration von Anwendun- gen auf die Clustersysteme, da keine Änderung des Anwen- Während relationale Datenbanksysteme stets auf die Wah- dungscodes notwendig ist. Da die NDB-Engine von MySQL rung der Konsistenz bestehen und dies zur Beeinträchtigung Cluster nur einen Teil der Funktionen von InnoDB und My- der Performance und Skalierbarkeit nach sich zieht, verfol- ISAM unterstützt, müssen fehlende Funktionalitäten auf die gen viele NoSQL-Systeme den im Abschnitt 2 aufgefassten 34 Ansatz, strenge Konsistenzforderungen zugunsten der Per- Komplexitäts- und Mächtigkeitsgrades genutzt, was aus Sicht formance aufzugeben. des Programmierers ein Fortschritt, aus Sicht eines Daten- Ausfallsicherheit: Ein Großteil der NoSQL-Systeme bie- bänklers aber durchaus als Rückschritt gesehen werden kann tet hervorragende Replikations- und Failovertechniken, um [2]. Insbesondere der Verzicht einiger NoSQL-Systeme auf Ausfälle von Knoten innerhalb einer Shared-Nothing-Archi- die Gewährleistung der ACID-Eigenschaften führt dazu, dass tektur zu kompensieren, indem das System vor Datenverlust ein Großteil von Unternehmen den Einsatz dieser Systeme geschützt und der laufende Betrieb minimal beeinflusst wird. ausschließen wird. Schemaflexibilität: NoSQL-Systeme verdeutlichen, dass neben dem relationalen Datenbankmodell andere Datenmo- 5. VERBINDUNG BEIDER WELTEN delle existieren, die Daten gemäß ihrer Eigenschaften ad- Relationale Datenbanksysteme bieten aufgrund jahrelan- äquat speichern, ohne sie in ein fixes Datenbankschema zu ger Forschung und Entwicklung u.a. eine enorme Verbrei- fügen. Für einfache, schemafreie Daten bieten Key-Value- tung und Bekanntheit, ein ausgereiftes mathematisches Fun- Stores die Möglichkeit, mehrattribute Objekte anhand eines dament, die Datenbanksprache SQL und nicht zuletzt zu- eindeutigen Schlüssels zu speichern und abzufragen. Dokum- gesicherte Transaktionseigenschaften durch ACID. Auf der enten-basierte Systeme erlauben zudem das Speichern kom- anderen Seite existieren NoSQL-Systeme, deren Verbreitung plexerer Inhalte wie verschachtelte Daten und bieten durch sich in der Regel auf wenige Web-Anwendungen beschränkt. leistungsfähigere Abfragesprache beispielsweise das Suchen Charakterisiert durch die in Abschnitt 4 zusammengefass- auf beliebigen Attributen. Wide-Column-Stores vereinen hin- te Eigenschaften sowie die verwendeten Konzepte, weisen gegen Vorzüge des Relationenmodells mit Funktionalitäten sie zum Teil Zielstellungen auf, die sich deutlich von der wie flexiblen Schemata und Versionierung. Diese Datenmo- Zielstellung klassischer relationaler Datenbanksysteme un- delle werden beispielweise durch die Graphen-DBS ergänzt. terscheidet. Die Komplexität des Datenmodells spiegelt sich meist in der Eine Verbindung von Konzepten und Implementierungen zur Verfügung gestellten Programmierschnittstelle bzw. Ab- relationaler Datenbanksysteme und NoSQL Data Stores kann fragesprache wieder, es existieren für die Datenmodelle kaum dazu genutzt werden, die Vorteile beider Welten zu vereinen. standardisierte Notationen und standardisierte, deskriptive Im Folgenden werden mögliche Ansätze zur Vereinigung an- Sprachen. Entsprechend ihrer Zielstellung bieten sie häufig hand stellvertrender Beispiele vorgestellt. auf REST basierende Schnittstellen.[15] Kosten: Das Gros der Systeme wird als Open Source 5.1 Erweiterungen von NoSQL-Produkten und mit wenigen Nutzungseinschränkungen zur Verfügung NoSQL-Systeme wurden in der Regel für ein spezielles An- gestellt. Die Installation und Verwendung der Systeme ist wendungsgebiet entwickelt. Durch eine Erweiterung der Sys- meist unkompliziert. Zudem ist häufig ein Betrieb auf güns- teme kann ihr Einsatzbereich vergrößert werden, wodurch sie tigen Commodity Servern möglich, da Einschränkungen be- die Aufmerksamkeit von mehr Unternehmen auf sich ziehen züglich der zu verwendenen Hardware kaum vorhanden sind können. Somit wird neben der Erweiterung der Funktionali- und geläufige Betriebssysteme unterstützt werden. tät auch die Bekanntheit des Produkts gesteigert. Ein Bei- 4.2 Bewertung spiel für diesen Ansatz ist das Produkt Hive[17], welches das NoSQL-System Hadoop um die deskriptive, SQL-ähnliche NoSQL-Datenspeicher sind hervorragend geeignet, um kos- Sprache HiveQL erweitert und Schnittstellen in Form ei- tengünstig skalierbare und hochverfügbare Datenspeicherung nes CLIs, einer Web-Gui und JDBC/ODBC bietet. Zudem und -verarbeitung in einem begrenzten Anwendungsfall be- schafft es durch komplexe Analysen und das Absetzen von reitzustellen. Aus Sicht dieser Systeme sind die größten Hür- Ad-hoc-Abfragen die Voraussetzung, Hadoop für Data Ware- den beim Einsatz relationaler Systeme für Web-Applikatio- housing zu nutzen. nen nicht das relationale Datenbankmodell, ACID oder gar SQL. So zeigen aktuelle Entwicklungen im Bereich relationa- 5.2 Hybridsystem ler Datenbanksysteme wie VoltDB2 oder HyPer3 , dass diese Hybride Systeme wie HadoopDB[1] führen zu einem Kom- Merkmale eine lineare Skalierbarkeit nicht zwingendermaßen promiss zwischen zwei unterschiedlichen Produktwelten und ausschließen. Im Zentrum der Beanstandungen stehen hin- erschaffen dabei Produkte mit neuen Funktionalitäten. Das gegen die Tatsachen, dass keine bewährten parallelen und Open-Source-Produkt HadoopDB kombiniert MapReduce in hochverfügbaren Open Source RDBMS existieren und die Form der Implementierung Hadoops sowie Hive und Post- Implementierung bewährter relationaler DBMS häufig kei- greSQL, wobei das System bereits mit anderen Datenbank- ne hinreichende Skalierbarkeit zulässt. systemen getestet wurde. HadoopDB kann sowohl SQL-An- Die Spezialisierung der NoSQL-Systeme auf eine wenige fragen als auch MapReduce-Jobs entgegennehmen und bie- Anwendungsgebiet verwehrt in vielen Fällen den Einsatz tet den Zugriff auf Hadoops verteiltes Dateisystem HDFS bei sich ändernden Anforderungen, wie beispielsweise dem oder alternativ auf ein Datenbanksystem wie PostgreSQL Wunsch komplexer Abfragen auf Daten bei simplen Daten- an. In der Folge sind Nutzer durch die Verwendung von Ha- modellen. Bei der Nutzung eines relationalen DBMS wären doopDB in der Lage, mittels SQL auf ein Shared-Nothing- hierbei kaum Änderungen vonnöten, während ein NoSQL- DBMS zuzugreifen. System angepasst oder gar ausgetauscht werden muss. Ein Austausch gestaltet sich zudem schwierig, da es den Syste- 5.3 Anpassung von RDBMS men an standardisierten Notationen und Schnittstellen man- Der Abschnitt 4 verdeutlicht, dass die bewährten funda- gelt. Zudem werden statt deskriptiven Sprachen je nach Da- mentalen Konzepte hinter dem relationalen Datenbankmo- tenmodell meist Low-Level-Abfragesprachen verschiedenen dell mit Anforderungen wie enormer Skalierbarkeit vereinbar 2 http://voltdb.com/ sind, es hierzu jedoch einer Anpassung der von System R 3 http://www3.in.tum.de/research/projects/HyPer/ abstammenden Architektur bedarf. Die Implementierungen 35 von DBMS müssen sich durch geeignete Konfigurationsmög- von bereits wenige Beispiele existieren. Als Mittel der Wahl lichkeiten weit mehr als bisher an verschiedene Einsatzzwe- zur Vereinigung von Konzepten relationaler Datenbanksys- cke anpassen lassen. Realisiert werden kann dies beispielswei- teme und NoSQL-Systeme zeichnen sich jedoch aus Sicht se durch die Ausnutzung der Austauschbarkeit von Kompo- des Autors flexible RDBMS-Implementierungen ab, die sich nenten in modularen DBMS-Architekturen wie [7] oder die gezielter als in aktuellen Systemen an verschiedene Einsatz- Implementierung von adaptierbaren DBMS-Komponenten. zwecke anpassen lassen. Als mögliche Ansatzpunkte wurden Ein möglicher Ansatzpunkt dieses Konzepts könnte das die Implementierung verschiedener Storage-Engines und wei- Anbieten einer wahlweisen Speicherung auf langsamen, per- terer Transaktionskonzepte vorgeschlagen. sistenten Festspeichern oder im schnellen, flüchtigen Arbeits- speicher oder einer kombinierten Lösung sein, was bereits in 7. LITERATUR einigen Systemen wie dem in Abschnitt 3.3 beschriebenen [1] A. Abouzeid, K. Bajda-Pawlikowski, D. Abadi, MySQL Cluster möglich ist. Hierdurch bieten sich entspre- A. Silberschatz, and A. Rasin. HadoopDB: an chend der Charakteristika und des Umfang der zu speichern- architectural hybrid of MapReduce and DBMS den Daten sowie den Zugriffseigenschaften verschiedene Ein- technologies for analytical workloads. In VLDB ’09, satzmöglichkeiten. Orthogonal kann wahlweise eine spalten- pages 922–933. VLDB Endowment, 2009. oder zeilenbasierte Speicherung angeboten werden, um so- [2] D. J. DeWitt and M. Stonebraker. MapReduce: A wohl im OLTP- als auch im OLAP-Bereich überzeugende major step backwards, 2008. Leistungskennzahlen zu erzielen. Für die Implementierung [3] D. Florescu and D. Kossmann. Rethinking cost and bieten einige Systeme bereits verschiedene Storage-Engines performance of database systems. SIGMOD Rec., innerhalb eines Systems. 38:43–48, June 2009. Auch die Transaktionsverwaltung relationaler Datenbank- systeme bietet sich bezüglich einer Erweiterung an, indem [4] S. Gilbert and N. Lynch. Brewer’s conjecture and the neben den harten Anforderungen von ACID und den heute feasibility of consistent, available, partition-tolerant wählbaren Isolationsszenarien weitere Transaktionskonzep- web services. SIGACT News, 33:51–59, June 2002. te mit schwächeren Anforderungen integriert werden und [5] T. Grebe. Gruppendynamik – Oracle Real Application Administratoren die Wahl des Transaktionskonzepts über- Cluster vs. MySQL Cluster. databasepro, (6):46–63, lassen wird. Aus Sicht des in Abschnitt 4 angesprochenen 2010. CAP-Theorems könnten je nach Konfiguration des Systems [6] IBM. Transparent Application Scaling with IBM DB2 verschiedene CAP-Eigenschaften erfüllt werden und somit pureScale. Technical report, IBM, 2009. das Datenbanksystem an verschiedene Einsatzzwecke ange- [7] F. Irmert, M. Daum, and K. Meyer-Wegener. A new passt werden. Die Realisierung kann beispielsweise über ein approach to modular database systems. In EDBT autonomes Modul zur Transaktionsverwaltung in einer mo- Workshop der SETMDM ’08, pages 40–44, New York, dularen DBMS-Architektur gemäß [8] erfolgen. NY, USA, 2008. ACM. [8] F. Irmert, C. P. Neumann, M. Daum, N. Pollner, and K. Meyer-Wegener. Technische Grundlagen für eine 6. ZUSAMMENFASSUNG laufzeitadaptierbare Transaktionsverwaltung. In BTW In diesem Beitrag wurde die Notwendigkeit adaptierbarer ’09, pages 227–236, Münster, Germany, 2009. flexibler RDBMS-Implementierungen aufgezeigt. Als Grund- [9] A. Maslo. Unendliche Weiten – IBM DB2 pureScale lage diente der Vergleich von Oracle RAC, IBM DB2 PureS- für Power Systems. databasepro, (1):82–86, 2010. cale und MySQL Cluster. Er verdeutlichte, dass die Herstel- [10] MySQL. Hochverfügbarkeitslösungen von MySQL – ler zum Erreichen des Ziels eines horizontal skalierbaren und Ein Überblick über die Hochverfügbarkeitslösungen hochverfügbaren Clusterdatenbanksystems gemäß verschie- von MySQL. Technical report, MySQL AB, 2007. dener Implementierungsansätze verfahren. Während Oracle [11] Oracle. MySQL Cluster 7.0 & 7.1: Architektur und RAC und IBM DB2 PureScale sich durch gute Lastbalan- neue Funktionen. Technical report, Oracle, Inc., 2010. cierung, effizientes Logging, Locking und Caching sowie ein- [12] Oracle. Oracle Real Application Clusters fache Migration von Anwendungen auf die Clustersysteme Administration and Deployment Guide, 11g Release 2. hervorheben, ist MySQL Cluster vor allem durch geringe Technical report, Oracle Corporation, 2010. Ansprüche bezüglich der verwendeten Hardware und unkom- [13] M. Stonebraker. The NoSQL Discussion has nothing plizierte Fehlerbehandlung aufgrund der Shared-Nothing-Ar- to do with SQL. Blog-Eintrag, 2010. chitektur gekennzeichnet. [14] M. Stonebraker, C. Bear, U. Çetintemel, NoSQL Data Stores stellen vermehrt eine Alternative zu M. Cherniack, T. Ge, N. Hachem, S. Harizopoulos, RDBMS dar, die Systeme sind jedoch meist auf den Einsatz J. Lifter, J. Rogers, and S. Zdonik. One size fits all - in wenigen Anwendungsgebieten limitiert. Zudem mangelt Part 2: benchmarking results. In In CIDR, 2007. es ihnen an Standardisierung und vor allem die Low-Level- Abfragesprachen sind aus Sicht der Datenbankforschung als [15] M. Stonebraker and R. Cattell. Ten Rules for Scalable Rückschritt zu werten. Performance in Simple Operation“ Datastores. ” Durch die Verknüpfung bewährter Konzepte und Imple- Communications of the ACM, 2010. mentierungen der RDBMS mit Ansätzen der NoSQL-Bewe- [16] M. Stonebraker, S. Madden, D. J. Abadi, gung können Vorteile beider Welten vereint werden. Die Er- S. Harizopoulos, N. Hachem, and P. Helland. The end weiterung eines NoSQL-Systems führt nicht nur zu zusätzli- of an architectural era (it’s time for a complete chen Funktionalitäten, sondern steigert zudem die Bekannt- rewrite). In VLDB ’07, pages 1150–1160. VLDB heit und eröffnet neue Einsatzbereiche. Eine weitere Mög- Endowment, 2007. lichkeit stellt eine Kombination von RDBMS- und NoSQL- [17] A. Thusoo. Hive - A Petabyte Scale Data Warehouse Implementierungen in Form eines hybriden Systems dar, wo- using Hadoop. Technical report, Facebook Inc., 2009. 36 Ad-hoc Datentransformationen für Analytische Informationssysteme Christian Lüpkes OFFIS - Institut für Informatik Escherweg 2 26121 Oldenburg, Deutschland christian.luepkes@offis.de ABSTRACT ganisierten Taxonomien, sogenannten Dimensionen, gespei- Beim Betrieb von Data Warehouse Systemen kann es zu ei- chert. Dimensionen beschreiben, wie die Daten analysiert nem Semantic Shift kommen. Dieser bezeichnet eine Verän- werden können. derung der Bedeutung von Dimensionselementen und kann Das Data Warehouse ist dabei nach der Definition von bei Nichtbeachtung zu Informationsverlust und fachlich in- Inmon eine themenorientierte, integrierte, stabile Sammlung korrekten Analyseergebnissen führen. In dieser Arbeit wird zeitbezogener Daten, welche als Datenbasis zur Analyse dient ein graph-basierter Ansatz vorgeschlagen, welcher die Ände- [9]. Data Warehouses haben also immer einen Zeitbezug, bie- rungen zwischen Dimensionen als Überleitungen verwalten ten aber keine hochentwickelten Konzepte, um mit Änderun- und für Analysen zur Verfügung stellen kann. Dadurch wird gen in den Metadaten über die Zeit umzugehen. Klassisch es möglich, Anfragen in Analytischen Informationssystemen wird davon ausgegangen, dass die Metadaten über die Zeit unter Berücksichtigung eventueller Semantic Shifts zu be- weitgehend stabil sind [7] [11]. Falls die Metadaten in Einzel- antworten. Dieser Ansatz verzichtet dabei auf eine kennzahl- fällen doch angepasst werden müssen, werden die gespeicher- basierte Approximation und nutzt die Überleitungen klassi- ten Daten einfach den neuen Metadaten entsprechend umco- scher Adaptionsverfahren. Der eingeführte Ansatz wird kri- diert, die sogenannte Instanzadaption [2] [11]. Der Nachteil tisch hinsichtlich bestehender Ansätze diskutiert und exem- dieses Ansatzes ist, dass beim Umcodieren üblicherweise ein plarisch in verschiedenen Domänen durchgeführt. Informationsverlust entsteht. Zudem wird durch die Ände- rung der Metadaten und die Instanzadaption eine Wieder- holung früherer Anfragen unmöglich. Außerdem besteht bei Categories and Subject Descriptors klassischen Systemen keine Möglichkeit die spezifischen In- H.2.7 [Database Management]: Administration — Da- formationen der Metadatenänderungen zu speichern, da die ta warehouse and repository; H.2.8 [Database Manage- Metadaten selbst nicht zeitbezogen gespeichert werden [12]. ment]: Applications; H.4 [Information Systems Appli- cations]: Miscellaneous 2. PROBLEMBESCHREIBUNG Um das identifizierte Problem des Semantic Shift bei Da- General Terms tenanalysen zu verdeutlichen, soll an dieser Stelle zunächst Design, Data Analysis ein Beispiel aus der Arbeit des Autors im deutschen Ge- sundheitswesen gegeben werden. Dort werden alle Diagno- Keywords sen nach der ICD-Klassifikation, der International Statisti- cal Classification of Diseases and Related Health Problems, Data warehouse, Schema Versioning, OLAP, Temporal Data codiert. Die Klassifikation selbst beinhaltet sowohl beschrei- Warehouse bende als auch ordnende Metadaten und wird als Dimension zur Datenanalyse verwendet. Die deutsche Modifikation der 1. EINLEITUNG WHO-ICD, ICD-GM (German Modifikation), wird dabei je- Die am meisten verwendete Architektur für Analytische des Jahr durch eine Expertengruppe des DIMDI, Deutsches Informationssysteme ist die des Data Warehouses mit Me- Institut für Medizinische Dokumentation und Information tadaten, welche die gespeicherten Daten beschreiben und ei- aktualisiert [3] [4] [5]. ner auf diesen Metadaten aufbauender Auswertungssoftwa- Die Aktualisierungen bestehen darin, dass neu identifi- re. Die Metadaten werden dabei in streng hierarchisch or- zierte Erkrankungen einen Code zugewiesen bekommen, Er- krankungen zusammengefasst werden oder einzelne Krank- heitsbereiche neu unterteilt werden. So wurde zum Beispiel im Jahr 2006 der Code J09 für die neu identifizierte Vogel- grippe eingeführt. Um die Daten zwischen den Jahren transformieren zu kön- nen, stellt das DIMDI zusätzlich sogenannte Überleitungen in einem Datenbankformat zur Verfügung. In den Abbildun- gen 1 und 2 sind diese exemplarisch in Ausschnitten für die 23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 31.05.2011 - 03.06.2011, Obergurgl, Austria. Jahre 2005 bis 2007 gezeigt. Der Buchstabe A zeigt dabei Copyright is held by the author/owner(s). an, ob eine Überführung automatisch in der durch die Spal- 37 2005 2006 2007 icd_code2005 icd_code2006 auto2005_2006 auto2006_2005 J10.0 J10.0 A A J10 J09-J10 J09-J10 J10.0 J09 A J10.1 J10.1 A A J10.8 J10.0 J09 J10.8 J10.0 J10.8 J10.0 J10.8 J10.8 A A J09 J10.0 J10.8 J10.1 J10.0 J10.8 J10.1 J10.0 J10.8 J10.1 Abbildung 1: Ausschnitt der offiziellen ICD Über- leitungen zwischen den Jahren 2005 und 2006 Abbildung 4: Darstellung dreier Teilgraphen der ICD-GM Metadaten für Influenzaviren und deren tenüberschrift festgelegten Richtung möglich ist. Überleitung über die Jahre 2005 bis 2007 icd_code2006 icd_code2007 auto2006_2007 auto2007_2006 J09 J09 A A ist dies unproblematisch, da es keinerlei Änderungen in der J10.0 J10.0 A A Datenbeschreibung gab; zu erkennen an der Existenz der bi- J10.1 J10.1 A A jektiven Kanten zu den gleichen Knoten jedes Jahres. Das J10.8 J10.8 A A Problem des Semantic Shift tritt auf, wenn J10.0 für die Jahre 2005 bis 2007 untersucht werden soll. Es ist nicht ein- Abbildung 2: Ausschnitt der offiziellen ICD Über- deutig, welche Bedeutung von J10.0 verwendet werden soll. leitungen zwischen den Jahren 2006 und 2007 Falls die Bedeutung des Codes J10.0 vom Jahr 2005 beab- sichtigt ist, sollte für die Folgejahre auch der Code J09 be- Im Jahr 2005 auf 2006 ist es zum Beispiel möglich, den rücksichtigt werden. Falls die Semantik von 2006 oder 2007 Code J10.0 zwischen den Jahren umzucodieren. Allerdings gemeint ist, muss dem menschlichen Analysten bewusst sein, gibt es noch einen zweiten Eintrag von J10.0 auf J09 bei dass es eine inhaltliche Änderung vom Jahr 2005 zu 2006 für dem nur eine Umcodierung von 2006 auf 2005 zugelassen J10.0 gab auch wenn die Daten syntaktisch identisch sind ist. und Transitionen in beide Richtungen existieren. In Analytischen Informationssystemen werden die Daten Das analysespezifische Hintergrundwissen des Fachexper- meist nach der aktuellsten ICD-Definition gespeichert. Da- ten ist, dass J10.0 ein Sammelknoten für nicht genauer be- ten aus dem Jahr 2005 würden also im Jahr 2006 und 2007 stimmte Influenzaviren ist. Wie bereits oben erwähnt, wurde umcodiert. Entsprechend den Überleitungsregeln aus den in 2006 die Vogelgrippe identifiziert und als neuer Code J09 Abbildungen 1 und 2 würde der Wert J10.0 syntaktisch eingefügt. Dadurch wurde die Bedeutung von J10.0 als al- gleich bleiben und nicht umcodiert werden. le unbestimmten Influenzaviren zwar nicht verändert, aber Eine typische Anfrage wäre nun der Art Zeig mir die verglichen mit 2005 fehlen nun die Vogelgrippefälle. Für sta- ” tistische Analysen auf solch einer feingranularen Ebene wür- jährliche Summe aller behandelten J10.0 Patienten der Jah- re 2005, 2006 und 2007“ welche das in Abbildung 3 gezeigte den daher fehlerhafte Ergebnisse geliefert. Bei einer Analyse Ergebnis liefert. Im Jahr 2006 gab es also im Vergleich zum auf den Elternknoten J10 des Jahres 2005 oder J09-J10 der Vorjahr eine Abnahme von J10.0 Patienten die sich im Jahr Jahre 2006 und 2007 wären die Resultate korrekt, da alle 2007 noch deutlicher fortsetzt. Transformationskanten auf Kindknoten verweisen. Für die Ergebnisse in Abbildung 3 bedeutet dies, dass die Abnahme der J10.0 Erkrankungen auch darin begründet Summe der behandelten J10.0 Patienten nach Jahr liegt, dass Krankheitsfälle in J09 codiert wurden, die vorher in J10.0 enthalten waren. 2005 2006 2007 18347 17913 17548 2.2 Weitere Domänen Der Semantic Shift kann nicht nur in der medizinischen Abbildung 3: Summe aller behandelten J10.0 Pati- Dokumentation beobachtet werden, sondern auch in anderen enten der Jahre 2005, 2006 und 2007 Bereichen. So kann man z.B. für die Entwicklung der Länder Europas von 1988 bis 2000 bedingt durch den Zusammen- bruch des Warschauer Pakts ähnliches feststellen. Allerdings 2.1 Darstellung als Graph muss dort beachtet werden, dass es sich bei den abgeleiteten In Abbildung 4 ist exemplarisch ein Ausschnitt der ICD- und angepassten Metadaten nicht um gesetzlich vorgegebene Klassifikation für nachgewiesene sonstige Influenzaviren der Dimensionsstrukturen handelt, sondern um von Fachexper- Jahre 2005 bis 2007 abgebildet. Der Graph repräsentiert da- ten erstellte Dimensionen. Dies ist der Normalfall bei Da- bei die offizielle Taxonomie der ICD Codes und die gerichte- ta Warehouses. Die Dimension soll alle Länder im Herzen ten Kanten repräsentieren die offiziell als gültig definierten Europas widerspiegeln. Bis zum Jahr 1991 gab es die bei- Transformationsregeln für Umcodierugnen der drei abgebil- den eigenständigen deutschen Staaten BRD und DDR. In deten Jahre 2005, 2006 und 2007, wie sie in den Tabellen der Dimension wären diese dann als Blätter verfügbar. Mit der Abbildungen 1 und 2 definiert sind. der Wiedervereinigung wird das Blatt DDR gelöscht und In einem Data Warehouse werden die zu analysierenden die dazugehörigen Daten der BRD zugeordnet. Der Begriff Daten in der Regel auf der feinsten verfügbaren Klassifika- BRD ist also syntaktisch gleich geblieben, beschreibt nun tionsstufe vorgehalten. Veranschaulicht handelt es sich also aber einen deutlich größeren Bereich. um die Ausprägungen der Blätter. Falls eine Analyse der Würde man die Daten der BRD betrachten, so könnte Erkrankungen J10.1 oder J10.8 durchgeführt werden soll, man z.B. in 1991 eine deutliche Steigerung der Einwohner- 38 zahl feststellen. Dies wäre aber nicht durch hohe Geburtsra- Die am weitest gehende Lösung für das präsentierte Pro- ten begründet, sondern durch die größere betrachtete Fläche blem wurde 2002 in [12] veröffentlicht. Ein formales Tem- infolge der Wiedervereinigung mit der DDR. poral-Modell für die Beschreibung von Änderungen in den Die umgekehrte Richtung kann man bei der Tschechoslo- Dimensionen wurde dazu eingeführt [7]. Es wurden entspre- wakei beobachten. Bis 1990 war es die ČSSR, dann wurde chende Transformationsfunktionen definiert, welche die er- das gleiche Land umbenannt in ČSFR und im Jahr 1992 laubten Datenänderungen beschreiben. Der Ansatz ermög- aufgeteilt in die zwei Staaten Slowakei SR und Tschechien licht dabei Anfragen über verschiedene Versionen der Di- ČR. Für den letzt genannten Fall würde in der Dimension mensionen hinweg, indem die Daten zur Anfragezeit adap- ein Blatt gelöscht und dafür zwei neue Blätter eingefügt. Die tiert werden. Der Nachteil des Ansatzes liegt in der Realisie- dazugehörige Transformationsregel wäre, dass es keine Mög- rung der Instanzadaption durch die Verwendung von Matri- lichkeit gibt, ČSFR auf SR und ČR abzubilden, wohl aber zenmultiplikation. Jeder Wert einer Dimensionsversion muss in der Gegenrichtung. von Fachexperten mit einem Koeffizienten versehen werden, der aussagt wie ähnlich der Wert dem Nachfolger in der ver- 1989 1990 1991 1992 bundenen Dimensionsversion ist. Dies erlaubt eine Abschät- Alle Alle Alle Alle zung, um den Semantic Shift zu lösen. Jedoch hat dies zwei Nachteile. Zum einen muss der Koeffizient für jede Verwen- CSSR CSFR CSFR CR SR dung der Dimension in einer Kennzahl individuell angege- ben werden, da sich die Koeffizienten für z.B. Erkrankungs- BRD DDR BRD DDR BRD BRD und Sterberisiko unterschiedlich verhalten und deshalb die Koeffizienten nicht für alle Analysen gleich sind. Zum ande- ren wird das in den Transformationsdaten inhärente Wissen Abbildung 5: Darstellung von vier Ausschnitten ei- nicht dazu genutzt, genaue anstatt approximierten Ergeb- ner Länderdimension für die Jahre 1989 bis 1992 nissen zu liefern. und deren Überleitungen Die graph-basierte Visualisierung der beschriebenen Di- 4. DER GRAPH-BASIERTE ANSATZ mensionsentwicklung ist in Abbildung 5 zusehen. Dazu muss Wie in der Problembeschreibung ausgeführt und in den gesagt werden, dass der Aufbau und die Entwicklung der Di- Abbildungen 4 und 5 veranschaulicht, lassen sich Dimensio- mension von Fachexperten für Analysezwecke durchgeführt nen als streng hierarchische Bäume mit einem Wurzelknoten wurde. Die Dimensionen und Transformationen hätten auch darstellen. Die Blätter repräsentieren dabei in der Regel die auf andere Arten modelliert werden können. im Data Warehouse speicherbaren Werte. Falls Analysen auf den Elternknoten durchgeführt werden sollen, werden diese standardmäßig aus den Kindelementen berechnet [2]. 3. EXISTIERENDE LÖSUNGANSÄTZE Bei den Dimensionen handelt es sich um von Fachexper- Der erste Lösungsansatz für das Problem der sich ändern- ten modellierte Metadaten, die nur zu bestimmten Zeitpunk- den Dimensionen wurde 1993 von Kimball postuliert [11]. ten geändert werden. Deshalb ist es möglich, die Änderun- Die Lösung besteht in der Umcodierung der Daten nach der gen einer Dimension zusammen mit einer Versionsnummer jeweilig neuesten Dimensionsbeschreibung. Dies kann dabei zu speichern. Dieser Ansatz zur Beschreibung der zeitlichen in drei verschiedenen Arten geschehen. Der Type 1 Ansatz Entwicklung wurde auch von [12] und [8] verfolgt. Anders überschreibt die alten Werte mit den neuen, umcodierten aber als bei [11] soll keine Instanzadaption mit Informati- Werten. Die Type 2 und Type 3 Ansatz behält die alten onsverlust vorgenommen werden, sondern die Transformati- Werte zusätzlich bei. Auf diese Weise können alte Werte in onsregeln als gerichtete Kanten zwischen den Blättern zweier die neue Dimension transformiert, bzw. eingebunden wer- Dimensionsversionen gespeichert werden. Es wird verlangt, den. Der Nachteil aller dieser Ansätze ist aber, dass sie nicht dass jede neue Version einer Dimension Transformationsre- in der Lage sind mit dem Semantic Shift syntaktisch gleicher geln zu mindestens einem Vorgänger definiert. Dies ist keine Ausprägungen umzugehen. Es gibt also keine Unterstützung Einschränkung, da es beim Fehlen von Transformationsre- für Datenanalysen, die über verschiedene Versionen der Di- geln nicht um einen Nachfolger der Dimension sondern um mensionen hinausgehen, wenn sich die Bedeutung der Daten eine vollständig neue, andere Dimension handelt. geändert hat. Bei einer Anfrage an das Analytische Informationssystem Das Problem der Anfragen über mehrere Dimensionsver- soll ein Interpreter zwischen den Anwender und das Auswer- sionen wurde 2006 in [8] als graphentheoretisches Problem tungssystem geschaltet werden. Dieser Interpreter wertet die diskutiert. Dabei wurden die Metadaten als sogenannte Sche- Transformationsregeln aus und stellt fest, ob in dem ange- magraphen repräsentiert. Für die Graphen wurden erlaub- fragten Zeitraum für die auszuwertenden Daten eine Ände- te Modifikationen definiert, welche die potentiellen Ände- rung stattgefunden hat. Wenn dies nicht der Fall ist, wird rungen der Dimensionen wiedergeben. Wird eine Dimension die Anfrage ohne Nutzerinteraktion und ohne Änderungen durch eine Modifikation geändert, wird dies als neue Versi- durchgeführt. Falls jedoch zwei oder mehrere Dimensions- on in einem Graphen gespeichert. Basierend auf einer Gra- versionen von der Anfrage betroffen sind, wird der Interpre- phenalgebra ist es dadurch möglich, Anfragen über verschie- ter mittels der ein- und ausgehenden Kanten der Knoten dene Dimensionsversionen hinweg zu stellen. Diesem Ansatz prüfen, ob auf zusätzliche Knoten über die Kanten zuge- fehlt zum einen der Umgang mit dem Semantic Shift der Da- griffen werden kann. Wenn die Knoten für den gewünschten ten. Zum anderen erscheint er nicht praxisgerecht, da für his- Zeitraum stabil sind, wird dem Nutzer die Veränderung der torische Daten neu hinzugekommene Angaben nachträglich Dimension für seinen angefragten Ausschnitt als sogenann- eingepflegt werden müssen, um Vergleiche über verschiedene ter Evolutionspfad angezeigt. Versionen zu ermöglichen. Da es nicht beabsichtigt ist, die Definition der Transfor- 39 mationsregeln auf genau einen Vorgänger und Nachfolger Dimensionsversionen unter einem Elternelement sind, wird zu beschränken, kann es durchaus mehrere unterschiedliche davon ausgegangen, dass die Elternelemente gleich sind. Die Evolutionspfade geben, die zu unterschiedlichen Mengen von Anfrage wird dann direkt ausgeführt. Sollte es in irgendei- Knoten führen. Deswegen sollen die gefunden Evolutions- nem gültigen Evolutionspfad eines beliebigen Kindes meh- pfade dem anfragenden Nutzer angezeigt werden, der dann rere Elternknoten geben, würden dem Anwender wieder die den für seine Anfrage geeignetsten auswählen kann. Dabei verschiedenen Optionen wie bei den Einzelelementen ange- ist festzustellen, dass die Bedeutung der Evolutionspfade zeigt. Der Anwender wird also immer über Bedeutungsände- immer der modellierten Realwelt einer Dimensionsversion rungen und Systembrüche automatisch graphisch informiert entspricht. Dies führt dazu, dass die Daten dann ad-hoc und kann die für seine Zwecke geeignete Anfrage auswählen. zum Anfragezeitpunkt unter die ausgewählte Dimensions- version transformiert werden. Die Datentransformation ist 4.2 Vorteile des Ansatzes allerdings keine Instanzadaption, sondern eine Transforma- Es wird erwartet und angestrebt, dass der vorgestellte An- tion eines Wertes auf eine Menge von Werten. satz die folgenden Vorteile bietet: 4.1 Beispiel der Lösungsidee • Durch den graphenbasierten Ansatz, der auf eine kenn- Falls der Nutzer eine Anfrage der Art Gib mir die Summe zahlabhängige Approximation verzichtet, ist es mög- ” lich die Überführungsregeln für alle Analyseanfragen aller behandelten J10.0 Patienten der Jahre 2005 bis 2007“ stellt, wird der Interpreter die Werte J10.0 und die ICD-GM zu verwenden, welche die Dimension beinhaltet. Dies Dimensionsversionen 2005, 2006 und 2007 identifizieren. Den ist eine deutliche Erweiterung gegenüber [12]. Transformationsregeln in Abbildung 4 folgend, wird der In- • Da die Überfühungsregeln auch in klassischen Adap- terpreter zwei verschiedene Arten von J10.0 feststellen: Die tionsverfahren wie [11] benötigt werden, ist kein zu- Version 2005 hat zwei eingehende Kanten aus der Version sätzlicher Arbeitsaufwand der Fachexperten notwen- 2006, einmal vom J10.0 als auch vom J09 Knoten. Der In- dig, um die Kanten bereit zustellen. terpreter kann also feststellen, dass der Knoten J10.0 Ver- sion 2005 geteilt wurde. Nun prüft der Interpreter die iden- • Durch den graphenbasierten Ansatz ist es bei meh- tifizierten Knoten des Jahres 2006 und findet zusätzlich nur reren Überleitungsregeln pro Dimensionsversion mög- bidirektionale Kanten zu den Knoten des Jahre 2007, was lich, gröbere Versionen einer Dimension zu übersprin- bedeutet, dass keine Änderung stattgefunden hat. gen. Gröber meint dabei, dass Fehlen einzelner Kno- ten, die in späteren Versionen wieder eingefügt wur- 2005 2006 2007 den. Bei einer Umcodierung des Datenbestandes wäre J10.0 dies ein irreversiebler Informationsverlust. J10.0 J09 J09 J10.0 • Der Import und die Haltung der Daten wird verein- facht, da die Daten in ihrer originären Version gespei- Abbildung 6: Lösungsvorschlag mit Erweiterung der chert werden können. Die Daten müssen nicht in eine Anfragemenge, Konzept J10.0 Version 2005 einzige Version umcodiert werden. • Da der Nutzer zwischen verschiedenen inhaltlichen In- 2006 2007 terpretationen eines Wertes wählen kann, ist das An- fragesystem mächtiger als klassische Systeme. Zudem J10.0 J10.0 erlaubt dies die Wiederholung historischer Analysen, da die Datenbasis nicht umcodiert und die Dimensions- daten genauso erhalten bleiben. Abbildung 7: Lösungsvorschlag mit Beschränkung des Anfragebereichs, Konzept J10.0 Version 2006 4.3 Zu untersuchende Fragestellungen und 2007 Um sicherzustellen, dass ein Data Warehouse zusammen mit einer OLAP Analyse Anwendung die vorgestellten Funk- Dem Nutzer wird als Zwischenergebnis seiner Anfrage mit- tionen und insbesondere Vorteile erfüllen kann, muss unter- geteilt, dass zwei verschiedene Interpretationen von J10.0 sucht werden, welche Konsistenzbedingungen die Überlei- für den Zeitraum 2005 bis 2007 identifiziert wurden. Es wer- tungsregeln als auch die Metadaten einhalten müssen. Zu- den dann diese zwei verschiedenen Evolutionspfade zur Aus- dem sind die Anforderungen an die Datenrepräsentation und wahl angeboten: In Abbildung 6 wird die Erweiterung der Speicherung der Transformationsregeln und zusätzlichen Ver- Anfrage für die Jahre 2006 und 2007 um den Wert J09 vor- sionsinformationen in den Metadaten als auch der Daten- geschlagen, damit die Anfrage der Bedeutung von J10.0 im haltung zu untersuchen. Ein weiterer Bereich ist, wie sich Jahr 2005 entspricht. Die zweite angebotene Lösung ist in die Methoden auf verschieden Datenarten (Integer, Boolean, Abbildung 7 zu sehen. Hier wird die Bedeutung von J10.0 Nominal) als auch verschiedene Analyse Operationen (Sum, der Jahre 2006 und 2007 vorgeschlagen. Max, Min, Average) anwenden lassen. Da in Analysen auch Werden Anfragen auf höheren Ebenen der Dimension, wie oft mehrere verschiedene Dimensionen genutzt werden, muss z.B. die Gib mir die Summer aller behandelten Fälle von als letzter wichtiger Punkt noch die Anwendbarkeit auf meh- Grippen durch nachgewiesene Influenzaviren“ welche dem rere Dimensionen durchdacht werden. ” ICD Gruppencode J10 des Jahres 2005 bzw. J09-J10 der Jahre 2006 und 2007 entspricht, ist dies auch ohne wei- 4.4 Evaluation teres möglich. Für alle Kindelemente von J10 werden die Um den Ansatz mit seinen Konzepten und festgelegten Evolutionspfade ausgewertet. Da alle Kindelemente in den Anforderungen zu evaluieren, wird ein Prototyp auf Basis 40 von MUSTANG - Multidimensional Statistical Data Analy- Systematisches Verzeichnis. Systematisches Verzeichnis sis Engine [1] [13] umgesetzt werden. Dies ist ein kommerzi- zur Internationalen statistischen Klassifikation der elles Daten Analyse Tool, welches insbesondere für Analysen Krankheiten und verwandter Gesundheitsprobleme - im Gesundheitswesen, z.B. Krebsregistern, eingesetzt wird. German Modification. Deutsche Krankenhaus Verlags-Gesellschaft, (2004) Da das vorgestellte Thema durch zwei Projekte mit Kli- [4] DIMDI - Deutsches Institut für Medizinische nikdaten motiviert wurde, bei denen sich der Semantic Shift Dokumentation und Information: ICD-10-GM Version als problematisch erwiesen hatte, soll das Konzept in diesen 2006. Systematisches Verzeichnis. Deutsche evaluiert werden. Dabei handelt es sich zum einen um Da- Krankenhaus Verlags-Gesellschaft, (2005). ten deutscher Kliniken der Jahre 2006 bis 2010. Hier sollen [5] DIMDI - Deutsches Institut für Medizinische Fragen der Versorgungsforschung auf einer feingranularen Dokumentation und Information: ICD-10-GM Version Ebene ausgewertet werden, was bisher nicht möglich war. 2007. Band I: Systematisches Verzeichnis. Deutsche Zum anderen geht es in einem Forschungsprojekt der EU Krankenhaus Verlags-Gesellschaft, (2006) darum, für spezielle Herzschrittmacherpatienten statistisch [6] DIMDI - Deutsches Institut für Medizinische valide Muster zu identifizieren, die in historischen Patien- Dokumentation und Information: ICD-10-GM Version tendaten früherer Fälle enthalten sind. Die Patientendaten 2011: Band I: Systematisches Verzeichnis. Deutsche stammen dabei aus den Jahren 2006 bis 2011 eines österrei- Krankenhaus Verlags-Gesellschaft, (2010) chischen Universitätsklinikums, in dem später die Anwen- [7] Eder, J, Koncilia, C., Morzy, T.,: The COMET dung erfolgt. Hier liegt der Fokus darauf, alte Codierungen Metamodel for Temporal Data Warehouses. In Proc. of akkurat unter die aktuellste Version zu subsumieren, damit the 14th Int. Conference on Advanced Information die Muster auf aktuelle Fälle angewendet werden können. Systems Engineering (CAISE02), pp. 83–99.Springer Verlag (LNCS) (2002) 5. ZUSAMMENFASSUNG [8] Golfarelli, M., Lechtenbörger, J., Rizzi, S., Vossen, G.: Dieses Paper stellt einen Ansatz vor, der akkurate Da- Schema versioning in data warehouses: enabling tenanalysen in einem Analytischen Informationssystem über cross-version querying via schema augmentation. In sich ändernde Datengrundlagen ermöglicht. Die Datenände- DataKnowl. Eng., 59(2):435–459, 2006. Elsevier Science rungen können dabei sowohl syntaktischer als auch seman- Publishers B. V., Amsterdam, (2006) tischer Natur sein. Änderungen der Daten werden dabei als [9] Inmon, W. H.: Building the data warehouse (2nd ed.). verbindende Kanten zwischen verschiedenen Versionen einer John Wiley & Sons, Inc.,New York, NY, USA, (1996) Dimension modelliert und diese Dimensionen dabei als Gra- [10] Inmon, W. H., Strauss, D., Neushloss, G.: DW 2.0: phenstruktur aufgefasst. Durch die Interpretation der Ver- The Architecture for the Next Generation of Data bindungen zum Zeitpunkt einer Analyseanfrage, werden die Warehousing. Morgan Kaufmann Publishers Inc., San möglichen Evolutionspfade identifiziert. Die Evolutionspfa- Francisco, CA, USA, (2008) de repräsentieren dabei domänspezifisches Hintergrundwis- [11] Kimball, R.: Slowly Changing Dimensions. In DBMS sen, wie z.B. die Bedeutungsänderung von Werten, den Se- online, http://www.dbmsmag.com/9604d05.html (1996) mantic Shift. Der Nutzer kann dieses Hintergrundwissen vi- [12] Koncilia; C. A.: The COMET Temporal Data suell erfassen und sich für einen geeigneten Evolutionspfad Warehouse. PhD thesis, Universität Klagenfurt (2002) entscheiden. Die Analyseanfrage wird dann zur Anfragezeit [13] Teiken, Y., Rohde, M., Mertens, M.: Mustang - so umgewandelt, dass die Daten ad-hoc unter die gewähl- Realisierung eines analytischen informationssystems im te Bedeutung des Evolutionspfads transformiert werden. Da kontext der gesundheitsberichtserstattung. In K.-P. die Evolutionspfade so berechnet werden, dass Sie inhaltlich Fähnrich and B. Franczyk, editors, GI Jahrestagung identische und vergleichbare Mengen repräsentieren, sind die (1), volume 175 of LNI, pages 253–258. GI, (2010) Anfrageergebnisse akkurat. Dies wird dadurch ermöglicht, dass die Daten in ihrem Originalformat gespeichert und die Transformationsregeln nur gespeichert aber nicht direkt auf APPENDIX die Daten angewendet werden. Mit dem vorgestellten Modell A. ACKNOWLEDGMENTS und den dazugehörenden Methoden sind keine verlustbehaf- teten Datentransformationen oder Abschätzungen notwen- The research leading to these results has received in part dig. funding from the European Community’s Seventh Frame- work Programme (FP7/ 2007-2013) under grant agreement no. ICT-248240, iCARDEA project. 6. REFERENCES [1] Appelrath, H.-J., Rohde, M. , Thoben, W. , OFFIS e.V., MUSTANG - Multidimensional Statistical Data Analysis Engine: http://www.offis.de/en/offis_in_portrait/ structure/projects/detail/status/mustang.html, (2011) [2] Bauer, A., Günzel, H.: Data Warehouse Systeme. dpunkt.verlag, 3. überarbeitete und aktualisierte Auflage, (2009) [3] DIMDI - Deutsches Institut für Medizinische Dokumentation und Information: ICD-10-GM 2005 41 42 Wissensbasiertes Business Intelligence für die Informations-Selbstversorgung von Entscheidungsträgern Matthias Mertens OFFIS - Institut für Informatik Escherweg 2 26121 Oldenburg, Germany mertens@offis.de ABSTRACT Keywords Im Bereich der Business Intelligence haben sich Analyti- Semantic Metadata, Data Warehouse, Analytical Informati- sche Informationssysteme (AIS) mit dem Ziel entwickelt, on System, Decision support, Business Intelligence verschiedene Datenquellen integriert analysieren zu können und Informationen zu gewinnen die Business User, in ih- 1. EINLEITUNG rem Entscheidungsfindungsprozess unterstützen. Sowohl die Die Unterstützung des Managements und die Verbesse- hohe Komplexität, die sich aus der Flexibilität und Mäch- rung des Entscheidungsfindungsprozesses werden als Schlüs- tigkeit solcher Systeme ergibt, als auch die hohe notwendi- seleigenschaften der Business Intelligence (BI) gesehen [6]. ge Interaktion mit dem Nutzer zur Durchführung adäquater Entscheidungsträger, sogenannte Business User, sollen be- Analysen, bedingen entsprechendes Analyse- und Domänen- fähigt werden, alle benötigten Informationen zur richtigen wissen sowie ein tiefergehendes konzeptionelles und techni- Zeit zu erhalten. In der BI wurden analytische Informa- sches Verständnis. Dieses ist meistens bei Business Usern tionssysteme (AIS) entwickelt, die es Business Usern er- ohne entsprechende Schulung nicht gegeben, wodurch eine lauben große Datenmengen zu visualisieren, zu handhaben eigenständige Informationsversorgung mittels AIS behindert und zu analysieren. AIS bestehen aus einem Data Ware- wird. Erschwerend kommt hinzu, dass AIS in der Regel kei- house (DWH) und darauf aufbauenden Analysekomponen- ne zusätzlichen Metadaten zu Business Regeln, Strategien ten. Während das DWH es ermöglicht verschiedene Daten- oder Hintergrundinformationen erfassen, verwalten und für quellen qualitätsgesichert zu integrieren und multidimensio- die Analyseunterstützung bereitstellen können. nal aufzubereiten, erlauben die Analysekomponenten Online Idealerweise sollten Business User auf Basis einer Analyse- Analytical Processing (OLAP) Operatoren, komplexe statis- unterstützung des AIS dazu befähigt werden, adäquate Ana- tische Verfahren sowie geografische Operatoren in verschie- lysen durchzuführen, ohne zwingend über Analyse- und Do- denen Visualisierungen auf den integrierten Daten durchzu- mänenwissen verfügen zu müssen. Diese analyseunterstüt- führen. zenden Funktionalitäten können von weiterführenden Infor- mationen, über eine Navigationsunterstützung für Analyse- AIS haben jedoch auch verschiedene Mängel, die im nächs- pfade bis hin zu einer Vorschlagsgenerierung von Analyse- ten Abschnitt 2 näher betrachtet werden. Aus diesen leitet schritten reichen. sich die Forschungsfrage sowie die zugehörigen Anforderun- In diesem Paper werden Konzepte eines Analyseprozesses gen an einen Ansatz ab, welcher in Abschnitt 3 diskutiert und darauf aufbauend analyseunterstützende Funktionen vor- wird. Im Anschluss wird der eigene Ansatz mit zugehörigen gestellt, die eine Informations-Selbstversorgung des Business Konzepten und Funktionalitäten zur Analyseunterstützung Users erlauben. Der Fokus wird hierbei auf die Erweiterung in Abschnitt 4 mit der Anwendungsdomäne Krankenhaus- eines AIS um semantische Metadaten gelegt, um eine Erfas- ” marktanalyse“ (KMA) präsentiert, bevor im Abschnitt 5 sung, Verwaltung und Nutzung von Analyse- und Domänen- verwandte Arbeiten in diesem Forschungsumfeld aufgezeigt wissen zu ermöglichen. werden. Abschließend erfolgt in Abschnitt 6 eine Zusammen- fassung sowie ein Ausblick des Forschungsvorhabens. Categories and Subject Descriptors J.1 [Administrative data processing]: Business; H.4.2 2. MÄNGEL ANALYTISCHER INFORMA- [Information Systems Applications]: Types of Systems— Decision support TIONSSYSTEME In dem am OFFIS entwickelten AIS - Multidimensional Statistical Data Analysis Engine (MUSTANG) [9] - konn- te beobachtet werden, dass sich aus der hohen Flexibilität und Mächtigkeit von AIS eine Komplexität ergibt, welche zu einer signifikanten Herausforderung für Business User werden kann, wenn diese eigenständig adäquate explorative Analysen durchführen möchten. Im Gegensatz zu Analys- ten verfügen Business User in der Regel über ein geringeres 23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 31.05.2011 - 03.06.2011, Obergurgl, Austria. konzeptionelles Verständnis des multidimensionalen Daten- Copyright is held by the author/owner(s). modells (MDM) sowie geringeres notwendiges Analyse- und 43 Domänenwissen. Hierbei enthält das Domänenwissen Infor- Wie kann eine Komplexitätsreduktion von AIS mationen darüber, welche Fragestellungen einer zu untersu- mit dem Ziel erfolgen, ungelernte Business User chenden Analyse zu Grunde liegen, mit welchen Kennzahlen zu befähigen, selbst adäquate explorative Analy- Analysen zu spezifischen Fragestellungen möglich sind, wel- sen für eine intuitive und effiziente Informations- che explizite Semantik diese Kennzahlen haben und in wel- Selbstversorgung durchzuführen. chen Beziehungen diese zueinander stehen. In Abgrenzung dazu umfasst Analysewissen Informationen zu den Analyse- Um die Forschungsfrage zu beantworten, sieht der verfolg- instrumenten, d.h den Analyseoperationen, -verfahren und te Lösungsansatz die Verwendung von verschiedenen Analy- den möglichen Visualisierungen. Schließlich wird in den AIS seunterstützungsfunktionalitäten vor, welche explizites mo- für die Durchführung komplexer Analysen eine hohe Inter- delliertes semantisches Domänen- und Analysewissen aus- aktion mit den Business Usern benötigt, wodurch diese ohne nutzen. Dieses wird in ein semantisches Datenmodell des entsprechende Schulung schnell überfordert sind. AIS importiert, dort verwaltet und durch verschiedene Ser- vices genutzt werden. Ein weiterer Mangel von AIS wird in der geringen Be- rücksichtigung von Metadaten gesehen [2], die weiterführen- Folgenden Anforderungen werden an einen Ansatz gestellt: de Informationen über die quantitativen DWH Daten so- wie die DWH Struktur (Kennzahlen und Dimensionselemen- • Der Ansatz soll es einem domänenunabhängigen AIS te) bereitstellen. Zu diesen zählen Annahmen, Definitionen, ermöglichen Business User im Kontext domänenspezi- Business Regeln, Terminologien und Hintergrundinforma- fischer Analyseaufgaben zu unterstützen. Dafür wird tionen [10]. Daher müssen Business User sich die Semanti- ein Konzept bestehend aus einem generischen Daten- ken von Daten und Strukturen durch Zuhilfenahme externer modell in Verbindung mit einem domänenunabhängi- Quellen selbst erschließen [2]. gen AIS benötigt. Das Konzept wird für eine spezifi- sche Domäne instanziiert. Des weiteren sind AIS derzeit nicht in der Lage, Analyse- und Domänenwissen zu importieren, zu verwalten und für • Der Ansatz soll den Lernprozess von Analyse- und Do- weiterführende Analyseunterstützung der Business User zu mänenwissen unterstützen und den initialen Einarbeit- nutzen. Insbesondere ist die Expertise aus dem Bereich der ungs- und Trainingsaufwand ins AIS reduzieren. Busi- Analysestrategien und den Best Practices“ für Analysen in ness User sollen von der inhärenten Expertise des AIS ” spezifischen Domänen von Interesse. Wissen, das durch Ana- lernen. lysten in AIS eingebracht wird, geht in der Regel verloren [1]. • Der Ansatz soll eine Komplexitätsreduktion eines AIS Idealerweise sollten Business User befähigt werden, multi- verfolgen, ohne jedoch die Flexibilität und die Mäch- dimensionale quantitative Daten zu analysieren, ohne zwin- tigkeit des AIS einzuschränken. Das AIS soll für Busi- gend über Analyse- und Domänenwissen sowie ein tiefge- ness User mit geringer Expertise intuitiv benutzbar hendes konzeptionelles Verständnis verfügen zu müssen. Das sein, so dass diese adäquate explorative Analysen auf AIS sollte den Business User in seinen explorativen ad-hoc dem DWH durchführen können. Des Weiteren soll der Analysen unterstützen, indem es modelliertes semantisches, Ansatz die Anzahl der Nutzer-Interaktionen für das maschinenlesbares und -verständliches Wissen ausnutzt. Ana- Erreichen gleicher Analyseergebnisse reduzieren, wo- lyseunterstützende Funktionalitäten für eine Business User durch die Effektivität des AIS gesteigert werden soll. Self-Information Service [2, 12], könnten von weiterführen- den Informationen zu DWH Entitäten, über eine Naviga- • Das Konzept soll es ermöglichen, mit verschiedenen tionsunterstützung für Analysepfade bis hin zu einer Vor- Metadatenarten umzugehen und diese in einer intelli- schlagsgenerierung von weiteren sinnvollen Analyseschritten genten Art und Weise für eine Analyseunterstützung reichen. zu verknüpfen. Oftmals sind Ansätze in der Litera- tur zu finden [2, 7, 8, 11], die Hintergrundinforma- In diesem Paper werden nun im Folgenden Konzepte für tionen sowie Regeln über die DWH Struktur bereit- eine semantische Metadatenbasis sowie darauf aufbauende halten. Ferner sollen aber Metadaten zum Analysepro- analyseunterstützende Funktionalitäten für ein AIS vorge- zess berücksichtigt werden, die den Analyseprozess von stellt. Ziel ist es, dass Business User sich selbst mit Informa- einer Fragestellung über verschiedene Analyseschritte tionen auf eine effiziente und intuitive Art und Weise ver- hin zu einem Analyseergebnis beschreiben und wesent- sorgen können. Exemplarisch werden Beispiele aus der Do- liche Informationen für eine Analyseunterstützung be- mäne Krankenhausmarktanalyse (KMA) gebracht, da hier reithalten. Diese Metadaten werden auch Strategien Business User, z.B. Krankenhauscontroller durch die Verän- oder Best Practices“ genannt und beschreiben die Ex- derungen im deutschen Gesundheitswesen gezwungen wer- ” pertise bzw. das Analyse- und Domänenwissen eines den, zur Sicherung der Wettbewerbsfähigkeit die Potentiale Analysten. Schließlich soll das AIS ebenfalls Metada- ihres Krankenhauses zielgerichtet zu erschließen und Leis- ten zu quantitativen Daten des DWH, sprich zu Analy- tungsangebote konkurrenzfähig auszurichten. seergebnissen wie z.B. Trends, spezifische Zusammen- hänge, etc. verarbeiten. 3. FORSCHUNGSFRAGE UND ANFORDE- Im nächsten Abschnitt 4 werden verschiedene Konzepte RUNGEN eines Datenmodells sowie die darauf anwendbaren Funktio- Motiviert aus den in Abschnitt 2 genannten Mängeln wird nalitäten zur Analyseunterstützung und zur Erfüllung der die folgende Fragestellung abgeleitet: Anforderungen diskutiert. 44 4. WISSENSBASIERTE FUNKTIONEN UND 4.1 Analyseunterstützende Funktionalitäten KONZEPTE FÜR EINE ANALYSEUNTER- Um den genannten Mängeln aus Abschnitt 2 unter Be- STÜTZUNG rücksichtigung der in Abschnitt 3 erläuterten Anforderun- gen zu begegnen, werden die Metadaten in Form einer se- Ziel des hier diskutierten Ansatzes ist es, Business User mantischen Suche, Navigation und eines Recommendings ge- im Kontext domänenspezifischer Analyseaufgaben zu unter- nutzt. Die Metadaten werden an den Business User über die- stützen. Hierzu sollen verschiedene unterstützende Funktio- se Funktionalitäten kommuniziert. nalitäten auf Basis eines modellierten semantischen Meta- datenmodells bereitgestellt werden (s. Abschnitt 4.1). Als Semantische Suche: Das übergeordnete Ziel der seman- Wissensrepräsentationssprache zur Modellierung des Meta- tischen Suche ist, eine Suchfunktion auf definierten Meta- datenmodells, in Form von mehreren miteinander verknüpf- daten anzubieten. Instanzen des Metadatenmodells sollen ten Ontologien, kommt OWL-DL zum Einsatz. Eine DWH- anhand ihrer Semantik gesucht, gefunden und anschließend Ontologie bildet das MDM des jeweils zu Grunde liegen- visualisiert werden. den DWHs als Instanzen ab und ermöglicht es, in den dar- Ein spezifischeres Ziel ist unter anderem die Suche nach be- auf aufbauenden Ontologien das MDM zu referenzieren. Die stehenden Fragestellungen und damit verbundenen Analyse- Analyse-Ontologie modelliert abstrakt Entitäten und deren ketten, die sich auf die jeweilige Analysesituation adaptieren Beziehungen, die die Analyseprozesse in einem MDM be- lassen. Auch semantisch verknüpfte Fragestellungen, die in schreiben. Diese decken den gesamten Analyseprozess von einer Vorgänger-, Nachfolgerbeziehung stehen, können ge- Fragestellungen, über Analyseketten hin zu Analyseergeb- funden werden. Daneben spielt auch das Finden von Analy- nissen ab, beschreiben aber auch die enthaltenden Opera- seergebnissen und damit verbundenen quantitativen Daten toren, Visualisierungen, Verfahren und Business Rules. Die des DWH eine Rolle. Annotationen auf den quantitativen wichtigsten Konzepte werden in Abschnitt 4.2 erläutert. Die Daten können mit ihrer Semantik gefunden und in der zu- auf der Analyse-Ontologie aufbauende Domänen-Ontologie gehörigen Analysevisualisierung wieder dargestellt werden. beinhaltet die konkreten Instanzen der Analyse-Ontologie Ebenfalls lassen sich die durchlaufende Analysekette samt für eine Domäne. Sie bildet also das für Analyseunterstüt- Fragestellung und analysierendem Business User ermitteln zung genutzte Analyse- und Domänenwissen ab. Für eine und als Ausgangsbasis für anknüpfende Analysen verwen- detaillierte Beschreibung der Ontologien und deren Zusam- den. menhänge sei auf [9] verwiesen. Semantische Navigation: Werden die Klassen und Re- Im Metadatenmodell zu speicherndes Wissen soll Aus- lationen des Metadatenmodells für eine konkrete Domäne sagen zu konkreten Fragestellungen, über durchzuführende instanziiert, so kann eine Navigation von einer Klassenin- Analyseschritte bis hin zu erkennbaren Analyseergebnissen stanz zur Nächsten, entlang der dazwischen definierten se- enthalten. Soll z.B. die Fragestellung Welchen Marktanteil mantischen Relation, erfolgen. Im Kontext eines AIS kann ” hat mein Krankenhaus (KH) im Einzugsgebiet?“ untersucht diese semantische Navigation zum einen als eine reine Navi- werden, so ist als Wissen modelliert, dass das Einzugsge- gation innerhalb der Metadaten erfolgen und zum anderen biet, bestehend aus Kernmarkt, erweiterter Kernmarkt und können zusätzliche assoziierte Operationen des AIS ausge- Peripheriemarkt, für das KH über dessen Fallzahlen ermit- führt werden. telt werden muss und dass der Marktanteil eine berechnete Für Ersteres sei auf Abb. 1 verwiesen. Wird die Fragestel- Kennzahl im DWH ist. Diese berechnet sich aus dem Ver- lung zur Kennzahl B mit Hilfe der semantischen Suche ge- hältnis der erwarteten Fallzahl und den behandelten Fällen funden, so kann der Business User sowohl zu den notwen- des KH. Des Weiteren ist z.B. als Wissen modelliert, dass digen Vorgänger-Fragestellungen als auch den Nachfolger- sich aus der ersten Fragestellung weitere relevante Frage- Fragestellungen oder zu weiteren verbundenen Instanzen na- stellungen ableiten können, z.B. Wie verhält sich die Fra- vigieren. ” gestellung für Konkurrenten oder aber für spezifische Fach- abteilungen (FA) des eigenen KH?“. Für letzteres müssen muss / optional verfeinert / aggregiert Kennzahl C insbesondere die behandelten Diagnosen (ICD-Codes) und optional die vorhandene Ausstattung / Verfahren (OPS-Codes) so- Nachfolger Fragestellung wie der Versorgungsschwerpunkt der FA im MDM berück- 1 sichtigt werden. Besonders relevant ist das Wissen zu weite- Kennzahl A Kennzahl B Kennzahl ... rem Analysevorgehen im Kontext von Analyseergebnissen, Vorgänger Nachfolger Fragestellung Fragestellung wie z.B. erkannten Auffälligkeiten: Änderungen im Patien- Fragestellung ... tenspektrum / Einweiserverhalten; oder Erkennen von Ver- Kennzahl m sorgungslücken oder Regionen mit stillen Reserven“. ” Nachfolger Fragestellung m Das Konzept sieht einen initialen Aufbau der Wissens- basis, mit Hilfe einer Expertengruppe vor. Diese können im Sub- Sub- Sub- Verfeinerungen KMA Umfeld z.B. einer Krankenhauskette oder einem Bera- Kennzahl B Fragestellung Fragestellung Fragestellung in den 1 ... n verschiedenen tungsunternehmen angehören und ihr Analyse- und Domä- Dimensionen nenwissen in den Ontologien persistieren. Da das modellier- te Wissen eine Allgemeingültigkeit in der modellierten Do- Abbildung 1: Beziehungen von Fragestellungen mäne haben soll, ist eine spätere personifizierte Anpassung bzw. die Erfassung zusätzlicher personenbezogener Metada- Möchte der Business User basierend auf einer Fragestel- ten derzeit nicht vorgesehen. lung eine konkrete Analyse durchführen, so kann er von der 45 Fragestellung zu der verbundenen Start-Analysevisualisier- Analysevisualisierung: Eine Analysevisualisierung ist ung wechseln und dann entlang eines spezifischen Analy- die grafische Repräsentation der quantitativen Daten eines sepfades zu einer Ende-Analysevisualisierung navigieren (s. Analyseschrittes z.B. in Form einer Pivottabelle, eines Dia- Abb. 2). Diese Art der semantischen Navigation ist immer gramms oder einer Karte. Sie besteht aus 1 bis n Kenn- mit realen Aktionen und Daten des AIS verbunden, da Ana- zahlen, die wiederum in 1 bis m Dimensionen aufgespannt lysevisualisierungen quantitative Daten des DWH anzeigen sind. Von diesen Dimensionen sind jeweils 1 bis z Dimen- und beim Analysevisualisierungswechsel durch die Domä- sionselemente gewählt. Im Kontext der Analysekette sind nenoperationen ein oder mehrere OLAP Operationen im sogenannte Start- und Ende-Analysevisualisierungen defi- AIS angewendet werden. niert. Erstere dienen als Einstiegspunkte für die Analysen von Fragestellungen. Von ihnen aus können die Analysepfa- Vorschlagsgenerierung: Eine wichtige Funktion ist das de mit ihren verschiedenen Analysevisualisierungen durch- Geben von Hinweisen und Vorschlägen durch das AIS im laufen werden. Letztere ermöglichen das Interpretieren der Kontext einer Fragestellung und einer Analysevisualisierung. quantitativen Daten hinsichtlich der Fragestellung und das Diese werden aus dem im Metadatenmodell hinterlegten Ana- Ableiten von Analyseergebnissen. lyse- und Domänenwissen abgeleitet. Vor allem weiterfüh- rende Hintergrundinformationen, Business Rules und Ana- Domänenoperation: Eine Domänenoperation ermöglicht lysestrategien sowie weitere Fragestellungen können wertvol- das Navigieren zwischen zwei Analysevisualisierungen und le Informationen im Analyseprozess sein. kommt zum Einsatz, wenn spezifische Ausprägungen des Hinweise zu weiterführenden sinnvollen Analysevisualisie- MDM in einer Analysevisualisierungen eintreten. Domänen- rungen können durch das AIS gegeben werden, indem mögli- operationen können aus einer Menge auszuführender OLAP- che Domänenoperationen und die enthaltenen Business Ru- Operatoren, Business Rules und Visualisierungswechseln be- les auf ihre Anwendbarkeit in einer Analysevisualisierung stehen. Ihr Zweck ist es, die notwendigen Schritte der Kenn- überprüft werden. Ziel der Vorschlagsgenerierung soll es sein, zahlen-, Dimensionen-, Dimensionselemente- und Visualisie- dass relevante Analysevisualisierungen erreicht werden, die rungsauswahl bzw. des -wechsels für den Endanwender durch- eine Interpretation der quantitativen Daten hinsichtlich der zuführen und somit die Komplexität des MDM und der Fragestellung zulassen. Wichtig ist, dass beim Geben der Analysedurchführung zu verbergen. So kann der Business Hinweise und Vorschläge sowie bei der Anwendung von Do- User direkt von einer Analysevisualisierung zu einer nächs- mänenoperationen die Hintergründe kurz erläutert werden, ten sinnvollen Analysevisualisierung gelangen. Ob eine Ana- damit diese für den Business User nachvollziehbar bleiben lysevisualisierung als sinnvoller weiterer Analyseschritt ge- und er sich zusätzlich Analyse- und Domänenwissen aneig- sehen werden kann, ist über die Business Rules definiert. nen kann. Business Rules: Business Rules repräsentieren konkre- 4.2 Wissensbasierte Konzepte tes Analyse- und Domänenwissen und werden als semanti- sche Metadaten zu den domänenspezifischen Inhalten eines Im Folgenden werden die für eine Analyseunterstützung AIS modelliert. Sie beschreiben weiterführende Informatio- notwendigen Entitäten des Analyseprozesses in einem AIS nen und Regeln und kommen im Analyseprozess in den Do- näher betrachtet. mänenoperationen zur Anwendung. Business Rules lassen Fragestellung: Eine Fragestellung gibt einer Hypothese Aus- sich aus den Best Practices“ eines Analysten ableiten und druck, die es zu klären gilt und auf deren Ergebnis eine ” beziehen sich in der Regel auf eine Fragestellung, eine Analy- Entscheidung basieren kann. Als Beispiel sei “Was sind die sevisualisierung oder ein Analyseergebnis, oder aber auf eine Marktanteile in meinem Einzugsgebiet?” genannt. Hierbei Kombination aus diesen. Die Business Rule ist anwendbar, ist eine einzelne Fragestellung in der Regel nicht losgelöst wenn das MDM einen spezifischen definierten Zustand er- von Anderen zu betrachten (s. Abb. 1). Vielmehr kann ei- reicht. Mehrere Business Rules können in unterschiedlichen ne Fragestellung über Vorgänger verfügen, wie z.B. “Was ist Domänenoperationen anwendbar sein, woraus sich mehrere mein Einzugsgebiet?”, auf welche zuvor eine Antwort gefun- Möglichkeiten für den Business User ergeben können, wie er den werden muss. Sie kann über weiterführende Nachfolger- seine Analyse fortsetzen möchte. Durch die Gewichtung der Fragestellungen verfügen, die sich aus dem Analyseergebnis Business Rules kann hierbei ein Ranking entstehen. ergeben und optional weiter analysiert werden können. Bei- spiele sind: “Was sind die Marktpotenziale in meinem Ein- Analysepfad: Unter einem Analysepfad wird eine Men- zugsgebiet?” oder “Wie wird sich mein Marktanteil entwi- ge von Analysevisualisierungen verstanden, die durch Domä- ckeln?”. Neben Vorgängern und Nachfolgern kann es auch nenoperationen zu einem Pfad in einer definierten Reihenfol- Subfragestellungen geben, welche die gleiche Kennzahl(en) ge verbunden werden. Typischerweise wird ein Analysepfad wie die Originalfrage behandeln, jedoch diese hinsichtlich ein in einer konkreten Analyse von einer Start-Analysevisual- oder mehrerer Dimensionen weiter verfeinern. isierung zu einer Ende-Analysevisualisierung durchlaufen. Hierbei ist zu beachten, dass Analysepfade nicht zwingend Analysekette: Eine Analysekette wird für die Analyse zuvor definiert sein müssen, sondern sich aus der Anwend- von Fragestellungen verwendet. Diese bildet den logischen barkeit von Domänenoperationen auf Analysevisualisierun- Rahmen der Analyse und enthält weitere Konzepte wie Ana- gen im Kontext einer spezifischen Fragestellung ergeben kön- lysepfade, Analysevisualisierungen, Domänenoperationen und nen. Die Menge aller Analysepfade zu einer Fragestellung Business Rules. Die Zusammenhänge sind in der Abb. 2 dar- bildet die Analysekette. gestellt. Ziel der Analysekette ist das Finden ein oder mehre- rer Analysevisualisierungen, die eine Interpretation der quan- Analyseergebnis: Analyseergebnisse beschreiben eine In- titativen Daten des DWH erlauben. terpretation von quantitativen Daten im MDM des DWH. 46 Finden von bestehenden Analysekette (Durchlaufen ein oder mehrerer Analysepfade) Analyse- Fragestellungen und ergebnisse Analysevisualisierungen (Bestätigung / Analysepfad 1 als Startpunkt Wiederlegung Analysepfad 2 der Hypothese) Analysepfad 3 Start Ende Fragestellung Analyse- erlaubt Analyse- Verknüpft mit Analyse- Domänenoperation Domänenoperation Analyse- visualisierung finden ergebnis visualisierung visualisierung Domänen- Domänen- operation operation Sub- Ende Analyse- Analyse- erlaubt Fragestellung Domänenoperation Domänenoperation Analyse- finden ergebnis visualisierung visualisierung Domänen- Domänen- operation operation Ende Sub- Domänen- Analyse- Domänen- erlaubt Analyse- operation operation Analyse- Fragestellung visualisierung finden ergebnis visualisierung wird zu Basis für Hypothese neue Nachfolger-Fragestellung ç externe Domänenoperation Entscheidung Abbildung 2: Zusammenhang von Konzepten im Analyseprozess Dies können Korrelationen und Zusammenhänge zwischen tidimensionalen Datenraum zu navigieren und um die be- den Daten, aber auch Trends, Einbrüche, Zunahmen, Auf- nötigten Informationen zu erfragen. Hierbei ist laut [5] das fälligkeiten, geografische Ballungen, etc. sein. Erstellen entsprechender Anfragen eine schwierige Aufgabe. Daher wird in dieser Arbeit ein Framework vorgestellt, dass den Nutzer in der Analyse unterstützt, indem es passende 5. VERWANDTE ARBEITEN OLAP Operatoren vorschlägt. Diese werden durch die Aus- Im Kontext der Business Intelligence gibt es vielfältige wertung des OLAP Server Query Logs abgeleitet. Forschungsfragen, die von der Erschließung des Analysewis- sens [1], über die Anpassung der BI-Tools an Business An- Eine andere Art der Analyseunterstützung für eine höhere forderungen [11, 2] und die integrierte Anfrage von BI-Tools Nutzerfreundlichkeit wird im Kontext der BI in der Tren- [12, 4] bis hin zur Annotation von Datenschemata mit wei- nung von Business und IT Belangen gesehen. Anders als terführenden Informationen zur Analyseunterstützung rei- in den zuvor genannten Arbeiten spielen hier semantische chen [2, 7, 8, 11]. In vielen Fällen soll der Analyst und teil- Metadaten eine entscheidende Rolle. Über die Metadaten- weise auch der Business User [2, 12] stärker in den Fokus modelle können die Entitäten der zugrunde liegenden BI- rücken, indem die BI-Software besser an individuelle Infor- Systeme mit ihren zugehörigen Relationen modelliert wer- mationsbedürfnisse angepasst werden kann oder aber eine den. Ebenfalls erlauben diese flexiblen, erweiterbaren Meta- Analyseunterstützung zur individuellen Befriedigung des In- datenstrukturen weiterführende Informationen zu den Enti- formationsbedarfs angeboten wird. Viele der verwandten Ar- täten, wie beispielsweise Business Rules oder Expertenwis- beiten versuchen die jeweiligen adressierten Probleme durch sen festzuhalten. In [7] und [8] werden diese Möglichkeiten die Nutzung von semantischen Metadaten und damit ver- weiter vertieft und als Anwendung z.B. die Nutzung der Me- bundenen Semantic Web Technologien zu lösen. tadaten im Extraktions-, Transformations- und Ladeprozess (ETL) für ein DWH angeführt. Im Bereich der Dokumentation von Analyseprozessen und -ergebnissen ist die Arbeit [1] zur Distribution von Business- In der Arbeit von [11] wird auf dieser Semantic Web Basis Intelligence-Wissen zu nennen. Diese zielt auf die kontrollier- eine Architektur für analytische Tools vorgeschlagen, um Ef- te organisationsweite Verbreitung und Weiterverwendung fizienzsteigerungen im Entscheidungsfindungsprozess zu er- von Berichten und Analyseansätzen durch das Einstellen der zielen. Durch die Nutzung einer Domänen-Ontologie, welche BI-Inhalte in Wissensmanagementsysteme ab, jedoch ohne die Entitäten der zu untersuchenden Domäne, deren Relatio- auf eine konkrete technische Umsetzung einzugehen. nen sowie weitere Informationen bereitstellt und durch die Nutzung einer Business-Intelligence-Ontologie, welche Infor- Im Kontext von Analyseprozessen ist auch die Arbeit von mationen zu den Datenstrukturen des multidimensionalen [3] relevant, da diese den Begriff der Analysekette einführt. Modells vorhält, soll eine Unterstützung im Analyseprozess Fokus der Arbeit ist die Mensch-Maschine Interaktion, wo- erfolgen. Zum einen soll die Auswahl von Dimensionselemen- bei das Finden, Aufbereiten und Darstellen von Daten als ten durch proaktive Vorschläge erleichtert werden und zum technisch / operative Tätigkeit gesehen wird. Zu den kogniti- anderen sollen durch ein semiautomatisches Umschreiben ven Tätigkeiten zählen die Bildung eines anwenderorientier- der Anfragen Analyseergebnisse aufgewertet werden. Die En- ten Analysemodells sowie dessen Prüfung und Verfeinerung. titäten werden in den jeweiligen Domänen-Ontologien oft- mals mit ihrem natürlichsprachlichen Namen versehen, da Während der Durchführung von Analysen werden eine diese eher die Business Semantik ausdrücken als die kor- Reihe von OLAP Anfragen gesendet, um durch den mul- respondierenden technischen Bezeichner des MDM. Nutzer 47 können so Anfragen in einer für sie vertrauten Terminologie prachen modelliert und für die Domäne der Krankenhaus- an das System stellen. Dieser Ansatz wird in [4] und [12] ver- marktanalyse instanziiert. Dieses Metadatenmodell wird in wendet, um auf einer abstrakten Ebene unternehmensweite eine zu implementierende semantische Metadatenebene des Informationen integriert aus verschiedenen BI-Systemen wie am OFFIS entwickelten AIS - Multidimensional Statisti- DWH, ERP, CRM, etc. anzufragen. In diesen Ansätzen wer- cal Data Analysis Engine (MUSTANG) - eingebettet, um den semantische Metadaten auch für die Integrationsaufga- Analyse- und Domänenwissen zu erfassen, zu verwalten und ben und das Umschreiben von Anfragen verwendet. für die genannten Analyseunterstüzungsfunktionalitäten zu verwenden. Eine Umsetzung und Evaluierung wird im Rah- Die Unterstützung eines technisch unversierten Business men einer laufenden Dissertation und einer studentischen Users wird insbesondere in [2] und [12] fokussiert. In [2] liegt Projektgruppe erfolgen. der Schwerpunkt auf einer kollaborativen ad-hoc Entschei- dungsunterstützung, in der Daten integriert aus den ver- 7. REFERENCES schiedenen BI-Tools dargestellt und über semantische Meta- [1] H. Baars. Distribution von daten mit weiterführenden Informationen versehen werden. Business-Intelligence-Wissen. Analytische Insbesondere sollen über Web 2.0 Technologien Information Informationssysteme, pages 409–424, 2005. Mash-Ups gebildet, aber auch eine Kollabration zwischen [2] H. Berthold, P. Rösch, S. Zöller, F. Wortmann, verschieden Business Usern erzielt werden. A. Carenini, S. Campbell, P. Bisson, und F. Strohmaier. An Architecture for ad-hoc and Auch wenn, wie in vielen anderen Arbeiten, die semanti- collaborative Business Intelligence. In Proceedings of schen Metadaten eine entscheidende Rolle spielen, grenzt der the 2010 EDBT/ICDT Workshops, EDBT ’10, pages eigene Ansatz sich von diesen durch die Modellierung von 13:1–13:6, New York, NY, USA, 2010. ACM. Konzepten und deren Instanziierung in Form von Analyse- [3] N. Bissantz. Deltaminer. Wirtschaftsinformatik, und Domänenwissen ab. Im Fokus steht dabei das Wissen 43(1):77–80, 2001. zu Analyseprozessen, das von verschiedenen Komponenten [4] L. Cao, C. Zhang, und J. Liu. Ontology-based eines AIS zur Unterstützung des Business Users genutzt wer- Integration of Business Intelligence. Web Intelligence den kann. Eine technologisch ähnliche Umsetzung mit Hilfe and Agent Systems, Volume 4, 2006. von verschiedenen Ontologien wie sie in [11] und [12] genannt werden, wird angestrebt. [5] A. Giacometti, P. Marcel, und E. Negre. A Framework for Recommending Olap Queries. In Proceeding of the ACM 11th international workshop on Data 6. FAZIT UND AUSBLICK warehousing and OLAP, DOLAP ’08, pages 73–80, Analytische Informationssysteme haben sich im Kontext New York, NY, USA, 2008. ACM. der Business Intelligence als Systeme zur Informationsge- [6] P. Gluchowski und H.-G. Kemper. Quo Vadis Business winnung für Business User im Entscheidungsfindungsprozess Intelligence? Aktuelle Konzepte und etabliert. Allerdings setzen AIS aufgrund ihrer hohen Inter- Entwicklunstrends. Business Intelligence Spektrum, 1. aktionsmöglichkeiten und Komplexität entsprechendes Ana- Jg., Heft 1, Mai 2006:12 – 19, 2006. lyse- und Domänenwissen sowie ein tiefergehendes techni- [7] N. Inference. Ontology and Data Warehousing. sches Verständnis voraus, um adäquate Analysen durchfüh- Technology white paper, NETWORK INFERENCE, ren zu können (s. Abschnitt 1). Dieses liegt jedoch ohne ent- INC., 2004. sprechende Schulungen bei Business Usern nicht vor. Auch [8] L. Ludwig. Business Intelligence und das Semantic werden in der Regel keine Metadaten zu Business Regeln, web: Ein Traumpaar. 2005. Strategien oder Hintergrundinformationen durch AIS bereit- [9] M. Mertens, Y. Teiken, und H.-J. Appelrath. gestellt, die den Business User unterstützen können. Da je- Semantische Anreicherung von strukturierten Daten doch Business User befähigt werden sollen, sich selbst mit und Prozessen in Analytischen Informationssystemen Informationen zu versorgen, wurde in dieser Arbeit als For- am Beispiel von Mustang. In Forschungskolloquium schungsfrage untersucht, wie die Komplexität von AIS redu- der GI Fachgruppe 5.8 - Management Support ziert werden kann, damit Business User eine adäquate ex- Systems, Dortmund, Deutschland. Universität plorative ad-hoc Analyse durchführen können. Hierzu wur- Dortmund, 2009. den zunächst in Abschnitt 3 Anforderungen an einen ent- sprechenden Ansatz definiert. Darauf aufbauend wurden in [10] B. ONeil. Semantics and business. The Data Abschnitt 4 verschiedene Konzepte aus dem Bereich der Administration, 2007. Datenanalyse definiert und erläutert, die in einem seman- [11] D. Sell, L. Cabral, E. Motta, J. Domingue, tischen Metadatenmodell für ein AIS modelliert und instan- F. Hakimpour, und R. Pacheco. A semantic web based ziiert werden können und somit als Basis für weiterführende Architecture for Analytical Tools. In CEC ’05: Analyseunterstüzungsfunktionalitäten dienen. Von zentraler Proceedings of the Seventh IEEE International Bedeutung waren die Konzepte der Fragestellung, Analyse- Conference on E-Commerce Technology, pages kette, Analysepfad und Analysevisualisierung sowie Domä- 347–354, Washington, DC, USA, 2005. IEEE nenoperationen, Business Rules und Analyseergebnisse. Als Computer Society. Funktionen wurden die Semantische Suche, die Semantische [12] M. Spahn, J. Kleb, S. Grimm, und S. Scheidl. Navigation und die Vorschlagsgenerierung präsentiert, be- Supporting Business Intelligence by providing vor in Abschnitt 5 verwandte Arbeiten vorgestellt und gegen ontology-based End-User Information Self-Service. In den eigenen Ansatz abgegrenzt wurden. Als weiterer Schritt OBI ’08: Proceedings of the first international im Forschungsvorhaben werden die vorgestellten Konzepte workshop on Ontology-supported business intelligence, in einem Metadatenmodell mittels Wissensrepräsentationss- pages 1–12, New York, NY, USA, 2008. ACM. 48 Towards Efficiently Running Workflow Variants by Automated Extraction of Business Rule Conditions Markus Döhring Christo Klopper Birgit Zimmermann SAP Research Darmstadt SAP Deutschland SAP Research Darmstadt Bleichstraße 8 Hasso-Plattner-Ring 7 Bleichstraße 8 64283 Darmstadt, Germany 69190 Walldorf, Germany 64283 Darmstadt, Germany markus.doehring@sap.com christo.klopper@sap.com birgit.zimmermann@sap.com ABSTRACT 1. INTRODUCTION Efficient workflow variant management is becoming crucial Workflow management systems (WfMS) are becoming an especially for enterprises with a large process landscape. Our essential part of most industrial IT system landscapes [19]. research fosters the combination of business rules for adapt- For some domains, traditional WfMS have already been de- ing reference workflows at runtime and tailoring them to termined as unsuitable to cover prevalent requirements w.r.t. many different situations. A main goal is to optimize the the flexibility of workflows [7]. In order to address the chal- performance of workflow instances w.r.t. different aspects, lenge of managing workflow variants (i.e. workflows with e.g., branching decisions, throughput time or compliance. slight deviations from a “reference workflow”) at design-time Having a data mining procedure at hand which can auto- as well as their dynamic adaptation at runtime due to chang- matically extract potentially useful conditions from execu- ing data contexts, we have proposed the integration of busi- tion logs to create new variants is therefore a very signifi- ness rules containing adaptation operations on adaptive seg- cant benefit. The extracted conditions could be conveniently ments in reference workflows [10]. reused within the business rules of our framework, which can In many practical scenarios, it is unrealistic that process handle the deviations at runtime for those special situations. analysts are able to define all variants and exceptions in However, most existing data-mining techniques do not de- a workflow. Especially when a WfMS is introduced in a scribe a continuous mining pipeline how to get from work- company, but also if workflow models are already mature, flow logs to problematic context conditions for new variant environmental changes may lead to shifts in the impact fac- creation or are difficult for business people to interpret. tors on process performance. A potential relief for making Therefore we present an integrated rule mining method- such blind spots in workflow execution visible is the applica- ology, starting with the semi-automatic discovery of “hot tion of process mining techniques. The goal is to find data- spots” within workflow instance logs. Then, data variables dependencies for weak spots in the workflows and making of instances related to these hot-spots are translated into a them available as conditions for additional business rules data mining classification problem. Other than related ap- leading to new workflow variants. Existing work has partly proaches, we employ a fuzzy rule learning algorithm, yielding addressed these issues each with a relatively isolated view easily interpretable and reusable conditions for variants. We on e.g. bottleneck detection or dependency mining. Results also provide first insights from a case study at a consulting w.r.t. to an integrated “mining pipeline” for a business user company and corresponding open research challenges. are however still quite unsatisfying. For example, prevalent approaches leave the user with a mined decision tree which, as we will show, might be hard to read for real-world work- Categories and Subject Descriptors flow logs. Instead, we aim at a pipeline from a workflow defi- H.2.8 [Database Management]: Database Applications— nition in an understandable notation over automated mining Data Mining; H.4.1 [Information Systems Applications]: application to interpretable business (variant) rules. Office Automation—Workflow Management; D.2.2 [Software Our approach is based on the general idea of rule-based Engineering]: Design Tools and Techniques workflow adaptation as described in Section 2. As a solu- tion to the above challenges, in Section 3 we present a min- ing methodology which we consider promising as a suitable Keywords mining pipeline for a business user. For each of the method- workflow, business rules, process mining, process perfor- ology’s three generic steps, concrete technologies and their mance, rule learning wiring are explicated, especially the employment of a fuzzy mining approach for ruleset extraction. We then present first learnings from a case study on real-world workflow ex- ecution data building upon our methodology in Section 4 and summarize challenges which have to be solved to fully implement our methodology in Section 5. In Section 6 we discuss related research, before we conclude in Section 7 and state remaining issues for future work. 23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 31.05.2011 - 03.06.2011, Obergurgl, Austria. Copyright is held by the author/owner(s). 49 2. FLEXIBILIZATION OF WORKFLOWS BY ADAPTATION RULES Workflow Logs Select Problem Category(s) Our methodology for condition extraction is motivated 2. Automatic Detection of by a general approach for workflow adaptation [10, 9]. It is •Control-Flow (BPMN Model) „Hot Spots“ •Transformation of hot- spots into classification problem considered essential to establish a basic understanding of the •KPIs (SCIFF or LTL) •Behaviour Constraints •BPMN to petrinet conversion. •Fuzzy rule-learning for (SCIFF or LTL) data-dependencies of hot- nature of business(variant) rules as targeted for being auto- •… •Conformance checking •Performance checking spots matically mined. Our framework as well as the examples (bottlenecks) •Aggregation of problems 3. Automatic Filtering of 1. Specify Expectations to hot-spots. in this paper rely on BPMN2 [1], because its notation is a Against your Process „responsible“ data dependencies de-facto industry standard which was designed to be under- Extract Adaptation Rule standable for business users. Basically, the framework con- for Workflow Improvement sists of three conceptual building blocks for workflow variant Workflow Model management and flexible workflow adaptation: Specify Rules 1. Adaptive Segments in BPMN2 Reference Work- flows: An adaptive segment demarcates a region of a work- Figure 1: Outline of the Rule Extraction Procedure flow which may be subject to adaptations at runtime when entering the segment. It corresponds to a block-structured part of the workflow, i.e. a subgraph which has only one 3. METHODOLOGY FOR VARIANT RULE incoming and one outgoing connection. In special cases, adaptive segments can also be “empty”. What matters is CONDITION EXTRACTION that they correspond to valid BPMN2 workflow definitions As already stated, we are interested in automatically ex- and not to a kind of white box which is left empty for later tracting condition constraints (the “IF-part”) for potentially filling. We have extended the BPMN2 metamodel to capture useful workflow adaptation rules within our framework. Use- the special semantics of adaptive segments [9]. ful in this respect means, that the condition constraints 2. Workflow Adaptations Defined in BPMN2: The should describe eventually problematic situations in work- actual definition of potential adaptations which can take flow instances by means of their data context values, such place at runtime have been proposed as a pattern catalogue that a timely adaptation of a workflow instance can eventu- [10] which also relies on BPMN2 notation, with the benefit ally prevent such a situation. Our proposed methodology is that adaptation patterns are comprehensible and extensible. illustrated in Figure 1 in a circular manner. The methodol- The catalogue contains basic adaptations like SKIP or IN- ogy is divided into three main phases explained in detail in SERT, but also more sophisticated event- and time- related the following subsections. For each phase, concrete concepts patterns, like “event-based cancel and repeat” or “validity and technologies for implementing the methodology are dis- period”. Every adaptation pattern has the block-structured cussed and open challenges are outlined where existing. adaptation segment as an obligatory input parameter. As such, patterns can be conveniently nested and combined. 3.1 Formulation of Log Expectations 3. Linking Adaptations to Data Contexts by Busi- The first phase of our methodology consists in the def- ness Rules: Business (variant) rules are used to apply suit- inition of expectations towards a set of workflow instance able adaptations for different situations expressed by data logs. Correspondingly, there are two obligatory input com- context conditions. The data context can be globally valid ponents for the extraction pipeline: a workflow model and (like a date) or workflow instance specific (like an order a sufficiently large set of workflow instance logs belonging value). A pseudo-syntax for variant rules, where ∗ stands to the model. The instance logs must contain workflow- for 0-n repetitions, can be defined as: ON entry-event IF relevant events like at least the start or finishing timestamp THEN APPLY []∗ Once the general relations of adaptive segments context variables1 . Since we want to target business users and potential adaptations have been established by a pro- with our rule extraction approach, we consider BPMN as an cess analyst, the conditions could be maintained by a busi- appropriate input format for the expected control-flow logic ness user e.g., via a domain-specific language. For automatic restricing the expected order of task executions and event rule extraction, in this work we therefore especially focus on occurrences in the input logs. the IF-part of potentially newly discovered variant rules and As an optional input, additional constraints w.r.t. work- aim at revealing data dependencies for variants which are flow execution can be provided in some form of logic. These not a-priori known, but have significant implicit impact on constraints may concern time-related interdependencies of the overall business performance of workflow execution. events within a workflow instance log, whereas typical key Figure 2 exemplifies the above concepts based on a ship performance indicators (KPIs) like throughput times can be engine maintenance workflow fragment. The actual conduc- understood as a subset of such time constraints. But also tion of engine tests for a ship may depend on the harbor other more sophisticated circumstances which are hard to in which it currently resides. Due to environmental re- model in BPMN2 graph structures can be provided as log- strictions, many different harbors impose specific time con- ical constraints, as for instance that a task A should be straints on ships conducting engine tests. In Hamburg for executed N times after the occurrence of task B. Suitable example, ships may only have 12h time, after which devices logics to formulate such process-related constraints can for need to be reset and the tests need to be restarted. For example be based on the SCIFF framework [5] or linear tem- adapting the workflow correspondingly, a generic parame- poral logic (LTL) [17]. Since a regular business user may not terizable template is used and weaved with the segment at 1 It is hard to give generally valid recommendations on data runtime. size characteristics, but from experience reasonable mining can start from 1000 instances with about 5 context variables. 50 be familiar or feel comfortable with such logics, it is recom- In contrast to the checking mechanisms for issues (1.) mended to provide constraint templates, i.e. small chunks of and (2.), a challenge consists in the spotting of the logic mapped to easily parameterizable pieces of restricted actual source for a constraint violation. For our KPI natural language for constraint maintenance. example (B 1h after A), if B is not executed at all, it has to be decided whether A or not B or both are to be 3.2 Automatic Discovery of “Hot Spots” considered as the actual error source and kept for fur- For the ability to apply established mining and analy- ther analysis. Potentials lie in the partly automated sis techniques on the instance logs in combination with the mapping of constraint predicates to places or transi- workflow model, it is useful to first transform the BPMN tions in the underlying model and the consideration of workflow definition into a pure formal representation, e.g. in “what happened first”. Research is still ongoing here. terms of petri net graphs which are backed by a long trail of As a final step of this phase, the user is confronted with is- research and corresponding toolsets. Transformation mech- sues which have a particular degree of “severity” (e.g. exceed anisms which are able to map a large part of BPMN con- a predefined fraction of instances which are non-conformant) structs to petri net constructs exist [8] and can be employed and gets the corresponding “hot-spots” based on average in- within our methodology. The next phase of our methodol- stance execution marked in the BPMN process model. The ogy then consists in the automatic discovery of problematic proper automatic accumulation and back-projection of is- spots in the instance logs, relating to different issues: sues to the BPMN workflow model remains an open issue. The user may then select one or several hot spots and one or 1. Non-conformance to defined workflow model: several problem types for these hot-spots for further analysis Using log-replay approaches on the petri net model by mining data dependencies as business rule conditions as as presented in [16], it can be determined whether described in the next subsection. instances behave exactly according to the underlying model or whether there are deviations. Provided the 3.3 Automatic Extraction of Rules for “Hot petri net has been suitably constructed, such devia- Spot Occurrences” tions can be structurally spotted as petri net places For the selected hot-spots and problem types, the instance where tokens are left over after an instance has been data from the workflow logs is transformed into a classifica- finished or where tokens often are missing when a tran- tion problem for machine learning algorithms. A classifi- sition should be fired. In most of the latter cases, a cation problem consists of a number of cases (=workflow distinct transition (=BPMN task) can be “blamed” for instances), each made up of a number of numeric or nomi- causing the non-conformance. Places and transitions nal data variable values (=workflow instance or task context, with a relatively high error-rate are kept for further e.g. order value, customer priority or shipment partner) and analysis within our methodology. a single class in terms of a category for a learning instance. The class can be determined in a binary manner as problem- 2. Disproportionate delays (bottlenecks): Similar atic or non-problematic from the problem types connected to the above petri net log-replay techniques, the so- to the hot spots, but also the distinction of finer-granular journ times of tokens in places and the times it takes problem classes can be considered. The variable values for to execute transitions can be stored [12]. Based on this a learning instance can be constructed by looking at their computed data, it can be determined where instances occurrence when an instance has reached a hotspot in the on average get stuck for a disproportionate amount of petri net. Special challenges in this conversion step concern time related to the average overall throughput time. the treatment of some control-flow constructs, as for exam- The corresponding threshold values can be computed ple a loop which may cause multiple visits of a hotspot in a automatically if they are not explicitly formulated as workflow, whereas the context variables may have changed KPI constraints, which is discussed below. Again, con- meanwhile. Such problems and solution approaches, for in- cerned places and transitions are kept for analysis. stance creating a separate training instance for each loop execution, are discussed, e.g., in [15]. 3. Non-conformance to execution constraints: SCIFF Having the training set for a machine learning classifier at or LTL constraints can be checked on the instances logs hand, established algorithms like C4.5 decision tree [14] or using approaches from [5] resp. [17] with respect to rule learners [6, 11] can be applied. In fact recent research their violation. The employment of constraint check- mostly favors decision trees for presenting mining results to ing allows for a very broad range of non-conformance the business user [18]. However, we have tested the C4.5 types being checked. Three of the most important ones decision tree learner on a real-world dataset (see Section 4) are: and found its results not interpretable for the business user to draw any reasonable conclusions from it mainly due to • The violation of KPIs by the use of time-related the size and complexity of the overall decision tree. Despite constraints (for example, task B has to be exe- ex-post global optimization heuristics in C4.5, local feature cuted 1h after task A latest). selection often leads to redundant splits in the initial decision trees. As rules can only be extracted one-by-one along paths • The deviation from expected routing decisions (for in the decision tree [11], they are of rather less use for di- example if orderValue>10.000 in a sales order, al- rectly extracting conditions for use in adaptation rules that ways choose the “priority shipment” branch after might eventually tackle the problematic situation at work- an exclusive gateway). flow runtime. The problem with established rule learners • Data- or organizational incompliance like the vi- like RIPPER [6] in turn is that they generate ordered rule- olation of the “four-eyes principle” for some tasks. lists, which means each rule in the list covers only those 51 learning instances which are not covered by the previous was conducted only after another task already was executed. rule. This characteristic makes the corresponding output Combining these information types, we would identify the rules also hard to read and interpret for an end user. Po- validation task as a “hot spot” in the process. tential relief consists in the employment of a fuzzy learning For our first analysis purpose however, we have concen- approach which generates globally valid rules that have a trated on the decision whether a request has been staffed or probabilistic certainty factor to hold on the dataset or not. not. Following [15], we turn the decision into a binary classi- We are currently evaluating a novel algorithm [13] w.r.t. fication problem using a manually selected subset of context the suitability for being employed within our methodology, variables that have occurred while instance execution. The which is subject to discussion in the following section. results are presented in the following. 4.3 Preliminary Results 4. CASE-STUDY Running a C4.5 decision tree (J48 implementation) learner The first feasibility study for our methodology was con- with standard parameters yields a decision tree of size 757 ducted at a large globally operating IT consulting company. with 644 leaves. It is quite obvious that this output type In the following, we report on the input dataset, the realiza- would need a considerable time to be interpreted for a busi- tion of our methodology in the ProM2 framework, and our ness user. Leaving aside the rule learning algorithms for or- preliminary results and findings. dered rule lists, we instead applied the fuzzy rule induction algorithm presented in [13]. Results were very promising, 4.1 Description of the Dataset for example generating the following output (some context The focus of the case study is on a staffing workflow for values changed for anonymization): serving customer and company-internal human resource re- (Remote = Y) and (ReqingSRegion = DUCKBURG) and (ReqType = Project) quests for different type of IT projects. A simplified cor- => class=Branch 4.1 { ROLE_Closed (Not Staffed)/complete } (CF = 0.61) (ReqingSRegion = NA) and (StartDateFlexible = Yes) and responding model in BPMN notation is shown in Figure 3. (ReqingLOB = FS__Consulting) and (CustIndustry = ) => class=Branch 4.1 { ROLE_Closed (Not Staffed)/complete } (CF = 0.71) The first three sequential steps are creating and submitting (Remote = N) and (ContractType = ) and (CustIndustry = UTILITIES) and (JobText = B) and (Requestor = ABC) and (StartDateFlexible = No) the request and then having it validated by an authorized => class=Branch 4.1 { ROLE_Closed (Not Staffed)/complete } (CF = 0.53) person. Resources can be found by three different strategies: (Remote = ) => class=Branch 4.2 { ROLE_Staffed/complete } (CF = 0.73) (Remote = Y) => class=Branch 4.2 { ROLE_Staffed/complete } (CF = 0.7) by company-internal broadcasts, by external broadcasts to (ReqingSRegion = GOTHAM_CITY) => class=Branch 4.2 { ROLE_Staffed/complete } (CF = 0.72) (StartDateFlexible = No) => class=Branch 4.2 { ROLE_Staffed/complete } (CF = 0.72) partner consulting companies or by directly contacting a po- tentially suitable resource. After at least one such search Manual inspection of the instances characterized e.g. by procedure has been triggered, different reactions can occur, the first two rules immediately showed that they in fact con- namely the acceptance, rejection, withdrawal or feedback of stitute problematic situations in the staffing workflows. In a non-availability for a particular resource. At anytime during flexible WfMS according to Section 2, these conditions could these search procedures, an initial proposition of currently now be reused as a condition for a variant rule with the click gathered resources can be made to the customer. After the of a button, for example inserting addtional activities in the request is closed, it is marked as either successfully or not workflow to handele the problematic situation or not even staffed. The input dataset consisted of 13225 workflow in- trying specific activities because of potential waste of time. stance logs each with up to 50 data context variable values attached. In this case, context variables concern for example 5. OPEN CHALLENGES the country a request is sent from, the concerned industry For a better overview and to motivate future work in this profile or the overall duration of the project. area, the main challenges we experienced while setting up 4.2 Realizing the Methodology based on ProM the mining pipeline are briefly recapitulated: For some basic analysis techniques, we rely on functional- • A petri net conversion most useful for mining purposes ity provided by ProM. The translation of the BPMN model has to be determined, as straight-forward mappings into a petri net was done manually, as automated mapping have problems with more advanced BPMN constructs approaches still generated too complex results which could or generate valid but overcomplex petri nets. make first mining and analysis efforts more difficult. The • The accumulation and aggregation of hot spots from resulting petri net is shown in the upper middle of Figure 4. the petri net-based and especially the constraint-based Black boxes indicate “silent” transitions which do not corre- checking methods has to be defined in more detail. spond to any task in the BPMN model. On the left upper This challenge is connected to linking back hot spots side, one of the additional constraints provided by the con- to the BPMN model for further investigation. sulting company for its staffing workflows is shown, i.e. that before or at least in parallel to an external broadcast, there • The conversion of hot spots to a classification prob- should also be an internal broadcast trying to gather the lem has to be advanced w.r.t. problematic control-flow required resources. The lower left window shows the evalu- structures as for example loop or special joins. ation results of these rules. In the right window, the petri • For the classification problem, the selection of context net-based bottleneck analysis indicates an overproportional variables and algorithm parameters has to be made waiting time between request submission and request vali- accessible for a business user. Experiments also showed dation (concrete values in the figure have been changed for that the rule output may vary significantly w.r.t. the anonymization purposes). In the lower middle window, we predicates used in the rules. We have to find a way see an instance marked with a conformance issue, namely for stabilizing the rule output, e.g. by modifying the that the request validation sometimes has been left out or learning algorithm w.r.t. this goal and not only taking 2 prediction accuracy into account. http://www.promtools.org/prom5/ 52 6. RELATED WORK 8. REFERENCES Due to space restrictions, we do not cover the broad range [1] Business Process Model and Notation (BPMN) - of general process mining approaches in this section, but Version 2.0 11-01-03, 2011. rather elaborate on selected approaches which tackle the is- [2] L. Bodenstaff, A. Wombacher, M. Reichert, and M. C. sue of dependency- or constraint-extraction in workflow logs: Jaeger. Monitoring Dependencies for SLAs: The The authors of [15] present the idea of decision point min- MoDe4SLA Approach. SCC’08, pages 21–29, 2008. ing in workflows by translating a routing decision into a [3] M. Castellanos, F. Casati, U. Dayal, and M.-C. Shan. classification problem for machine learning. In this work, A Comprehensive and Automated Approach to we generalize this idea also for problem domains in work- Intelligent Business Processes Execution Analysis. flow execution like bottlenecks or general rule compliance. DAPD, 16(3):239–273, Nov. 2004. In [18], a pipeline for analyzing influential factors of business [4] F. Chesani, E. Lamma, P. Mello, M. Montali, process performance is presented. Some of the steps resem- F. Riguzzi, and S. Storari. Exploiting Inductive Logic ble that of our approach, however e.g. decision trees are Programming Techniques for Declarative Process used for dependency analysis. The approach is evaluated on Mining, pages 278–295. Springer, 2009. a simulated dataset. As we have motivated, decision trees [5] F. Chesani, P. Mello, M. Montali, F. Riguzzi, and are rather unsuited for direct extraction of globally valid S. Storari. Compliance Checking of Execution Traces “hot-spot” conditions for a business user on real-world data. to Business Rules. In BPM’08 Workshops, pages An approach for learning constraints for a declarative work- 129—-140, Milan, 2008. Springer. flow model is presented in [4], however focusing on control- [6] W. W. Cohen. Fast Effective Rule Induction. In flow constraints and neglecting data-dependencies. In [3], ML’95, pages 115—-123, 1995. related to HP’s solution for business operation management, an overview on the suitability of different mining techniques [7] P. Dadam and M. Reichert. The ADEPT Project: A for specific analysis types are discussed. Rule extraction Decade of Research and Development for Robust and is mentioned, but only as rules derived from decision trees Flexible Process Support. CSRD, 23(2):81–97, 2009. which as discussed may get too complex for our purposes. [8] R. M. Dijkman, M. Dumas, and C. Ouyang. The approach in [2] focuses on dependencies of service-level Semantics and Analysis of Business Process Models in agreements for service compositions and analyzes reasons for BPMN. IST, 50(12):1281—-1294, 2008. SLA violations. In contrast to our approach, where depen- [9] M. Döhring and B. Zimmermann. vBPMN: dencies are extracted from historic data, the dependencies Event-Aware Workflow Variants by Weaving BPMN2 in [2] are identified at design time for later comparison with and Business Rules. In EMMSAD’11, London, 2011. monitoring results at runtime. Springer. [10] M. Döhring, B. Zimmermann, and L. Karg. Flexible Workflows at Design- and Runtime using BPMN2 Adaptation Patterns. In BIS’11, Poznan, 2011. Springer. 7. CONCLUSION [11] E. Frank and I. H. Witten. Generating Accurate Rule We motivated the need for automated extraction of con- Sets Without Global Optimization. In ICML’98, dition constraints for problematic “hot spots” in workflows Madison, 1998. by the initial uncertainty of a modeler when introducing a [12] P. Hornix. Performance Analysis of Business Processes flexible WfMS and by rapidly changing impact factors on through Process Mining. (January), 2007. workflow execution performance. Existing approaches for [13] J. Hühn and E. Hüllermeier. FURIA: an algorithm for data dependency extraction have turned out not to deliver unordered fuzzy rule induction. DMKD, conveniently interpretable results on real-world datasets and 19(3):293–319, Apr. 2009. were considered generally hard to employ for business users. [14] J. R. Quinlan. C4.5: Programs for Machine Learning. Therefore in this work we have proposed a methodology Morgan Kaufmann Publishers Inc, 1993. which starts from a BPMN workflow definition with a set [15] A. Rozinat and W. van Der Aalst. Decision mining in of additional template-based constraints and transforms the business processes, 2006. workflow into a petri net for automatic hot-spot discovery [16] A. Rozinat and W. M. P. van der Aalst. Conformance according to rule-conformance, control-flow-conformance and checking of processes based on monitoring real bottleneck detection. The hot-spots in turn are transformed behavior. IS, 33(1):64–95, 2008. into a classification problem for further mining algorithms [17] W. M. P. van der Aalst, H. T. de Beer, and B. F. van which should explain the data-dependencies characterizing Dongen. Process Mining and Verification of the problem. One key differentiator to other approaches Properties. In OTM Conferences (1), pages 130—-147, is the use of a fuzzy rule induction approach, which deliv- Agia Napa, 2005. Springer. ers globally valid and interpretable rules. Our approach es- [18] B. Wetzstein, P. Leitner, F. Rosenberg, I. Brandic, pecially aims at providing the corresponding conditions for S. Dustdar, and F. Leymann. Monitoring and reuse in adaptation rules which improve the overall workflow Analyzing Influential Factors of Business Process performance by circumventing critical situations. Performance. EDOC’09, pages 141–150, 2009. However, some integration steps between the phases of our [19] P. Wolf, C., Harmon. The State of Business Process methodology, like a BPMN to petri net translation suitable Management 2010, 2010. for mining purposes, the aggregation of problem situations to hot-spots or the guided parameter selection for the rule mining algorithm remain subject to future work. 53 IF dockyardStation==Hamburg THEN APPLY NonFailableTimedHandler(measurements, time=12h, handlerTask=ResetDevices) <