Datenbank 笔记

1. Datenbankentwurf / ER-Modellierung

Entity-relationship diagram

Funktionalitäten:

1:1, 1:N, N:1, N:M

Min-Max: (min,max)

Multiplizität

2. Das Relationale Modell

Schlüssel, Primärschlüssel

Relationen mit gleichem Schlüssel kann man zusammenfassen.

Anomalie: 异常

Die Relationale Algebra

• Selektion
• Projektion (会自动去重)
• Kreuzprodukt
• Join (Verbund)
• Umbenennung
• Mengendifferenz
• Division
• Vereinigung
• Mengendurchschnitt
• Semi-Join (linkes Argument wird gefiltert) (筛选左表，仅保留在右表中有匹配记录的左表行。)
• Semi-Join (rechtes Argument wird gefiltert)
• Anti-Semi-join
• ⟕ linker äußerer Join (会保留左表中的所有记录，即使在右表中没有匹配的记录时，右表对应的位置会以 NULL 填充。)
• ⟖ rechter äußerer Join
• ⟗ (voller) äußerer Join

Der Relationenkalkül (relationaler Tupelkalkül)

Bsp.:

Der Domänenkalkül

Bsp.:

Diese 3 Sprachen sind gleich mächtig

3. SQL

standadisierte

-Datendefinitions (DDL)-

-Datenmanipulations (DML)-

-Anfrage (Query)-Sprache

Datendefinition (DDL)

Datentypen:

• character(n), char(n)

• character varying(n), varchar(n)

• numeric(p,s), integer, decimal

  p（precision，精度）：数值的总位数（包含小数点前后的所有数字）。

  s（scale，小数位数）：小数部分的位数（小数点后的位数）。

• blob oder raw – für sehr große binäre Daten

• clob – für sehr große String-Attribute

• date – für Datumsangaben

• xml – für XML-Dokumente

1
2
3
4

create table Professoren (
    PersNr integer not null,
    Name varchar(30) not null,
    Rang character(2));

Datenmanipulation

Einfügen von Tupeln

1
2
3
4

insert into hören
select MatrNr, VorlNr
from Studenten, Vorlesungen
where Titel = 'Logik';

1
2

insert into Studenten (MatrNr, Name)
values (28121, 'Archimedes');

Löschen von Tupeln

1
2

delete Studenten
where Semester > 13;

Verändern von Tupeln

1
2

update Studenten
set Semester = Semester + 1;

Anfrage

1
2
3

select (distinct)  as
from
where    and 

Sortieren:

1
2
3

select PersNr, Name, Rang
from Professoren
order by Rang desc, Name asc;

Mengenoperation:

1

union, intersect, minus

1
2
3
4
5

select
from
where (not) exists (select from where)

where not in ()

比较：

1

(where) value >= ALL(子查询)

Aggregationsfunktion:

1

avg, max, min, count, sum

Gruppierung:

1
2
3
4

select
from
(where)
group by 

Alle in der select-Klausel aufgeführten Attribute - außer den aggregierten - auch in der group by-Klausel aufgeführt werden.

比如说下面这里的gelesenVon, Name：

1
2
3
4
5

select gelesenVon, Name, sum(SWS)
from Vorlesungen, Professoren
where gelesenVon = PersNr and Rang = 'C4'
group by gelesenVon, Name
		having avg(SWS) >=3;

Casting:

1
2

cast(expression AS target_data_type)
cast(h.AnzProVorl as decimal(6,2))

Allquantor und Implikation:

Auswertung bei NULL-Werten

and, between, in (1,2,3,4)

like mit Platzhalter:

“%” (für beliebig biele Zeichen)

“_” (für genau ein Zeichen)

case

left/right/full outer join

Rekursion

Vorgänger des „Wiener Kreises“ der Tiefe n:

1
2
3
4
5
6
7
8
9
10
11

select v1.Vorgänger
from voraussetzen v1,
     ...
     voraussetzen vn_minus_1,
     voraussetzen vn,
     Vorlesungen v
