12.gyak. Rekurzív Datalog program kiértékelése PL/SQL-ben
   
>> 3.7. Az "Eljut feladat" rekurzív lekérdezések PL/SQL-ben
>> Köv.héten: II.ZH -- Ehhez egy minta zh - gépes feladatsor
   

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 >> Rek.PSM (jelszóval)
- 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 az egyik korábbi gyakorlaton: 9gyak#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!
  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;

   
Rek2.feladat:
- (Papíros feladat) Fejezzzük ki Datalog programmal, hogy mely (x,y) város párokra
   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, K) <-  Jaratok(_, X, Y, K, _, _)
   2.    Eljut(X, Y, K) <- Eljut(X, Z, K1) AND Jaratok(_, Z, Y, K2, _, _) 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),
                             koltseg NUMBER);
   
- Most úgy töltsük fel az ELJUT2 táblát, hogy a költség oszlop a minimális költséget
   tartalmazza a két város között (A és B város között a lehető legolcsóbb út költsége)
   
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 old meg PL/SQL-ben úgy is, hogy ne csak a várospárokat, hanem
   a teljes útvonalat is listázzuk ki.
   
Vissza az AB1 gyakorlat oldalára             Vissza a Kezdőlapra