Towards a formal framework for heterogeneous relation algebra

We define a language for polymorphic typed relations and introduce a typing discipline for terms of that language. A modular type inference system for the derivation of the most general type of a term is presented and correct ness and well as weak completeness of the type inference system w.r.t. the typing discipline is proven. Finally, we give an interpretation of our lang uage based on the classical model of relation algebra. (C) 1999 Elsevier Sc ience Inc. All rights reserved.