where v1.Nachfolger = v2.Vorgänger and
      ...
      vn_minus_1.Nachfolger = vn.Vorgänger and
      vn.Nachfolger = v.VorlNr and
      v.Titel = 'Der Wiener Kreis';

Mit Rekursion:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

with recursive TransVorl (Vorg, Nachf) as (
    -- 递归的基础查询（初始层级）
    select Vorgänger, Nachfolger from voraussetzen
    union all
    -- 递归部分（从前一层继续查找更深的层级）
    select t.Vorg, v.Nachfolger
    from TransVorl t, voraussetzen v
    where t.Nachf = v.Vorgänger
)

select Titel 
from Vorlesungen 
where VorlNr in (
    select Vorg 
    from TransVorl 
    where Nachf in (
        select VorlNr 
        from Vorlesungen 
        where Titel = 'Der Wiener Kreis'
    )
);

4. Datenintegrität

Integritätsbedingungen:

-Schlüssel

-Beziehungskardinalitäten

-Attributdomänen

-Inklusion bei Generalisierung

Referentielle Integrität

Fremdschlüssel

Änderung von referenzierten Daten:

1. Default 会拒绝执行主键的更改操作
2. cascade (Kaskadieren): 级联，外键会随着主键的更改一起更改
3. set NULL

Statische Integritätsbedingungen:

1
2

create table Studenten
(Semester integer check Semester between 1 and 13)

1
2

create table Prof
(Rang character(2) check(Rang in ('C2','C3','C4')))

Konsistenzbedingung:

1
2
3
4
5
6
7

create table prüfen
(MatrNr ···
VorNr ···
Note ···
primary key (MatrNr,VorNr))
constraint VorherHören
	check (···)

Trigger:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

-- 1. 
create trigger keine Degradierung
-- 2.
before update on Professoren
for each row
-- 3.
when (old.Rang is not null)
begin
-- 4.
    if :old.Rang = 'C3' and :new.Rang = 'C2' then
        :new.Rang := 'C3';
    end if;
    
    if :old.Rang = 'C4' then
        :new.Rang := 'C4';
    end if;
    
    if :new.Rang is null then
        :new.Rang := :old.Rang;
    end if;
end;

1. create trigger Anweisung, gefolgt von einem Namen,
2. der Definition des Auslösers, in diesem Fall bevor eine Änderungsoperation (before update on) auf einer Zeile (for each row) der Tabelle Professoren ausgeführt werden kann,
3. einer einschränkenden Bedingung (when) und
4. einer Prozedurdefinition in der Oracle-proprietären Syntax.

Temporale Daten

5. Relationale Entwurfstheorie

Funktionale Abhängigkeiten

Functional Dependency (FD)

R:= {A,B,C,D}

假设

:

(可以理解成函数的 rechtseindeutig)

Super-Schlüssel :

( 生成元)

voll funktional abhängig von () :

• kann nicht mehr verkleinert werden

  ()

Kandidaten-Schlüssel:

( 最小生成元)

Armstrong-Axiome

FD-Hülle einer Attributmenge

Kanonische Überdeckung

没有冗余的属性(Attribute)和依赖(Abhängigkeit)

Berechnung:

1. 消除右部冗余属性 (, 时仅保留 和 )
2. 消除左部冗余属性
3. 删除冗余的函数依赖 (，， 时仅保留 和 )

R = R1 R2

2 Korrektheitskriterien für die Zerlegung von Relationenschemata:

1. Verlustlosigkeit
2. Abhängigkeitserhaltung

verlustlose Zerlegung:

( R = R1 R2 )

Hinreichende Bedingung für die Verlustlosigkeit einer Zerlegung:
oder

Normalformen

Erste Normalform (1NF):

Nur atomare Domäne.

都要是singleton，不能出现集合或者重复行

反例：

正例：

Zweite Normalform (2NF)：

falls jedes Nicht(kandidat)schlüssel-Attribut voll funktional abhängig ist von jedem Kandidatenschlüssel der Relation.

