Rekurzívne dotazy

transcript

Rekurzívne dotazy

Juraj Fečanin

Aleš Plšek

1.12.2004

1.cíl Jak funguje rekurze v SQL?

2.cíl Zásady implementace

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

I. kapitola

• 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

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.)

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

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

II. kapitola

Konštrukcia a priebeh rekuzívnych dotazov

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

Nerekurzívne dotazy 1

ZAMESTNANCI

MENO PLAT NADRIADENÝ

• Tabuľka, na ktorej si vysvetlíme základné princípy rekurzívnych dotazov

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

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

• 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)

2. Za klauzulou WITH musí byť definovaný dočasný pohľad

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;

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

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

Odlišný pohled - ilustrace

BBB CCC DDD

EEE FFF

AAA AAA AAA

BBB CCC DDD

DDD DDD

EEE FFF

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

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

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é;

III. kapitola

Logické hierarchie a jejich vztah k rekurzi

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

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

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

BBB CCC DDD

EEE FFF

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

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

BBB CCC DDD

EEE FFF

Rekurzivní hierarchie - příklad

KEYO PRICE

AAA $10

BBB $21

CCC $23

DDD $25

EEE $33

FFF $34

GGG $44

Objekty Vztahy

BBB CCC DDD

EEE FFF

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

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)

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

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)

IV. kapitola

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

Rekurzivní data

• Uvažujme strukturu dat AAA

BBB CCCDDD

EEE FFF

PKEY CKEY

AAA BBB

AAA CCC

AAA DDD

CCC EEE

DDD AAA

DDD FFF

DDD EEE

FFF GGG

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

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

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

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;

V. kapitola

PríkladyProblém priechodu častí, Rekurzívne

vyhledávánie, CAST výraz,…

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.

Č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

Orientovaný acyklický graf

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í

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

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:

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

275 250

100300

Letová mapa

Číslo_letu Z Do Cena

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

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’;

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

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 )

CAST (c1+c2 AS Decimal(8,2))CAST (meno || adresa AS Varchar(255))

zaokrúhlenie

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))

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.

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’);

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

Číslo_vlaku Z Do Cena

Číslo_letu Z Do Cena

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))

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’);

VI. kapitola

Zásady implementácie

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

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

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

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í

Zdroje a literatura

DB2/V2 Recursive SQL

Database programming & design:

Don Chamberlin – Recursion in SQL

Rekurzívne dotazy

Documents