[dbis logo]

.Lehre.Semesterübersicht
[Institut fuer Informatik] [Leerraum] [Humboldt-Universitaet zu Berlin]

Forschungsseminar: Neue Entwicklungen im Datenbankbereich

Dieses Seminar wird von Mitgliedern der Lehr- und Forschungseinheit als Forum der Diskussion und des Austauschs genutzt. Studierende und Gäste sind herzlich eingeladen.

 

Das Seminar findet in RUD25, Raum 3.113 statt.

Termine

Datum Beginn Vortragende(r) Titel
31.10.2011 9:30 Uhr Matthias Sax, Martin Kost Adaptive Optimization of Data-Flow Programs in a Distributed Environment, "Privacy-aware Data Processing"
14.11.2011 9:30 Uhr Alexander Pospiech "N-way Joins in einer massiv parallelen Datenverarbeitungsumgebung"
21.11.2011 9:30 Uhr Prof. Johann-Christoph Freytag, Matthias Sax Eindrücke von der VLDB 2011
28.11.2011 9:30 Uhr Jan Hendrik Nielsen "Veröffentlichung medizinischer Daten in verteilten Datenbanken"
05.12.2011 9:30 Uhr Steffen Zeuch "Konzept und Implementierung einer Zugriffsunterstützung für Daten mit geringer Nutzungsfrequenz in einer In- Memory-Datenbank"
19.12.2011 9:30 Uhr Dennis Schnieder "Konkurrierende Ausführung von Join-Algorithmen in Stratosphere"
16.01.2012 9:00 Uhr Robert Przewozny "Parallele Datengenerierung als Lasttest für Stratosphere"
23.01.2012 9:30 Uhr Martin Kost "Privacy Analysis using Ontologies"
30.01.2012 9:30 Uhr Raffael Dzikowski "A Formal Perspective on Stratosphere PACTs"
06.02.2012 9:30 Uhr Martin Filip "Fusion von Massenspektren zur verbesserten Peptidsequenzierung"
20.02.2012 9:30 Uhr Raffael Dzikowski "SECONDO - An Extensible Database System"
27.02.2012 9:30 Uhr Matthias Sax "PACT Rewriting"
19.03.2012 9:30 Uhr Fabien Fier "Analysis of Sensor Data with the PACT Programming Model"
02.04.2012 9:30 Uhr Martin Kost, Matthias Sax Privacy-aware Data Processing, "Processing Continuous Input Data with Stratosphere"

Zusammenfassungen

"N-way Joins in einer massiv parallelen Datenverarbeitungsumgebung" (Alexander Pospiech)

Diese Studienarbeit beschäftigt sich mit der Theorie und Praxis von Nway Joins in massiv parallelen Datenverarbeitungssystemen. In diesem Fall auf der Ausführungsumgebung Nephele, einer massiv parallelen Datenfluss-Verarbeitungsumgebung. Die bekannten Varianten von N-way Joins sind hier de niert als Operatoren die Join-Bäume mit binären Joins beliebiger Relationen und Attribute erzeugen und verarbeiten. Für die Bildung von Join-Bäumen müssen Metriken und Heuristiken benutzt werden um möglichst optimale Anfragepläne zu erstellen. Es müssen Entscheidungen über Reihenfolgen der binären Joins und im Falle der buschigen Join-Bäume auch über Parallelität getro en werden In jedem Fall gehen durch diese Entscheidungen Freiheitsgrade verloren. Diese Freiheitsgrade sollen mit Hilfe von zu implementierenden Joinalgorithmen wiedergewonnen werden. Der Aspekt der Verteilung wird von der Ausführungsumgebung sichergestellt. Die Algorithmen sollen unter anderem die Möglichkeiten von Mehrkernprozessoren ausnutzen und insbesondere bei feingranulierten, unabhängigen Teilaufgaben eine hohe Datenparallelität ermöglichen. Ein Algorithmus wird auf Basis des Sort-Merge-Algorithmus implementiert, ein anderer auf Basis von Snapshots der Daten sowie Algorithmen auf Basis des Hashjoins, wobei insbesondere Varianten des Symmetric-Hash-Joins entwickelt werden. Die Studienarbeit beschränkt sich auf 3-Wege Joins. Zur Evaluation wird die Performance der Algorithmen gemessen und mit Varianten von z.b. Hash-Join-Bäumen verglichen.

