Rekurzivní dotazy v SQL

Martin ČermákTomáš Dvořák

Alena Rybičková

Úvod

SQL příkaz snaha o čitelnost, srozumitelnost

rekurzivní SQL dotaz je rekurzivní, pokud je použit ve své vlastní

definici hůře čitelné i srozumitelné dotazy často jediný efektivní způsob získání výsledku

bez rekurze je potřeba v hostitelském programu mít funkci, která zpracovává výsledky z dílčích dotazů

výhodné pro hledání vztahů ve stromové struktuře lze použít pro acyklické i cyklické grafy

Syntaxe rekurzivního dotazu

WITH [RECURSIVE] <query_alias_name> [ ( <column_list> ) ]AS ( <select_query> )<query_using_query_alias_name>

vše podstatné je uvnitř <select_query>

Použití klauzule WITH

použitím klauzule WITH vzniká tzv. Common Table Expression (CTE)

CTE je dočasný pohled (temporary view) požití CTE

ve složitých dotazech, kde je nějaký poddotaz použit alespoň dvakrát

v rekurzivních dotazech

Jednoduchý příklad

Zamestnanec(Jmeno, Plat, Vedouci)

hledáme zaměstnance, kteří mají plat alespoň 100.000 a jejichž přímý nadřizený je ‘Hoover’

SELECT Jmeno, PlatFROM ZamestnanecWHERE Vedouci = ‘Hoover’ AND Plat > 100000

Jednoduchý příklad – rekurze hledáme-li všechny zaměstnance, jejichž

nadřízený (nemusí být přímý) je ‘Hoover’ potřebujeme rekurzivní dotaz použijeme klauzuli WITH definující “Common Table

Expression” (CTE) obsahuje dvě části spojené klauzulí UNION ALL

inicializační poddotaz bude zpracován jako první, neovlivňuje rekurzi v našem příkladě vyhledá Hooverovy přímé podřízené

rekurzivní poddotaz přidává další záznamy k dočasnému pohledu (v závislosti

na dříve nalezených) v našem příkladě zde budou přidáni zaměstnanci, jejich

přímý nadřízený již byl přidán do dočasného pohledu

Jednoduchý příklad – rekurze

WITH Adept (Jmeno, Plat) AS(( SELECT Jmeno, Plat [inicializační poddotaz] FROM Zamestnanec WHERE Vedouci = ‘Hoover’ ) UNION ALL ( SELECT Z.Jmeno, Z.Plat [rekurzívní poddotaz] FROM Adept AS A, Zamestnanec AS Z WHERE Z.Vedouci = A.Jmeno ))SELECT Jmeno [finální dotaz]FROM AdeptiWHERE Plat > 100000;

Pravidla rekurzivního poddotazu

nesmí obsahovat sloupcové opreace SELECT DISTINCT GROUP BY HAVING

může obsahovat odkaz na výraz ve kterém je sám definovaný, ale ne poddotaz nižší úrovně

každý sloupec rekurzivního poddotazu musí být typově kompatibilní s příslušným sloupcem v inicializačním poddotazu používá se přetypování – CAST

Složitější dotaz – nerekurzivní News(ID, Forum, Question) Hledáme fórum s nevyšším počtem příspěvků

SELECT COUNT(ID) AS Nbr, ForumFROM NewsGROUP BY ForumHAVING COUNT(ID) = (

SELECT MAX(Nbr)FROM ( SELECT COUNT(ID) AS Nbr, Forum

FROM NewsGROUP BY Forum )

Hledáme vlastně MAX(COUNT(...))

Příklad na použití klauzule WITH

News(ID, Forum, Question)

WITH Q_count_news (Nbr, Forum) AS ( SELECT COUNT(ID), Forum) FROM News GROUP BY Forum )SELECT Nbr, ForumFROM Q_count_newsWHERE Nbr = (SELECT MAX(Nbr) FROM Q_count_news)

Poznámky k příkladu

dočasný pohled Q_count_news používáme pro zjednodušení zápisu SQL dotazu

