Relation algebra with multi-relations

Abstract

This report proposes a theory of multi-relations, which are similar to normal mathematical relations, except for the fact that each tuple has a given multiplicity. It is shown that most of the set-oriented operations on relations, such as union and intersection can be generalised (in the same way in which sets can be generalised to multisets). The typical relational operations of composition and transposition and the theory of ‘lifting’ can be generalised too. Several alternative representations are discussed, including ternary relations, and multisets of tuples. Multi-relations can be visualised as directed graphs where each edge is labeled with a number. Alternatively, the multiplicity could be visualised by giving the edge a certain thickness.

The approach is helpful in situations where one is not satisfied with the knowledge that there is a certain connection ('uses', 'calls'etc.) between two units (components, modules, processes), but where one wants to have quantitative information on how many sub-connections exist.

Keywords:

• Software structuring
• graph algorithms
• reverse engineering
• formal specification
• relation algebra
• Galois connections
• algebra
• abstract data types
• databases

C.R. Categories::

• G.2.2
• F.4.3