<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>Slicing in Assistenzsystemen</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Hannes Grunert</string-name>
          <xref ref-type="aff" rid="aff1">1</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Andreas Heuer</string-name>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>Lehrstuhl für Datenbank- und, Informationssysteme, Universität Rostock</institution>
          ,
          <addr-line>18051 Rostock, ah(at)informatik.uni-rostock.de</addr-line>
        </aff>
        <aff id="aff1">
          <label>1</label>
          <institution>Lehrstuhl für Datenbank- und, Informationssysteme, Universität Rostock</institution>
          ,
          <addr-line>18051 Rostock, hg(at)informatik.uni-rostock.de</addr-line>
        </aff>
      </contrib-group>
      <pub-date>
        <year>1896</year>
      </pub-date>
      <fpage>24</fpage>
      <lpage>29</lpage>
      <abstract>
        <p>ACM Klassifikation Zwei Kernaspekte des Datenschutzes sind Datensparsamkeit und Datenvermeidung. §3a des Bundesdatenschutzgesetzes [1] definiert diese als Forderung, dass Informationssysteme möglichst wenig personenbezogene Daten erheben, verarbeiten oder nutzen sollen. Dies betrifft neben der Konzeption von Informationssystemen auch den Prozess der Datenverarbeitung. Assistenzsysteme sollen den Nutzer bei der Bewältigung seines Alltags, sei es im Beruf oder zu Hause, unterstützen. Über verschiedene Sensoren, wie Bewegungssensoren und Wärmemessgeräte, werden Informationen über die momentane Situation und die Aktivitäten des Anwenders gesammelt. Diese Daten werden im System gespeichert und mit weiteren Informationen, beispielsweise dem Nutzerprofil eines sozialen Netzwerkes verknüpft. Aus den so gewonnenen Informationen lassen sich Verhaltensmuster, Präferenzen und zukünftige Ereignisse ermitteln. Auf Basis dieser Daten reagiert das Assistenzsystem eigenständig auf die Bedürfnisse des Nutzers und regelt Raumtemperatur, Lüftung und weitere vernetzte Geräte. Assistenzsysteme sammeln häufig wesentlich mehr Informationen als sie für die Ausführung ihrer Funktionen benötigen. Der Nutzer hat dabei meist keinen oder nur einen unwesentlichen Einfluss auf die Speicherung und Verarbeitung seiner personenbezogenen Daten. Dadurch ist sein Recht auf informationelle Selbstbestimmung verletzt. Die Einführung von Datenschutzmechanismen wird seitens der Entwickler von Assistenzsystemen skeptisch angesehen. Es wird befürchtet, dass durch die Anonymisierung der Daten die Entwicklung des Systems zurückgeworfen wird. Durch die Anonymisierung bzw. Pseudonymisierung der Nutzerdaten gehen Detailinformationen verloren, wodurch Analysefunktionen ungenauere Ergebnisse zurückliefern und im Extremfall unbrauchbar werden. Im Rahmen des Graduiertenkollegs MuSAMA1 werden Datenschutzkonzepte für die Anfrageverarbeitung in Assistenzsystemen entworfen. Diese werden allerdings nicht ontop auf die bestehenden Analysefunktionen aufgesetzt, sondern in enger Zusammenarbeit während der Entwicklung integriert. Ein Beispiel für dieses Zusammenwirken ist die Umsetzung des Slicing-Konzeptes von Li et al. [10] zusammen mit der Regressionsanalyse [6] auf hochdimensionalen Sensordaten.</p>
      </abstract>
      <kwd-group>
        <kwd>Datenbanken</kwd>
        <kwd>Datenschutz</kwd>
        <kwd>Datensparsamkeit</kwd>
      </kwd-group>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>Kurzfassung</title>
      <p>Datenschutz stellt eine große Herausforderung für die
Entwicklung von Informationssystemen dar. Obwohl
viele Konzepte zur Wahrung des Datenschutzes
bestehen, werden Datenschutztechniken in der Regel nicht in
Datenbankmanagement- und Assistenzsysteme integriert.</p>
      <p>In diesem Artikel stellen wir eine SQL-Implementierung
des Slicing-Konzeptes von Li et al. [10] vor. Es erfolgt eine
detaillierte Betrachtung hinsichtlich der Parametrisierung
des Algorithmus und dessen Auswirkung auf
Informationsverlust und Grad des Datenschutzes.</p>
    </sec>
    <sec id="sec-2">
      <title>Stichworte</title>
    </sec>
    <sec id="sec-3">
      <title>EINLEITUNG</title>
      <p>1.1</p>
    </sec>
    <sec id="sec-4">
      <title>PArADISE</title>
      <p>Für die Umsetzung von Datenschutzrichtlinien in
