Rekursive Anfragen in SQL

Rupert Schneeberger

26.11.2010

Aufgabenstellung

Beispiel:

• Flugverbindungen

• Anzeige von Strecken mit UmsteigemoglichkeitenLINIENFLUG

Abflug AnkunftWien FrankfurtFrankfurt LondonWien BudapestWien VenedigVenedig RomWien ZurichZurich ParisParis Madrid

Madrid Zurich

Relationenalgebra (SQL-92)

s e l e c t Abf lug , Ankunftfrom LINIENFLUGwhere Abf lug = ’Wien ’

unions e l e c t LF1 . Abf lug , LF2 . Ankunftfrom LINIENFLUG LF1 , LINIENFLUG LF2where LF1 . Abf lug = ’Wien ’ and LF1 . Ankunft = LF2 . Abf lug

unions e l e c t LF1 . Abf lug , LF3 . Ankunftfrom LINIENFLUG LF1 , LINIENFLUG LF2 , LINIENFLUG LF3where LF1 . Abf lug = ’Wien ’ and LF1 . Ankunft = LF2 . Abf lugand LF2 . Ankunft = LF3 . Abf lug

Problem: Abfragetiefe nur fest definierbar!

Rekursionsanfrage (SQL:1999)

Abhilfe mit with-Klausel:

with r e c u r s i v e r e k u r s i o n s t a b e l l e as (r e k u r s i v e r −an f rage−ausd ruck

)[ t r a v e r s i e r u n g s k l a u s e l ] [ z y k l e n k l a u s e l ]an f rage−ausd ruck

Initialisierung:

s e l e c t . . .from t a b e l l e where . . .union a l l

Rekursionsschritt:

s e l e c t . . .from t a b e l l e , r e k u r s i o n s t a b e l l ewhere r e k u r s i o n s b e d i n g ung

Anwendung auf Beispiel

with r e c u r s i v e FLUGSTRECKE( Abf lug , Ankunft ) as (s e l e c t Abf lug , Ankunftfrom LINIENFLUGwhere Abf lug = ’Wien ’

union a l ls e l e c t FS . Abf lug , FL . Ankunftfrom FLUGSTRECKE FS , LINIENFLUG FLwhere FS . Ankunft = FL . Abf lug )

s e l e c t d i s t i n c t ∗ from FLUGSTRECKE

Abflug AnkunftWien FrankfurtWien BudapestWien VenedigWien Zurich

Abflug AnkunftWien FrankfurtWien BudapestWien VenedigWien ZurichWien LondonWien RomWien Paris

Abflug AnkunftWien FrankfurtWien BudapestWien VenedigWien ZurichWien LondonWien RomWien ParisWien Madrid

Traversierungsreihenfolge

• Manipulation der Reihenfolge

• Traversierungsklausel• in die Breite

s e a r c h b read th f i r s t by s p a l t e s e t pseudo−s p a l t e

• in die Tiefe

s e a r c h depth f i r s t by s p a l t e s e t pseudo−s p a l t e

with r e c u r s i v e FLUGSTRECKE( Abf lug , Ankunft , S t r e c k e ) as (s e l e c t Abf lug , Ankunft ,

Ab f lug | | ’− ’ | | Ankunft as S t r e c k efrom LINIENFLUGwhere Abf lug = ’Wien ’

union a l ls e l e c t FS . Abf lug , FL . Ankunft ,

S t r e c k e | | ’− ’ | | FL . Ankunft as S t r e c k efrom FLUGSTRECKE FS , LINIENFLUG FLwhere FS . Ankunft = FL . Abf lug )s e a r c h depth f i r s t by Ankunft s e t Re i h e n f o l g e

s e l e c t S t r e c k efrom FLUGSTRECKE o r d e r by Re i h e n f o l g e

StreckeWien-FrankfurtWien-Frankfurt-LondonWien-BudapestWien-VenedigWien-Venedig-RomWien-ZurichWien-Zurich-ParisWien-Zurich-Paris-Madrid

Sicherheit: Beschrankung

with r e c u r s i v e FLUGSTRECKE( Abf lug , Ankunft , Umste igen ) as (s e l e c t Abf lug , Ankunft , 0from LINIENFLUGwhere Abf lug = ’Wien ’

union a l ls e l e c t FS . Abf lug , FL . Ankunft , Umste igen + 1from FLUGSTRECKE FS , LINIENFLUG FLwhere FS . Ankunft = FL . Abf lug and Umsteigen < 2 )

s e l e c t d i s t i n c t ∗ from FLUGSTRECKE

Sicherheit: Zyklenerkennungwith r e c u r s i v e FLUGSTRECKE( Abf lug , Ankunft , S t r e c k e ) as (

s e l e c t Abf lug , Ankunft ,Ab f lug | | ’− ’ | | Ankunft as S t r e c k e

from LINIENFLUGwhere Abf lug = ’Wien ’

union a l ls e l e c t FS . Abf lug , FL . Ankunft ,

S t r e c k e | | ’− ’ | | FL . Ankunft as S t r e c k efrom FLUGSTRECKE FS , LINIENFLUG FLwhere FS . Ankunft = FL . Abf lug )c y c l e Ankunft s e t Zyk lu s to ’ ∗ ’ d e f a u l t ’− ’

s e l e c t St recke , Zyk lu s from FLUGSTRECKE

Strecke Zyklus...

...Wien-Zurich -Wien-Zurich-Paris -Wien-Zurich-Paris-Madrid -Wien-Zurich-Paris-Madrid-Zurich *

Unterstutzte RDBMS

• IBM DB2 (Windows & Unix), SQL Server 2005Weglassung des Schlusselworts recursive

• IBM DB2 (z/OS) gemaß Standard

• Oracle besitzt eigene Befehle fur hierarchische Anfragen