Datenbankenmanagementsysteme

Vereinfacht gesagt ist eine Datenbank ein abstraktes Sammelsurium von Informationen, welches von einem Anwendungssystem benötigt wird. Beschäftigt man sich mit der IT, studiert man zum Beispiel das digitale Forensik Fernstudium oder möchte einen Online-Shop erstellen, dann kommt man nicht drum herum, sich mit der Datenbanktechnik auseinanderzusetzen. Die größte existierende Datenbank ist übrigens archive.org, ein frei zugängliches digitales Langzeitarchiv.

Kapitel 1 - DBMS Grundkonzept

Was sind die drei Hauptaufgaben eines DBMS?

  1. Daten Speichern und Verwalten - also ein Sprachkonzept zur Kommunikation und Abstraktion
  2. Bereitstellen von Daten in Form von Anfragen; Übersetzer, welcher Übergang zwischen Benutzerebene und interner Ebene darstellt (Integritätskontrollen, Sicherungsmechanismen etc.)
  3. Mehrbenutzersystem - Zugriffskontrolle und Sperrmechanismen

Schedule-Prinzip

Was sind die Nachteile von Dateisystemen?

  1. keine Trennung von Programm und Daten (keine Daten-Programm Abhängigkeit)
  2. Redundanzen durch anwendungsbezogende Dateistrukturen
  3. Inkonsistenz schnell vorhanden, da keine Schutzmechanismen

Ein DBMS soll diese Nachteile eliminieren durch

Welche Schwerpunkte sind bei der Implementierung zu betrachten?

Was ist Datenunabhängigkeit

...bedeutet eine (weitgehende) Unabhängigkeit von Daten mit ihren arbeitenden Programmen und Nutzern. Dies bedeutet, daß die physische Organisation der Daten für Dialoge und Programme transparent sein soll. Das heißt ein Programm muß sich nicht um die Datenstruktur und den Zugriffspfad kümmern.

Physische Datenunabhängigkeit

Bezieht sich darauf, dass Anwenderprogramme sich nicht um die interne Speicherung und Verwaltung der Daten kümmern müssen. So sollten Datenbanktuning oder Erweiterung von Speicherstrukturen keine Auswirkungen auf Anwendungsprogramme haben.

Logische Datenunabhängigkeit

besagt, dass ein Datenbestand und seine Zusammenhänge für verschiedene Anwendungen aus unterschiedlichen Perspektiven interpretiert werden können.

Zusammenhang

  • die ANSI-SPARC macht logische und physische Datenabhängigkeit möglich
  • durch Einführung der drei Ebenen
  • logische Datenunabhängigkeit, da externe Schema Anwendungen vor Änderungen des internen Schema (z.B. Änderungen am Schema) schützen
  • physische Datenunabhängigkeit, da konzeptuelles Schema Anwendungen vor Änderungen des internen Schemas (z.B. Tuning) schützt

Was ist mit effizienter Organisation gemeint?

Anfragen an das DBMS müssen in akzeptabler Zeit beantwortbar sein. Aus diesem Grund müssen geeignete Organisationsformen zur Verfügung gestellt werden, nach denen die Daten effizient von externen Speichern gelesen und geschrieben werden können.

Wozu Datensicherheit?

Im Falle eines Betriebsmittelsausfalles kann der interne Zustand der Datenbank in einen nicht definierten Zustand geraten. Das DBMS muss deshalb Funktionen bereitstellen, welche dies überwachen und gegebenenfalls reparieren - das so genannte Recovery.

Was ist mit Datenschutz gemeint?

Um sensible Daten zu schützen sind gewisse Vorkehrungen notwendig. Es muss möglich sein verschiedenen Nutzern auch verschiedene Rechte zuweisen zu können. Insbesondere Datensicherheit und Datenintegrität sind Gegenstand der Sparc Drei-Sichten-Architektur.

Was ist ein Datenmodell?

Ist das zentrale Hilfsmittel zur Herstellung einer Abstraktion eines gegebenen Realweltausschnitts und den Einzelheiten der physischen Speicherung. Es umfaßt eine Menge von Konzepten mit denen sich die Struktur einer DB beschreiben läßt.

Struktur Datentypen, Beziehungen, Bedingungen, welche von Daten erfüllt werden sollen (DDL)
Operationen zur Beschreibung von Anfragen und Updates an eine Datenbank (DML)

Was ist ein Schema?

Schemata sind Modelle verschiedener Abstraktionsniveaus bzw. Ebenen, die durch eine Datenbankbeschreibungssprache so beschrieben sind, dass diese durch das DBMS verarbeitet werden können.

Welche drei wichtigen Datenmodelle gibt es?

Hierarchisches Datenbanksystem, Netzwerksysteme und Relationales Modell.

Erklären sie das hierarchische Datenbanksystem!

Ein Record ist hier ein Knoten einer Baumstruktur, welche die Beziehungen zwischen dieses Records darstellt. Ein Knoten kann mehrere Nachfolger haben. Während einem Knoten mehrere Söhne zugeordnet werden können, kann er aber höchstens einen Vorgänger haben. Falls aus logischer Sicht zwei verschiedene Knoten den gleichen Record als Nachfolger haben, muss dieser mehrfach, also redundant, aufgeführt werden.

Technisch werden die Beziehungen zwischen den Records über Pointer realisiert. Der Zugriff erfolgt über eine geeignete Traversierung (z.B. Preoorder) der Struktur vom Wurzelknotens ausgehend.

Das hierarchische Modell erlaubt es, Datensätze mit variabler Länge (also mit Wiederholungsgruppen) einfach zu modellieren. Dazu wird ein Datensatz in einen Teil ohne und einen Teil mit Wiederholungsgruppen aufgeteil.

Einfügen, Löschen und Ändern kann immer nur im Rahmen der Hierarchie geschehen. D.h. es kann kein direkter Zugriff erfolgen, sondern nur über den Vater. Es ist also ein sequentielles Travasieren notwendig.

Welche Probleme hat das hierarchische System?

N:M Beziehungen sind nicht direkt abbildbar, weil die möglichen 1:n-Beziehnungen gerichtet sind von 1 zu n. Somit würde die Struktur keinen Baum sondern einen Graphen darstellen. Werden Datensätze an einer zweiten Stelle zur Verarbeitung erneut benötigt, müssen diese auch noch einmal im Modell auftreten. Das heisst, es herrscht Redundanz...

Um die Graphenbildung und Redundanzen zu vermeiden werden virtuelle Satztypen eingeführt. Dies wird vor allem bei der Implementierung der Bill Of Material (Stückliste) genutzt!

Was sind Netzwerksysteme?

Netzwerksysteme sind den hierarchischen Systemen ähnlich. Sie müssen sich aber nicht der Baumstruktur beugen. Redundante Knoten sind hier auch nicht notwendig, da Link-Records eingeführt werden, welche die Mehrfachzuweisungen realisieren. Es werden ebenso Pointer zur Umsetzung der Beziehungen verwendet.

Beziehungstypen sind ausschließlich 1:1 oder 1:n und werden als gerichteter Graph zwischen den Satztypen dargestellt.

Set-Typen

Die Bezeichnung Set drückt aus, daß zu jedem logischen Datensatz A ein Satz vom Typ B gehört, zu dem alle Sätze gehören, die über A mit B in Beziehnung stehen. Es kann aber auch Sätze geben die zu keinem andern Satztyp in Beziehung stehen.

Owner & Member

Owner ist im hierarchischen Modell der Vater. Member ist im hierarchischen Modell der Sohn.

n:m Beziehungen im Netzwerkmodell

N:M Beziehungen werden in 1:n Beziehungen mit Hilfe eines Kettsatzes (Kett-Record)erzeugt, welcher in beiden Beziehungen als Member eingetragen wird. Daraus ergibt sich ein ungerichteter Graph, da man hin- und zurückgelangen kann.

Das Netzwerkmodell ist zwar leistungsfähiger als das Hierarchische Modell, lässt sich aber weitaus schwieriger Implementieren und Verarbeiten. Das Auffinden von Datensätzen ist wesentlich komplizierter, da durch das Netzwerk navigiert werden muss.

Currency Konzept

Currency bedeutet, daß Bezug auf die aktuelle Position im Netzwerk unter Verwendung interner Datenbankaktualitäts-Indikatoren genommen werden kann (Currency Indicators). Die Werte der Indikatoren können als datenbankinterne Schlüssel gesehen werden.

Zusammenfassung

  • hierarchischem Modell und Netzwerkmodell verbindet Daten mit Zeigern
  • deshalb kaum Trennung von interner und konzeptioneller Ebene möglich
  • Anfragesprache muss entlang der Zeiger Navigieren
  • Das Relationale Modell speichert Daten in Tabellenstrukturen und basiert auf 3-Ebenen Architektur
  • Objektorientierte Datenbanken sind besonders für das Ablgegen komplexer Objekte geeignet

Wie funktioniert das Relationale System?

Dieses Modell verzichtet im Gegensatz zu den anderen auf Pointer zur Darstellung von Beziehungen. Daten werden ausschließlich über inhaltliche Angaben aufeinander bezogen. Die Entities einer Klasse werden in Form von Tabellen (Relationen) dargestellt, in deren Zeilen die Beschreibungen stehen. Die Struktur der Tabelle wird über die Spalten-Überschriften festgelegt. Eine Zeile einer Relation wird als Tupel bezeichnet.

Eine wichtige Eigenschaft für Attribute ist der elementare Charakter, d.h. es sind keine zusammengesetzten Attribute oder ähnliches erlaubt. Die gespeicherten Daten werden ausschliesslich über mengenorientiert verknüpft. Der Zugriff erfolgt über fünf grundlegenden Operationen:

Folgende Operationen sind keine Grundoperationen:

Was kennzeichnet das Objektorientierte Modell?

Hier wird ein Entity-Typ durch eine Klasse mit den dazugehörigen Funktionen repräsentiert. Attribute der Klassen müssen nicht atomar sein, sondern bestehen aus Records, Listen oder Mengen. Durch das Prinzip der Vererbung kann die Struktur eines Entity-Typs an andere Klassen weiteregegeben werden. Binäre Beziehungen können durch mengenwertige Attribute modelliert werden. 

class Person
        type tuple (name : String, geb_datum : Date, kinder : list(Person))
end;

class Student inherit Person
        type tuple (mat_nr : Integer, hoert : set (Vorlesung))
end;

class Vorlesung
        type tuple (titel : String, gehoert_von : set (Student))
end;

Beispielquelle: Universität Osnabrück

Wie sieht das Ansi/Sparc Modell aus?

Externe Ebene Umfasst verschiedene Sichten der Nutzer (z.B. ein SQL Statement) Diese Subschemata werden in einem externen Schema beschrieben, welches nur diesen Ausschnitt der konzeptuellen Schicht enthält und gegebenenfalls Teile verwehrt.
Konzeptuelle Ebene Repräsentiert die logische Gesamtsicht der Daten und ihrer Beziehungen untereinander. Sie beschreibt also das, was in der Datenbank abgelegt werden soll. Ferner werden auch Integritätsbedingungen und Zugriffsrechte dokumentiert.
  • Stabiler Bezugspunkt für alle Anwendungen (ändert sich kaum)
  • Dokumentation (Das Datenbankschema dokumentiert einen Weltausschnitt)
  • Kontrolle (bietet Möglichkeit der Nutzung zentraler Dienste, wie Versionsmanagment)
  • Datenunabhängigkeit
Interne Ebene Verwaltung der Daten als "interne Records" (Datensätze). Informationen über Art und Aufbau verwendeter Datenstrukturen und spezieller Zugriffsmechanismen. Sie lokalisiert die Daten auf den Sekundärspeichern und ist extrem eng mit dem Betriebssystem verknüpft (z.B. Wandlung logischer Adressen in physikalische)

Transformationsvorschriften beschreiben, wie man aus einem konzeptuellen Modell ein internes bzw. externes Modell herleitet. Werden Änderungen an der Internen Ebene vorgenommen, so müssen nur die Transformationsregeln angepasst werden. Datenmodelle auf der 3-Ebenen Architektur basierend, gewährleisten ein hohes Maß an Datenunabhängigkeit.

Physische Datenunabhängigkeit:

Bei Änderungen des internen Schemas sind nur die Transformationsvorschriften zu ändern. Externe Sichten bleiben unbeeinflusst. Anders gesagt, beschreibt Physische Datenunabhängigkeit die Isolierung der Anwendungen von der physischen Dateiorganisation.

Logische Datenunabhängigkeit:

Die Anwendungen werden von der konzeptuellen Ebene der Modellierung isoliert. In Abhängigkeit von der Flexibilität der Transformationen können ggf. unterschiedliche Interpretationen der Daten in den externen Schemata niederschlagen.

Statische Datenunabhängigkeit:

Die Anwendung muss bei statischer Datenunabhänigkeit bei Änderungen im konzeptuellen oder internen Modell neu gebunden werden. (Erreicht durch Binden zur Übersetzungszeit)

Dynamische Datenunabhängigkeit:

Anwendungen sind von allen Änderungen völlig unabhängig. (Erreicht durch Binden zur Zugriffszeit)

DBMS-Prinzip

