REFLEXIVE DATENBANKEN

Dr. Klaus Peters

BIOGRAPHIE (1/3)

Geboren 1962, 1988 Mathematik-Studium, Humboldt-Universität 1990 Promotion 1990-1994 Lehre und Forschung in Berlin, Bonn,

Wuppertal 1994-1995 Institut für Biochemie der HU; Design,

Implementierung und Test diskreter geometrischer Algorithmen zur Untersuchung der räumlichen Struktur von Proteinen

BIOGRAPHIE (2/3)

1996-1998 Chefredakteur des Lexikons der Mathematik; Konzeption zur Erstellung des Lexikons, Auswahl der Stichwörter; Koordination der Themen, Autoren und Zuarbeiten

1998-2009 DResearch GmbH; Beratung, Management und Software–Entwicklung; verantwortlicher Entwickler des Teilprojektes Installation und Update der @vantage Plattform und @vantage Komponenten auf SUN Clustersystemen und verteilten Systemen; Softwareverwaltungs- und Softwareausliefungssysteme

BIOGRAPHIE (3/3)

Seit 2009 DResearch GmbH; Entwicklung von Webapplikationen im eGovernment-Bereich; Installation, Konfiguration, Dokumentation, Entwicklung von automatischen Testumgebungen, Anwender-Schulungen für eGovernment-Projekte, Weiterentwicklung einer Bezahlplatform für sächsische Behörden und Gemeinden

Seit 2009: Vorlesung zu Mathematik 1, 2 und 3 an der HTW für den Bachelor-Studiengang Computer Engineering

Homepage: http://home.htw-berlin.de/~peterskl E-Mail: peterskl@htw-berlin.de

AGENDA

Motivation

Modellierung

Beispiele

Abfragen

Diskussion

Summary

Modellierung und Beschreibung von Beziehungen zwischen Entitäten gleichen Typs

Modellierung und Beschreibung von rückbezüglichen Beziehungen

Entität

s

r

MOTIVATION

FRAGESTELLUNGEN

Wo treten solche Reflexionen in der Praxis auf?

Welche Arten von Reflexionen gibt es? Welche Probleme gibt es bei reflexiven

Beziehungen? Wie werden sie in einem DBMS

abgebildet? Wie werden Abfragen programmiert,

die mit dem vorhandenen SQL nicht abgebildet werden können?

BEISPIELE

Wer ist der Vorgesetzte eines Mitarbeiters?

Welcher Bearbeiter vertritt wen? Welches ist die nächste Haltestelle

eines Busses? Welche Vorlesungen sind für eine

Vorlesungen Voraussetzung?

Wie können solche Beziehungen modelliert werden?

MODELLIERUNG

Motivation

Modellierung

Beispiele

Abfragen

Diskussion

Summary

GRAPHEN

Definition: Ein (gerichteter) Graph ist ein Paar (E,K) (E – Ecken/Knoten), K- Kanten/Verbindungen), wobei K eine Menge Paaren von Ecken ist: KEE.

Für eine Ecke heißen diejenigen Kanten, die diese Ecke als erstes Element haben, ausgehende Kanten, die anderen heißen eingehende Kanten.

BEISPIEL FÜR GRAPHEN

A

B D

C

E

BÄUME

Definition: Ein Baum ist ein zusammenhängender Graph ohne Kreise, beim dem genau eine Ecke (die Wurzel) nur ausgehende Kanten hat und alle anderen Ecken genau eine eingehende haben.

BEISPIEL FÜR BÄUME

A

E

C

F

DB

G H

Definition: Eine Liste ist ein Baum, beim dem jeder Knoten nur maximal eine ausgehende Kante hat.

Jeder Knoten hat maximal einem Vorgänger und maximal einen Nachfolger.

LISTEN

BEISPIEL FÜR LISTEN

A C

D

B

BEISPIELE

Motivation

Modellierung

Beispiele

Abfragen

Diskussion

Summary

PersonalNr Nachname Vorname

1 Müller Peter

2 Meier Clara

3 Lehmann Thomas

4 Schulze Hans

5 Schröder Andreas

6 Heinrich Beate

Die Ausgangsdaten (Tabelle „Mitarbeiter“):

DIE BEZIEHUNG „VORGESETZTER“

5. Andreas Schröder

3. Thomas Lehmann

1. Peter Müller

6. Beate Heinrich

2. Clara Meier

4. Hans Schulze

DIE BEZIEHUNG „VORGESETZTER“ ALS BAUM

… ALS DATENBANKTABELLE

Die zusätzliche Spalte „Vorgesetzter“ stellt einen Schlüssel auf die Tabelle selbst dar: mc:c-Beziehung

PersonalNr Nachname Vorname Vorgesetzter

1 Müller Peter 5

2 Meier Clara 5

3 Lehmann Thomas 4

4 Schulze Hans 1

5 Schröder Andreas

6 Heinrich Beate 2

DIE BEZIEHUNG „VERTRETER FÜR“