CTE (podobně jako pohled) musí mít název uvnitř CTE mohou být sloupce přejmenované

Použití více CTE v jednom dotazu WITH

Q_count_news (Nbr, Forum) AS ( SELECT COUNT(ID), Forum FROM News GROUP BY Forum ), Q_max_count_news (Nbr) AS ( SELECT MAX(Nbr) FROM Q_count_news )SELECT T1.*FROM Q_count_news T1 INNER JOIN Q_max_count_news T2 ON T1.Nbr = T2.Nbr

Rekurze v SQL

rekurzivní dotaz má dvě části první část říká jak se má začít – bez rekurze druhá část říká jak má vypadat další krok obě části jsou spojeny pomocí klauzule UNION ALL

rekurzivní dotaz vzniká použitím názvu CTE uvnitř druhé (rekurzivní) části dotazu

je třeba definovat podmínky, za kterých je rekurze ukončena

Rekurze s výpočtem

křídlo

vzpěra křidélko podvozek

nýtpant

11

5

100

10 58

2

4

3

Rekurze s výpočtem (2)

Part Subpart Qty

křídlo vzpěra 5

křídlo křidélko 1

křídlo podvozek 1

křídlo nýt 100

vzpěra nýt 10

křidélko pant 2

křidélko nýt 5

podvozek pant 3

podvozek nýt 8

pant nýt 4

Rekurze s výpočtem (3)

acyklický graf směr šipky říká z čeho je daný díl sestaven hodnoty u šipek říkají kolik daných součástek je

použito u jednoho dílu každá řádka v tabulce je reprezentována šipkou

Rekurze s výpočtem (4)

otázka: Kolik nýtů je použito při výrobě křídla? výpočet vyžaduje rekurzivní průchod grafem musíme sečíst nýty použité v jednotlivých součástech

křídla u jednotlivých součástek musíme brát v úvahu jejich

počet

dotaz bude obsahovat obvyklé části inicializační poddotaz rekurzivní poddotaz finální dotaz

Rekurze s výpočtem – SQL dotaz

WITH wingparts(subquery, qty) AS (( SELECT subpart, qty

[inicializační poddotaz] FROM components WHERE part = ‘křídlo’ ) UNION ALL ( SELECT c.subpart, w.qty * c.qty

[rekurzivní poddotaz] FROM wingparts w, components c WHERE w.subpart = c.part ));

Rekurze s výpočtem – průběh dotazu

Subpart Qty

vzpěra 5 přímé použití

křidélko 1

podvozek 1

nýt 100

nýt 50 z vzpěry

pant 2 z křidélka

nýt 5 z křidélka

pant 3 z podvozku

nýt 8 z podvozku

nýt 8 z pantu křidélka

nýt 12 z pantu podvozku

křídlo

vzpěra křidélko podvozek

nýtpant

11

5

100

10 58

2

4

3

Rekurze s výpočtem – celý dotaz

WITH wingparts(subquery, qty) AS (( SELECT subpart, qty [inicializační poddotaz] FROM components WHERE part = ‘křídlo’ ) UNION ALL ( SELECT c.subpart, w.qty * c.qty [rekurzivní poddotaz] FROM wingparts w, components c WHERE w.subpart = c.part ))SELECT sum(qty) AS qty [finální dotaz]FROM wingpartsWHERE subpart = ‘nýt’;

Výsledek: qty = 183

Databázové servery podporující rekurzivní dotazy

MS SQL Server 2005 IBM DB2 v7.2 Oracle 9i

podoruje jen procházení ve stromě – omezená syntaxe

nepodporuje rekurzivní dotazy klauzule START WITH, CONNECT BY

...

Syntaxe průchodu stromů v Oracle 9i

SELECT sloupce FROM tabulka [WHERE podmínka3]START WITH podmínka1CONNECT BY podmínka2[ORDER BY …]

Řádky vyhovující podmínce ve START WITH jsou považovány za kořenové řádky na první úrovni vnoření

Pro každou řádku na úrovni i se rekurzivně hledají přímí potomci vyhovující podmínce v klauzuli CONNECT BY na úrovni i+1 Řádka předka se v podmínce označuje klíčovým slovem

