11.gyak. Rekurzió Datalogban, SQL3-ban és PL/SQL-ben
Adatbázis-sématervezés: E/K diagram leképezése relációkra

 
-- A gyakorlat táblás része: Lekérdezések logikai lekérdező nyelven: 
> E5. Rekurzív monoton (negáció nélküli) Datalog
> E6. Rekurzió az SQL3-ban WITH RECURSIVE utasítás
   
--  A gyakorlat gépes része
> 2.5. Hierarchikus lekérdezések (CONNECT BY PRIOR)
> 2.6. Az "Eljut feladat" Oracle hierarchikus lekérdezéssel
> 3.7. Az "Eljut feladat" rekurzív lekérdezések Oracle PL/SQL-ben
   
-- Köv.héten: II.ZH 
      
E5. Rekurzív monoton (negáció nélküli) Datalog
   
Tankönyvben:  
- Datalog: [Ullman-Widom]  5.3-5.4. Datalog szabályok és lekérdezések
- Rekurzió: [Ullman-Widom] 10.2. Rekurzió az SQL-ben (466-474.o.)
   
Az Eljut feladat:
- Az alábbi feladat a tankönyv (Ullman-Widom kék könyv) 10.2 szakaszára épül.
  Jaratok(legitarsasag, honnan, hova, koltseg, indulas, erkezes)
  táblában repülőjáratok adatait tároljuk. Azt keressük, hogy Dallasból mely városokba
  tudunk eljutni (átszállás nélkül közvetlenül vagy egy vagy több átszállással).
- (Papíros feladat) Fejezzük ki Datalog programmal, hogy mely (x,y) város párokra
   lehetséges közvetlenül, egy vagy több átszállással eljutni x városból y városba?
- Megoldás:
   1.    Eljut(x, y)<- Jaratok(l, x, y, k, f, e)
   2.    Eljut(x, y) <- Eljut(x, z) AND Jaratok(l, z, y, k, f, e)
         
E6. Rekurzió SQL3 szabványban WITH RECURSIVE
   
Tankönyvben:  
- Rekurzió: [Ullman-Widom] 10.2. Rekurzió az SQL-ben (466-474.o.)
   
Az Eljut feladat:
- Az alábbi feladat a tankönyv (Ullman-Widom kék könyv) 10.2 szakaszára épül.
  Jaratok(legitarsasag, honnan, hova, koltseg, indulas, erkezes)
  táblában repülőjáratok adatait tároljuk. Azt keressük, hogy Dallasból mely városokba
  tudunk eljutni (átszállás nélkül közvetlenül vagy egy vagy több átszállással).
- (Papíros feladat) Fejezzük ki az SQL3 szabványban szereplő WITH RECURSIVE
   utasítással, hogy mely (x,y) város párokra lehetséges közvetlenül, egy vagy több
   átszállással eljutni x városból y városba? ! (Csak papíron! Oracle nem támogatja).
- Megoldás:
            WITH RECURSIVE eljut AS
                  (SELECT honnan, hova FROM jaratok
             UNION
                  SELECT eljut.honnan, jaratok.hova
                  FROM eljut, jaratok
                  WHERE eljut.hova = jaratok.honnan)
            SELECT hova FROM eljut WHERE honnan='DAL';
   

2.5. Hierarchikus lekérdezések az Oracle-ben (CONNECT BY PRIOR)
      Családfák. SFW START WITH ... CONNECT BY PRIOR ...
 
Segédanyagok:
>> Oracle: Hierarchikus lekérd.pdf  (jelszavas anyag) példáit próbáljuk ki az Oracle-ben!
     -- ehhez a HR séma tábláihoz készítsük el a szinonimákat create_synonym
>> hiera_lekerd.txt (Nikovits Tibor) valamint AB1_Hierarchikus.pdf (Kiss Attila)
    
Feladatok a hierarchikus lekérdezésekhez
- Táblák és feladatok:  dolgozo_tabla.txt  Ehhez a táblák létrehozása:  create_dolgozo.txt
- Listázzuk ki az dolgozo tábla alapján a főnökökhöz tartozó beosztottak nevét és osztályukat.
   a.) A dolgozo tábla önamagára való hivatkozásával (többtáblás lekérdezés sorváltozókkal).
   b.) A CONNECT BY utasításrész használatával, a hierarchikus szerkezetet 'KING'-től
        felülről lefelé bejárva.
   c.)  Alulról felfelé járjuk be a hierarchikus szerkezet egy ágát 'SMITH'-től kezdve.
   
