Post on 09-Mar-2016
description
transcript
Principles of Distributed Database
Systems
ausgearbeitet von
Rainer Steinlesberger 0026446
EinleitungDDBS = Netzwerk von Computern (Sites) + Datenbank
DDBS = Verteilung + Integration
+
=
Netzwerk Datenbank
DDBS
Übersicht1. Einleitung2. Was ist ein DDBS?3. Überblick über relationale DBMS4. Computer Netzwerke5. Architektur von DBMS6. Design einer verteilten
Datenbank
Geschichtlicher RückblickEnde der 60er Anfang der 70er ging man zunehmend dazu über Datenbanksysteme zu benutzen, um
•die Datenunabhängigkeit der Anwendungsprogramme zu erhöhen,•transaktionsorientierte Verarbeitung zu ermöglichen,•Mehrbenutzerbetrieb zu realisieren,•sowie die Recovery-Funktionen zu verbessern.
Entstehen von Rechenzentren, wodurch die Betriebsorganisation zentralisiert wurde!
Die Datenmenge wuchsen immer weiter an zusammengehörende Datenbestände wurden auf verschiedene Datenbanken verteilt.
Dadurch entstanden Probleme mit der Konsistenthaltung der Daten.
In den 80iger und 90iger Jahren konnten durch Onlineanwendungen bislang getrennteAnwendungen und Datenbestände zusammengeführt werden.
Desshalb
wurden integrierte verteilte Informationssysteme realisiert.
Definition„A distributed database is a collection of multiple, logically interrelated databases distributed over a computer network. A distributed database management system is the software that permits the management of the DDBS and makes the distribution transparent to the users.“
Zentrale Datenbankin einem Netzwerk
CommunicationNetwork
Boston
ParisSan
Francisco
Edmonton
Verteilte Datenbankstruktur
CommunicationNetwork
Boston
ParisSan
Francisco
Edmonton
•Boston Angestellte
•Paris Angestellte
•Boston Projekte
•Paris Angestellte
•Paris Projekte
•Boston Angestellte
•Boston Projekte
•Edmonton Angestellte
•Paris Projekte
•Edmont Projekte
•San Francisco Angestellte
•San Francisco Projekte
Transparentes Management
• Datenunabhängigkeit• Netzwerk Transparenz• Replizierungs- bzw. Kopiertransparenz• Fragmentierungstransparenz
Verbesserte Leistung• Ein DBMS teilt die Datenbank und erlaubt es den Daten
somit sehr sehr nahe ihrem Ort, wo sie gebraucht werden, gespeichert zu werden.dies hat 2 Vorteile:
1. Seit jeder Knoten einen Teil der Daten bewältigt, ist der Kampf um Ressourcen wie CPU nicht mehr so wichtig wie in zentralisierten Datenbanken
2. Lokalisierung vermindert die Verzögerung bei entfernten Aufrufen
Probleme• Verteiltes Datenbank-Design• Verteilte Suchprozesse• Verteiltes Verzeichnis-Management• Verteilte Konkurrenzkontrolle• Verteiltes Deadlock Management• Betriebssystem-Unterstützung• Heterogene Datenbanken
3. Relationale DBMS
Relationen• Def.: in Beziehung stehend....• Relationen sind 2dimensonale Tabellen von
Werten
1. NormalformO------------------------------------------------------------------------------------------------O| Vorlesungen | Verantwortliche | Hörer | Bewert. |
O------------------------------------------------------------------------------------------------O| Vorl.Nr. | Vorl.Name | Hörs. | Vorn. | Nachn. | Nr. | Vorn. | Nachn. | Matr.Nr. |Note
|O------------------------------------------------------------------------------------------------O|
|| 3721 | Informatik | HS1 | 130 | Alan | Kurow | 102 | Fritz | Maier | 8610826 | 2 || 3721 | Informatik | HS1 | 130 | Alan | Kurow | 102 | Fritz | Müller | 8510721 | 5 || 3721 | Informatik | HS1 | 130 | Franz | Girke | 108 | Fritz | Maier | 8610826 | 3 || 3721 | Informatik | HS1 | 130 | Franz | Girke | 108 | Fritz | Müller | 8510721 | 4 || 3721 | Informatik | HS1 | 130 | Franz | Girke | 108 | Hans | Schuh | 8610933 | 1
O----------------------------------------------------------------------------------------------------O| Vorlesungen | Verantwortliche | Hörer | Bewert.
|O----------------------------------------------------------------------------------------------------O|
Vorl.Nr. | Vorl.Name | HS | HS-Gr. | Vorn. | Nachn. | Nr. | Vorn. | Nachn. | Matr.-Nr. | Note
|O----------------------------------------------------------------------------------------------------O|
3721 | Informatik | HS1 | 130 | Alan | Kurow | 102 | Fritz | Maier | 8610826 | 2 3721 | Informatik | HS1 | 130 | Alan | Kurow | 102 | Fritz | Müller | 8510721 | 5 3721 | Informatik | HS1 | 130 | Franz | Girke | 108 | Fritz | Maier | 8610826 | 3 3721 | Informatik | HS1 | 130 | Franz | Girke | 108 | Fritz | Müller | 8510721 | 4 3721 | Informatik | HS1 | 130 | Franz | Girke | 108 | Hans | Schuh | 8610933 | 1
2. NormalformDie 2. Normalform vermeidet partielle funktionale Abhängigkeiten (diese
bewirken Redundanzen). Eine partielle funktionale Abhängigkeit besteht, wenn Attribute (die nicht Schlüsselkandidaten sind) funktional schon von einem Teil des Schlüssels abhängen. Die zweite Normalform kann durch Elimination der abhängigen Attribute und Auslagerung in eine eigene Relation erreicht werden.
Der Primärschlüssel besteht aus dem Attributetupel (Vorlesungsnummer, Verantwortlichennummer, Matrikelnummer)
Wir zerlegen nun die Relation in vier Relationen, die dann in 2. Normalform sind.
2. NormalformO-------------------------------------------O| V.-Nr. | Ver.-Nr. | Matr.-Nr. | Bewertung |O-------------------------------------------O||| 3721 | 102 | 8610826 | 2|| 3721 | 102 | 8610721 | 5 || 3721 | 108 | 8610826 | 3 || 3721 | 108 | 8610721 | 4 || 3721 | 108 | 8610933 | 1
O------------------------------------O|
Hörsaal
V.-Nr. | V.-Name | Bez. | Größe |
O------------------------------------O|
3721 | Informatik | HS1 | 130 |
3722 | Informatik | HS4 | 140 |
O-------------------------------O
| Ver.-Nr. | Vorname | Nachname
|O------------------------------O
102 | Alan | Kurow |
108 | Franz | Girke |
O----------------------------------O|
Matr.-Nr. | H.-Vorn. | H.-Nachn. |
O----------------------------------O|
8610826 | Fritz | Maier |
8610721 | Fritz | Müller |
8610933 | Hans | Schuh |
3. Normalform
O-------------------------------------------O|V.-Nr. | V.-Name | Hörsaal-Bezeichnung |O-------------------------------------------O|3721 | Informatik | HS13722 | Informatik | HS4 || : | : | : |
O-------------------------------------O|Hörsaal-Bezeichnung | Hörsaal-Größe |O-------------------------------------O|HS1 | 130 HS4 | 140 || : | : |
Eine Relation ist in dritter Normalform, wenn sie in 2. Normalform ist und es kein Attribut, welches nicht Teil des Schlüssels ist, gibt, welches transitiv vom Schlüssel abhängt.
O------------------------------------O|
Hörsaal
V.-Nr. | V.-Name | Bez. | Größe |
O------------------------------------O|
3721 | Informatik | HS1 | 130 |
3722 | Informatik | HS4 | 140 |
Relationale Daten Sprache
• Relationale AlgebraVerknüpft konstruktiv die vorhandenen Relationen durch
Operatoren wie ∩,∪,...• Relationaler Kalkulus
Beschreibt Eigenschaften des gewünschten Ergebnisses mit Hilfe einer Formel der Prädikatenlogik 1. Stufe unter Verwendung von ∀,∃,∨,∧,¬,...
Relationale Algebra• Selection• Projection• Union• Set Difference• Cartesian Product• Intersection• ..........
Einige Beispiele...
• Selection Semester>10(Studenten)
• ∏Name(Studenten) ...... Projektion
• ∏Name (Studenten) ∪ ∏Name(Professoren) (2 Relationen mit gleichem Schema)
• ∏Name (Studenten) - ∏Name(Geprüft) (2 Relationen mit gleichem Schema)
Relationaler Kalkulus• Tupelkalkül
{t | F(t)} {p|p ∈ Professoren ٨ p.Alter =
‚35’}
• Bereichskalkül{[v1, v2,..., vn] | P(v1, v2,..., vn)}
4. Netzwerk
4. Netzwerk
Topologien im Überblick...
OSI-Referenzmodell
5. Architektur von DBMS
5. Architektur von DBMS
Die Idee hinter dem ANSI/SPARC Modell ist die Datenunabhängigkeit der Daten gegenüber Veränderungen der Speicherstrukturen.
Das DBMS ist eine Schnittstelle zu den Daten.
Architekturmodell
Architektur von DBMS
•Client - Server Architektur
•Verteilte Datenbank Architektur
•Multi Datenbank Architektur
Client/Server Architektur
Hier gibt es typischerweise einen zentralen Datenbank-Server und eine größere Anzahl vernetzter Arbeitsplatzrechner, die keine relevanten Daten speichern. Der Benutzer am Arbeitsplatzrechner sieht die volle Funktionalität des DBMS. Das System verhält sich wie ein zentrales Datenbanksystem, die Kommunikation ist für den Benutzer transparent
Verteiltes Datenbanksystem
• Hier gibt es mehrere Datenbankserver, wobei bestimmte Daten auf nur einem Rechner oder auch auf mehreren (replizit) gespeichert sein können.
• Eine virtuelle Datenbank, deren Komponenten physisch in einer Anzahl unterschiedlicher, real existierender DBMS abgebildet werden.
• Transaktionen können in diesem Fall über mehrere DBMS laufen.• Sammlung von Daten, die
– Aufgrund gemeinsamer, verknüpfender Eigenschaften dem gleichen System angehören
– Auf versch. Rechnern im Netzwerk verteilt sind– Wobei jeder Rechner seine eigene Datenbank besitzt– Autonom lokal Aufgaben abwickeln kann
Verteiltes Datenbanksystem
- gleichzeitige Benutzung der Rechenleistung mehrerer Rechner
- Engpaß in zentralen Datenbanksystemen bei Zugriff auf die Daten wird vermieden, da die Daten verteilt sind (ggf. repliziert)
- Daten werden von einem Datenbanksystem verwaltet- Verteilungstransparenz- Grundlage: 4-Ebenen-Schema-Architektur
Verteiltes Datenbanksystem
4 - Ebenen - Schema - Architektur
externes Schema 1 externes Schema N
konzeptionelles Schema
lokales konzept. Schema
lokales konzept. Schema
lokales konzept. Schema
lokales internes Schema
lokales internes Schema
lokales internes Schema
. . .
. . .
. . .
Multidatenbanksystem- Ein MDBS ist ein Verbund von mehreren
Datenbanksystemen.- Das Konzeptionelle Schema repräsentiert nur den
Teil von Daten, den die lokalen DBMS teilen wollen.
- Auf jedes DBS können lokale Anwendungen zugreifen.
- Jedes DBS kann Daten enthalten, welche keine Beziehung zu Daten anderer DBS haben.
Multidatenbanksystem
Modell mit globalem konzeptionellem Schema
LES LES LES LES LES LES
GES GES GES
GKS
LKS 1 LKS n
LIS 1 LIS n
...
...
Multidatenbanksystem
Modell ohne globales konzeptionelles Schema
ES 1 ES 2 ES 3
LKS 1 LKS 3
LIS 1 LIS 3
LKS 2
LIS 2
MDB-Schicht
Lokale System -Schicht
6. Design
6. DesignEntwurfsmethodik• top-down: von den Anforderungen zum Systementwurf;
geeignet für Neuentwicklungen.• bottom-up: Integration bestehender Datenbanken zu einer
verteilten; typisch bei heterogenen Datenbanken.Datenverteilung• Fragmentierung der Daten zur Bildung logischer Einheiten,• Verteilung der Fragmente auf den Sites: Allokation aller Fragmente
an jeder Site (volle Replikation) oder jedes Fragment an mehr als einer Site (partielle Replikation) oder jedes Fragment an genau einer Site (Partitionierung).
Die Trennung von Fragmentierung und Allokation dient der Vereinfachung des Entwurf.
• Globales Schema: Definition der Relationen eines vDBS ohne Berücksichtigung der Verteilung,
• Fragmentierungsschema: Definition der Abbildung zwischen globalen Relationen und Fragmenten,
• Allokationsschema: Definition der Abbildung zwischen Fragmenten und Sites.
Der Zugriff zu den Daten soll hinsichtlich Fragmentierung, Lokation, und Replikation transparent sein.
R1
R2
R3
R4
R1,1
R2,1
R1,2
R2,2
R3,3R4,3
Globale Relation
Fragmente
Allokation an den Sites
S1
S2
S3
Fragmente und ihre Allokation
R
Beispiel: JNO JNAME BUDGET LOC
J1 Instrumentation 150000 Montreal
J2 DatabaseDevelop. 135000 New York
J3 CAD/CAM 250000 New York
J4 Maintenance 310000 Paris
JNO JNAME BUDGET LOC
J1 Instrumentation 150000 Montreal
J2 DatabaseDevelop. 135000 New York
JNO JNAME BUDGET LOC
J3 CAD/CAM 250000 New York
J4 Maintenance 310000 Paris
horizontale Fragmentierung
Beispiel: JNO JNAME BUDGET LOCJ1 Instrumentation 150000 Montreal
J2 DatabaseDevelop. 135000 New York
J3 CAD/CAM 250000 New York
J4 Maintenance 310000 Paris
JNO JNAME BUDGET LOCJ1 Instrumentation 150000 MontrealJ3 CAD/CAM 250000 New York
JNO JNAME BUDGET LOC
J2 DatabaseDevelop. 135000 New York
J4 Maintenance 310000 Paris
JNO ImportanceJ1 low
J2 high
J3 low
J4 high abgeleitete horizontale Fragmentierung
Beispiel: JNO JNAME BUDGET LOC
J1 Instrumentation 150000 Montreal
J2 DatabaseDevelop. 135000 New York
J3 CAD/CAM 250000 New York
J4 Maintenance 310000 Paris
vertikale Fragmentierung
JNO BUDGET
J1 150000
J2 135000
J3 250000
J4 310000JNO JNAME LOC
J1 Instrumentation Montreal
J2 DatabaseDevelop. New York
J3 CAD/CAM New York
J4 Maintenance Paris
Sei F = {F1, ..., Fn} eine Menge von Fragmenten, S = {S1, ..., Sm} ein Netzwerk gegeben durch die Menge seiner Sites, und Q = {Q1, ..., Qp} die Menge der relevanten Anwendungen.
Allokationsproblem: Was ist die „optimale“ Zuordnung von F zu S bzgl. Q?
Optimaltätskriterium:•Minimalität der Kosten gegeben durch die Speicherkosten der Fi an den Sites Sj, der Anfragekosten für Fi an Site Sj, der Änderungskosten der Fi an allen Sites an den sie gespeichert sind, und die Kosten der Datenkommunikation.•Performanz im Sinne von Antwortzeiten oder Systemdurchsatz.
Allokation