Table of Contents

Datenbanksysteme I

Allgemein

Probleme

Aufbau

Anwendungen (mehrere)
Externe Ebene Views (mehrere)
↓↓ Logische Datenunabhängigkeit ↓↓
Konzeptionelle Ebene
↓↓ Physische Datenunabhängigkeit ↓↓
Interne Ebene Speicherformat

Anforderungen

Sprachen

Datenmodelleigenschaften

Datenmodelle

Verbindung zur Datenbank

Optimierung

|
Anfrage (deklarativ)
↓
Scanner/Parser/View-Erzeuger
|
algebraischer Ausdruck
↓
Anfrageoptimierung
|
Auswertungsplan (prozedural)
↓
Ausführung

Kanonischer Auswertungsplan

Query in Funktionsbaum übersetzten

Beispiel 

SELECT A1, A2
FROM R1, R2, R3
WHERE B1, B2

Ergibt $\pi_{A_1, A_2}(\sigma_{B_1}(\sigma_{B_2}(R_1 \times (R_2 \times R_3))))$

Optimierung: Filter so früh wie möglich

Wo kann optimiert werden

Wie kann optimiert werden

Transaktionen

Datensicherheit

Technische Fehler

Wann Was Undo Redo
Transaktionsfehler Rücksetzen Lokales Undo
nicht abgeschlossene Transaktion rückgängig
Systemfehler Warmstart Globales Undo
nicht abgeschlossene Transaktionen rückgängig 		Globales Redo
Alle abgeschlossenen Transaktionen nachholen
Medienfehler Kaltstart
Backup einspielen 		Globales Redo
Alle abgeschlossenen Transaktionen nachholen

Integrität

Synchronisation

Anomalien

Lost update
t1 r(x) w(x)
t2 w(x)
Dirty read/write
t1 w(x) w(x)
t2 r(x)
Non-repeatable read
t1 r(x) r(x)
t2 w(x)
Phantom-Problem

Non-repeatable read mit Aggregiertem read

Serialisierung

allgemeiner Schedule Durcheinander <latex>\[\frac{(m_1 + m_2 + \dots){\color{red}!}}{m_1{\color{red}!} \cdot m_2{\color{red}!} \cdot \dots}\]</latex>
serialisierbarer (allgemeiner) Schedule Durcheinander kann in Blockform gebracht werden
serieller Schedule Blockform <latex>\[n{\color{red}!}\]</latex>

Graph Zeichen

Übergang Markierung
$w_i(x) \rightarrow r_j(x)$ wr(x)
$r_i(x) \rightarrow w_j(x)$ rw(x)
$w_i(x) \rightarrow w_j(x)$ ww(x)

Kein rr(x)

Zyklenfrei? ⇒ Serialisierbar durch topologisches sorieren

Technicken

Anwendung

"MVC" Aufteilungen

Thin client Fat client Stored procedure Web Application Application Server
Client GUI GUI
Logik 		GUI
Hauptprogramm 		Browser GUI
Application
Server 		Logik
DB-Server
Logik
DB-Schnittstelle
DB

DB-Schnittstelle
DB
Prozeduren
DB-Schnittstelle
DB 		Webserver
Logik
DB-Schnittstelle
DB

DB-Schnittstelle
DB

Interaktion

Cursor

  1. Declaration
    SQL eingeben
  2. Open
    Ausführen
  3. Fetch loop
  4. Close

Vorübersetzes SQL mit Platzhaltern

Mathe

Funktionale Abhängigkeiten

Arten

Axiome

