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

Sachse, Steffen

Indizierung von häufigen Hypergraphstrukturen

Lichtwark, Martin

Meyer, Holger

Heuer, Andreas

The Mecklenburg Field Name Archive — Challenges in Crowd based Cataloging and Indexing

Der Einsatz von NoSQL/Graphdatenbanken und Crowd Sourcing am Beispiel des Mecklenburger Flurnamenarchives

Möller, Mark Lukas

Stromdatenverarbeitung für Data-Science-Anwendungen basierend auf Sensordaten

Einsatzmöglichkeiten von Crowdsourcing im Umfeld des Mecklenburgischen Flurnamenarchivs (Applications of Crowdsourcing in The Mecklenburg Field Name Archive)

Auge, Tanja

Umsetzung von Provenance-Anfragen in Big-Data-Analytics-Umgebungen

Crowd Sourcing in Digitalen Archiven

Directed hypergraphs are known from graph theory 11 and are well understood within their own domain 7--9, 22, 23. This paper provides an overview on the expressiveness of directed and typed hypergraphs as a modeling paradigm not only for the content of digital libraries and archives but a variety of applications. Furthermore, hypergraphs are sufficiently expressive to provide an implementation logic for conceptual models like CIDOC/CRM 18 in the context of museum-related systems and digital archives

Schering, Alf-Christian

The Hydra.PowerGraph System

Kluth, Johann

