Universität Rostock, Lehrstuhl Datenbank- und Informationssysteme: Dbis Repository

Grunert, Hannes

Heuer, Andreas

Datenschutz im PArADISE

Tepke, Jan

Damerius, Christoph

Steffenhagen, Hannes

  
NeidI – Privacy
Gruppe “Oben”
  
Anforderungen
●  Local Server:
– Komplexe Aggregate, 
OVER, PARTITION BY, 
etc.
● Home Media Center:
– Einfache Aggregate, 
AVG, MIN, etc.
● Ziel: möglichst viel nach 
unten schieben 
→ Privacy
–
  
Architektur Query 
Transformation
Parser
Zwischenrepräsentation
Query
         QueryTransformer
PushDown Query (In ZR)Remaining Query (In ZR)
ExpressionSplitter LayerNo
-split FROM list
-partition SELECT list
-split WHERE
ExpressionToID-
Converter
 To SQL  To SQL
  
SQL Parser
simple_select_stmt returns [SimpleSelectStmt result]
 : K_SELECT v1=set_quantifier v2=result_columns
   v3=optional_from_list
   v4=optional_where_clause
   v5=optional_group_by_clause
   v6=optional_ordering_terms {$result = new 
SimpleSelectStmt($v1.result, $v2.result, $v3.result, 
$v4.result, $v5.result, $v6.result);}
 ;
set_quantifier returns [Option<SetQuantifier> result]
 : K_DISTINCT {$result = 
Option.apply(DISTINCT$.MODULE$);}
 | K_ALL {$result = Option.apply(ALL$.MODULE$);}
 | {$result = Option.apply(null);}
 ;