PRIOR

Syntaxe průchodu stromů v Oracle 9i

SELECT sloupce FROM tabulka [WHERE podmínka3]START WITH podmínka1CONNECT BY podmínka2[ORDER BY …]

Na závěr jsou odstraněny řádky nevyhovující podmínce ve WHERE

Pokud není definováno třídění, odpovídá pořadí průchodu pre-order

Každý řádek obsahuje pseudo-sloupec LEVEL, obsahující úroveň řádku v hierarchii

Oracle 9i vs. ISO 1999

tabulka zaměstnanců: Emp(EmpNo, Name, Manager) Oarcle 9i:

SELECT LPAD(’ ’, 2*Level) || Name Jmeno, LevelFROM EmpSTART WITH Manager IS NULLCONNECT BY Manager = PRIOR EmpNo;

ISO:WITH Emp AS ( SELECT EName AS Jmeno, 0 AS Level FROM Emp x WHERE Manager IS NULL UNION ALL SELECT EName, Level+1 FROM Emp y JOIN Emp ON y.Manager = Emp.EmpNo)SELECT * FROM Emp;

SQL1999 a SQL Server 2005

Tomáš Dvořák

Syntaxe

WITH [ RECURSIVE ] <query_alias_name> [ ( <column_list> ) ] AS ( <select_query> ) <query_using_query_alias_name>

MS SQL Server 2005 zatím nepodporuje klíčové slovo RECURSIVE

Stromová struktura

Id FatherID Name

1 NULL ALL

2 1 SEA

3 1 EARTH

4 1 AIR

5 2 SUBMARINE

6 2 BOAT

7 3 CAR

Id FatherID Name

8 3 TWO WHEELES

9 3 TRUCK

10 4 ROCKET

11 4 PLANE

12 8 MOTORCYCLE

13 8 BICYCLE

Stromová struktura (2)

ALL

SEAEARTH

AIR

SUBMARINE BOAT CAR ROCKET PLANE TWO

WHELLED

MOTOR-CYCLE

BICYCLE

TRUCK

Stromová struktura – předchůdci ‘Motorcycle’

chceme zjistit všechny předchůdce „Motorcycle“ začneme řádkou obsahující „Motorcycle“

SELECT Name, FatherIDFROM VehicleWHERE Name = ‘Motorcycle’

dotaz provádějící další krok bude vypadat následovně:

SELECT Name, FatherIDFROM Vehicle

Stromová struktura – předchůdci ‘Motorcycle’ (2)

oba předchozí dotazy spojíme pomocí klauzule UNION ALL

WITH tree (date, id) AS ( SELECT Name, FatherID FROM Vehicle WHERE Name = ‘Motorcycle’ UNION ALL SELECT Name, FatherID FROM Vehicle )

Stromová struktura – předchůdci ‘Motorcycle’ (3)

posledním krokem k rekurzi je vytvoření cyklu

WITH tree (date, id) AS ( SELECT Name, FatherID FROM Vehicle WHERE Name = ‘Motorcycle’ UNION ALL SELECT Name, FatherID FROM Vehicle V INNER JOIN tree t ON t.id = V.ID )SELECT *FROM tree

Stromová struktura – předchůdci ‘Motorcycle’ (4)

Výsledek našeho dotazu tedy je:

Data Id

MOTORCYCLE 8

TWO WHEELES 3

EARTH 1

ALL NULL

Předchůdci bez rekurze (1)

Dá se rekurze odstranit? ANO, pomocí zásobníku. Do tabulky přidáme 2 nové sloupečky:

RIGHTBOUND a LEFTBOUND Joe Celko: „SQL for smarties“ kapitola „Trees and

Hierarchies“

Předchůdci bez rekurze (2)

Tabulku naplníme daty, pro nové sloupečkyUPDATE VEHICLES SET LEFTBOUND = 1 , RIGHTBOUND = 26 WHERE ID = 1

UPDATE VEHICLES SET LEFTBOUND = 2 , RIGHTBOUND = 7 WHERE ID = 2

