U.Minho Transposing Relations: from Maybe Functions to Hash Tables
[ DI/UM ]

by J.N. Oliveira, C.J. Rodrigues
In MPC'07 : Seventh International Conference on Mathematics of Program Construction, 12-14 July, 2004, Stirling, Scotland, UK (Organized in conjunction with AMAST'04), volume 3125 of Lecture Notes in Computer Science, pages 334-356. Springer, 2004.
© Springer 2004, ISBN 3-540-22380-0
Paper: [available as a 195K pdf file]

Abstract: Functional transposition is a technique for converting relations into functions aimed at developing the relational algebra via the algebra of functions.

This paper attempts to develop a basis for generic transposition. Two instances of this construction are considered, one applicable to any relation and the other applicable to simple relations only.

Our illustration of the usefulness of the generic transpose takes advantage of the free theorem of a polymorphic function. We show how to derive laws of relational combinators as free theorems of their transposes. Finally, we relate the topic of functional transposition with the hashing technique for efficient data representation.

  author    = {J.N.\ Oliveira and
               C.J.\ Rodrigues},
  title     = {Transposing Relations: From Maybe Functions to Hash Tables.},
  booktitle = {MPC},
  year      = {2004},
  pages     = {334-356},
  ee        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3125{\&}spage=334},
  crossref  = {conf/mpc/2004},
  bibsource = {DBLP, http://dblp.uni-trier.de}