kategória

Biológia állatok Fizikai Földrajz Kémia Matematika Növénytan Számítógépes

Filozófia

Relaciós algebra, relaciós teljesség

matematika

egyéb tételek

Vizsga matek

Matematika A1 vizsga elméleti kérdések

Szamsorozatok és tulajdonsagaik (korlatossag, monotonitas, konvergencia), nevezetes szamsorozatok

Relaciós algebra, relaciós teljesség

Relációs algebra, relációs teljesség

1. Bevezetés

A praktikus alkalmazások szempontjából a relációs adatmodell a legfontosabb a modellek közül. Sikerének titka egyszerûsége, érthetõsége, és a hozzá kapcsolódó számos mûvelet. S bár kifejezõereje jó, hatékonysága hozzá képest alulmarad.

Alapja a síkbeli, kétdimenziós táblázat, a reláció. A reláció a táblákkal analóg, mert a kapcsolatokat ezek segítségével lehet leírni. A reláció elemei a sorok, a táblázat fejlécében pedig az attribútumok szerepelnek.

Példa: FILM

CÍM

ÉV

SZALAGFAJTA

= r rek.

Óz

Def.: Reláció

A reláció egy síkbeli tábla, ami pedig egy direkt szorzat egy részhalmaza, amelyben a sorok (rekordok) sorrendje lényegtelen. Felfogható úgy is, mint Attribútum -> Érték függvények halmaza, ahol az oszlopok (= attribútumok) sorrendje irreleváns.

A fenti példában:

FILM CÍM ÉV SZALAGFAJTA

r(CÍM)="Óz"

Def.: Nézet

. Szintén egy síkbeli táblázat:

R(A₁,A₂,...A_k)

A₁

A₂

A_k

. ~R D₁ D₂ D_k, ahol D_iaz A_iértékkészlete. (A sorok sorrendje nem számít.)

. A sor egy f ÈD_ifüggvény. (Az oszlopok sorrendje nem számít.)