Veröffentlichung medizinischer Daten in verteilten Datenbanken (Jan Hendrik Nielsen)

Diese Studienarbeit beschäftigt sich mit dem Schutz von sensiblen Daten in einer verteilten Service-Infrastruktur unter Verwendung von etablierten Standard-Webservices. Da in medizinischen Systemen viele personenbezogene Daten gespeichert werden, erfährt das Thema Datenschutz im Gesundheitswesen eine breite öffentliche Wahrnehmung. Durch die zunehmende Erhebung digitaler, medizinischer Daten entstehen neue Risiken für den Datenschutz. Dies wird insbesondere bei der Veröffentlichung medizinischer Studien ersichtlich. Werden heutzutage medizinische Daten der Öffentlichkeit zugänglich gemacht, so ist es üblich diese zu anonymisieren. Zu diesem Zweck werden explizit identifizierende Attribute einer Person, wie der Name und die Adresse, aus der Veröffentlichung entfernt. Jedoch bietet dieses Vorgehen nur eine trügerische Sicherheit, denn die sensiblen Daten können der betreffenden Person trotz Anonymisierung mittels zusätzlichem Wissen wieder zugeordnet werden. Diese Arbeit integriert bekannte Methoden zur Datenanonymisierung in eine Studiendatenbank, welche sich an der Berliner Altersstudie II (BASE II) orientiert. Die BASE II ist ein Forschungsprojekt, welches die körperliche und geistige Gesundheit über die Lebensspanne eines Menschen untersucht. Die Daten werden unter Benutzung von bestehenden Standard-Komponenten der Amazon Webservices in einer verteilten Service-Infrastruktur gespeichert und durch eine Service-Schnittstelle zur Verfügung gestellt. Die Service-Schnittstelle wurde um eine Datenschutzkomponente erweitert, welche trotz möglicher Kompromittierung einer Teilkomponente eine zuverlässige Anonymität der Daten gewährleistet.

Konzept und Implementierung einer Zugriffsunterstützung für Daten mit geringer Nutzungsfrequenz in einer In- Memory-Datenbank (Steffen Zeuch)

Diese Thesis beschäftigt sich mit der Kernfrage, wie eine große Datenmenge im Rahmen der SAP HANA Database mit möglichst geringem Hauptspeicherverbrauch gespeichert und verwaltet werden kann. Den konkreten Anwendungsfall stellen die sog. kalten Daten eines SAP BW Systems dar. Diese werden vor allem durch eine geringe Zugriffsfrequenz und ein hohes Datenvolumen charakterisiert. Die reine In-Memory Speicherung dieser Daten würde zu einem enormen Hauptspeicherbedarf führen, den nicht jeder SAP Kunde bereit ist zur Verfügung zu stellen. Aus diesem Grund wird zu Beginn untersucht, ob sich durch die Wiederverwendung oder Migration der vorhandenen Komponenten der SAP HANA Database eine mögliche Problemlösung ergeben würde. Aus dieser Untersuchung ging allerdings hervor, das ohne zusätzlichen Entwicklungsaufwand keine zufriedenstellende Lösung erreicht werden konnte. Daher wurden vier Lösungsvarianten erarbeitet, diskutiert und eine von diesen für die Implementierung ausgewählt. In dieser Variante wird die sog. D Tabelle durch einen bereits vorhanden B* Baum als Index und einem neu entwickelten Container für die Datenablage realisiert. Die D Tabelle bildet die logische Klammer um diese beiden Komponenten und stellt an ihrem Interface Methoden bereit, um die Datensätze zu modifizieren. Die D Tabelle erfüllte zu Projektende einen Großteil der an sie gestellten Anforderungen und konnte darüber hinaus bereits einige optionale Anforderungen späterer Versionen integrieren. Der Zugriff über die SQL Schnittstelle der SAP HANA Database wurde aus Zeitgründen nicht implementiert, wodurch auf die D Tabelle am Projektende lediglich intern zugegriffen werden konnte.