Verteidigung Bachelorarbeit
Eignung von Query
Containment-Techniken zur
Reformulierung von Anfragen bei der
datenschutzfreundlichen Gestaltung von
Informationssystemen
Johann Kluth
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK
Einleitung Zwischenstand Umsetzung Ende
Motivation
• Query Containment
• Datenbankanfragen beschleunigen
• Datenbankanfragen verteilen
• Anfrageergebnisse in Assistenzsystemen anonymisieren
→ Datenschutz einhalten
→ benötigte Daten bleiben erhalten
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 1
Einleitung Zwischenstand Umsetzung Ende
Übersicht
• Zwischenstand — Zusammenfassung
• Techniken
• MiniCon
• Umsetzung
• Implementierung
• Ergebnisse
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 2
Einleitung Zwischenstand Umsetzung Ende
Query Containment
Test zweier Anfragen auf Enthaltensein
Abbildung: Die Einordnung von QC im Anfrageprozessor des PArADISE-Projektes.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 3
Einleitung Zwischenstand Umsetzung Ende
Answering Queries using Views
Gegeben: Anfrage Q in KNF, Menge von Sichten V , auf Datenbank D .
Gesucht: Rewriting r(V ) = Q1 von Q
g
Anforderungen:
• möglichst vollständig die Sichten nutzen,
• möglichst wenig unterschiedliche Sichten nutzen (weniger Joins) und
• semantisch äquivalent zur originalen Anfrage sein.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 4
Einleitung Zwischenstand Umsetzung Ende
Answering Queries using Operators
Operatoren anstelle von Sichten nutzen: Anwendung in Assistenzsystemen
Gegeben: O = Menge möglicher Operatoren
Gesucht: Rewriting, welches eine Teilmenge der Operatoren aus O
nutzt. Anfragen liefern dann ein gefiltertes Ergebnis an den Server.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 5
Einleitung Zwischenstand Umsetzung Ende
Query Containment Problem
AQuV: @ Q‘ : Q1(D) @ Q‘(D) v Q(D)
AQuO: @ Q‘ : Q1(D) A Q‘(D) w Q(D)
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 6
Einleitung Zwischenstand Umsetzung Ende
Vergleich der Algorithmen
Algorithmen:
• Bucket
• MiniCon
• Inverse Rules
Kriterien:
• Allgemein
• Einsatzmöglichkeiten
• Laufzeiteffizienz
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 7
Einleitung Zwischenstand Umsetzung Ende
Vergleich der Algorithmen
Algorithmen:
• Bucket
• MiniCon
• Inverse Rules
Kriterien:
• Allgemein
• Einsatzmöglichkeiten
• Laufzeiteffizienz
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 7
Einleitung Zwischenstand Umsetzung Ende
MiniCon-Algorithmus
Ist eine Verbesserung des Bucket-Algorithmus, basiert daher auf diesem.
Q(x) = p1(x , y) ∧ p1(y , x) ∧ p2(x , y)
V1(a) = p1(a, b) ∧ p1(b, a)
V2(c , d) = p2(c , d)
V3(f , h) = p1(f , g) ∧ p1(g , h) ∧ p2(f , g)
Teilziele:
1. p1(x , y)
2. p1(y , x)
3. p2(x , y)
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 8
Einleitung Zwischenstand Umsetzung Ende
MiniCon-Algorithmus
MiniCon Description
h(vi ) h ϕ G
V2(c , d) c → c , d → d x → c , y → d 3
V3(f , f ) f → f , h→ f x → f , y → g 1, 2, 3
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 9
Einleitung Zwischenstand Umsetzung Ende
MiniCon-Algorithmus
1. Teilziel: p1(x , y)
Gefundene Sicht: V1(a) = p1(a, b) ∧ p1(b, a)
V1 widerspricht folgenden Bedingungen für eine MCD:
1. Die Sicht enthält in ihrem Kopf mindestens eine Kopfvariable der
Anfrage.
2. Wenn eine Variable der Anfrage in einem Verbund als Prädikat
vorkommt, dann:
2.1 muss derselbe Verbund auch in der Sicht vorkommen, oder
2.2 die Variable MUSS im Kopf der Sicht stehen.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 10
Einleitung Zwischenstand Umsetzung Ende
MiniCon-Algorithmus
1. Teilziel: p1(x , y)
Gefundene Sicht: V3(f , h) = p1(f , g) ∧ p1(g , h) ∧ p2(f , g)• V3 kann auch das 2. und 3. Teilziel abdecken (G = 1, 2, 3)
• Bedingungen für MCDs sind erfüllt
• Algorithmus läuft weiter, bis alle MCDs gefunden sind
Bemerkung: 2. Teilziel trivial.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 11
Einleitung Zwischenstand Umsetzung Ende
MiniCon-Algorithmus
3. Teilziel: p2(x , y)
Gefundene Sicht: V2(c , d) = p2(c , d)
• V2 deckt das Teilziel komplett ab + erfüllt Regeln
→ MCD wird übernommen
→ Algorithmus bricht ab, da alle MCDs gefunden sind
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 12
Einleitung Zwischenstand Umsetzung Ende
MiniCon-Algorithmus
Die gefundenen MCDs zu der Anfrage Q .
h(vi ) h ϕ G
V2(c , d) c → c , d → d x → c , y → d 3
V3(f , f ) f → f , h→ f x → f , y → g 1, 2, 3
Vorteil: Kein extra Test auf Containment notwendig (MiniCon garantiert
das von sich aus)
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 13
Einleitung Zwischenstand Umsetzung Ende
Wichtige Klassen
• MiniCon: Ausführung des Algorithmus
• MCD: Repräsentation einer MiniCon Description
• Query: Analyse einer SQL-Anfrage
• View: Analyse einer Sicht
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 14
Einleitung Zwischenstand Umsetzung Ende
Wichtige Funktionen
• checkFirstMiniConProperty:
• Prüfe erste Bedingung für eine MCD
• checkSecondMiniConProperty:
• Prüfe zweite Bedingung für eine MCD
• formingMCDs:
• Erstellt die MCDs aus Informationen der Sichtdefinition
• combiningMCD:
• Kombiniert die MCDs zu einem Rewriting der Anfrage
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 15
Einleitung Zwischenstand Umsetzung Ende
Testfälle
Datenbankschema (relevanter Ausschnitt):
Alle vorhandenen Sichten stehen auf S. 33 meiner Arbeit.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 16
Einleitung Zwischenstand Umsetzung Ende
Testfall 1 — Einfacher Fall
1. SELECT * FROM artists
text
Passende Sicht:
artview: SELECT id, name FROM artists
Rewriting:
• SELECT id, name FROM artview
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 17
Einleitung Zwischenstand Umsetzung Ende
Testfall 2 — Unmöglicher Fall
2. SELECT * FROM years
text
Kein Rewriting, da keine passende Sicht existiert, welche
auf die Relation ”years” zugreift.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 18
Einleitung Zwischenstand Umsetzung Ende
Testfall 3 — Teilmenge
3. SELECT * FROM composers
text
Passende Sicht:
containedset: SELECT id, name FROM composers WHERE id < 500
Rewriting:
• SELECT id, name FROM containedset
ACHTUNG: Ergebnismenge des Rewritings ist kleiner als die der
originalen Anfrage.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 19
Einleitung Zwischenstand Umsetzung Ende
Anforderungen
• Bei jedem Attribut muss der Relationenname mit angegeben werden.
• Anfrage muss eine SPJ-Anfrage in SQL-Notation sein. Vergleiche auf
Äquivalenz im WHERE-Teil erlaubt.
• Alle Sichten müssen komplett klein benannt werden und dürfen keine
kompletten Relationennamen enthalten.
• Datenbankmanagementsystem: PostgreSQL
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 20
Einleitung Zwischenstand Umsetzung Ende
Zusammenfassung der Arbeit
• Bucket-, MiniCon- und Inverse-Rules-Algorithmus
1. analysiert
2. vorgestellt
3. verglichen
• MiniCon implementiert und getestet
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 21
Einleitung Zwischenstand Umsetzung Ende
Ausblick
1. Chase & Backchase
2. Christian Langmacher: Vertikale Verteilung von SQL-Anfragen auf
DBMS-Servern abnehmender Leistungsfähigkeit.
3. Tanja Auge: Umsetzung von Provenance-Anfragen in
Big-Data-Analytics-Umgebungen.
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 22
Einleitung Zwischenstand Umsetzung Ende
ENDE
text
Fragen? Anmerkungen? Feedback?
18. September 2017 c© 2017 UNIVERSITÄT ROSTOCK | INSTITUT FÜR INFORMATIK 1 – 23


Eignung von Query Containment-Techniken zur Reformulierung von Anfragen bei der datenschutzfreundlichen Gestaltung von Informationssystemen

Awolin, Hannes

Verfahren zur Ermittlung von Integritätsbedingungen in NoSQL-Datenbanken

Not a member yet