Informatika | Adatbázisok » Buza-Kis - Az adatbázisok hatása a relációs algebrára

Informatika a felsőoktatásban 2008 Debrecen, 2008. augusztus 27-29 AZ ADATBÁZISOK HATÁSA A RELÁCIÓS ALGEBRÁRA THE EFFECT OF THE DATABASES ON RELATIONAL ALGEBRA Buza Antal1, B. Kis Piroska2 1. Dunaújvárosi Főiskola, Informatikai Intézet, 2. Dunaújvárosi Főiskola, Matematikai Intézet Összefoglaló A relációs algebra hagyományosan négy műveletcsoport (halmazműveletek, szelekció és projekció, összekapcsolások, átnevezések) vizsgálatával foglalkozik. A megállapítható műveleti azonosságok hasznosak például akkor, amikor valamely, a felhasználó által kezdeményezett adatbázisművelet minél hatékonyabb végrehajtási tervét keresi az adatbázisrendszer. Az adatbázisok használata során egyre konkrétabban körvonalazódik, hogy a felhasználói igények kielégítése néhány további tipizálható művelet megvalósítását is igényli (rendezés, csoportképzés, összesítések, stb.) Ezen új műveletek bevezetése a relációs algebrába

lehetővé teszi a műveleti tulajdonságok tanulmányozását, új műveleti azonosságok megállapítását, segítve ezzel a hatékonyabb adatbázisrendszerek kialakítását. Az előadásban az új műveleteket és néhány tulajdonságukat mutatjuk be. Kulcsszavak Relációs algebra, adatbázis Abstract Relational algebra uses four groups of operations (the set operations, the selection and projection, the different kinds of join, and the rename) traditionally. There are several operational identities which are very helpful in the query optimization process of database systems. The experience of practical use of databases showed that the expansion of classical relational algebra is required. The new operations are: sorting, grouping, aggregations, extension of projection, and extension of join. Several operational identities are found in the expanded relational algebra Based on this knowledge we are able to growing the effectiveness of database systems. This is an remarkable

retroactivity from practice to development of the theory. Keywords Relational algebra, Database 1 Informatika a felsőoktatásban 2008 1. Debrecen, 2008. augusztus 27-29 Bevezetés A tudományok fejlődését jelentős mértékben ösztönzi a gyakorlatban felvetődő problémák megoldásának keresése. A fejlődés mozgató ereje lehet ezen túl a szellemi alkotás érdekessége, szépsége is – ez leginkább talán a matematika fejlődésében megjelenő további motívum. Az algebra a matematika területéhez tartozik, így annak részeként a relációs algebra is ide sorolható. Ugyanakkor a relációs algebra egy alkalmazott matematikai diszciplínának is tekinthető, amelynek fő alkalmazási területét az informatikai tudományok képezik. A relációs algebrán is megfigyelhető a gyakorlati igények által generált változás, fejlődés. A relációs algebra legfőbb alkalmazási területe a relációs adatbázisok tervezése és megvalósítása. E cikk a

relációs algebra gyakorlat által gerjesztett változásait igyekszik bemutatni. 2. Az „eredeti” relációs algebra A relációs algebra alapművei közé tartoznak Codd 1970-ben és 1972-ben publikált munkái [1], [2]. Ezekhez igazodóan általánosan elfogadottá vált az, hogy mely műveletek tekintendők a relációs algebra műveleteinek, s ezeket négy csoportba sorolták. Így például Ullman és Widom 1997-ben megjelent „A First Coures in Database Systems” című könyvében is megtaláljuk ezt a csoportosítást, nevezetesen a négy műveletcsoport: 1) 2) 3) 4) Halmazműveletek (, , -). Szelekció és projekció (, ). Összekapcsolások (,⋈, ⋈ C ,). Átnevezés (). Más szerzőknél elvétve még megjelenik az osztás () művelet is. A relációkat az általánosan megszokott táblázatos formájúnak tekintve, a továbbiakban a relációk soraira és oszlopaira fogunk hivatkozni, valamint a reláció és a táblázat megnevezéseket is

azonos értelemben használjuk. Ezek a műveletek a relációk jellemzőihez igazodva semmilyen kikötést nem tartalmaznak a relációk sorai sorrendjére, de lényegében oszlopai sorrendjére sem. Ez „elméleti” megközelítésben teljesen elfogadható, hiszen az egyik fő elvárás az adatbázisokkal kapcsolatban az, hogy a valóságot hűen ábrázolják. Ha például egy hallgatói adatbázisra gondolunk, akkor az, hogy abban a hallgatók milyen sorrendben szerepelnek (sorok sorrendje), illetve az, hogy egy hallgató adatai milyen sorrendben (oszlopok sorrendje) fordulnak elő valóban teljesen lényegtelen, hiszen az adatbázis ilyen kikötés nélkül is helyesen tükrözheti a valóságot. Ezek a műveletek elegendőek arra, hogy sokféle lekérdezést leírjunk velük (a kifejező erőről Codd értekezik az 1972-ben megjelent cikkében[2]), a lekérdezéseket „felhasználva” kifejezzünk a megszorításokat, és megállapíthatunk számos műveleti azonosságot. A