Megj: Példatár 3.fejezet elméleti összefoglalóban "Hierarchikus adatszerkezet megjelenítése"
     

2.6. Az Eljut feladat Oracle hierarchikus lekérdezéssel
- Hierarchikus lekérdezések az Oracle-ben (CONNECT BY PRIOR)
    
- Az Eljut feladat:  Jaratok(legitarsasag, honnan, hova, koltseg, indulas, erkezes)
  táblában repülőjáratok adatait tároljuk. Azt keressük, hogy Dallasból mely városokba
  tudunk eljutni (átszállás nélkül közvetlenül vagy egy vagy több átszállással).
- Készítsünk ebből saját példányt: jaratok_tabla.txt és az alapján dolgozzunk
            DROP TABLE jaratok;
            CREATE TABLE jaratok(
                            legitarsasag CHAR(2),
                            honnan VARCHAR2(10),
                            hova VARCHAR2(10),
                            koltseg NUMBER,
                            felszallas NUMBER,
                            erkezes NUMBER);
      
            INSERT INTO jaratok VALUES('UA', 'SF','DEN', 1000, 930,1230);
            INSERT INTO jaratok VALUES('AA', 'SF','DAL', 10000, 900,1430);
            INSERT INTO jaratok VALUES('UA','DEN','CHI', 500, 1500,1800);
            INSERT INTO jaratok VALUES('AA','DEN','DAL', 2000, 1400,1700);
            INSERT INTO jaratok VALUES('AA','DAL','CHI', 600, 1530,1730);
            INSERT INTO jaratok VALUES('AA','DAL', 'NY', 2000, 1500,1930);
            INSERT INTO jaratok VALUES('AA','CHI', 'NY', 3000, 1900,2200);
            INSERT INTO jaratok VALUES('UA','CHI', 'NY', 2000, 1830,2130);
   
- Oracle hierarchikus lekérdezések CONNECT BY PRIOR,
   Amennyiben azt szeretnénk megtudni, hogy mely városokba lehet eljutni Dallasból
   ezt a következő hierarchikus lekérdezéssel kapjuk meg ('DAL'='Dallas')
            SELECT DISTINCT hova
            FROM jaratok
            WHERE HOVA <> 'DAL'
            START WITH honnan = 'DAL'
            CONNECT BY PRIOR hova = honnan;

- Most szúrjunk be még egy sort, ami után már irányított kör is lesz a táblában:
            INSERT INTO jaratok VALUES('LH', 'CHI', 'DEN', 2000, 1900, 2100);
   Ekkor a fenti hierarchikus lekérdezés nem működik, viszont NOCYCLE-lel igen:
            SELECT DISTINCT hova
            FROM jaratok
            WHERE HOVA <> 'DAL'
            START WITH honnan = 'DAL'
            CONNECT BY NOCYCLE PRIOR hova = honnan;
 
- Átszállásokkal mely városokba lehet eljutni San Franciscoból ('SF'='San Francisco')
            SELECT LPAD(' ', 4*level) ||honnan, hova, level-1 Atszallasok
            FROM jaratok
            WHERE HOVA <> 'SF'
            START WITH honnan = 'SF'
            CONNECT BY NOCYCLE PRIOR hova = honnan;
   
- A hierarchikus lekérdezésben további pszeudo oszlopokat is használhatunk, amint
   azt az alábbi példában láthatjuk az útvonal megadását
           SELECT hova, sys_connect_by_path(honnan||'->'||hova, '/'),
                          connect_by_isleaf, connect_by_iscycle
           FROM jaratok
           START WITH honnan = 'SF'
           CONNECT BY NOCYCLE PRIOR hova = honnan;
   
- Mely (x, y) várospárokra lehetséges egy vagy több átszállással eljutni x városból y városba?
   Ezt PL/SQL programmal fogjuk Oracle-ben megoldani (folytatjuk, lásd 3.7. Rek.PL/SQL)
   

