'

&

$

%1E

infü

hrun

g,A

rchi

tekt

ur

Aus

gang

spun

ktIS

wer

den

anvi

elen

Stel

len

eing

eset

zt

Pro

blem

Was

gena

uis

tei

nIS

?U

nter

wel

chen

Asp

ekte

nw

erde

nIS

hier

beha

ndel

t?

Lösu

ngD

efini

tion

von

IS;

Blic

kwin

kela

ufIS

,in

sbes

.In

form

atik

-Sic

htw

eise

• Beispiele für Anwendungen

• Grundformen

• Definition Informationssysteme

– große Datenmengen

– Verfügbarkeit

– Verläßlichkeit

– Mehrbenutzerbetrieb

– Datenverwaltung

∗ Speicherung∗ Anfragen∗ Änderungen

• Blickwinkel auf IS

– Modell einer Miniwelt

– eigenständige Miniwelt

– Vermitteln von Mitteilungen

• Sichtweisen der informatik:

– Paradigmen: Theorie, Abstraktion, Design

– formale Sprachen: erfinden, verwirklichen, be-nutzen

• Programmieren - stufenweises Vorgehen

• Gliederung der Vorlesung

• Literatur

'

&

$

%2M

odel

lieru

ng

Aus

gang

spun

ktD

aten

inIS

habe

nre

gelm

äßig

eSt

rukt

urun

dw

erde

nin

best

imm

-te

rA

rtun

dW

eise

vera

rbei

tet

Pro

blem

Wie

kann

man

Stru

ktur

und

Ver

halt

enan

wen

dung

snah

besc

hrei

ben?

Lösu

ngE

R-M

odel

l,R

egel

grap

hen,

Pet

ri-N

etze

• Semantische Begriffe für die Modellierung

• Ansatz für ein Begriffsgerüst

– Seiendes

– Eigenschaft/Attribut

– Rolle

– Klassenbildung (Abstraktion)

– Aussonderung (Spezialisierung)

– Verallgemeinerung (Generalisierung)

– Aggregation

• statische Gesichtspunkte

– Bedingungen

– Regeln

• dynamische Gesichtspunkte

– Information

– Mitteilung

– Verstehen

• Verpflichtungen

• Begriffsgerüst für die Modellierung

• zeitabhängige / zeitunabhängige Teile

• Schema und Instanz

• ER-Diagramme

• Regelgraphen

• Beispiel

'

&

$

%3Lo

gik,

Men

genl

ehre

Aus

gang

spun

ktG

rund

kenn

tnis

sein

Logi

kun

dM

enge

nleh

re

Pro

blem

Wel

che

Gru

ndla

gen

wer

den

für

das

Ver

stän

dnis

des

Folg

ende

nbe

nöti

gt?

Gib

tes

eine

nB

ezug

zude

nse

man

tisc

hen

Beg

riff

enau

sde

rM

odel

lieru

ng?

Lösu

ngG

rund

begr

iffe

aus

Logi

kun

dM

enge

nleh

re;

Geg

enüb

erst

ellu

ngzu

sem

an-

tisc

hen

Beg

riff

en

• Prädikatenlogik

– Syntax

– Semantik

• Mengenlehre

• semantische Begriffe

• Gegenüberstellung: Begriffe / Logik + Mengenlehre

– semantische Begriffe

– Syntax

– Semantik

• Gegenüberstellung: Begriffe / proz. Programmier-sprachen

'

&

$

%4Lo

goda

t,S

chem

as

Aus

gang

spun

ktE

R-M

odel

lzur

sem

anti

sche

nM

odel

lieru

ng

Pro

blem

ER

-Mod

ellk

ann

man

nich

tpr

ozes

sier

en;

eini

geA

spek

tede

rA

nwen

dung

(z.B

.R

egel

n)kö

nnen

schl

echt

dari

nfo

rmul

iert

wer

den

Lösu

nglo

gikb

asie

rtes

Mod

ell:

LOG

OD

AT

;Sy

ntax

und

Sem

anti

k

• Datenmodell

• logikorientiertes Datenmodell: LOGODAT

• semantischer Begriff vs. Darstellung in LOGODAT

