An exercise in the structured design of complex algorithms in (extensions of) SQL

From time to time developers of (database) applications will encounter, explicitly or implicitly, structures such as trees, graphs, and networks. Such applications can for instance relate to bills of material, organisation charts, networks of (rail)roads, networks of conduit pipes, telecom -networks, and data dictionaries. Algorithms on such data structures often ask for recursion or iteration of which the number of repetitions is unknown beforehand. Such algorithms are usually programmed in a third generation language (3GL) and are therefore typically "record-at- a-time". Extensions of SQL with procedures and "control of flow" constructions such as if-then-else and while make it possible to solve such graph problems completely (and compactly) on 4GL-level. Actually, such SQL-extensions already exist for some time in several commercially available database management systems. In this paper we will work out the idea of graph algorithms on 4GL-level starting with the "standard" recursive graph problem of the computation of the set of all paths in a graph. It will also be shown that the computation of the paths themselves can easily be extended with the computation of additional path properties. Such algorithms operate essentially different from the algorithms on 3GL-level. One of the advantages of our approach is that it makes the development of ad hoc queries in such (recursive) application areas considerably easier (i.e., both simpler and faster), which in turn facilitates the development of the MIS-part of information systems in those application areas. Even on 4GL-level we are able to influence the efficiency of our graph algorithms. We will therefore present some improvements on our algorithms, all leading to successively better results. It turns out that our intuition regarding the correctness (and the termination) of these (subtle) "set-at-a-time" algorithms sometimes lags behind. Therefore we also pay special attention to the correctness and termination of the algorithms (using invariants). All programs turn out to be rather compact: they consist of only a few SQL-statements. This clearly contributes to the transparency of the structure of the algorithm and the maintainability of the software.