Date post: | 06-Apr-2015 |
Category: |
Documents |
Upload: | merten-laucks |
View: | 112 times |
Download: | 5 times |
Datenbanksysteme 1
Datenbanksysteme II
Vorlesung WS 2006 / 2007
Paul Manthey
Datenbanksysteme 2
Abfragesprachen (DML): SQL-Versionen
• Geschichte
• SEQUEL (1974, IBM Research Labs San Jose)
• SEQUEL2 (1976, IBM Research Labs San Jose)
• SQL (1982, IBM)
• ANSI-SQL (SQL-86; 1986)
• ISO-SQL (SQL-89; 1989; drei Sprachen Level 1, Level 2, + IEF)
• (ANSI / ISO) SQL2 (als SQL-92 verabschiedet)
• (ANSI / ISO) SQL3 (als SQL:1999 verabschiedet)
• (ANSI / ISO) SQL:2003
• trotz Standardisierung: teilweise Inkompatibilitäten zwischen Systemen der einzelnen Hersteller
Datenbanksysteme 3
SQL-Kern
select
• Projektionsliste
• arithmetische Operationen und Aggregatfunktionen
from
• zu verwendende Relationen, evtl. Umbenennungen
where
• Selektions-, Verbundbedingungen
• Geschachtelte Anfragen (wieder ein SFW-Block)
group by
• Gruppierung für Aggregatfunktionen
having
• Selektionsbedingungen an Gruppen
Datenbanksysteme 4
Beispieldaten
Datenbanksysteme 5
Auswahl von Tabellen: Die from-Klausel
• einfachste Form
• hinter jedem Relationennamen kann optional eine Tupelvariable stehen
select * from relationenliste
• Beispiel
select * from Produkt
• bei mehr als einer Relation wird das kartesische Produkt gebildet:
select * from Produkt, Hersteller
• alle Kombinationen werden ausgegeben!
Datenbanksysteme 6
Tupelvariablen (Aliase)
• Einführung von Tupelvariablen erlaubt mehrfachen Zugriff auf eine Relation
select * from Produkt eins, Produkt zwei
• Spalten lauten dann:
eins.ProdId, eins.Bezeichnung, eins.Preis, eins.Bestand, eins.Herstid
zwei.ProdId, zwei.Bezeichnung, zwei.Preis, zwei.Bestand, zwei.HerstId
Datenbanksysteme 7
Natürlicher Verbund in SQL 92
• frühe SQL-Versionen
• üblicherweise realisierter Standard in aktuellen Systemen
• kennen nur Kreuzprodukt, keinen expliziten Verbundoperator
• Verbund durch Prädikat hinter where realisieren
• Beispiel für natürlichen Verbund
select * from Produkt, Hersteller
where Produkt.HerstId = Hersteller.HerstId
• neuere SQL-Versionen
• kennen mehrere explizite Verbundoperatoren (engl. join)
• als Abkürzung für die ausführliche Anfrage mit Kreuzprodukt aufzufassen
• Beispiel
select * from Produkt natural join Hersteller
Datenbanksysteme 8
Verbunde als explizite Operatoren: join
• Verbund mit beliebigem Prädikat
select * from Produkt join Hersteller
on Produkt.HerstId = Hersteller.HerstId
• Gleichverbund mit using
select * from Produkt join Hersteller using (HerstId)
• Kreuzprodukt
select * from Produkt, Hersteller
• als cross join
select * from Produkt cross join Hersteller
Datenbanksysteme 9
Die select-Klausel
• Festlegung der Projektionsattribute
select [distinct] { attribut | arithmetischer-ausdruck |
aggregat-funktion }+
from ...
• Attribute der hinter from stehenden Relationen, optional mit einem Präfix, der den Relationennamen oder den Namen der Tupelvariablen angibt
• arithmetische Ausdrücke über Attributen dieser Relationen mit passenden Konstanten
• Aggregatfunktionen über Attributen dieser Relationen
Datenbanksysteme 10
distinct eliminiert Duplikate
select Ort from Kunde
• liefert die Ergebnisrelation als Multimenge
select distinct Ort from Kunde
• ergibt Projektion aus der Relationenalgebra
Datenbanksysteme 11
Tupelvariablen (Aliase) und Relationennamen• Abfrage
select Bezeichnung from Produkt
• ist äquivalent zu
select Produkt.Bezeichnung from Produkt
• Präfixe für Eindeutigkeit
select HerstId, Name, ProdId, Bezeichnung, Preis (falsch!)
from Produkt, Hersteller
where Produkt.HerstId = Hersteller.HerstId
• Attribut HerstId existiert in Tabelle Produkt und auch in Hersteller, richtig mit Präfix
select Hersteller.HerstId, Name, ProdId, Bezeichnung, Preis
from Produkt, Hersteller
where Produkt.HerstId = Hersteller.HerstId
Datenbanksysteme 12
Aliase für Eindeutigkeit
• bei der Verwendung von Tupelvariablen, kann der Name einer Tupelvariablen zur Qualifizierung eines Attributs benutzt werden
select eins.Bezeichnung, zwei.Bezeichnung
from Produkt eins, Produkt zwei
Datenbanksysteme 13
Die where-Klausel
select ...from ... where bedingung
• Formen der Bedingung
• Vergleich eines Attributs mit einer Konstanten
attribut op konstante
mögliche Vergleichssymbole op abhängig vom Wertebereich; etwa =, <>, >, <, >= sowie <=.
• Vergleich zwischen zwei Attributen mit kompatiblen Wertebereichen
attribut1 op attribut2
• logische Konnektoren or, and und not
Datenbanksysteme 14
Verbundbedingung
• Verbundbedingung hat die Form
relation1.attribut = relation2.attribut
• Beispiel
select Produkt.Bezeichnung, Hersteller.Name
from Produkt, Hersteller
where Produkt.HerstId = Hersteller.HerstId
Datenbanksysteme 15
Schachtelung von Abfragen (Unterabfragen)
• für Vergleiche mit dynamischen Wertemengen notwendig
• Standardvergleiche in Verbindung mit den Quantoren all () oder any ()
• spezielle Prädikate für den Zugriff auf Mengen: in und exists
• Notation in Prädikat
attribut in ( SFW-block )
• Beispiel
select Name, Vorname from Kunde
where KNr in ( select KNr from Bestellung)
• not in kann für Bildung von Differenzen verwendet werden, z.B. für die Anfrage „Kunden ohne Bestellungen“
select Name, Vorname from Kunde
where KNr not in (select KNr from Bestellung)
Datenbanksysteme 16
Mengenoperationen
• Mengenoperationen erfordern kompatible Wertebereiche für Paare korrespondierender Attribute
• beide Wertebereiche sind gleich oder
• beide sind auf character basierende Wertebereiche (unabhängig von der Länge der Strings) oder
• beide sind numerische Wertebereiche (unabhängig von dem genauen Typ) wie integer oder float
• Beispiel
select A, B, C from R1
union
select A, C, D from R2
Datenbanksysteme 17
Vereinigung zweier Relationen mit union
Datenbanksysteme 18
Differenz
• ältere SQL-Versionen kennen keinen Differenzoperator
RelKNr (Kunde) − RelKNr (Bestellung)
• dargestellt durch
select KNr from Kunde
where KNr not in ( select KNr from Bestellung )
• Hinweis: Verbund-Abfragen zur Differenzbildung sind i.a. schneller
Datenbanksysteme 19
Mengenoperationen im neuen SQL
• Vereinigung, Durchschnitt und Differenz als union, intersect und except
• orthogonal einsetzbar
select count(*) from ( (select Name, Vorname, Ort,
PLZ, Strasse from Kunde)
union
(select Name, Vorname, Ort, PLZ, Strasse from Adresse) )
Datenbanksysteme 20
Mächtigkeit des SQL-Kerns
Datenbanksysteme 21
Weiteres zu SQL
• Erweiterungen des SFW-Blocks
• innerhalb der from-Klausel weitere Verbundoperationen (äußerer Verbund),
• innerhalb der where-Klausel weitere Arten von Bedingungen, insbesondere Bedingungen mit „Wildcards“ und Bedingungen mit Quantoren,
• innerhalb der select-Klausel die Anwendung von skalaren Operationen und Aggregatfunktionen,
• zusätzliche Klauseln group by und having
Datenbanksysteme 22
Äußere Verbunde
• zusätzlich zu klassischen Verbund (inner join) in SQL-92 auch äußerer Verbund Übernahme von „dangling tuples“ in das Ergebnis und Auffüllen mit Nullwerten
• outer join übernimmt alle Tupel beider Operanden (Langfassung: full outer join)
• left outer join bzw. right outer join übernimmt alle Tupel des linken bzw. des rechten Operanden
• äußerer natürlicher Verbund jeweils mit Schlüsselwort natural, also z.B. natural left outer join
Datenbanksysteme 23
Bereichsselektion
• Bereichsselektion
attrib between konstante1 and konstante2
• ist Abkürzung für
attrib konstante1 and attrib konstante2
• schränkt damit Attributwerte auf das abgeschlossene Intervall [konstante1, konstante2] ein
• Beispiel
select Bezeichnung from Produkt
where Preis between 50 and 100
Datenbanksysteme 24
Ungewissheitsselektion
• Notation
attribut like spezialkonstante
• Mustererkennung in Strings (Suche nach mehreren Teilzeichenketten)
• Spezialkonstante kann die Sondersymbole ‘%’ und ‘_’ beinhalten
• ‘%’ steht für kein oder beliebig viele Zeichen (in MS Access ‘*’ )
• ‘_’ steht für genau ein Zeichen (in MS Access ‘?’ )
• Beispiel
select * from Produkt where Bezeichnung like ’Rainbow%opper’
ist Abkürzung für
select * from Produkt where Bezeichnung = ’Rainbow Hopper’
or Bezeichnung = ’Rainbow-Hopper’ or
or Bezeichnung = ’Rainbowhopper’
or Bezeichnung = ’Rainbow-Whopper’ or ...
Datenbanksysteme 25
Selektion nach Nullwerten
• Null-Selektion wählt Tupel aus, die bei einem bestimmten Attribut Nullwerte enthalten
• Notation
attribut is null
• Beispiel
select * from Produkt
where Bezeichnung is null
Datenbanksysteme 26
Bedingungen mit Quantoren
• Quantoren: all, any, some und exists
• Notation
attribut op { all | any | some } (
select attribut
from ...where ...)
• Beispiele
select ProdId, Bezeichnung from Produkt
where ProdId = any ( select ProdId from Bestellposten )
• any und some haben identische Bedeutung!
select ProdId, Bezeichnung from Produkt
where Preis >= all ( select Preis from Produkt )
Datenbanksysteme 27
Das exists-Prädikat
• Namen der derzeit bestellten Produkte
select Bezeichnung from Produkt
where exists ( select * from Bestellposten
where Bestellposten.ProdId = Produkt.ProdId )
• „Verzahnt“ geschachtelte (korrelierte) Anfrage
in der inneren Anfrage wird Relationen- oder Tupelvariablen-Name aus dem from-Teil der äußeren Anfrage verwendet
Datenbanksysteme 28
Das not exists-Prädikat
• Simulation des Allquantors mit doppelter Negation
select * from Bestellung b
where not exists
( select * from Produkt p
where not exists ( select * from Bestellposten bp
where bp.ProdId = p.ProdId and b.BestNr = bp.BestNr ))
• Übersetzung
• „Gib alle Bestellungen aus, so dass kein Produkt existiert, das nicht in dieser Bestellung vorkommt“. ( also die Bestellungen die alle Produkte umfassen . . . )
Datenbanksysteme 29
Skalare Ausdrücke
• skalare Operationen auf
• numerischen Wertebereichen: etwa +, −, * und /,
• Strings: Operationen wie char_length (aktuelle Länge eines Strings), die Konkatenation || und die Operation substring (Suchen einer Teilzeichenkette an bestimmten Positionen des Strings),
• Datumstypen und Zeitintervallen: Operationen wie current_date (aktuelles Datum), current_time (aktuelle Zeit), +, − und *
• Umwandlung des DM-Preises in den aktuellen Euro-Preis
select ProdId, Bezeichnung, Preis / 1.95583 as EuroPreis
from Produkt
• erzeugt folgende Ergebnistabelle
Datenbanksysteme 30
Aggregatfunktionen und Gruppierung
• Aggregatfunktionen berechnen neue Werte für eine gesamte Spalte, etwa die Summe oder den Durchschnitt der Werte einer Spalte
• Beispiel
Ermittlung des Durchschnittspreises aller Artikel oder des Gesamtumsatzes über alle verkauften Produkte
• bei zusätzlicher Anwendung von Gruppierung
Berechnung der Funktionen pro Gruppe, z.B. der Durchschnittspreis pro Warengruppe oder der Gesamtumsatz pro Kunde
Datenbanksysteme 31
Aggregatfunktionen (1)
• Aggregatfunktionen in Standard-SQL
• count: berechnet Anzahl der Werte einer Spalte oder alternativ (im Spezialfall count(*)) die Anzahl der Tupel einer Relation
• sum: berechnet die Summe der Werte einer Spalte (nur bei numerischen Wertebereichen)
• avg: berechnet den arithmetischen Mittelwert der Werte einer Spalte (nur bei numerischen Wertebereichen)
• max bzw. min: berechnen den größten bzw. kleinsten Wert einer Spalte
• Argumente einer Aggregatfunktion
• ein Attribut der durch die from-Klausel spezifizierten Relation,
• ein gültiger skalarer Ausdruck oder
• im Falle der count-Funktion auch das Symbol *
Datenbanksysteme 32
Aggregatfunktionen (2)
• vor dem Argument (außer im Fall von count(*)) optional auch die Schlüsselwörter distinct oder all
• distinct: vor Anwendung der Aggregatfunktion werden doppelte Werte aus der Menge von Werten, auf die die Funktion angewendet wird
• all: Duplikate gehen mit in die Berechnung ein (Default-Voreinstellung )
• Nullwerte werden in jedem Fall vor Anwendung der Funktion aus der Wertemenge eliminiert (außer im Fall von count(*))
Datenbanksysteme 33
Aggregatfunktionen: Beispiele
• Gesamtbestand aller Produkte
select sum(Bestand) from Produkt
ergibt
• Anzahl der Bestellungen
select count() from Bestellung
• Anzahl der Kunden, für die derzeit eine Bestellung vorliegt
select count(distinct KNr) from Bestellung
• Durchschnittspreis aller Produkte
select avg(all Preis) from Produkt
Verwendung von all, da bei distinct doppelte Preise eliminiert werden würden, was den Durchschnittspreis verfälscht
Datenbanksysteme 34
Aggregatfunktion in where-Klausel
• Aggregatfunktionen liefern nur einen Wert Einsatz in Konstanten-Selektionen der where-Klausel möglich
• Beispiel
Produkte, deren Bestand unter dem Durchschnitt liegt
select ProdId, Bezeichnung from Produkt
where Bestand < ( select avg(all Bestand) from Produkt)
Datenbanksysteme 35
group by und having
• Notation
select ... from ... [where ...]
[group by attributliste ]
[having bedingung ]
• Schema mit Relation REL:
• Anfrage:
select A, sum(D) from REL where ...
group by A, B
having A<4 and sum(D)<10 and max(C)=4
Datenbanksysteme 36
Gruppierung: Schema (1)
• Schritt 1: from und where
• Schritt 2: group by A, B
Datenbanksysteme 37
Gruppierung: Schema (2)
• Schritt 3: select A, sum(D)
• Schritt 4: having A < 4 and sum(D) < 10 and max(C) = 4
Datenbanksysteme 38
Gruppierung: Beispiele (1)
• Anfrage: „pro Bestellung die Anzahl der zugehörigen Posten“
select BestNr, count(*) as Posten
from Bestellposten group by BestNr
• Ergebnisrelation
Datenbanksysteme 39
having: Beispiel
• Anfrage: „Bestellungen mit mehr als einer Position“
select BestNr, count(*) from Bestellposten
group by BestNr
having count(*) > 1
• Ergebnisrelation
Datenbanksysteme 40
Gruppierung: Beispiele (2)
• Anfrage: „Gesamtwert jeder einzelnen Bestellung“
select b.BestNr, sum (bp.Anzahl * p.Preis)
from Bestellung b, Bestellposten bp, Produkt p
where b.BestNr = bp.BestNr and bp.ProdId = p.ProdId
group by b.BestNr
• Gruppierung ohne Ausgabe einer Aggregation: „Bestellungen, deren Bestellwert 100 Euro überschreitet“
select b.BestNr
from Bestellung b, Bestellposten bp, Produkt p
where b.BestNr = bp.BestNr and bp.ProdId = bp.ProdId
group by b.BestNr
having sum (bp.Anzahl * p.Preis) > 100
Datenbanksysteme 41
Sortierung mit order by
• Notation
order by attributliste
• Beispiel
select Bezeichnung, Preis
from Produkt
order by Preis asc
• Sortierung aufsteigend (asc) oder absteigend (desc)
Datenbanksysteme 42
Behandlung von Nullwerten
• skalare Ausdrücke: Ergebnis null, sobald Nullwert in die Berechnung eingeht
• in allen Aggregatfunktionen bis auf count(*) werden Nullwerte vor Anwendung der Funktion entfernt
• fast alle Vergleiche mit Nullwert ergeben Wahrheitswert unknown (statt true oder false)
• Ausnahme: is null ergibt true, is not null ergibt false
• Boolesche Ausdrücke basieren dann auf dreiwertiger Logik
Datenbanksysteme 43
Wahrheitstafeln für Nullwerte
Datenbanksysteme 44
Benannte Abfragen
• Abfrageausdruck, der in der Abfrage mehrfach referenziert werden kann
• Notation
with abfrage-name [(spalten-liste) ] as ( abfrage-ausdruck )
• Abfrage ohne with
select * from Produkt where Preis >= 0.8 *
(select avg(Preis) from Produkt)
and Preis <= 1.2 * (select avg(Preis) from Produkt);
• Abfrage mit with
with Durchschnitt(Wert) as ( select avg(Preis) from Produkt )
select * from Mitarbeiter, Durchschnitt
where Preis > 0.8 * Wert and Preis <= 1.2 * Wert;
Datenbanksysteme 45
Beschreibungssprachen (DDL)
• Aufgaben von SQL
• Übertragung eines konzeptionellen Datenbankschemas in ein Data Dictionary gemäß Relationenmodell
• Spezifikation des Datenbankschemas nach
• Attributen
• Datentypen
• Integritätsbedingungen
• Einschränkungen (constraints)
• Wertebereiche (domains bzw. checks)
Datenbanksysteme 46
Datentypen in SQL-92
• Zeichenkettentypen
• feste Länge, z.B. char, text, ...
• variable Länge, z.B. nvarchar,varchar2, ...
• Numerische Typen
• Festpunktzahlen, z.B. numerical, decimal, integer, ...
• Gleitpunktzahlen, z.B. real, float, double, ...
• Datums- / Zeittypen
• Datumsangaben, z.B. date, datetime, ...
• Zeitangaben, z.B. time, timestamp, ...
• Bitketten
• feste Länge, z.B. bit, ...
• vaiable Länge, z.B. bit varying, blob, ...
Datenbanksysteme 47
Definition von Basistabellen
• Eine Basistabelle umfasst
• den Namen der Tabelle
• ein oder mehrere Attribute mit den zugehörigen Datentypen und ggf. spaltenbezogenen Einschränkungen
• ggf. tabellenbezogene Einschränkungen
• BNF-Spezifikation
Datenbanksysteme 48
Integritätsbedingungen in SQL
• not null: Nullwerte verboten
• default: Angabe von Default-Werten
• check ( search-condition ): Attributspezifische Bedingung (in der Regel Ein-Tupel-Integritätsbedingung)
• primary key: Angabe eines Primärschlüssel (Schlüsselintegrität)
• foreign key ( Attribut(e)) references Tabelle( Attribut(e): Angabe eines Fremdschlüssel (referentielle Integrität)
Datenbanksysteme 49
Integritätsbedingungen: Wertebereiche
create domain: benutzerdefinierter Wertebereich
• Beispiel
create domain Einsatzart varchar(20) default ’Leicht’
• Anwendung
create table Drachen (
ProdId int primary key,
Material varchar(20),
Einsatz Einsatzart,
...
);
Datenbanksysteme 50
Integritätsbedingungen: check-Klausel
check: Festlegung weitere lokale Integritätsbedingungen innerhalb der zu definierenden Wertebereiche, Attribute und Relationenschemata
• Beispiel: Einschränkung der zulässigen Werte
• Anwendung
create table Drachen (
ProdId int primary key,
Material varchar(20),
Leinen int check(Leinen between 2 and 8),
Einsatz Einsatzart,
...
);
Datenbanksysteme 51
Integritätsbedingungen: Referentielle Integrität
• Überprüfungsmodi von Bedingungen
• on update | delete
Angabe eines Auslöseereignisses, das die Überprüfung der Bedingung anstößt
• cascade | set null | set default | no action
Kaskadierung: Behandlung einiger Integritätsverletzungen pflanzt sich über mehrere Stufen fort, z.B. Löschen als Reaktion auf Verletzung der referentieller Integrität
• deferred | immediate
legt Überprüfungszeitpunkt für eine Bedingung fest
• deferred
Zurückstellen an das Ende der Transaktion
• immediate
sofortige Prüfung bei jeder relevanten Datenbankänderung
Datenbanksysteme 52
Integritätsbedingungen: Beispiel
• Kaskadierendes Löschen
create table Produkt (
ProdId int primary key,
Bezeichnung varchar(50) not null,
Preis float not null,
Bestand int not null,
HerstId int,
foreign key (HerstId)
references Hersteller (HerstId)
on delete cascade)
Datenbanksysteme 53
Rechtevergabe
• In Datenbanken
• Zugriffsrechte: (AutorisierungsID, DB-Ausschnitt, Operation)
• AutorisierungsID: interne Kennung eines „DB-Benutzers“
• Datenbank-Ausschnitt: Relationen und Sichten
• DB-Operation(en): Lesen, Einfügen, Ändern, Löschen
• In SQL
grant <Rechte> on <Tabelle> to <BenutzerListe> [with grant option]
• Erläuterungen
• In <Rechte>-Liste: all bzw. Langform all privileges oder Liste aus select, insert, update, delete
• Hinter on: Relationen- oder Sichtname
• Hinter to: Autorisierungsidentifikatoren (auch public, group)
• spezielles Recht: Recht auf die Weitergabe von Rechten (with grant option)
Datenbanksysteme 54
Zurücknahme von Rechten
revoke <Rechte> on <Tabelle> from <BenutzerListe> [restrict | cascade ]
• restrict: Falls Recht bereits an Dritte weitergegeben: Abbruch von revoke
• cascade: Rücknahme des Rechts mittels revoke an alle Benutzer propagiert, die es von diesem Benutzer mit grant erhalten haben
Datenbanksysteme 55
Transaktionskonzept
Definition
Eine Transaktion TA ist eine Folge von Operationen (Aktionen), die die Datenbank von einem konsistenten Zustand in einen konsistenten, eventuell veränderten, Zustand überführt, wobei das ACID-Prinzip eingehalten werden muss.
• Aspekte
• Semantische Integrität: Korrekter (konsistenter) DB-Zustand nach Ende der Transaktion
• Ablaufintegrität: Fehler durch „gleichzeitigen“ Zugriff mehrerer Benutzer auf dieselben Daten vermeiden
• Kommandos einer Transaktionssprache
• Begin-of-Transaction-Kommando BOT: Beginn einer Transaktion (in SQL implizit!)
• commit: die Transaktion soll erfolgreich beendet werden
• abort: die Transaktion soll abgebrochen werden
Datenbanksysteme 56
Eigenschaften von Transaktionen
Eine TA erfüllt die folgenden ACID-Bedingungen:
• A(tomicity): Eine TA ist die kleinste, atomare Ausführungseinheit.
• Entweder alle durch eine TA vorgenommenen Änderungen werden wirksam oder gar keine.
• C(onsistency): Eine TA überführt einen konsistenten DB-Zustand in einen anderen konsistenten DB-Zustand.
• Innerhalb einer TA sind Inkonsistenzen erlaubt.
• I(solation): Eine TA ist gegenüber anderen TAs isoliert, d.h. das Ergebnis einer TA kann nicht direkt durch eine andere TA beeinfluss werden.
• Jede TA wird logisch so ausgeführt, als gäbe es keine andere TA.
• D(urability): Ist eine TA einmal erfolgreich abgeschlossen, dann bleibt ihre Wirkung auf die Datenbasis dauerhaft erhalten (auch im Fall eines Systemfehlers)
Datenbanksysteme 57
Transaktion: Integritätsverletzung
• Beispiel
• Übertragung eines Betrages B von einem Haushaltsposten K1 auf einen anderen Posten K2
• Bedingung: Summe der Kontostände der Haushaltsposten bleibt konstant
• vereinfachte Notation
Transfer = < K1:=K1-B; K2:=K2+B >;
• Realisierung in SQL: als Sequenz zweier elementarer Änderungen; Bedingung ist zwischen den einzelnen Änderungsschritten nicht unbedingt erfüllt!
Datenbanksysteme 58
Transaktion: Verhalten bei Systemabsturz
• Folgen
• Inhalt des flüchtigen Speichers zum Zeitpunkt tf ist unbrauch-bar! Transaktionen in unterschiedlicher Weise davon betroffen
• Transaktionszustände
• zum Fehlerzeitpunkt noch aktive Transaktionen (T2 und T4)
• bereits vor dem Fehlerzeitpunkt beendete Transaktionen (T1, T3 und T5)
Datenbanksysteme 59
Vereinfachtes Modell für Transaktion
• Repräsentation von Datenbankänderungen einer Transaktion
• read(A, x): weise den Wert des DB-Objektes A der Variablen x zu
• write(x, A): speichere den Wert der Variablen x im DB-Objekt A
• Beispiel einer Transaktion T
read(A, x); x := x − 200; write(x, A);
read(B, y); y := y + 100; write(y, B);
• Ausführungsvarianten für zwei Transaktionen T1, T2:
• seriell, etwa T1 vor T2
• „gemischt“, etwa abwechselnd Schritte von T1 und T2
Datenbanksysteme 60
Probleme im Mehrbenutzerbetrieb
• Inkonsistentes Lesen: Nonrepeatable Read
• Abhängigkeiten von nicht freigegebenen Daten: Dirty Read
• Das Phantom-Problem
• Verlorengegangenes Ändern: Lost Update
• Beispiel Nonrepeatable Read
• Zusicherung x = A + B + C am Ende der Transaktion T1
• x, y, z seien lokale Variablen
• Ti ist die Transaktion i
• Integritätsbedingung A + B + C = 0
Datenbanksysteme 61
Nonrepeatable Read
Datenbanksysteme 62
Dirty Read
Datenbanksysteme 63
Das Phantom-Problem
Datenbanksysteme 64
Lost Update
Datenbanksysteme 65
Serialisierbarkeit
Definition
Eine verschränkte Ausführung mehrerer Transaktionen heißt serialisierbar, wenn ihr Effekt identisch zum Effekt einer (beliebig gewählten) seriellen Ausführung dieser Transaktionen ist.
Definition
Ein Schedule ist ein „Ablaufplan“ für eine Transaktion, bestehend aus einer Abfolge von elementaren Transaktionsoperationen.
Datenbanksysteme 66
Konflikte
Datenbanksysteme 67
Konfliktserialisierbarkeit
Definition
Zwei Schedules s und s‘ heissen konfliktäquivalent, wenn die Reihenfolge von zwei in Konflikt stehenden Operationen in beiden Schedules gleich ist.
• andernfalls: unterschiedliche Effekte, z.B.
w1(x)w2(x) vs. w2(x)w1(x)
Definition
Ein Schedule s ist genau dann konfliktserialisierbar, wenn s konfliktäquivalent zu einem seriellen Schedule ist.
Datenbanksysteme 68
Graphbasierter Test
• Konfliktgraph G(s) = (V, E) von Schedule s:
1. Knotenmenge V enthält alle in s vorkommende Transaktionen
2. Kantenmenge E enthält alle gerichteten Kanten zwischen zwei in Konflikt stehenden Transaktionen
• Eigenschaften
1. ist s ein serieller Schedule, dann ist der vorliegende Konfliktgraph ein azyklischer Graph
2. für jeden azyklischen Graphen G(s) lässt sich ein serieller Schedule s‘ konstruieren, so dass s konfliktserialisierbar zu s‘ ist (Test z.B. durch topologisches Sortieren)
3. enthält ein Graph Zyklen, dann ist der zugehörige Schedule nicht konfliktserialisierbar
Datenbanksysteme 69
Zeitlicher Verlauf dreier Transaktionen
Datenbanksysteme 70
Konfliktgraph
Datenbanksysteme 71
Sperren
• Sperrprotokoll
• Sichern der Serialisierbarkeit durch exklusiven Zugriff auf Objekte (Synchronisation der Zugriffe)
• Implementierung über Sperren und Sperrprotokolle
• Sperrprotokoll garantiert Konfliktserialisierbarkeit ohne zusätzliche Tests!
• Sperrmodelle
• Schreib- und Lesesperren in folgender Notation:
• rl(x): Lesesperre (engl. read lock) auf einem Objekt x
• wl(x): Schreibsperre (engl. write lock) auf einem Objekt x
• Entsperren ru(x) und wu(x), oft zusammengefasst u(x) für engl. unlock
Datenbanksysteme 72
Sperrdisziplin
• Schreibzugriff w(x) nur nach Setzen einer Schreibsperre wl(x) möglich
• Lesezugriffe r(x) nur nach rl(x) oder wl(x) erlaubt
• nur Objekte sperren, die nicht bereits von einer anderen Transaktion gesperrt
• nach rl(x) nur noch wl(x) erlaubt, danach auf x keine Sperre mehr; Sperren derselben Art werden maximal einmal gesetzt
• nach u(x) durch ti darf ti kein erneutes rl(x) oder wl(x) ausführen
• vor einem commit müssen alle Sperren aufgehoben werden
Datenbanksysteme 73
Verklemmungen
• Alternativen
• Verklemmungen werden erkannt und beseitigt (Wartegraph)
• Verklemmungen werden von vornherein vermieden (z.B. durch konservatives 2PL = 2 Phasen Sperrprotokoll)
Datenbanksysteme 74
Fehlerklassifikation im DB-Betrieb (1)
• Transaktionsfehler
• haben den Abbruch der jeweiligen Transaktion zur Folge
• haben keinen Einfluss auf den Rest des Systems
• typische Transaktionsfehler: Fehler im Anwendungsprogramm, Transaktionsabbruch explizit durch den Benutzer
• Behandlung: „Isoliertes“ Zurücksetzen aller Änderungen der abgebrochenen Transaktionen
• Systemfehler
• Folge: Zuerstörung der Daten im Hauptspeicher betreffen jedoch nicht den Hintergrundspeicher
• typische Systemfehler: DBMS-Fehler, Betriebssystemfehler, Hardware-Fehler
Datenbanksysteme 75
Fehlerklassifikation im DB-Betrieb (2)
• Behandlung:
1. Zurücksetzen der von nicht beendeten Transaktionen in die DB eingebrachten Änderungen
2. Nachvollziehen der von abgeschlossenen Transaktionen nicht in die DB eingebrachten Änderungen
• Mediafehler
• ziehen den Verlust von stabilen Datenbankbankdaten nach sich
• häufige Ursachen: „Head-Crashes“, Naturgewalten wie Feuer oder Erdbeben
• Maßnahmen: DB-Archiv auf anderen „Medien“
Datenbanksysteme 76
Recovery-Logbuch
• Protokollierung aller durchgeführten Änderungen
• dokumentiert Status aller Transaktionen
• wird direkt auf stabilen Speicher geschrieben
Datenbanksysteme 77
Recovery: Wiederherstellen nach Fehler
1. Log wird rückwärts durchlaufen
2. Alle (T, commit)-Einträge werden notiert; diese Transaktionen werden als erfolgreich („Winner“) markiert
3. Für jede erfolgreiche Transaktion T werden alle (T,A, a)-Einträge gesucht und a in die Datenbank geschrieben
4. Transaktionen ohne (T, commit) oder mit (T, abort) werden als „Loser“ ignoriert Warnung an den Benutzer: „T not committed!“ oder ein automatisches restart
Datenbanksysteme 78
Physische Datenorganisation
Datenorganisation sollte so optimiert werden, dass folgende Wünsche erfüllt werden:
• schnelles Finden von Daten innerhalb einer Datei (geringer Zeitaufwand!)
• wenig Speicherverbrauch beim Abspeichern aller Daten (geringe Kosten)
• wenig Aufwand beim Löschen, Einfügen, Ändern (geringer Zeitaufwand)
• einfacher Algorithmus (wenig Wartung und geringe Fehleranfälligkeit)
Datenbanksysteme 79
Physische Datenorganisation
Datenorganisation sollte so optimiert werden, dass folgende Wünsche erfüllt werden:
• schnelles Finden von Daten innerhalb einer Datei (geringer Zeitaufwand!)
• wenig Speicherverbrauch beim Abspeichern aller Daten (geringe Kosten)
• wenig Aufwand beim Löschen, Einfügen, Ändern (geringer Zeitaufwand)
• einfacher Algorithmus (wenig Wartung und geringe Fehleranfälligkeit)
Datenbanksysteme 80
Dateibegriff
Sequentielle Dateien (Sequentieller Speicher)
• Die einzelnen Datensätze sind innerhalb der Datei nacheinander (sequentiell) ohne Lücken abgespeichert. Anwendung: Archivierung, Sicherung, kleine Dateien ( < 10 MBytes)
Adressierte Dateien (Adressierbarer Speicher)
• Die einzelnen Datensätze sind innerhalb der Datei an bestimmten Adressen abgespeichert. Auf diese Datensätze kann direkt über die Adresse zugegriffen werden, vorausgesetzt diese Adresse wurde gespeichert. Eine aufwendige Suche innerhalb der Datei entfällt. Anwendung: große Dateien (im MByte- bis GByte-Bereich), wo kurze Antwortzeiten beim Zugriff auf bestimmte Daten gefordert werden.
Datenbanksysteme 81
Speicherung auf adressierbarem Speicher (1)
Direktadressierung
• Bei der Direktadressierung ist die Speicheradresse eine Funktion der dort gespeicherten Daten.
• Beispiel: elektronisches Notizbuch. Stehen in unserem Notizbuch pro Tag 100 Bytes Speicher zur Verfügung, so entspricht dies dem bewährten Terminkalender, wo pro Tag ein fester Bereich für Notizen existiert. Werden nun Einträge zum 2. Februar gesucht, so lassen sich diese Daten an Hand folgender Rechnung sofort finden:
• Der 2. Februar ist der 33. Tag des Jahres.
Definition
Enthält ein Suchbegriff auch die Information zum direkten Auffinden der Daten an der Adresse A, so nennen wir ihn den Suchschlüssel der Datei. Mathematisch ist die gesuchte Adresse A eine Funktion f des Suchschlüssels:
Datenbanksysteme 82
Speicherung auf adressierbarem Speicher (2)
Geordnete Speicherung mit Suchschlüssel
• Gespeicherten Daten sind sortiert.
• Algorithmus: Binäre Suche.
Datenbanksysteme 83
Einstufige physische Datenstrukturen (1)
Listen auf sequentiellem Speicher
Listen sind die einfachste Methode der Datenspeicherung und eignen sich besonders gut für sequentielle Speicher, aber auch allgemein bei kleineren Datenbeständen. Merkmale dieser Listen auf sequentiellem Speicher sind:
• der Anfang der Liste ist bekannt,
• zu jedem Element existiert ein direktes Nachfolgeelement,
• am Ende steht ein Ende-Signal.
Dies lässt sich wie folgt darstellen:
Datenbanksysteme 84
Einstufige physische Datenstrukturen (2)
Tabellen auf adressierbarem Speicher
Bei Tabellen auf adressierbarem Speicher liegt die Direktadressierung zugrunde. Die Merkmale sind:
• Jedes Element ist direkt zugreifbar,
• Jedes Element belegt gleich viel Speicherplatz.
• Es muss auch für im Augenblick nicht belegte Elemente einer Tabelle Speicherplatz reserviert werden. Hier gibt es auch keine Anfangs- oder Ende-Informationen. Dies ist auch nicht notwendig, denn die Tabelle ist statisch fest vorgegeben. Eine Tabelle mit 80 Elementen besitzt daher folgendes Aussehen:
Datenbanksysteme 85
Einstufige physische Datenstrukturen (3)
Geordnete Listen auf adressierbarem Speicher
• der Anfang ist bekannt,
• zu jedem Listenelement existiert ein direktes Nachfolgeelement,
• die Elemente sind nach dem Suchbegriff geordnet,
• das Binäre Suchverfahren ist anwendbar,
• am Ende steht ein Ende-Signal.
Datenbanksysteme 86
Einstufige physische Datenstrukturen (4)
Geordnete verkettete Listen
• der Anfang der Liste ist bekannt,
• zu jedem Element existiert ein Verweis auf das nächste Element,
• das Ende ist markiert.
• Adressierbarer Speicher ist Voraussetzung
Datenbanksysteme 87
Einstufige physische Datenstrukturen (5)
Zusammenfassung
Datenbanksysteme 88
Mehrstufige physische Datenstrukturen (1)
• Hierarchischer Aufbau
• Mehrstufiger Zugriff über die Hierarchie
• In Zwischenstufen werden keine Nutzdaten, sondern Verwaltungsdaten (Adressen) gespeichert.
• Im Normalfall Speicherung in unterschiedlich schnellen / großen Speichermedien
• Beispiel: 15 beliebige Einträge in einem Binären Baum
Datenbanksysteme 89
Mehrstufige physische Datenstrukturen (2)
• Je mehr Baumdaten im Hauptspeicher, desto effektiver
• Datenblockstrukturen sollten deiner Defragmentierung entgegenwirken
Datenbanksysteme 90
Mehrstufige physische Datenstrukturen (3)
Index sequential access method
• Funktionsweise eines Index
• Verwendete Indexstrukturen
• Sequentielle Dateien
• B+-Bäume
• Hashtabellen
• Annahmen
• Relation als Datei organisiert
• Blockweiser Daten-Zugriff
Datenbanksysteme 91
Mehrstufige physische Datenstrukturen (4)
Definition
Sind die Datensätze nach dem Suchschlüssel des Index sortiert, so wird der Index als Primärindex bezeichnet.
Eigenschaften
• Index auf Datendatei
• Datensätze der Datendatei nach Suchschlüssel sortiert
• Suchschlüssel des Primärindex nicht notwendigerweise Primärschlüssel der Relation
• Indexdatei enthält Suchschlüsselwert-Zeiger-Paare
• Dichter Index hat ≥ 1 Eintrag pro Suchschlüsselwert
• Dünner Index besitzt weniger Einträge
• O(log2 n) Festplattenzugriffe
Datenbanksysteme 92
Mehrstufige physische Datenstrukturen (5): Primärindex
Datenbanksysteme 93
Mehrstufige physische Datenstrukturen (6)
Eigenschaften
• Index auf Datendatei
• Datensätze der Datendatei nicht nach Suchschlüssel sortiert
• Suchschlüssel des Sekundärindex häufig Nichtschlüsselattribut(e) der Relation
• Dichter Index, 1 Eintrag pro Datensatz
• Aufbau und Zugriff wie bei Primärindex
Datenbanksysteme 94
Mehrstufige physische Datenstrukturen (7): Sekundärindex
Datenbanksysteme 95
Mehrstufige physische Datenstrukturen (8)
Mehrstufige Indizierung
• Indizierung eines Index
• 1. Stufe kann Primär- oder Sekundärindex auf Datendatei sein
• n. Stufe ist dünner Primärindex auf (n–1). Stufe, wobei n ≥ 2
• Manipulation und Reorganisation separat pro Indexstufe
Datenbanksysteme 96
Mehrstufige physische Datenstrukturen (9)
Fazit
Datenbanksysteme 97
Mehrstufige physische Datenstrukturen (10): Hashing
• Organisation der Datensätze in Hashtabelle
• Einteilung der Hashtabelle in fixe Anzahl an Buckets
• Buckets zunächst gleich groß
• 1. Block eines Buckets per Nummer auffindbar
• Zugriff per Hashfunktion h
• Datensatz mit Suchschlüssel K fällt in Bucket h(K)
• Soll mögliche Suchschlüsselwerte gleich verteilen
• Soll Datensätze zufällig verteilen
Gleichmäßiges Anwachsen aller Buckets
Suchzeit für alle Suchschlüssel annähernd gleich
• Bei geeigneter Bucket-Anzahl O(1) Festplattenzugriffe
Datenbanksysteme 98
Mehrstufige physische Datenstrukturen (11): Hashing
Dateiorganisationsform inklusive Index
Datenbanksysteme 99
Mehrstufige physische Datenstrukturen (12)
Fazit