(3)Relációs algebra – A relációs algebrai m veletek operandusai a relációk

M veletek a relációs modellben

• A felhasználónak szinte állandó jelleggel szüksége van az adatbázisban eltárolt adatok egy részére.

• Megfogalmaz egy kérést, amelyben leírja, milyen adatokra van szüksége, az adatbázis nyelvezetében ezt lekérdezésnek nevezzük.

A relációs adatmodell m veleteire kétféle jelölést használunk:

– relációs algebra, mely algebrai jelölést használ, a lekérdezéseket algebrai operátorok segítségével adja meg;

– relációs kalkulus, mely matematikai logikán alapul, a lekérdezést logikai formulák segítségével adja meg.

A relációs algebra és a relációs kalkulus ekvivalens:

o egy relációs algebrai lekérdezés átalakítható egy relációs kalkulusbeli lekérdezéssé és fordítva (lásd [Ul89]).

Relációs algebra

– A relációs algebrai m veletek operandusai a relációk.

– A relációt a nevével szokták megadni, például R vagy Alkalmazottak.

– Az operátorokat alkalmazva a relációkra, eredményként szintén relációkat kapunk, ezekre ismét alkalmazhatunk relációs algebrai operátorokat, így egyre bonyolultabb kifejezésekhez jutunk.

– Egy lekérdezés tulajdonképpen egy relációs algebrai kifejezés.

– A relációs algebrai m veletek esetén szükségünk lesz feltételekre.

– A feltételek a következ típusúak lehetnek:

<attribútum_név>

<attribútum_név>

<konstans>

=

<>

<

<=

>

>=

<attribútum_név> IS IN

<reláció> (melynek egy attribútuma van)

<konstans> IS NOT IN

NOT <feltétel>

<feltétel> OR <feltétel>

AND

Relációs algebra m veletei

– Az els öt az alapvet m velet, a következ ket ki tudjuk fejezni az els öt segítségével.

1) Kiválasztás (Selection):

• Az R relációra alkalmazott kiválasztás operátor f feltétellel olyan új relációt hoz létre, melynek sorai teljesítik az f feltételt.

• Az eredmény reláció attribútumainak a száma megegyezik az R reláció attribútumainak a számával.

• Jelölés:

σf (R).

Grafikusan ábrázolva, ha az R reláció a nagy téglalap, a kiválasztás eredménye a befestett rész.

példa: Keressük a kis kereset alkalmazottakat (akinek kisebb, vagy egyenl a fizetése 500 euró-val). A lekérdezés a következ :

σFizetés <= 500 (Alkalmazottak) A lekérdezés eredménye:

SzemSzám Név RészlegID Fizetés

111111 Nagy Éva 2 300

222222 Kiss Csaba 9 400

333333 Kovács István 2 500

példa: Keressük a 9-es részleg nagy fizetés alkalmazottait (akinek 500 euró-nál nagyobb a fizetése). A lekérdezés:

σFizetés > 500 AND RészlegID = 9 (Alkalmazottak) Az eredmény:

SzemSzám Név RészlegID Fizetés

456777 Szabó János 9 900

2) Vetítés (Projection): Adott R egy reláció A1, A2,..., An attribútumokkal.

• A vetítés eredménye: reláció, mely R-nek csak bizonyos attribútumait tartalmazza.

• Ha kiválasztunk k attribútumot az n-b l: A A_i1, _i2, ,A -et, és ha _ik esetleg a sorrendet is megváltoztatjuk, az eredmény reláció a kiválasztott k attribútumhoz tartozó oszlopokat fogja tartalmazni, viszont az összes sorból.

• az eredmény is egy reláció, nem lehet két azonos sor a vetítés eredményében, az azonos sorokból csak egy marad az eredmény relációban.

• Jelölés:

1, 2, , ( )

i i ik

A A A R

π

Grafikusan ábrázolva, ha az R reláció a nagy téglalap, a vetítés eredménye a befestett rész.

példa: Ha az Alkalmazottak relációból csak az alkalmazott neve és fizetése érdekel, akkor a következ m velet eredménye a kért reláció:

Név, Fizetés(Alkalmazottak) π

Az eredmény:

Név Fizetés (euró)

Nagy Éva 300

Kiss Csaba 400

Szabó János 900

Szilágyi Pál 700

Vincze Ildikó 800 Kovács István 500

példa:

CREATE TABLE Diákok (

BeiktatásiSzám INT PRIMARY KEY, Név VARCHAR(50),

Cím VARCHAR(100),

SzületésiDatum DATE,

CsopKod CHAR(3) REFERENCES Csoportok (CsopKod), Átlag REAL

);

CsopKod(Diákok) π

3) Descartes szorzat.

• adottak az R1 és R2 relációk

• a két reláció Descartes szorzata (R₁ × R₂) azon párok halmaza, amelyeknek els eleme az R1 tetsz leges eleme, a második pedig az R₂ egy eleme.

• az eredményreláció sémája az R1 és R2 sémájának egyesítése.

R1

R1 × R2 eredménye:

A R1.B R2.B C D 12 33 20 55 80 12 33 30 67 97 12 33 40 75 99 24 46 20 55 80 24 46 30 67 97 24 46 40 75 99 A B

12 33 24 46

R2 B C D

20 55 80 30 67 97 40 75 99

4) Egyesítés.

• adottak az R₁ és R₂ relációk,

• R1 és R2 attribútumainak a száma megegyezik,

• ugyanabban a pozícióban lev attribútumnak ugyanaz az értékhalmaza,

• a két reláció egyesítése tartalmazni fogja R1 és R2 sorait,

• az egyesítésben egy elem csak egyszer szerepel,

• jelölés: R₁ U R₂

5) Különbség.

• adottak az R₁ és R₂ relációk,

• R1 és R2 attribútumainak a száma megegyezik

• ugyanabban a pozícióban lev attribútumnak ugyanaz az értékhalmaza

• a két reláció különbsége azon sorok halmaza, amelyek R1-ben szerepelnek és R2-ben nem

• jelölés: R₁ ⁻ R₂

Szem

Szám Név RészlegID Fizetés (euró)

222222 Kiss Csaba 9 400

456777 Szabó János 9 900

234555 Szilágyi Pál 2 700

333333 Kovács István 2 500

Szem

Szám Név RészlegID Fizetés (euró)

111111 Nagy Éva 2 300

456777 Szabó János 9 900

123444 Vincze Ildikó 1 800

R1

R2

R1 U R2:

Szem

Szám Név Részleg

ID Fizetés (euró) 222222 Kiss Csaba 9 400 456777 Szabó János 9 900 234555 Szilágyi Pál 2 700 333333 Kovács István 2 500 111111 Nagy Éva 2 300 123444 Vincze Ildikó 1 800

R1 - R2:

Szem

Szám Név Részleg

ID Fizetés (euró) 222222 Kiss Csaba 9 400 234555 Szilágyi Pál 2 700 333333 Kovács István 2 500

Még vannak hasznos m veletek: ezek az öt alapvet m velettel kifejezhet ek.

6) Metszet:

• adottak az R₁ és R₂ relációk,

• R1 és R2 attribútumainak a száma megegyezik

• ugyanabban a pozícióban lev attribútumnak ugyanaz az értékhalmaza

• a két reláció metszete:

)

( _{1 2}

1 2

1 R R R R

R ∩ = − − .

7) Théta-összekapcsolás ( -Join):

• adottak az R₁ és R₂ relációk,

• R1 és R2 relációk Descartes szorzatából kiválasztjuk azon sorokat, melyek eleget tesznek a feltételnek:

R₁ R₂ =σ_θ(R R₁× ₂)

példa: számítsuk ki: R1 R₂

A R1.B R1.C R2.B R2.C D

11 23 32 23 32 44

11 23 32 23 32 57

11 23 32 76 82 99

65 76 82 76 82 99

97 76 82 76 82 99

R1 A B C 11 23 32 65 76 82 97 76 82

R2 B C D 23 32 44 23 32 57 76 82 99

8) Természetes összekapcsolás (Natural join):

• legyenek az R₁ és R₂ relációk

• az R1 és R2 relációknak egy vagy több közös attribútuma van.

• legyen B az R1, illetve C az R2 reláció attribútumainak a halmaza,

• a közös attribútumok: B ∩ C = {A1, A₂, …, A_p}.

A természetes összekapcsolás:

R₁ R₂ = π_{B C∪} (R_{1 ( .R A R A1 1= 2. ) ( .1 ∧ R A R A1 2= 2. )2 ∧ ∧( .R A R A1 p= 2. p)}R₂,

Ri.Aj jelöli az Aj attribútumot az Ri relációból, i {1,2}, j {1,2, …, p}.

R1 R2

A B C D

11 23 32 44 11 23 32 57 65 76 82 99 97 76 82 99

R₁ ^{A B C}

11 23 32 65 76 82 97 76 82

R₂ ^{B C D}

23 32 44 23 32 57 76 82 99

• R1 és R2 relációk természetes összekapcsolása esetén azokat a sorokat párosítjuk össze, amelyek értékei az R₁ és R₂ összes közös attribútumán megegyeznek,

• legyen r₁ az R₁ egy sora és r₂ az R₂ egy sora, ekkor az r₁ és r₂ párosítása akkor sikeres, ha az r1 és r2 megfelel értékei megegyeznek az összes A₁, A₂, …, A_p közös attribútumon.

• ha az r1 és r2 sorok párosítása sikeres, akkor a párosítás eredményét összekapcsolt sornak nevezzük,

• az összekapcsolt sor megegyezik az r1 sorral az R1 összes attribútumán és r2 sorral az R2 összes attribútumán,

• az R1 R2 eredményében R1 és R2 közös attribútumai csak egyszer szerepelnek.

példa: Szállít Szállítók Áruk Szállítók:

SzállID SzállNév SzállCím 111 Rolicom A.Iancu 15 222 Sorex 22 dec. 6 Áruk:

ÁruID ÁruNév MértEgys 45 Milka csoki tábla

67 Heidi csoki tábla

56 Milky way rúd

Szállít:

SzállID ÁruID Ár

111 45 2.5

222 45 2.6

111 67 1.7

111 56 2.1

222 67 1.8

222 56 2.2

Szállít Szállítók eredménye:

SzállID SzállNév SzállCím ÁruID Ár 111 Rolicom A.Iancu 15 45 2.5 222 Sorex 22 dec. 6 45 2.6 111 Rolicom A.Iancu 15 67 1.7 111 Rolicom A.Iancu 15 56 2.1 222 Sorex 22 dec. 6 67 1.8 222 Sorex 22 dec. 6 56 2.2

Szállít Szállítók Áruk eredménye:

SzállID SzállNév SzállCím Áru

ID ÁruNév Mért

Egys Ár 111 Rolicom A.Iancu 15 45 Milka csoki Tábla 2.5 222 Sorex 22 dec. 6 45 Milka csoki Tábla 2.6 111 Rolicom A.Iancu 15 67 Heidi csoki Tábla 1.7 111 Rolicom A.Iancu 15 56 Milky way Rúd 2.1 222 Sorex 22 dec. 6 67 Heidi csoki Tábla 1.8 222 Sorex 22 dec. 6 56 Milky way Rúd 2.2

• relációs algebrai m veletek alkalmazásával újabb relációkat kapunk,

• szükséges egy olyan operátor, amelyik átnevezi a relációkat.

9) Átnevezés:

• R(A1, A2, …, An) egy reláció,

• ρ_{S B B( , , , )1 2 Bn} ( )R az átnevezés operátor az R relációt S relációvá nevezi át, az attribútumokat pedig balról jobbra B1, B2, …, Bn-né,

• ha az attribútum neveket nem akarjuk megváltoztatni, akkor ( )ρ_S R operátort használunk.

10) Hányados (Quotient):

• R₁ reláció sémája: {X₁, X₂,…, X_m, Y₁,Y₂,…,Y_n},

• R2 reláció sémája pedig: {Y1, Y2, …, Yn},

• R1 az osztandó, R2 az osztó.

Jelölés: X = {X1, X₂,…, X_m}, Y = {Y₁,Y₂,…,Y_n}.

R1 (X, Y), R2 (Y) hányadosát jelöljük:

R1 DIVIDE BY R2 (X)-el

a hányados reláció sémája {X1, X2,…, Xm}.

A hányados relációban megjelenik egy x sor, ha minden y sorra az R2- b l az R₁-ben megjelenik egy r₁ sor, melyet az x és y sorok összeragasztásából kapunk.

példa:

A = π_ÁruID(Áruk),

S = πSzállID, ÁruID(Szállít)

a következ sorok az S relációban:

SzállID ÁruID

S1 A1

S1 A2

S1 A3

S1 A4

S1 A5

S1 A6

S2 A1

S2 A2

S3 A2

S4 A2

S4 A4

S4 A5

a) A reláció:

ÁruID A1 S DIVIDE A(SzállID) eredménye:

SzállID S1 S2

b) A reláció:

ÁruID A2 A4