smarten Umgebungen wird derzeit das PArADISE2-Framework
[7] entwickelt, welches insbesondere die Aspekte der
Datensparsamkeit und Datenvermeidung in heterogenen
P2PSystemen realisieren soll.</p>
      <p>PArADISE ist Werkzeug, welches den Entwicklern und
Nutzern von Assistenzsystemen helfen soll effizient und
datenschutzkonform Anfragen auf Sensordaten zu formulieren.
Der Kern des Frameworks ist ein datenschutzfreundlicher
1Multimodal Smart Appliance Ensembles for Mobile
Applications
2Privacy-Aware Assistive Distributed Information System
Environment
Anfrageprozessor (siehe Abbildung 1). Dieser Prozessor
erhält als Eingabe zum einen die Datenschutzeinstellungen der
Nutzer, zum anderen den Informationsbedarf des Systems
anhand von Anfragen an das Datenbanksystem. Als
Ausgabe wird ein anonymisierter, annotierter Teil des
Datenbestandes zurückgeliefert. In den Annotationen wird
angegeben, wie der Datenbestand anonymisiert wurde und ob
bereits die erforderlichen Analysen der Daten auf dem
ausführenden Knoten umgesetzt wurden. Falls keine Analyse
durchgeführt wurde, muss der Knoten, welcher das Ergebnis
erhalten hat, die weitere Verarbeitung der Daten
übernehmen.</p>
      <p>Der Anfrageprozessor arbeitet in zwei Stufen. Ziel der
ersten Stufe, der Vorverarbeitungsphase, ist die Modifikation
der eingehenden Anfragen, sodass möglichst wenige Daten
aus der Datenbank ausgelesen werden. Dazu wird die
Anfrage analysiert. Durch die Analyse lässt sich erkennen, welche
Attribute angefragt werden, wie diese hinsichtlich ihres
Wertebereichs gefiltert und ggf. aggregiert und gruppiert
werden.</p>
      <p>Die so erhaltenen Informationen über die Anfrage werden
mit den vorformulierten Privatheitsansprüchen [4] des
Nutzers verglichen. Treten an dieser Stelle Widersprüche auf,
wie beispielsweise der Zugriff auf ein Attribut, welches der
Nutzer nicht von sich preisgeben möchte, wird die Anfrage
angepasst. Dabei werden verschiedene Techniken, wie
Anfrageumschreibungen und Abbildungen auf Sichten,
angewandt.</p>
      <p>In der Nachverarbeitungsphase erfolgt, sofern
erforderlich, die Anonymisierung der Daten. Dabei wird überprüft,
ob spezielle Kriterien wie k-Anonymität [11] zutreffen.
Anschließend erfolgt die Anonymisierung der Daten unter
Berücksichtigung des Grades der benötigten Anonymität und
des Informationsverlustes [8] zur Wahrung von
Funktionalität und Datenschutz.</p>
      <p>Durch die Vorverarbeitung der Anfrage müssen weniger
Daten in der Nachverarbeitungsphase anonymisiert werden.
Dadurch erfolgt nur eine geringe Erhöhung der Antwortzeit
auf die Anfrage.
1.2</p>
    </sec>
    <sec id="sec-5">
      <title>Laufendes Beispiel</title>
      <p>Die Umsetzung des Slicing-Konzeptes wird in diesen
Artikel anhand eines laufenden Beispiels erläutert. Für die
Implementation und Evaluation des Algorithmus wurde die
Adult-Relation aus dem UCI Machine Learning
Repository [9] verwendet. Die Relation besteht aus
personenbezogenen Daten, bei denen Schlüssel sowie Vor- und Nachname
der betroffenen Personen entfernt wurden. Die
verbleibenden 15 Attribute enthalten weitere personenbezogene
Angaben, wie beispielsweise Alter, Ehestand, Staatsangehörigkeit
und Schulabschluss.</p>
      <p>Tabelle 1 zeigt einen Ausschnitt der gesamten Relation. In
diesem Artikel wird gezeigt, wie diese Relation schrittweise
in eine anonymisierte Relation (siehe Tabelle 3) überführt
wird.</p>
      <p>Der Rest des Artikels ist wie folgt strukturiert: Kapitel 2
gibt einen Überblick über das Anonymisierungskonzept von
Li et al. Im folgenden Kapitel gehen wir detailliert darauf
ein, wie das Konzept durch Operationen aus der
Relationenalgebra realisiert werden kann. In Kapitel 4 wird
beschrieben wie die Implementation des Konzeptes in SQL erfolgt.
Kapitel 5 evaluiert den Ansatz anhand des laufenden
Beispiels. Das letzte Kapitel fasst den Beitrag zusammen und
gibt einen Ausblick auf zukünftige Arbeiten.</p>
    </sec>
    <sec id="sec-6">
      <title>2. SLICING</title>
      <p>In [10] stellen Li et al. ein neues Anonymisierungskonzept