假设R:= {A,B,C,D}的Kandidaten-Schlüssel是{A,B},那么需要满足C,D sind voll funktional abhängig von {A,B}。

只要出现类似{A} {C}之类的就不行了。

可以理解成不能有多余列。

Remark: 如果Kandidaten-Schlüssel只有一个元素，那么一定满足2NF。

反例（1非2）：

{A,B}为Kandidaten-Schlüssel。有{A} {C}。

Dritte Normalform (3NF)：

wenn für jede für geltende funktionale Abhängigkeit der Form mit und mindestens eine von drei Bedingungen gilt:

• , d.h., die FD ist trivial
• Das Attribut ist in einem Kandidatenschlüssel von enthalten – also ist prim
• ist Superschlüssel von

假如{A,B}是Kandidatenschlüssel，那么可以{C,D} {A}是符合第二条要求的。（但是这个不满足后面的BCNF）

反例（2非3）：

满足{A,B} {C}， {A,B} {D} voll，所以满足2NF；

有{C} {D}，所以不满足3NF。

Synthesealgorighmus:

zerlegen R in R1,…,Rn, sodass:

1. R1,…,Rn verlustlos
2. R1,…,Rn abhägigkeitserhaltend
3. Alle R1,…,Rn in 3NF

Boyce-Codd-Normalform (BCNF)：

wenn für jede für geltende funktionale Abhängigkeit der Form (FDs) und mindestens eine von drei Bedingungen gilt:

• , d.h., die FD ist trivial
• ist Superschlüssel von

反例（3非BCNF）：

有

AB CD

C B

因为B属于Kandidatschlüssel，所以满足3NF，但是不满足BCNF。

Man kann jede Relation verlustlos in BCNF-Relationen zerlegen, aber nicht unbedingt abhägigkeitserhaltend.

Dekompositions-Algorithmus

Mehrwertige Abhägigkeit (Multivalued Dependency, MVD):

2行对上，2行交叉对应

Jede FD is auch eine MVD:

Eine MVD ist trivial iff:

• oder

Vierte Normalform (4NF):

falls für jede MVD eine der folgenden gilt:

• Die MVD ist trivial oder
• ist Superschlüssel von R

6. Physische Datenorganisation

Speicherhierarchie

Register

Cache

Hauptspeicher

Plattenspeicher

Archivspeicher

RAID

Redundant Arrays of Independent Disks

MTTF, MTTR, MTTDL

RAID 0: Striping

RAID 1: Spiegelung

RAID 0+1(10): Striping und Spiegelung

RAID 2: Striping auf Bit-Ebene

RAID 3: Striping auf Bit-Ebene mit Paritätsinfo

RAID 4: Striping von Blöcken

RAID 5: Striping von Blöcken, Verteilung der Paritätsblöcke

Indexstrukturen

B-Bäume

B+-Bäume

Erweiterbares Hashing

Dynamisches Wachsen möglich

Beispiel: gespiegelte binäre PersNr

• h(004) = 00100000… (4=0…0100)
• h(006) = 01100000… (6=0…0110)
• h(048) = 00001100… (48=0…0110000)

Globale Tiefe

Lokale Tiefe

R-Baum

mehrdimensionalen Zugriffsstrukturen

7. Anfragebearbeitung

Logische Optimierung

Kanonische Übersetzung:

SQL Relationale Algebra

Äquivalenzerhaltende Transformationsregeln

一共12条

Dependent Join

Physische Optimierung

Nested Loop Join

foreach :

​ foreach :

​ if s.a=r.a then Res:= Res (r s)

O(N*M)

Block-Nested Loop Algorithmus

foreach Block

​ foreach

​ foreach

​ if s.b = r.a then Res:= Res (r s)

O(N * M/B)

(M/B: Anzahl der Blöcke)

Index-Join

Voraussetzung: 其中一个表是sortiert的且有B-Baum

O(N * log(M))

Merge-Join

Voraus.: 2个表都是sortiert的

O(N+M) linear

Hash-Join