Konkurrierende Ausführung von Join-Algorithmen in Stratosphere (Dennis Schneider)

Die Studienarbeit beschäftigt sich mit der Implementation eines dynamischen Wechsels von Join-Algorithmen während der Anfrageausführung im Foschungsprojekt Stratosphere:
Bislang unterstützt Stratospheres Match-Operator nur die Ausführung eines vorher festgelegten Join-Algorithmus. Wurde ein ungeeigneter Algorithmus gewählt, wird die Anfrage suboptimal ausgeführt. Deswegen wird ein neuer Operator, CompetingMatch, entworfen und implementiert. Im Untschied zum Match-Operator wählt dieser Operator den für die konkreten Eingabedaten geeigneteren aus zwei Join-Algorithmen aus, welche vorher angegeben werden. Dafür werden beide Algorithmen auf einem kleinen Teil der Eingabedaten parallel ausgeführt. Der geeignetere verarbeitet anschließend die restlichen Daten.
Basierend auf der Diplomarbeit von Matthias Sax wird der in Stratosphere implementierte Hash-Join erweitert, um vom CompetingMatch-Operator benutzt werden zu können: Er kann nach der Wettbewerbsphase entweder abgebrochen werden oder ihm können die restlichen Daten zur Berechnung des vollständigen Join-Ergebnisses übertragen werden. Abschließend wird der zusätzliche Aufwand durch die kurze Wettbewerbsphase und die Kapselung in den neuen Operator durch Benchmarks beziffert. Dafür wird die Laufzeit eines einfachen PACT-Programms mit nur einem Join (Hash-Join / erweiterter Hash-Join) auf verschiedenen Eingabedaten gemessen.

Parallele Datengenerierung als Lasttest für Stratosphere (Robert Przewozny)

Das Ziel dieser Studienarbeit ist die Einbettung einer existierenden Lösung zur parallelen Datengenerierung in die verteilte Ausführungseinheit Nephele. Anders als in der momentanen Umsetzung soll die Erzeugung von Testdaten nicht entkoppelt von der Durchführung eines Tests erfolgen, indem etwa zuvor erstellte Dateien als Eingabe verwendet werden. Stattdessen soll die Datengenerierung ebenfalls in die Cloud verlagert werden und so als Bestandteil eines Nephele-Jobs von der einfachen Verteilung und dem flexiblen Scheduling des Systems profitieren. Während eines Lasttests soll der Durchsatz eines Tasks nicht mehr durch die I/O-Geschwindigkeit beim Auslesen von Dateien begrenzt sein, sondern von den Optimierungen des Systems abhängen, wie etwa dem Einsatz eines schnellen Netzwerk- oder Interprozess-Kanals vom erzeugenden zum konsumierenden Task. Zusammen mit der Möglichkeit, die Geschwindigkeit der Datengenerierung während eines Testdurchlaufs zu variieren, soll so ein besserer Realitätsbezug von Benchmarks erreicht werden.

Privacy Analysis using Ontologies (Martin Kost)

As information systems extensively exchange information between participants, privacy concerns may arise from potential misuse. Existing design approaches consider non-technical privacy requirements of different stakeholders during the design and the implementation of a system. However, a technical approach for privacy analysis is largely missing.

This paper introduces a formal approach for technically evaluating an information system with respect to its designed or implemented privacy protection. In particular, we introduce a system model that describes various system aspects such as its information flow. We define the semantics of this system model by using ontologies. Based on the system model together with a given privacy ontology, and given privacy requirements we analyze the modeled system to detect privacy leakages and to calculate privacy indicators. The proposed method provides a technical approach to check whether a system conforms to the privacy requirements of the stakeholders or not.

A Formal Perspective on Stratosphere PACTs (Raffael Dzikowski)

Gegenstand dieser Studienarbeit ist eine Betrachtung der Stratosphere PACTs aus dem Blickwinkel der funktionalen Programmierung; einem Gebiet, dem einige der darin verwendeten Konzepte ursprünglich entstammen, sowie eine formale Festlegung ihrer Semantik. Zu diesem Zweck werden zunächst alle PACTs in einer funktionalen Programmiersprache (Haskell) ausgedrückt. In einem nächsten Schritt dient die Haskell-Implementation, aus der bereits eine bestimmte Semantik hervorgeht, als Grundlage für eine Formulierung der PACT Semantik in mathematischer Form.