vor, welches auf der Permutation von Daten beruht. Im
Gegensatz zu den bisher gängigen Anonymisierungsverfahren
wie k-Anonymität [11] verzichtet dieses Verfahren auf
Generalisierungstechniken.</p>
      <p>Eine Relation ist k-anonym, wenn, auf Basis der
identifizierenden Attributmengen der Relation, ein Tupel von k-1
anderen Tupeln nicht unterscheidbar ist. In der Regel wird
eine Person durch ein Tupel in der Relation dargestellt. In
Assistenzsystemen werden, je nach Anwendungsgebiet, nur
Informationen über eine Person gesammelt. Dies gilt z. B.
bei der Überwachung von Demenzpatienten. Dort lassen sich
mittels der aufgenommenen Daten einzelne Handlungen
einer Person identifizieren. Diese gilt es ebenfalls zu
anonymisieren.</p>
      <p>Bei der Generalisierung von Daten kommen
Detailinformationen abhanden, die bei vielen Analysefunktionen
benötigt werden. Das Slicing-Verfahren verspricht einen höheren
Datennutzen, indem es die Verbindung von stark
korrelierenden Attributen bewahrt. Auf dieser Grundlage ist es
trotz Anonymisierung weiterhin möglich Data-Mining- und
Analyse-Techniken, wie Regressionsanalysen, anzuwenden.</p>
      <p>Das Konzept permutiert nicht den kompletten
Datenbestand, sondern partitioniert die Daten sowohl horizontal als
auch vertikal. Bei der horizontalen Partitionierung (Tuple
Partition) wird der Datenbestand nach festgelegten
Filterkriterien (Selektion nach einem bestimmten Attribut,
Anzahl an Partitionen, ...) in mehrere Mengen von Tupeln
zerlegt.</p>
      <p>Die vertikale Partitionierung (Attribute Partition)
unterteilt den Datenbestand spaltenweise, indem aus der
vorhandenen Attributmenge mehrere kleine Attributmengen
gebildet werden. Eine mögliche vertikale Zerlegung besteht im
Aufteilen der Attribute eines Quasi-Identifikators [2] auf
mehrere Partitionen.</p>
      <p>Aus einem Datenbestand der durch n horizontale und m
vertikale Partitionsvorgaben zerteilt wird, entsteht ein
Raster aus n*m kleineren Relationen. Jede dieser Teilrelationen
wird anschließend permutiert, indem die Reihenfolge der
Tupel vertauscht wird. Die permutierten Relationen werden
anschließend wieder zu einer einzelnen Relation verknüpft.
3.</p>
    </sec>
    <sec id="sec-7">
      <title>UMSETZUNG IN DER RELATIONALEN</title>
    </sec>
    <sec id="sec-8">
      <title>ALGEBRA</title>
      <p>Für das Slicing-Konzept wird von Li et al. eine grobe
Methodik für die Implementierung vorgestellt. In diesem
Abschnitt demonstrieren wir die Adaption des Verfahrens auf
die relationale Algebra. Konkrete Implementierungsdetails
werden im nachfolgenden Kapitel vorgestellt.
3.1</p>
    </sec>
    <sec id="sec-9">
      <title>Schritt 1: Horizontaler Split</title>
      <p>Im ersten Schritt wird die Relation R in n disjunkte
Partitionen R1, ..., Rn zerlegt. Für jede Partition Ri wird eine
Selektionsbedingung ci angegeben, welche die Tupel aus R
den Partitionen zuordnet:</p>
      <p>R1 := σ c1 (R), ..., Rn := σ cn (R).
(1)
Abbildung 1: Das Konzept des datenschutzfreundlichen Anfrageprozessors
Die Auswahl der Selektionsbedingungen muss dabei
geschickt gewählt werden. Eine Möglichkeit besteht aus der
Selektion nach einem bestimmten Attribut, wobei für jeden
einzelnen auftretenden Attributwert (oder eine Menge von
Attributwerten) eine Selektionsbedingung der Form
attribut = ’Wert’aufgestellt wird. Eine weitere Variante besteht
darin, die Tupel in R zu nummerieren (neues Attribut rank)
und die Selektionen in der Form ’rank between vj and vk’3
zu beschreiben.
3.2</p>
    </sec>
    <sec id="sec-10">
      <title>Schritt 2: Vertikaler Split</title>
      <p>Nachdem die Relation R in mehrere kleinere Relationen
