Slicing in Assistenzsystemen Wie trotz Anonymisierung von Daten wertvolle Analyseergebnisse gewonnen werden können Hannes Grunert Andreas Heuer Lehrstuhl für Datenbank- und Lehrstuhl für Datenbank- und Informationssysteme Informationssysteme Universität Rostock Universität Rostock 18051 Rostock 18051 Rostock hg(at)informatik.uni-rostock.de ah(at)informatik.uni-rostock.de Kurzfassung mit weiteren Informationen, beispielsweise dem Nutzerprofil Datenschutz stellt eine große Herausforderung für die eines sozialen Netzwerkes verknüpft. Aus den so gewonne- Entwicklung von Informationssystemen dar. Obwohl nen Informationen lassen sich Verhaltensmuster, Präferen- viele Konzepte zur Wahrung des Datenschutzes beste- zen und zukünftige Ereignisse ermitteln. Auf Basis dieser hen, werden Datenschutztechniken in der Regel nicht in Daten reagiert das Assistenzsystem eigenständig auf die Be- Datenbankmanagement- und Assistenzsysteme integriert. dürfnisse des Nutzers und regelt Raumtemperatur, Lüftung In diesem Artikel stellen wir eine SQL-Implementierung und weitere vernetzte Geräte. des Slicing-Konzeptes von Li et al. [10] vor. Es erfolgt eine Assistenzsysteme sammeln häufig wesentlich mehr Infor- detaillierte Betrachtung hinsichtlich der Parametrisierung mationen als sie für die Ausführung ihrer Funktionen benö- des Algorithmus und dessen Auswirkung auf Informations- tigen. Der Nutzer hat dabei meist keinen oder nur einen un- verlust und Grad des Datenschutzes. wesentlichen Einfluss auf die Speicherung und Verarbeitung seiner personenbezogenen Daten. Dadurch ist sein Recht auf informationelle Selbstbestimmung verletzt. ACM Klassifikation Die Einführung von Datenschutzmechanismen wird sei- H.2.4 [Database Management]: Systems—Query Proces- tens der Entwickler von Assistenzsystemen skeptisch an- sing; K.4.1 [Computer and Society]: Public Policy Issu- gesehen. Es wird befürchtet, dass durch die Anonymisie- es—Privacy rung der Daten die Entwicklung des Systems zurückgewor- fen wird. Durch die Anonymisierung bzw. Pseudonymisie- Stichworte rung der Nutzerdaten gehen Detailinformationen verloren, wodurch Analysefunktionen ungenauere Ergebnisse zurück- Datenbanken, Datenschutz, Datensparsamkeit liefern und im Extremfall unbrauchbar werden. Im Rahmen des Graduiertenkollegs MuSAMA1 werden 1. EINLEITUNG Datenschutzkonzepte für die Anfrageverarbeitung in Assis- Zwei Kernaspekte des Datenschutzes sind Datensparsam- tenzsystemen entworfen. Diese werden allerdings nicht on- keit und Datenvermeidung. §3a des Bundesdatenschutzge- top auf die bestehenden Analysefunktionen aufgesetzt, son- setzes [1] definiert diese als Forderung, dass Informations- dern in enger Zusammenarbeit während der Entwicklung systeme möglichst wenig personenbezogene Daten erheben, integriert. Ein Beispiel für dieses Zusammenwirken ist die verarbeiten oder nutzen sollen. Dies betrifft neben der Kon- Umsetzung des Slicing-Konzeptes von Li et al. [10] zusam- zeption von Informationssystemen auch den Prozess der Da- men mit der Regressionsanalyse [6] auf hochdimensionalen tenverarbeitung. Sensordaten. Assistenzsysteme sollen den Nutzer bei der Bewältigung seines Alltags, sei es im Beruf oder zu Hause, unterstüt- 1.1 PArADISE zen. Über verschiedene Sensoren, wie Bewegungssensoren Für die Umsetzung von Datenschutzrichtlinien in smar- und Wärmemessgeräte, werden Informationen über die mo- ten Umgebungen wird derzeit das PArADISE2 -Framework mentane Situation und die Aktivitäten des Anwenders ge- [7] entwickelt, welches insbesondere die Aspekte der Da- sammelt. Diese Daten werden im System gespeichert und tensparsamkeit und Datenvermeidung in heterogenen P2P- Systemen realisieren soll. PArADISE ist Werkzeug, welches den Entwicklern und Nutzern von Assistenzsystemen helfen soll effizient und da- tenschutzkonform Anfragen auf Sensordaten zu formulieren. Der Kern des Frameworks ist ein datenschutzfreundlicher 1 Multimodal Smart Appliance Ensembles for Mobile Applications 2 27th GI-Workshop on Foundations of Databases (Grundlagen von Daten- Privacy-Aware Assistive Distributed Information System banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. Environment Copyright is held by the author/owner(s). 24 Anfrageprozessor (siehe Abbildung 1). Dieser Prozessor er- spiels. Das letzte Kapitel fasst den Beitrag zusammen und hält als Eingabe zum einen die Datenschutzeinstellungen der gibt einen Ausblick auf zukünftige Arbeiten. Nutzer, zum anderen den Informationsbedarf des Systems anhand von Anfragen an das Datenbanksystem. Als Aus- 2. SLICING gabe wird ein anonymisierter, annotierter Teil des Daten- In [10] stellen Li et al. ein neues Anonymisierungskonzept bestandes zurückgeliefert. In den Annotationen wird ange- vor, welches auf der Permutation von Daten beruht. Im Ge- geben, wie der Datenbestand anonymisiert wurde und ob gensatz zu den bisher gängigen Anonymisierungsverfahren bereits die erforderlichen Analysen der Daten auf dem aus- wie k-Anonymität [11] verzichtet dieses Verfahren auf Ge- führenden Knoten umgesetzt wurden. Falls keine Analyse neralisierungstechniken. durchgeführt wurde, muss der Knoten, welcher das Ergebnis Eine Relation ist k-anonym, wenn, auf Basis der identifi- erhalten hat, die weitere Verarbeitung der Daten überneh- zierenden Attributmengen der Relation, ein Tupel von k-1 men. anderen Tupeln nicht unterscheidbar ist. In der Regel wird Der Anfrageprozessor arbeitet in zwei Stufen. Ziel der ers- eine Person durch ein Tupel in der Relation dargestellt. In ten Stufe, der Vorverarbeitungsphase, ist die Modifikation Assistenzsystemen werden, je nach Anwendungsgebiet, nur der eingehenden Anfragen, sodass möglichst wenige Daten Informationen über eine Person gesammelt. Dies gilt z. B. aus der Datenbank ausgelesen werden. Dazu wird die Anfra- bei der Überwachung von Demenzpatienten. Dort lassen sich ge analysiert. Durch die Analyse lässt sich erkennen, welche mittels der aufgenommenen Daten einzelne Handlungen ei- Attribute angefragt werden, wie diese hinsichtlich ihres Wer- ner Person identifizieren. Diese gilt es ebenfalls zu anonymi- tebereichs gefiltert und ggf. aggregiert und gruppiert wer- sieren. den. Bei der Generalisierung von Daten kommen Detailinfor- Die so erhaltenen Informationen über die Anfrage werden mationen abhanden, die bei vielen Analysefunktionen benö- mit den vorformulierten Privatheitsansprüchen [4] des Nut- tigt werden. Das Slicing-Verfahren verspricht einen höheren zers verglichen. Treten an dieser Stelle Widersprüche auf, Datennutzen, indem es die Verbindung von stark korreli- wie beispielsweise der Zugriff auf ein Attribut, welches der erenden Attributen bewahrt. Auf dieser Grundlage ist es Nutzer nicht von sich preisgeben möchte, wird die Anfrage trotz Anonymisierung weiterhin möglich Data-Mining- und angepasst. Dabei werden verschiedene Techniken, wie An- Analyse-Techniken, wie Regressionsanalysen, anzuwenden. frageumschreibungen und Abbildungen auf Sichten, ange- Das Konzept permutiert nicht den kompletten Datenbe- wandt. stand, sondern partitioniert die Daten sowohl horizontal als In der Nachverarbeitungsphase erfolgt, sofern erforder- auch vertikal. Bei der horizontalen Partitionierung (Tuple lich, die Anonymisierung der Daten. Dabei wird überprüft, Partition) wird der Datenbestand nach festgelegten Filter- ob spezielle Kriterien wie k-Anonymität [11] zutreffen. An- kriterien (Selektion nach einem bestimmten Attribut, An- schließend erfolgt die Anonymisierung der Daten unter Be- zahl an Partitionen, ...) in mehrere Mengen von Tupeln zer- rücksichtigung des Grades der benötigten Anonymität und legt. des Informationsverlustes [8] zur Wahrung von Funktionali- Die vertikale Partitionierung (Attribute Partition) unter- tät und Datenschutz. teilt den Datenbestand spaltenweise, indem aus der vorhan- Durch die Vorverarbeitung der Anfrage müssen weniger denen Attributmenge mehrere kleine Attributmengen gebil- Daten in der Nachverarbeitungsphase anonymisiert werden. det werden. Eine mögliche vertikale Zerlegung besteht im Dadurch erfolgt nur eine geringe Erhöhung der Antwortzeit Aufteilen der Attribute eines Quasi-Identifikators [2] auf auf die Anfrage. mehrere Partitionen. 1.2 Laufendes Beispiel Aus einem Datenbestand der durch n horizontale und m vertikale Partitionsvorgaben zerteilt wird, entsteht ein Ras- Die Umsetzung des Slicing-Konzeptes wird in diesen Ar- ter aus n*m kleineren Relationen. Jede dieser Teilrelationen tikel anhand eines laufenden Beispiels erläutert. Für die Im- wird anschließend permutiert, indem die Reihenfolge der Tu- plementation und Evaluation des Algorithmus wurde die pel vertauscht wird. Die permutierten Relationen werden Adult-Relation aus dem UCI Machine Learning Reposito- anschließend wieder zu einer einzelnen Relation verknüpft. ry [9] verwendet. Die Relation besteht aus personenbezoge- nen Daten, bei denen Schlüssel sowie Vor- und Nachname der betroffenen Personen entfernt wurden. Die verbleiben- 3. UMSETZUNG IN DER RELATIONALEN den 15 Attribute enthalten weitere personenbezogene Anga- ALGEBRA ben, wie beispielsweise Alter, Ehestand, Staatsangehörigkeit Für das Slicing-Konzept wird von Li et al. eine grobe Me- und Schulabschluss. thodik für die Implementierung vorgestellt. In diesem Ab- Tabelle 1 zeigt einen Ausschnitt der gesamten Relation. In schnitt demonstrieren wir die Adaption des Verfahrens auf diesem Artikel wird gezeigt, wie diese Relation schrittweise die relationale Algebra. Konkrete Implementierungsdetails in eine anonymisierte Relation (siehe Tabelle 3) überführt werden im nachfolgenden Kapitel vorgestellt. wird. Der Rest des Artikels ist wie folgt strukturiert: Kapitel 2 3.1 Schritt 1: Horizontaler Split gibt einen Überblick über das Anonymisierungskonzept von Im ersten Schritt wird die Relation R in n disjunkte Par- Li et al. Im folgenden Kapitel gehen wir detailliert darauf titionen R1 , ..., Rn zerlegt. Für jede Partition Ri wird eine ein, wie das Konzept durch Operationen aus der Relationen- Selektionsbedingung ci angegeben, welche die Tupel aus R algebra realisiert werden kann. In Kapitel 4 wird beschrie- den Partitionen zuordnet: ben wie die Implementation des Konzeptes in SQL erfolgt. Kapitel 5 evaluiert den Ansatz anhand des laufenden Bei- R1 := σc1 (R), ..., Rn := σcn (R). (1) 25 Abbildung 1: Das Konzept des datenschutzfreundlichen Anfrageprozessors Age Workclass Occupation Relationship Race Sex 39 State-gov Adm-clerical Not-in-family White Male 50 Self-emp Exec-managerial Husband White Male 38 Private Handlers-cleaners Not-in-family White Male 53 Private Handlers-cleaners Husband Black Male 28 Private Prof-speciality Wife Black Female 34 Private Sales Husband White Female Tabelle 1: Die Beispielrelation vor der Anonymisierung Die Auswahl der Selektionsbedingungen muss dabei ge- auf unterschiedliche Partitionen zu verteilen. Die Ermittlung schickt gewählt werden. Eine Möglichkeit besteht aus der von identifizierenden Attributmengen, sogenannten Quasi- Selektion nach einem bestimmten Attribut, wobei für jeden Identifikatoren [2], lässt sich mit geringem Aufwand [5] vor einzelnen auftretenden Attributwert (oder eine Menge von der Anonymisierung realisieren. Attributwerten) eine Selektionsbedingung der Form attri- but = ’Wert’ aufgestellt wird. Eine weitere Variante besteht 3.3 Schritt 3: Permutation darin, die Tupel in R zu nummerieren (neues Attribut rank) Nach der Bildung der Teilrelationen Rij erfolgt die ei- und die Selektionen in der Form ’rank between vj and vk ’3 gentliche Anonymisierung. Die Permutation erfolgt durch zu beschreiben. den Ordnungsoperator τ , welcher die Tupel jeder Teilrelati- on sortiert. In Abschnitt 4.2 wird genauer erklärt wie eine 3.2 Schritt 2: Vertikaler Split zufällige Sortierung erfolgen kann. Das Resultat der Permu- Nachdem die Relation R in mehrere kleinere Relationen tation wird in der Liste Lij hinterlegt: Ri zerlegt wurde, wird jede Ri durch Projektionen weiter unterteilt. Jede Projektion πattributmengej (Ri ) wählt dabei Lij := τ (Rij ). (3) ein oder mehrere Attribute aus der Relation R aus. Für jede An dieser Stelle geschieht ein kleiner Bruch mit der rela- Partitionen Ri werden dabei die gleichen m Projektionen tionalen Algebra. Der Ordnungsoperator τ darf zwar auf angewandt um die m Teilrelationen Rij aus Ri zu bilden: Relationen angewandt werden, liefert allerdings keine Rela- Ri1 := πattributmenge1 (Ri ), ..., Rim := πattributmengem (Ri ). tion, sondern eine Liste zurück. τ darf somit nur als letzter Operator angewandt werden [3]. Dies stellt ein Problem dar, (2) weil für den Slicing-Algorithmus die permutierten Listen im Die Attributmengen in den Projektionen müssen dabei nicht zwangsweise disjunkt sein4 . Sie dürfen keine identifizierende letzten Schritt wieder zusammengefügt werden müssen. Attributmenge enthalten, da ansonsten Rückschlüsse auf die Die Listen müssen entsprechend wieder zurück in Rela- Identität einer Person gezogen oder Handlungen eindeutig tionen überführt werden. Um die Ordnung zu bewahren, wird jedes Tupel mit einer Ordnungszahl Ord (siehe Tabelle bestimmt werden können. Die Auswahl der Attributmengen sollte dabei in Abstimmung mit den Analysefunktionen ge- 2) versehen, welche ihre Position in der Liste widerspiegelt. troffen werden, um z. B. stark korrelierende Attribute nicht Die Ordnungszahl wird für die folgenden Verbundoperatio- nen benötigt. Die permutierten Relationen werden mit Rij 0 3 vj , vk nummerische Werte bezeichnet. 4 Im grundlegenden Algorithmus von Li et al. [10] wird Dis- junktheit vorausgesetzt. Erweiterungen setzen Disjunktheit 3.4 Schritt 4: Zusammenfügen nicht voraus. Im letzten Schritt erfolgt das Zusammenfügen der permu- 26 Ord 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 zusammenge- fasst. Race und Sex wurden in jeweils einzelne Partitionen zusammengefasst. Age Workclass Occupation Relationship Race Sex 39 Private Exec-managerial Husband White Male 38 State-gov Adm-clerical Not-in-family White Male 50 Self-emp Handlers-cleaners Not-in-family White Male 28 Private Handlers-cleaners Husband Black Female 34 Private Sales Husband Black Female 53 Private Prof-speciality Wife White Male Tabelle 3: Beispielrelation nach Anwendung des Slicing-Konzeptes tierten Teilrelationen Rij 0 zur permutierten Gesamtrelation SELECT ∗ R . Das Zusammenfügen geschieht dabei in zwei Teilschrit- 0 FROM AS h S p l i t T a b l e ten. WHERE = Im ersten Teilschritt werden die permutierten Teilrela- −−AND BETWEEN AND tionen Rij 0 über den Verbundoperator zu den permutierten Partitionen Ri0 miteinander verbunden. Der Verbund erfolgt Abbildung 2: SQL-Anweisung für die horizontale Zerlegung über die zuvor angelegte Ordnungszahl: von Relationen Ri0 := Ri1 ./i1.Ord=i2.Ord Ri2 ... ./i1.Ord=im.Ord Rim . (4) SET @rank = 0 ; Abschließend wird die Vereinigung der permutierten Parti- SELECT ∗ , tionen Ri0 gebildet: @rank:=@rank+1 AS ’ ID ’ [ n FROM
AS dummyTable ; R0 := Ri0 . (5) i=1 Abbildung 3: Künstliche Erzeugung von Gruppierungsattri- buten basierend auf Ordnungszahlen R0 ist das Ergebnis des Slicing-Ansatzes. Die permutierte Relation kann im weiteren Verlauf für Analysefunktion un- ter Einhaltung des Datenschutzes verwendet werden. (siehe Abbildung 3) oder, sofern vom Datenbanksystem un- terstützt, mittels der Funktion RANK() die Nummerierung 4. IMPLEMENTIERUNG automatisch erzeugen lassen. Die Umsetzung des Slicing-Konzeptes erfolgte mittels Sowohl das Erzeugen als auch der horizontale Split ver- SQL-92. Einige Datenbanksysteme, wie die verwendete ursachen einen linearen Aufwand. Die Komplexität dieses MySQL-DB, benötigen für die Ausführung temporäre Ta- Schrittes beträgt O(n ∗ m), wobei n die Anzahl der Tupel in bellen, die mittels CREATE TEMPORARY TABLE er- der Relation und m die Anzahl der Partitionen darstellt. zeugt werden. Zwecks Übersichtlichkeit wird in den Quellco- 4.2 Vertikaler Split, Permutation, Ordnung des auf diese Anweisung verzichtet. Parameter und Tabellen- Aliase werden nachfolgend in angege- Der vertikale Split, die Permutation der Tupel und das ben. Erzeugen der Ordnungszahl lassen sich in einer einzelnen SQL-Anweisung zusammenfassen (siehe Abbildung 4). Aus- 4.1 Horizontaler Split gehend von den zuvor erzeugten Partitionen hSplitTable Für den horizontalen Split werden alle Attribute aus der werden die für die Projektion benötigten Attribute übernommen und unter einem durchnum- list> in der inneren SQL-Anweisung übergeben und über merierten Alias hSplitTable abgespeichert. Die Selek- zufällig erzeugte Werte sortiert (ORDER BY RAND()). Die tionsbedingungen werden für das Attribut mittels äußere SQL-Anweisung übernimmt die projizierten Attribu- verschiedener Attributwerte (, ) festgelegt und ggf. te (ohne den Zufallswert) und fügt eine Ordnungszahl @rank mit weiteren Bedingungen verknüpft (siehe Abbildung 2). hinzu. Das Ergebnis wird unter den Alias p abgelegt, Sofern kein Selektionsattribut vorhanden ist oder explizit wobei i der Index des horizontalen Splits und j der Index kein solches Attribut verwendet werden soll, so lässt sich ein des vertikalen Splits darstellt. künstliches Attribut einfügen. Dafür lassen sich die Zeilen Während die vertikale Aufteilung der Daten und das Hin- der Tabelle
entweder manuell durchnummerieren zufügen der Ordnungszahlen einen linearen Aufwand (bzgl. 27 SET @rank = 0 ; MySQL-Datenbank mit InnoDB als Speichersystem verwen- SELECT @rank:=@rank+1 AS Ord , < a t t r l i s t > det. FROM (SELECT < a t t r l i s t > FROM h S p l i t T a b l e Der Client wurde mit einem i7-3630QM als CPU betrie- AS dummyTbl ORDER BY RAND( ) ) AS p ben. Dieser bestand ebenfalls aus vier Kernen, die jeweils über 2,3 GHz und 6 MB Cache verfügten. Als Arbeitsspei- Abbildung 4: SQL-Anweisung zur vertikalen Zerlegung und cher standen 8 GB zur Verfügung. Als Laufzeitumgebung Permutation von Relationen zur parametrisierten Generierung der SQL-Anfragen wurde Java SE 8u20 eingesetzt. SELECT Die verwendete Adult-Relation [9] besteht aus insgesamt FROM p JOIN ( p , . . . , p) 32561 Tupeln, die zunächst im CSV-Format vorlagen und in ON ( p. Ord=p. Ord , die Datenbank geparst wurden. ... p. Ord=p.Ord ) 5.1 Laufzeit AS Join Abbildung 7 zeigt die Laufzeit der Implementation. Es wurde eine feste vertikale Partitionierung gewählt (Age und Abbildung 5: SQL-Anweisung für die Verbundoperation Workclass, Occupation und Relationship sowie Race und Sex als einzelne Attribute). Die 32561 Tupel wurden auf eine va- riable Anzahl von horizontalen Partitionen aufgeteilt (1, 2, der Anzahl der Partitionen) erzeugen, benötigt die Permuta- 5, 10, 25, 50, 75, 100, 200, 300, 400, 500), sodass insgesamt tion durch das anschließende Sortieren einen höheren Auf- zwölf Parametrisierungen getestet wurden. Für jede Vari- wand. Die Komplexität beträgt dabei O(m ∗ log(n0 ) ∗ n0 ), ante wurden zehn Tests ausgeführt und der Mittelwert der wobei m die Anzahl der Teilrelationen und n0 die An- Laufzeit gebildet. zahl der Tupel innerhalb einer Teilrelation ist. Der Anteil Die Zeitmessung erfolgte zu mehreren Zeitpunkten wäh- log(n0 ) ∗ n0 stellt dabei den Aufwand für gängige Sortierver- rend des Algorithmus. Die erste Messung erfolgt für die hori- fahren. Unterstützt das verwendete Datenbankmanagement- zontale (hSplit), die zweite für die vertikale Partitionierung system hashbasierte Sortierverfahren, so beträgt die Kom- (vSplit). Für die Permutation und dem anschließenden Join plexität lediglich O(m ∗ n0 ). erfolgte die dritte Zeitmessung (Permutate/Join). Die letz- te Messung ermittelt die Zeit für die abschießenden Union- 4.3 Zusammenfügen Operationen. Das Zusammenfügen der Teilrelationen erfolgt in zwei Schritten. Zunächst erfolgt der Verbund der Attribute über ·104 einen Equi-Join auf den Ordnungszahlen, wobei die ers- 4 hSplit vSplit Laufzeit in Millisekunden te Teilrelation p mit allen anderen Teilrelationen (p, ..., p) verknüpft wird (siehe Abbildung 5). 3.5 Permutate/Join Es erfolgt zudem eine Projektion auf die Attribute der Ori- 3 Union ginalrelation , damit die Ordnungszahl im Ergeb- 2.5 nis nicht erscheint. Das Ergebnis des Verbundes wird in der 2 temporären Relation Join hinterlegt. Anschließend werden die so erzeugten Relationen Join1 bis 1.5 JoinN mittels des UNION-Operators vereinigt (Siehe Ab- 1 bildung 6). Das Ergebnis des Slicing-Konzeptes wird in der 0.5 Relation pRelation ausgegeben. Diese stellt eine permutierte 0 Version der Ursprungsrelation
dar. 10 50 100 200 300 400 500 5. AUSWERTUNG Anzahl der Teilrelationen Die Evaluation erfolgte in einer Client-Server-Umgebung. Abbildung 7: Betrachtung der Laufzeit des Slicing- Als Server dient eine virtuelle Maschine, die mit einer Algorithmus für unterschiedlich große Partitionen. Bei 64-Bit-CPU (QEMU Virtual CPU version (cpu64-rhel6), großen Partitionen nimmt der Aufwand für die Permutation vier Kerne mit jeweils @2 GHz und 4 MB Cache) und der einzelnen Teilrelationen drastisch zu. Kleinere Partitio- 4 GB Arbeitsspeicher ausgestattet ist. Auf dieser wurde eine nen benötigen eine geringere Laufzeit für die Permutation; das Erstellen der Teilrelationen erfordert aber mehr Zeit. SELECT ∗ FROM J o i n 1 Der Aufwand für die Partitionierung steigt linear mit der UNION ALL Anzahl der Partitionen. Dies betrifft sowohl die horizonta- SELECT ∗ FROM J o i n 2 le (51 ms bis 6626 ms), als auch die vertikale (255 ms bis ... 3664 ms) Partitionierung. Gleiches gilt auch für die abschlie- UNION ALL ßende Vereinigung, hier sind die Laufzeiten von 68 ms bis SELECT ∗ FROM JoinN 204 ms jedoch nicht ausschlaggebend. AS p R e l a t i o n Die meiste Rechenzeit wird, zumindest bis zu einer An- zahl von ca. 250 horizontalen Partitionen, für die Permuta- Abbildung 6: SQL Anweisung zur horizontalen Vereinigung tion benötigt. Bei einer höheren Anzahl an Partitionen sinkt der permutierten Partitionen die Zeit für die Permutation. Durch die geringe Anzahl an 28 Anzahl hSplit vSplit vJoin/ Union Assistenzsystemen harmoniert. Um festzustellen, für wel- Buckets in ms in ms Permutate in ms che Analysefunktionen ein geeignetes Anonymisierungsver- in ms fahren existiert, sind weiterführende Arbeiten notwendig. 1 51 255 388846 68 Im Rahmen des PArADISE-Projektes werden dazu weitere 2 89 252 189844 155 Datenschutztechniken und Analysefunktionen in den vorge- 5 126 253 78324 142 stellten Anfrageprozessor integriert. 10 177 278 39503 143 25 345 389 15664 143 7. DANKSAGUNG 50 652 531 8075 156 Hannes Grunert wird durch die Deutsche Forschungsge- 75 931 663 5315 145 meinschaft (DFG) im Rahmen des Graduiertenkollegs 1424 100 1267 875 4297 172 (Multimodal Smart Appliance Ensembles for Mobile Appli- 200 2518 1415 2422 181 cations - MuSAMA) gefördert. Wir danken den anonymen 300 3938 2130 1896 171 Gutachtern für ihre Anregungen und Kommentare. 400 5315 2955 1687 202 500 6626 3664 1615 204 8. LITERATUR Tabelle 4: Messwerte für die einzelnen SQL-Anfragen [1] Bundesrepublik Deutschland. Bundesdatenschutzgesetz, 2010. [2] Tore Dalenius. Finding a Needle In a Haystack or Tupeln pro Partition ist der Aufwand für das Sortieren/Per- Identifying Anonymous Census Records. Journal of mutieren innerhalb einer Partition geringer. Official Statistics, 2(3):329–336, 1986. Die Gesamtlaufzeit nimmt bis ca. 100 Partitionen stark [3] Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer ab (389744 ms bis 7117 ms) und stagniert bis ca. 200 Par- Widom. Database systems - the complete book titionen (7054 ms). Danach übersteigt der lineare Aufwand (international edition). Pearson Education, 2002. zur Partitionierung den Einsparungen für die Permutation [4] Hannes Grunert. Privacy Policy for Smart (bis zu 12621 ms). Environments. http://www.ls-dbis.de/pp4se, 2014. zuletzt aufgerufen am 13.05.2015. 5.2 Anwendung mit Analysefunktionen [5] Hannes Grunert and Andreas Heuer. Big Data und Die Auswirkungen der Anonymisierung auf die Analyse- der Fluch der Dimensionalität: Die effiziente Suche funktionen in Assistenzsystemen wurden am Beispiel linea- nach Quasi-Identifikatoren in hochdimensionalen rer Regression getestet. Bei der linearen Regression wird eine Daten. In Proceedings of the 26th GI-Workshop on Regressionsgerade der Form Foundations of Databases (Grundlagen von yi = α + β ∗ xi +  (6) Datenbanken). http://ceur-ws.org, 2014. [6] Albert Hein, Frank Feldhege, Anett Mau-Möller, bestimmt. Dabei wird der Zusammenhang zwischen einer Rainer Bader, Uwe Zettl, Oliver Burmeister, and abhängigen Variablen y und einer unabhängigen Variablen Thomas Kirste. NASFIT - Intelligente x ermittelt. Hierbei werden die Parameter α und β, unter Assistenzsysteme zur Funktionsunterstützung und Berücksichtigung eines maximalen Fehlers , bestimmt. Für Therapieüberwachung bei neuromuskulären die Variablen x und y werden jeweils zwei Attribute der Störungen. In Ambient Assisted Living 7. Datenbank getestet. AAL-Kongress 2014 Berlin, Germany, January Bei der Forschung zur Modellbildung für Assistenzsyste- 21-22., 2014, Tagungsbände, Berlin, Germany, me werden viele Regressionsanalysen mit unterschiedlichen January 2014. VDE Verlag. Attributen überprüft. Die Parametrisierung der vertikalen [7] Andreas Heuer. METIS in PArADISE: Provenance Partitionierung des Slicing-Algorithmus erfolgt für die zu Management bei der Auswertung von testenden Attributpaare. Dabei werden diese Kombinatio- Sensordatenmengen für die Entwicklung von nen in eine Partition aufgenommen. Um den Aufwand der Assistenzsystemen. In Datenbanken für Business, Anonymisierung gering zu halten, werden möglichst große Technologie und Web - Workshopband, volume 242 of Attributkombinationen gebildet. Bei der Partition der Attri- Lecture Notes in Informatics, pages 131–135. Springer, bute wird dabei im Vorfeld berücksichtigt, dass diese keinen 2015. Quasi-Identifikator enthalten [5]. Durch dieses Vorgehen ist [8] Ayça Azgin Hintoglu and Yücel Saygın. Suppressing es möglich, die Regressionsanalysen ohne Informationsver- microdata to prevent classification based inference. lust auszuführen. Durch bisher gängige Anonymisierungs- The VLDB Journal, 19(3):385–410, 2010. konzepte, wie k-Anonymität [11], ist dies nicht gewährleis- tet. [9] Ronny Kohavi and Barry Becker. Adult Data Set. http://archive.ics.uci.edu/ml/datasets/Adult, 1996. zuletzt aufgerufen am 13.05.2015. 6. AUSBLICK [10] Tiancheng Li, Ninghui Li, Jian Zhang, and Ian Molloy. In dieser Arbeit stellten wir die Umsetzung des Slicing- Slicing: A new approach for privacy preserving data Ansatzes von Li et al. auf Basis der relationalen Algebra vor. publishing. Knowledge and Data Engineering, IEEE Dieses Anonymisierungsverfahren bietet einen guten Kom- Transactions on, 24(3):561–574, 2012. promiss zwischen Datenschutz und Analysefunktionalitäten [11] Pierangela Samarati. Protecting Respondents’ durch Minimierung des Informationsverlustes. Identities in Microdata Release. IEEE Transactions Anhand von linearen Regressionsanalysen wurde gezeigt, on Knowledge and Data Engineering, 13(6):1010–1027, dass das Slicing-Verfahren mit den Funktionalitäten von 2001. 29