61
Rekurzívne dotazy Juraj Fečanin Aleš Plšek 1.12.2004
Rekurzívne dotazy
Juraj Fečanin
Aleš Plšek
1.12.2004
2
Cíle
1.cíl Jak funguje rekurze v SQL?
2.cíl Zásady implementace
3
Obsah
1. Úvod
2. Konstrukce a průběh rekurzivních dotazů
3. Logické hierarchie a jejich vztah k rekurzi
4. Zastavení rekurzivního výpočtu
5. Příklady, pokročilejší techniky rekurze
6. Zásady implementace
7. Závěr
4
I. kapitola
Úvod
5
Úvod
• SQL příkaz – správnost výsledku, čitelnost a efektivnost
• Rekurzivní SQL příkaz čitelnost a srozumitelnost
• Proč tedy používat rekurzivní dotazy?
• Někdy jediný efektivní způsob získání výsledku
6
Použití
• Efektivní řešení problému na komplexních strukturách dat.
• Vhodné při dotazech, kdy každý zpracovaný záznam bude součástí výsledku
(Najdi všechny zaměstnance pracující pro Boba.)
• Nebezpečné pro dotazy s nízkým počtem záznamů v odpovědi
(Najdi pět nejrychlejších spojů z Bostonu do Dallasu.)
7
Další informace
• Základní pravidlo: Vyloučit co největší počet záznamů jak nejrychleji to je možné
• Vede ke snížení čitelnosti
• Pozor u zacyklených dat!• Problémy s rekurzivními SQL příkazy
• Při dodržení správných zásad mohou být efektivním a užitečným nástrojem
8
K čemu se rekurze používá?
1. Vytvoření náhodného vzorku dat(Sample data)
2. Výpis prvních n záznamů
3. Generování jednoduchých parserů
4. Zjištení hierchických vazeb mezi záznamy
5. Normalizace a denormalizace datových struktur
9
II. kapitola
Konštrukcia a priebeh rekuzívnych dotazov
10
Rekurzia v SQL
• Výraz je rekurzívny, ak používa sám seba v svojej definícii
• Náhrada programu, ktorý by spracovával výsledky dotazov
• Nebezpečenstvo zacyklenia
11
Nerekurzívne dotazy 1
ZAMESTNANCI
MENO PLAT NADRIADENÝ
• Tabuľka, na ktorej si vysvetlíme základné princípy rekurzívnych dotazov
12
Nerekuzívne dotazy 2
• Mená zamestnancov, ktorých nadriadený je pán Hoover a zarábajú viac ako $100.000
• Čo ak chceme vypísať mená všetkých Hooverových podriadených (nielen priamo), ktorí zarábajú viac ako $100.000
SELECT meno,plat FROM zamestnanci WHERE nadriadeny=‘Hoover’ AND plat>100000
13
Pravidlá pre rekurzívne dotazy 1
1. Definujeme výraz s použitím klauzule WITH– na jeho základe sa vytvorí dočasný pohľad– tento výraz musí byť definovaný ako zjednotenie
dvoch oddelených častí (UNION ALL)– prvá časť - inicializačný poddotaz
- bez rekurzie
- vyhodnocovaný ako prvý– druhá časť - rekurzívny poddotaz
- pridáva nové riadky do dočasného pohľadu
- pozor na zarážku
14
Pravidlá pre rekurzívne dotazy 2
• Rekurzívny poddotaz– nemá obsahovať stĺpcové funkcie, SELECT
DICTINCT, GROUP BY alebo HAVING– má obsahovať odkaz na výraz, v ktorom je zahrnutý
sám, ale nie poddotaz nižšej úrovne– každý stĺpec rekurzívneho poddotazu musí byť
kompatibilný s príslušným stĺpcom inicializačného poddotazu (cast)
15
Pravidlá pre rekurzívne dotazy 3
2. Za klauzulou WITH musí byť definovaný dočasný pohľad
16
Príklad
WITH adepti(meno,plat) AS ((SELECT meno,plat [inicializačný poddotaz] FROM zamestnanci WHERE nadriadeny=‘Hoover’) UNION ALL (SELECT z.meno,z.plat [rekurzívny poddotaz] FROM adepti AS a,zamestnanci AS z WHERE z.nadriadeny=a.meno))SELECT meno [finálny dotaz]FROM adeptiWHERE plat>100000;
17
Príklad - komentár
• pri vyhodnocovaní dočasného pohľadu, databáza vidí iba riadky, ktoré boli pridané v predchádzajúcej iterácii
• systém pokračuje v rekurzii, kým sa do pohľadu pridávajú riadky
• potreba byť opatrný – nekonečný cyklus
18
Odlišný pohled
• Dočasná tabulka jako fronta záznamů
• Na začátku obsahuje záznamy získané z inicializačního dotazu
• Postupně na každý záznam spušten iterační dotaz, výsledky se přidávají na začátek fronty
• Proces končí při vyprázdnění fronty
19
Odlišný pohled - ilustrace
AAA
BBB CCC DDD
EEE FFF
GGG
AAA AAA AAA
BBB CCC DDD
CCC
EEE
DDD DDD
EEE FFF
FFF
GGG
20
Odlišný pohled - poznámky
• Výstup rekurzivního dotazu může být použit v dalším rekurzivním výrazu
(Najdi všechny státy v USA a pak všechny města v každém státě.)
• Pozor u UNION ALL, nestačí jen UNION (s ohledem na duplicity)
• Pro efektivnější zpracování dotazu se doporučuje vhodná indexace záznamů
• Výstupem je dočasná tabulka – zachována platnost všech definovaných omezení pro dočasné tabulky
21
Možnosti použitia
• ak je rekurzívny dotaz použitý vo vnútri výrazu CREATE VIEW, definuje sa rekurzívny pohľad
• ak vo vnútri INSERT výrazu, je jeho výsledok vložený do cieľovej tabuľky
• veľmi silná technika• napr. chceme vytvoriť tabuľku ČÍSLA so
stĺpcami PORADOVÉ a NÁHODNÉ
čísla od 1 do 1000 náhodné čísla od 1 do 1000
22
Príklad
CREATE TABLE čísla(poradové Integer,náhodné Integer);
INSERT INTO čísla(poradové,náhodné) WITH dočasné(n) AS (VALUES(1) [inicializačný
poddotaz] UNION ALL SELECT n+1 FROM dočasné [rekurzívny poddotaz] WHERE n<1000) SELECT n,integer(rand()*1000) FROM dočasné;
23
III. kapitola
Logické hierarchie a jejich vztah k rekurzi
24
Logické hierarchie
• Logické hierarchie v reálném světě a jejich reprezentace v relačních databázích
• Typy hierarchií– Divergentní– Konvergentní– Rekurzivní
• Další rozeznávaná vlastnost– Vyvážená/Nevyvážená
Divergentní hierarchie
• Žádný objekt nemá více než jednoho předka
• Libovolný počet potomků• Často obsahuje každá
vrstva vždy jen jeden typ objektů– Např. geografická
hierarchie = země,kraj,město,ulice
• Implementace - stačí jedna tabulka
AAA
BBB CCC DDD
EEE FFF GGG
KEYO PKEY NUM PRICE
AAA $10
BBB AAA 1 $21
CCC AAA 5 $23
DDD AAA 10 $25
EEE DDD 44 $33
FFF DDD 5 $34
GGG FFF 5 $44
26
Konvergentí hierarchie
• Libovolný počet předků a potomků• Reprezentují např. logické objekty, výrobky(popis
součástek)• Implementace – dvě tabulky
– Tabulka popisující objekty– Tabulka popisující vztahy mezi objekty
AAA
BBB CCC DDD
EEE FFF
GGG
27
Konvergentí hierarchie - příklad
KEYO PRICE
AAA $10
BBB $21
CCC $23
DDD $25
EEE $33
FFF $34
GGG $44
Objekty
PKEY CKEY NUM
AAA BBB 1
AAA CCC 5
AAA DDD 20
CCC EEE 33
DDD EEE 44
DDD FFF 5
FFF GGG 5
Vztahy AAA
BBB CCC DDD
EEE FFF
GGG
28
Rekurzivní hierarchie
• Libovolný počet předků• Objekt může být přímo či nepřímo svým předkem• V reálném světě je tato hierarchie téměř vždy špatná • Většinou nahrazuje konvergentní hierarchii tam, kde to
přispěje ke zjednodušení• Realizace - jako u konvergentní hierarchie
AAA
BBB CCC DDD
EEE FFF
GGG
29
Rekurzivní hierarchie - příklad
KEYO PRICE
AAA $10
BBB $21
CCC $23
DDD $25
EEE $33
FFF $34
GGG $44
Objekty Vztahy
AAA
BBB CCC DDD
EEE FFF
GGG
PKEY CKEY NUM
AAA BBB 1
AAA CCC 5
AAA DDD 20
CCC EEE 33
DDD AAA 99
DDD FFF 5
DDD EEE 45
FFF GGG 5
30
Vyvážené/Nevyvážené hierarchie
• Vyvážené hierarchie– úroveň = jednotná množina hodnot, stejná
vzdálenost objektů od kořene– Většinou každá úroveň obsahuje jiné typy
objektů (např. stát, město, ulice)
• Nevyvážené hierarchie– Všechny objekty jednotného typu
(např. společnost vlastnící další společnosti)
31
Datové/Ukazatelové hierarchie
• Stejný design, různé použití
• Ukazatelová hierarchie– V hlavních tabulkách uloženy jen data– Logické struktury a hierarchie definovány
zvlášť– Použití např. v bankovních aplikacích
32
Datové hierarchie
• Databáze popisuje vztahy mezi objekty(tabulky obsahující informace o všech
součástech letadla)
• Při rekurzivním zpracování je třeba být velmi opatrný(např. pro spočítání váhy objektů potřebujeme
uvažovat jak počet podobjektů, tak jejich hmotnosti)
33
IV. kapitola
Zastavení rekurzivního výpočtu
34
Zastavení rekurzivního výpočtu
• Jak zjistit, kdy se má výpočet ukončit?
• Prevence zacyklení
• Techniky zastavení výpočtu:1. Skončit po průchodu určitého počtu úrovní
2. Nevracet se na už jednou navštívená místa
35
Rekurzivní data
• Uvažujme strukturu dat AAA
BBB CCCDDD
EEE FFF
GGG
PKEY CKEY
AAA BBB
AAA CCC
AAA DDD
CCC EEE
DDD AAA
DDD FFF
DDD EEE
FFF GGG
36
Zastavení po průchodu n úrovněmiWITH Parent(ckey,lvl) AS ( (SELECT DISTINCT pkey, 0
FROM TROUBLE WHERE pkey = ‘AAA’)
UNION ALL (SELECT C.ckey,P.lvl + 1
FROM Trouble C, Parent P
WHERE P.ckey = c.pkeyAND P.lvl +1 < 4 )
)SELECT ckey, lvl FROM Parent;
Výsledek
CKEY LVL
AAA 0
BBB 1
CCC 1
DDD 1
EEE 2
AAA 2
EEE 2
FFF 2
BBB 3
CCC 3
DDD 3
GGG 3
37
Stop na n-té úrovní, výpis cestWITH Parent(ckey,lvl,path,loc) AS (( SELECT DISTINCT pkey, 0
, VARCHAR (pkey,20) , 0
FROM TROUBLE WHERE pkey = ‘AAA’)
UNION ALL (SELECT C.ckey,P.lvl + 1 , P.path|| ’>’ ||C.ckey , LOCATE (C.ckey|| ’>’ ||P.path)
FROM Trouble C , Parent P
WHERE P.ckey = c.pkeyAND P.lvl +1 < 4 ))
SELECT ckey, lvl, path, loc FROM Parent;
Výsledky
CKE LVL PATH LOC
AAA 0 AAA 0
BBB 1 AAA>BBB 0
CCC 1 AAA>CCC 0
DDD 1 AAA>DDD 0
EEE 2 AAA>CCC>EEE 0
AAA 2 AAA>DDD>AAA 1
EEE 2 AAA>DDD>EEE 0
FFF 2 AAA>DDD>FFF 0
BBB 3 AAA>DDD>AAA>BBB 0
CCC 3 AAA>DDD>AAA>CCC 0
DDD 3 AAA>DDD>AAA>DDD 2
GGG 3 AAA>DDD>FFF>GGG 0
38
Najdi všechny potomkyWITH Parent(ckey,lvl,path,loc) AS ( ( SELECT DISTINCT pkey, 0
, VARCHAR (pkey,20)FROM TROUBLEWHERE pkey = ‘AAA’ )
UNION ALL ( SELECT C.ckey,P.lvl + 1
, P.path|| ’>’ ||C.ckeyFROM Trouble C
, Parent P WHERE P.ckey = c.pkey AND LOCATE (C.ckey|| ’>’ ||P.path) = 0
))SELECT ckey, lvl, path FROM Parent;
Výsledky
CKE LVL PATH
AAA 0 AAA
BBB 1 AAA>BBB
CCC 1 AAA>CCC
DDD 1 AAA>DDD
EEE 2 AAA>CCC>EEE
EEE 2 AAA>DDD>EEE
FFF 2 AAA>DDD>FFF
GGG 3 AAA>DDD>FFF>GGG
39
Zastavení při nalezení cykluWITH Parent(ckey,lvl,path) AS ( ( SELECT DISTINCT pkey, 0
, VARCHAR (pkey,20) FROM TROUBLE WHERE pkey = ‘AAA’ )
UNION ALL ( SELECT CASE
WHEN LOCATE (C.ckey|| ’>’, P.path) > 0 THEN RAISE_ERROR(‘70001’,’Error: Loop in database found’)
ELSE C.CKEY END , P.lvl + 1 , P.path|| ’>’ ||C.ckey FROM Trouble C
, Parent P WHERE P.ckey = c.pkey)
SELECT ckey, lvl, path FROM Parent;
)
40
V. kapitola
PríkladyProblém priechodu častí, Rekurzívne
vyhledávánie, CAST výraz,…
41
Problém priechodu častí 1
• výroba lietadiel• tabuľka všetkých častí, použitých v istom type lietadla, a ich
komponentkrídlo
výstuha kormidlo podvoz.
nit
čáp
Časť Komponenta Počet
Krídlo Výstuha 5
Krídlo Kormidlo 1
Krídlo Podvozok 1
Krídlo Nit 100
Výstuha Nit 10
Kormidlo Čáp 2
Kormidlo Nit 5
Podvozok Čáp 3
Podvozok Nit 8
Čáp Nit 4
5
100
10
11
5 2
83
4
Orientovaný acyklický graf
42
Problém priechodu častí 2
Aký je počet nitov použitých na jednom krídle?– problém: Musíme uvažovať aj počet častí
obsahujúcich nity.– použijeme tie isté pravidlá ako v predchádzajúcich
príkladoch– dočasný pohľad: ČASTI_KRÍDLA
• riadok obsahuje komponentu a počet komponent pre istú časť krídla
– inicializačný poddotaz vyberie časti, použité priamo pri kompletizovaní krídla
– rekurzívny poddotaz vyberá časti na nižších úrovniach kompletizácie
– acyklický graf rekurzia sa zastaví
43
Realizácia
WITH časti_krídla(komponenta,počet) AS
((SELECT komponenta,počet [inicializačný poddotaz]
FROM komponenty
WHERE časť=‘krídlo’)
UNION ALL
(SELECT k.komponenta,č.počet*k.počet [rekurzívny poddotaz]
FROM časti_krídla č,komponenty k
WHERE č.komponenta=k.časť))
SELECT sum(počet) AS počet
FROM časti_krídla
WHERE komponenta=‘nit’;
Výsledok: počet
183
44
Realizácia 2
WITH časti_krídla(komponenta,počet) AS
((SELECT komponenta,počet FROM komponenty WHERE časť=‘krídlo’) UNION ALL (SELECT
k.komponenta,č.počet*k.počet FROM časti_krídla č,komponenty k WHERE č.komponenta=k.časť))SELECT komponenta,sum(počet) AS
početFROM časti_krídlaGROUP BY komponenta;
Komponenta Počet
Výstuha 5
Kormidlo 1
Podvozok 1
Čáp 5
Nit 183
Výsledok:
45
Rekurzívne vyhľadávanie
Nájdi najlacnejšiu trasu zo San Fracisca do New Yorku.
POZOR!!! Graf nie je acyklický.
Chicago
San Francisco New York
Los Angeles
Dallas
50
275 250
100300
200
225
Letová mapa
Lety
Číslo_letu Z Do Cena
46
San Francisco – New York
Na úvod skúsme vyhľadať cesty zo San Francisca do New Yorku.– inicializačný poddotaz zistí všetky mestá, do ktorých
sa dá doletieť zo San Francisca jediným letom– rekurzívny poddotaz nájde všetky mestá, ktoré sú
dosažitelné z pôvodných– pre každé dosiahnuté mesto sa zaznamená trasa a
celková cena– nakoniec sa zo získaných ciest vyberú tie, ktoré
končia v New Yorku
47
Realizácia
WITH cesty(do,trasa,cena) AS ((SELECT do,do,cena FROM lety WHERE z=‘San Francisco’) UNION ALL (SELECT l.do,
c.trasa || ’,’ || l.do, c.cena+l.cena
FROM cesty c,lety l WHERE c.do=l.z))SELECT trasa,cenaFROM cestyWHERE do=‘New York’;
48
Realizácia
WITH cesty(do,trasa,cena) AS ((SELECT do,do,cena FROM lety WHERE z=‘San Francisco’) UNION ALL (SELECT l.do,
c.trasa || ’,’ || l.do, c.cena+l.cena
FROM cesty c,lety l WHERE c.do=l.z))SELECT trasa,cenaFROM cestyWHERE do=‘New York’;
Dva problémy:- do stĺpca trasa vkladáme stále
dlhší a dlhší reťazec (musíme systému nejakým spôsobom oznámiť jeho maximálnu dĺžku)
- dotaz neskončí, kým systému nedôjdu prostriedky
49
CAST výraz
• zmena hodnoty z jedného dátového typu na iný• definované v SQL92
• cieľový dátový typ musí byť dobre definovaný (veľkosť, rozsah, presnosť – ak je def.)
• nastavené hodnoty sú Decimal(5,0), Char(1), Graphic(1)• ostatné typy bez hodnôt• nemožnosť konverzie• pri nezhode veľkostí
CAST ( výraz AS typ )
NULL
CAST (c1+c2 AS Decimal(8,2))CAST (meno || adresa AS Varchar(255))
CHYBA
zaokrúhlenie
50
Riešenie prvého problému
• systém od nás potrebuje informáciu o tom, kam až môže narásť dĺžka položky
• môžme určiť, že dĺžka trasy môže byť obmedzená na 100 znakov (čo je dosť miesta pre trasy, ktoré nás zaujímajú)
• pomocou pretypovania stĺpca na Varchar(100) v inicializačnom aj rekurzívnom poddotaze sa s týmto problémom vysporiadame
• zmeny:– inicializačný poddotaz: CAST(do AS Varchar(100))– rekurzívny poddotaz: CAST(c.trasa || ’,’ || l.do AS
Varchar(100))
51
Riešenie druhého problému
Aké pravidlá by sme si určili pri vyhľadávaní spojenia?
1. Neuvažuj lety, ktoré smerujú do San Francisca.
2. Neuvažuj lety, ktoré letia z New Yorku.
3. Neuvažuj trasy, ktoré majú viac ako 3 lety.
52
RealizáciaWITH cesty(do,trasa,počet_letov,cena)
AS ((SELECT do,
CAST(do AS Varchar(100)),1,cena
FROM lety WHERE z=‘San Francisco’) UNION ALL (SELECT l.do,
CAST(c.trasa || ’,’ || l.do ASVarchar(100)),c.počet_letov+1,c.cena+l.cena
FROM cesty c,lety l WHERE c.do=l.z AND l.do<>’San Francisco’ AND l.z<>’New York’ AND c.počet_letov<3))SELECT trasa,cenaFROM cestyWHERE do=‘New York’AND cena= (SELECT min(cena) FROM cesty WHERE do=‘New York’);
53
Viac inicializačných poddotazov
Nájdi najlacnejšiu trasu zo San Fracisca do New Yorku.
– použijeme 2 inicializačné poddotazy – lety zo San Francisca, vlaky zo San Francisca
– k tomu 2 rekurzívne poddotazy – pridávanie letov resp. vlakov k trasám
Vlaky
Číslo_vlaku Z Do Cena
Lety
Číslo_letu Z Do Cena
54
Realizácia 1WITH cesty(do, trasa, plán,
počet_častí, cena) AS ((SELECT do, CAST(do AS Varchar(100)), CAST(číslo_letu AS
Varchar(100)), 1, cena FROM lety WHERE z=‘San Francisco’) UNION ALL (SELECT do,
CAST(do AS Varchar(100)), CAST(číslo_vlaku AS
Varchar(100)),
1, cena FROM vlaky WHERE z=‘San Francisco’) UNION ALL (SELECT l.do,
CAST(c.trasa || ’,’ || l.do AS Varchar(100)), CAST(c.plán || ’,’ || l.číslo_letuAS Varchar(100)), c.počet_častí+1, c.cena+l.cena
FROM cesty c,lety l WHERE c.do=l.z AND l.do<>’San Francisco’ AND l.z<>’New York’ AND c.počet_častí<3))
55
Realizácia 2
UNION ALL SELECT x.do,
CAST(c.trasa || ’,’ || x.do ASVarchar(100)),
CAST(c.plán || ’,’ || x.číslo_vlakuAS
Varchar(100)),c.počet_častí+1,c.cena+x.cena
FROM cesty c,vlaky x WHERE c.do=x.z AND x.do<>’San Francisco’ AND x.z<>’New York’ AND c.počet_častí<3))
SELECT trasa,plán,cenaFROM cestyWHERE do=‘New York’AND cena= (SELECT min(cena) FROM cesty WHERE do=‘New York’);
56
VI. kapitola
Zásady implementácie
57
Zásady 1
1. Vytvárajme rekurzívny dotaz, ktorý je zjednotením (UNION ALL) jedného alebo viacerých inicializačných poddotazov a jedného alebo viacerých rekurzívnych poddotazov.
2. Inicializačný poddotaz musí byť nerekurzívny.3. Rekurzívny poddotaz by mal používať výraz,
v ktorom sa nachádza.4. Rekurzívny poddotaz by nemal obsahovať
stĺpcové funkcie, SELECT DISTINCT, GROUP BY alebo HAVING
58
Zásady 2
5. Stĺpce rekurzívnych poddotazov musia byť kompatibilné s prislúchajúcimi stĺpcami inicializačných poddotazov
6. Rekurzívne poddotazy musia špecifikovať, ako sa každý nový riadok získa z už existujúceho. Ak dáta obsahujú cykly, poddotaz musí obsahovať pravidlo na zastavenie rekurzie.
7. Pri písaní konečného dotazu, použite rekurzívny výraz a môžete pridať nejaký ďalší predikát
59
Varovná hlášení
• Některé rekurzivní SQL dotazy generují následující varovné hlášeníSQL0347W The recursion comon table expression „RECURSION.TEMP1“ may contain an infinitive loop. SQLSTATE=01605
60
Varovná hlášení II
WITH Temp1(N1) AS ((SELECT Integer(10)
FROM STAFF WHERE ID = 10 )
UNION ALL (SELECT Integer(N1 + 10)
FROM Temp1 WHERE N1 < 50)
)SELECT * FROM Temp1;
varovné hlášení
WITH Temp1(N1) AS
((SELECT Integer(ID)
FROM STAFF
WHERE ID = 10 )
UNION ALL
(SELECT Integer(N1 + 10)
FROM Temp1
WHERE N1 < 50)
)
SELECT *
FROM Temp1;bez varování
61
Zdroje a literatura
DB2/V2 Recursive SQL
Database programming & design:
Don Chamberlin – Recursion in SQL