● Übersetzt SQL Quelltext in Scala Zwischenrepräsentation
● In ANTLRv4 implementiert
● SELECT x,y 
FROM z 
WHERE x = y
SimpleSelectStatement(Nothing,
   List(ResultColumn(ColumnName(„x“),Nothing,Nothing),
          ResultColumn(ColumnName(„y“),Nothing,Nothing)),
   List(TableExpression(Table(„z“)),
   Some(BinOp(„=“,ColumnName(„x“),ColumnName(„y“))),
   Nothing,
   Nil)
–
  
Query Transformation
● Teile FROM Listen (NATURAL JOINS)
– Framework Call: Tabelle ist auf Layer → bleibt
● Tabelle ist nicht auf Layer → nach 
unten schieben
SELECT * FROM TAB1 NATURAL JOIN TAB2
remote_table ← SELECT * FROM TAB2
SELECT * FROM TAB1 NATURAL JOIN remote_table
–
  
Query Transformation
● Teile Projektionsliste
split(e:Expr) => (Expr,List[ResultColumn])
● Extrahiere so viele Sub-Expressions wie möglich
● Ersetzen von Sub-Expressions durch ColumnNames (Hash-Wert von 
Sub-Expression)
● Außerdem referentielle Layer Transparenz
→ Auf ColumnNames muss projiziert werden, falls nicht auf aktuellem 
Layer vorhanden und Expression nicht nach unten geschoben werden 
darf.
● Nur FunctionCalls, die auf unteren Layern unterstützt werden, können 
nach unten geschoben werden.
● Aggregat vor OVER Klausel muss auf Local Server Layer verbleiben
  
Query Transformation
● WHERE wird als Expression behandelt → analog zu 
Projektionsliste
● Spezielle Behandlung für Konjunktionen
– - Teil-Terme extrahieren und nach unten schieben 
wenn möglich
– - Abspaltung von Klauseln die nach unten 
geschoben werden können
– →Frühere Filterung von Zeilen → Privacy  
–
  
Query Transformation
● Beispiel Sensor
SELECT MIN(sensor.time), 
     AVG(sensor.x + sensor.y) AS avg_sy,
     AVG(sensor.x + sensor.y) OVER(PARTITION BY sensor.key)
FROM sensor
WHERE ((sensor.i + sensor.j) < 20) AND 
    (sensor.time BETWEEN 1 AND 10)
Split
  
Query Transformation
● Beispiel Sensor: Split auf Local Server Ebene
remote_table ← SELECT (MIN(sensor.time) )  AS 
id_56e75d9e,
       (AVG((sensor.y + sensor.x)) )  AS id_b6e62d57, 
       sensor.x  AS id_d2404843, 
       sensor.y  AS id_ea386849, 
       sensor.key  AS id_6b4c67f9
FROM sensor  
WHERE (((sensor.i + sensor.j) < 20) AND 
      (sensor.time  BETWEEN 1 AND 10)) 
SELECT id_56e75d9e, id_b6e62d57 AS avg_sy,      
  (AVG((id_d2404843 + id_ea386849))) 
    OVER (PARTITION BY id_6b4c67f9) 
FROM remote_table
  
Query Transformation
● Beispiel Sensor: Split auf HMC Ebene
remote_table ← SELECT (sensor.y + sensor.x)  AS 
id_acdbc907, 
sensor.time  AS id_5d283dd0,
sensor.x  AS id_d2404843,
sensor.y  AS id_ea386849,
sensor.key  AS id_6b4c67f9
FROM sensor  
WHERE (((sensor.i + sensor.j) < 20) AND 
(sensor.time BETWEEN 1 AND 10)) 
SELECT (MIN(id_5d283dd0) )  AS id_56e75d9e,
(AVG(id_acdbc907) )  AS id_b6e62d57,
id_d2404843 AS id_d2404843,
id_ea386849 AS id_ea386849,
id_6b4c67f9 AS id_6b4c67f9
FROM remote_table
  
Query Transformation
● Beispiel Multi-Layer
SELECT sensor.y + analytics.geo_location AS 
sy_plus_geo,
cloud_meta.aws_user * (sensor.x + sensor.y) AS 
magic_hash
FROM sensor NATURAL JOIN analytics 
NATURAL JOIN cloud_meta
WHERE cloud_meta.aws_acl = 'admin' OR 
analytics.time_zone = 'UTC+1'
Split
  
Query Transformation
● Beispiel Multi-Layer: LocalServer Split
remote_table ← SELECT 
(sensor.y + analytics.geo_location)  AS id_254f6e78,
 (sensor.x + sensor.y)  AS id_f209090c, 
(analytics.time_zone = 'UTC+1')  AS id_01aeb1ae 
FROM (sensor NATURAL JOIN analytics)
SELECT id_254f6e78 AS sy_plus_geo,
(cloud_meta.aws_user * id_f209090c)  AS 
magic_hash
FROM (cloud_meta  NATURAL JOIN remote_table)  
WHERE ((cloud_meta.aws_acl = 'admin') 
OR id_01aeb1ae)
  
Query Transformation
● Beispiel Multi-Layer: HMC Split
remote_table ← SELECT 
(sensor.x + sensor.y)  AS id_f209090c,
sensor.y  AS id_ea386849
FROM sensor
SELECT 
(id_ea386849 + analytics.geo_location)  AS id_254f6e78,
id_f209090c AS id_f209090c,
(analytics.time_zone = 'UTC+1')  AS id_01aeb1ae 
FROM (analytics  NATURAL JOIN remote_table)
  
Datenbank Anbindung (Konzept)
● Derzeitig nur für PostgresSQL
Client
Query
Query Transformer
DB
Push Down Query  
DB with
Remote table
Remaining Query
  
Datenbank Anbindung (Implementierung)
● Auf Datenbankseite: Extension pljava (erlaubt 
Implementierung)
● Copy Remote Table Funktion anlegen, Parameter: 
Datenbankverbindung, Query, Tabellenname.
● Führt Query aus.
● Iteriert über das ResultSet und Column-Handler-
Chain.
● Legt Ergebnistabelle an.
  
Demo
  
Ausblick (Offene Probleme)
● Kombination aus INNER JOIN und NATURAL JOIN nicht kommutativ
● GROUP BY nicht trivial transformierbar (abhängig von Aggregat)
● ORDER BY ändert Semantik wenn Reihenfolge der Ordering Terms 
verändert wird
● Set Quantifier 
● Aufspalten von Projektionsliste in Aggregat- und nicht Aggregat-Teil
● Substituierte Namen dürfen bestimmte Länge nicht überschreiten 
→ Hash
● Umbenennung von Tabelle mit Alias funktioniert noch nicht.
● Anbindung an PArADISE noch nicht vollständig
● Berücksichtigt noch keine Nutzer privacy policies 
  
NeidI – Privacy
Gruppe “Oben” Fragen?


NeidI – Privacy Gruppe "Oben" (Home Media Center & Lokler Server)

Krause, Tjark

Datenmigration in Data-Warehouses: Konzeption und Entwicklung eines Prozesses zur Transformation von Star- bzw. Snowflake-Schemen zu Data Vault

Nösinger, Thomas

XML-Schemaevolution - Änderung eines XML-Schemas mit automatisierter Adaption assoziierter XML-Dokumente

Wegener, Paul

Auswahl und Evaluierung von Data Mining Verfahren zur Bewertung von Kundendaten

Wächter, Felix

Haufschild, Martin

PArADISE 
S&A-Level
Felix Wächter, Martin Haufschild
1
Gliederung
Aufgaben
Teilnehmer
HMC, Appliance, Sensor
Anmerkungen und Festlegungen
Protokoll
Abläufe
Anforderungen
Nachrichtenformat
Code
Fragen
2
Aufgaben
3
Aufgaben
Anfragen von oben 
HMC → Appliance
Umschreiben und Verteilen von Anfragen
Appliance → Sensoren
Prozessieren von Anfragen
Sensoren
Appliance
Zusammenführen von Ergebnissen
4
Teilnehmer
5
Teilnehmer - Home Media 
Center
ortsfest über längeren Zeitraum
im Netzwerk
Verbindung mit Local Server
relativ hohe Leistungsfähigkeit
lange Uptime
<SQL-Standard hier einfügen>
Bsp.:
PC
NUC
Spielekonsole
6
Teilnehmer - Appliances
mobil
“kommen und gehen”
begrenzte Leistungsfähigkeit
unvorhersehbare Uptime
unterstützen BerkeleyDB/ SQLite, MongoDB, U1DB, … 
Bsp.:
Android/ iOS/ Tizen/ … 
Phones, Tablets, Wearables, TVs
(teilweise nur dokumentenorientierte DBs (Ubuntu Phone)
7
Teilnehmer - Sensoren
Geräte zur Datenerfassung
Aktivität über größere Zeiträume
TinyDB (oder gar keine DB)
Bsp.: 
Kameras
Rasberry Pi (“DIY-Geräte”)
Heizungssteuerungen
Lichtschalter
Bewegungssensoren
… 
8
Teilnehmer - Anmerkungen
haben vier Hierarchiestufen (LS, HMC, A, S)
weitere Differenzierung auf jeder Stufe notwendig
Bsp.: HMC
NUC → eher stationär
PS4 → wird schon eher aus dem Netzwerk entfernt
Bsp.: Appliances
Android → SQLite 
Ubuntu Phone → U1DB (dokumentenorientiert, JSON)
9
Teilnehmer - Anmerkungen
Kriterien für die Einteilung in Geräteklassen:
Rechenleistung
verfügbarer SQL-Standard/ DB-Technologie
Fähigkeiten (z.B. verfügbare Sprachen)
Vertrauen in Plattform/ Gerät
Erweiterbarkeit
Verweildauer im Netzwerk
durchschnittliche Uptime
Belastung (durch andere Anwendungen)
10
Teilnehmer - Anmerkungen
Plattform Sprachen Datenbanken
Android Java, C/C++ SQLite
iOS Objective-C, Swift SQLite, Core Data
Tizen Javascript, C SQLite, ActiveRecord.js, 
MiniMongo (kommt mit 
Blaze Library)
Ubuntu Phone HTML5, QML U1DB
Firefox OS Javascript keine (?) LocalStorage
11
Teilnehmer - Anmerkungen
Geräteklasse Rolle Mobilität 
im Haus
Verweildauer 
im Netzwerk
Kontrolle über Daten
Laptop HMC, 
Appliance
gering mittel
Spielekonsole HMC, 
Appliance
gering lang
SmartTV Appliance gering lang
Phone/ Tablet Appliance, 
Sensor
hoch mittel bis kurz
SmartWatch Sensor* hoch kurz
* Wearables können u.U. direkt in die DB des Companion-Devices schreiben 12
Teilnehmer - Festlegungen
Beschränkung auf Einteilung in Sensoren und Appliances
Sensor
TinyDB
Python3
Raspberry Pi
Appliance 
BDB, SQLite 
Python3, Java
NUC, Laptop oder Smartphone
13
Teilnehmer - Festlegungen
Einbettung in einfachen Lifecycle
- Anmeldung im Netzwerk
- Betrieb (Anfrageverarbeitung)
- Abmeldung vom Netzwerk
14
Protokoll
15
Protokoll - Gliederung
Annahmen
Anforderungen
Logik/ Handlungssequenzen
Protokollspezifikation
Kommentar und Ausblick
16
Protokoll - Annahmen
einfacher Lifecycle
Sensor, Appliance, HMC wie bereits beschrieben
bestehendes (TCP/IP) Netz
kein Handover 
Geräte verschwinden nicht einfach
→ Sensor und Appliance führen ihr individuelles Setup 
durch und treten anschließend miteinander in Kontakt. 
Eine eventuell durchzuführende Discovery-Phase wird 
übersprungen. 
17
Protokoll - Anforderungen 
Sensor-Appliance-Communication (SAC):
Anmeldung des Sensors bei der Appliance
Abmeldung des Sensors von der Appliance
Deassoziierung des Sensors von Seiten der Appliance
Anfrage von Appliance an Sensor
Übermittlung von Sensordaten an die Appliance
Appliance-HMC-Communication (AHC):
De-/ Assoziierung von Appliance und HMC
Query Transmission
Result Set Transmission
18
Protokoll - Logik
19
Protokoll - Logik
20
Protokoll - Logik
21
Protokoll - Logik
22
1) HMC sendet Query
2) HMC erhält Token 
3) Appliance legt Tabelle für QueryResult an
4) Appliance schreibt die Anfrage um
5) Appliance sendet Anfragen an Sensoren
6) Sensoren führen Anfragen durch
7) Sensoren liefern Ergebnisse bei 
Appliance ab
23
Begründung:
- HMC blockiert nicht
- Ausfall/ lahmer Sensor wenig 
problematisch
- weniger Last auf Appliance
- HMC kann auch schon Teile des 
ResultSets holen
- Daten können schon verarbeitet werden 
(Appliance, HMC) bevor alle Anfragen 
durch sind
24
Protokoll - Spezifikation
Nachrichten im JSON-Format
zweiteilig
1. Nachrichtentyp
2. Daten
25
Protokoll - Spezifikation
Nachrichtentyp:
beschreibt Vorgang/Aktion
“QUERY”, “REGISTRATION”, “CONFIRMATION”, … 
Daten:
für den jeweiligen Vorgang notwendige Informationen
Anfrage an Sensor → QueryID & Anfrage
26
Protokoll - Spezifikation
27
Protokoll - Spezifikation
28
Protokoll - Spezifikation
29
Protokoll - Spezifikation
30
Protokoll - Spezifikation
31
Protokoll - Spezifikation
32
Implementierung
33
SQL-TO-TinyDB-Wrapper
 Sensor-Ebene nur mit TinyDB-DBMS ausgestattet
 TinyDB mit JSON-Format und nur mit Python-Schnittstelle
 Konvertierung der SQL-Anfragen von Appliance-Ebene in die Python-