Welche acht Schritte führt das DBMS nach einer (deskriptiven) Anfrage aus?

  1. Syntax prüfen (Integritätscheck)
  2. Tabellen in Schema vorhanden?
  3. Zugriffsrechte prüfen
  4. Festellen welche Operationen intern auszuführen sind und wie der Anfrage-Operand intern gespeichert ist
  5. Erstellung eines effizienten Codestückes zur Antwortberechnung
  6. Operanden aus Datenbank lesen
  7. Aufbereiten der Operanden (Optimieren)
  8. Sicherstellen, daß Operanden nicht während Ausführung durch andere Anfragen geändert werden (Kritischer Abschnitt - Zwei Phasen Protokoll)

In welche fünf Ebenen kann man die Struktur eines DBMS einteilen?

Die fünf Ebenen eines DBMS

Ebene 1 der Benutzersprache
I/O-Prozessor
nimmt Anfragen entgegen und gibt Ergebnisse und Fehler aus.

Parser
übernimmt syntaktische Analyse der Anfrage bzw. des Auftrages.

Precompiler
für eingebettete Kommandos.

Autorisierungskontrolle
in jedem Falle bevor es zu Ebene 2 geht!

Weitergabe des Codes an Ebene 2 ( Update - oder den Query-Prozessor) durch die Autorisierungskontrolle (bei relationalen DB als Baum mit Operanden als Blätter und Operatoren als Knoten)
Ebene 2 der Anfrageverarbeitung
Update-Prozessor:
Änderungen in der Datenbank vornehmen

Integritätsprüfung:
semantische Korrektheit der DB = Konsistenz, deren Regeln beim Erstellen des Schemas definiert werden, wie z.B. höhe<>0

Query-Prozessor:
nur Anfragen an Datenbank und somit keine Integritätsprüfung notwendig, dafür aber Optimierung

Optimierer:
versucht unnötigerweise komplizierte Benutzeranfragen zu vereinfachen

Weitergabe des Codes an Ebene 3 durch den Optimierer
Ebene 3 der Zugriffsstrukturen
Zugriffsplanerstellung
Bestimmung eines Zugriffspfades aus den vorhandenen Zugriffsstrukturen (z.B. Indexe)

Code-Erzeugung
Erzeugung des Zugriffs- und Ausführungscodes, was immer nur eine Folge von Lese und Schreiboperationen (=Transaktionen) sind

Weitergabe der Transaktionen an die Transaktionsmanager
Ebene 4 der Synchronisation paralleler Zugriffe
Transaktionsverwaltung:
Synchronisation parallel ablaufender Transaktionen durch Verzahnung, da Nutzer einer DB nie exklusiven Zugriff hat. Kein sequentieller Ablauf, da sonst kurze Transaktionen gegebenenfalls lange warten müssen, obwohl diese in disjunkten Teilen arbeiten

Scheduler:
Synchronisation der zeitlich überlappten Transaktionen (Concurrency Control)

Recovery-Manager:
Transaktionen werden nach "Alles oder Nichts" Prinzip bearbeitet. Wird eine Transaktion nicht beendet, stellt der Recovery Manager den Urzustand der DB mit Hilfe des Log-Buches wieder her. (auch nach Hardwarefehlern o.ä.)
Ebene 5 der Speicherverwaltung
Buffermanager
Hauptspeicherverwaltung für jede Transaktion

Data-Manager
mit Geräte- und Sekundärspeichermanager führt die physischen Zugriffe aus

Nutzung von Betriebssystem Funktionen
Alle Ebenen sind mit dem Data-Dictonary verbunden!

Was ist das Data Dictonary?

Metadaten bzw. Beschreibungen der Daten und somit der Schemata werden im Data Dictonary gespeichert. Datenbank selbst und das interne Logbuch der Datenbank sind zwei weitere zentrale Systemkomponenten.

Es enhält unter anderem...

Was macht der Query-Prozessor des DBMS?

Er stellt einen Pool von Ausführungsoperatoren sowie Mechanismen für deren Kommunikation und Synchronisation (zB. Pipes) zur Verfügung. Im Grunde ist der Anfrageprozessor dafür verantwortlich die algebraischen Ausdrücke auf physischer Ebene zu verarbeiten. Dabei wird optimiert durch Parallelverarbeitung mehrerer Prozesse. Ein Prozess schreibt ein Zwischenergebnis in ein File und eine andere Prozess nimmt diese Zwischenergebnisse heraus zur Fortsetzung der Operation.

Was sind die drei wichtigsten Dienste eines DBMS?

Datenmanager, Zugriffsmanager und Systempuffermanager stellen die wichtigsten Dienste im DBMS dar...

Was macht der Datenmanager?

Der Datenmanager ist die Mengenschnittstelle. Er übersetzt und optimiert die Anfragen, Integritäts- und Zugriffskontrollen.

Was macht der Zugriffsmanager?

Stellt eine 1-Tupel-Schnittstelle dar. Er ist verantwortlich für Einfügen/Löschen/Suchen und Ändern von Tupeln. Er stellt Operatoren für Schemata und Transaktionsmanagement bereit.

Welche Aufgabe hat der Systempuffermanager?

Der Systempuffermanager ist die Seitenschnittstelle, welche bei Bedarf neue Seiten vom Betriebssystem anfordert (pinned pages).

Kapitel 2 - Prinzipien des Entwurfs

Welche fünf wichtigen Qualitätsmerkmale sind zu beachten?

  1. Vollständigkeit
  2. Korrektheit
  3. Minimalität
  4. Lesbarkeit
  5. Modifizierbarkeit

Was heißt Vollständigkeit?

Vollständigkeit in Bezug auf den nachgebildeten Umweltausschnitt!

Was heißt Korrektheit des Datenbankschemas?

ist gegeben, wenn die Konzepte des betreffenden Datenmodells korrekt verwendet werden und das Schema syntaktisch und semantisch Korrekt ist.

Was heißt Minimalität eines Datenbankschemas

in Bezug auf einmaliges vorkommen verschiedener Anforderungen. Gleichzustellen mit Redundanzvermeidung, welche aber manchmal z.B. durch Normalisierung, sogar erwünscht ist.

Was heißt Lesbarkeit des Schemas

durch z.B. ER-Diagramme (symmetrisch etc) und selbsterklärende Entity-Bezeichnungen.

Was heißt Modifizierbarkeit eines Datenbank Schemas

durch gute Modularisierung und Dokumentation des Schemas.

Beschreiben sie die vier Schritte des Datenbankentwurfs!

  1. Anforderungsanalyse und -spezifikation (Herausfinden was gewollt wird)
  2. Konzeptueller Entwurf (ER-Diagramm, Beschreibung etc.)
  3. Logischer Entwurf (Umsetzung in ein Daten-Modell wie z.B. das Relationelle)
  4. Datendefinition (Implementierung des Schemas mit DDL)
  5. Physischer Entwurf (Tuning, Indexe u.s.w)
  6. Wartung

Die Schritte errinnern sehr an das veraltete Wasserfallmodell der Softwaretechnik!

Welche Anforderungen werden an den Entwurfsprozeß gestellt?

Was gehört zur Anforderungsanalyse und -spezifikation?

Was gehört zum Konzeptueller Entwurf?

Was gehört zum logischen Entwurf?

Was gehört zum physischen Entwurf?

  1. Definition des internen Schemas
  2. Wahl geeigneter Speicherstrukturen
  3. Festlegung von Zugriffsmechanismen mit Ziel, Suchpfade zu minimieren
  4. Später Tuning um Parametereinstellungen zu korrigieren

Welche Tuningmöglichkeiten gibt es dabei?

Welche Mittel bietet das ER-Diagramm?

Was sind Entities und Entity-Typen?

Eine Entity beschreibt ein wohlunterscheidbares Objekt der realen Welt welche mit anderen Objekten in Beziehung stehen. Entity-Typen beschreiben Klassen von Objekten bzw. Entities gleicher Charakteristika und Eigenschaften, aber unterschiedlicher Ausprägungen. Entities werden über Schlüssel identifiziert.

Was sind Quantifizierungen

Quantifizierungen werden im ER-Diagramm auf den Verbindungslinien angebracht und beschreiben die Art der Beziehung (1:n,1:1 oder m:n).

Was ist ein schwacher Entity Typ?

Schwache Entities sind solche, welche nicht durch ihre eigenen Attribute eindeutig identifizierbar sind und somit nicht autonom existieren können. Sie werden im ER-Diagramm durch doppelt gerahmnte Rechtecke dargestellt.

Was ist Aggregation? (part of)

Mit Aggreagation bezeichnet man die Zusammenfassung verschiedener Objekte zu einer Objekthierarchie, welche dann für bestimmte Betrachtungen als Ganzes bzw. als Einheit betrachtet wird. Im ER-Diagramm werden einem obergordneten Entity-Typ mehrere Entity-Typen untergeordnet, um eine Part-Of Hierachie herzustellen.

Was ist Generalisierung? (is a)

als Generalisierung wird die Zusammenfassung ähnlicher Objekte zu einem generischen Objekttyp verstanden. Die Is-A Relation ist ein wesentliches Element der Generalisierung. Dabei werden Attribute von Entities weiter oben in der Hierarchie an die Entities nach unten hin vererbt. (Bsp: Student (Matr) IS-A Uni-Mitglied (Name))

Was heißt Integrität von relationalen Datenbanken?

Gespeicherte Informationen in Datenbanken sind normalerweise bestimmten Randbedingungen unterworfen. Sinn und Zweck ist, die gültigen Zustände aus der Menge aller möglichen Zustände einer Datenbank herauszufiltern. Sind die semantischen Bedingungen der jeweiligen Anwendung und werden zur Entwurfszeit der Datenbank erstellt.

Welche Arten von Integritätsbedingungen gibt es?

Integritätskontrolle soll semantische Fehler und sinnlose Zustände der Datenbank verhindern. Sie wird in der Regel dem DBMS überlassen, welches über einen speziellen Monitor die Integrität der DB überwacht. Dies hat den Vorteil, dass im Grunde alle Transaktionen problemlos gestartet werden können und selbst ad-hoc Benutzer sich nicht um die Integrität der DB kümmern brauchen.

Was sind Statische Integritätsbedingungen?

Entstehen durch Festlegung des jeweiligen Schemas definierte Regeln. Bsp: Jahr beetween 1900 and 2030

  1. Schlüsselbedingungen (primary key (idx))
  2. referentielle Integrität und Fremdschlüssel
  3. Attribut-Bedingungen (not null etc..)
  4. Bereichseinschränkungen (Check-Klausel)

Referentielle Integrität ist die Integrität von Fremdschlüsseln, die gegeben ist, wenn der Fremdschlüssel entweder nur Nullwerte oder ausnahmslos keine Nullwerte enthält. Falls keine Nullwerte exisitieren gibt es in beiden Relationen ein Tupel, wo Fremdschlüssel und Schlüssen übereinstimmen. Falls die Referentielle Integrität nicht gegeben ist würde bei Änderungen zu Inkonsistenten kommen

Erlaubte Änderungen sind:

Was sind transitionale Bedingungen?

Sind halbdynamische Bedingungen und schränken die möglichen Übergangszustände ein.

Was sind dynamische Bedingungen?

Sind temporale Bedingungen und schränken als Verallgemeinerung der transitionalen Bedingungen die möglichen Zustandsfolgen ein.

Was sind Assertions und Trigger?

Assertions und Trigger sind Mittel zur Integritätskontrolle. Assertions werden durch "check" geprüft. Eine Assertion bildet meist eine Mengendifferenz und prüft, ob eine gültige Teilmenge vorliegt. Bsp: 

create assertion GueltigesFachgebiet
Check ( not exists 
		(select distinct Fachgebiet from Lektor
		Except select distinct Fachgebiet from Buch)
	   )

Die Behanldung kann entweder immediate oder deferred (verzögert) erfolgen.

Integritätsüberwachung

  1. transaktionsorientiert ( Überprüfung erfolgt im Kontext eines Programmes)
  2. ereignisorientiert (durch Trigger definierte Bedingungen)

Trigger sind benutzerdefinierte Prozeduren, die automatisch bei Erfüllung einer bestimmten Bedingung vom DBMS gestartet werden. Diese Prozeduren können BEFORE oder AFTER gesteuert sein. Before-Trigger werden oft genutzt, um Berechnungen vorzunehmen, um diese in die Integritätsprüfung aufzunehmen. After-Trigger eignen sich besonders gut, um Änderungen in Tabellen zu loggen, um z.B. Change Notes abzuspeichern.

Trigger z.B. werden gestartet, wenn eine Integritätsverletzung aufgetreten ist, um diese zu beseitigen. Aktive DBMS verfolgen diese Strategie viel intensiver.

Kapitel 3 - Relationenalgebra und Normalisierung

Was ist das Entwurfsziel bei relationalen Datenbankschemata?

Eine Relationenschema soll einen Entity-Typ oder einen Beziehungstyp beschreiben. Eine Relation sollte deshalb Informationen enthalten, die auch wirklich zusammengehören. Dabei ist es nicht einfach beiden Ansprüchen der beiden Kriterien zu genügen. Ein Datenbankschema ist die Menge aller Relations-Schemata.

Was ist das relationale Datenmodell?

Daten werden als Relationen durch Tabellen (Entitätsmengen) dargestellt. Dabei entspricht eine Zeile einer Entity und eine Spalte einem Attribut.

