Transcript
Drei Implementierungen der relationalen Algebra in Clojure Sören Gutzeit Fachbereich MNI
Gliederung ●
Relationale Algebra und Clojure
●
Auf Basis von Clojure Maps ○
●
Binary associated table Algebra ○
●
Vorlage: Bader und Incanter
Vorlage: Martin Kersten
Transrelational Model ○
Vorlage: Chris Date
Relationale Algebra und Clojure
Anforderungen der relationalen Algebra Relation und RelVar Warum Clojure?
Anforderung der relationalen Algebra ●
Relation != Tabelle ○ ○
Ein Tupel ist in der Relation, oder nicht. Keine vorgeschriebene Reihenfolge.
●
Eine Relation ist ein Wert.
●
(Hauptspeicher-orientiert)
Anforderung der relationalen Algebra ●
Operationen ○ ○ ○ ○ ○ ○ ○
●
Mengenoperationen Umbenennen Projektion Restriktion Verbundsoperation Gruppierung Aggregatfunktionen
Relation als Ergebnis. ○
Ausnahme: Aggregatfunktionen
int x = 5 Typ - Variable - Wert
Relation und RelVar ●
Eine Relation ist ein Wert. ○ ○
●
Relation werden nicht verändert. Durch Operationen entstehen neue/andere Werte.
Eine RelVar ist eine Variable. ○
RelVars können Relationen halten.
Warum Clojure? ●
Wunderschöne Sprache.
●
Immutable Data Stuctures ○ ○ ○
●
(fast) alles ist ein Wert. Werte werden nicht verändert. Operationen erstellen neue Werte.
refs ○ ○
Variablen in Clojure. Durch Transaktionen veränderbar.
Clojure Maps Basis (hashRel)
Vorlage: Bader und Incanter Datentyp Verwendung von clojure.set
Vorlage: Bader und Incanter ●
Core.relational ○ ○ ○
●
Masterthesis von Markus Bader, MNI, 2014. Darstellung von Tupeln durch Vektoren. umfangreiche Operationenmenge.
Dataset ○ ○ ○ ○
Incanter, R-like Statistik und Grafik Plattform. Darstellung von Tupeln durch Maps. mäßige Operatonsmenge. sehr performante Mengenoperationen.
xrel und clojure.set ●
Datenformat auch xrel genannt.
●
Einige Mengenoperstoren darauf ausgelegt. ○
index.
(clojure.set/index p #{ :gender })
Index Beispiel
Verbundoperator ●
Klassische Doppelschleife. ○ ○
●
Äußere und Innere Schleife für n*m Vergleiche. Sehr aufwendig.
Verwendung von index und HashMaps. ○ ○
Indizierung einer Relation mit n Tupeln plus m Hash-Aufrufe. Sehr effizient.
Demo 1
Binary associated table Algebra
Vorlage: Kersten Vertikale Fragmentierung Höhere und niedere Algebra
Binary associated table ●
Kurzform BAT Algebra.
●
Martin Kersten, Centrum Wiskunde & Informatica Amsterdam, 1970.
●
Spalten / Attribute -orientiert. ○
Vertikale Fragmentierung.
Vertikale Fragmentierung
Vertikale Fragmentierung ●
Teilung der Relation in BATs. ○
●
Jedes Attribute eine Tabelle.
Objekt-IDs als Fixpunkte. ○
jedes Tupel eine eindeutige oID.
BAT in Clojure ●
Menge statt Multimenge. ○
●
Binary Unit ~ BAT-Tupel. ○
●
Duplikate in BATs.
Bestehend aus :head und :tail.
Grundlegend alle Datentypen als Wert erlaubt. ○
Auch BATs.
Demo 2
BAT Algebra ●
Algebra bezogen auf Binäre Tabellen. ○ ○
●
Operationen im kleinen. Blick auf das Wesentliche.
Algebra niederer Stufe. ○
Übersetzung in höher Algebra
Operatoren
Vergleich SQL - BAT
Demo 3
Verbund-Operationen ●
Spielen (wie gesehen) eine große Rolle.
●
Freie Wahl der Vergleichsoperationen. ○
●
Konzept wie in hashRel auf Gleichheit ausgelegt. ○
●
=, !=, <, >=, ... , (fn[x] true)
wird dafür auch verwendet.
Für andere Vergleichsoperationen: Doppelschleife mit index. ○
minimiert Vergleiche.
100 Vergleiche
9 Vergleiche
Transrelational Model
Vorlage: Chris Date Trennung von Werten und Struktur
Transrelational Model ●
Kurzform TR.
●
Vorlage: Chris Date ○
●
Ursprung Stephen A. Tarin, US Patent, 1999
Trennung von Wert und Struktur in einer Relation
S#
SNAME
STATUS
CITY
1 S4
Clark
20
London
2 S5
Adams
30
Athens
3 S2
Jones
10
Paris
4 S1
Smith
20
London
5 S3
Blake
30
Paris
S#
SNAME
STATUS
CITY
1 S4
Clark
20
London
2 S5
Adams
30
Athens
3 S2
Jones
10
Paris
4 S1
Smith
20
London
5 S3
Blake
30
Paris
Original
S#
SNAME
STATUS
CITY
1 S1
Adams
10
Athens
2 S2
Blake
20
London
3 S3
Clark
20
London
4 S4
Jones
30
Paris
5 S5
Smith
30
Paris
Sortierte Werte
S#
SNAME
STATUS
CITY
1 S1
Adams
10
Athens
2 S2
Blake
20
3 S3
Clark
4 S4 5 S5
SNAME
STATUS
CITY
1 5
4
4
5
London
2 4
5
2
4
20
London
3 2
2
3
1
Jones
30
Paris
4 3
1
1
2
Smith
30
Paris
5 1
3
5
3
Field Value Table (FVT)
S#
Record Reconstruction Table (RRT)
S#
SNAME
STATUS
CITY
S#
1 S1
1 5
2
2
3
20
3
STATUS
CITY
3
1
4
4 5
London
SNAME
Smith Field Value Table (FVT)
5
3
Record Reconstruction Table (RRT)
Transrelational Model ●
Traversieren durch beide Tabellen. ○
●
ZigZag-Algorithmus
Tupel von beliebigen Punkt rekonstruierbar. ○
geschlossener Kreis.
●
“Schnelles Suchen, aufwendiges Schreiben.”
●
Duplikate schwer zu identifizieren.
●
Viel Spielraum für Optimierungen.
S#
SNAME
STATUS
CITY
1 S1
Adams
10
Athens
2 S2
Blake
20
London
3 S3
Clark
20
London
4 S4
Jones
30
Paris
5 S5
Smith
30
Paris S#
Optimierung: Konservierte Spalten
SNAME
STATUS
CITY
1 S1
Adams
10
Athens
2 S2
Blake
20
London
3 S3
Clark
30
Paris
4 S4
Jones
5 S5
Smith
S#
SNAME
STATU S
CITY
1 S1
Adams [1:1]
10 [1:1]
Athens [1:1]
2 S2
Blake [2:2]
20 [2:3]
London [2:3]
3 S3
Clark [3:3]
30 [4:5]
Paris [4:5]
4 S4
Jones [4:4]
S5
Smith [5:5]
5
Optimierung: Konservierte Spalten
S#
SNAME
STATUS
CITY
1 5
1∎4
1∎4
1∎5
2 4
2∎5
2∎2
2∎4
3 2
3∎2
2∎3
2∎1
4 3
4∎1
3∎1
3∎2
5 1
5∎3
3∎5
3∎3
Demo 4
Operationen ●
TR Basis. ○
●
Relationale Algebra. ○
●
Lesen, Einfügen, Löschen, Bearbeiten.
Projektion, Restriktion, Mengenoperationen.
Problem: Restriktion mit mehrfachen Bedingungen. ○ ○
Sehr aufwendige Implementierung. Optimierung der Operation.
Prädikat: (= S# “S3”)
S#
SNAME
STATUS
CITY
1 S1
Adams
10
Athens
2 S2
Blake
20
3 S3
Clark
4 S4 5 S5
SNAME
STATUS
CITY
1 5
4
4
5
London
2 4
5
2
4
20
London
3 2
2
3
1
Jones
30
Paris
4 3
1
1
2
Smith
30
Paris
5 1
3
5
3
Field Value Table (FVT)
Restriktion-Beispiel 1
S#
Record Reconstuction Table (RRT)
Prädikat: (and (>= STATUS 20) (or (= CITY “LONDON”) (= NAME “ADAM” ))) S#
SNAME
STATUS
CITY
1 S1
Adams
10
Athens
2 S2
Blake
20
3 S3
Clark
4 S4 5 S5
SNAME
STATUS
CITY
1 5
4
4
5
London
2 4
5
2
4
20
London
3 2
2
3
1
Jones
30
Paris
4 3
1
1
2
Smith
30
Paris
5 1
3
5
3
Field Value Table (FVT)
Restriktion-Beispiel 2
S#
Record Reconstuction Table (RRT)
Restriktion-Lösungsansätze (and
(intersection
( > :status 10)
( > :status 10)
(or
(union (<= :status 30)
(<= :status 30)
(= :city London)))
(= :city London)))
Restriktion-Lösungsansätze (intersection
(intersection
( > :status 10)
(area-search > :status 10)
(union
(union
(<= :status 30)
(area-search <= :status 30)
(= :city London)))
(point-search :city London)))
Demo 5
Fazit
Fazit ●
HashRel ○ ○ ○
●
BAT ○ ○
●
Einfaches Konzept. Unterstützung durch Clojure-Mechaniken. wenig weitere Optimierungsmöglichkeiten. Operieren im kleinen. Viel Optimierungsmöglichkeiten. ■ Oberschicht für höhere Algebra. ■ Auch für größere Verwendung.
TR ○ ○ ○
Komplexes Konzept. ■ umfangreiche Operationen. Viel Optimierungsmöglichkeiten. ■ siehe Restriktion. Von große Datenmengen auf kleine schließen
Vielen Dank für Ihre Aufmerksamkeit! https://github.com/seegy/more.relational
Fragen?