PersonalNr Nachname Abteilung

1 Müller Nordeuropa

2 Meier Nordeuropa

3 Lehmann Südosteuropa

4 Schulze Südosteuropa

5 Schröder Mitteleuropa

6 Heinrich Südosteuropa

Die Ausgangsdaten (Tabelle „Bearbeiter“):

5. Andreas Schröder

3. Thomas Lehmann

1. Peter Müller

6. Beate Heinrich

2. Clara Meier

4. Hans Schulze

DIE BEZIEHUNG „VERTRETER FÜR“ ALS GRAPH

…ALS DATENBANKTABELLE

PersonalNr Nachname Abteilung VertreterFuer

1 Müller Nordeuropa 2

2 Meier Nordeuropa 1

3 Lehmann Südosteuropa 4

4 Schulze Südosteuropa 6

5 Schröder Mitteleuropa

6 Heinrich Südosteuropa 3

Die zusätzliche Spalte „VertreterFuer“ realisiert die c:c Beziehung als Schlüssel auf sich selbst.

DIE BEZIEHUNG „NÄCHSTE HALTESTELLE“

StationsNr Station

1 Nordbahnhof

2 Badstraße

3 Schlossstraße

4 Seeallee

Die Ausgangsdaten (Tabelle „Stationen“):

3. Schlossstraße

4. Seeallee

2. Badstraße

1. Nordbahnhof

DIE BEZIEHUNG „NÄCHSTE HALTESTELLE“ ALS LISTE

ALS DATENBANKTABELLE

StationsNr Station naechsteStation

1 Nordbahnhof 4

2 Badstraße 1

3 Schloßstraße

4 Seeallee 3

Die zusätzliche Spalte „naechsteStation“ realisiert als Schlüssel auf sich selbst die c:c-Beziehung.

Die Ausgangsdaten (Tabelle „Vorlesungen“):

DIE BEZIEHUNG „BENÖTIGTE VORLESUNG“

VNr Vorlesung

1 Zahlen

2 Folgen

3 Reihen

4 Differentialrechnung

DIE BEZIEHUNG „BENÖTIGTE VORLESUNG“ ALS GRAPH

1. Zahlen

4. Differential-rechnung

2. Folgen

3. Reihen

BEZIEHUNG „VORLESUNG“

Id Vorlesung noetigFuer

1 1 2

2 1 3

3 1 4

4 2 3

5 2 4

Die Abhängigkeit zwischen den Vorlesungen wird als mc:mc-Beziehung durch eine zusätzliche Tabelle mit zwei Schlüsseln auf die Vorlesungstabelle realisiert.

VNr Vorlesung

1 Zahlen

2 Folgen

3 Reihen

4 Differentialrechnung

DEFINITION

Eine reflexive Datenbank ist eine Datenbank, bei der wenigstens eine Tabelle (reflexive Tabelle) eine Beziehung auf sich selber hat.

PROBLEM DER REFLEXIVEN DATENBANKEN

Relation zwischen gleichartigen Entitäten

Abfragen werden schnell zu Ketten von Abfragen

Zyklen sind möglich Modellierender Graph kann

unzusammenhängend sein Ketten von Abfragen könnten schwierig

zu beantworten sein

DATENBANKABFRAGEN

Motivation

Modellierung

Beispiele

Abfragen

Diskussion

Summary

ABFRAGEN

Wer ist der Chef einer Abteilung? Welche Mitarbeiter muss ich maximal

vertreten? Wird eine bestimmte Haltstelle vor

einer anderen angefahren? Welche Vorlesungen sind insgesamt

Voraussetzungen für eine bestimmte Vorlesung?

NÜTZLICHE SQL-STATEMENTS

Kartesisches Produkt WITH-Klausel IN-Klausel START WITH … CONNECT BY-Klausel

AUSGANGSDATEN (BEZIEHUNG „VORGESETZTER“)ID Name Abteilung Vorgesetzter

1 Albrecht a1 11

2 Beier a1 1

3 Conrad a1 12

4 Dietz a1 2

5 Engel a1 2

6 Fischer a1 2

7 Gericke a1 3

8 Holz a1 3

9 Ingold a1 5

10 Junge a1 5

11 Kurz a2 0

12 Lorenz a1 11

5

…ALS GRAPH

11

4

1

8

2 3

6 7

9 10

12

Abfrage: Wer ist der oberste Chef in der Abteilung vom Mitarbeiter Engel?

KARTESISCHES PRODUKTSELECT ma1.name, ma2.name chef FROM Ma ma1, Ma ma2 WHERE

ma1.vorgesetzter = ma2.id;NAME Chef--------- --------Albrecht KurzBeier AlbrechtConrad LorenzDietz BeierEngel BeierFischer BeierGericke ConradHolz ConradIngold EngelJunge EngelLorenz Kurz

WITH-KLAUSEL

