Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 8 / b

Join on equal middle components, produce the outer pair, and eliminate duplicate outputs. Using the variant declarations from part (a):

def compose1[X, Y, Z](r: Rel1[X, Y], s: Rel1[Y, Z]): Rel1[X, Z] = {
  val joined = (for {
    (x, y) <- r.pairs
    (middle, z) <- s.pairs
    if y == middle
  } yield (x, z)).distinct
  new Rel1[X, Z] {
    val pairs: List[(X, Z)] = joined
  }
}

Every produced pair has a witness y with both required input pairs, proving soundness. Conversely, any witness for a composed pair occurs in the two input lists, so the nested traversal produces that pair; .distinct retains one occurrence, proving completeness. Thus the result represents $S\circ R$, with each pair listed once, even if either input lists duplicates or several witnesses yield the same outer pair. Equality of middle values is assumed to implement the relation's intended key equality. The nested join examines $|r.pairs||s.pairs|$ candidate pairs before duplicate elimination.