10.gyak. Rekurzív Datalog program kiértékelése PL/SQL-ben
   
> A gyakorlat táblás része: Lekérdezések logikai lekérdező nyelven:
   >> E4.1. Lekérdezések kifejezése Datalogban, relációs algebra és Datalog átírások
   >> E4.2. Rekurzív Datalog és rekurzió az SQL3-ban WITH RECURSIVE utasítás
> A gyakorlat gépes része:
   >> 2.5. (folyt) 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 -- Ehhez egy minta zh - gépes feladatsor
      

E4.1. Lekérdezések kifejezése Datalogban
   
Áttekintés:
- Az 1-2. gyakorlat lekérdezéseit először természetes nyelven fogalmaztuk meg, majd
  "táblákban gondolkodva" azt néztük meg, hogyan mely táblából milyen műveletekkel
  tudjuk megkapni az eredménytáblát, ezt megadtuk formálisan is relációs algebrában.
- Ezután a 3-4. gyakorlaton SQL SELECT utasítással (multihalmazokon) fejeztük ki
  ugyanezeket a lekérdezéseket. Az 5-6. gyakorlaton néztünk további lehetőségeket
   az SQL SELECT-ben, majd kiterjesztettük a relációs algebrát erre a lehetőségekre.
- A mai gyakorlaton visszatérünk az 1-2. gyakorlatok relációs algebrai lekérdezéseire
  (halmazokon) és a lekérdezéseket fejezzük ki (nem rekurzív) Datalog programmal.
   
Segédanyag:  
- Relációs algebra Datalog átírások: AB1_Datalog_pp25_27.pdf
- Tankönyvben [Ullman-Widom] 5.3-5.4. Datalog szabályok és lekérdezések
   
Datalog feladatok:
Egyszerű táblák és lekérdezések a kezdetekhez:
Szeret tábla és feladatok
Sörivók adatbázis és feladatok
Tankönyv Termék sémán alapuló feladatai:
Termék-PC-Laptop-Nyomtató adatbázis
Hajóosztályok-Csaták-Kimenetelek adatbázis
A fenti linkeken elérhető feladatokat fejezzük ki nem-rekurzív Datalog programmal!
   
Megjegyzés. A rekurziót a következő menüpontban tárgyaljuk, például a tranzitív lezárt
nem fejezhető ki  relációs algebrában, viszont rekurzív Datalog programmal megadható.
      
E4.2. Rekurzív nem-negált Datalog és SQL3 WITH RECURSIVE
   
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) 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.    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)

- (Papíros feladat) A fenti rekurzív Datalog programot írd át az SQL3 szabványban
   szereplő WITH RECURSIVE utasítással! (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. (folyt) 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, lásd 7.gyak#2.5. Hier.lekérd
   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
- 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  #Rekurzió
- (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!
         
 Vissza az AB1 gyakorlat oldalára             Vissza a Kezdőlapra