…

UPDATE VEHICLES SET LEFTBOUND = 12 , RIGHTBOUND = 13 WHERE ID = 12

UPDATE VEHICLES SET LEFTBOUND = 14 , RIGHTBOUND = 14 WHERE ID = 13

Předchůdci - bez rekurze (3)

Předchůdci - bez rekurze (4)

Dotaz na předchůdce MOTORCYCLE využije intervalů a bude vypadat:

SELECT *

FROM Vehicles

WHERE RightBound > 12

AND LeftBound < 13

Zobrazení stromu (1)

Někdy můžeme chtít zobrazit data v tabulce jako strom

WITH tree (data, id, level, pathstr)AS (SELECT NAME, ID, 0, CAST('' AS VARCHAR(MAX)) FROM VEHICLE

WHERE ID_FATHER IS NULL UNION ALL

SELECT NAME, ID, t.level + 1, t.pathstr +’>’+ V.NAME FROM VEHICLE V INNER JOIN tree t ON t.id = V.ID_FATHER)

SELECT SPACE(level) + data as data, id, level, pathstr

FROM tree ORDER BY pathstr, id

Zobrazení stromu (2)

Data Level PathStr

All 1

Air 1 Air

Plane 2 Air>Plane

Rocket 2 Air>Rocket

Earth 1 Earth

Car 2 Earth>Car

Truck 2 Earth>Truck

2Wheeles 2 Earth>2Wheeles

Bicycle 3 Earth>2Wheeles>Bicycle

…

Zobrazení – bez rekurze (1)

Do tabulky potřebujeme přidat sloupeček LEVEL, který nám označuje úroveň uzlu

Spočítáme ji při vkládání uzlu

UPDATE VEHICLES SET LEVEL = 0 WHERE ID = 1

UPDATE VEHICLES SET LEVEL = 1 WHERE ID = 2

…

UPDATE VEHICLES SET LEVEL = 0 WHERE ID = 13

UPDATE VEHICLES SET LEVEL = 1 WHERE ID = 14

Zobrazení – bez rekurze (2)

SELECT SPACE(level)+ name AS data

FROM Vehicle

ORDER BY LEFT_BOUND

Data

All

Sea

Submarine

Boat

Earth

Car

Two Wheeles

Motorcycle

Mazání tabulek (1)

Cíl: smazat tabulku Problém: tabulky jsou provázány integritními

omezeními (FOREIGN KEY apod.) Co chceme: posloupnost jak máme mazat tabulky,

abychom nakonec mohli smazat, tu kterou chceme Jak: pomocí rekurze projdeme tabulky, na kterých je

integritní omezení

Mazání tabulek (1)

WITH T_CONTRAINTES (table_name, father_table_name) AS (SELECT DISTINCT CTU.TABLE_NAME, TCT.TABLE_NAMEFROM INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS

RFC INNER JOIN

INFORMATION_SCHEMA.CONSTRAINT_TABLE_USAGE CTU ON RFC.CONSTRAINT_CATALOG = CTU.CONSTRAINT_CATALOG

AND RFC.CONSTRAINT_SCHEMA = CTU.CONSTRAINT_SCHEMA AND

RFC.CONSTRAINT_NAME = CTU.CONSTRAINT_NAME

Mazání tabulek (2)

INNER JOIN INFORMATION_SCHEMA.TABLE_CONSTRAINTS TCT

ON RFC.UNIQUE_CONSTRAINT_CATALOG = TCT.CONSTRAINT_CATALOG AND RFC.UNIQUE_CONSTRAINT_SCHEMA = TCT.CONSTRAINT_SCHEMA AND RFC.UNIQUE_CONSTRAINT_NAME = TCT.CONSTRAINT_NAME

WHERE CTU.TABLE_CATALOG = @DB AND CTU.TABLE_SCHEMA = @USR) ,

Mazání tabulek (3)

T_TREE_CONTRAINTES (table_to_delete, level)