Reflexivität ${\color{ForestGreen}Y} \subseteq {\color{red}X}$ $\Longrightarrow$ ${\color{red}X} \rightarrow {\color{ForestGreen}Y}$
Verstärkung ${\color{red}X} \rightarrow {\color{ForestGreen}Y}$ $\Longrightarrow$ ${\color{red}X}{\color{RoyalBlue}Z} \rightarrow {\color{ForestGreen}Y}{\color{RoyalBlue}Z}$
Transistivität ${\color{red}X} \rightarrow {\color{ForestGreen}Y} \wedge {\color{ForestGreen}Y} \rightarrow {\color{RoyalBlue}Z}$ $\Longrightarrow$ ${\color{red}X} \rightarrow {\color{RoyalBlue}Z}$
Vereinigung ${\color{red}X} \rightarrow {\color{ForestGreen}Y} \wedge {\color{red}X} \rightarrow {\color{RoyalBlue}Z}$ $\Longrightarrow$ ${\color{red}X} \rightarrow {\color{ForestGreen}Y}{\color{RoyalBlue}Z}$
Dekomposition ${\color{red}X} \rightarrow {\color{ForestGreen}Y}{\color{RoyalBlue}Z}$ $\Longrightarrow$ ${\color{red}X} \rightarrow {\color{ForestGreen}Y} \wedge {\color{red}X} \rightarrow {\color{RoyalBlue}Z}$
Pseudotransitivität ${\color{red}X} \rightarrow {\color{ForestGreen}Y} \wedge {\color{RoyalBlue}Z}{\color{ForestGreen}Y} \rightarrow V$ $\Longrightarrow$ ${\color{red}X}{\color{RoyalBlue}Z} \rightarrow V$

Attributhülle

AttrHülle(F,X) mit
F = FDs
X = Start Attributmenge

Starte mit X und wende so lange F ab, bis nichts mehr geht. (“Schau wie weit du kommst”)

Normalisierung

Anomalien

1. NF

Bedingung

Alle Attribute atomar

Attributwerte dürfen nicht …

2. NF

Bedingung

Jedes Attribut entweder
voll funktional Abhängig von jedem Schlüsselkandidaten
– oder –
prim (teil eines Schlüsselkandidaten)

Trivial: nur ein einelementiger Schlüsselkandidat ⇒ 2. NF

Sonst: Vom Schlüssel nicht voll funktional Abhängige Attribute werden herausgelöst, in eigene Tabelle

3. NF

Bedingung

Jede FD $X \rightarrow Y$ ist mindestens eins:

  • tivial
  • X enthält Schlüsselkandidat
  • $\forall a \in (Y-X)$ ist prim

Keine (nicht trivialen) FDs unter Nicht-Schlüssel-Attributen

  1. Kanonische Überdeckung
    1. Linksreduktion
      Komme ich von X-x und identischem FD dennoch auf Y, dann streiche x aus X
    2. Rechtsreduktion
      Komme ich von X und FD ohne y dennoch auf y in Y, dann streiche y aus Y
    3. $X \rightarrow \emptyset$ entfernen
    4. Gleiche X zusammenfassen
  2. Relationsschema erzeugen und FDs zuweisen
    1. Aus jedem FD erzeuge eine Relation mit X als Primärschlüssel und Y als Attribute
    2. Ordne jedes FD den Relationen zu, die alle seine “Buchstaben” enthält
  3. Schlüsselkandidat rekonstruieren
    Stelle sicher, dass eine Relation einen ehemaligen Schlüsselkandidaten enthält, notfalls erzeuge eine neue mit leerem ohne zugeordnete FDs
  4. Überflüssige Relationen eliminieren
    Lösche Relationen, die Teilmenge einer anderen sind.

Boyce-Codee-Normalform

Bedingung

Jede FD $X \rightarrow Y$ ist mindestens eins:

  • tivial
  • X enthält Schlüsselkandidat

Keine (nicht trivialen) FDs unter Schlüssel-Attributen

4. NF

Wirkung

Nicht mehrere Tabellen in einer.

Bedingung

Jede MVD $X \twoheadrightarrow Y$ ist mindestens eins:

  • tivial
  • X enthält Schlüsselkandidat

MVD (Multi Valued Dependency): Mehre Attributwerte, eines Attributs, sind von der linken Seite abhängig.

Begriffe

Schlüssel

