Kapitel 6 - Physische Datenorganisation
|
Inhalt
|
- Was ist Physische Datenorganisation?
- Wie erfolgt die Adressierung von Daten?
- Möglichkeiten der Indexierung - Zugriffspfade für Primärschlüssel
- Möglichkeiten für Zugriffspfade für Sekundärschlüssel
- Möglichkeiten für Verbindungen zwischen Datensätzen
|
Was ist die zentrale Frage bei der physischen Organisation?
Wie soll das Speichern von Dateien erfolgen, die aus einzelnen Sätzen bestehen?
Dabei geht es im Besonderem um Sätze/Blöcke, Arten der Primärorganisation und Sekundärorganisation,
um Speicherstrukturen für Relationen und um verschiedene Join-Algorithmen.
Was ist ein Satz?
Ein Satz besteht aus einer festen Anzahl von Feldern. Die Schlüssel werden analog zum Relationenmodell
betrachtet und der Blockzugriff erfolgt über die Blockadresse. Das Speicherverwaltungsystem
bietet den Zugriff auf Blöcke bestimmter Größe und verwaltet unbenutzte
und gelöschte Blöcke.
Was ist Primärorganisation und was ist Sekundärorganisation?
Primärorganisation: Organisation der Hauptdatei (enthält die Daten) und der
Hauptzugriffsstruktur
Sekundärorganisation: Eine alternative Zugriffsstruktur neben der primären
Zugriffsstruktur
Wie arbeiten Festplattengeräte?
Um Daten dauerhaft speichern zu können, wird ein Externspeicher benötigt. Diese sind um ein Vielfaches langsamer als
Arbeitspeicher und Caches. Genau aus diesem Grund sind ausgeklügelte Strukturen und Zugriffsmöglichkeiten notwendig.
Eine Festplatte besteht aus mehreren übereinander liegenden Magnetscheiben. Diese Oberflächen sind in
eine feste Anzahl von gleichgroßen Spuren eingeteilt. Übereinander liegende Spuren bilden Zylinder.
Die Festplattenkapazität setzt sich dann in erster Linie aus Zylindern zusammen, welche genauso viele
Spuren haben, wie es Oberflächen gibt. Jede Spur ist wiederum in eine feste Anzahl von Sektoren eingeteilt,
welche die kleinsten adressierbaren Einheiten in einer Festplatte darstellen. So sind Informationen über
Angabe von Zylinder, Oberfläche und Sektornummer abrufbar.
Wo ist der Zusammenhang zwischen Records und Dateien?
DBMS speichern ihre Tupel in Form von Records ab. Solche Records werden in Dateien abgelegt. Eine Datei ist eine vom
Betriebssystem verwaltete logische Einheit. Relationale DBMS fassen aber oft ihre Daten in einer eigenen allumfassenden
katalogisierten Datei zusammen.
Wozu werden Datenblöcke verwendet?
Um die Effizienz zu erhöhen werden mehrere Sektoren zu Blöcken zusammengefasst. (oder auch Pages etc.) Der Vorteil dieser
Herangehensweise ist, das DBMS durch die Nutzung von Blöcken unabhängiger von den Geräten werden.
Wie funktioniert die Adressierung?
Adressiert kann ein Block über die Adresse des ersten Sektors dieses Blockes werden. Wie so oft werden auch hier meist
logische Adressen statt der physikalischen Adressen verwendet. Die logischen Adressen werden dann einfach durchnummeriert,
um einen einfachen Zugriff zu gewährleisten. Der Vorteil an der logischen Adressierung ist, dass bei Umspeicherung nur
die Umsetzungsfunktion zwischen logischer und physischer Adresse angepasst werden muss. So müssen die vielfach auftretenden
Adressverweise in den Verwaltungsdaten im Gegensatz zur physikalischen Adressierung nicht aktualisiert werden.
Wie erfolgt die Adressierung für physische Sätze?
Man unterscheidet physische, seitenbezogene und logische Adressierung. Die Adresse besteht aus zwei Komponenten:
Adresse der Datei und Position innerhalb der Seite. Der Zugriffsmanager ermittelt die benötigte Seite. Diese wird vom
Systempuffermanager angefordert, der diese bei Bedarf durch einen Betriebssystemaufruf vom Externspeicher anfordert.
Wie werden Tupeladressen berechnet?
Der Datenmanager fordert Tupel mit bestimmten Attributwerten an. Die Adressen werden dann über die Indizes vom
Zugriffsmanager bestimmt.
Wozu dient die Indexierung?
Indexe werden verwendet, um die Abarbeitung der Zugriffspfade zu optimieren. Im einfachsten Fall sind alle Datensätze absteigend
nach dem Primärschlüssel sortiert gespeichert. Um nun die Suche nach einem speziellen Datensatz zu beschleunigen, wird neben den Daten
eine Art Inhaltsverzeichnis (Index) gepeichert. Ein Index hat immer die gleiche Struktur:
Index := (Primärschlüssel, Blockidentifikator)
Indexe sind in der Regel nicht dicht, d.h. sie enthalten nicht alle Schlüsselwerte des Primärschlüssels. Desweiteren können Indexe
kaskadiert werden, was bei großen Datenbeständen sinnvoll erscheint.
Ist ein Index nicht dicht, wird bei einer Suche über den am naheliegensten Blockidentifikator zugegriffen und
fort an sequentiell oder binär in diesem Block weitergesucht.
Welche Arten der Primärorganisation kennen Sie?
- Ungeordnete Dateien
- Indexsequentiell (siehe ISAM)
- Clustered
- Hashorganisation
- B*-Baum
- mehrdimensionale Strukturen (Grids,k-d-Bäume...)
Wie arbeitet ISAM - Indexed-Sequential Access Method?
Hauptdatei: enthält die Datensätze
Indexdatei: ermöglicht effizienten Zugriff nach Schlüssel
Für ein sortiert gespeichertes File gibt es einen Index, welcher für die Werte dieses Schlüssels die Adressen der
entsprechenden Tupel referenziert. Ein dünner Index hat zur Folge dass nach der Referenzierung eine Sequentielle Suche
nach dem gewünschten Tupel folgt. Ein dichter Index ist eine eindeutige Abbildung der Schlüsselmenge auf die Tupel,
was natürlich viel Speicher in Anspruch nimmt.
ISAM kann einstufig aber auch mehrstufig implementiert sein. Dabei liegen die Daten an den "Blättern" dieses mehrstufigen Indexes.
Nach Löschoperationen kann es notwendig werden, die Verwaltungsdaten aus Performancegründen neu zu organisieren.
Durch Einfügen können so genannte Überlaufketten entstehen. Um Überlauf bis zu einem gewissen Grad vorzubeugen, werden Blöcke beim
Erstellen nicht vollständig gefüllt, um Spielraum bereitzustellen. (Speicherreserve)
So eignet sich ISAM ideal für große, statische Datenbestände. Bestände mit starken Schwankungen werden besser als B*-Baum
repräsentiert, da dort der Index dynamisch an das Bestandsmaß angepasst wird.
Wie funktioniert die clustered Methode?
Clustered ist eine Abart der indexsequentiellen Speicherung. Dabei ist die Hauptdatei nicht nach dem
Primärschlüssel sortiert (Sortierung nach "Schlüsselfeld")! Die indizierten Felder der Hauptdatei dürfen
in unterschiedlichen Sätzen den gleichen Wert annehmen. Das Einfügen, Suchen und Löschen erfolgt wie bei
der indexsequentiellen Form.
Was ist vorteilhaft am clustern?
Das Clustern mehrerer Dateien! Dabei werden Tupel verschiedener Relationen mit gleichen Werten in bestimmten
Feldern (clustering attributes) in benachbarten Blöcken gespeichert, um somit Abfragen schneller
durchführen zu können.
- prejoin -> Abfragen schneller
- geringerer Speicherbedarf, da Feld nur einmal gespeichert
Nachteil ist aber, dass Relation auf mehrere Blöcke verteilt wird und somit bei Abfragen
innerhalb einer Relation mehr Zugriffe notwendig werden, als ohne Clustering...
Wozu wird der Sekundärindex benötigt?
Suchanfragen welche nicht unmittelbar durch den physikalischen Schlüssel erschlagen werden können, machen in großen Datenbanken
die Einrichtung von so genannten Sekundärindexen erforderlich.
Ein Sekundärindex verwendet normalerweise individuelle Record-Adressen, weshalb nach Bestandsänderungen
dieser Index auch angepasst werden muss.
Form eines Sekundärindex:
Attributwert 1, Adresse 1
Attributwert 2, Adresse 2
Attributwert 3, Adresse 3
...
Attributwert n, Adresse n
Wie arbeiten Baumstrukturen als mehrstufige Indexe?
ISAM hat den Nachteil, dass mit zunehmender Anfrage/Update Aktivität die Performance immer schneller abnimmt. Bäume haben
logarithmische Komplexität und eignen sich deshalb ebenfalls zur Verwaltung der Indexe. Im besonderen Maße werden B-Bäume
verwendet (jedes Blatt gleich Tief ist, wächst von unten nach oben, bestimmter Füllgrad für Knoten). B*-Bäume sind B-Bäume,
welche nur an den Blättern einen bestimmten Füllgrad der Knoten verlangen, um den Baum im Speicher halten zu können.
Sie vereinen die Vorteile von ISAM und B-Bäumen, da sie erstens strikt zwischen Verwaltungsdaten und Bestand (an den Blättern)
trennen und gleichzeitig dynamisch ihre innere Struktur nach Operationen anpassen bzw. reorganisieren.
Ein B*-Baum mit Parameter k wird charakterisiert durch folgende Eigenschaften:
- Jeder Weg von der Wurzel zu einem Blatt hat dieselbe Läange.
- Jeder Knoten außer der Wurzel und den Blättern hat mindestens k Nachfolger.
- Jeder Knoten hat höchstens 2k Nachfolger.
- Die Wurzel hat keinen oder mindestens 2 Nachfolger.
Hash-Verfahren als Zugriffspfad für Primärschlüssel?
Wie bei Hash üblich, wird über eine Hash-Funktion, deren Eingabewerte hier die Primärschlüssel sind, eine Speicheradresse
direkt berechnet. Das Verfahren wird auch Streuspeicherverfahren genannt, da es die Datensätze im gesamten verfügbaren
Speicherbereich verteilt.
Nun kann es vorkommen, dass zwei oder mehr Primärschlüssel auf den gleichen Block zeigen. Eine sogenannte Kollision entsteht.
Aufgelöst wird dieses Problem entweder
- mit Überlaufketten
- durch Nutzung des ersten freien Speicherbereiches im Hashbereich
- durch Einführung einer sekundären Hashfunktion für kollidierte Datensätze
Warum ist Hashing als Speicherverfahren für Datenbanken ungeeignet?
Hashing eignet sich nicht, um Datensätze sortiert auszugeben oder Bereichsabfragen vorzunehmen. Dafür sind Indexstrukturen
besser geeignet, da diese eine lexikografische Ordnung auf die Sätze definieren. Wenn bei Hashing eine Bereichsabfrage notwendig
wird, müssen alle Datensätze gelesen werden!
Zugriffspfade als Listen?
Listen haben den Vorteil, dass sie eine vollständige Ordnung der Datensätze durch Zeiger implizieren. Unabhängig von der
physikalischen Speicherung ergibt sich durch Listen immer eine logische Datei.
Der Nachteil ist aber, das bei n Elementen immer (n+1)/2 Datensätze zu durchforsten sind. Ausserdem kann es durch Einfügen
oder Löschen passieren, dass die Liste sehr ungünstig im Speicherbereich verteilt wird, was sich negativ auf das Laufzeitverhalten
auswirken würde.
Welche Primärorganisationen sind die schnellsten?
- Hashorganisation: Hashtabelle + (Bucketlänge / 2)
- Indexsequentiell (lockerer Index): log2(n/ed)
- B*-Baum: < 1 + logd(n/e)
- Dichter Index: log2(n/d)
n: Anzahl der Datensätze in der Hauptdatei
e: Anzahl der Datensätze pro Block in der Hauptdatei
d: Anzahl der Einträge pro Block in der Indexdatei
Wozu mehrdimensionale Suchstrukturen?
Beispiel:
Gesucht sind alle Personen mit der Eigenschaft
- Alter zwischen 18 und 25 Jahre alt
- Einkommen zwischen 2000 und 35000 €
- PLZ zwischen 09000 und 09999
Mit eindimensionalen Suchstrukturen, müssten alle Abfragen einzeln mit je einer Komplexität von O(k + log n) vollzogen werden
und anschließend die Teilmengen über Joins verbunden werden. Dies kann selbst bei Anfragen, welche nur geringe Datensätze
zurückliefern sehr lange dauern.
Deshalb sind mehrdimensionale Suchstrukturen besser geeignet, da hier nicht ein-dimensionale-Schlüssel verwendet werden, sondern zwei oder mehr.
Was sind Gird Files?
Grid Files (Gitter mit variabler Gittergröße) werden wie k-d-Bäume für mehrdimensionale Suchanfragen benötigt.
Sie verzichten auf die lineare Ordnung der Records und auf die Auszeichnung eines physischen Schlüssels.
Sie ordnen Records in einen mehrdimensionalen Record-Raum ein, dessen Koordinatenachsen von den linear geordneten
Wertebereichen der gewählten Attribute bestimmt werden. Es wird also ein mehrdimensionaler Raum aufgespannt.
Durch die mehrdimensionale Partitionierung eines Suchraumes lasses sich sogenannte Breichsabfragen beantworten.
Erreicht wird dies (bei k-dimensionalen Tupeln) durch
- k Skalen zum Einstieg ins Grid-Directory (im Hauptspeicher)
- ein Grid-Directory zum Finden der Bucket-Nr. (im Hintergrundspeicher)
- Buckets für Datensätze (im Hintergrundspeicher)
zwei eindimensionale Skalen: welche die momentane Unterteilung der X- bzw. Y-Achse enthalten:
var X: array [0..max_x] of attribut_wert_x;
var Y: array [0..max_y] of attribut_wert_y;
ein 2-dimensionales Grid-Directory, welches Verweise auf die Datenblöcke enthält:
var G: array [0..max_x - 1, 0..max_y - 1] of pointer;
Was ist ein k-d-Baum?
K-d-Bäume sind spezielle binäre Suchbäume mit einem k-dimensionalen Suchschlüssel. Der mehrdimensionale Suchraum wird durch
die Datenpunkte in d Dimensionen aufgeteilt. Die Daten werden unter Beachtung dieses Schlüssels im Suchbaum angeordnet, um so
die mehrdimensionalen Bereichsabfragen effizient verarbeiten zu können.
Im 2-dimensionalen Fall gilt für jeden Knoten mit Schlüssel [x=y]:
| im linken Sohn | im rechten Sohn |
| auf ungerader Ebene | alle Schlüssel <= x | alle Schlüssel > x |
| auf gerader Ebene | alle Schlüssel <= y | alle Schlüssel > y |
Warum Zugriffspfade für Sekundärschlüssel anlegen?
Suchanfragen beziehen sich oft nicht auf Primärschlüssel sondern auf nichtidentifizierende Attribute oder Attributkombinationen
(Sekundärschlüssel), für die normalerweise nur eine sequentielle Suche des Datenbestandes zum Ergebnis führt. Ein weiterer Unterschied
zu Primärschlüsseln ist, dass Sekundärschlüssel meist mehrere Datensätze identifizieren. Um das Problem zu Lösen werden Zugriffspfade
für Sekundärschlüssel eingerichtet. Dafür gibt es zwei grundlegende Techniken:
- Zugriffspfade in den Datensätzen durch Zeigererweiterungen (Listen etc.)
- separate Zugriffspfad-Datenstrukturen (Invertierung, Kett-Sätze etc.)
Bei sekundären Pfaden wird also keine Umsortierung der Datensätze vorgenommen...
Bemerkung: Sekundärindexe verweisen direkt auf Datensätze, wogegen Primärindexe meist auf Blöcke verweisen, welche die Datensätze enthalten.
Welche Kriterien sollten bei Indexierung betrachtet werden?
Indiziere Attribute,
- die oft in WHERE-Klausen vorkommen
- die häufig auf ihr Maximum bzw. Minimum abgefragt werden
- die in Join-Operationen verwendet werden
- mit hoher Selektivität (viele verschiedene Attributwerte)
Indiziere nicht Attribute
- mit geringer Selektivität
- aus kleinen Relationen
Wie kann man Verbindung zwischen Sätzen unterstützen?
- durch Invertierung (Erzeugung von Indexen)
- durch Listen und Ringe, d.h. durch Verkettung
verbindende Sätze in Listenstrukturen ablegen (schwierig bei n:m Beziehungen)
- durch variable Zeigerfelder
An jeden Satz wird ein Zeigerfeld variabler Länge angehängt, mit dessen Hilfe auf die zu verbindenden Sätze verwiesen wird.
- durch Kettsätze
Bei n:m Beziehungen zwischen Sätzen wird ein neuer Satztyp eingeführt in dem jedes Beziehungspaar durch einen Satzeintrag repräsentiert wird
Wie funktioniert die Invertierung?
Bei der Invertierung werden für Sekundärschlüssel separate Indexe angelegt.
Eine Datei heißt invertiert bezüglich A, wenn für einen Sekundärindex A ein eigener Index angelegt worden ist.
Sekundärschlüssel bestehen im Gegensatz zu Primärschlüsseln aus Datensätzen variabler Länge. Der Vorteil ist, dass falls eine Datei für
mehrere Sekundärschlüssel invertiert ist, Anfragen nach Kombinationen dieser Schlüssel ohne Zugriff auf die eigentlichen Datensätze möglich
werden.
Wo liegt der Unterschied zu Multi-List-Strukturen?
Multi-List-Strukturen erweitern die vorhandenen Datensätze um je ein Zeigerfeld pro Sekundärschlüsselattribut, welche entsprechend der
der Schlüsselwerte zu einer logischen Folge miteinander verknüpft werden. Invertierung speichert dagegen
die Indexwerte nicht in den vorhandenen Strukturen, sondern in zusätzlich angelegten Listen. (je eine Liste pro Sekundärschlüssel)
Was heißt Selektivität?
Eine hohe Selektivität ist vorhanden, wenn die Anzahl der durch den Schlüssel zu lesenden Datensätze sehr viel kleiner als die Gesamtanzahl
der vorhandenen Datensätze ist.
Wozu Verbindungen zwischen Datensätzen?
Da Beziehungen zwischen Entities in einer Datenbank genauso enthalten sein müssen, wird es notwendig Verbindungen zwischen diesen
Entities mit aufzunehmen.
Eine Verbindung realisiert eine Beziehung zwischen zwei Satztypen, so dass für jeden Satz der einen Beziehung alle zugehörigen
Sätze der Anderen gefunden werden können, ohne auf andere Sätze als auf diese beiden zuzugreifen.
Dabei wird zwischen informationstragenden Verbindungen und nicht-informationstragenden Verbindungen unterschieden. Zweitere werden
nur aus Effizienzgründen implementiert.
Wie können die Verbindungen realisiert werden?
- durch Komposition von separaten internen Sätzen auf konzeptueller und logischer Ebene.
D.h. die Beziehungen werden durch die Transformationsregeln realisiert!
-
durch direkte Verbindungen zwischen Sätzen verschiedener Typen auf der internen Ebene.
Der Nutzen ist den Zugriff für häufig gefragte Beziehungen zu Beschleungigen!
Auf welche Arten lassen sich die Verbindungen auf interner Ebene realisieren?
- Invertierung (siehe oben)
- Phyisische Nachbarschaft (Sätze werden in einem zusammengefasst und gemeinsam gespeichert)
- Listen und Ringe (anhängen variabel langer Zeigerfelder an die Datensätze)
- Kettsätze (für rekursive m:n Beziehungen / Stücklisten)
- physische (Byte-Adressen / statisch) und logische Zeiger (dynamisch über Zuordnungstabelle)auf Datensätze
Wie werden Kettsätze realisiert?
Ein Kettsatz ist ein "Verbindungssatz" mit einer eigenen Struktur (neuer Datentyp).
Die Struktur besteht aus einem Tupel (s,t), welches eine Verbindung zwischen s und t beschreibt.
Dabei enthät jeder Verbindungssatz zwei Zeiger, von denen der Erste auf den Listenkopf von s
und der zweite auf den Listenkopf von t zeigt und alle Elemente verbindet deren zweite Komponente t ist.
Wie können rekursive Verbindungen dargestellt werden?
Es gibt eine n:m-Beziehung zwischen verschiedenen Ojekten eines größeren Gesamtobjektes, welches wiederum Teil eines noch Größeren ist u.s.w...
(Problem der Aggregation)
Man erstellt zwei separate Dateien. Beim Stücklistenproblem sind das Stammdatei (Daten) und Strukturdatei (Kettsatzdatei). Dabei
enthält die Strukturdatei die Daten über die Bauteile (Nummer,Bezeichnung,Durchmesser...) und die Kettsatzdatei je einen Satz für
jede Verbindung zwischen zwei Bauteilen.
|
|
|
|
|
| Kapitel 1 | DBMS Konzept |
|
Eigenschaften, Bestandteile, Ebenen...
|
| Kapitel 2 | DB Entwurf |
|
Qualitätsmerkmale, funktionale Abhängigkeiten, ER...
|
| Kapitel 3 | Normalformen |
|
Übersicht Normalformen, Anomalien...
|
| Kapitel 4 | Relationalität |
|
Regeln und Vorgehensweisen...
|
| Kapitel 5 | Sprachen |
|
relationale Sprachen, SQL, Query...
|
| Kapitel 6 | Datenorganisation |
|
Tertiärspeicher, Adressierung, Indexe, ISAM...
|
| Kapitel 7 | Transaktionskonzept |
|
Datenintegrität, Serialisierbarkeit, ACID...
|
| Kapitel 8 | Concurrency Control |
|
Read-Write Modell, Schedules, Prinzip...
|
| Kapitel 9 | Scheduler & Recovery |
|
2-Phasen-Sperren,Deadlocks,Recovery...
|
|
|
|
|
|
|
|
|
Quellen:
|
Gottfried Vossen
Datenbankmanagementsysteme
|
Heuer und Saake
Konzepte und Sprachen
|
Prof. Benn
Skript und Vorlesung
|
Relationale Datenbanken
Andreas Kelz
|
Word Wide Web
Verschiedenste Seiten
|
|
|
|
|
|
|
Home 
Normalformen