3.7. Az "Eljut feladat" PL/SQL-ben (ez előadás tananyag is!)
       
Rek1.feladat: Segédanyag, lásd az előadás anyagát >> Rekurzió-PSM-ben.pdf
- Az alábbi feladat a Tankönyv (Ullman-Widom kék könyv) 10.2 szakaszára épül.
   Jaratok(legitarsasag, honnan, hova, koltseg, indulas, erkezes)
   táblában repülőjáratok adatait tároljuk. A tábla létrehozása, lásd jaratok_tabla.txt
- Az alapfeladat, hogy adjuk meg mely (x, y) várospárokra lehetséges egy vagy több
   átszállással eljutni x városból y városba? Ezt egy relációs algebrai kifejezésként
   nem tudjuk megadni zárt alakban, klasszikus SQL SELECT utasítással sem tudjuk
   kifejezni, csak azt tudjuk, hogy átszállás nélkül, egy átszállással, két átszállással, stb...
    select distinct honnan, hova
       from jaratok

    union
    select j1.honnan, j2.hova
       from jaratok j1, jaratok j2

       where j1.hova=j2.honnan
    union
    select j1.honnan, j3.hova
       from jaratok j1, jaratok j2, jaratok j3

       where j1.hova=j2.honnan
       and j2.hova=j3.honnan 

    -- union stb... de ez nem rel.alg.kif.
      
Emlékeztető, ezért vezették be az SQL3 szabványban a WITH RECURSIVE
   rekurzív lekérdezéseket, lásd fent  #E6. Rekurzió SQL3 szabványban
- (Papíros feladat) Fejezzzük ki Datalog programmal, hogy mely (x,y) város
   párokra lehetséges egy vagy több átszállással eljutni x városból y városba?
- Megoldás-1:
   1.    Eljut(x, y) <- Jaratok(_, x, y, _, _, _)
   2.    Eljut(x, y) <- Eljut(x, z) AND Eljut(z, y)
- Ezzel a Datalog programmal az a probléma, hogy nem lineáris, nem tudjuk
   átírni az SQL3 szabványban szereplő WITH RECURSIVE utasításra.
- Megoldás-2:
   1.    Eljut(x, y) <- Jaratok(_, x, y, _, _, _)
   2.    Eljut(x, y) <- Eljut(x, z) AND Jaratok(_, z, y, _, _, _)
- Ez a Datalog program már rendben van, monoton (nem szerepel benne negáció)
   és lineáris (az értékadás kifejezésben egyetlen rekurzív relációt használunk).
   
- (Papíros feladat) A fenti nemnegált lineáris rekurzív Datalog programot írjuk át
   az SQL3 szabványban szereplő WITH RECURSIVE rekurzív lekérdezéssé!
   (Az SQL-99 szabvány csak az ún. monoton és lineáris rekurziót támogatja)
- Megoldás: (csak papíron, mert az Oracle még nem támogatja)
    WITH RECURSIVE eljut AS
         (SELECT honnan, hova FROM jaratok
         UNION 
          SELECT eljut.honnan, jaratok.hova
          FROM eljut, jaratok
          WHERE eljut.hova = jaratok.honnan)
    SELECT * FROM eljut;
- Fontos: UNION (halmaz) és UNION ALL (multihalmaz) közötti különbség!!! 
   
Feladat PL/SQL-ben:
- A fenti nemnegált rekurzív Datalog programot írjuk át Oracle PL/SQL programra!
- Ehhez előbb hozzuk létre egy alábbi szerkezetű ELJUT1 táblát:
            DROP TABLE Eljut1;
            CREATE TABLE Eljut1(
                             honnan VARCHAR2(10),
                             hova VARCHAR2(10));

- Írjunk egy olyan PL/SQL programot, ami feltölti az ELJUT1 táblát a megfelelő
   város párokkal, ahol az első városból el lehet jutni a másodikba. Mely (x, y)
   várospárokra lehetséges egy vagy több átszállással eljutni x városból y városba?

