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

E.O. de Brock
Additional contact information
E.O. de Brock: Groningen University

No 97A46, Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management)

Abstract: 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.

Date: 1997
References: Add references at CitEc
Citations:

Downloads: (external link)
http://irs.ub.rug.nl/ppn/163866880 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://irs.ub.rug.nl/ppn/163866880 [302 Found]--> https://irs.ub.rug.nl/ppn/163866880 [302 Found]--> https://www.rug.nl/research/portal/publications/pub(ba2ca115-0251-4a52-af45-c60b99c94d60).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/pub(ba2ca115-0251-4a52-af45-c60b99c94d60).html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gro:rugsom:97a46

Access Statistics for this paper

More papers in Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management) Contact information at EDIRC.
Bibliographic data for series maintained by Hanneke Tamling ().