DKOD DNEV FIZETES FOGLALKOZAS BELEPES OAZON --------------------------------------------------- 1 SMITH 800 CLERK 1980 20 2 ALLEN 1600 SALESMAN 1981 30 3 WARD 1250 SALESMAN 1981 30 4 JONES 2975 MANAGER 1981 20 5 MARTIN 1250 SALESMAN 1981 30 6 BLAKE 2850 MANAGER 1981 30 7 CLARK 2450 MANAGER 1981 10 8 SCOTT 3000 ANALYST 1982 20 9 KING 5000 PRESIDENT 1981 10 10 TURNER 1500 SALESMAN 1981 30 11 ADAMS 1100 CLERK 1983 20 12 JAMES 950 CLERK 1981 30 13 FORD 3000 ANALYST 1981 20 14 MILLER 1300 CLERK 1982 10 Tegyük fel, hogy a FOGLALKOZAS, a BELEPES és az OAZON oszlopokra létezik bitmap index (3 index). Készítsük el az alábbi lekérdezésekhez szükséges bitvektorokat, majd végezzük el rajtuk a szükséges műveleteket, és adjuk meg azt az előállt bitvektort, ami alapján a végeredmény sorok megkaphatók. Ellenőrzésképpen adjuk meg a lekérdezést SQL-ben is. - Adjuk meg azoknak a dolgozóknak a nevét, akik 1981-ben léptek be és a foglalkozásuk hivatalnok (CLERK), vagy a 20-as osztályon dolgoznak és a foglalkozásuk MANAGER. belepes 1981: 01111110110110 oazon 20: 10010001001010 and and foglalkozas clerk: 10000000001101 foglalkozas manager: 00010110000000 -------------------- ------------------ 00000000000100 00010000000000 00000000000100 or 00010000000000 ----------------- 00010000000100 4. JONES, 12. JAMES select dnev from dolg where belepes=1981 and foglalkozas='CLERK' or oazon=20 and foglalkozas='MANAGER'; - Adjuk meg azoknak a dolgozóknak a nevét, akik nem 1981-ben léptek be és a 10-es vagy a 30-as osztályon dolgoznak. belepes 1981: 01111110110110 oazon 10: 00000010100001 or belepes nem 1981: not 01111110110110 oazon 30: 01101100010100 ------------------ ------------------ 10000001001001 01101110110101 10000001001001 and 01101110110101 ------------------ 00000000000001 14. MILLER select dnev from dolg where belepes!=1981 and (oazon=10 or oazon=20); Tegyük fel, hogy a dolgozó tábla sorai egyenként 1 blokkot foglalnak el, és a memóriánk 4 blokknyi. Rendezzük a tábla sorait fizetés szerint egy rendezés alapú algoritmussal. Adjuk meg az első menet után a rendezett részlistákat (elég a dnev, fizetest megadni). Hány menetes algoritmusra lesz szükségünk? 1. menet: DKOD DNEV FIZETES FOGLALKOZAS BELEPES OAZON DKOD DNEV FIZETES FOGLALKOZAS BELEPES OAZON --------------------------------------------------- --------------------------------------------------- 1 SMITH 800 CLERK 1980 20 1 SMITH 800 CLERK 1980 20 2 ALLEN 1600 SALESMAN 1981 30 3 WARD 1250 SALESMAN 1981 30 3 WARD 1250 SALESMAN 1981 30 2 ALLEN 1600 SALESMAN 1981 30 4 JONES 2975 MANAGER 1981 20 4 JONES 2975 MANAGER 1981 20 --------------------------------------------------- --------------------------------------------------- 5 MARTIN 1250 SALESMAN 1981 30 5 MARTIN 1250 SALESMAN 1981 30 6 BLAKE 2850 MANAGER 1981 30 7 CLARK 2450 MANAGER 1981 10 7 CLARK 2450 MANAGER 1981 10 6 BLAKE 2850 MANAGER 1981 30 8 SCOTT 3000 ANALYST 1982 20 8 SCOTT 3000 ANALYST 1982 20 --------------------------------------------------- --------------------------------------------------- 9 KING 5000 PRESIDENT 1981 10 12 JAMES 950 CLERK 1981 30 10 TURNER 1500 SALESMAN 1981 30 11 ADAMS 1100 CLERK 1983 20 11 ADAMS 1100 CLERK 1983 20 10 TURNER 1500 SALESMAN 1981 30 12 JAMES 950 CLERK 1981 30 9 KING 5000 PRESIDENT 1981 10 --------------------------------------------------- --------------------------------------------------- 13 FORD 3000 ANALYST 1981 20 14 MILLER 1300 CLERK 1982 10 14 MILLER 1300 CLERK 1982 10 13 FORD 3000 ANALYST 1981 20 2. menet osszefuzes 1--------------- első részlista első blokkja \ 1 fizetésre rendezett tábla dkod oszlopa 3 ------------ második részlista első blokkja \ amelyik első blokk következik \ 12 2 | --------- harmadik részlista első blokkja / az kiíródik és a mutató a > 11 4 | | ------ megyedik részlista első blokkja / blokk következő elemére mutat / 3 | | | 5 5---- | | 14 7 | | 10 6 | | 2 8 | | 7 | | 6 12------ | 4 11 | 8 10 | 13 9 | 9 | 14--------- 13 Tegyük most fel, hogy a memóriánk 6 blokknyi és van még egy vásárlás tábla, aminek a szerkezete a következő: VASARLAS(dkod, cikk, mennyiseg, ar). Ennek a táblának a sorai is 1 blokkot foglalnak és a tábla kb. 120 sorból áll. Mennyi a műveletigénye egy hash alapú, egy rendezés alapú és egy beágyazott ciklusos algoritmusnak, ami arra válaszol, hogy az egyes dolgozók összesen mennyit költöttek? Feltehetjük, hogy az összegeket gyűjtő számlálók még beférnek a memóriába a blokkok mellett. Írjuk le röviden, hogy az egyes algoritmusok hogyan fognak működni. Adjuk meg a kosarakat a hasítás alapú algoritmus első menete után. Nested Loops (egymásba ágyazott ciklusok) 1*14+3*120=374 (vagy 1*120+24*14=456, ha a nagyobb a külső ciklus) Hash Join (Hash illesztés) 3*14+3*120=402 (kétmenetes algoritmussal) Sort Merge (rendezés alapú) 5*14+5*120=670 (a harmadik menetben már befér az 1+4 rendezett futam) M=6 B(DOLG)=14 B(VAS)=120 B(DOLG) beolvasás+kiírás, a végeredményt már nem írjuk ki. MŰVELETIGÉNY=5*B(DOLG)+7*B(VAS)=5*14+7*120=910 Beágyazott ciklusos algoritmus: _______________________________ A kisebbik (DOLGOZO) táblából M-1 (=5) sort sort olvassunk be a memóriába. A fennmaradó 1 blokkba a másik tábla sorait olvassuk be egyenként, majd összekapcsoljuk őket. Ez után beolvassuk a következő 5 sort a kisebbik táblából és a fennmaradó 1 blokkba ismét a másik tábla sorait olvassuk be egyenként, majd összekapcsoljuk őket. Végül a fennmaradó 4 sort olvassuk be a kisebbik táblából és a fennmaradó 1 blokkba ismét a másik tábla sorait olvassuk be egyenként, majd összekapcsoljuk őket. MŰVELETIGÉNY=1*B(DOLG)+(B(DOLG)/(M-1))*B(VAS)=1*14+(14/5)*120 =14+360=374 (14/5=3)