S DIVIDE A(SzállID):

SzállID S1 S4

c) A reláció:

ÁruID A1 A2 A3 A4 A5 S DIVIDE A(SzállID): A6

SzállID S1

Lekérdezések megfogalmazása relációs algebrai m veletek segítségével

• relációs algebra segítségével tetsz leges bonyolultságú kifejezéseket képezhetünk.

• az operátorokat alkalmazhatjuk adott relációkra, illetve más operátorok alkalmazásának eredményeként kapott relációkra.

• relációs algebrai m veletek megfogalmazásakor zárójeleket használhatunk az operándusok csoportosítása érdekében.

• relációs algebrai kifejezéseket megadhatunk kifejezésfával is

példa: Legyenek a Szállítók, Áruk, Szállít relációk

lekérdezés: „Keressük a ’Milka csoki’-t szállító cégek nevét.”

A: lépésekre felbontva:

MCsokiIDk = π_ÁruID(σÁruNév 'Milka csoki'₌ (Áruk)) MCsokiAjánlatok = σÁruID IN MCsokiIDk(Szállít) MCsokiSzállítóIDk = π_SzállID(MCsokiAjánlatok) McsokiSzállítóNevek =

SzállNév( SzállID IN MCsokiSzállítóIDk(Szállítók))

π σ

B: π_SzállNév(σÁruNév 'Milka csoki'₌ (Szállít Szállítók Áruk))

„Keressük azon szállítókat, akik nem szállítják a 67-es ID-j árut”.

Száll67 = π_SzállID(σ_{ÁruID 67=} (Szállít))

NemSzáll67 = π_SzállID(Szállítók) − Száll67 Nem2Száll67 =π_SzállID(σ_{ÁruID 67<>} (Szállít))

Kérdés: Mi a különbség NemSzáll67 és Nem2Száll67?

Ahhoz, hogy megkapjuk a szállító nevét:

SzállNév(

π NemSzáll67 Szállítók)

példa: „Keressük azon szállítókat, kik szállítják az összes árut.”

SzállNév(

π ((πSzállID, ÁruID(Szállít)) DIVIDE BY (π_ÁruID(Áruk))) Szállítók) Osztáshoz egy bináris és egy unáris relációra van szükség.

• a bináris reláció: πSzállID, ÁruID(Szállít)

• az unáris pedig: π_ÁruID(Áruk).

Az osztás eredménye tartalmazni fogja azon szállítók ID-jét, akik az összes árut szállítják.

példa: „Keressük azon szállítókat, akik legalább azon árukat szállítják, melyeket az 111 ID-jú szállító szállít.”