Schnittstelle nötig
 Wrapper deshalb in Python programmiert unter Nutzung von Lamda-
Ausdrücken
 Fähigkeiten des Wrappers:
 nur SELECT-Anfragen für eine Relation verarbeitbar
 nur Attribut-Wert-Vergleiche im WHERE-Teil durch .search()-Aufruf 
von TinyDB. Auch kein WHERE-Teil möglich.
 beliebig tiefe Klammerungen und logische Verknüpfungen (and, or, 
not) im WHERE-Teil
 Projektionen auf beliebige und beliebig viele Attribute (ohne Rel.) 
durch map. Auch Wildcard (*) möglich.
 Bsp.: SELECT a, b FROM tabelle WHERE a<2 or (a>5 and b==4)
SQL-TO-TinyDB-Wrapper
 Wrapper erweiterbar um
 Attribut-Attribut-Vergleiche durch filter
 Aggregationen (SUM, AVG), MIN, MAX durch map und reduce
 Projektionen auf Operationen von Attributen, z.B. SELECT 2*Col_A 
FROM Tabelle 
 Wrapper nutzt sqlparse-Modul von Python und traversiert dann dessen 
Syntaxbaum
 Wrapper-Aufruf:
 execfile(SQLToTinyDB.py) (existiert nur in Python2)
 SQLToTinyDB(<SQL_String>) gibt String für TinyDB-Tabelle zurück
 eval(SQLToTinyDB(<SQL_String>)) führt TinyDB-Anfrage aus
 Ergebnis des Wrapper-Aufrufs im JSON-Format. Noch Konvertierung zu 