2. A relációs adatmodell alapmûveletei (E.F. Codd, '70)

. halmazmûveletek

únió (Jele: È

Adott két reláció: R és S.

RÈS az R és S sorait jelenti.

A mûveltnek nincs mindig értelme, ezért megfogalmazhatunk - nem kötelezõ érvényû - követelményeket az únióval kapcsolatban:

legyen R és S oszlopszáma egyenlõ!

esetleg oszlopaik típusa is feleljen meg egymásnak!

Példa

A	B
a	a
a	c
b	c

A	D
a	a
a	d
a	c
b	b

RÈS

A
a	a
a	c
b	c
a	d
b	b

Ahogy a példában is látszik, elõfordulhat, hogy az únióban hiányozni fog egy attribútumnév (oszlopfejléc). Az ismétlõdõ sorok általában nem megengedettek (pl.: (a,a) ) az únióban, mivel a relációs világ értékorientált, és a redundanciát igyekszik kiiktatni ott, ahol lehet.

különbség (Jele: \)

Adott két reláció: R és S.

R\S elemei R azon sorai lesznek, amelyek nem szerepelnek S-ben.

R\S örökli az R oszlopszámát, attribútumait, típusait.

Példa: az úniónál bemutatott R-re és S-re

R\S

A	B
b	c

direkt szorzat (Descartes-szorzat, jele:

Adott két reláció: R (k oszlopa és m sora van) és S (l oszlopa és n sora van).

R S-nek (k+l) számú oszlopa lesz, amikor a direkt szorzat-képzés során R sorait kiegészítjük az S soraival az összes lehetséges módon. Tehát R S-nek m n számú sora lesz.

R S(A₁,...A_k,B₁,...,B_l)

Formálisan: R(A₁,...A_k)

S(B₁,...,B_l)

Példa: az úniónál bemutatott R-re és S-re k=l=2 k+l=4

R S

A	B	A'	D
a	a	a	a

		b	b
a	c	a	a

Az alapmûveletek közül ez a legnehezebb és leglassabb. Bár polinom idõben elvégezhetõ, mégis ez aleginkább idõigényes mûvelet.

. relációs mûveletek

szelekció (Jele: s_F(R)[1])

A szelekció egy adott R relációra és F formulára vonatkozik.

s_F(R) az R reláció azon sorait jelenti, amelyekre F formula igaz. Örökli a típusokat és attribútumokat.

F alakja (Codd eredeti javaslata szerint): AQB, AQc, cQA, ahol:

A és B attribútumnevek,

c egy konkrét érték,

Q pedig elemi összehasonlító operátorok halmaza: Q

Ezeket az F formulákat atomoknak nevezzük. Az atomok kombinálhatók a ØÙ jelekkel.

Példa s_A=D(S) s_(A=B) _(A_¹_b)(R)

A	D
a	a
b	b

A	B
a	a
a	c

A szelekció eredménye sosem egy elemi objektum, hanem általános esetben egy reláció, azaz sorok kollekciója.

vetítés (projekció) (Jele: P

A P_Ai1,...Ail(R) vetítés az R vetítését végzi el az A_i1,...A_iloszlopokra:

paramétere egy R reláció;

meg kell adni R biznoyos attribútumait is (A_i1,...A_il);

bizonyos oszlopokat elhagy a fenti R relációból;

és megváltoztatja az oszlopok sorrendjét.

Szemantikája egyszerû

1. vegyük az R A_i1,...A_iloszlopait ebben a sorrendben;

2. hagyjuk el R többi oszlopát;

3. hagyjuk el az esetleges ismétlõdéseket is.

Példa P_A(R)

A relációs alapmûveletek relációkat adnak eredményül, ezért ezen relációs mûveletek egymással kombinálhatók. Pl.: s_A<D(R S), ez elõször egy Descartes-szorzást, majd egy szelekciót jelöl.

3. A relációs adatmodell további fontos mûveletei

metszet (Jele:

Adott két reláció: R és S.

R S sorai azok a sorok lesznek, melyek R-nek és S-nek is sorai.

Formálisan: R S=R\(R\S)=S\(S\R)

Példa: az úniónál megismert R-re és S-re

R S

A	B
a	a
a	c

Az attribútumok öröklõdése itt kétféle lehet.

természetes illesztés (összekapcsolás, join) (Jele: )

Adott két reláció, R és S. Az természetes illesztés mûvelete bármely két halmazra értelmes operáció.

R S kiszámítása attól függ, hogy melyek a közös attribútumnevek a relációkban:

R(A₁,...A_k,B₁,...,B_s)

S(A₁,...A_k,C₁,...,C_d)

vagyis az A_i-k a közös attribútumnevek.

Az R S-bõl indulva vesszük azokat a sorokat, amelyekre igaz, hogy R.A_i=S.A_i.

Az eredményt vetítjük rá R.A₁,...,R.A_k,C₁,...,C_d,B₁,...,B_s-re.

Tulajdonságai

Az így kiadódó R S -nek (k+s+d) számú oszlopa lesz.

Örököl attribútumokat és típusokat is.

k=0 esetén egyszerû szorzatmûveletet jelent.

Kifejezhetõ alapmûveletekkel (a gyakorlatban igyekszünk másként megkapni az egyesítés eredményét): R S = P_{A1,...Ak,B1,...,Bs,C1,...,Cd} s_Ai=Ai'(R S)). A vetítésnél nem kell az azonos sorokat törölni.

Példa: k=1, s=2,d=1, (k+s+d)=4

A	B	C
a	b
a	c
b	c

R S

D	C
a
b
x

A	B	C	D
a	b		a
a	b		x
a	c		b

félillesztés (Jele: )

Technikai szerepe van a lekérdezési optimalizátorokban (elosztott rendszerekben).

R S = P_R(R S).

Általános (Q illesztés

Adott két reláció: R és S.

A az R, B az S reláció attribútuma.

R S jelentése: s_A_Q_B(R S)

^A^{Q B}

Ebben az esetben tehát nem egyenlõségre, hanem általános mûveletre végezzük el az illesztést.

Példa: R S

^R.C<S.C

A	B	R.C	D	S.C
a	b		b

Def.: Relációs teljesség

Egy relációs lekérdezõ nyelvet relációsan teljesenek nevezünk, ha benne az öt alapmûvelet (únió, különbség, direkt szorzat, szelekció, vetítés) megvalósítható. Az SQL relációsan teljes.

Egyes komoly lekérdezõ nyelvek ezen minimális követelményeket túl is teljesítik, azaz nem csak relációs, hanem aggregációs mûveletekre is képesek.

Def.: Aggregáció

Az összesítõ mûveleteket, melyek egy relációból elemi értéket állítanak elõ, aggregációknak nevezzük. Például.: AVG (átlag), MIN (minimum), MAX (maximum), CNT (számlálás), SUM (összegzés).

Példa: DOLGOZÓ(SzemélyiSzám, Fizetés,...)

F_CNT _{Szemszám,
AVG Fizetés}(DOLGOZÓ) eredménye egy számpár lesz. Megkapjuk a dolgozók számát és az átlagos fizetést.

4. NULL értékek problematikája

A NULL értékek kitöltetlen attribútum-értékeket jelentenek.

Például: TERMELÕ(Név,Cím,Termék,Ár)

(Rezeda Kázmér,NULL,Zab,300)

s_{Cím="Budapest"}(TERMELÕ)

A NULL érték jelentése azonban nem homogén. Jelentheti azt, hogy

létezik ugyan az attribútum-érték, de nem ismerjük (ez a megengedõ álláspont), vagy hogy

az érték nem létezik (ez a nem megengedõ álláspont).

Mûveletek NULL értékekkel

Baloldali külsõ illesztés (Jele: )