Ri zerlegt wurde, wird jede Ri durch Projektionen weiter
unterteilt. Jede Projektion π attributmengej (Ri) wählt dabei
ein oder mehrere Attribute aus der Relation R aus. Für jede
Partitionen Ri werden dabei die gleichen m Projektionen
angewandt um die m Teilrelationen Rij aus Ri zu bilden:
Ri1 := π attributmenge1 (Ri), ..., Rim := π attributmengem (Ri).
(2)
Die Attributmengen in den Projektionen müssen dabei nicht
zwangsweise disjunkt sein4. Sie dürfen keine identifizierende
Attributmenge enthalten, da ansonsten Rückschlüsse auf die
Identität einer Person gezogen oder Handlungen eindeutig
bestimmt werden können. Die Auswahl der Attributmengen
sollte dabei in Abstimmung mit den Analysefunktionen
getroffen werden, um z. B. stark korrelierende Attribute nicht
3vj , vk nummerische Werte
4Im grundlegenden Algorithmus von Li et al. [10] wird
Disjunktheit vorausgesetzt. Erweiterungen setzen Disjunktheit
nicht voraus.
auf unterschiedliche Partitionen zu verteilen. Die Ermittlung
von identifizierenden Attributmengen, sogenannten
QuasiIdentifikatoren [2], lässt sich mit geringem Aufwand [5] vor
der Anonymisierung realisieren.
3.3</p>
    </sec>
    <sec id="sec-11">
      <title>Schritt 3: Permutation</title>
      <p>Nach der Bildung der Teilrelationen Rij erfolgt die
eigentliche Anonymisierung. Die Permutation erfolgt durch
den Ordnungsoperator τ , welcher die Tupel jeder
Teilrelation sortiert. In Abschnitt 4.2 wird genauer erklärt wie eine
zufällige Sortierung erfolgen kann. Das Resultat der
Permutation wird in der Liste Lij hinterlegt:</p>
      <p>Lij := τ &lt;Attribute&gt;(Rij ).
(3)
An dieser Stelle geschieht ein kleiner Bruch mit der
relationalen Algebra. Der Ordnungsoperator τ darf zwar auf
Relationen angewandt werden, liefert allerdings keine
Relation, sondern eine Liste zurück. τ darf somit nur als letzter
Operator angewandt werden [3]. Dies stellt ein Problem dar,
weil für den Slicing-Algorithmus die permutierten Listen im
letzten Schritt wieder zusammengefügt werden müssen.</p>
      <p>Die Listen müssen entsprechend wieder zurück in
Relationen überführt werden. Um die Ordnung zu bewahren,
wird jedes Tupel mit einer Ordnungszahl Ord (siehe Tabelle
2) versehen, welche ihre Position in der Liste widerspiegelt.
Die Ordnungszahl wird für die folgenden
Verbundoperationen benötigt. Die permutierten Relationen werden mit Ri0j
bezeichnet.
3.4</p>
    </sec>
    <sec id="sec-12">
      <title>Schritt 4: Zusammenfügen</title>
      <p>Im letzten Schritt erfolgt das Zusammenfügen der
permuOrd Age Workclass Ord Occupation Relationship Ord Race Ord Sex
1 39 State-gov 1 Adm-clerical Not-in-family 1 White 1 Male
2 50 Self-emp 2 Exec-managerial Husband 2 White 2 Male
3 38 Private 3 Handlers-cleaners Not-in-family 3 White 3 Male
Ord Age Workclass Ord Occupation Relationship Ord Race Ord Sex
1 53 Private 1 Handlers-cleaners Husband 1 Black 1 Male
2 28 Private 2 Prof-speciality Wife 2 Black 2 Female
3 34 Private 3 Sales Husband 3 White 3 Female
Tabelle 2: Beispielrelation nach horizontalem und vertikalem Split. Der horizontale Split erfolgte auf dem internen Attribut
ROW_ID. Für den vertikalen Split wurden die Attribute Age und Workclass sowie Occupation und Workclass
zusammengefasst. Race und Sex wurden in jeweils einzelne Partitionen zusammengefasst.</p>
    </sec>
    <sec id="sec-13">
      <title>4. IMPLEMENTIERUNG</title>
      <p>Die Umsetzung des Slicing-Konzeptes erfolgte mittels
SQL-92. Einige Datenbanksysteme, wie die verwendete
MySQL-DB, benötigen für die Ausführung temporäre
Tabellen, die mittels CREATE TEMPORARY TABLE
erzeugt werden. Zwecks Übersichtlichkeit wird in den
Quellcodes auf diese Anweisung verzichtet. Parameter und
TabellenAliase werden nachfolgend in &lt;spitzen Klammern&gt;
angegeben.
4.1</p>
    </sec>
    <sec id="sec-14">
      <title>Horizontaler Split</title>
      <p>Für den horizontalen Split werden alle Attribute aus der