• Schreibweisen

• LOGODAT-Struktur

• Logik und LOGODAT

• LOGODAT-Schema

• Beispiel:

– ER-Diagramm

– LOGODAT-Schema

– Hypergraph der EDB-Komponente

• Semantik eines LOGODAT-Schemas

– Ausprägung

– Basisrelation

– Vervollständigung

– Sichtrelation

– Instanz

• Beispiel

• Formalisierung von Modellierungen:

– Seieendenklassen

– Beziehungenklasse

– Hierarchie

– Regel

'

&

$

%5Lo

goda

t,O

per

atio

nen

Aus

gang

spun

ktLO

GO

DA

T-S

chem

as;

bish

erke

ine

Anf

rage

n/Ä

nder

unge

n!

Pro

blem

Wie

lass

ensi

chA

nfra

gen

und

Änd

erun

gen

inLO

GO

DA

Tfo

rmul

iere

n?

Lösu

ngSy

ntax

und

Sem

anti

kvo

nLO

GO

DA

T-O

pera

tion

en

• LOGODAT-Operationen:

– Anfrage

– Änderung

• Deklarative Semantik von LOGODAT-Operationen:

– Anfragen

– Änderungen

• Operationale Fixpunktsemantik

'

&

$

%6Lo

goda

t,F

ixpu

nkts

eman

tik

Aus

gang

spun

ktLO

GO

DA

Tbi

etet

mäc

htig

eA

nfra

geop

erat

ione

n,in

sbes

onde

redu

rch

Rek

ursi

on

Pro

blem

Wie

kann

man

reku

rsiv

eA

nfra

gen

korr

ekt

proz

essi

eren

?

Lösu

ngFi

xpun

ktsa

tz;

Äqu

ival

enz

von

dekl

arat

iver

und

oper

atio

nale

rSe

man

tik

• Grundfakten-Transformation

– Definition

– Monotonie und Stetigkeit: Satz, Bewweis

• Fixpunktsatz von Tarski-Kleene

• kleinster Fixpunkt

• Fixpunktsemantik von LOGODAT-Anfragen

• grundlegende Eigenschaften von Grundfakten-Transformationen

• Hilfssatz

• Äquivalenz von deklarativer Semantik und operatio-naler Fixpunktsemantik

• Korrektheit und Vollständigkeit der Fixpunktseman-tik

– Satz

– Beweis

'

&

$

%7R

elat

iona

leS

chem

as

Aus

gang

spun

ktLO

GO

DA

Tal

slo

gisc

hes

Dat

enm

odel

l

Pro

blem

LOG

OD

AT

ist

ein

kaum

impl

emen

tier

tes

Dat

enm

odel

l,ab

eräh

nlic

hzu

mre

lati

onal

enM

odel

l

Lösu

ngB

esch

reib

ung

des

rela

tion

alen

Dat

enm

odel

ls

• Relationales Datenmodell

– Notation

– Relationenschema und Instanz

– Relationales Datenbankschema und Instanz

– Beispiel

• Schema als Selbstbeschreibung

– Metaschema für relationale Datenbanken

– Hypergraph zum Metaschema

– Beispiel

'

&

$

%8R

elat

iona

leO

per

atio

nen

Aus

gang

spun

ktW

irha

ben

das

Rel

atio

nale

Dat

enm

odel

lke

nnen

gele

rnt,

aber

noch

kein

eO

pera

tore

n

Pro

blem

Wel

che

Ope

rati

onen

gibt

esim

rela

tion

alen

Mod

ell?

Lösu

ngR

elat

iona

leO

pera

tion

en:M

enge

nope

rati

onen

,Ope

rati

onen

auf

eine

r/zw

eiR

elat

ione

n

• natürlicher Verbund

• Selektion mit A=c

• Projektion

• Selektion mit Spaltenvergleich

• Vereinigung

• Komplement

• Differenz

• Division

'

&

$

%9R

elat

iona

leA

nfra

gen

Aus

gang

spun

ktB

ishe

rnu

rdi

eO

pera

tore

nde

sR

elat

ione

nmod

ells

kenn

enge

lern

t

Pro

blem

Wie

lass

ensi