Eigenschaften

  1. Eindeutig
    $t_1 \ne t_2 \Rightarrow \pi_S(t_1) \ne \pi_S(t_1)$
    Unterschiedliche Tupel ⇒ Unterschiedliche Schlüssel
  2. Minimal
    $\text{Eindeutig}(T) \wedge T \subseteq S \Rightarrow T = S$
    Keine Teilmenge des Schlüssels erfüllt die 1. Eigenschaft

(Minimal bedeutet nicht: Die wenigsten Attribute)

Schlüssel und FD sind semantische Eigenschaften (nicht anhand von aktueller Ausprägung erkennbar)

Arten

Primes Attribut: Teil eines Schlüsselkandidaten

Beweis

Beispiel: Beweise das S = (A, B) Schlüsselkandidat ist.

  1. Eindeutigkeit
    $S \rightarrow R$ herleiten
  2. Minimalität
    Zeigen das weder $A \rightarrow R$ noch $B \rightarrow R$ gild

Relationsschemata

geordnet

Schema R = (id:Integer, Name:String)
Ausprägung r = {(1, Alice), (2, Bob), (42, Eve)}

ungeordnet (mit Domänenabbildung)

Schema R = {id, Name} mit
dom(id) = Integer, dom(Name) = String
Ausprägung r = {t1, t2, t3} mit
t1(id) = 1, t1(Name) = Alice,
t2(id) = 2, t2(Name) = Bob,
t3(id) = 42, t3(Name) = Eve

Relationale Algebra

Formel Name Iden-
tisch 		Duplikat-
elimi-
nation 		SQL Kommentar
$A \cup B$ Vereinigung X X UNION
UNION ALL 		Duplikatelimination in SQL nur bei UNION
$A - B$ Differenz X EXCEPT
MINUS
$A \times B$ Kreuzprodukt
Kartesisches Produkt
$\sigma_F(A)$ Selektion WHERE
$\pi_{a, b, \dots}(A)$ Projektion X SELECT
$A \cap B$ Durchschnitt X INTERSECT
$A \div B$ Quotient Allquantor. Die Tupel aus A, die alle Attribute aus jedem B Tupel gleich haben, ohne die B Attribute.
$A \bowtie B$ Natural Join NATURAL JOIN t Inner-Join (Tupel ohne Partner gehen verloren)
Vergleich aller gleichbenannten
$A \underset{a = b}{\bowtie} B$ Equi Join X JOIN t USING(id) Inner-Join (Tupel ohne Partner gehen verloren)
$A \underset{a \Theta b}{\bowtie} B$ Theta Join JOIN t ON f Inner-Join (Tupel ohne Partner gehen verloren)
Θ = Vergleichsoperator

Identisch

Relationale Algebra und SQL

Relationen-Kalkül

t ∈ Schema ⇔ Schema(t) t[A] ⇔ t.A

Ψ(r | t): Ersetze t in Ψ(r | t) mit dem konkreten Tupel r

Quantoren sind nur im Relationenkalkül möglich.

Variable ist …

Es ist möglich unendlich (nicht speicherbare) Relationen zu beschreiben.
Eine Relation ist sicher wenn alle Vaiablen x einer (gespeicherten) Relation angehören Schema(x).