Relation &lt;table&gt; übernommen und unter einem
durchnummerierten Alias hSplitTable&lt;id&gt; abgespeichert. Die
Selektionsbedingungen werden für das Attribut &lt;attr&gt; mittels
verschiedener Attributwerte (&lt;x&gt;, &lt;y&gt;) festgelegt und ggf.
mit weiteren Bedingungen verknüpft (siehe Abbildung 2).</p>
      <p>Sofern kein Selektionsattribut vorhanden ist oder explizit
kein solches Attribut verwendet werden soll, so lässt sich ein
künstliches Attribut einfügen. Dafür lassen sich die Zeilen
der Tabelle &lt;table&gt; entweder manuell durchnummerieren</p>
      <sec id="sec-14-1">
        <title>SELECT ∗</title>
        <p>FROM &lt;table&gt; AS h S p l i t T a b l e &lt;i &gt;
WHERE &lt;a t t r &gt; = &lt;x&gt;</p>
        <p>AND &lt;a t t r &gt; BETWEEN &lt;x&gt; AND &lt;y&gt;
Abbildung 2: SQL-Anweisung für die horizontale Zerlegung
von Relationen
Abbildung 3: Künstliche Erzeugung von
Gruppierungsattributen basierend auf Ordnungszahlen
(siehe Abbildung 3) oder, sofern vom Datenbanksystem
unterstützt, mittels der Funktion RANK() die Nummerierung
automatisch erzeugen lassen.</p>
        <p>Sowohl das Erzeugen als auch der horizontale Split
verursachen einen linearen Aufwand. Die Komplexität dieses
Schrittes beträgt O(n ∗ m), wobei n die Anzahl der Tupel in
der Relation und m die Anzahl der Partitionen darstellt.
4.2</p>
      </sec>
    </sec>
    <sec id="sec-15">
      <title>Vertikaler Split, Permutation, Ordnung</title>
      <p>Der vertikale Split, die Permutation der Tupel und das
Erzeugen der Ordnungszahl lassen sich in einer einzelnen
SQL-Anweisung zusammenfassen (siehe Abbildung 4).
Ausgehend von den zuvor erzeugten Partitionen hSplitTable&lt;i&gt;
werden die für die Projektion benötigten Attribute
&lt;attrlist&gt; in der inneren SQL-Anweisung übergeben und über
zufällig erzeugte Werte sortiert (ORDER BY RAND()). Die
äußere SQL-Anweisung übernimmt die projizierten
Attribute (ohne den Zufallswert) und fügt eine Ordnungszahl @rank
hinzu. Das Ergebnis wird unter den Alias p&lt;i, j&gt; abgelegt,
wobei i der Index des horizontalen Splits und j der Index
des vertikalen Splits darstellt.</p>
      <p>Während die vertikale Aufteilung der Daten und das
Hinzufügen der Ordnungszahlen einen linearen Aufwand (bzgl.
SET @rank = 0 ;
SELECT @rank:=@rank+1 AS Ord , &lt; a t t r l i s t &gt;
FROM (SELECT &lt; a t t r l i s t &gt; FROM h S p l i t T a b l e &lt;i &gt;
AS dummyTbl ORDER BY RAND( ) ) AS p&lt;i , j &gt;
Abbildung 4: SQL-Anweisung zur vertikalen Zerlegung und
Permutation von Relationen
SELECT &lt;a t t r − l i s t &gt;
FROM p&lt;i ,1 &gt; JOIN ( p&lt;i ,1 &gt; , . . . , p&lt;i , n&gt;)
ON ( p&lt;i , 1 &gt; . Ord=p&lt;i , 2 &gt; . Ord ,
. . .</p>
      <p>p&lt;i , 1 &gt; . Ord=p&lt;i , n&gt;.Ord )
AS Join&lt;i &gt;</p>
      <p>Abbildung 5: SQL-Anweisung für die Verbundoperation
der Anzahl der Partitionen) erzeugen, benötigt die
Permutation durch das anschließende Sortieren einen höheren
Aufwand. Die Komplexität beträgt dabei O(m ∗ log(n0) ∗ n0),
wobei m die Anzahl der Teilrelationen und n0 die
Anzahl der Tupel innerhalb einer Teilrelation ist. Der Anteil
log(n0) ∗ n0 stellt dabei den Aufwand für gängige
Sortierverfahren. Unterstützt das verwendete
Datenbankmanagementsystem hashbasierte Sortierverfahren, so beträgt die
Komplexität lediglich O(m ∗ n0).
4.3</p>
    </sec>
    <sec id="sec-16">
      <title>Zusammenfügen</title>
      <p>Das Zusammenfügen der Teilrelationen erfolgt in zwei
