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';
- Fontos: UNION (halmaz)
és UNION
ALL (multihalmaz) közötti
különbség!!!
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);
- 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.
- 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
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ü)