chko

mpl

exer

eA

nfra

gen

(z.B

.aus

LOG

OD

AT

)fo

rmul

iere

n?

Lösu

ngR

elat

ione

nalg

ebra

;M

ächt

igke

itim

Ver

glei

chzu

LOG

OD

AT

• Anfragen

• Definition: relationale Anfrage

• Definition: relationale Anfragesprache

• Relationenalgebra

• transitive Hülle

• Logikorientierte Datenmodelle

• Mächtigkeit der Relationenalgebra: Satz, Beweis

• Formalisierung von Anfragen

• Beispiel

'

&

$

%10R

elat

ione

nkal

kül

Aus

gang

spun

ktR

elat

ione

nalg

ebra

als

proz

edur

ale

Anf

rage

spra

che,

LOG

OD

AT

als

nich

tim

plem

enti

erte

logi

sche

Anf

rage

spra

che.

Pro

blem

Gib

tes

logi

sche

Anf

rage

spra

che,

die

äqui

vale

ntzu

rR

elat

ione

nalg

ebra

ist?

Lösu

ngR

elat

ione

nkal

kül:

Synt

axun

dSe

man

tik;

Mäc

htig

keit

imV

ergl

eich

zuR

elat

ione

nalg

ebra

und

LOG

OD

AT

• Syntax

• Semantik

• Gleichmächtigkeit von Algebra und Kalkül

– Satz

– Beweis

• negationsfreie Universum-unabhängige Relationen-algebra L

– Definition

– Abildung nach LOGODAT (Satz, Beweisskizze)

'

&

$

%11S

QL

Aus

gang

spun

ktR

elat

ione

nkal

kül

als

logi

sche

Anf

rage

spra

che

des

Rel

atio

nenm

o-de

lls

Pro

blem

Rel

atio

nenk

alkü

list

nich

tdi

rekt

als

Com

pute

rspr

ache

geei

gnet

Lösu

ngSQ

Lal

sst

anda

rdis

iert

eD

aten

bank

spra

che

• Kalkülteil

– Dreischrittverfahren

– Vereinfachungen

– Beispiele

• algebraischer Teil von SQL

– algebraischer, arithmetischer und textverarbei-tender Teil

– Natürlicher Verbund

– A=c-Selektion

– Projektion

– Vereinigung

– A=B-Vergleich

– Differenz

'

&

$

%12Z

ugri

ffss

truk

ture

n

Aus

gang

spun

ktR

elat

ione

nmod

ell(

inkl

.O

pera

tion

en)

Pro

blem

Wel

che

Dat

enst

rukt

uren

wer

den

verw

ende

t,um

sow

ohl

Änd

erun

gen

als

auch

Anf

rage

neffi

zien

tzu

real

isie

ren?

Lösu

ngT

upel

-ID

vs.

Tup

elad

ress

e;Z

ugri

ffss

truk

ture

n:Li

ste,

B∗ -

Bau

m,

Link

s

• Dauerhaftigkeit

• Lebensdauer eines Tupels

• Tupel-ID → Tupeladresse

• Effizienz für Anfragen und Änderungen

• Zugriffsstrukturen

– sequentielle Liste

– B∗-Baum

– Links

'

&

$

%13V

erbu

nd-A

lgor

ithm

en

Aus

gang

spun

ktO

pera

tion

enun

dZ

ugri

ffss

truk

ture

nde

sR

elat

ione

nmod

ells

Pro

blem

Ver

bund

ist

kom

plex

este

Ope

rati

onde

sR

elat

ione

nmod

ells

—w

ielä

sst

sich

dies

eeffi

zien

tre

alis

iere

n?

Lösu

ngV

erbu

nd-A

lgor

ithm

en:

Nes

tedL

oop,

Sort

iert

esM

isch

en,

Link

-Ver

bund

,H

ash-

Filt

er-V

erbu

nd

• natürlicher Verbund

• Hauptaufgabe jeder Verwirklichung

• NestedLoop

– Grundidee

– Strukturen für den NestedLoop-Verbund

– NestedLoop mit Blockliste

– Aufwandsabschätzung

• Sortiertes Mischen

• Link-Verbund