Ein Schlüssel einer Relation ist eine minimale Attributmenge die ein Tupel R D1 x D2 x .... x Dn (D sind Domains bzw. Wertebereiche) eindeutig identifiziert. Ein Relationsschema R(A1,....,An) spezifiziert eine Relation R mit den Attributen A1,....,An. Dabei ist jedem Attribut Ai ist ein Wertebereich dom(Ai) zugeordnet.

Auf welche zwei Möglichkeiten kann man Abfragen an Relationen stellen?

Mit einer Relationenalgebra oder einem Relationenkalkül...

Was ist eine Relationenalgebra?

Die Relationenalgebra definiert Operationen auf Relationen, die neue Relationen erzeugen

Grundoperationen

Selektion (Auswahl bestimmter Tupel), Projektion (Auswahl bestimmter Spalten), Vereinigung, Mengendifferenz, Kartesisches Produkt, Umbenennung

Verbund, Durchschnitt und Division lassen sich aus den Grundoperationen ableiten.

Beispiel: (ANGEST[ANGNR=ANGNR]ANG_PRO)[PNR=17][NAME]

Natural Join (nur gleiche Attributnamen) oder Teta Joins (mit Prädikat) werden auch innere Joins genannt (inner join). Bei ihnen gehen diejenigen Tupel der Argumentrelationen verloren, die keinen Join-Partner gefunden haben. Bei den äußeren Join-Operatoren (outer joins) werden - je nach Typ des Joins - auch partnerlose Tupel gerettet:

Was ist ein Relationenkalkül?

Durch ein Prädikat (eine Bedingung) wird die Menge der gewünschten Tupel beschrieben mit Hilfe einer Formel der Pradikatenlogik 1. Stufe unter Verwendung von Existenzquantoren, Allquantoren, And, Or und der Negation.

Beispiel:


{t|q}, dabei ist t eine Liste von Attributnamen

q: Prädikat

z.B. {STUDENT.WOHNORT|STUDENT.MATRIKEL=22762}

Worin unterscheiden sich Relationenalgebra und Relationenkalkül?

Die Relationenalgebra stellt konstruktive Regeln zur Erzeugung neuer Relationen bereit, hier insbesondere die Grundoperationen (Vereinigung, Differenz, kartesisches Produkt, Selektion, Projektion) und zusätzlich die Operationen Join und Natural Join.

Der Relationenkalkül dagegen arbeitet mit deskriptiven Regeln. Mit seiner Hilfe wird die Menge der bei einer Abfrage gewünschten Tupel beschrieben indem eine Bedingung angegeben wird, die die Tupel erfüllen müssen.

Sind Abfrageergebnisse im Voraus beweisbar?

Die Relationenalgebra erlaubt eine sichere Bestimmung des Ergebnisses im Voraus, da konstruktive Regeln verwendet werden.

Formulieren Sie eine Abfrage in Relationenalgebra und in Relationenkalkül! 


Relationenalgebra: STUDENT[Name='Muller'][Matrikel] 

Relationenkalkül: {STUDENT.Matrikel|STUDENT.Name='Muller'}

Wie werden Entitätstypen und Beziehungen in relationalen Datenbanken dargestellt?

Beide werden als Relationenschemata dargestellt.

Was ist das Ergebnis einer Selektion/Projektion auf einer Relation?

Wiederum ein Relation.

Was sind die drei wichtigsten Operationen der relationalen Algebra?

Die Projektion

Auswahl der Spalten einer Tabelle ohne dabei doppelte Zeilen zuzulassen.

Die Selektion

Auswahl von Entitäten (Zeilen) aus einer Relation (Tabelle) unter einer bestimmten Bedingung

Der Natürliche Verbund - natural join

Verbindet über die Vereinigung zweier oder mehrerer Attributmengen Relationen zur einer neuen Relation.

Der unqualifizierte Join ist die teuerste Operation in der Relationenagebra, denn er ergibt das kartesische Produkt zweier Mengen und bildet somit bei zwei Tabellen der Mächtigkeiten n und m eine neue Relation der Mächtigkeit nm!

Was sind funktionale Abhängigkeiten?

Man beachte den logischen Zusammenhang, welcher Attribute und ihre Attributwerte untereinander haben. Zum Beispiel lässt sich durch einen fortlaufenden CD-Index in einer CD-Datenbank eindeutig eine CD bestimmen, da die dazugehörigen Attribute über diesen Schlüssel eindeutig definiert sind. Man sagt nun auch, dass alle restlichen Attribute vom CD-Index voll funktional abhängig sind. Also ist ein Primätschlüssel ein Beispiel für funktionale Abhängigkeit. Dabei ist das Auffinden von funktionalen Abhängigkeiten nicht immer einfach. (sie entstehen durch 1:n Kardinalitäten im ERD)

Voll funktional abhängig heißt, wenn B von keiner echten Teilmenge von A abhängig ist. (Minimalitätsforderung)

Ein Attribut B ist von einem Attribut A funktional abhängig, wenn es zu jedem A genau ein B gibt.

Wenn zwei Tupel einer Relation gleiche Werte für alle Attribute in A haben und auch ihre B-Werte übereinstimmen, dann ist B von A funktional abhängig. Anders formuliert, bestimmen die A-Werte eindeutig die B-Werte.

Für funktionale Abhängigkeiten gelten folgende Eigenschaften:

Erweiterung Kontextunabhängigkeit funktionaler Abhängigkeiten heißt, das man eine gegebene Relation durch ergänzende Attribute erweitern kann, ohne die funktionalen Abhängigkeiten zu zerstören.
Gibt es mehrere funktionale Abhängigkeiten können diese in mehrere Relationen geteilt werden und durch einen verlustfreien Join auch wieder hergestellt werden.

Welche Arten von Anomalien gibt es?

Anomalien entstehen durch Auftreten bzw. Nichterkennen von funktionalen Abhängigkeiten.

Was ist eine Einfüge-Anomalie?

Ein neues Tupel kann erst eingetragen werden, wenn alle X Informationen vorliegen. Falls Nullwerte erlaubt sind, gibt es dann Probleme falls die fehlende Info zum Schlüssel gehört.

Was ist eine Lösch-Anomalie?

Wird eine Information aus der Relation entfernt, so gehen mehr Informationen verloren, als gewollt war. Tritt oft auf wenn in einer Relation mehr als eine Entity vertreten ist!

Was ist eine Änderungs-Anomalie?

Falls eine Änderung der Daten vorgenommen werden muss, muss dies an mehreren Stellen in der Relation geschehen, da sonst die Konsistenz bedroht ist.

Wozu dienen Normalformen?

Normalformen dienen der Vermeidung von Anomalien und zur Vermeidung von Redundanz. Normalisierung heißt ein Aufteilen von Informationen in Relationen entsprechend ihrer Semantik.

Beispiel:

LIEFER(Lieferant, Artikel,Adresse, Preis)

Einfüge-Anomalie

Lieferant ohne Artikel (bisher keine Lieferung) kann nicht berücksichtigt werden.

Lösch-Anomalie:

Löschen eines Artikels führt möglicherweise auch zum Verlust des Lieferanten.

Änderungsanomalie:

Bei einer Preisänderung eines Artikels muß die ganze Relation durchsucht werden

Wie sind die ersten vier Normalformen definiert und wie kann man sie erklären?

In der 1.NF sind die Attributwerte sind unteilbar. (d.h. keine mengenwertigen Attribute) Die 2.NF besagt, jedes Nichtschlüsselattribut A von R ist voll funktional abhängig von jedem Schlüssel S von R (und nicht nur von Teilen des Schlüssels) und die 3.NF definiert, das für alle implizierten Abhängigkeiten S A mit A S gilt: S enthält einen Schlüssel oder A ist Schlüsselattribut(d.h. es gibt keine Abhängigkeiten zwischen Nichtschlüsselattributen einer Relation)

Die BCNF (Boyce Codd Normalform) ist so definiert, das für jede funktionale Abhängigkeit S A gilt: S enthält einen Schlüssel für R. (d.h. es gibt keine Abhängigkeit zwischen Nichtschlüsselattributen und Schlüsseln)

Was heißt Dekomposition?

Unter Dekomposition einer Relation in mehrere, einer Normalform genügenden Relationen, versteht man eine Aufteilung der Ursprungsrelation, bei der keine Information verloren geht.

Wir arbeitet das Dekompositionsprinzip?

Die Aufteilung geschieht durch geschickte Projektionen, die durch natürliche Join-Operationen verlustfrei rückgängig zu machen sind.

Was bedeutet FD-treue Zerlegung?

Die Zerlegung eines Relationenschemas soll nicht mehr, aber auch nicht weniger Integritätsbedingungen (hier funktionale Abhängigkeiten) enthalten als die Ursprungsrelation.

Welche Normalformen gibt es?

Was definiert die erste Normalform?

Eine Relation ist in der ersten Normalform, wenn jeder Attributwert atomar ist, d.h. es gibt keine zusammengesetzten Attribute in Form von Arrays, Sets oder Aufzählungstypen.

1. Normalform

  • jeder Attributwert ist atomar
  • ohne zusammengesetzte Attribute

Was definiert die zweite Normalform

Eine Relation ist in der Zweiten Normalform, wenn sie in der Ersten Normalform ist und jedes Nicht-Schlüsselattribut von jedem Schlüsselkandidaten vollständig funktional abhängig ist.

Ein Attribut Y ist von einem Attribut X funktional abhängig, wenn es zu jedem X genau ein Y gibt. Vollständig funktional abhängig bedeutet, daß das Nicht-Schlüsselattribut nicht nur von einem Teil der Attribute eines zusammengesetzten Schlüsselkandidaten funktional abhängig ist, sondern von allen Teilen.

Datenfelder, die von einem Schlüsselkandidaten nicht vollständig funktional abhängig sind, werden in weiteren T abellen untergebracht. Besteht der Primärschlüssel nur aus einem einzigen, so ist eine Relation in Erster Normalform automatisch in Zweiter Normalform.

2. Normalform

  • Es darf keine partiellen Abhängigkeiten zwischen Schlüsseln und Nicht-Schlüssel-Attributen geben
  • Das heißt, es darf kein Nicht-schlüssel-Attribut von einem Schlüssel abhängen
  • Dies wird aufgelöst, in dem die Abhängigkeit in eine extra Tabelle ausgelagert wird

NF2 Herstellung

Was definiert die dritte Normalform

Eine Relation ist in der Dritten Normalform, wenn Sie in der Zweiten Normalform ist und jedes Nicht-Schlüssel-Attribut von keinem Schlüsselkandidaten transitiv abhängig ist.

3. Normalform

  • Es darf keine transitiven Abhängigkeiten eines Nicht-Schlüssel-Attributes von einem Schlüssel geben
  • Das heißt, es darf kein Nicht-schlüssel-Attribut von einem anderen Nicht-schlüssel-Attribut abhängen
  • Das heißt Attribut B ist abhängig von Schlüssel und Attribut C ist abhängig von B
  • Wird aufgelöst, in dem die beiden Spalten in eine extra Tabelle ausgelagert werden
  • 3NF ist ein Spezialfall der Broyce-Codd-Normalform

NF3 Herstellung

Wie sieht die Boyce-Codd Normalform (BCNF) oder 3 1/2 NF aus?

Eine Relation ist in Boyce-Codd Normalform, wenn jeder Determinant ein Schlüsselkandidat ist.

Ein Determinant ist eine Attributmenge, von der ein anderes Attribut vollständig funktional abhängig ist. Die Boyce-Codd-Normalform ist eine Weiterentwicklung der 3 NF. In der Dritten Normalform kann es vorkommen, daß ein Teil eines (zusammengesetzten) Schlüsselkandidaten funktional abhängig ist von einem Teil eines anderen Schlüsselkandidaten. Die Boyce-Codd-Normalform verhindert dies.

Anders gesagt: In der BCNF wird jedes Attribut welches ein Schlüssel sein könnte, zu einem Schlüssel gemacht.

Boyce-Codd Normalform

  • Es darf keine transitiven Abhängigkeiten eines Nicht-Schlüssel-Attributes oder eines Schlüssel-Attributesvon einem Schlüssel geben
  • Das heißt, es darf kein Nicht-schlüssel-Attribut oder Schlüssel von anderen Attributen transitiv abhängen
  • Wird aufgelöst, in dem die abhängigen Spalten in eine extra Tabelle ausgelagert werden

Was definiert die vierte Normalform?

Eine Relation ist in Vierter Normalform, wenn sie in Boyce-Codd Normalform ist und für jede mehrwertige Abhängigkeit einer Attributmenge Y von einer Attributmenge X gilt:

Mehrwertige Abhängigkeit: (Multivalued Dependency, MVD)

Ein Schlüssel bestimmt nicht nur ein Attribut X sondern eine ganze Liste einer Attributmenge X. Dann liegt eine mehrwertige Abhängigkeit vor. Die mehrwertige Abhängigkeit ist trivial, wenn sich die Tabelle nicht weiter zerlegen läßt.

4. Normalform

  • Mehrwertige Abhängigkeiten sind verboten
  • Das heißt es darf keine Redundazen in funktional Abhängigen Attributen geben
  • Beispiel ISBN (eindeutig) und Autor (uneindeutig, da mehrere Autoren)
  • Wird aufgelöst, in dem die mehrwertigen Spalten in eine extra Tabelle ausgelagert werden

Was definiert die fünfte Normalform?