műveleti azonosságok birtokában az adatbázisrendszer megteheti azt, hogy egy adott műveletsort nem a felhasználó által megfogalmazott formában, hanem azzal ekvivalens, de kevesebb elemi műveletet igénylő formában hajt végre, ezzel esetenként jelentősen csökkenti a feladat elvégzésének időszükségletét. Az ilyen „optimalizálással” Garcia-Molina et al „Database System Implementation” című, 2000-ben megjelent könyvükben részletesen foglalkoznak[3]. 2 Informatika a felsőoktatásban 2008 Debrecen, 2008. augusztus 27-29 Az a tény, hogy relációk soraira és oszlopaira vonatkozóan nincsenek megkötések, elméleti szempontból elfogadható, az adatbázisrendszer megvalósítása szempontjából pedig kimondottan előnyös, hiszen a nem létező előírásokat nem kell betartaniuk, a működésük ezzel is gyorsabbá tehető. A kikötések hiánya ugyanakkor a felhasználás igényeinek sokszor nem felel meg. Gondoljunk például egy sehogy sem

rendezett telefonkönyvre Abban lehet, hogy sok hasznos információ van, de emberi felhasználásra alkalmatlan. Megállapíthatjuk, hogy a gyakorlat megfogalmazott olyan igényeket, amelyek kielégítésére a korábban definiált relációalgebrai műveletek nem elegendőek. 3. A relációs algebra kibővítése Ullman és Widom már [4]-ben foglalkoztak a relációs modell kiterjesztésével, bár még nem formalizáltan, de írtak a módosítások, összesítések és nézetek szükségességéről, azonban a rendezésről például csak közvetetten. Az ugyanolyan című, de jelentősen átdolgozott, öt évvel későbbi, a 2002-ben megjelent kiadásban [5] már önálló fejezetet szentelnek a multihalmazokon értelmezett műveleteknek és a relációalgebra további műveleteiként bevezetik a következőket: 1) 2) 3) 4) 5) Duplikátum-kiküszöbölő művelet ( ). Összesítő műveletek (SUM, MIN, MAX, COUNT, AVG). Csoportképzés ( ). Rendezés (). Kibővített

projekció (). 6) Külső összekapcsolások (⋈̊ R ,). A multihalmazok kezelése is gyakorlati igény (néhány számítás, mint például az átlag eredményét félrevezetővé tenné, ha nem engednénk meg a multihalmazok kezelését), az „új” műveletekről pedig jól érzékelhető, hogy az SQL „visszahatásaként” keletkeztek. Duplikátum kiküszöbölése Legyen R egy reláció. Ha erre a relációra alkalmazzuk a  -val jelölt duplikátumkiküszöbölő műveletet, akkor eredménye, a (R) az R relációban egyszeresen vagy többszörösen előfordult sorok egy-egy példányából álló reláció lesz. Összesítő műveletek Az SQL szabvány(ok) öt összesítő műveletének (SUM, MIN, MAX, COUNT, AVG) megfelelő műveletek. Az SQL-hez hasonlóan a csoportképzéssel kombinált a hatásuk, azaz csoportonként működnek, ha vannak csoportok, különben a teljes relációt egy csoportnak tekintik. 3 Informatika a felsőoktatásban 2008 Debrecen,

2008. augusztus 27-29 Csoportképzés A  csoportképző operátor indexe egy L lista. A lista elemei az alábbiak lehetnek:   Az R reláció olyan attribútuma, mely szerepet játszik  csoportképzésben. Ez az attribútum azon attribútumok egyike, mely (értékei) szerint R reláció sorait csoportosítjuk. A lista ilyen elemeit csoportosító attribútumoknak nevezzük A reláció valamely attribútumára alkalmazandó összesítő művelet. Az eredményrelációban az összesítéssel keletkezett oszlopoknak nevet is adhatunk, amelyet itt nyíllal és az új névvel adunk meg. Az ilyen attribútumokat összesített attribútumoknak nevezzük. A  L (R) kifejezés eredményrelációját a következőképpen állítjuk elő:  R sorait csoportosítjuk. Egy-egy csoportba az összes olyan sorok tartoznak, melyek az L listában megadott csoportosító attribútumokon azonos értéket tartalmaznak. (Attribútumonként külön-külön) Ha nem adunk meg csoportosító