Schritten. Zunächst erfolgt der Verbund der Attribute über
einen Equi-Join auf den Ordnungszahlen, wobei die
erste Teilrelation p&lt;i,1&gt; mit allen anderen Teilrelationen
(p&lt;i,2&gt;, ..., p&lt;i,n&gt;) verknüpft wird (siehe Abbildung 5).
Es erfolgt zudem eine Projektion auf die Attribute der
Originalrelation &lt;attrlist&gt;, damit die Ordnungszahl im
Ergebnis nicht erscheint. Das Ergebnis des Verbundes wird in der
temporären Relation Join&lt;i&gt; hinterlegt.</p>
      <p>Anschließend werden die so erzeugten Relationen Join1 bis
JoinN mittels des UNION-Operators vereinigt (Siehe
Abbildung 6). Das Ergebnis des Slicing-Konzeptes wird in der
Relation pRelation ausgegeben. Diese stellt eine permutierte
Version der Ursprungsrelation &lt;table&gt; dar.</p>
    </sec>
    <sec id="sec-17">
      <title>AUSWERTUNG</title>
      <p>Die Evaluation erfolgte in einer Client-Server-Umgebung.
Als Server dient eine virtuelle Maschine, die mit einer
64-Bit-CPU (QEMU Virtual CPU version (cpu64-rhel6),
vier Kerne mit jeweils @2 GHz und 4 MB Cache) und
4 GB Arbeitsspeicher ausgestattet ist. Auf dieser wurde eine</p>
      <sec id="sec-17-1">
        <title>SELECT ∗ FROM J o i n 1</title>
        <p>UNION ALL
SELECT ∗ FROM J o i n 2
. . .</p>
        <p>UNION ALL
SELECT ∗ FROM JoinN
AS p R e l a t i o n
Abbildung 6: SQL Anweisung zur horizontalen Vereinigung
der permutierten Partitionen
MySQL-Datenbank mit InnoDB als Speichersystem
verwendet.</p>
        <p>Der Client wurde mit einem i7-3630QM als CPU
betrieben. Dieser bestand ebenfalls aus vier Kernen, die jeweils
über 2,3 GHz und 6 MB Cache verfügten. Als
Arbeitsspeicher standen 8 GB zur Verfügung. Als Laufzeitumgebung
zur parametrisierten Generierung der SQL-Anfragen wurde
Java SE 8u20 eingesetzt.</p>
        <p>Die verwendete Adult-Relation [9] besteht aus insgesamt
32561 Tupeln, die zunächst im CSV-Format vorlagen und in
die Datenbank geparst wurden.
5.1</p>
      </sec>
    </sec>
    <sec id="sec-18">
      <title>Laufzeit</title>
      <p>Abbildung 7 zeigt die Laufzeit der Implementation. Es
wurde eine feste vertikale Partitionierung gewählt (Age und
Workclass, Occupation und Relationship sowie Race und Sex
als einzelne Attribute). Die 32561 Tupel wurden auf eine
variable Anzahl von horizontalen Partitionen aufgeteilt (1, 2,
5, 10, 25, 50, 75, 100, 200, 300, 400, 500), sodass insgesamt
zwölf Parametrisierungen getestet wurden. Für jede
Variante wurden zehn Tests ausgeführt und der Mittelwert der
Laufzeit gebildet.</p>
      <p>Die Zeitmessung erfolgte zu mehreren Zeitpunkten
während des Algorithmus. Die erste Messung erfolgt für die
horizontale (hSplit), die zweite für die vertikale Partitionierung
(vSplit). Für die Permutation und dem anschließenden Join
erfolgte die dritte Zeitmessung (Permutate/Join). Die
letzte Messung ermittelt die Zeit für die abschießenden
UnionOperationen.</p>
      <p>Der Aufwand für die Partitionierung steigt linear mit der
Anzahl der Partitionen. Dies betrifft sowohl die
horizontale (51 ms bis 6626 ms), als auch die vertikale (255 ms bis
3664 ms) Partitionierung. Gleiches gilt auch für die
abschließende Vereinigung, hier sind die Laufzeiten von 68 ms bis
204 ms jedoch nicht ausschlaggebend.</p>
      <p>Die meiste Rechenzeit wird, zumindest bis zu einer
Anzahl von ca. 250 horizontalen Partitionen, für die
Permutation benötigt. Bei einer höheren Anzahl an Partitionen sinkt
die Zeit für die Permutation. Durch die geringe Anzahl an
n 4
e
nd3.5
ku 3
e
lis2.5
l
i
Tupeln pro Partition ist der Aufwand für das
Sortieren/Permutieren innerhalb einer Partition geringer.</p>
      <p>Die Gesamtlaufzeit nimmt bis ca. 100 Partitionen stark
ab (389744 ms bis 7117 ms) und stagniert bis ca. 200
Partitionen (7054 ms). Danach übersteigt der lineare Aufwand
zur Partitionierung den Einsparungen für die Permutation
(bis zu 12621 ms).
5.2</p>
    </sec>
    <sec id="sec-19">
      <title>Anwendung mit Analysefunktionen</title>
      <p>Die Auswirkungen der Anonymisierung auf die