Eine Relation R ist in Fünfter Normalform (oder Project-Join-Normalform), wenn sie in Vierter Normalform ist und für jede Join-Abhängigkeit (R1, R2, ..., Rn) gilt:

Join-Abhängigkeit (Join Dependency)

Eine Relation R genügt der Join-Abhängigkeit (R1, R2, ..., Rn) genau dann, wenn R gleich dem Join von R1, R2, ..., Rn ist. Eine Join-Abhängigkeit ist trivial, wenn ein Ri aus (R1, R2, ..., Rn) gleich R ist.

Was sollte wärend der Normalisierung immer getan werden?

Das normalisierte Schema mit dem ER-Diagramm auf Korrektheit überprüfen.

Was versteht man unter Erweiterung der relationalen Algebra?

Das Selektionskriterium. Im 1NF Modell beziehen sich Selektionskriterien auf atomare Werte. Im 2NF-Modell beziehen diese sich nicht auf einzelne atomare Werte sondern auf Mengen aus Werten des Attribut-Wertebereichs. Daraus ergeben sich zusätzliche Operationen, wie gleich und ungleich, and, or oder not...

Zusätzliche Operationen in der 2NF

Nest-Operation

Die Attributwerte eines Attributes einer Relation werden zu einer Menge zusammengefaßt, falls die Werte aller restlichen Attribute identisch sind.

Unnest-Operation

Ist die inverse Operation zu Nest.

Was ist eine "NF2-Relation"?

Bei dem NF2-Relationalen Datenmodell wird die erste Normalform aufgehoben. Attribut-Wertebereiche dürfen Mengen sowie Mengen von Mengen sein. Die erste NF ist ein Spezialfall mit atomaren Wertemengen.

Sind D1,D2,...,Dn atomare Wertebereiche (Domains) und ist eine Relation R eine Teilmenge von C1 x C2 x ... Cm, also eine Teilmenge der kartesischen Produkte der Wertebereiche, dann ist es gestattet, komplexe Wertebereiche als Potenzmenge der atomaren Wertebereiche zu konstruieren. Es sind aber keine Wertebereiche zugelassen, welche nur aus kartesischen Produkten bestehen!

Kapitel 4 - Codd's Regeln der Relationalität

Zwölf Regeln der Relationalität

Regel 1: Darstellung von Information

Alle Information in relationalen Datenbanken müssen logisch in Tabellen dargestellt sein, insbesondere

Regel 2: Zugriff auf Daten

Jeder Wert einer relationalen Datenbank muß logisch durch eine Kombination von Tabellenname, Primärschlüssel und Attributname (Spaltenname) auffindbar sein. Dies bedeutet, daß in einer Tabelle an jedem Schnittpunkt einer Zeile mit einer Spalte nur ein Wert stehen darf.

Beispiel

Tabellenname: Angestellte ; Primärschlüssel: Angestellter = Meier; Attributname: Gehalt = 5300

Regel 3: Systematische Behandlung von Nullwerten

Nullwerte stellen in Attributen, die nicht Teil eines Primärschlüssels sind, fehlende Information dar und werden durchgängig gleich, insbesondere unabhängig vom Datentyp des Attributes, behandelt.

Beispiel:

Man kann also nicht in numerischen Feldern bei fehlenden Daten das Feld leerlassen, und bei Textfeldern das Zeichen -- einfügen. Fehlende Informationen werden heute meist mit NULL bezeichnet.

Regel 4: Struktur einer Datenbank

Die Datenbankstruktur wird in derselben logischen Struktur wie die Daten gespeichert, also in Tabellen. Dazu muß die Struktur aller Tabellen, die zu einer Datenbank gehören, in einer Tabelle (dem Katalog) zugänglich sein. Diese Forderung bedingt, daß sich eine Änderung im Katalog automatisch in einer geänderten Datenbankstruktur auswirkt!

Regel 5: Die Abfragesprache

Ein relationales System enthält mindestens eine befehlsgesteuerte Abfragesprache, die mindestens die folgenden Funktionen unterstützt:

Regel 6: Aktualisieren von Views

Alle Views, die theoretisch aktualisiert werden können, können auch vom System aktualisiert werden.

Beispiel:

Hat man zwei Spalten A und B mit Zahlen, so kann man sich eine weitere Spalte definieren, die A*B enthält. Ändert man einen Wert in dieser Spalte, so kann daraus nicht der Wert der Spalten A und B bestimmt werden, da im allgemeinen aus dem Produkt zweier Zahlen diese zwei Zahlen nicht bestimmt werden können. Dieses View kann also theoretisch nicht aktualisiert werden.

Das Problem

Im allgemeinen kann nicht entschieden werden, ob ein View theoretisch aktualisiert werden kann

Regel 7: Abfragen und Editieren ganzer Tabellen

Abfrage- und Editieroperationen müssen als Operanden ganze Tabellen und nicht nur einzelne Sätze erlauben.

Regel 8: Physikalische Unabhängigkeit

Der Zugriff auf die Daten durch den Benutzer muß unabhängig davon sein, wie die Daten gespeichert werden oder wie physikalisch auf sie zugegriffen wird. Dies bedeutet, daß Anwendungen nur auf die logische Struktur des Systems zugreifen dürfen.

Beispiel:

Die Daten dürfen auf einem Datenträger durchaus hierarchisch gespeichert sein. Nur die logische Struktur der Datenbank muß relational sein. Ändert der Datenbankverwalter die physikalische Struktur, darf der Anwender davon nichts mitbekommen.

Regel 9: Logische Unabhängigkeit der Daten

Anwendungen und Zugriffe dürfen sich logisch nicht ändern, wenn Tabellen so geändert werden, daß alle Informationen erhalten bleiben. (z. B. beim Aufspalten einer Tabelle in zwei Tabellen)

Regel 10: Unabhängigkeit der Integrität

Alle Integritätsbedingungen müssen in der Abfragesprache definierbar sein und in Tabellen dargestellt werden. Das System muß mindestens die folgenden Integritätsbedingungen prüfen:

Vollständigkeitsintegrität (Entity Integrity, Existential Integrity)

Ein Primärschlüssel muß eindeutig sein und darf insbesondere keinen Nullwert enthalten.

Beziehungsintegrität (Referentielle Integrität, Referential Integrity)

Zu jedem Fremdschlüsselwert existiert ein Primärschlüsselwert.

Beispiel:

Zu jeder Personalnummer muß es auch einen Namen eines Angestellten geben.

Regel 11: Verteilung der Daten

Anwendungen für eine nicht-verteilte Datenbank dürfen sich beim Übergang zu einer verteilten Datenbank logisch nicht ändern.

Beispiel

Wenn die oben beschriebenen Tabellen in einem Netzwerk auf zwei verschiedenen Rechnern gespeichert sind, darf sich bei der Anwendung nichts ändern, wenn die Tabellen irgendwann auf denselben Rechnern gespeichert werden.

Regel 12: Unterlaufen der Abfragesprache

Unterstützt ein relationales Datenbanksystem neben der High-Level-Abfragesprache eine Low-Level-Abfragesprache, so darf diese die Integritätsbedingungen der High-Level-Sprache nicht unterlaufen.

Beispiel

Die Low-Level Abfragesprache darf z. B. nicht direkt auf die physikalischen Eigenschaften der gespeicherten Daten zugreifen.

Kapitel 5 - Codd Vollständige relationale Sprachen

Welche zwei Schnittstellen zu Datenbanken gibt es?

Prozedurale Sprachen

Deskriptive Sprachen

Somit ist bei deskriptiven Anfragesystemem im wesentlichen der Anfrageübersetzer und Optimierer des DBMS für eine effiziente Abarbeitung verantwortlich und nicht der Programmierer, wie bei prozeduraler Anfrage.

Hohe Komplexität der Übersetzung, da die Auswahlmächtigkeit

Beispiel für prozeduralen Anfragen

Ein typische Beispiel für prozedurale Anfragen beschreibt das Netzwerkmodell:

Erklären sie das Prinzip der Relationenalgebra!

Es wird unterschieden zwischen prozeduraler Algebra und deskriptiven Kalkülen. Ein Ausdruck einer prozeduralen Sprache gibt indirekt immer mit an, wie d.h. durch Ausführung welcher Operationen das Ergebnis berechnet werden kann.

Mengenorientiert

Aus einer oder mehreren Tupelmengen werden neue erzeugt. Anfragen werden in Form formaler Ausdrücke (der Relationenalgebra bzw. des Relationenkalküls) übermittelt.

Relationenalgebra ist niedrig polynomiell.

Optimieren kann man die Relationenalgebra indem man die Anfragebäume optimiert. Selektion und Projektion werden in Richtung Blätter verschoben, um schon anfangs kleine Zwischenergebnisse zu erhalten.

Relationenalgebra ist stets in Maßstab für die Ausdrucksstärke einer Sprache. Falls eine Sprache so Ausdrucksstark ( d.h. es gibt zu jedem Ausdruck in der einen Sprache einen äquivalenten in der anderen) wie die Relationenalgebra ist, so ist diese Codd-Vollständig. SQL ist bspw. nicht-prozedural, d.h. der Fragesteller stellt eine Frage, gibt aber keinen Algorithmus zur Lösung vor. Dieser ist in der Sprache selbst enthalten.

Erklären sie das Prinzip der Relationenkalküle!

Geben im Gegensatz zu prozeduralen Sprachen keine Berechnungsprozedur mit auf dem Weg, sondern nur eine Beschreibung der betroffenen Tupel der Ergebnisrelation.

Sie sind unter bestimmten Umständen Codd-Vollständig!

Wozo SQL - Structured Query Language?

SQL ist eine nicht-prozedurale, mengenorientierte Sprache für Relationale Datenbanksysteme. SQL kann Relationen als Einheiten verarbeiten, verfügt aber z.Z. noch nicht über Steuerstrukturen wie Schleifen oder Case-Anweisungen. SQL kann interaktiv eingesetzt werden oder in einer Programmiersprache eingebettet sein. (embedded SQL)

SQL-Anweisungen teilen sich in zwei Sprachen:

Datendefinitionsprache, zum Vereinbaren von Datenstrukturen, wie Relationen, Zugriffspfade etc..

Datenmanipulationssprache, zum Verarbeiten der Daten durch Einfügen, Löschen oder Updates.

Wichtige SQL-Anweisungen

Select-Anweisung

SELECT * FROM relation [WHERE Bedingung];

Bedinung ist durch Vergleichsoperatoren und den Anweisungen BETWEEN, IN, ANY und ALL definierbar.

Join

SELECT name.attribut {,...} 
FROM relation [Korrelation], relation [Korrelation] 
WHERE bedingung
Durch die Korrelation ist es möglich Joins mit ein und der selben Tabelle durchzuführen. Korrelation heißt nix anderes als zwei Variablen einzuführen, um die Tabellen unterscheiden zu können. Um doppelte Tabellenzeilen zu Vermeiden verwende man SELECT DISTINCT!

Gruppenverarbeitung

Um Tupel herauszufiltern, welche auf gemeinsamen Eigenschaften basieren, bietet SQL einige Möglichkeiten: 

SELECT attribut, {...} FROM relation GROUP BY gruppenattribut {,...} 
[HAVING bedingung]

Gruppenauswertungsfunktionen:

AVG(A), COUNG(A),COUNT(*),MAX(A),MIN(A),SUM(A)

Sortieren

ORDER BY [ASC|DESC]

Wie stellt man den Join in SQL dar?

Seien R(A1,.....,An) und S(B1,....,Bm) Relationen.

In Relationenalgebra:

R[Ai=Bj]S

In SQL:

SELECT A1,.....,An,B1,....,Bm FROM R, S WHERE Ai=Bj

Wie kann man den Natural Join in SQL und in Relationenalgebra darstellen?

Seien S(s1,..,sn,a1,..,am) und R(r1,..,rk,a1..am) Relationen mit gleichen Attributennamen a1..am die sowohl in S als auch in R vorkommen. 

Select S.s1,...,S.sn,S.a1..S.am,R.r1,..,R.rk
Where S.a1=R.a1,..,A.am=R.am
Relationenalgebra: 
R NATJOIN S:=(RxS)[S.a1=R.a1,..,A.am=R.am]
[S.s1,...,S.sn,S.a1..S.am,R.r1,..,R.rk]

Wie stellt man einen Join zwischen einer Relation mit sich selbst dar?

Diese Auto-Join genannte Operation gelingt mit Hilfe der Verwendung von Tupelvariablen: Relationenkalkül 


RANGE ANGEST X

RANGE ANGEST Y

{Y.Name| (X.Gehalt > Y.Gehalt)   (X.Name = Y.Vorgesetzter)}
Relationenalgebra: 

Y[Y.Gehalt > X.Gehalt][X.Name = Y.Vorgesetzter]X [Y.Name]
SQL: 
SELECT Y.Name FROM Angest X, Angest Y WHERE X.Name
 = Y.Vorgesetzter AND Y.Gehalt > X.Gehalt

Wozu benötigt man Tupelvariablen?

Tupelvariablen sind immer dann nötig , wenn der Verbund einer Relation mit sich selbst gebildet werden soll oder dann, wenn bei einem Join von zwei verschiedenen Tabellen Attribute mit gleichen Namen auftreten.

Anders ausgedrückt: Immer dann wenn innerhalb einer Abfrage verschiedene Tupel derselben Relation betrachtet werden, braucht man Tupelvariable.

