This directory contains CSRI Technical Report #345 entitled
Binary Relational Algebra
Applied to Software Architecture
by
Richard C. Holt
holt@csri.toronto.edu
Computer Systems Research Institute
Department of Computer Science
University of Toronto
Abstract
The architecture of a piece of software refers
to its structure as given by its components and their
interconnections. An architectural style is a set of
commonalities among the structures of a number of software
systems. We are concerned with architectures that
are characterized by directed graphs. The graphs we are
interested in contain edges that are "typed" or "colored",
which means that there are a finite number of different
kinds of edges. The nodes in the graphs represent entities
such as procedures, modules and subsystems. The edges
in the graphs represent relations among these entities,
such as "calls", "accesses", "imports", "includes", and
"uses".
This paper shows how binary relational algebra, as
defined by Tarski and refined by Schmidt and others, can
be used to formalize this type of architectural style. We
show how this algebraic approach can be used to give
constraints among the relations in an architecture. For
example, we can use a relational inequality to formalize
the rule that: items within a object can be used from outside
the object only if they have been exported from the object.
We have developed a prototype "relational calculator", which
reads data bases that represent sets of relations, and which
allows us to compute new relations and sets. We have used
this calculator in a reverse engineering project to determine
the clients of a given subsystem, based on relations for
containment and usage.
We formalize the concept of an architectural style in terms of
rules that limit the use of relations. We propose a form for
rules in which each rule is written as a relational inequality.
We show that such rules are monotonic, which implies that adding
new edges can allow more edges, but cannot disallow previously
allowed edges.
-----------------------------------------------------------------
If you have the uncompress program, get the 345.ps.Z file.
Transfer this file in binary mode, uncompress it and then
print it out on a PostScript printer.
If you do not have uncompress, get the 345.ps file in
ascii mode, and print it on a PostScript printer.
If you have any problems, please contact holt@csri.toronto.edu.