Das übergeordnete Ziel, wofür diese Studienarbeit einen Grundstein legt, ist die Analyse der algebraischen Eigenschaften von PACTs, da diese einen Beitrag zur Anfrageoptimierung leisten können. Im Rahmen des Vortrages werden exemplarisch einige dieser Eigenschaften vorgestellt. Auch wird eine kurze Einführung in funktionale Programmierung am Beispiel von Haskell gegeben.

Fusion von Massenspektren zur verbesserten Peptidsequenzierung (Martin Filip)

Das DBnovo-Projekt ist Gegenstand einer interdisziplinären Zusammenarbeit der Institute Chemie und Informatik der HU-Berlin. Zielstellung dieses Projektes ist die Sequenzierung von Peptiden in komplexen Peptidgemischen. Die spezifische Abfolge einzelner Aminosäuren ist für jedes Peptid charakteristisch. Ziel ist es, die Abfolge der Aminosäuren zu ermitteln. Per Massenspektrometrie wird ein Peptid durch Bindungsbrüche zwischen den Aminosäuren in kleinere Fragmente zerteilt und deren "Masse zu Ladungsverhältnis" gemessen. Jedes Fragment erzeugt in dem Fragmentspektrum ein Signal, das die Intensität des gemessenen "Masse zu Ladungsverhältnisses" wiedergibt.

Bei einer einzelnen Messung entstehen in der Regel nicht alle nötigen Signale. Daher werden die Messungen mehrfach vorgenommen. Die resultierenden Spektren werden fusioniert, ihre relevanten Signale identifiziert und die Massendifferenzen zwischen ihnen berechnet. Da alle Aminosäuren eine spezifische Masse besitzen, lassen sich aus den Massendifferenzen die Aminosäuren bestimmen. Aus den Daten wird ein Graph aufgebaut. Jeder Knoten steht für einen Signal, jede Kante zwischen zwei Knoten steht für genau eine Massendifferenz und damit für Kompositionen von Aminosäuren. Mit Hilfe effizienter Suchstrategien werden in dem Graph die wahrscheinlichsten Sequenzen ermittelt und ausgegeben. Im Ergebnisteil werden die Ergebnisse des Fusionsansatzes mit denen der Einzelmessungen verglichen und eine Verbesserung der Peptidsequenzierung nachgewiesen.

SECONDO - An Extensible Database System (Raffael Dzikowski)

In diesem Vortrag wird das erweiterbare Datenbanksystem SECONDO vorgestellt, das von der Forschungsgruppe um Herrn Prof. Dr. Ralf Hartmut Güting an der FernUniversität in Hagen entwickelt wurde.

Zu den Besonderheiten des Systems gehören eine saubere, vollständig auf Erweiterbarkeit ausgelegte Architektur sowie eine solide mathematische Grundlage, die einen allgemeinen und einheitlichen Rahmen für Erweiterungen auf zwei verschiedenen Ebenen bietet: Der Ebene der Datentypen und der Ebene des Datenmodells.

Darüber hinaus hat SECONDO die Eigenschaft, dass Anfrageausführungspläne in einer für Menschen lesbaren Form dargestellt werden, so dass die Hauptschritte bei der Anfragebearbeitung eingesehen werden können.

PACT Rewriting (Matthias Sax)

The Stratosphere system provides the PACT programming model to specify data flow programs which can be executed in a massively parallel manner. PACT (Parallelization Contracts) is an extension of the Map/Reduce programming model. Additionally, to the second-order functions Map and Reduce, PACT support the three second-order functions Match, Cross, and CoCroup, which have two inputs instead of just one. Furthermore, PACT programs are DAGs and the second-order functions can be arranged in an arbitrary order.

Both extensions offer the possibility, to express the same task with different PACT programs. Those programs have the same operators, but apply them in different orders to the input data. The runtime characteristics of the program depend on the input data and the order if the operators within the program. Therefore, an optimization problem occurs. Given some input data, what PACT program is the best according to a given cost model? The challenge is the fact, that PACT programs do not have an algebraic specification but execute imperative user-code (first-order functions).