• Hash-Filter-Verbund

'

&

$

%15T

rans

akti

onen

Aus

gang

spun

ktO

pera

tion

ende

sR

elat

ione

nmod

ells

Pro

blem

Änd

erun

gen

imM

ehrb

enut

zerb

etri

ebkö

nnen

zuun

erw

ünsc

hten

Eff

ekte

nfü

hren

Lösu

ngT

rans

akti

onen

als

zent

rale

sK

onze

ptzu

rG

rupp

ieru

ngzu

sam

men

gehö

ren-

der

Änd

erun

gen

• Anforderungen (bzgl. Ablaufintegrität)

• Parallelität und Unabhängigkeit

• ACID-Eigenschaften

– atomicity

– consistency

– isolation

– durability

• Transaktionen erhalten Bedingungen

• Transaktionen laufen parallel und voneinanderunabhängig ab

• Korrekte Reihenfolgen

• Anweisungen, Transaktionen, Pläne

• Read/Write-Modell

'

&

$

%16K

onfli

kt-S

eria

lisie

rbar

keit

Aus

gang

spun

ktT

rans

akti

onen

imM

ehrb

enut

zerb

etri

eb

Pro

blem

Wel

che

Sche

dule

ssi

ndzu

läss

ig?

Lösu

ngK

onfli

kt-S

eria

lisie

rbar

keit

zur

Ken

nzei

chnu

nger

laub

ter

Sche

dule

s

• Konflikte

• Konflikt-Äquivalenz von Read/Write-Plänen,Konflikt-Serialisierbarkeit

– Konfliktgraphen

– Serialisierbarkeits-Test

– Transaktion und Konflikte

– Plan und Konfliktgraph

– Konflikt-Äquivalenz

• Abbruch, Wirksamwerden und Versionen

– Abbruch von Transaktionen

• Versionsfunktion

'

&

$

%17S

ched

uler

Aus

gang

spun

ktK

onfli

kt-S

eria

lisie

rbar

keit

zur

Ken

nzei

chnu

nger

laub

ter

Sche

dule

s

Pro

blem

Gew

ährl

eist

ung

von

Kon

flikt

-Ser

ialis

ierb

arke

itim

lauf

ende

nB

etri

eb

Lösu

ngSp

erre

nun

dSp

errp

roto

kolle

• Aufgaben

• Grobstruktur eines Schedulers

• Sperren

– Sperrprotokoll-Scheduler

– Erweiterung des Read/Write Modells um Sperren

– Semantik von Sperren

– Verträglichkeiten

– Arbeitsweise Sperrprotokoll-Scheduler

• Zwei-Phasen-Sperrprotokol

– Konflikt-Serialisierbarkeit unter dem Zwei-Phasen-Sperrprotokoll

– Sperrprotokoll-Scheduler verlangt Zwei-Phasen-Sperrprotokoll

– Verklemmungen

– Striktes Sperrverhalten

• Baum-Sperrprotokoll

– Sperren für baumartige Objektstrukturen

– Baum-Sperrprotokoll

– Konflikt-Serialisierbarkeit unter dem Baum-Sperrprotokoll

• Warn-Sperrprotokoll

– Motivation, Definition

– Warn-Sperrprotokoll

– Warn-Sperrprotokoll-Scheduler

– Konflikt-Serialisierbarkeit unter dem Warn-Sperrprotokoll

• Zeitmarken-Scheduler

– Idee, Arbeitsweise

– Konflikt-Serialisierbarkeit unter dem Zeitmarken-Scheduler

– Nutzlose Schreibanweisungen

– Unvergleichbarkeit von Zwei-Phasen-Sperrprotokollund Zeitmarken-Scheduler

• Pessimistische und optimistische Scheduler

'

&

$

%18S

icht

-Ser

ialis

ierb

arke

it

Aus

gang

spun

ktK

onfli

kt-S

eria

lisie

rbar

keit

oftm

als

zust

reng

–Si

cht-

Seri

alis

ierb

arke

ital

sA

lter

nati

ve:

betr

acht

etE

ndzu

stan

dun

dge

lese

neD

aten

Pro

blem

Gew

ährl

eist

ung