ResultSet für JDBC-Treiber nötig.
Fragen ?
36


PArADISE Sensor- & Appliance-Level

Auge, Tanja

Ringvorlesung:
Forschung @ DBIS
Tanja Auge
Wintersemester 16/17
1 Die vier P
Social-Networks wie Facebook und Twitter, Forschungseinrichtungen wie das
”
Euro-
pean Council for Nuclear Research“, kurz CERN und Log-Analysen im Web oder von
Sensoren produzieren eine Unmenge an zu verarbeitenden Daten. Dieses Datenvolumen,
ihre große Vielfalt sowie die Geschwindigkeit der Datenverarbeitung werden hierbei un-
ter dem Begriff Big Data zusammengefasst. Die Bezeichnung Big Data wird i.A. fu¨r
Datenvolumina verwendet, die so umfangreich sind, dass sie nur schwer mit klassischen
Mitteln verarbeitet werden ko¨nnen [11]. Zur Charakterisierung werden die folgenden
vier Eigenschaften unterschieden (siehe Abbildung 1.1a):
• Data at Rest (Volume): Verwaltung großer Datensammlungen
• Data in Motion (Velocity): Unmittelbare Verarbeitung der Datenstro¨me
• Data in Many Forms (Variety): verschiedene Datentypen
• Data in Doubt (Veracity): Unzuverla¨ssigkeit oder Unsicherheit der Daten
(a) Die 4 V: Volume, Velocity, Variety und
Veracity
(b) Die 4 P: Privacy, Preservation, Paral-
lelization und Provenance
Abbildung 1.1: Vom Ergebnis zur Daten-Herkunft
Bei der Analyse von Big Data in Assistenzsystemen ko¨nnen vier Schwerpunkte gesetzt
werden (siehe Abbildung 1.1b):
• Privacy: Privatheit / Datenschutz
• Preservation: Langzeitarchivierung der Daten
• Parallelization: Effiziente Analyse auf großen Datenmengen
• Provenance: Herkunft der Daten
2
Privacy
Das Ziel der Privacy-Analyse besteht in der Gewa¨hrleistung der Privatheit der Nutzer
von Assistenzsystemen: Systeme, die im Hintergrund laufen und den Nutzer in seinen
Anwendungen unterstu¨tzen, zum richtigen Zeitpunkt eingreifen und Hilfe auf akusti-
schem oder optischem Weg anbieten. Assistenzsysteme sind vertrauenswu¨rdig, diskret
und ko¨nnen bei Bedarf abgeschaltet werden. Einen Abgleich der Ziele des Assistenz-
systems gegen die Privatheitsanspru¨che des Nutzers auf Basis der Anonymisierungs-
eigenschaften von Daten sind Gegenstand des Langzeitprojektes PArADISE (Privacy
AwaRe Assistive Distributed Information System Environment) [5].
Preservation
Die Langzeitarchivierung von Daten ist ein langwieriger und zeitaufwendiger Prozess.
Analoge Medien wie Bu¨cher, Pergament oder Ho¨hlenmalereien - um nur einige zu nen-
nen - ko¨nnen eine
”
Haltbarkeit“ von bis zu 500 Jahren aufweisen. Eine a¨hnlich lange
digitale Archivierung kann durch Bilder oder die Verfilmung der Daten erreicht werden.
An der Universita¨t Rostock werden diese hochvernetzten Dokumentmengen mit Hilfe
von typisierten, gerichteten Hypergraphen im Rahmen des Langzeitprojektes HyDRA
(a HYpergraph of Documents in a Relational Archive) modelliert. Forschungsgegen-
stand sind hier unter anderem die Anfrageverarbeitung und -optimierung sowie die
Dokumentmodellierung und -speicherung [5].
Parallelization
Die Parallelisierung von Big Data Analytics wird ebenfalls im Projekt PArADISE un-
tersucht. Ziel ist eine automatische Transformation in SQL, um die SQL-Anfrage an-
schließend zu optimieren und hochgradig zu parallelisieren. So ko¨nnen die Datenban-
kanfragen weiter optimiert und eine gro¨ßere Daten- und Transaktionssicherheit erreicht
werden [10].
Provenance
Das Langzeitprojekt METIS (Management, Evolution, Transformation und Integrati-
on von Schemata) vereint die Verfahren zur Integration, Transformation und Evolution
von Daten. Auch die Frage der Datenherkunft wird in diesem Projekt untersucht [5].
Schwerpunkte einer Provenance-Untersuchung wa¨ren beispielsweise die Rekonstruie-
rung einer Datenbankanfrage oder die Nachvollziehbarkeit einer (wissenschaftlichen)
Aussage [7].
3
2 Provenance
Das Wort provenance stammt aus dem englischen Sprachgebrauch und bedeutet wo¨rt-
lich u¨bersetzt Herkunft oder Ursprung [3]. Im Sinne der Informatik bescha¨ftigt sich das
Provenance Management mit der Ru¨ckverfolgbarkeit eines Ergebnisses bis zu den rele-
vanten Originaldaten. Anwendung findet dieses Management etwa in der Interpretation
von Statistiken, der Analyse von Wahlergebnissen oder Umfragen sowie experimentellen
Auswertungen [7].
Provenance-Anfragen und -Antworten:
Provenance-Anfragen:
• where-Anfrage: Woher kommen die Daten?
• why-Anfrage: Warum dieses Ergebnis?
• how-Anfrage: Wie kommt das Ergebnis zustande?
• why not-Anfrage: Warum fehlt ein bestimmtes Element im Ergebnis?
Provenance-Antworten [8]:
• extensionale Antwort:
Tupel aus den Originaldaten → Antwort auf where- oder why-Anfrage
• intensionale Antwort: Beschreibung der Daten
• anfragebasierte Antwort:
Selektionspra¨dikate → Antwort auf why- und how-Anfragen
• modifikationsbasierte Antwort:
Vorschlag zur minimalen A¨nderung der Auswertung
→ Antwort auf why not-Anfrage
Typischerweise werden sowohl vier Provenance-Anfragen als auch vier Provenance-
Antworten unterschieden. Die ersten drei Anfragen ko¨nnen dabei bzgl. ihres Informati-
onsgehalt wie folgt geordnet werden: where ⊂ why ⊂ how. Wa¨hrend die where-Anfrage,
im Falle einer extensionalen Antwort, lediglich die Namen der beno¨tigten Tabellen
wiedergibt, liefert die how-Anfrage eine konkrete Berechnungsvorschrift in Form eines
Provenance-Polynoms [2].
4
Provenance-Halbringe
Ein Provenance-Halbring ist ein kommutativer Halbring (K,+, ·, 0, 1) mit
• K: Menge der Tupelidentifikatoren (jedes Tupel der Ausgangsdatenbank hat einen
eindeutigen Tupelidentifikator),
• (K,+): kommutative Halbgruppe mit neutralem Element 0 (entspricht der Ver-
einigung oder Projektion (ohne Duplikate)),
• (K, ·): kommutative Halbgruppe mit neutralem Element 1 (entspricht dem natu¨r-
lichen Verbund),
• Distributivgesetz:
∀x, y, z ∈ K : [(x + y) · z = x · z + y · z] ∧ [z · (x + y) = z · x + z · y].
Jedem Ergebnistupel einer Provenance-Anfrage kann ein eindeutiges Provenance-Poly-
nom bestehend aus den Tupelidentifikatoren der Quelltupel zugeordnet werden. Diese
ko¨nnen durch die Verwendung von K-Semimodulen um Aggregate wie MIN, MAX,
AVG, SUM und COUNT erweitert werden [1].
Experimente in der Biologie [4]:
Die Anwendung von Provenance Management soll im Folgenden kurz anhand des
Leibniz-Instituts fu¨r Ostseeforschung in Warnemu¨nde erla¨utert werden. Durch diverse
Messungen, Analysen und Simulationen werden eine Vielzahl heterogener biologischer,
chemischer, physikalischer und numerischer Daten erzeugt, die anschließend im Rahmen
des Forschungsdatenbankenmanagements langfristig gespeichert und verwaltet werden
sollen. Fragen nach der Herkunft der Daten, ihrer Relevanz und der Rekonstruierbarkeit
von Ergebnissen ko¨nnen nun mit Hilfe von Provenance-Fragen beantwortet werden. So
kann beispielsweise bei der Messung des Sauerstoffgehalts der Ostsee (siehe Abbildung
2.1) gezielt nach dem rot eingerahmten Ausreißer gefragt werden. Die Provenance-
Antwort hierauf kann sowohl intensional als auch extensional erfolgen.
Abbildung 2.1: Why-Provenance am Beispiel des Sauerstoffgehalts der Ostsee
5
3 Offenes Problem
Ein unter Privacy-Aspekten gutes Assistenzsystem speichert nur Daten, die die Pri-
vatheit des Nutzers nicht verletzen. Provenance-Anfragen wu¨rden hier in der Regel
eine intensionale, d.h. beschreibende, Antwort liefern; eine extensionale Antwort wi-
derspricht gro¨ßtenteils den Privacy-Aspekten. Eine automatische Rekonstruktion der
Originaldaten, kann sich in solchen Fa¨llen allerdings als schwierig herausstellen. Die
hierfu¨r no¨tigen inversen Schemaabbildungen werden zwar bzgl. ihrer Eigenschaften un-
tersucht und im Bereich der Schema-Evolution erfolgreich angewendet, ko¨nnten aber
auch in der Provenance-Analyse von Nutzen sein [6].
Ein offenes Problem im Bereich der Rekonstruierbarkeit besteht beispielsweise in der
Berechnung dieser inversen Abbildungen durch
”
Rettung“ von Annotationen. Sei dazu
zuna¨chst eine Datenbank eines Fitness-Studios d(S) wie folgt gegeben:
• P1: Person (1234, Max Mustermann, Mitarbeiter)
• P2: Person (1234, Max Mustermann, Sportler)
• K1: Kursbelegung (1234, Bauch-Beine-Po)
• K2: Kursbelegung (1234, Ru¨cken-Fit)
• K3: Kursbelegung (1234, Kettlebell)
Eine Anfrage nach den Teilnehmern des Kurses Bauch-Beine-Po liefert nun Max Mus-
termann sowohl als Mitarbeiter als auch als Sportler im Rahmen einer extensionalen
Antwort. Formal entspricht dies den Zeugen {P1,K1} und {P2,K1}.
Ein Zeuge ist ein Tupel in T = {t1, ..., tn}, der Menge der Ergebnistupeln ti einer
Anfrage q1 auf die Quelldatenbank d(S). Die why-Provenance von t ∈ T entspricht nun
der Zeugenmenge T selbst. In obigem Beispiel bedeutet dies fu¨r das Tupel t = {P1,K1}:
why(t) = T, denn die Anfrage q1 = ”
Teilnehmer des Kurses Bauch-Beine-Po“ liefert
gerade T = {{P1,K1}, {P2,K1}}.
Rekonstruierbar ist eine Anfrage q1 also fu¨r die von den Zeugen T = {t1, ..., tn} aufge-
spannte Teildatenbank dW der Quelldatenbank d(S). Das METIS-Projekt verfolgt nun
die Idee, die Annotationen dA zu retten, so dass T = q
−1
2 (t ∪ dA). Fu¨r den Fall, dass
die Annotationenmenge gerade der von den Zeugen aufgespannten Teildatenbanken dW
entspricht - also einer erhaltenden Transaktion - folgt die Rekonstruierbarkeit automa-
tisch und es gilt q−12 = q
−1
1 . Andernfalls handelt es sich bei q2 um eine Pseudoinverse
und es stellt sich die Frage, nach einer sta¨rkeren Einschra¨nkung von dA?
6
Betrachten wir erneut das obige Beispiel erweitert um die folgenden Personen und
Kursbelegungen:
• P3 : Person (1235, Paul Paulchen, Mitarbeiter)
• P4 : Person (1236, Peter Petersen, Sportler)
• P5: Person (1237, Simon Simonson, Mitarbeiter)
• P4: Kursbelegung (1235, Ru¨cke-Fit)
• K5: Kursbelegung (1236, Bauch-Beine-Po)
• K6: Kursbelegung (1237, Bauch-Beine-Po).
Die Anfrage q3 = ”
Wie viele Mitarbeiter nehmen am Bauch-Beine-Po-Kurs teil?“ liefert
die Zahl 2. Dabei kan die Annotationenmenge wie folgt reduziert werden:
• P1: Person (1234, Max Mustermann, Mitarbeiter) ⇒ P ′1 = (a, Mitarbeiter)
• P5: Person (1237, Simon Simonson, Mitarbeiter) ⇒ P ′5 = (b, Mitarbeiter)
• K1: Kursbelegung (1234, Bauch-Beine-Po) ⇒ K ′1 = (a)
• K6: Kursbelegung (1237, Bauch-Beine-Po) ⇒ K ′6 = (b)
Die exakte Identifikationsnummer ist eventuell nicht relevant oder darf aufgrund von
Privacy-Aspekten nicht vero¨ffentlicht werden; sie kann aber durch eine eindeutige Va-
riable ersetzt werden. Der Name des Mitarbeiters ist fu¨r die obige Anfrage irrelevant
und der Kursname bereits in der Anfrage enthalten. Die Annotationenmenge kann also
auf dA = {P ′1, P ′5,K ′1,K ′6} reduziert werden.
7
Literaturverzeichnis
[1] Y. AMSTERDAMER, D. DEUTCH, V. TANNEN: Provenance for Aggregate Queries,
Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Prin-
ciples of database systems, pp. 153–164, 2011
[2] T. AUGE, S. BROSSMANN, P. WILSDORF: Endpra¨sentation ProSA-Gruppe, Neueste
Entwicklungen in der Informatik, Pra¨sentation, SoSe 16/17
[3] P. HEMETSBERGER : Deutsch-Englisch-Wo¨rterbuch,
http://www.dict.cc/?s=provenance, 07.03.2017
[4] A. HEUER : Digitale Bibliotheken und Multimedia-Retrieval, Lehrstuhl fu¨r
Datenbank- und Informationssysteme, Vorlesungsskript, WiSe 16/17
[5] A. HEUER : Langzeitprojekte, Lehrstuhl fu¨r Datenbank- und Informa-
tionssysteme, https://dbis.informatik.uni-rostock.de/forschung/
langzeitrahmenprojekte/, 2017
[6] A. HEUER : METIS in PArADISE: Provenance Management bei der Auswertung
von Sensordatenmengen fu¨r die Entwicklung von Assistenzsystemen, Datenbanksys-
teme fu¨r Business, Technologie und Web (BTW 2015) - Workshopband, 2.-3. Ma¨rz
2015, Hamburg, Germany, 2015
[7] A. HEUER : Neueste Entwicklung in der Informatik - Motivation, Lehrstuhl fu¨r
Datenbank- und Informationssysteme, Vorlesungsskript, SoSe 16
[8] A. HEUER : Neueste Entwicklung in der Informatik - Provenance, Lehrstuhl fu¨r
Datenbank- und Informationssysteme, Vorlesungsskript, SoSe 16
[9] A. HEUER : Theorie relationaler Datenbanken, Lehrstuhl fu¨r Datenbank- und Infor-
mationssysteme, Vorlesungsskript, SoSe 16
[10] A. HEUER : Ringvorlesung: Forschung @ DBIS, Lehrstuhl fu¨r Datenbank- und
Informationssysteme, Vorlesungsskript, WiSe 16/17
[11] INNOVATION IS FREEDOM : OVH Big Data,
https://www.ovh.de/dedicated_server/HG/big-data-glossar.xml,
05.03.2017
8