Megoldás vázlata (az előadáson szerepelt ez a vázlat és a vizsgára is kell!)
-- Eljut tábla növelése ciklusban, a ciklus során ellenőrizni kell, hogy történt-e
    változás, növekszik-e a sorok száma (Számláló), duplikátumokra figyelni kell!
-- A ciklus előtt kezdeti értékek beállítása
  delete from eljut1;
  RegiSzamlalo:= 0;
  insert into eljut1
    (select distinct honnan, hova from jaratok);

  select count(*) into UjSzamlalo from eljut1;
-- A ciklust addig kell végrehajtani, ameddig növekszik az eredmény, fontos,
    hogy csak olyan várospárokat vegyünk az eredményhez, ami még nem volt!
    Ezt többféleképpen szűrhetjük, az alábbi megoldásban NOT IN alkérdést 
    használunk. Próbáljuk ki más megoldásokkal is, például NOT EXISTS
    alkérdéssel vagy a MINUS halmazművelettel illetve egyéb megoldásokkal!
  LOOP
  insert into eljut1
    (select distinct eljut1.honnan,jaratok.hova
     from eljut1, jaratok  
     where eljut1.hova = jaratok.honnan
     and (
eljut1.honnan,jaratok.hova)
          NOT IN (select * from eljut1)
);
  select count(*) into UjSzamlalo from eljut1;
  EXIT WHEN UjSzamlalo = RegiSzamlalo;
  RegiSzamlalo := UjSzamlalo;
  END LOOP;

-- A program végrehajtása után ellenőrizzük le, kérdezzük le az eljut1 táblát:
    select * from eljut1 order by honnan, hova;
       
Rek2.feladat:
- (Papíros feladat) Fejezzzük ki Datalog programmal, hogy mely (x,y) város párokra
   hány átszállással és milyen költségekkel lehetséges egy vagy több átszállással eljutni
   x városból y városba?
- Megoldás:
   1.    Eljut(x, y, n, k) <-  Jaratok(_, x, y, k, _, _) AND n=0
   2.    Eljut(x, y, n, k) <- Eljut(x, z, n1, k1) AND Jaratok(_, z, y, k2, _, _) AND
                                       AND n=n1+1 AND k=k1+k2

- Most hozzuk létre egy alábbi szerkezetű ELJUT2 táblát, amely a költséget is tartalmazza:
            DROP TABLE Eljut2;
            CREATE TABLE Eljut2(
                             honnan VARCHAR2(10),
                             hova VARCHAR2(10),
                             atszallas NUMBER,
                             koltseg NUMBER);
   
- Most úgy töltsük fel az Eljut2 táblát, hogy az átszállás oszlop tartalmazza hányszor
   kellett átszállni és a költség oszlop az utazás költséget (repülőjegyek árának összegét)
   tartalmazza a két város között (A és B város között). Ennek az Eljut2 táblának a
   segítségével keressük ki a két város között a lehető legolcsóbb út költségét.
   
Rek3.feladat:
- Tegyük fel, hogy nemcsak az érdekel, hogy el tudunk-e jutni az egyik városból a másikba,
   hanem az is, hogy utazásunk során az átszállások is ésszerűek legyenek, vagyis ha több
   járattal  utazunk és átszállásra van szükségünk, akkor az érkező járatnak legalább egy
   órával a rá következő indulás előtt meg kell érkeznie.
   (Feltehetjük, hogy nincs egy napnál hosszabb utazás)
- Ezt a feladatot is fejezzzük ki előbb Datalog programmal, majd hozzuk létre az ELJUT3
   táblát a megfelelő szerkezettel, és most úgy töltsük fel az ELJUT3 táblát, hogy a minimális
   időt tartalmazza két város között (A és B város között a lehető leggyorsabb út és ideje)
   
Rek4.feladat:
- A fenti feladatokat oldjuk meg PL/SQL-ben úgy is, hogy ne csak a várospárokat,
   hanem a teljes útvonalat is listázzuk ki.
    
Gyakorló feladatok: Azokat a feladatokat, amelyekre az órán nem maradt idő,
gyakorló feladatként otthon önállóan be lehet fejezni és emailben be lehet küldeni!
> Köv.héten: II.ZH 
       
Fel a lap tetejére                          Vissza az AB1gyak oldalára (főmenü)