von

Sich

t-Se

rial

isie

rbar

keit

imla

ufen

den

Bet

rieb

Lösu

ngT

est

auf

Sich

t-Se

rial

isie

rbar

keit

;V

ergl

eich

Kon

flikt

-Ser

ialis

ierb

arke

it/

Sich

t-Se

rial

isie

rbar

keit

imla

ufen

den

Bet

rieb

• Access-Modell

– Access-Pläne

– Semantik von Access-Plänen

– Endzustand-Äquivalenz von Access-Plänen,Endzustand-Serialisierbarkeit

– Serialisierbarkeitsgraph, Serialisierbarkeitstest

• Read/Write-Modell

– Semantik von Read/Write-Plänen

– Wertverlaufs-Semantik

– Sicht-Äquivalenz von Read/Write-Plänen, Sicht-Serialisierbarkeit

– Serialisierbarkeitsgraphen

– Serialisierbarkeitstest

• Konflikt-Serialisierbarkeit vs. Sicht-Serialisierbarkeit

– Konflikt-Serialisierbarkeit impliziert Sicht-Serialisierbarkeit

– Konflikt-Serialisierbarkeit echt strenger als Sicht-Serialisierbarkeit

• Projektion von Plänen

– Monotonie der Konflikt-Serialisierbarkeit

– Konflikt-Serialisierbarkeit ist größte monotoneTeilklasse von Sicht-Serialisierbarkeit

'

&

$

%20O

bjek

tori

enti

erte

Mod

elle

Aus

gang

spun

ktE

R-M

odel

l,re

lati

onal

esM

odel

l

Pro

blem

groß

eD

ista

nzzw

isch

enE

R-

und

rela

tion

alem

Mod

ell

Lösu

ngob

jekt

orie

ntie

rte

Dat

enm

odel

le:

unm

itte

lbar

eU

nter

stüt

zung

sem

anti

sche

Kon

zept

e

• Logik- vs. objektorientierte Datenmodelle

• Objektorientierte Nachbildungen

• Objekte:

– Aufbau

– Eigenschaften

– Klassen und Typen

– Surrogate und Werte

• objektorientierte Beschreibung des relationalenDatenmodells

– Typen

– Anfragetypen

– Ergebnisse von Anfragen

– Strukturelle und operationale Gesichtspunkte

• Modellierung semantischer Bedingungen im relatio-nalen und im objektorientierten Modell

– Beziehungen

– Aussonderungs- und Verallgemeinerungsbedin-gungen

– Spezialisierungshierarchie struktureller Typen

– Inklusionshierarchie von Klassen

– Verallgemeinerungsbedingung und abstrakteKlassen

• Unterstützung und Umschreibung semantischerBegriffe in objektorientierten Datenmodellen

'

&

$

%24S

chem

aent

wur

f

Aus

gang

spun

ktE

R-M

odel

l,re

lati

onal

esM

odel

l

Pro

blem

Wie

kom

mt

man

zuei

ner

gute

nM

odel

lieru

ng?

Lösu

ngK

rite

rien

für

eine

ngu

ten

Ent

wur

f;E

ntw

urfs

heur

isti

ken

• Entscheidungen und ihre wechselseitige Abhängig-keit

• Seiende

• grundlegende Beziehungen und Handlungen

• Vollständigkeit und Redundanzfreiheit

• Entwurfsheuristiken

• Aufgaben der Entwurfstheorie

'

&

$

%25Fu

nkti

onal

eA

bhän

gigk

eite

n

Aus

gang

spun

ktR

elat

ione

nmod

ell

Pro

blem

Ber

ücks

icht

igun

gfu

nkti

onal

erA

bhän

gigk

eite

nbe

imSc

hem

aent

wur

f

Lösu

ng3.

Nor

mal

form

,B

oyce

-Cod

d-N

orm

alfo

rm

• funktionale Abhängigkeiten:

– Syntax, Semantik und Pragmatik

– logische Implikationen

– Abschluß einer Attributmenge: Satz, Beweis

• Schlüssel

– Definition

– Relationenschemas mit genau einem Schlüssel:Satz, Beweis

• 3. Normalform