Ringvorlesung: Forschung @ DBIS

Weu, Dennis

Erkennung, Übersetzung und parallele Auswertung von Operatoren und Funktionen aus R in SQL

oai:eprints.dbis.informatik.uni-rostock.de:14By the events in the past years, the integration of data protection mechanisms into information systems becomes a central  research  problem  again. In this poster, we show  how query rewriting can be used to maintain privacy of users in smart (or assistive) environments.  We developed a privacy respecting query processing and a vertical fragmentation of queries,  processing maximal parts of the query as close to the sources of the data (e.g.  sensors) as possible

Privacy Protection through Query Rewriting in Smart
Environments ∗
Hannes Grunert
Database Research Group
University of Rostock
18051 Rostock, Germany
hg(at)uni-rostock.de
Andreas Heuer
Database Research Group
University of Rostock
18051 Rostock, Germany
ah(at)uni-rostock.de
ABSTRACT
By the events in the past years, the integration of data pro-
tection mechanisms into information systems becomes a cen-
tral research problem again. In this poster, we show how
query rewriting can be used to maintain privacy of users in
smart (or assistive) environments. We developed a privacy
respecting query processing and a vertical fragmentation of
queries, processing maximal parts of the query as close to
the sources of the data (e.g. sensors) as possible.
Categories and Subject Descriptors
H.2.4 [Database Management]: Systems—Query Pro-
cessing ; K.4.1 [Computer and Society]: Public Policy
Issues—Privacy
General Terms
Privacy Enhancing Technologies, Database Systems
1. PRIVACY
Smart Metering, Internet surveillance, motion profiles, bio-
metric databases, data retention: In the digital world steadily
more and more information about ourselves and our envi-
ronment is collected. Besides “classical” personal informa-
tion, such as the name, age or gender, a plurality of sensors
records our activities and inclinations. Active and passive
RFID tags, cameras, microphones, but also sensors on light
switches and power sockets capture the current situation in
the ubiquitous environments, up to 100 times per second.
Especially smart environments such as assistive systems
using activity and intention recognition [4] are a possible
cause of privacy violations, especially if the query realizing
the recognition analysis is performed on a cloud server.
To reduce privacy violations, it is necessary
∗A full version of this paper is available as a Technical Re-
port at www.ls-dbis.de/digbib/dbis-tr-cs-01-16.pdf
c©2016, Copyright is with the authors. Published in Proc. 19th Inter-
national Conference on Extending Database Technology (EDBT), March
15-18, 2016 - Bordeaux, France: ISBN 978-3-89318-070-7, on OpenPro-
ceedings.org. Distribution of this paper is permitted under the terms of the
Creative Commons license CC-by-nc-nd 4.0
Figure 1: The concept of the privacy-aware query-
processor.
• to decrease collected personal information, i.e. to ap-
ply the principle of data avoidance (except where data
are required),
• to process data with personal references as less as pos-
sible or — at least — as close to the local data sources
(sensors) as possible and
• to anonymize, pseudonymize and delete personal data,
unless it is used for further processing and necessary
to realize the aim of the assistive environment.
Data minimization and data avoidance are therefore pre-
scribed, indispensable requirements for the design of smart
systems. This requirement can be achieved in databases by
transforming both queries and query results, as well as using
views [3].
2. PRIVACY-AWAREQUERYPROCESSING
The PArADISE1-approach aims to withdraw the burden
of respecting privacy constraints from the assistive systems
by adding privacy protection mechanisms to those systems
storing and analyzing the data: database systems on differ-
ent levels. PArADISE combines performance aspects of big
data analytics (by using massively parallel database technol-
ogy [5]) and privacy protection. Our privacy-aware query-
processor (see Figure 1) generates anonymized result sets.
These data maintain a high degree of value for the initial
query generated by the assistive system. On the opposite,
additional knowledge can hardly be derived.
1Privacy Aware Assistive Distributed Information System
Environment
Poster Paper
 
 
Series ISSN: 2367-2005 708 10.5441/002/edbt.2016.98
The preprocessor allows the analysis and the rewriting of
database queries regarding user-defined privacy policies [2].
During the execution of the request, it is decided whether
the request will be answered and anonymized directly on
the current network peer, or is sent to lower nodes (vertical
fragmentation, see below). The postprocessor executes the
anonymization of the query results, taking into account var-
ious criteria of quality and privacy. For this, several data
protection metrics and algorithms are provided. The mod-
ule for the automatic generation of privacy settings produces
and adapts existing user-defined privacy policies to new de-
vices and changing requirements and queries.
3. QUERY REWRITING BY VERTICAL
FRAGMENTATION
The smart environment or assistive system sends a query
request Q to the database d integrating the entire sensor
data recorded in our environment. The result of Q is needed
to perform the activity and intention recognition. The data
sources are sensors being located in appliances in apartments
and buildings. Instead of shipping d to the cloud server
sending the request, maximal parts of Q will be evaluated
as close to the sensor as possible. As can be seen in Fig-
ure 2, instead of performing Q(d) in the cloud, the maximal
subquery Qj will be shipped to the next lower node of the
processing chain, in the case of the example a PC located
in our apartment. While Q performs an iterative machine
learning algorithm implemented in R and SQL, and Qj be-
ing a complex SQL query with recursion, the lowest node in
the processing chain (the sensors) can only compute some
filter mechanisms (simple selections) and some simple ag-
gregations over the last values generated (window function:
average of last minute). Each of the nodes will ship the
query result dj to the node sending the request. After a fi-
nal anonymization step A, the data “leaving our apartment”
d′ will only be a small subset of the original data d.
We assume that the lower nodes will each have less query
computing power than the higher nodes: while sensors are
only performing simple filters / selections and aggregations,
an appliance like a TV or a smart network music player will
be able to perform simple (SQLsuperlight) database queries,
an Android-based home media server even more complex
SQL queries.
The whole query processing procedure
Q(d) := dj = Qj(. . . d
′
i = A(di = Qi(. . . (d1 = Q1(d)) . . . )
is transformed in a way, that the cloud server will perform
a remainder query Qδ on d
′ instead of performing Q on
d, hence resulting in the privacy protecting query rewriting
Q(d) −→ Qδ(d′). In other words, the query Q is fragmented
in queries Qj (that can be performed at a lower node) and
a remainder query Qδ that can only performed at the more
powerful node of our vertical fragmentation of query proces-
sors.
Since recognizing the maximal SQL queries in an R ma-
chine learning algorithm is undecidable in general, we try to
detect some larger “SQLable” patterns in the activity and
intention recognition procedures described in [4]. Other as-
pects of our privacy-aware query-processor are described in,
e.g. [1].
By rewriting the query Q into Qj and Qδ and only per-
forming Qδ outside our “privacy protected” appliance en-
Figure 2: Vertical Query Fragmentation: Query and
query result transformation on different peers.
semble in our apartment, we hope to automatically prevent
the service provider of our assistive system to use our per-
sonal data in a way we did not consider to be possible when
starting to use his smart service. A remaining open prob-
lem is to decide whether a privacy-violating query Q↓ can be
performed even on d′ instead of d. In this case, we have to
extend the anonymization step A already performed. This
open problem results in a query containment problem of
Q,Q↓ and Qj that will be part of our further research.
4. ACKNOWLEDGMENTS
Hannes Grunert is funded by the German Research Foun-
dation (DFG), Graduate School 1424 (Multimodal Smart
Appliance Ensembles for Mobile Applications - MuSAMA).
The authors gratefully acknowledge the constructive com-
ments of the anonymous referees.
5. REFERENCES
[1] H. Grunert. Distributed denial of privacy. In
INFORMATIK 2014: Big Data Komplexita¨t meistern,
pages 2299–2304. Springer, 2014.
[2] H. Grunert and A. Heuer. Generating privacy
constraints for assistive environments. In Proceedings of
the 8th International Conference on PErvasive
Technologies Related to Assistive Environments,
PETRA 2015. ACM, 2015.
[3] A. Heuer and A. Lubinski. Data reduction - an
adaptation technique for mobile environments. In
Interactive Applications of Mobile Computing
(IMC’98), 1998.
[4] F. Kru¨ger, M. Nyolt, K. Yordanova, A. Hein, and
T. Kirste. Computational State Space Models for
Activity and Intention Recognition. A Feasibility
Study. PLOS ONE, Nov. 2014. 9(11): e109381.
doi:10.1371/journal.pone.0109381.
[5] D. Marten and A. Heuer. A framework for
self-managing database support and parallel computing
for assistive systems. In Proceedings of the 8th
International Conference on PErvasive Technologies
Related to Assistive Environments, PETRA 2015.
ACM, 2015.
709


Privacy Protection through Query Rewriting in Smart Environments

Tessnow, Christian

Evaluierung einer Datenmigrationssoftware hinsichtlich des TPC-DI-Benchmarks

Not a member yet