This talk gives an overview of our approach to tackle the challenges. The idea is to derive some semantical information about the first-order function by static code analysis. Hence, the "black-box" user-code is turned into a "grey-box". The derived information is sufficient to detect many re-ordering possibilities within the program without changing the final result. We present re-ordering conditions and rules as well as formal proofs about their correctness. Additionally, we present an algorithm for static code analysis and enumeration of PACT programs.

The present results are a joined work of Mathias Peters, Rico Bergmann, Matthias Sax, Astrid Rheinländer, Fabian Hüske, and Kostas Tzoumas.

Analysis of Sensor Data with the PACT Programming Model (Fabian Fier)

Wireless and wired communication networks are a highly discussed research topic. In the Humboldt-Wireless-Lab project a wireless network is set up for experimental studies. The used network nodes are designed to collect network data for further statistical evaluation. Additionally, some nodes are equipped with seismographic sensors in order to collect seismographical data. In this seminar paper we follow up with seismographic data.

The Clickwatch framework which is written in Java was developed in order to retrieve and analyze the data from the nodes. On the nodes, the Click API is used as a standard interface.

To investigate the applicability of the collected data to forecast earthquakes an experiment was designed. Every 10 milliseconds acceleration data is measured in three dimensions by the network nodes. Afterwards the method of Moving Average and Fourier Transformation is computed on the seismographic data sets per node per dimension. The Moving Average takes the window size x as parameter. It gets computed by the sum of the preceding x values divided by x. With the help of this method, the data is normalized. The Fourier Transformation is used to highlight the occurrence of relevant frequencies and to gain a visual impression of the empirical distribution of the data.

The Stratosphere project facilitates a dedicated programming model PACT, which advances the Map-Reduce model. Stratosphere implements a framework using the cloud computing paradigm. The architecture of the framework consists of multiple layers of execution. On the lowest level, Nephele executes directed acyclic graphs that represent parallelizable dataow programs. On top, PACT is used as an interface to write those programs. PACT programs are compiled for the further execution by Nephele.

In the experiment on seismographic data of the Humboldt Wireless Lab huge amounts of data arise, roughly 20 MB per minute per node. An analysis involves complex computations of the sensor-time signals. Using a single machine for a large amount of nodes over a long period of time is not feasible, because the computations might run for hours or even days. One way to accelerate these analyses is parallelization. The computations can be divided by nodes or by time. Each part of the data can be processed independently. This approach is called data parallelization.

In this seminar paper we utilize Stratosphere for the analysis part of the described Clickwatch experiment. We port the existing use case from Clickwatch into one or more PACT programs. The seminar paper includes a system description of parallelization with PACT. Additionally, the use case of Clickwatch is introduced. The porting of the use case into PACT is described and arising problems are discussed. Finally, different implementation possibilities are compared.



[Punkt]  Sommersemester 2019

[Punkt]  Wintersemester 2018/19

[Punkt]  Sommersemester 2018

[Punkt]  Wintersemester 2017/18

[Punkt]  Sommersemester 2017

[Punkt]  Sommersemester 2016

[Punkt]  Wintersemester 2015/16

[Punkt]  Sommersemester 2015

[Punkt]  Wintersemester 2014/15

[Punkt]  Sommersemester 2014

[Punkt]  Wintersemester 2013/14

[Punkt]  Sommersemester 2013

[Punkt]  Wintersemester 2012/13

[Punkt]  Sommersemester 2012

[aktiver Punkt]  Wintersemester 2011/12

[Punkt]  Sommersemester 2011

[Punkt]  Wintersemester 2010/11

[Punkt]  Sommersemester 2010

[Punkt]  Wintersemester 2009/10

[Punkt]  Sommersemester 2009

[Punkt]  Wintersemester 2008/09

[Punkt]  Sommersemester 2008

[Punkt]  Wintersemester 2007/08

[Punkt]  Sommersemester 2007

[Punkt]  Wintersemester 2006/07

[Punkt]  Sommersemester 2006

[Punkt]  Wintersemester 2005/06

[Punkt]  Sommersemester 2005

[Punkt]  Wintersemester 2004/05



Ansprechpartner