title: Language features to implement relational algebra
body: <p>I've been trying to encode a relational algebra in Scala (which to my knowlege has one of the most advanced type systems) and just don't seem to find a way to get where I want.</p>
  
  <p>As I'm not that experienced with the academic field of programming language design I don't really know what feature to look for.</p>
  
  <p>So what language features would be needed, and what language has those features, to implement a statically verified relational algebra?</p>
  
  <p>Some of the requirements:
  A Tuple is a function mapping names from a statically defined set of valid names for the tuple in question to values of the type specified by the name. Lets call this name-type set the domain.</p>
  
  <p>A Relation is a Set of Tuples with the same domain such that the range of any tuple is uniqe in the Set</p>
  
  <p>So far the model can eaisly be modeled in Scala simply by</p>
  
  <pre><code>trait Tuple
  trait Relation[T&lt;Tuple] extends Set[T]
  </code></pre>
  
  <p>The vals, vars and defs in Tuple is the name-type set defined above. But there should'n be two defs in Tuple with the same name. Also vars and impure defs should probably be restricted too.</p>
  
  <p>Now for the tricky part:</p>
  
  <p>A join of two relations is a relation where the domain of the tuples is the union of the domains from the operands tuples. Such that only tuples having the same ranges for the intersection of their domains is kept.</p>
  
  <pre><code>def join(r1:Relation[T1],r2:Relation[T2]):Relation[T1 with T2]
  </code></pre>
  
  <p>should do the trick.</p>
  
  <p>A projection of a Relation is a Relation where the domain of the tuples is a subset of the operands tuples domain.</p>
  
  <pre><code>def project[T2](r:Relation[T],?1):Relation[T2&gt;:T]
  </code></pre>
  
  <p>This is where I'm not sure if it's even possible to find a sollution. What do you think? What language features are needed to define project?</p>
  
  <p>Implied above offcourse is that the API has to be usable. Layers and layers of boilerplate is not acceptable.</p>