Analysefunktionen in Assistenzsystemen wurden am Beispiel
linearer Regression getestet. Bei der linearen Regression wird eine
Regressionsgerade der Form
yi = α + β ∗ xi +
(6)
bestimmt. Dabei wird der Zusammenhang zwischen einer
abhängigen Variablen y und einer unabhängigen Variablen
x ermittelt. Hierbei werden die Parameter α und β , unter
Berücksichtigung eines maximalen Fehlers , bestimmt. Für
die Variablen x und y werden jeweils zwei Attribute der
Datenbank getestet.</p>
      <p>Bei der Forschung zur Modellbildung für
Assistenzsysteme werden viele Regressionsanalysen mit unterschiedlichen
Attributen überprüft. Die Parametrisierung der vertikalen
Partitionierung des Slicing-Algorithmus erfolgt für die zu
testenden Attributpaare. Dabei werden diese
Kombinationen in eine Partition aufgenommen. Um den Aufwand der
Anonymisierung gering zu halten, werden möglichst große
Attributkombinationen gebildet. Bei der Partition der
Attribute wird dabei im Vorfeld berücksichtigt, dass diese keinen
Quasi-Identifikator enthalten [5]. Durch dieses Vorgehen ist
es möglich, die Regressionsanalysen ohne
Informationsverlust auszuführen. Durch bisher gängige
Anonymisierungskonzepte, wie k-Anonymität [11], ist dies nicht
gewährleistet.</p>
    </sec>
    <sec id="sec-20">
      <title>AUSBLICK</title>
      <p>In dieser Arbeit stellten wir die Umsetzung des
SlicingAnsatzes von Li et al. auf Basis der relationalen Algebra vor.
Dieses Anonymisierungsverfahren bietet einen guten
Kompromiss zwischen Datenschutz und Analysefunktionalitäten
durch Minimierung des Informationsverlustes.</p>
      <p>Anhand von linearen Regressionsanalysen wurde gezeigt,
dass das Slicing-Verfahren mit den Funktionalitäten von</p>
      <p>Assistenzsystemen harmoniert. Um festzustellen, für
welche Analysefunktionen ein geeignetes
Anonymisierungsverfahren existiert, sind weiterführende Arbeiten notwendig.
Im Rahmen des PArADISE-Projektes werden dazu weitere
Datenschutztechniken und Analysefunktionen in den
vorgestellten Anfrageprozessor integriert.</p>
    </sec>
    <sec id="sec-21">
      <title>DANKSAGUNG</title>
      <p>Hannes Grunert wird durch die Deutsche