• Boyce / Codd-Normalform

'

&

$

%26V

erbu

ndab

häng

igke

iten

Aus

gang

spun

ktR

elat

ione

nmod

ell

Pro

blem

Ber

ücks

icht

igun

gm

ehrw

erti

ger

Abh

ängi

gkei

ten

beim

Sche

mae

ntw

urf

Lösu

ng4.

und

5.N

orm

alfo

rm

• mehrwertige Abhängigkeiten

– Konzept

– Syntax, Semantik und Pragmatik

– mengenwertige Funktionalität und Produktbil-dungen

– logische Implikationen

• logische Implikationen

– für mehrwertige Abhängigkeiten

– für funktionale und mehrwertige Abhängigkeiten

– Korrektheit einiger Implikationen

• 4. Normalform

• Verbundabhängigkeiten

– Konzept

– Syntax, Semantik und Pragmatik

• 5. Normalform

'

&

$

%27E

ntha

lten

sein

sabh

ängi

gkei

ten

Aus

gang

spun

ktre

lati

onal

eE

ntw

urfs

theo

rie,

obje

ktor

ient

iert

erE

ntw

urf

Pro

blem

Ber

ücks

icht

igun

gde

rIn

klus

ions

hier

arch

ievo

nK

lass

enbe

imre

lati

onal

enE

ntw

urf

Lösu

ngE

ntha

lten

sein

sabh

ängi

gkei

ten

refe

renz

iere

nSc

hlüs

sel

• Enthaltenseinsabhängigkeiten

– Konzept

– Einbettung

– ... im logikorientierten Datenmodell

– Formalisierung der Aussonderungs- und Verweis-bedingungen der Modellierung

• Implikationen

– von Enthaltenseinsabhängigkeiten

– von funktionalen Abhängigkeiten und Enthalten-seinsabhängigkeiten

– Reflexivität, Transitivität, Projektion und Per-mutation: Satz, Beweis

• Zusammenwirken von funktionalen Abhängigkeitenund Enthaltenseinsabhängigkeiten

– Unentscheidbarkeit

– entscheidbare Spezialfälle: F-I-Rückschluß, F-I-Vereinigung

'

&

$

%28E

ntw

urfs

verf

ahre

n

Aus

gang

spun

ktA

bhän

gigk

eite

n,N

orm

alfo

rmen

Pro

blem

Wie

kom

mt

man

beig

egeb

enen

Abh

ängi

gkei

ten

zuei

nem

gute

nSc

hem

a?

Lösu

ngG

ütek

rite

rien

für

Sche

mat

a;Ä

quiv

alen

zvo

nSc

hem

ata;

Zer

legu

ngs-

und

Synt

hese

verf

ahre

n

• wünschenswerte Eigenschaften und verbotene Teil-strukturen

– Relationenschema mit genau einem Schlüssel

– 3. Normalform

– Boyce/Codd-Normalform

– 4. Normalform

– 5. Normalform

– Enthaltenseinsabhängigkeiten referenzierenSchlüssel

• Kosten beim Betreiben einer Datenbank

– Kostenarten: Speicherungskosten, Anfrageko-sten, Änderungskosten

– Rolle der Normalformen

– Redundanzfreiheit

• wünschenswerte Eigenschaften von Schemas

– Entwurfsheuristiken für eine gute Modellierung

– Kostenoptimierung (insbes. Speicherungs- undÄnderungskosten)

• halbalgorithmisches Verfahren zum Entwurf vonDatenbankschemas

– Algorithmus

– Transformationen

– Äquivalenzkriterium: Instanzenunterstützung

• Zerlegungen gemäß einer Verbundabhängigkeit

– Verbund-Unterstützung eines Universalrelation-Schemas

– Verbund-Unterstützung eines Universalrelation-Schemas mit funktionalen Abhängigkeiten

– Verbund-unterstützte Zerlegung in Boyce /Codd-Normalform

– Boyce / Codd-Normalform und treue Unterstüt-zung

– treue Zerlegungen

– treue Verbund-Unterstützung eines Universalrelation-Schemas mit funktionalen Abhängigkeiten

• treue Verbund-unterstützte Synthese in 3.Normal-form