Wohin wird SQL übersetzt?

SQL wird direkt vom Datenmanager interpretiert.

Was geschieht bei einer SQL-Query an ein DBMS?

  1. Prüfung der Syntax und Zugriffsrechte
  2. Wahl einer geeigneten Methode zur Ausführung der Operation
  3. Feststellen, wie die Operanden gespeichert sind und wie effektiv auf diese Datenstrukturen zugegriffen werden kann (Zugriffspfade)
  4. Generieren von Ausführbaren Code, welcher
  5. die beteiligten Daten aus der DB in den Datenbank-Puffer transferiert
  6. die oben gewählte Methode integriert
  7. das Ergebnis ausgibt
  8. Ausführen des Erstellten Codes

Um nun mehreren Benutzern ein gleichzeitiges Arbeiten zu garantieren, sind alle Schritte bis 5 reentrant. D.h. sie können parallel ablaufen. Jeder Auftrag bekommt einen Platz im Buffer und wird abgearbeitet, wenn es an der Reihe ist. Hier kann es zur Synchronisationsproblemen kommen. Man kann den Buffer als Cache sehen. Schreibt der Prozess geänderte Daten in die DB zurück, muss womöglich ein Update eines anderen Pufferbereiches ausgeführt werden, da dieser sonst noch das falsche Datum trägt. Dies wird meist, wie aus Rechnerarchitektur bekannt, über Dirty-Bits in den einzelnen Seiten des Buffers geregelt. Wird eine Seite benötigt, wird das Dirty-Bit interpretiert und gegebenenfalls die Seite neu von der Platte in den Puffer geladen.

Wie erfolgt die Optimierung von Abfragen? Was ist bei Projektionen zu beachten?

  1. Selektionen möglichst früh ausführen, um die Ergebnismenge klein zu halten
  2. Zusammenfassung von Selektionen zu komplexen Selektionen, da dies die Zahl der Zugriffe auf die Daten minimal hält.
  3. Bei Projektionen zuerst diejenigen Attribute nehmen, die keine Eliminierung von Duplikaten erfordern
    dann möglichst früh (also wenn mindestens ein Schlüssel des Relationenschemas erhalten bleibt), sonst möglichst spät.
  4. Suche nach gemeinsamen Teilbäumen im Operatorbaum und Vereinigung dieser Bäume (Blätter: Relationen, innere Knoten Operationen, Selektion, Join, Projektion)
  5. Joins möglichst spät
  6. Optimierung auf physischer Ebene: Ausnutzung von Sekundärindizes (Invertierung), Sortierung, Speicherstruktur der Datenbanktabellen

Wie wird ein Join ausgeführt? 

Beispiel: R(A,D), S(B,C); Gesucht R[A=B]S

Was macht die Anfrage-Optimierung?

Durch algebraische Optimierung, kann vor Ausführung des Codes schon optimiert werden, in dem Umformungen auf Basis der Relationenalgebra vorgenommen werden. Join-Operationen sind in der Regel sehr teuer. Dagegen sind Selektion und Projektion relativ billige Operationen.

Man unterscheidet das naive Vorgehen (einfach laut Klammerung auflösen) und das optimierte Vorgehen, indem die Anfrage so umformuliert wird, dass wenig aufwendige Operationen bevorzugt werden, um teuere Operationen mit kleinen Relationen ausführen zu können. 

Anfrage > Parsen > Validierung > View-Resolution
 > Optimierung > QEP > Code > Ausführung > Ausgabe

High Level Optimierung:

Auf Grund von Rechenregeln wird die Anfrage optimiert. Ist somit unabhängig vom DBMS.

Folgende Optimierungskriterien sind zu beachten:

  1. optimierte Anfrage muss äquivalent zu Originalanfrage sein
  2. statische Daten, wie die Anzahl von Tupeln pro Relation einbeziehen
  3. eventuelle Sortierung der Tupel innerhalb einer Relation beachten
  4. eventuell existierende Zugriffspfade, wie Sekundärindexe o.ä. nutzen

Low Level Optimierung:

QEP Erstellung und Optimierung der Datenorganisation und Implementierung.

Wie werden Anfragen dargestellt und intern weitergegeben?

Anfragen werden in Form von Operatorbäumen dargestellt. Er zeigt die zu bearbeitenden Relationen, die auszuführenden Operationen und die Präzedenzen (Aufrufreihenfolge) zwischen den Operatoren an.

Schedule-Prinzip

Was ist der Nested-Loop-Join?

sucht nach gleichen Werten der gemeinsamen Attribute in den zu verbindenden Relationen. Dabei muss für jedes Tupel der Relation A jedes Tupel der Relation B verglichen werden. Optimiert wird hier durch blockweißes Lesen der Daten. Somit entsteht quadratischer Aufwand.

Wie arbeitet Sort-Merge-Join?

Sortiert erst die Operanden anhand der Verbund-Attribute aufsteigend und mischt anschliessend die gleichwertigen Attribute zur Ergebnisrelation.
Falls die Operanden-Relation schon sortiert ist, weil z.B. für Attribut A ein Index existiert, ist das Verfahren dem Nested-Loop Join in jedem Fall vorzuziehen, da dann der Aufwand nur noch linear ist...

Wie arbeitet der Hash-Join?

Ist eine Einteilung der Relationen in Partitionen über eine Hashfunktion. Danach kann jede Partition einzeln betrachtet werden.

Was muß man bei der Ausführung von SQL-Anfragen tun?

Wie kann man Datenbanken Tunen?

Es gibt vier grundlegende Prinzipien.

  1. Lokale Optimierung zur Erreichung globaler Effekte (Hardwareausnutzung überwachen)
  2. Partitionierung zur Vermeidung von Bottlenecks ( Transaktionen in Lange und Kurze)
  3. Intitiale Kosten > Laufende kosten (Leseoperationen sind beim Starten teurer - dann billig)
  4. Angemessene Aufgabenverteilung zwischen Systemkomponenten

Systemkomponenten

Tuning kann auch durch Denormalisierung vorgenommen werden, wenn z.B. extrem viele Verbund-Operationen auf die normalisierte Relation angewendet werden müssen.

Kapitel 6 - Physische Datenorganisation

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.

Kaskadierter Index

Welche Arten der Primärorganisation kennen Sie?

  1. Ungeordnete Dateien
  2. Indexsequentiell (siehe ISAM)
  3. Clustered
  4. Hashorganisation
  5. B*-Baum
  6. mehrdimensionale Strukturen (Grids,k-d-Bäume...)

Wie arbeitet ISAM - Indexed-Sequential Access Method?

Die Hauptdatei enthält die Datensätze und die 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.

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:

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:

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

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?

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

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

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:

Bei sekundären Pfaden wird also keine Umsortierung der Datensätze vorgenommen.

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,

Indiziere nicht Attribute

Wie kann man Verbindung zwischen Sätzen unterstützen?

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?

Auf welche Arten lassen sich die Verbindungen auf interner Ebene realisieren?

  1. Invertierung (siehe oben)
  2. Phyisische Nachbarschaft (Sätze werden in einem zusammengefasst und gemeinsam gespeichert)
  3. Listen und Ringe (anhängen variabel langer Zeigerfelder an die Datensätze)
  4. Kettsätze (für rekursive m:n Beziehungen / Stücklisten)
  5. 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 7 - Integrität und Transaktionskonzept

Was kann zur Datenintegrität beigetragen werden?

Durch einzelne wenige fehlerhafte Daten kann der gesamte Datenbestand einer Datenbank zerstört werden. DBMS müssen deshalb einige Fehlersituationen selbstständig erkennen und entsprechend darauf reagieren.

Das Überprüfen von Randbedingungen für Attribut-Ausprägungen und das Überwachen von Beziehungen zwischen Tupeln sind zwei der wenigen Möglichkeiten des DBMS für den ersten Fall. Diese werden im Allgemeinen unter logischer Datenintegrität als Integritätsbedingungen bezeichnet.

Die wichtigste Komponente ist mit Sicherheit der Transaktionsmanager, welcher den Mehrbenutzerbetrieb abgleicht, um Kollisionen zu vermeiden.

In welche fünf Bereiche kann man Integrität klassifizieren?

Was ist semantische Integrität?

Das DBMS muss unabsichtliche Fehlbedienungen oder auch beabsichtigte Fehleingaben erkennen und hier Kontrollmöglichkeiten besitzen, um die Zulässigkeit der Eingaben zu prüfen.

Die Bedingungen werden im konzeptuellen Schema definiert oder im DBMS selbst etwa durch Typprüfungen für Attributwertdomänen oder Bereichsprüfungen numerischer Werte.

Das Problem von Integritätsprüfungen ist die möglich hohe Komplexität. Es muss also ein Trade-Off zwischen Veränderung der Laufzeit, der Wahrscheinlichkeit von Integritätsverletzungen und der Korrektheitsanforderung der jeweiligen Umgebung getroffen werden.

Was ist operationale Integrität?

Wenn mehrere Benutzer gleichzeitig an einer Datenbank arbeiten, können sie sich gegenseitig stören oder beeinflussen, wenn sie auf die selben Daten zugreifen. Auch wenn sich jeder Teilnehmer korrekt verhält, können durch Überschneidung von Operationen Fehler auftreten, welche die Datenbank in einen inkonsistenten Zustand versetzen könnten. Deshalb wird zur Aufrechterhaltung der operationalen Integrität eine Koordination der verschiedenen Operationen notwendig...

Deshalb wird hier der Begriff der Transaktion und der Synchronisation paralleler Transaktionen notwendig.

Was ist eine Transaktion?

Eine Transaktion ist ein Benutzerauftrag, der die Datenbank von einem konsistenten Zustand in einen anderen ebenfalls konsistenten Zustand überführen soll. Eine Transaktion ist zwingend atomar, d.h. nicht unterbrechbar durch irgendwelche anderen Prozesse bzw. Transaktionen!

Interner Ablauf eines SQL Statements

Transaktionen und korrekte Verarbeitung

Es muss eine zeitlich verzahnte Verarbeitung verschiedener Aufträge möglich sein. Dabei muss ein gewisser Grad an Fehlertoleranz garantiert werden können.

Transaktionsverarbeitung = Concurrency-Control + Recovery-Manager Wichtigstes Prinzip bei der Transaktionsverarbeitung ist das Read-Write-Transaktionen Modell, welches eine Abstrahierung erlaubt und dadurch Fehlerverarbeitung und Umgehung erleichtert. Read-Write-Transaktionen führen wiederrum zu Schedules.

Wozu Parallelität bei Transaktionsverarbeitung?

Ein DBMS könnte Konsistenz bewahren, wenn es alle ankommenden Transaktionen in einen Buffer legen würde, um sie dort sequentiell abzuarbeiten. Dies ist aber auf Grund extremer Wartezeiten nicht akzeptabel. Deshalb müssen Transaktionen so weit wie möglich Parallel verarbeitet werden. Dies kann ohne Bedenken geschehen, wenn folgende beiden Bedingungen zutreffen:

Sind diese Bedingungen nicht gegeben kommt es zu Konflikten.

Was sind Phantome?

Phantome sind Objekte in einer Datenbank, welche zu einem bestimmten Zeitpunkt noch nicht existieren, die aber nicht illegal sind. Sie treten bei mehrphasigen Operationen, wie beim Erstellen von Statistiken auf. Wird in der ersten Phase eine Anzahl bestimmt, danach Datensätze hinzugefügt, so treten diese im weiteren Verlauf der Berechnungen als Phantome auf. Das DBMS muss dies irgendwie verhindern. Die Technik hierfür wird später erklärt. (Einführung von LOCK und UNLOCK)

Was bedeutet das ACID-Prinzip?

Atomicity (Atomar)

Aus Sicht des Nutzers wird seine Anfrage (bzw. Programm) komplett oder gar nicht ausgeführt. Falls ein Fehler während der Ausführung auftritt, erscheint die Datenbank in dem Zustand, als wäre der Code nie ausgeführt worden. Der Recovery Manager biegt es wieder gerade.

Consistency (Konsistenz)

Alle Integritätsbedingungen der DB werden eingehalten und die DB wird in einem konsistenten "Zustand" gehalten, falls sie vor Ausführung der Transaktion in einer solchen war.

Isolation

Das Programm läuft völlig unabhängig von eventuell parallel laufenden Prozessen in einem gesicherten Pufferbereich ab. Zur Verarbeitung bekommt des Programm nur sichere konsistente Daten aus der DB. Die Isolation verhindert somit Konflikte im Mehrbenutzerbetrieb.

Durability (Persistenz)

Falls eine "Befehl erfolgreich ausgeführt" Meldung angezeigt wird, muss sichergestellt sein, dass die geänderten Daten auch nach jedem Hard- oder Softwarefehler permanent in der Datenbank erhalten bleiben. Sogar wenn die Daten sich zu diesem Zeitpunkt noch im Puffer und nicht auf dem Sekundärspeicher befinden.

Was sind die Kostenkriterien einer Transaktion?

CPU-Intensität und I/O-Intensität.

Kann eine Transaktion zwischen BOT und EOT ein rechtliches Dokument erzeugen?

Nein, die Daten sind erst nach EOT bzw. nach dem abschließenden Commit 'amtlich'. Falls eine Dokument zwischen BOT und EOT amtlich wäre, dann wäre im übrigen die Rücksetzbedingung verletzt.