SzállNév(

π ((πSzállID, ÁruID(Szállít)) DIVIDE BY

(πÁruID(σSzállID 111₌ (Szállít))) Szállítók) 1. áru ID-k, melyeket szállít a 111-es ID-j szállító:

SzállID 111

ÁruID( (Szállít))

π σ ₌

2. az osztás segítségével meghatározzuk azon szállító ID-kat, akik szállítják legalább az el z lekérdezésben megkapott árukat.

példa: „Keressük azon szállítókat, akik csak a 67-es ID-j árut szállítják.”

SzállNév(

π ((π_SzállID(σ_{ÁruID 67=} (Szállít))) −

(π_SzállID(σ_{ÁruID 67<>} (Szállít))) Szállítók)

1. szállítók, akik a 67-es ID-j árut szállítják: π_SzállID(σ_{ÁruID 67=} (Szállít)) ezek között azok is szerepelnek, akik a 67-es ID-j árun kívül még más árukat is szállítanak.

2. π_SzállID(σ_{ÁruID 67<>} (Szállít)) megadja azokat a szállítókat, akik a 67-esen kívül akármi más árut szállítanak. Ezek között a szállítók között szerepelnek azok:

• akik a 67-est és mást is szállítanak

• akik nem szállítják a 67-es árut, de szállítanak mást.

A különbség segítségével kiküszöböljük azokat a szállítókat, akik a 67- est és mást is szállítanak.

Azok, akik nem szállítják a 67-est, de mást igen a különbség eredményében nem fognak szerepelni.

Ebben azok a szállítók fognak szerepelni, akik csak a 67-est szállítják.

Lekérdezések optimalizálása

• minden ABKR-nek van lekérdezés−feldolgozó rendszere, mely a lekérdezést relációs algebrai m veletek sorozatává alakítja,

• egy lekérdezést több relációs algebrai kifejezéssé is alakíthatjuk, amelyek ugyanazt az eredményt adják, ezeket ekvivalens kifejezéseknek nevezzük,

• a lekérdezés optimalizáló feladata, hogy az ekvivalens kifejezések közül kiválassza a leggyorsabban kiértékelhet kifejezést,

• a relációs algebrai m veletek tulajdonságait felhasználva a kifejezéseket átalakíthatjuk.

Relációs algebrai m veletek algebrai tulajdonságai Ekvivalencia jele: ↔

R reláció sémája A={ , ,..., }A A_{1 2} A_n , S sémája B = {B1, B2, …, Bm}

T sémája C = {C1, C2, …, Ck}, ahol n, m, k N az attribútumok száma.

– Join kommutatív:

R S ↔ S R

– Bináris m veletek asszociatívak:

(R S T× × ↔ × ×) R S T( )

(R S ) T ↔ R ( S T )

– Unáris m veletek idempotensek:

Ha ugyanarra a relációra több vetítést alkalmazunk, ezeket csoportosíthatjuk, ha A^'⊆ A A, ^''⊆ A i A^'⊆ A^'', akkor:

'( ''( )) '( )

A A R A R

π π ↔ π

Ha több kiválasztást ( _{p A( )}

σ i i ) ugyanarra a relációra vonatkozik, ezeket csoportosíthatjuk, ahol p az _i A attribútumra alkalmazott _i feltétel:

1( )1 ( 2( 2)( )) 1( )1 2( 2)( )

p A p A R p A p A R

σ σ ↔σ _∧

- Vetítés és kiválasztás sorrendje felcserélhet :

1,..., _n( ( _p)( )) 1,..., _n ( ( _p)( 1,..., ,_{n p} ( )))

A A p A R A A p A A A A R

π σ ↔π σ π

• ha a vetítést a kiválasztás el tt akarjuk végrehajtani, akkor az A_p attribútumnak kell szerepelnie a vetítés attribútumai között.

• ha A_p { ,..., }A₁ A , akkor az utolsó vetítés az _n { ,..., }A₁ A _n attribútumokra jobb oldalon fölösleges.

– Kiválasztás és bináris m veletek sorrendje felcserélhet : (Emlékeztet : A az R reláció attribútuma). _i

( )_i ( ) ( ( )_i ( ))

p A R S p A R S

σ × ↔ σ ×

( )_i (

p A R

σ _{p A B( j, )k} S) ↔σ_{p A( )i} ( )R _{p A B( j, )k} S

– A kiválasztás és egyesítés sorrendje felcserélhet , ha az R és T relációk sémája ugyanaz:

( )_i ( ) ( )_i ( ) ( )_i ( )

p A R T p A R p A T

σ ∪ ↔σ ∪σ

- Vetítés és bináris m veletek sorrendje felcserélhet : Legyen A^'⊆ A, B^'⊆ B, C = A^'∪ B ^', akkor:

' '

( ) ( ) ( )

C R S A R B S

π

π

π

C(R

π

i j S ↔ π R _{p A B}( , )_{i j}

π

ahol '

Ai ∈ A és ' Bj ∈B .

( ) ( ) ( )

C R S C R C S

π

π

π

• A gyakorlatban a Descartes szorzatot nem célszer használni, mivel ez a legköltségesebb m velet.

• A természetes összekapcsolás is drága m velet, a gyakran használatosak közül a legdrágább.

• Az ABKR lekérdezés optimalizálója a join-t nem úgy végzi, hogy Descartes szorzatot elkészíti és abból kiválogatja az összepárosítható sorokat.

• Több algoritmus is létezik a join végrehajtására, egyik az ún.

merge-join, mely a közös attribútum szerint rendezett összekapcsolandó relációt egy új relációba fésüli össze.

„Keressük a ’Milka csoki’-t szállító cégek nevét.”

más megoldás:

C: π_SzállNév σ_ÁruNév='Milka csoki' Áruk) Szállít Szállítók)

• A relációs algebrai kifejezéseket kifejezésfával is megadhatjuk.

• Az el bbi relációs algebrai kifejezés kifejezésfája a következ ábrán látható.

• A lekérdezés végrehajtását, illetve optimalizálását lásd részletesebben a [MoUlWi00]-ben.

AruNev='Milka csoki'

σ

Szállítók

SzállNév

π

Áruk

Szállít