Relacyjny model danych

Wykład 2

S. Kozielski

Model danych

• struktury danych

• operacje na danych

• ograniczenia integralno

ś

ciowe

Relacyjny model danych

• relacje

• operacje (operatory) algebry relacji

• wi

ę

zy referencyjne + ograniczenia dziedzin relacji

Relacja (matematyka)

X, Y – zbiory,

Iloczyn kartezja

ń

ski X

×

Y = {(x,y): x

∈

X

∧

y

∈

Y}

Dwucz

ł

onowa relacja w X

×

Y = {(x,y): x

∈

X

∧

y

∈

Y

∧

x

ρ

y}

⊂

X

×

Y

N – cz

ł

onowa relacja (relacja stopnia N):

podzbiór iloczynu kartezja

ń

skiego X

1

×

X

2

×

X

3

×

...

×

X

N

Relacja – bazy danych

Atrybuty: A

1

, A

2

, A

3

, …

np.: nazwisko, nrp, kwota, adres

Dziedziny atrybutów: D

A1

, D

A2

, D

A3

,... (inaczej domeny: dom(A

1

), dom(A

2

))

– zbiory dopuszczalnych warto

ś

ci atrybutów (typy danych)

Schemat relacji: R = { A

1

, A

2

, ..., A

p

} – podzbiór zbioru atrybutów

Relacja r o schemacie R: r(R) - podzbiór iloczynu kartezja

ń

skiego dziedzin

atrybutów tworz

ą

cych schemat D

A1

×

D

A2

×

...

×

D

Ap

r(R)

⊂

D

A1

×

D

A2

×

...

×

D

Ap

Przykład:

R = {nrp, nrt, kwota}

D

nrp

= {1, 2, 3}, D

nrt

= {1, 2, 3}, D

kwota

= {150, 200, 300}

D

nrp

×

D

nrt

×

D

kwota

= {1, 1, 150

2, 1, 150

3, 1, 150

…

3, 3, 150

3, 3, 200

3, 3, 300}

Wypłaty

200

3

1

200

2

3

150

1

1

150

3

3

300

2

2

kwota

nrt

nrp

Wypłaty

⊂

D

nrp

×

D

nrt

×

D

kwota

Relacja jako zbiór krotek

r(R) = {t

1

, t

2

, t

3

, …, t

k

}

Krotka t jest uporz

ą

dkowan

ą

list

ą

warto

ś

ci t = < v

1,

v

2

…v

p

>

gdzie v

i

∈

D

Ai

lub jest specjaln

ą

warto

ś

ci

ą

pust

ą

NULL

(A, B, C)

————

a

1

b

1

c

1

- krotka t

1

a

2

b

2

c

2

- krotka t

2

a

3

b

3

c

3

- krotka t

3

a

4

b

4

c

4

- krotka t

4

n-ty element krotki t oznaczany jest przez t[A

n

] np. t

4

[B] = b

4

Elementarne własno

ś

ci relacji

• Ka

ż

dy atrybut relacji ma unikaln

ą

nazw

ę

• Porz

ą

dek atrybutów w relacji nie jest istotny

• Porz

ą

dek krotek w relacji nie jest istotny

• Relacja nie zawiera krotek powtarzaj

ą

cych si

ę

(wszystkie krotki s

ą

unikalne)

Unikalno

ść

krotek relacji a poj

ę

cie klucza

• Ka

ż

dy podzbiór S atrybutów schematu relacji R

(S

⊆

R), taki

ż

e dla ka

ż

dych dwóch krotek ze zbioru

r(R) zachodzi

t

i

[S]

≠

t

j

[S] jest nazywany

superkluczem (super key) relacji

• Superkluczem jest m.in. cały schemat relacji R

• Superklucz mo

ż

e posiada

ć

nadmiarowe atrybuty

Poj

ę

cie klucza relacji

• Kluczem K schematu relacji R nazywamy superklucz

schematu R o takiej własno

ś

ci,

ż

e usuni

ę

cie

dowolnego atrybutu A z K powoduje,

ż

e K’ = K - A nie

jest ju

ż

superkluczem

• Klucz jest minimalnym superkluczem (zachowuj

ą

cym

własno

ść

unikalno

ś

ci krotek relacji)

• Schemat relacji mo

ż

e posiada

ć

wi

ę

cej ni

ż

jeden klucz

• Wyró

ż

niony klucz: klucz główny (podstawowy)

• Pozostałe klucze: klucze kandyduj

ą

ce (wtórne)

Inna definicja klucza