Kapitel 8 - Concurrency Control

Weshalb Zugriffe auf Datenbankobjekte synchronisieren?

Ziel ist eine verzahnte Ausführung aller Transaktionen, um Antwortzeit und Performance hoch zu halten. Dafür müssen serialisierbare Schedules erstellt werden. Ein Schedule ist dann serialisierbar, wenn er im Ergebnis äquivalent zu der möglichen seriellen Ausführung der Transaktionen ist. Auftretende Synchronisationsprobleme, wie Dirty Read, Lost Update und Inkonsistent Read müssen ausgeschlossen werden.

Scheduled (verzahnt)

T1:read(a) -> T2:read(a) -> 1:read(b)

seriell

T1->T2->T3, also hier T1:read(a) -> T1:read(b) -> T2:read(a)

Desweiteren muss sichergestellt werden, daß die Transaktionen dem ACID-Prinzip genügen:

Atomicity / Atomarität

Eine Transaktion wird entweder vollständig oder gar nicht ausgeführt.

Consistency / Konsistenz

Eine Transaktion überführt einen konsistenten Zustand der Datenbank in einen anderen konsistenten Zustand.

Isolation

Die Zwischenergebnisse gleichzeitig ablaufender Transaktionen dürfen jeweils für die anderen Transaktionen nicht sichtbar sein. D.h. keine Transaktion merkt, daß andere Transaktionen parallel zu ihr laufen. Dies impliziert, das eine Transaktion rücksetzbar ist.

Durability / Dauerhaftigkeit

Die Ergebnisse einer erfolgreichen Transaktion werden gegen Versagen der Hard- und Software gesichert und können nur durch eine weitere Transaktion wieder geändert werden.

Im klassischen Fall werden die Punkte Consistency und Isolation dadurch erreicht, daß man verlangt, daß die Transaktionen serialisierbar ablaufen. Verletzungen der Serialisierbarkeit müssen erkannt und verhindert werden. Hierfür gibt es prinzipiell zwei Kategorien von Verfahren, pessimistische und optimistische. Sperren gewährleisten Konfliktserialisierbarkeit (Reihenfolge von Konfliktbeteiligten bleibt in beiden Schedules gleich) und sind pessimistische Verfahren. Sie definieren sich durch zwei Phasen:

Deadlocks können auch beim strikten 2-PL entstehen. Nur Preclaiming kann Deadlocks ausschließen, da hier alle Sperren auf einmal und atomar gesetzt werden und keine Sperren nachträglich angefordert werden können. Deadlocks werden normalerweise nach Timeouts auf Zyklen im Wartegraphen geprüft und erkannt.

Welche drei Definitionen gibt es für die Äquivalenz von Schedules?

Zustands-Serialisierbarkeit (ZSR)

Dies ist die intuitivste Definiton. Zwei Abfolgen der gleichen Transaktionen sind äquivalent, wenn für alle möglichen Anfangszustände und Semantiken der Transaktionen die Endzustände jeweils gleich sind.

Sichten-Serialisierbarkeit (SSR)

ist eine Verschärfung der Zustands-Serialisierbarkeit. Es wird zusätzlich verlangt, daß jede Leseoperation in den beiden 'Schedules' jeweils den Wert von derselben Schreiboperation erhält.

Konflikt-Serialisierbarkeit (KSR)

verlangt, daß die Reihenfolge jeweils zweier in Konflikt stehenden Operationen in beiden 'Schedules' gleich bleibt.

Erkäutern Sie das Read-Write Modell für Transaktionen!

Eine Transaktion ist eine endliche Folge von Schritten oder Aktionen der Form read(x) oder write(x). Somit ist eine Transaktion ein Straight-line Programm von Lese und Schreiboperationen. Es wird die Annahme gemacht, das eine Transaktion keine internen Redundanzen aufweisst. D.h. jedes Datenobjekt wird nur einmal gelesen bzw. geschrieben. Read bzw. Write aktionen sind atomar und dürfen nicht unterbrochen werden.

Schedule-Prinzip

Schwerpunkte

  1. Zeitlich verzahnte Ausführungsreihenfolgen von Schritten (read oder write) werden durch Schedules modelliert. (dynamischer Aspekt)
  2. Unter welchen Bedingungen ist ein Schedule korrekt?
  3. Entwurf und Verifizierung von Scheduling-Verfahren oder kurz Schedulern.

Was sind Schedules?

Durch Hinzunahme von zwei Pseudoschritten zu den Schritten read und write, lassen sich Schedules modellieren:

CommitTransaktion erfolgreich beendet. Ergebnisse können für andere Prozesse freigegeben werden.
AbortTransaktion aufgrund eines Fehlers vorzeitig abgebrochen.

Vollständige Schedules sind Schedules, bei denen alle geöffneten Schritte terminiert werden und auch die Schritte a und c enthalten sind. Normale Schedules beinhalten dies normalerweise nicht, da aus Effizienzgründen bei Begin einer Transaktionsverarbeitung noch gar nicht alle Transaktionen vorhanden sind. Diese Treffen beim Scheduler ja eh Schrittweise ein...

Zwei Daten-Operationen stehen im Konflikt, falls sie auf demselben Objekt operieren und eine von ihnen schreibt.

Was heißt Serialisierbarkeit?

Ein Schedule heißt seriell, wenn alle Schritte einer Transaktion unmittelbar hintereinander ablaufen. Zwei Schedules sind äquivalent, wenn sie die gleichen Transaktionen beherbergen und die gleiche Abhängigkeitsrelation besitzen. Ein Schedule heißt Konflikt-serialisierbar, wenn es für den Schedule einen äquivalenten seriellen Schedule gibt. D.h. wenn ein zeitlich verzahnter Schedule die gleichen Konflikte wie irgend eine serielle Abarbeitung aufweist, so kann dieser als Konsistenz bewahrend eingestuft werden.

Prüfen lässt sich dies mit einem Präzedenzgraph, welcher als Knoten die Transaktionen und die Kanten nach der zeitlichen Abarbeitung beinhaltet. Tritt in diesem Graph ein Zyklus auf, so ist der Schedule nicht Konflikt-serialisierbar. Die topologische Sortierung eines DAG's würde einen korrekten Schedule ergeben.

Erklären Sie wie Serialisierbarkeitsbedinung und Logs arbeiten!

Ein Log ist eine Folge von Read bzw. Write Operationen auf ein bestimmtes Objekt x mit der dazugehörigen Transaktionsnummer als Index. Gibt es zwei Transaktionsfolgen T1 und T2, so könnte im Log für das Objekt a (log(a)) folgende Folge von Operationen stehen: 

r1 w1 r2 w2

Dies heißt nichts anderes als:

  1. Objekt a wird von Transaktionsfolge 1 gelesen
  2. Objekt a wird von Transaktionsfolge 1 geschrieben
  3. Objekt a wird von Transaktionsfolge 2 gelesen
  4. Objekt a wird von Transaktionsfolge 2 geschrieben

In den einzelnen Logs muss eine eindeutige serielle Ausführung der Operationen möglich sein. Treten in zwei oder mehr verschiedenen Logs unterschiedliche Reihenfolgen auf wie z.B. r2 < r1, so ist das system nicht serialisierbar.

Überprüfen kann man die Deadlocks über den Wartegraphen, welcher sich leicht aus den Logs herstellen läßt.

Wie prüft man einen Schedule auf Deadlocks?

Man stellt die einzelnen Logs auf und prüft den Wartegraphen. Ein Log ist eine Folge von Transaktionen auf ein bestimmtes Objekt. Folgendes Beispiel soll das Vorgehen erläutern.

Folgender Schedule ist gegeben:

S[r1(b),r2(b),w2(b),r2(c),r2(d),r3(b),r4(d),w3(a),w4(d),r5(a),r5(c),w2(c)]

1. Aufstellen der Logs für die beteiligten Objekte a,b,c und d

log(A) log(b) log(c) log(d)
w3
r5 		r1
r2
w2
r3 		r2
r5
w2 		r2
r4
w4

2. Den Wartegraphen nach dem extrahierten Log aufstellen

  1. Zeichne für jede Transaktion einen Knoten.
  2. Wiederhole für jeden Log in welchem mindestens eine Transaktion schreibt und zwei lesend zugreifen:
    • Verbinde jede Leseoperation r vor dem Write mit dem Knoten der Schreibertransaktion
    • Verbinde jede Schreibertransaktion mit jedem danach folgenden Readbefehl
    • Schlingen sind zwecklos und können dabei ignoriert werden

Wartegraph mit Zyklus

3. Wartegraph auf Zyklus prüfen, denn mit ist der Schedule nicht serialisierbar

Wie wir sehen enthält der Graph einen Zyklus. Dies bedeutet, daß die genannten Bedingungen in den Logs nicht gelten. Und zwar das die Reihenfolgen der Zugriffe in allen Logs gleich ist. Dies ist hier nicht der Fall. Denn was nicht sein darf, ist 

T2 vor T3 kommt, T3 vor T5 komt und T5 vor T2 kommt

Deshalb erzeugen T2, T3 und T5 einen Deadlock.

Was ist die Serialisierbarkeitsbedinung in Schedules?

Die oben erkläre Bedingung lässt sich auf Schedules übertragen. Ein Schedule ist ja nichts weiter als eine Folge von Read / Write Operationen, welche als Zusammenfassung aller Logs aufgefasst werden kann. Somit gilt in einer Schedule die Serialisierbarkeitsbedinung ebenso. Desweiteren kann man aus einer Schedule die einzelnen Logs herleiten.

Ein Schedule ist nicht serialisierbar, wenn sein Graph bestehend aus den Transaktionen und den gerichteten Kanten, welche den Ablauf beschreiben, einen zyklus enthält.

Wann stehen zwei Operationen bzw. Transaktionen in Konflikt?

Wenn beide auf das selbe Objekt zugreifen und eine von beiden eine Schreiboperation ist.

Warum wird nicht ein Prinzip wie "Shortest Transaction Next" angewandt?

Weil solche Prinzipien nicht die Reihenfolge der Transaktionen beibehalten!

Welche Synchronisationsprobleme gibt es?

Lost Update

read1(x)  >  read2(x)  >  update1(x)  >  update2(x)

Das Update von Prozess 1 geht somit verloren.

Dirty Read

Read1(x)  >  Update1(x)  >  Write1(x) >  Read2(x)  >  Update2(x)  >  ABORT1 > Write2(x)

Inconsistent Read

Prozess eins ließt ein Datum und speichert es zwischen. Prozess 2 dagegen, ändert das Datum erst danach und somit hat Prozess 1 den falschen alten Wert des Datums gelesen.

Was passiert alles bei einem Commit?

  1. After-Images müssen zu diesem Zeitpunkt im Log stehen
  2. Before-Images können verworfen werden
  3. Datenbank kann muß aber nicht geschrieben sein (Daten können sich auch noch im Systempuffer befinden)
  4. Daten werden für die Außenwelt sichtbar

Welche Sychronisationsverfahren für Schedules gibt es?

verifizierend (optimistisch, validierend)

Vor dem Commit wird geprüft, ob eine Transaktion an einer nichtserialisierbaren Schedule beteiligt ist. Falls ja, dann wird die Transaktion abgebrochen. (abort) Die Prüfung auf Serialisierbarkeit wird auch certification bzw. validation genannt.

präventiv (pessimistisch)

nicht-serialisierbare Schedules werden verhindert, v.a. durch Sperrverfahren, welche durch Sperren gemeinsamer Objekte gemeinsamen Zugriff verhindern (selten durch Zeitstempelverfahren).

Wie sehen optimistische Verfahren aus?

In der Arbeitsphase sind nur lesende Zugriffe auf die Datenbank möglich (kein Rollback nötig). Die Zwischenspeicherung erfolgt in einen privaten Arbeitsbereich.

In der Validationsphase erfolgt die Prüfung auf Nicht-Serialisierbarkeit der entstandenen Schedule (Abhängigkeitsgraph hat Zyklen).

Definition der Abhängigkeit

Konflikt zwischen zwei Operationen besteht wenn:

Zugriff auf dasselbe Objekt erfolgt, davon mindestens ein Schreibzugriff. Ty ist abhängig von Tx, gdw. es Operationen ax und by gibt die in Konflikt miteinander stehen und ax vor by in S ausgeführt werden soll.

Schreibphase: veränderte Objekte werden in die Datenbank geschrieben (Commit).

Was genau passiert in der Validationsphase, welche Operationen werden hier betrachtet?

Es genügt schreibende Zugriffe parallel ablaufender Transaktionen zu betrachten und mit den Lese- und Schreiboperationen der Transaktion für die die Validation durchgeführt wird zu vergleichen. Die Prüfung auf Zyklen erfolgt auch hier im Abhängigkeitsgraph.

KnotenTransaktionen, gerichtete Kanten zu jeweils abhängigen Transaktion
Abhängigkeit: mindestens eine Operation steht im Konflikt mit einer vorher in der Schedule stehenden Operation einer anderen Transaktion.

Wie kann man Transaktionen synchronisieren?

Durch den Einsatz von Synchronisationsverfahren:

Welche Sperrverfahren gibt es?

Zwei-Phasen-Sperrprotokolle werden am häufigsten benutzt - vor allem Sperren bis EOT. Premclaiming wird dagegen kaum verwendet. Folgende weitere klassifikation ist möglich...

