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