Tupelkalkül Bereichskalkül
Alle Großstädte in Bayern
Schema(t) = Schema(Städte)
{t | Städte(t) ∧ f[Land] = Bayern ∧ t[SEinw] ≥ 500000}
In welchem Land liegt Passau
Schema(t) = (Land:String)
{t | (∃ u ∈ Städte)(u.Sname = Passau ∧ u.Land = t.Land} 		$\{ x_3 \mid \exists x_1, x_2 : (\text{Städte}(x_1, x_2, x_3) \wedge x_1 = \text{Passau}) \}$
$\{ x_3 \mid \exists x_2 : (\text{Städte}(\text{Passau}, x_2, x_3)) \}$
CDU-regierte Städte
Schema(t) = Schema(Städte)
{t | Städte(t) ∧ (∃ u ∈ Länder)(u.Lname = t.Land ∧ u.Partei = CDU) } 		$\{x_1 \mid \exists x_2, x_3, y_2 : (\text{Städte}(x_1, x_2, x_3) \wedge \text{Länder}(x_3, y_2, \text{CDU}))\}$
SPD alleinregierte Länder
Schema(t) = SChema(Länder)
{t | Länder(t) ∧ (∀ u ∈ Länder)(u.LName = t.LName ⇒ u.Partei = SPD} 		$\{x_1 \mid \exists x_2 : (\text{Länder}(x_1, x_2, \text{SPD}) \wedge \neg \exists y_3 : \text{Länder}(x_1, x_2, y_3) \wedge y_3 \ne \text{SPD} \}$
Schema(t) = SChema(Länder)
{t | Länder(t) ∧ (∀ u ∈ Länder)(u.LName = t.LName ⇒ u.Partei = SPD}

Speicher Stukturen

Jeder zusätzlich Schlüssel wirkt sich negativ auf updates aus.

Seitenarten (für Daten- und Raumorganisierende Strukturen)

Schlüsselarten

B+ Baum

Erweiterbares Hashing (Directory)

Lineares Hashing (Ohne directory)

$\text{Belegungsfaktor} = \frac{\text{Alle Schlüssel}}{\text{Kapazität in \textit{Primär}seite}} > 0.8 \Rightarrow \text{Expansion}$

Invertierte Listen

Reverse pattern matching

Composite Indizes

mehrere Attribute

E/R-Modell

Elemente:

Umsetzen:

SQL

Typen

integer integer4 int
smallint integer2
float(p) float Bits der mantisse (nicht Exponent)
decimal(p, q) numeric(p, q) Exakte Komma Zahlen. p Stellen gesamt, davon q Nachkommastellen.
character(n) char(n)
character varying(n) varchar(n)
date
time
timestamp

http://www.postgresql.org/docs/9.2/static/datatype-numeric.html

Constrains

Integritätsbedingungen

Schlüssel

Fremdschlüssel Zusätze

Folgende sachen können am Ende einer REFERENCES Angabe stehen

Bla

a + b a - b a * b a / b
a = b a <> b
a < b a > b a <= b a >= b
x BETWEEN a AND b
a IS NULL a IS NOT NULL
a IN (…)
a AND b a OR b a NOT b
s1 || s2 CHAR_LENGTH(s) SUBSTRING(s FROM pos [FOR len]) a LIKE '...' 
CREATE TABLE name (
  name typ constraints,
  name typ constraints,
  integritätsbedingungen
)
DROP TABLE name
ALTER TABLE name ADD (
  name typ constraints,
  name typ constraints
)
ALTER TABLE name DROP (
  name,
  name
)
ALTER TABLE name MODIFY (
  name typ constraints,
  name typ constraints
)
SELECT [DISTINCT]
  *,
  t.*,
  t.a,
  42,
  32 AS Foo    -- Hier AS
FROM
  t,
  Unisinn u,   -- KEIN AS
  (SELECT ...)
WHERE
INSERT INTO name [(a1, a2)]
VALUES
  (v11, v21),
  (v12, v22)
INSERT INTO name (a1, a2)
(SELECT ...)
UPDATE name
SET
  a1=v1, 
  a2=v2
[WHERE ...]
DELETE FROM name
[WHERE ...]
GRANT
  ALL
  ALL PRIVILEGES
  SELECT
  INSERT
  DELETE
  UPDATE
  UPDATE(a, b)
ON
  t
TO
  TU PUBLIC,
  userName
[WIDTH GRANT OPTION]
REVOKE
  ALL
  ALL PRIVILEGES
  SELECT
  INSERT
  DELETE
  UPDATE
  UPDATE(a, b)
ON
  t
FROM
  TU PUBLIC,
  userName
[RESTRICT | CASCADE]  -- RESTRICT: Nur den user löschen
                      -- CASCADE: nehme die rechte auch denjenigen, die sie vom user bekommen haben
CREATE INDEX name ON t (a1, a2, ...);
DROP INDEX name;
-- Laut script kein START TRANSACTION
SET TRANSACTION READ-ONLY  -- kein INSERT, UPDATE und DELETE. Dafür bessere Transaktionsplanung
SET TRANSACTION READ-WRITE -- default
SAVEPOINT name
COMMIT
ROLLBACK
ROLLBACK TO name

Join

NATURAL JOIN t Natural Join $A \bowtie B$ Vergleich aller gleichbenannten
JOIN t USING(id) Equi Join $A \underset{a = b}{\bowtie} B$
JOIN t ON f Theta Join $A \underset{a \Theta b}{\bowtie} B$ Θ = Vergleichsoperator
Join Art Verlustfreie
Seite 		NULL
L R L R
[INNER] JOIN
LEFT [OUTER] JOIN ✓ ✓
RIGHT [OUTER] JOIN ✓ ✓
FULL [OUTER] JOIN ✓ ✓ ✓ ✓

Quantoren

WHERE EXISTS (SELECT ...)             -- Ergebnis Form egal
WHERE NOT EXISTS (SELECT ...)         -- Ergebnis Form egal
WHERE ... a Θ ALL (SELECT ...)        -- Ergebnis genau ein Attribut, aber mehre Tupel
WHERE ... a Θ SOME/MANY (SELECT ...)  -- Ergebnis genau ein Attribut, aber mehre Tupel
WHERE ... a IN (SELECT ...)           -- Ergebnis genau ein Attribut, aber mehre Tupel

Grouping

GROUP BY x
HAVING SUM(y) > 42

keine Aggregartfunktionen in WHERE

In SELECT nur erlaubt

In SELECT nicht erlaubt

Befehl Zähle
NULL doppelte
COUNT(DISTINCT a)
COUNT([ALL] a) ✓
COUNT(*) ✓ ✓

Order

ORDER BY a [ASC/DESC], b [ASC/DESC], ...

Mengenoperatoren

Typ jedes Attributs muss kompatibel sein

[Im Gegensatz zur relationalen Algebra, wo Typ und Name jedes Attributs übereinstimmen muss (Schemata identisch)]

$A \cup B$ Vereinigung UNION [CORRESPONDING] mit Duplikatseliminierung
Vereinigung UNION ALL [CORRESPONDING] ohne Duplikatseliminierung
$A - B$ Differenz EXCEPT [CORRESPONDING]
MINUS [CORRESPONDING]
$A \cap B$ Durchschnitt INTERSECT [CORRESPONDING] 
SELECT ...
UNION/UNION ALL/EXCEPT/MINUS/INTERSECT [CORRESPONDING]
SELECT ...

View

Nutzen

Normaler View

CREATE [OR REPLACE] VIEW v AS SELECT ...
DROP VIEW v

Nicht erlaubt in Basisrelation:

Materialisierter View

INSERT INTO mv (SELECT ...)

Effekt-Konformität

Kein merkbarer unterschied zwischen View und Relation
Teil im
View 		Angewendete
Operation 		Problembeschreibung
SELECT INSERT Default (NULL) für wegprojezierte Attribute
INSERT
UPDATE
DELETE 		Nicht möglich, wenn DISTINCT oder arithmetische Ausdrücke
WHERE INSERT
UPDATE 		Tupel-Migration: Tupel verschwindet, da nicht von WHERE erfasst
Abhilfe: WHERE … WITH CHECK OPTION
JOIN
GROUP BY 		INSERT
UPDATE
DELETE 		Nicht möglich
Subquerry INSERT
UPDATE
DELETE 		Nicht möglich, wenn Selbstbezug

Beispiele

Finde Paare mit gleicher Eigenschaft <code sql> SELECT DISTINCT t1.name, t2.name FROM Foo t1, Foo t2 WHERE 

t1.attrib = t2.attrib
AND
t1.name < t2.name  -- Macht aus  (AA, AB, BA, BB) : (AB)