RX-Sperrverfahren:

Alle Transaktionen können gleichzeitig das Datenobjekt lesen. Falls eine Transaktion ein Datenobjekt ändert, müssen die Anderen warten.

RAX-Sperrverfahren:

Die Änderung des Datenobjektes erfolgt erst auf einer Kopie, so dass andere Transaktionen das Datenelement trotzdem weiterhin lesen können. Erst bei Transaktionsende wird das Datenobjekt durch die Kopie überschrieben.

RAC-Sperrverfahren:

Das Überschreiben des Datenelements durch die Kopie kann beim RAX-Sperrverfahren erst erfolgen, wenn keine lesenden Transaktionen mehr auf das Datenobjekt zugreifen. Das RAC-Sperrverfahren läßt demgegenüber weiterhin das Lesen zu, da beim Transaktionsende eine Kopie des ursprünglichen Datenobjekts geschrieben wird, auf die im Bedarfsfall zugegriffen werden kann.

Erläutern Sie die Concurrency Control!

Dynamische Erzeugung serialisierbarer Schedules, um Mehrbenutzerbetrieb zu überwachen und zu regulieren.

Schedule-Prinzip

Sendet der Scheduler ein Commit an den Recovery-Manager, so ist die Transaktion erfolgreich beendet worden. Dies bedeutet auch, daß alle Transaktionen im Scheduler initiiert werden. Wird ein Abort an den Recovery-Manager übermittelt, so weiß dieser, daß der Effekt nicht in der Datenbank sichtbar werden soll.

Was macht der Lock-Manager?

Der Lock-Manager ist Teil des Transaktionsmanagers, welcher die Lock- und Unlock-Prozeduren verwaltet und ausführt. Seine Aufgaben sind

Der Lock-Manager verwaltet seine Sperren in einer Tabelle, welche Einträge in der Form Objekt-ID, Transaction-ID und Modus (read,write,intentieren) enthält. Falls weitere Transaktionen einen weiteren Lock erfordern, werden diese an eine Warteschlange an die entsprechende Zeile angehängt.

Was ist Preclaiming?

Alle von einer Transaktionen benötigten Objekte werden vor Ausführung zusammen gesperrt. Notwendig dafür ist, dass alle notwendigen Betriebsmittel (hier read bzw write auf Objekte) vorher bekannt sein müssen. Eine andere weniger elegante Möglichkeit ist die des Timeouts. Nach einer definierten Wartezeit wird die Transaktion abgebrochen.

Kapitel 9 - Scheduler und Recovery

Wie funktioniert das Sperren bei Datenbanken?

Verwaltet werden Sperren durch den Lock-Manager. Lock a=Objekt wird angefordert und unlock a=Objekt wird freigegeben. Alle Locks werden in einer Sperrtabelle eingetragen.

Sperrprotokoll

Wie müssen Sperren gesetzt und freigegeben werden, damit serialisierbare Schedules entstehen? Zwei-Phasen-Sperrprotokoll!

Welche Sperrmodi gibt es?

Welche Arten von Sperren benötigt man?

Welches sind die sperrbaren Einheiten in einer Datenbank?

Sperrhierarchie

Datenbank - Area - Tabelle - Tupel/Seite(Lock-Escalation)

Deadlock-Behandlung (tritt bei exklusiven Sperren auf) wobei Schedules wechselweise auf Freigabe einer Sperreinheit warten

Livelock: durch wiederholt ungünstige Zuteilung von Sperren kann eine Transaktion permanent blockiert werden.

Was sind sperrende Scheduler?

Bei Sperrenden Schedulern werden so genannte Locks verwendet, um den Zugriff auf gemeinsam genutzte Daten zu synchronisieren. Eine gesetzte Sperre bedeutet, daß das Objekt für andere nicht verfügbar ist.

Ein sperrender Scheduler unterscheidet zwischen:

Welche Regeln gelten bei sperrenden Schedulern?

  1. falls im Schedule irgendwo ein Read (oder Write) auftritt, so gibt es vor diesem im Schedule ein Lock und irgendwo nach diesem ein Unlock
  2. Für jedes Read (oder Write) gibt es genau ein Lock und ein Unlock und nicht mehr
  3. read unlocks und write unlocks sind nicht redundant

Durch das exlkusive Sperren von Ojekten entsteht die Gefahr von Deadlocks. Desweiteren ist das Permanente Blockieren von Objekten möglich, wenn die Sperren ungünstig zugeteilt werden.

Wie arbeitet das 2-Phasen-Sperren?

Ein Scheduler ist ein 2PL Scheduler, wenn

  1. er die oben erwähnten drei Regeln einhält
  2. ist x durch zwei verschiedene Transaktionen gesperrt, so stehen diese nicht in Konflikt
  3. ein Sperrprotokoll hat zwei Phasen, wenn nach dem ersten Unlock-Schritt, keine weiteren Locks folgen können

Somit ist genau nach den ersten Unlock Phase 1 (das Sperren) beendet und Phase 2 begonnen.

Falls ein Objekt mit einer Lese-Sperre versehen wurde, so ist es nicht exklusiv gesperrt, sondern im shared mode. Somit können andere Objekte auch Lese-Sperren auf das Objekt referenzieren.

Falls das Objekt mit einer Schreib-Sperre versehen wurde, so ist es im exclusive mode, d.h. exklusiv gesperrt. Somit können keine anderen Transaktionen Lese- oder Schreib-Sperren auf das Ojekt referenzieren.

Schedule-Prinzip

Varianten des 2PL

Conservative two-phase-locking C2PL (statisches 2PL) = Was ist Preclaiming?

Jede Transaktion setzt zu Begin ihrer Ausführung (BOT) alle Sprerren gleichzeitig. Nachteil dieses Verfahren ist es, daß alle Read- und Write-Sets vorher bekannt sein müssen. Dazukommt, daß falls ein Konflikt mit einer Sprerre Auftritt, die gesamte Transaktion warten muß, bis diese durch das Unlock der anderen Transaktion aufgelöst wird. Da dies selten der Fall ist, wird es wenig benutzt. Der Vorteil ist hier aber, daß Deadlocks umgangen werden, da diese nicht auftreten können.

Das Preclaiming wird kaum implementiert.

Schedule-Prinzip

Strict two-phase-locking S2PL (dynamisches 2PL/Sperren bis EOT)

Alle gehaltenen Sperren einer Transaktion werden erst nach ihrem letzten Schritt aufgelöst. Dieses Verfahren ist von großer Bedeutung, da es ein isoliertes Rücksetzen von Transaktionen garantiert. D.h. im weiteren, daß eine Transaktion isoliert rückgesetzt werden kann, um danach wieder neu gestartet zu werden, ohne das andere Transaktionen beeinflußt werden. (ACID)

Schedule-Prinzip

Warum wird in der Praxis fast immer das strenge 2PL verwendet?

Man stelle sich zwei Transaktionen T1 und T2 vor. Das normale 2PL hätte bei folgendem Ablauf einige Probleme:

  1. T1 sperrt das Objekt A (lock(T1,A))
  2. T1 gibt A wieder freu
  3. nun sperrt T2 das Objekt A
  4. Die Transaktion T2 wird beendet (commit(T1))
  5. Das Beenden (commit) von T1 schlägt fehl
  6. Somit muss T1 zurückgesetzt werden
  7. T2 muss aber auch zurückgesetzt werden, da es das Objekt A auch verwendet hat (Dominoeffekt)
  8. T2 wird zurückgesetzt obwohl es bereits commited war! (wiederspricht ACID Prinzip: Dauerhaftigkeit)

Deshalb wird das strenge 2PL verwendet, weil hier dieser Ablauf gar nicht erst stattfinden kann. T1 würde die Sperre auf das Objekt A bis zum Schluss halten, bevor T1 commited wird. Erst dann kann T2 das Objekt A sperren. Ein eventuelles Rücksetzen von T1 durch das Recovery hätte somit keine weiteren Folgen (kein Dominoeffekt möglich).

Wie können sperrende Scheduler getuned werden?

  1. Entfernen unnötiger Sperren
  2. Zerlegen langer Transaktionen in mehrere kurze
  3. spezielle Techniken für lange Reads (Read Only keine Sperren weil Backup dieser)
  4. sinnvolle Granularität = Feinheitsgrad (Record-Level, Page oder Table Locking)
  5. Schema Updates bei geringer Aktivität durchführen (System Katalog wird zum Flaschenhals)
  6. Deadlock Intervall bei 2PL (Zylisch Wartegraphen auf Zyklen untersuchen)

Wie arbeiten Zeitstempel-Verfahren?

Dieses Verfahren soll von vornherein verhindern, dass Deadlocks entstehen können. Anstelle von Sperren, wird eine Transaktion mit einer drohenden Verletzung der Serialisierbarkeitskriterien abgebrochen und neu gestartet. Es gelten folgende Regeln:

Wie arbeiten optimistische Verfahren?

Die Transaktionen arbeiten völlig ohne Synchronistation. Erst bei einem Commit wird der Abhängigkeitsgraph auf Serialisierbarkeit (=Zyklusfreiheit) geprüft. Falls Zyklen auftreten, wird die Transaktion abgebrochen. Implementation:

Vorteile

Beschreiben Sie die drei Phasen der optimisitischen Verfahren!

1.Phase: Lesen & Verarbeiten

Aus Anwendungssicht ist dies die "eigentliche" Transaktion. Es werden alle benötigten Objekte gelesen und in einem gesicherten (isolierten!) Buffer hinterlegt. Die Verarbeitung der Objekte findet nun ausschließlich in diesem Bereich statt. So bleiben die Transaktionen für andere Prozesse vorerst unsichtbar.

2.Phase: Validierung der Ergebnisse

Nach dem Ende der Lesephase wird nun geprüft, ob die beteiligten Transaktionen mit Transaktionen parallel laufender Prozesse in Konflikt geraten ist. Ist dies der Fall wird die Transaktion einfach abgebrochen. Da alle Transaktionen in einem gesicherten Bereich liegen, brauch dieser also nur wieder zur "Wiederverwendung" freigegeben zu werden.

3.Phase: Rückschreiben auf Datenbank

War die Validierung erfolgreich werden alle Transaktionen aus dem Buffer in die Datenbank zurückgeschrieben. Die Transaktion ist hiermit beendet. (commited)

Wie funktioniert das Validieren genau?

Schritt 1:

Allen Transaktionen wird beim Eintritt in die Validierungsphase eine Serialisierungsnummer zugewiesen. Es wird für jede beteiligte Transaktion geloggt, welche anderen Transaktionen in der Lesephase beendet werden. Über die von diesen Transaktionen geschriebenen Objekte wird Buch geführt.

Schritt 2:

Für alle Transaktionen die während der Lesephase dieser Transaktion beendet wurden, wird geprüft ob die Lesemenge geich der Schreibmenge ist. Sind die Mengen ungleich, so wird abgebrochen.

Können bei optimistischen Verfahren Deadlocks entstehen?

Nein, denn ohne Sperren (exlusiver Betriebsmittelentzug) können keine Deadlocks entstehen!

Was ist mit Deadlocks bei Schedules?

Das 2-PL ist nicht Deadlock frei. Erklärung dafür ist, daß Locks sich gegenseitig blockieren können, aufgrund der Vorbedingung, daß ein exklusiv gesperrtes Objekt, nicht mehrfach reserviert werden kann. Einmal im Deadlock, kann man ihn nicht einfach durch ein Unlock auflösen, da dann ja die nicht aufgerufenen Locks nicht mehr in Kraft treten könnten. Eine weitere Situation, wo Deadlocks entstehen können, sind Lock-Konvertions. Updaten 2 Transaktionen gleichzeitig ihr Lesesperren auf ein Objekt X zu Schreib-Sperren, kann dadurch auch ein Deadlock provoziert werden. Deadlocks können mit Hilfe von Timeouts oder Wartegraphen (Zyklus bedeutet Deadlock) erkannt werden.

Bei welchen Synchronisationsverfahren können Deadlocks auftreten?

Bei Sperrverfahren, wenn man 2-Phasen-Sperrprotokoll oder Sperren bis EOT verwendet.

Wie kann man das Deadlock-Problem bei Transaktionen behandeln?

Verhinderung

Preclaiming, Zeitmarken auf Transaktionen (Abbruch im Falle der Deadlockgefahr durch Sortierung nach BOT)

Erkennung

Timeout und Prüfung des Wartegraphen auf Schlingenfreiheit oder Kombination beider Verfahren (Aufbau des Wartegraphen bei Timeout)

Erläutern sie die Deadlock-Problematik!

Ein Deadlock ist zyklisches Warten durch exklusive Zugriffs-Anforderung (exklusive Locks) mehrerer Schedules auf die gleichen Objekte (Betriebsmittel).

Was ist denn ein Livelock?

Livelocks entstehen, wenn nicht-serialisierbare Transaktionen immer wieder neu gestartet werden und somit eine ungewollte Iteration hervorufen wird.

Wie erkennt man Deadlocks und löst sie auf?

Die Prüfung auf Zyklen geschieht im Warte-Graph. Gerichtete Kante von Ti nach Tj, wenn Ti auf Tj wartet. Die Auflösung erfolgt indem die billigste Transaktion zurückgesetzt wird.

Wann prüft man auf Deadlocks?