WITH n AS(SELECT ma1.name, ma2.name chef FROM Ma ma1, Ma ma2 WHERE ma1.vorgesetzter=ma2.id) SELECT name, chef FROM n ORDER BY chef;

NAME CHEF-------- --------Beier Albrecht Fischer BeierDietz BeierEngel BeierHolz ConradGierke ConradIngold EngelLorenz KurzAlbrecht KurzConrad Lorenz

IN-KLAUSELSELECT name,id,vorgesetzter FROM Ma WHERE id IN (SELECT vorgesetzter FROM Ma WHERE id='5');

NAME ID VORGESETZTER----- -- ------------Beier 2 1

SELECT name,id,vorgesetzter FROM Ma WHERE id IN (SELECT vorgesetzter FROM Ma WHERE id IN (SELECT vorgesetzter FROM Ma WHERE id='5'));NAME ID VORGESETZTER-------- -- ------------Albrecht 1 11

Mit der IN-Klausel können wir nur eine endliche Tiefe des Baumes erfassen.

START WITH …CONNECT BY-KLAUSEL (1/2)

SQL> select lpad(' ',level+1)||name name, id from ma start with id='5' connect by prior vorgesetzter=id;

NAME ID------------ -- Engel 5 Beier 2 Albrecht 1 Kurz 11

START WITH …CONNECT BY-KLAUSEL (2/2)

SELECT level, name, sys_connect_by_path(name,'/') name_path FROM ma WHERE id = '5' CONNECT BY NOCYCLE PRIOR id=vorgesetzter order by level;

LEVEL NAME NAME_PATH ----- ----- -------------------------- 1 Engel /Engel 2 Engel /Beier/Engel 3 Engel /Albrecht/Beier/Engel 4 Engel /Kurz/Albrecht/Beier/Engel

Nicht jedes DBMS unterstützt solche Befehle.

PROGRAMME

Abfragen über Programmiersprachen realisieren (Java, C#, VBA, PLSQL)

Rekursivität wird benötigt. Abbruchkriterien einfügen

WER IST DER CHEF EINER ABTEILUNG?

public Knoten getWurzelInAbt(Mitarbeiter m, long id) {Knoten k = m.getKnoten(id);Abteilung a = k.getAbteilung();

if(k.getVorgesetzter() == null || b.getKnoten(k.getVorgesetzer).getAbteilung() != a) {

return k;} else {

return getWurzelInAbt(m, m.getKnoten(k.getVorgesetzter).getId();

}}

WELCHE MITARBEITER MUSS ICH MAXIMAL VERTRETEN?

public Knoten[] getAlleVertretene(Bearbeiter b, long id) {Knoten k0 = b.getKnoten(id);k=k0;Knoten[] vertretene = null;while (k.getVertreterFuer()!=null &&

k.getVertreterFuer() != k0) {k=k.getVertreterFuer();

vetretene.add(k);}return vetretene;

}

WIRD EINE BESTIMMTE HALTSTELLE NACH EINER ANDEREN ANGEFAHREN?

public Boolean isNachfolgendeHS(Stationen s, long id1, long id2) {Knoten k1 = s.getKnoten(id1);Knoten k2 = s.getKnoten(id2);Knoten k = k1;while (k.getNaechsteHS()!= null &&

k.getNaechsteHS()!= k2) {k=k.getNaechsteHS();

};return (k == k2)

}

WELCHE VORLESUNGEN SIND INSGESAMT VORAUSSETZUNGEN FÜR EINE BESTIMMTE VORLESUNG?

public Knoten[] getAlleBenoetigteV(Vorlesungen v, long id) {

Knoten[] alleBenoetigteV = null; Knoten[] benoetigteV = v.getBenoetigtFuer(id);

if ( benoetigteV !=null ) { alleBenoetigteV.addListUnique(benoetigteV); for (i=0; i<benoetigteV.size(); i++) { alleBenoetigteV.addListUnique( getAlleBenoetigteV(v, benoetigteV[i].getId)));

}return alleBenoetigteV;

DISKUSSION

Motivation

Modellierung

Beispiele

Abfragen

Diskussion

Summary

FRAGEN

Kann man in den Beispielen auf die Reflexivität verzichten?

Was sind die Vorteile? Was sind die Nachteile? Wie würde man ein komplexes

Liniennetz mit mehreren Stationen und mehreren Buslinien realisieren?

ZUSAMMENFASSUNG

Motivation

Modellierung

Beispiele

Abfragen

Diskussion

Summary

SUMMARY 1/2

reflexive relations can be modelled by graphs (trees or lists or nets)

reflexive relations lead to chains of request chains of request are mapped to find paths

from one node of the graph to another node modelling graph may contain cycles or may

be not connected

SUMMARY 2/2

reflexive relations can be represented in the database via additional key columns (one-to-many or one-to-one many-to many relations)

SQL statements support reflexive relations for chains of requests recursivity and abort

conditions are necessary For more complicate request we have to use

program interfaces

Vielen Dank! Fragen?