In relational algebra, a recursive relation R is defined by an equation of the form R = f(R), where f(R) is a positive relational algebra expression. Such an equation can be solved by applying a general closure operator. Although some optimization is possible, the performance obtained using this approach is very dependent on the form of the equation which defines R. Principally for this reason, we have developed specialized closure operators for relations which are solutions to problems of practical importance such as transitive closure, accessibility, shortest path, bill-of-materials, and deductions by containment comparisons. / This approach has led to the following general results: (1) design, classification, and analysis of many iterative methods for evaluating recursive relations, as well as analysis of experimental results; (2) formalization of the concept of iterative evaluation of a relation; (3) demonstration that domain algebra can be used to solve problems of concatenation and aggregation of the information associated with a recursive structure; (4) proof that relational division and general containment joins are left-monotone. / More specific results consist of a collection of original algorithms which run well on secondary storage, as shown by simulations. Among them, we wish to emphasize the differencing logarithmic transitive closure (TC) algorithms, which are superior to the previously known relational TC algorithms, and the shortest path algorithms, which are in fact generic algorithms for path algebra problems.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.75694 |
| Date | January 1987 |
| Creators | Clouâtre, André |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 000665188, proquestno: AAINL46055, Theses scanned by UMI/ProQuest. |
Page generated in 0.0025 seconds