Die Prüfung auf Zyklen erfolgt im Wartegraphen nach Einfügen einer Kante, in bestimmten Intervallen, wenn eine Transaktion über eine gewisse Zeit gewartet hat (Timeout).

Was ist der Unterschied zwischen Deadlock und Timeout?

Timeout: eine bestimmte Transaktion wartet auf ein Objekt länger als eine bestimmte Maximalzeit, trotzdem kann eine korrekte Fortsetzung möglich sein.

Deadlock: mindestens zwei Transaktionen warten jeweils auf die andere => unendliches Warten. Auflösung ist nur durch Abbruch einer der beiden Transaktionen möglich.

Weitere Fragen und Antworten

Warum benutzt man bei Datenbanken keine Semaphore?

Semaphore stellen bei Betriebssystemen den exklusiven Zugriff auf Betriebsmittel durch Prozesse sicher, dies garantiert im Falle der DB-Transaktionen aber keine Serialisierbarkeit! Exklusive Sperren machen Deadlocks erst möglich (siehe Deadlockvoraussetzungen bei Betriebssystemen)!

Wann ist eine Transaktion rücksetzbar?

Rücksetzbarkeitsbedingung für Lesen: Transaktion T kann erst dann abgeschlossen werden, wenn alle Transaktionen, von denen T Daten gelesen hat, abgeschlossen sind.

Rücksetzbarkeitsbedingung für Schreiben: Eine Transaktion darf ein Objekt erst schreiben, wenn alle Transaktionen, die x zuvor geschrieben haben, abgeschlossen oder abgebrochen sind.

strikte Ausführung: Transaktion T darf ein Objekt x erst schreiben oder lesen wenn alle Transaktionen, die x geschrieben haben, abgeschlossen oder abgebrochen sind.

Wie kann man Deadlocks erkennen und behandeln?

Die Erkennung erfolgt durch Prüfung des Wartegraphen auf Schlingenfreiheit- Die Behandlung kann durch Abbrechen der billigsten Transaktion bzw. durch den Einsatz von präventiven Synchronisationsverfahren erfolgen.

Warum ist Deadlockvermeidung unrealistisch?

Bei Produktionsdatenbanken hat man es mit einer großen Zahl sich fortlaufend ändernder Objekte zu tun. Zwischen diesen Objekten bestehen nahezu beliebig komplexe Querbezüge. Die Anzahl der benötigten Sperren ist in der Regel unbekannt. Beim Preclaiming wird zudem die Parallelität der Transaktionen und damit die Gesamtperformanz eingeschränkt.

Was ist der Unterschied zwischen pessimistischen und optimistischen Verfahren

Pessimistische Verfahren garantieren die Serialisierbarkeit von Transaktionen, optimistische Verfahren stellen die Parallelisierung in den Vordergrund und brechen beim Eintreten eines Deadlocks eine der beteiligten Transaktionen ab.

Wozu ist die Recovery notwendig?

Das Recovery System eines DBMS ist für die Fehlerverarbeitung zuständig. Dabei werden die Fragen geklärt, wie es Transaktionen bei Fehlererkennung abbrechen kann, ohne andere aktive Transaktionen zu beeinflussen oder wie sich das System nach einem Totalausfall wieder in einen stabilen konsistenten Zustand zurückversetzen kann.

Welche Fehlerklassen müssen erkannt werden?

  1. Transaktionsfehler, wenn eine Transaktion den Commit-Status nicht erreicht ( abort ). Der Zustand der DB vor Ausführung der Transaktion muß wieder hergestellt werden. Somit müssen eventuell ausgeführte Transaktionen wieder rückgängig gemacht werden.
  2. Systemfehler, wie Fehler im DBMS Code, BS oder in der Hardware selbst. Des weiteren zählen Stromausfälle mit dem Verlust des instabilen Speichers (Puffers) zu Systemfehlern.
  3. Mediafehler, wie Head Crashes von Platten, wo Teile des stabilen Speichers verlorengehen.

Wie funktioniert das Recovery-Protokoll?

Es gibt zwei Klassen von Transaktionen, welche beim Recovery unterschieden werden müssen.

  1. Transaktionen, welche vor dem Crash commited waren.
  2. Transaktionen, welche zum Zeitpunkt des Fehlers noch aktiv waren.

Der Rücksetzmechanismus muß nun sicherstellen, daß alle Änderungen der DB einer not-commited transactions mit einer UNDO-Operation rückgängig gemacht werden und alle freigegebenen Operationen mit einer REDO-Operation erneut durchlaufen und permanent auf die DB übertragen werden.

Es gibt zwei Arten von Datamanagern. In-Place-Updateing bedeutet, daß immer eine Kopie der aktuellen Daten sich im Puffer befindet. Ein zweites Konzept hält immer eine weitere Sicherheitskopie im Buffer - die Schattenkopie. Das Konzept heißt Schattenkopiekonzept oder Defeered Updating.

Der Puffer enthält je Seite ein Dirty-Bit, falls die Seite mit der Originalseite auf dem Sekundärspeicher inkonsistent ist.

Recovery-Manager

Er stellt sicher,daß alle Operationen atomar ausgeführt werden und konkurrierende Zugriffe synchronisiert werden. Aber der Scheduler ist es, welcher die Ausführungsreihe bestimmt.

Um nach einem Systemfehler erfolgreich ein restart durchführen zu können, ist ein Logbuch notwendig. Es gibt zwei grundlegende Log-Konzepte.

Physischer Log Logischer log
Enthält alle Informationen über die von Transaktionen geschriebenen Werte. (Transaktion, Before- und Afterimage) Die Einträge werden sortiert Log gespeichert. Enthält eine Beschreibung der Operationen in deklarativer Art und Weise. Macht das wiederherstellen aufwendiger.

Zusätzlich zur vollen wiederherstellung (Rollbacks), ist es notwendig, alle Listen (active, commit, abort) und auch die Zeiten BOT(t) und EOT(t) im Log zu sichern. So kann aufgeklärt werden, welche Operationen mit Undo- und welche mit Redo-Operationen zu bearbeiten sind.

Rollback

Rollback ist das rückgängigmachen von Änderungen einer oder mehrerer Transaktionen in einer Datenbank. Dazu sind Informationen über den Datenbankzustand vor der Transaktion notwendig.

Welche zwei grundlegenden Techniken gibt es für die Umsetzung des Rollbacks?

Wie werden die Logfiles benutzt?

Vor jeder Veränderung eines Objektes wird dessen alter Zustand (eine Kopie des Originalobjektes) in eine Logfile geschrieben. Bei einem Rollback wird diese Logfile rückwärts gelesen und abgearbeitet. Während dieser Abarbeitung wird jedes beteiligte Objekt mit dem Altwert aus der Logfile wieder überschrieben (bzw. rückgesetzt).

Updates auf Kopien

Änderungen einer Transaktion werden erst in die Datenbank geschrieben, wenn die Transaktion beendet ist. (siehe optimistische Verdfahren der Serialisierbarkeit)

Rollback heißt hier, daß die Kopien einfach fallen gelassen werden. Diese Technik wird auch deferred update. ("verzögert", da alle Änderungen erst nach EOT in die DB geschrieben werden)

Was sind Checkpoints?

Bei einem System-Neustart muss das System alle zum Zeitpunkt des Zusammenbruchs aktiv gewesenen Transaktionen rücksetzen. Das sind die Transaktionen, welche keinen EOT Eintrag im Log stehen haben. Das Problem ist nun folgendes. Im Worst Case muss das Recovery alle Transaktionen bis zum Begin des Logfiles zurückverfolgen, um sicher zu sein, daß keine Transaktion vergessen wurde.

Abhilfe schaffen hier sogenannte Checkpoints:

Um das Korrekte arbeiten der Checkpoints gewährleisten zu können, muss sicher gestellt werden, daß bei EOT alle Objekte einer Transaktion auch wirklich auf die Platte geschrieben wurden, da sonst das EOT des Logfiles nicht als Beweis gültig wäre...

Welche Arten von Checkpoints gibt es?

Bei laufendem Betrieb

Hier werden alle laufenden Operationen (nicht Transaktionen) kurzzeitig beendet, um dann die Logfile mit einer Liste der aktiven Transaktionen in das Logfile zu schreiben. Da nur Operationen und nicht Transaktionen beendet werden, wird mit diesem Verfahren der Systemdurchsatz kaum beeinflusst.

Bei Stillstand des Systems

Der Checkpoint wird erst gesetzt, wenn das DBMS stillsteht, d.h. alle Transaktionen in einem beendeten Zustand sind. Der Vorteil daran ist, dass das Recovery nie "hinter" einem Checkpoint notwendig werden würde. Nachteil ist aber zeitaufwendig.

Bei Transaktionsende

Nach Abschluss einer jeden Transaktion wird ein Checkpoint geschrieben. Somit ist diese Variante ein Sonderfall der Ersten.

Wie geht das Rücksetzen einer Transaktion vonstatten?

Rücksetzen (Undo)

Ist das Schreiben der before-Images in umgekehrter Reihenfolge. Bei optimistischen Verfahren ist dies nicht nötig, da hier das Schreiben erst nach der Validationsphase erfolgt.

Im Log befindet sich ein Mitschnitt der Aktivitäten der Transaktionen.

Im physischen Log werden die Werte von Datenbankobjekten vor und nach Änderungen durch Transaktionen gespeichert (before-/after Image). Im Log wird eine Marke für BOT sowie EOT gesetzt. Für ein etwaiges Rollback vor EOT wird ein before Image im Log gesichert. Ebenso wird unmittelbar vor EOT noch ein after-Image der Transaktion ins Log geschrieben. Dies dient zum Recovery nach Speicherfehlern und zum Wiederholen von nach dem letzten Checkpoint beendeten Transaktionen z.B. nach Systemzusammenbrüchen.

Im logischen Log werden die durchgeführten Operationen gespeichert.

Welche Transaktion wird bei einem Deadlock zurückgesetzt?

Die billigste Transaktion wird zurückgesetzt. Kosten stellen hierbei die Anzahl der erforderlichen DB-Zugriffe, die CPU-Zeit und die Anzahl der abzubrechenden Transaktionen (Rollbacks) dar. Also sollte diejenige Transaktion mit der geringsten Anzahl an Datenänderungen/-selektionen und mit der geringsten CPU-Intensität zurückgesetzt werden!

Was passiert bei einem Undo?

Bisherige Änderungen durch die Transaktion werden dadurch rückgängig gemacht, daß aus dem Logfile das before-Image in die Datenbank zurückgeschrieben wird. Beim Undo wird das Log-File rückwärts durchlaufen (bei einem Redo dagegen vorwärts). Ggf. wird ein fortgepflanzter Rollback angestoßen, da durch das Rücksetzen einer Transaktion alle von ihr abhängigen Transaktionen auch zurückgesetzt werden müssen.

Erläuterung des Recovery bei einem Systemstart (nach einem Absturz)

Sei TC die Menge der zum Zeitpunkt eines Systemabsturzes aktiven Transaktionen.

Undo/Redo: Durchsuche das Log vom Abbruch bis zum letzten Checkpoint, führe ein Undo aus für die in dieser Zeit nicht abgeschlossenen Transaktionen, für die übrigen Transaktionen aus TC ein Redo

Undo/No-Redo: physikalisches Schreiben vor dem Commit (schlecht bei Hot-Spots), für die seit dem letzten Checkpoint nicht abgeschlossenen Transaktionen wird ein Undo ausgeführt,

No-Undo/Redo: nur abgeschlossene Objekte werden in die Datenbank geschrieben, für die seit dem letzten Checkpoint nicht abgeschlossenen Transaktionen wird ein Redo durchgeführt.

No-Undo/No-Redo: Alle Änderungen werden vor Commit in einer einzigen atomaren Operation die Datenbank geschrieben. Damit dies performant machbar ist, wird Shadowing angewendet. Nachteil: Jeder Zugriff auf das DBS ist indirekt, durch das Anfertigen von Kopien (Shadow) werden die Daten in schwer zu kontrollierender Weise über die Hintergrundspeicher verteilt.

Wie lange muß man before und after-images aufheben?

Before-Images

werden für das Rollback von Transaktionen im Falle von Transaktionsfehlern oder Systemzusammenbrüchen benötigt. Die Speicherung erfolgt von BOT bis EOT.

Before-Images enthalten für jedes veränderte Objekt die ObjektID, den alten Wert des Objektes und die TransaktionsID.

After-Images

werden für das Recovery nach Speicherfehlern und für das Wiederholen von nach dem letzten Checkpoint beendeten Transaktionen im Falle eines System-Zusammenbruches benötigt. Die Speicherung erfolgt unmittelbar vor EOT bis zum nächsten Dump / Checkpoint.

Was wird zuerst geschrieben? Log oder Datenbank?

Natürlich zuerst in die Logfile. Anderfalls könnten nicht mit Sicherheit alle Operationen wieder rückgängig gemacht werden.

Quellen

Gottfried Vossen
Datenbankmanagementsysteme Heuer und Saake
Konzepte und Sprachen Prof. Benn
Skript und Vorlesung Relationale Datenbanken
Andreas Kelz

Downloads

Normalformen
DBMS
Concurrency Ctrl

Powered by HTML5 and twitter-bootstrap
Icons from Font-Awesome

Copyright by Holger Kreissl 2004 - 2019

Impressum

Datenschutzerklärung

Back To Top