Kapitel 6 - Physische Datenorganisation
- 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.
|
|
Normalformen