• Kluczem jest minimalny zestaw atrybutów schematu

relacji, którego warto

ś

ci jednoznacznie identyfikuj

ą

ka

ż

d

ą

krotk

ę

relacji

Przykład

Pracownicy (nrp, imi

ę

, nazwisko, PESEL, NIP,

seria_i_nr_dowodu, data_urodzenia, imi

ę

_ojca,

imi

ę

_matki, adres, nazwisko_rodowe, tytuł, zawód,

nazwa_zakładu_pracy, adres_zp, sta

ż

)

Klucze kandyduj

ą

ce:

nrp

PESEL

NIP

seria_i_nr_dowodu

imi

ę

, nazwisko, imi

ę

_ojca

Ró

ż

ne formy opisu stosowane w modelu relacyjnym

typ rekordu

nagłówek tablicy

schemat relacji

pole

kolumna

atrybut

rekord

wiersz

krotka

plik

tablica (tabela)

relacja

Opis fizyczny

(fizycznych struktur d.)

Opis tablicowy

Opis formalny

Algebra relacji

Dane relacje: r(R), s(S)

Podstawowe operacje: selekcja, projekcja, zł

ą

czenie,

iloczyn kartezja

ń

ski, dzielenie, operacje na zbiorach

Selekcja

w – warunek selekcji (wyra

ż

enie logiczne - predykat)

σ

w

(r) = {t : t

∈

r

∧

w(t) = True } = p(R)

Przykład selekcji

A

B

C

2

1

2

σ

C=2

⇒

A

B

C

2

2

Projekcja

Niech X

⊆

R

π

X

(r) = { u : t

∈

r

∧

u = t [X] } = q (X)

Przykład projekcji

A

B

C

A

C

π

AC

⇒

Zł

ą

czenie (naturalne)

r



s = { u :

∃

t

∈

r

∧ ∃

w

∈

s

∧

t [R

∩

S] = w [R

∩

S]

∧

u[R] = t

∧

u[S] = w}

= z (R

∪

S)

Przykład zł

ą

czenia naturalnego

r (A, B, C)

s (C, D)

z (A, B, C, D)

————
 ———

=

—————

a

1

b

1

c

1

c

1

d

1

a

1

b

1

c

1

d

1

a

2

b

2

c

2

c

5

d

5

a

4

b

4

c

1

d

1

a

3

b

3

c

3

a

4

b

4

c

1

Ogólna posta

ć

zł

ą

czenia (

Θ

- zł

ą

czenie)

r



w

s =

σ

w

(r

×

s)

lub

r



A

Θ

B

s =

σ

A

Θ

B

(r

×

s) ,

gdzie A

∈

R, B

∈

S, dom(A) = dom(B)

Dzielenie

Niech b

ę

d

ą

dane relacje: r(XY), s(Y)

r

÷

s = { u :

∀

w

∈

s

∃

t

∈

r t [Y] = w

∧

t [X] = u }

Przykład dzielenia

r (nrp, nrt)

s (nrt)

r

÷

s = z (nrp)

————

———

———

1

1

1

1

1 2

2

3

1

3

3

2 2

2 3
3 1
3 2
3

3

Operatory mnogo

ś

ciowe

(operacje na zbiorach krotek)

Niech b

ę

d

ą

dane relacje: r(R), s(R)

Suma:

r

∪

s

Ró

ż

nica:

r \ s

Iloczyn:

r

∩

s

Powy

ż

sze operacje mog

ą

by

ć

rozszerzone na

przypadek relacji r(R), s(S), w których R i S s

ą

równoliczne, a odpowiadaj

ą

ce sobie atrybuty

schematów R i S maj

ą

identyczne dziedziny

Pytanie Z1 jako wyra

ż

enie algebry relacji

Z1 =

π

nazwa

(

σ

nazwisko = ‘Jaworek’

(Pracownicy



Wyp

ł

aty



Tematy))

Zł

ą

czenie tabel

Wypłaty

nrp

nrt

kwota

2

2

300

3

3

150

1

1

150

3

2

200

1

3

200

Pracownicy

nrp

nazwisko

adres

nrz

1

Lipowski

Ruda

2

2

Grabski

Zabrze

1

3

Jaworek

Gliwice

1

Pracownicy



Wypłaty

200

3

2

Ruda

Lipowski

1

200

2

1

Gliwice

Jaworek

3

150

1

2

Ruda

Lipowski

1

150

3

1

Gliwice

Jaworek

3

300

2

1

Zabrze

Grabski

2

kwota

nrt

nrz

adres

nazwisko

nrp