Forschungsgemeinschaft (DFG) im Rahmen des Graduiertenkollegs 1424
(Multimodal Smart Appliance Ensembles for Mobile
Applications - MuSAMA) gefördert. Wir danken den anonymen
Gutachtern für ihre Anregungen und Kommentare.</p>
    </sec>
  </body>
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          <article-title>Anzahl der Teilrelationen Abbildung 7: Betrachtung der Laufzeit des SlicingAlgorithmus für unterschiedlich große Partitionen. Bei großen Partitionen nimmt der Aufwand für die Permutation der einzelnen Teilrelationen drastisch zu. Kleinere Partitionen benötigen eine geringere Laufzeit für die Permutation; das Erstellen der Teilrelationen erfordert aber mehr Zeit. 6. 8</article-title>
          . LITERATUR [1]
          <string-name>
            <given-names>Bundesrepublik</given-names>
            <surname>Deutschland</surname>
          </string-name>
          .
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          <string-name>
            <surname>Bundesdatenschutzgesetz</surname>
          </string-name>
          ,
          <year>2010</year>
          . [2]
          <string-name>
            <given-names>Tore</given-names>
            <surname>Dalenius</surname>
          </string-name>
          .
          <article-title>Finding a Needle In a Haystack or</article-title>
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          <string-name>
            <given-names>Official</given-names>
            <surname>Statistics</surname>
          </string-name>
          ,
          <volume>2</volume>
          (
          <issue>3</issue>
          ):
          <fpage>329</fpage>
          -
          <lpage>336</lpage>
          ,
          <year>1986</year>
          . [3]
          <string-name>
            <given-names>Hector</given-names>
            <surname>Garcia-Molina</surname>
          </string-name>
          ,
          <string-name>
            <given-names>Jeffrey D.</given-names>
            <surname>Ullman</surname>
          </string-name>
          , and Jennifer
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          <source>(international edition)</source>
          .
          <source>Pearson Education</source>
          ,
          <year>2002</year>
          . [4]
          <string-name>
            <given-names>Hannes</given-names>
            <surname>Grunert</surname>
          </string-name>
          . Privacy Policy for Smart
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          Environments. http://www.ls-dbis.de/pp4se,
          <year>2014</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation>
          <source>zuletzt aufgerufen am 13.05</source>
          .
          <year>2015</year>
          . [5]
          <string-name>
            <given-names>Hannes</given-names>
            <surname>Grunert</surname>
          </string-name>
          and
          <string-name>
            <given-names>Andreas</given-names>
            <surname>Heuer</surname>
          </string-name>
          . Big Data und
        </mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation>
          <string-name>
            <surname>Daten</surname>
          </string-name>
          .
          <source>In Proceedings of the 26th GI-Workshop on</source>
        </mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation>
          Datenbanken). http://ceur-ws.org,
          <year>2014</year>
          . [6]
          <string-name>
            <surname>Albert</surname>
            <given-names>Hein</given-names>
          </string-name>
          , Frank Feldhege, Anett Mau-Möller,
        </mixed-citation>
      </ref>
      <ref id="ref9">
        <mixed-citation>
          <string-name>
            <surname>Störungen</surname>
          </string-name>
          .
          <source>In Ambient Assisted Living</source>
          <volume>7</volume>
          .
        </mixed-citation>
      </ref>
      <ref id="ref10">
        <mixed-citation>
          <string-name>
            <surname>AAL-Kongress</surname>
          </string-name>
          2014 Berlin, Germany, January
        </mixed-citation>
      </ref>
      <ref id="ref11">
        <mixed-citation>
          21-
          <fpage>22</fpage>
          .,
          <year>2014</year>
          , Tagungsbände, Berlin, Germany,
        </mixed-citation>
      </ref>
      <ref id="ref12">
        <mixed-citation>
          <string-name>
            <surname>January</surname>
          </string-name>
          <year>2014</year>
          . VDE Verlag. [7]
          <string-name>
            <given-names>Andreas</given-names>
            <surname>Heuer</surname>
          </string-name>
          . METIS in PArADISE: Provenance
        </mixed-citation>
      </ref>
      <ref id="ref13">
        <mixed-citation>
          <string-name>
            <surname>Technologie und Web - Workshopband</surname>
          </string-name>
          , volume
          <volume>242</volume>
          of
        </mixed-citation>
      </ref>
      <ref id="ref14">
        <mixed-citation>
          Lecture Notes in Informatics, pages
          <fpage>131</fpage>
          -
          <lpage>135</lpage>
          . Springer,
        </mixed-citation>
      </ref>
      <ref id="ref15">
        <mixed-citation>
          <year>2015</year>
          . [8]
          <string-name>
            <given-names>Ayça</given-names>
            <surname>Azgin</surname>
          </string-name>
          Hintoglu and
          <string-name>
            <given-names>Yücel</given-names>
            <surname>Saygın</surname>
          </string-name>
          . Suppressing
        </mixed-citation>
      </ref>
      <ref id="ref16">
        <mixed-citation>
          <source>The VLDB Journal</source>
          ,
          <volume>19</volume>
          (
          <issue>3</issue>
          ):
          <fpage>385</fpage>
          -
          <lpage>410</lpage>
          ,
          <year>2010</year>
          . [9]
          <string-name>
            <given-names>Ronny</given-names>
            <surname>Kohavi</surname>
          </string-name>
          and
          <string-name>
            <given-names>Barry</given-names>
            <surname>Becker</surname>
          </string-name>
          .
          <source>Adult Data Set.</source>
        </mixed-citation>
      </ref>
      <ref id="ref17">
        <mixed-citation>
          <source>1996. zuletzt aufgerufen am 13.05</source>
          .
          <year>2015</year>
          . [10]
          <string-name>
            <given-names>Tiancheng</given-names>
            <surname>Li</surname>
          </string-name>
          ,
          <string-name>
            <given-names>Ninghui</given-names>
            <surname>Li</surname>
          </string-name>
          ,
          <string-name>
            <given-names>Jian</given-names>
            <surname>Zhang</surname>
          </string-name>
          , and Ian Molloy.
        </mixed-citation>
      </ref>
      <ref id="ref18">
        <mixed-citation>
          Transactions on,
          <volume>24</volume>
          (
          <issue>3</issue>
          ):
          <fpage>561</fpage>
          -
          <lpage>574</lpage>
          ,
          <year>2012</year>
          . [11]
          <string-name>
            <given-names>Pierangela</given-names>
            <surname>Samarati</surname>
          </string-name>
          . Protecting Respondents'
        </mixed-citation>
      </ref>
      <ref id="ref19">
        <mixed-citation>
          <source>on Knowledge and Data Engineering</source>
          ,
          <volume>13</volume>
          (
          <issue>6</issue>
          ):
          <fpage>1010</fpage>
          -
          <lpage>1027</lpage>
          ,
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>