AS (

SELECT DISTINCT table_name, 0

FROM T_CONTRAINTES WHERE father_table_name = @TABLE_TO_DELETE

UNION ALL

SELECT priorT.table_name, level - 1

FROM T_CONTRAINTES priorT

INNER JOIN T_TREE_CONTRAINTES beginT

ON beginT.table_to_delete = priorT.father_table_name

WHERE priorT.father_table_name<>priorT.table_name)

Mazání tabulek (4)

SELECT DISTINCT *

FROM T_TREE_CONTRAINTES

ORDER BY level

MS Server 2005

Počet rekurzivních volání je omezen na 100 Dá se ovlivnit nastavením

OPTION (MAXRECURSION n) Beta verze zatím nepodporuje klíčové slovo

RECURSION

Příklad – Hledání nejlepšího řešení

Alena Rybičková

San Francisco – New York

Flights

flightno origin destination cost

San Francisco – New York

hledáme jak se nejlevněji dostat ze San Francisca do New Yorku

data obsahují cykly, musíme vyřešit abychom nelétali pořád dokola

Rekurzivní dotaz

dočasný pohled nazvaný TRIPS tvoří UNION ALL mezi inicializačním poddotazem, který najde všechna

města, do kterých se dá dostat ze SF na jeden let rekurzivním poddotazem, který najde najde všechna

města, kam se lze dostat z již nalezených měst

První pokusWITH trips (destination, route, totalcost) AS