attribútumokat, akkor a teljes R relációt egyetlen csoportnak tekintjük.  Minden csoporthoz képezünk egy sort az eredmény relációban. Ez a sor a következőkből áll: - A csoportosító attribútumok adott csoporthoz tartozó értékei és - A csoportra vonatkozóan az L listában felsorolt összesített attribútumokhoz tartozó összesítések eredményei. Például ha a H reláció a hallgatók adatait tartalmazza, a szak, az évfolyam, az atl attribútumok rendre a szak azonosítója, az évfolyam azonosítója, és a hallgató tanulmányi átlaga, akkor  szak ,évfolyam, AVG(atl) átlag (H) eredménye egy háromoszlopos reláció, szakonként és évfolyamonként azok azonosítóival és az évfolyamátlagokkal. Feltettük, hogy az évfolyamátlag a hallgatók átlagaiból képzett átlag Rendezés Ha R egy reláció, L pedig R attribútumai listája, akkor a  L (R) kifejezés egy R-rel megegyező reláció, de a sorai L által meghatározott

sorrendben felsoroltak. Ha L az A 1 , A 2 , A n lista, akkor R sorai elsődlegesen A 1 attribútum értékei szerint rendezettek. Az A 1 attribútum értékei szerint azonos sorok A 2 attribútum értékei szerint rendezettek, és így tovább. Az A 1 , A 2 , A n szerint megegyező sorok sorrendje bizonytalan, esetleges A  művelet eltér a relációs algebránk többi műveletétől abban, hogy  az egyetlen olyan művelet, melynek eredménye sorok listája, nem pedig sorok halmaza. Így a lekérdezések eredményére a  műveletnek csak akkor van hatása, ha  az utolsó művelet. Ha a rendezést követően a relációs algebra más műveletét is végrehajtjuk, akkor az a művelet a rendezés eredményét halmaznak, vagy multihalmaznak tekinti, nem törődve a rendezettségével (tehát elronthatja a rendezést). 4 Informatika a felsőoktatásban 2008 Debrecen, 2008. augusztus 27-29 A projekció (vetítés) kibővítése A klasszikus relációs algebrában

bevezetett L(R) műveletben L az R attribútumai (egy részének) listája. A vetítés művelet kiterjesztése lehetővé teszi a sorokból kiszámított értékeknek az eredmény komponenseként való megjelenítését. A kiterjesztett vetítést is L(R) -rel jelöljük, ahol az L vetítési lista a következő elemekből áll:    R egyszerű attribútuma. Egy x  y alakú kifejezés, ahol x és y attribútumnevek. Az L lista x  y alakú eleme azt jelenti, hogy az R x attribútumát átnevezzük y-ra, tehát az eredményreláció sémájában ezen attribútum neve y lesz. Egy E  z alakú kifejezés, ahol E az R attribútumaiból, konstansokból, aritmetikai műveletekből, karakteres műveletekből álló kifejezés, z pedig az E kifejezés kiszámított értékének új attribútumneve. Például az a+b  x listaelem az eredményben x attribútum megjelenését írja elő, melynek tartalma a és b összege. A c||d  e listaelem az eredményben e

attribútum megjelenését írja elő, melynek tartalma c és d (karakteres értékűnek tekintett) összekapcsoltja (konkatenáltja). A vetítés eredményét R összes soraiból képezzük. Az L lista kiértékelésekor a hivatkozott attribútumértékeket a sor megfelelő komponenseivel helyettesítjük, és elvégezzük velük a kijelölt műveleteket. A vetítés eredménye reláció, melynek sémája az L listából – esetenként átnevezéssel – képzett attribútumnevek. R mindegyik sorából képződik egy sor az eredmény relációban. R duplikált soraiból az eredményben is duplikált sorok képződnek, de az eredményben akkor is keletkezhetnek duplikált sorok, ha R-ben nem voltak duplikátumok. Két példa a (kibővített) projekcióra: Megjegyzés: A  művelet technikai értelemben felesleges. Ha R(A 1 ,A 2 ,A n ) egy reláció, akkor (R) ekvivalens  A , A ,. A ( R ) -rel, az pedig ekvivalens  A , A , A ( R ) -rel 1 2 n 1 2 n Külső

összekapcsolások Az összekapcsolás művelet tulajdonsága, hogy előfordulhatnak nem kapcsolható, „lógó” sorok is. Ezek azok a sorok, melyekhez a másik relációban nem találunk egyetlen olyan sort sem, amely a kapcsolási feltételt kielégítené. A lógó soroknak az összekacsolás eredményében semmi nyomuk, így előfordulhat, hogy a kapcsolás nem reprezentálja az eredeti relációk összes adatát. Az olyan esetekben, amikor ez a viselkedés számunkra nem alkalmas, akkor az összekapcsolás – kereskedelmi rendszerekben megjelenő – „külső összekacsolás”-nak nevezett változatait használhatjuk. 5 Informatika a felsőoktatásban 2008 Debrecen, 2008. augusztus 27-29 Először a természetes összekapcsolás eseteit vizsgáljuk, melyben tehát a kapcsolási feltétel a két kapcsolandó reláció közös attribútumain az attribútumértékek azonossága. Az R⋈̊S külső összekapcsolás az R⋈S összekapcsolás soraival kezdődik, amit még

