Recursive SQL and graph theory

Preface

Seems very strange but it is possible to use "recursion" in SQL statements. By recursion I mean the method of defining function (or object) which inside its definition refers to itself. To write recursive SQL statement it is necessary to follow strict rules : http://msdn.microsoft.com/en-us/library/ms186243.aspx


Example
Consider simple table containing distances between cities.

CREATE TABLE CONNECTION (CITY_FROM VARCHAR(100), CITY_TO VARCHAR(100), DISTANCE DECIMAL);

delete from connection;
insert into connection values ('Warszawa', 'Augustów', 242);
insert into connection values ('Warszawa', 'Suwałki', 267);
insert into connection values ('Warszawa', 'Olsztyn', 192);
insert into connection values ('Augustów', 'Suwałki', 32);

insert into connection values ('Warszawa', 'Płock', 103);
insert into connection values ('Płock', 'Grudziądz', 133);
insert into connection values ('Grudziądz', 'Gdańsk',106);

insert into connection values ('Warszawa', 'Mława', 116);
insert into connection values ('Mława','Elbląg', 144);
insert into connection values ('Elbląg', 'Gdańsk', 58);

Now "recursive" statement:

WITH path (city_from, city_to, distance, stops)
    AS ( SELECT  f.city_from,  f.city_to, f.distance, 0
             FROM connection f
             WHERE  city_from='Warszawa'
          UNION ALL
             SELECT p.city_from, f.city_to,   
                    p.distance+f.distance, p.stops+1
             FROM connection f, path p
             WHERE p.city_to=f.city_from )
    SELECT substr(pa.city_from,1,20), substr(pa.city_to,1,20), min(distance) FROM path pa GROUP BY (pa.city_from, pa.city_to);

How it runs ?
The beginning is the statement before UNION ALL. It selects all direct connection from Warszawa.

• 'Warszawa', 'Augustów', 242;
• 'Warszawa', 'Suwałki', 267;
• 'Warszawa', 'Olsztyn', 192
• 'Warszawa', 'Płock', 103
• 'Warszawa', 'Mława', 116

Then runs the second part of UNION ALL command. It adds all direct connections of the destinations selected in the previous step. This time it is:

• 'Augustów', 'Suwałki', 32
• 'Płock', 'Grudziądz', 133
• 'Mława','Elbląg', 144

This second part is  "recursive" - it uses 'path'  table which is created in the whole statements.
The third and next steps are repetition of the second step. The only difference is that rows taken are rows added in the previous step (not the whole path table). This time following destinations will be added.

• 'Elbląg', 'Gdańsk', 58
• 'Grudziądz', 'Gdańsk',106

The fourth step will bring no rows - there is no destination for 'Gdańsk'  and it ends our 'recursion'.
The final statement selects minimal distance between Warszawa and all cities found.

Warszawa             Augustów                242,
Warszawa             Elbląg                  260,
Warszawa             Gdańsk                  318,
Warszawa             Grudziądz               236,
Warszawa             Mława                   116,
Warszawa             Olsztyn                 192,
Warszawa             Płock                   103,
Warszawa             Suwałki                 267,

During evaluation also 'stops' column is created, although not used. It contains number of cities visited during journey from 'Warszawa' to destination. In the final statement, by replacing minimal(distance) with minimal(stops) we can choose paths with having minimal number of nodes.

What this 'recursion SQL' has in common with graph theory ?
Answer is simple. Connection table describes nodes of directed graph. 'Recursive' statement is an implementation of Breadth-first_search. Distance is a weigth assigned to a node and our 'recursive' statement implements the algorithm of finding the Shortest path problem Shortest_path_problem

Danger.
Unfortunately, there is also a dark side oh this moon.
Consider connection table:

insert into connection values ('Warszawa', 'Augustów', 242);
insert into connection values ('Augustów', 'Warszawa', 242);

Our 'recursive' statement will run infinitely on that table. Using terminology from graph teory our statement is invalid if there is a 'cycle' in the graph, it is valid only for graphs without cycles. What's more important - there is no simply workaround to this problem.

Byliśmy na koncercie

Byliśmy 2 kwietnia 2010 roku na koncercie w ramach tegorocznego Wielkanocnego Festiwalu Ludwiga van Beethovena.

Requiem Hectora Berlioza skomponowane w 1837 to utwór rzadko wykonywany. Wymaga ogromnego składu (nawet do 600 głosów) chóru i orkiestry i to jest zapewne przyczyną rzadkiego pojawiania się tego dzieła w repertuarze. Koncert w Teatrze Wielkim był wyjątkową okazją posłuchania tej muzyki na żywo.

Koncert okazał się jednak rozczarowaniem. Nie potrafię powiedzieć, czy to problem samej partytury czy wykonawstwa. Głównie rozczarowały partie chóralne, zwłaszcza gdy chór śpiewa 'a capella'.  Śpiew brzmiał bardzo słabo, gdzieś się gubił w ogromnej sali Teatru Wielkiego. Czegoś tutaj zabrakło, większej werwy, lepszego przygotowania, może dyrygent (Charles Dutoit) nie potrafił narzucić swojej wizji tego dzieła ogromnemu chórowi (blisko 200 śpiewaków).

Wspaniale zabrzmiała środkowa część dzieła - Lacrymosa. Tutaj chór - śpiewający razem z orkiestrą - wyraźnie się odnalazł i dało to doskonały efekt.

Jedyna partia solowa ma miejsce w Sanctus. Dobrym zamysłem było umieszczenie solisty (Paul Groves) wśród orkiestry i gdy śpiewał "Sanctus benedictus" brzmiało to z pewnej oddali przypominając głos z nieba.

Połączone siły: sławnego dyrygenta, doskonałego solisty, podwójnego chóru Filharmonii Warszawskiej i Teatru Wielkiego, znakomitej orkiestry Sinfonia Varsovia  wzmocnionej o potężną sekcję perkusyjną poniosły jednak ewidentnie porażkę w starciu z monumentalnym dziełem Berlioza. Partytura została wykonana, ale - za wyjątkiem kilku fragmentów - nic nie odcisnęło się w pamięci.