((SELECT destination, destination, cost [initial subquery] FROM flights WHERE origin = 'SanFrancisco’)UNION ALL (SELECT f.destination [recursive subquery] t.route || ',' || f.destination, t.totalcost + f.cost FROM trips t, flights f WHERE t.destination = f.origin))SELECT route, totalcost [final query]FROM tripsWHERE destination = 'NewYork';

Problémy

porušení pravidla, že sloupce rekurzivního pododotazu nesmí být delsí než odpovídající sloupce inicializačního poddotazu

do sloupce route vkládáme výraz, který roste při každém zavolání rekurzivního poddotazu

ŘEŠENÍ: změníme datový typ u obou poddotazů (inicializační

i rekurzivní) na Varchar(50)

CAST výrazy

umožňuje změnit hodnotu z jednoho datového typu na jiný

CAST ( výraz AS datový typ ) definuje se délka, rozsah, přesnost

CAST (c1 + c2 AS Decimal(8,2))

CAST (name||address AS Varchar(255))

CAST výrazy

implicitní hodnoty jsou Decimal(5,0), Char(1), Graphic(1)

ostatní typy, pokud nejsou definované vlastnosti, při nemožnosti konverze – chyba

string delší je doplněn mezerami kratší se uřízne a vrátí warning message

Řešení

změníme datový typ u obou poddotazů (inicializační i rekurzivní) na Varchar(50)

v inicializačním poddotazu nahradíme druhý sloupec

CAST(destination AS Varchar(50)) v rekurzivním poddotaze

CAST(t.route || ',' || f.destination as Varchar(50))

Problém zacyklení

dotaz se nezastavi (dokud nevyčerpá prostředky), protože mapa je cyklický graf

pravidla bránící zacyklení1. vyřaď všechny letové úseky které letí od SF - počátek

letu

2. vyřaď všechny letové úseky které letí z NY - cíl letu

3. uvažuj jen lety s maximálně třemi úseky

Výsledný dotaz

WITH trips (destination, route, nseg, totalcost) AS

((SELECT destination,

CAST(destination AS Varchar(50)), 1, cost FROM flights WHERE origin = ‘SF'UNION ALL (SELECT f.destination

CAST(t.route || ',' || f.destination AS Varchar(50)),

t.nseg + 1, t.totalcost + f.cost

FROM trips t, flights f WHERE t.destination = f.originAND f.destination <> 'SF'

AND f.origin <> 'NY’AND t.nseg < 3))

SELECT route, totalcostFROM tripsWHERE destination = ‘NY'AND totalcost= (SELECT min(totalcost) FROM trips WHERE destination='NY');

Dotaz na nejmenší počet úseků

cesta s nejmenším počtem úseků změníme final query

SELECT route, totalcost

[final query]FROM tripsWHERE destination = 'NewYork'AND totalcost=

(SELECT min(nseg) FROM trips WHERE destination='NewYork');

Dotazy s více poddotazy

rekurzivní dotazy nejsou omezené jedním inicializačním nebo jedním rekurzivním poddotazem

všechny poddotazy jsou spojené pomocí UNION ALL

letadla + vlaky chceme se nejlevněji dostat z SF do NY 2 inicializační poddotazy + 2 rekurzivní poddotazy

Dotaz s více poddotazy

WITH trips (destination, route, nseg, totalcost) AS

((SELECT destination, CAST(destination

AS Varchar(50)), 1, cost FROM flights WHERE origin = ‘SF')UNION ALL

(SELECT destination, CAST(destination AS Varchar(50)), 1, cost FROM trains WHERE origin = 'SF')

UNION ALL (SELECT f.destination CAST(t.route || ',' || f.destination AS

Varchar(50)), t.nseg + 1, t.totalcost + f.cost FROM trips t, flights f WHERE t.destination =

f.origin AND f.destination <> 'SF' AND f.origin <> 'NewYork' AND t.nseg < 3)

Dotazy s více poddotazy

UNION ALL (SELECT x.destination

CAST(t.route || ',' || x.destination as Varchar(50)),

t.nseg + 1, t.totalcost + x.cost FROM trips t, trains x WHERE t.destination =

x.origin AND x.destination <> 'SF'

AND x.origin <> 'NY’ AND t.nseg < 3))

SELECT route, totalcost

FROM trips

WHERE destination = 'NY'

AND totalcost=

(SELECT min(totalcost)

FROM trips

WHERE destination='NY');

Další použití rekurze

Rekurzivní vkládání

tabulka je vytvořena a naplněna rekurzivním INSERT výrazem

tabulka NUMBERS obsahuje sloupce COUNTER a RANDOM, COUNTER bude obsahovat čísla od 1 do 1000 a RANDOM náhodná čísla od 1 do 1000 pomocí funkce rand()

Rekurzivní vkládání

CREATE TABLE numbers(counter Integer, random Integer);

INSERT INTO numbers(counter, random)WITH temp(n) AS

(VALUES(1)UNION ALL

SELECT n+1 FROM tempWHERE n < 1000)

SELECT n, integer(rand()*1000)FROM temp;

Rekurzivní vkládání

inicializační poddotaz je tvořen výrazem VALUES(1), určuje tabulku s jedním sloupcem a jedním řádkem obsahujícím 1

rekurzivní poddotaz vytváří sloupec 1000 po sobě jdoucích přirozených čísel

koncový SELECT (vnořený v INSERTU) generuje 1000 náhodných čísel pomocí funkce rand()

Shrnutí

1. dotaz tvoří UNION ALL, který se skládá z jednoho nebo více inicializačních a jednoho nebo více rekurzivních poddotazů

2. každý inicializační poddotaz musí být nerekurzivní3. rekurzivní poddotaz používá výraz ve kterém je

vložený4. rekurzivní poddotaz nesmí obsahovat sloupcové

funkce, SELECT DISTINCT, GROUP BY, HAVING

Shrnutí

5. sloupce rekurzivního poddotazu musí odpovídat (a nesmí být delší než) příslušnému sloupci inicializačního poddotazu

6. rekurzivní poddotaz musí specifikovat jak je každý řádek spočítán z již existujícího řádku

7. pokud data obsahují cykly, musí rekurzivní dotaz obsahovat pravidla pro zastavení

8. při psaní koncového dotazu se použije rekurzivní výraz a další predikáty (např. pro nalezení nejlepších řešení)

Reference

Don Chamberlin: Recursion in SQL: Tips and Techniques, May 1996

Frédéric BROUARD: Recursive Queries in SQL:1999 and SQL Server 2005, 2005 www.servercentral.com

Srini Venigalla: Expanding Recursive Opportunities with SQL UDFs in DB2 v 7.2, March 2005