选定一个哈希函数h()，计算R.A的值，分配到hash buckets里，然后再计算S.B的值，在哈希桶里匹配。

不需要预先排序

Partitionieren und Hashing的话需要2个哈希函数。

O(N+M) linear

Join mit Hashfilter (Bloom-Filter)

需要很多个（k个）不同的哈希函数
forall : 计算h_i(a) forall

0覆盖1。

会出现False Positive，但是不会出现False Negative

Externes Sortieren

Selektivität

Dynamische Programmierung:

1. Phase: Zugriffspläne ermitteln
2. Phase: Join-Pläne ermittel (2-fach, …, n-fach)
3. Phase: Finalisierung

8. Transaktionsverwaltung

Begin of Transaction (BOT)：转账开始的标志

read：读存款

write：写入（修改存款，出账入账）

commit：转账结束，所有操作festschreiben

abort：取消转账，所有状态复原

define savepoint

backup transaction: Auf den jüngsten Sicherungspunkt zurücksetzen.

commit work

rollback work: Alle Änderungen sollen zurückgesetzt werden.

ACID:

• Atomicity (Atomarität)：原子性。

  Alles oder Nichts.

• Consistency：一致性。

• Isolation：隔离性。

• Durability (Dauerhaftigkeit)：持久性。

  所有更改都必须永久存储。Änderungen erfolgreicher Transaktionen dürfen nie verloren gehen.

9. Fehlerbehandlung (Recovery)

Fehlerklassifikation

1. Lokaler Fhler in einer noch nicht festgeschriebenen Transaktion

   • Wirkung zurücksetzten
     R1-Recovery

2. Fehler mit Hauptspeicherverlust

   • Abgeschlossene TAs erhalten bleiben

     R2-Recovery redo

   • Noch nicht abgeschlossene TAs zurücksetzten

     R3-Recovery undo

3. Fehler mit Hintergrundspeicherverlust

   • R4-Recovery

steal：未提交的事务修改的页面不会被替换。

steal：允许替换缓存中的任何非固定页面。

force：事务提交时立即将数据写入磁盘。

force：修改的数据仍可保留在缓存中，提高性能。

Auswirkung auf Recovery:

Einbringungsstrategie（数据提交策略）:

1. Update in Place：直接覆盖
2. Twin-Block-Verfahren：复制整个数据块
3. Schattenspeicherkonzept：复制修改的页面

Log-Einträge:

• LSN (Log Sequence Number)：日志序列号
• Transaktionskennung(TA_ID)
• PageID
• Redo：纪录当前操作（比如说+=50）
• Undo：当前操作的逆向（比如-=50）
• PrevLSN：上一个日志记录的指针

[LSN, TransaktionsID, PageID, Redo, Undo, PrevLSN]

（中括号）

Protokollierung:

• Physische Protokollierung
  • before-image：修改前的Zustand
  • after-image
• Logische Protokollierung
  • Undo-Code
  • Redo-Code

Log-Information会记录2次以上：

1. Log-Datei

   R1,R2,R3

2. Log-Archiv

   R4

WAL-Prinzip (Write Ahead Log)：

1. Commit前，确保所有相关的日志记录已写入日志文件。

2. modifizierte Seite auslagern前，确保相关日志记录已写入日志存档（Log-Archiv）。

Winner：在崩溃前已经完成，需要Redo

Loser：在崩溃时仍然处于未提交状态，需要Undo

Wiederanlauf:

1. Analyse

   • Log-Datei analysieren
   • Winner-Menge ermitteln
   • Loser-Menge ermitteln

2. Redo

3. Undo

CLR: Compensating Log Record

用于记录撤销的操作。（给undo的）

简单来说就是为了预防恢复崩溃时发生的其他崩溃。

CLR-Einträge:

• LSN (Log Sequence Number)：日志序列号
• Transaktionskennung(TA_ID)
• PageID
• Redo：
• PrevLSN：上一个日志记录的指针
• UndoNxtLSN：Verweis auf die nächste rückgängig zu machende Änderung