kibővítünk a mind az R -ből, mind az S-ből származó lógó (nem kapcsolható) sorokkal. Az így keletkezett sorok nem minden attribútumát tudjuk feltölteni. Az olyan attribútumok, amelyeket nincs mivel feltölteni, null értéket kapnak. Az alapnak tekintett (természetes) külső összekapcsolásnak számos variánsa létezik. Az R⋈̊ L S bal oldali külső összekapcsolás a külső összekapcsoláshoz hasonló, de a lógó sorok közül csak a bal oldali (R) táblából származókat tartalmazza. Az R⋈̊ R S jobb oldali külső összekapcsolás a külső összekapcsoláshoz hasonló, de a lógó sorok közül csak a jobb oldali (S) táblából származókat tartalmazza. Mindhárom természetes külső összekapcsolásnak megvan a feltételes összekapcsolás megfelelője, mely a kapcsolási feltételnek megfelelően összekapcsolt sorokkal kezdődik, majd a másik táblából a kapcsolási feltétel szerint egyetlen sorral sem kapcsolható lógó sorok következnek. A

C feltétellel megadott külső feltételes összekapcsolás jelölésére a ⋈̊ C jelet használjuk. Ez a művelet is módosítható L -lel vagy R -rel, jelezvén, a bal vagy a jobb oldali külső feltételes összekapcsolást. 4. A relációs algebra további bővítéséről Az SQL további, relációkra vonatkozó műveletei A kibővítés után az SQL jelenlegi változatának lekérdezési lehetőségeit a relációs algebra műveletei is jól leírják. Ezekkel felállíthatók műveleti azonosságok, melyeket a lekérdezés optimalizálásában hasznosítunk. A gyakorlat igényeinek megfelelően az SQL-ben vannak utasítások az adatok módosítására, új sorok beszúrására, és sorok törlésére. Ezeknek is megfeleltethetnénk relációalgebrai műveleteket, de úgy tűnik, hogy ilyen megfeleltetésnek nincs akkora gyakorlati haszna, jelentősége, mint amekkora a lekérdezéssel kapcsolatosaknak van. A módosítás és a törlés végrehajtási idejének legnagyobb

részét azon sorok megkeresése teszi ki, amelyekre a művelet vonatkozik, ez pedig lekérdezés. A már megtalált sor törlése, illetve módosítása az adatbázisrendszer olyan beépített technikai tevékenysége, amin relációs algebrai meggondolások aligha tudnak érdemben segíteni. Hasonlóan, az új sor beszúrásához is leginkább annak tárolási helyét kell megállapítani, de kihasználva, hogy a sorok sorrendjére általában semmi megkötés nincs, ez is olyan feladat, ami sokkal inkább technikai, mint relációs algebrai meggondolásokat kíván. Következtetésként levonható, hogy a „klasszikus” relációs adatbázisok máig használt tipikus műveletei feltehetően nem igénylik a relációs algebrák további bővítését. A klasszikus relációs adatbázismodellen túl A relációs modell kereteinek tágításai – például a beágyazott, rétegzett relációk alkalmazása, vagy az objektum-relációs modell, és más bővítési meggondolások –

kivezethetnek a relációs algebra már bővített változatából is. Az, hogy ezen adatbázismodellek a gyakorlatban mennyire válnak be, és hogy igénylik-e a relációs algebrának valamilyen további bővítését, az a különböző modellek szerint, külön-külön 6 Informatika a felsőoktatásban 2008 Debrecen, 2008. augusztus 27-29 vizsgálandó meg. Általánosítható, egységes séma még nem látszik körvonalazódni, meglehet azonban, hogy majd letisztul újabb adatbázismodell is. Irodalomjegyzék [1] Codd E. F (1970) A relational model for large shared data banks, Comm ACM 13:6, 377-387. [2] Codd E. F (1972) Relational completeness of database sublanguages, Database Systems, Prentice Hall, Engelwood Cliffs, NJ. [3] Garcia-Molina H., Ullman J D, Widom J (2000) Database System Implementation, Prentice Hall [4] Ullman J. D, Widom J (1997) A First Coures in Database Systems (first edition) Prentice Hall [5] Ullman J. D, Widom J (2002) A First Coures in

Database Systems (second edition) Prentice Hall [6] Ullman J. D, Widom J (2008) A First Coures in Database Systems (third edition) Prentice Hall 7