Pracownicy



Wypłaty



Tematy

2

Pr. reaktora

200

3

2

Ruda

Lipowski

1

1

Pr. przetwor.

200

2

1

Gliwice

Jaworek

3

2

Pr. zasilacza

150

1

2

Ruda

Lipowski

1

2

Pr. reaktora

150

3

1

Gliwice

Jaworek

3

1

Pr. przetwor.

300

2

1

Zabrze

Grabski

2

kier.

nazwa

kwota

nrt

nrz

adres

nazwisko

nrp

σ

nazwisko = ‘Jaworek’

(

Pracownicy



Wypłaty



Tematy

)

1

Pr. przetwor.

200

2

1

Gliwice

Jaworek

3

2

Pr. reaktora

150

3

1

Gliwice

Jaworek

3

kier.

nazwa

kwota

nrt

nrz

adres

nazwisko

nrp

π

nazwa

(

σ

nazwisko = ‘Jaworek’

(

Pracownicy



Wyp

ł

aty



Tematy

))

Pr. przetwor.

Pr. reaktora

nazwa

Własno

ś

ci operatorów algebry relacji

r(R), s(S), z(Z) – dane relacje

1) Przemienno

ść

zł

ą

cze

ń

: r



s = s



r

2) Ł

ą

czno

ść

zł

ą

cze

ń

: (r



s)



z = r



(s



z)

3) Przemienno

ść

selekcji i zł

ą

cze

ń

dla wyra

ż

enia

σ

w

(r



s)

Niech atr(w) – zbiór atrybutów wyst

ę

puj

ą

cych w w

Je

ś

li atr(w)

⊆

R, to

σ

w

(r



s) = (

σ

w

(r ))



s

Je

ś

li atr(w)

⊆

S, to

σ

w

(r



s) = r



(

σ

w

(s ))

Je

ś

li w= w1

∧

w2 oraz atr(w1)

⊆

R i atr(w2)

⊆

S,

to

σ

w

(r



s) = (

σ

w1

(r ))



(

σ

w2

(s))

Przykłady równowa

ż

nej postaci wyra

ż

e

ń

P1=

π

nazwisko

(

σ

nrz=3

∧

kwota>2000

(

Pracownicy



Wyp

ł

aty))

P1=

π

nazwisko

((

σ

nrz=3

(

Pracownicy))



(

σ

kwota>2000

(Wyp

ł

aty)))

P2=

π

nazwisko

(

σ

nazwa = ‘Pr.gen.’

(

Pracownicy



Wyp

ł

aty



Tematy

))

P2=

π

nazwisko

(

Pracownicy



Wyp

ł

aty

(

σ

nazwa = ‘Pr.gen.’

(

Tematy

)))

Drzewo rozbioru wyra

ż

enia algebry relacji – plan realizacji zapytania

Pracownicy(20)

Wypłaty(50)



+

σ

nrz = 3

∧

kwota>2000

+

π

nazwisko

P1

Optymalizacja wyra

ż

e

ń

algebry relacji

(wykorzystanie przemienno

ś

ci selekcji i zł

ą

cze

ń

)

Pracownicy(20)

Wypłaty(50)



+

π

nazwisko

P1

σ

nrz = 3

σ

kwota>2000

P2=

π

nazwisko

(

σ

nazwa = ‘Pr.gen.’

(Pracownicy



Wyp

ł

aty



Tematy))

P2=

π

nazwisko

(Pracownicy



Wyp

ł

aty

(

σ

nazwa = ‘Pr.gen.’

(Tematy)))

Optymalizacja wyra

ż

e

ń

algebry relacji

(dobór kolejno

ś

ci zł

ą

cze

ń

- 1)

Pracownicy(20)

Wypłaty(50)



+

π

nazwisko

P2

Tematy(10)

σ

nazwa =’Pr. gen.’



Optymalizacja wyra

ż

e

ń

algebry relacji

(dobór kolejno

ś

ci zł

ą

cze

ń

- 2)

Pracownicy(20)

Wypłaty(50)



+

π

nazwisko

P2

Tematy(10)

σ

nazwa =’Pr. gen.’



Proste reguły optymalizacji wyra

ż

e

ń

algebry relacji

•

Przenie

ść

selekcje (i projekcje) jak najwy

ż

ej w drzewie rozbioru

wyra

ż

enia

•

Wykona

ć

projekcje razem ze zł

ą

czeniami lub selekcjami

•

Dobra

ć

kolejno

ść

zł

ą

cze

ń

według selekcji najsilniej

redukuj

ą

cych