Notes from going through Time and Relational Theory by C.J. Date, Hugh Darwen and Nikos A. Lorentzos

relation.rb

require "set"

module ArrayExtras
  refine Array do
    def second
      self[1]
    end

    def split_at(i)
      [first(i), drop(i)]
    end

    def uncons
      [first, drop(1)]
    end
  end
end

module RangeExtras
  using ArrayExtras

  refine Range do
    def overlaps?(other)
      other.begin <= self.end && self.begin <= other.end
    end

    def meets?(other)
      self.end.succ == other.begin
    end

    def met_by?(other)
      other.meets?(self)
    end

    def merges_with?(other)
      overlaps?(other) || meets?(other) || met_by?(other)
    end

    def union(other)
      Range.new(
        [self.begin, other.begin].compact.min,
        [self.end, other.end].compact.max,
      )
    end
  end

  refine Array do
    # @example
    #   [(1..1), (4..7), (5..9), (2..2)].collapse
    #   #=> [(1..2), (4..9)]
    #   [2..2, 4..4, 5..5, 6..6, 7..7, 12..12, 14..14, 15..15, 16..16, 17..17]
    #   #=> [(2..2), (4..7), (12..12), (14..17)]
    def collapse
      return self if empty? || one?

      ls, rs = split_at(length / 2)
      collapse_merge(ls.collapse, rs.collapse)
    end

    # @example
    #   [(1..2), (4..9)].expand
    #   #=> [(1..1), (2..2), (3..3), (4..4), (5..5), (6..6), (7..7), (8..8), (9..9)]
    def expand
      flat_map do |range|
        range.to_a.map do |elem|
          Range.new(elem, elem)
        end
      end
    end

    private

    def collapse_merge(as, bs)
      if as.empty?
        return bs
      elsif bs.empty?
        return as
      end

      a, rest_as = as.uncons
      mergeable_bs, rest_bs = bs.partition do |b|
        a.merges_with?(b)
      end

      [mergeable_bs.reduce(a, &:union)] + collapse_merge(rest_as, rest_bs)
    end
  end
end

class Tuple < Hash
  # @example
  #   Tuple[foo: "Foo", bar: 1, baz: true].union(Tuple[qux: false, qui: nil, bar: 1])
  #   #=> Tuple[foo: "Foo", bar: 1, baz: true, qux: false, qui: nil]
  #
  #   Tuple[foo: "Foo", bar: 1, baz: true].union(Tuple[qux: false, qui: nil, bar: 2])
  #   #=> nil
  def union(other)
    Tuple[merge(other)] if unionable?(other)
  end

  # @example
  #   Tuple[foo: "Foo", bar: 1, baz: true].project(:bar, :baz)
  #   #=> Tuple[bar: 1, baz: true]
  def project(*attributes)
    Tuple[slice(*attributes)]
  end

  # @example
  #   Tuple[foo: "Foo", bar: 1, baz: true].all_but(:bar, :baz)
  #   #=> Tuple[foo: "Foo"]
  def all_but(*attributes)
    clone.tap do |copy|
      attributes.each do |attribute|
        copy.delete(attribute)
      end
    end
  end

  private

  def unionable?(other)
    common_keys = keys & other.keys
    project(*common_keys) == other.project(*common_keys)
  end
end

class Relation < Set
  using ArrayExtras
  using RangeExtras

  # @example
  #   books = Relation[
  #     Tuple[book_id: 1, book_name: 'Anna Karenina', author_id: 1],
  #     Tuple[book_id: 2, book_name: 'War and Peace', author_id: 1],
  #     Tuple[book_id: 3, book_name: 'Madame Bovary', author_id: 2],
  #     Tuple[book_id: 4, book_name: 'A Sentimental Education', author_id: 2],
  #   ]
  #
  #   books.attributes
  #   #=> Set[:book_id, :book_name, :author_id]
  def attributes
    Set[*flat_map(&:keys)]
  end

  # @example
  #   books = Relation[
  #     Tuple[book_id: 1, book_name: 'Anna Karenina', author_id: 1],
  #     Tuple[book_id: 2, book_name: 'War and Peace', author_id: 1],
  #     Tuple[book_id: 3, book_name: 'Madame Bovary', author_id: 2],
  #     Tuple[book_id: 4, book_name: 'A Sentimental Education', author_id: 2],
  #   ]
  #
  #   books.project(:author_id, :book_id)
  #   #=>  Relation[Tuple[author_id: 1, book_id: 1], Tuple[author_id: 1, book_id: 2], Tuple[author_id: 2, book_id: 3], Tuple[author_id: 2, book_id: 4]]
  def project(*attributes)
    Relation.new(map { |tuple| tuple.project(*attributes) })
  end

  def extend
    Relation.new(map { |tuple| tuple.merge(yield tuple.clone) })
  end

  def restrict(&block)
    Relation[*select(&block)]
  end

  def d_union(other)
    result = self + other
    return if result.length != length + other.length

    result
  end

  def i_minus(other)
    result = self - other
    return if result.length == length

    result
  end

  # @example
  #   books = Relation[
  #     Tuple[book_id: 1, book_name: 'Anna Karenina', author_id: 1],
  #     Tuple[book_id: 2, book_name: 'War and Peace', author_id: 1],
  #     Tuple[book_id: 3, book_name: 'Madame Bovary', author_id: 2],
  #     Tuple[book_id: 4, book_name: 'A Sentimental Education', author_id: 2],
  #   ]
  #   authors = Relation[
  #     Tuple[author_id: 1, author_name: 'Leo Tolstoy'],
  #     Tuple[author_id: 2, author_name: 'Gustave Flaubert'],
  #   ]
  #
  #   books.join(authors)
  #   #=> Relation[Tuple[book_id: 1, book_name: "Anna Karenina", author_id: 1, author_name: "Leo Tolstoy"], Tuple[book_id: 2, book_name: "War and Peace", author_id: 1, author_name: "Leo Tolstoy"], Tuple[book_id: 3, book_name: "Madame Bovary", author_id: 2, author_name: "Gustave Flaubert"], Tuple[book_id: 4, book_name: "A Sentimental Education", author_id: 2, author_name: "Gustave Flaubert"]]
  #
  #   books.join(authors) == authors.join(books)
  #   #=> true
  def join(other)
    Relation.new(
      to_a
        .product(other.to_a)
        .map { |tuple_a, tuple_b| tuple_a.union(tuple_b) }
        .compact
    )
  end

  # Hrm, this is a more general intersection? (*) It looks like intersection where only the subset of attributes in self is taken ino account.
  def matching(other)
    join(other).project(attributes)
  end

  def not_matching(other)
    self - matching(other)
  end

  # zero : forall header. Relation header
  def self.zero
    Relation[]
  end

  # + : forall header. Relation header -> Relation header -> Relation header
  def +(other)
    union(other)
  end

  # * : Relation {} # Ah, ha!
  def self.one
    Relation[{}]
  end

  # * : forall header. Relation header -> Relation header -> Relation header
  def *(other)
    join(other)
  end

  # @example
  #   books = Relation[
  #     Tuple[book_id: 1, book_name: 'Anna Karenina', author_id: 1],
  #     Tuple[book_id: 2, book_name: 'War and Peace', author_id: 1],
  #     Tuple[book_id: 3, book_name: 'Madame Bovary', author_id: 2],
  #     Tuple[book_id: 4, book_name: 'A Sentimental Education', author_id: 2],
  #   ]
  #   books.project(:author_id, :book_id).group(:book_id, :book_id_rel)
  #   #=> Relation[Tuple[author_id: 1, book_id_rel: Relation[Tuple[book_id: 1], Tuple[book_id: 2]]], Tuple[author_id: 2, book_id_rel: Relation[Tuple[book_id: 3], Tuple[book_id: 4]]]]
  def group(attributes, as)
    Relation.new(map { |tuple| [tuple.all_but(*attributes), tuple.project(*attributes)] }
      .group_by(&:first)
      .map { |(a, bs)| a.merge(as => Relation.new(bs.map(&:second))) })
  end

  def ungroup(attribute)
    Relation.new(flat_map do |tuple|
      tuple
        .fetch(attribute)
        .map { |nested_tuple| tuple.all_but(attribute).merge(nested_tuple) }
    end)
  end

  # @example
  #   sno_during = Relation[
  #     Tuple[sno: 'S2', during: (2..4)],
  #     Tuple[sno: 'S2', during: (3..5)],
  #     Tuple[sno: 'S4', during: (2..5)],
  #     Tuple[sno: 'S4', during: (4..6)],
  #     Tuple[sno: 'S4', during: (9..10)],
  #   ]
  #   sno_during.unpack(:during)
  #   #=> Relation[Tuple[sno: "S2", during: 2..2], Tuple[sno: "S2", during: 3..3], Tuple[sno: "S2", during: 4..4], Tuple[sno: "S2", during: 5..5], Tuple[sno: "S4", during: 2..2], Tuple[sno: "S4", during: 3..3], Tuple[sno: "S4", during: 4..4], Tuple[sno: "S4", during: 5..5], Tuple[sno: "S4", during: 6..6], Tuple[sno: "S4", during: 9..9], Tuple[sno: "S4", during: 10..10]]
  def unpack(*attributes)
    attributes.reduce(self) do |acc, attribute|
      acc.unpack_single(attribute)
    end
  end

  def unpack_single(attribute)
    r1 = group(attribute, :x)
    r2 = r1.extend do |tuple|
      {
        x: tuple[:x].map { |x|
          x[attribute]
        }.expand.map { |expanded|
          { attribute => expanded }
        },
      }
    end
    r2.ungroup(:x)
  end

  # @example
  #   sno_during = Relation[
  #     Tuple[sno: 'S2', during: (2..4)],
  #     Tuple[sno: 'S2', during: (3..5)],
  #     Tuple[sno: 'S4', during: (2..5)],
  #     Tuple[sno: 'S4', during: (4..6)],
  #     Tuple[sno: 'S4', during: (9..10)],
  #   ]
  #   sno_during.pack(:during)
  #   #=> Relation[Tuple[sno: "S2", during: 2..5], Tuple[sno: "S4", during: 2..6], Tuple[sno: "S4", during: 9..10]]
  def pack(*attributes)
    attributes.reduce(unpack(*attributes)) do |acc, attribute|
      acc.pack_single(attribute)
    end
  end

  def pack_single(attribute)
    r1 = group(attribute, :x)
    r2 = r1.extend do |tuple|
      {
        x: tuple[:x].map { |x|
          x[attribute]
        }.collapse.map { |collapsed|
          { attribute => collapsed }
        },
      }
    end
    r2.ungroup(:x)
  end

  def using(*attributes)
    Using.new(self, *attributes)
  end

  class Using
    def initialize(relation, *attributes)
      @relation = relation
      @attributes = attributes
    end

    # @example
    #   r1 = Relation[
    #     Tuple[a: (2..4)]
    #   ]
    #   r2 = Relation[
    #     Tuple[a: (3..3)]
    #   ]
    #   r1.using(:a) - r2
    #   #=> Relation[Tuple[a: 2..2], Tuple[a: 4..4]]
    def -(other)
      on_operator(:-, other)
    end

    # @example
    #   r1 = Relation[
    #     Tuple[a: 2..2],
    #     Tuple[a: 4..4]
    #   ]
    #   r2 = Relation[
    #     Tuple[a: 3..3],
    #     Tuple[a: 4..4]
    #   ]
    #   r1.using(:a).union(r2)
    #   #=> Relation[Tuple[a: 2..4]]
    def union(other)
      on_operator(:union, other)
    end

    def join(other)
      on_operator(:join, other)
    end

    # @example
    #   r1 = Relation[
    #     Tuple[a: 1..7],
    #     Tuple[a: 12..12],
    #     Tuple[a: 14..17]
    #   ]
    #   r2 = Relation[
    #     Tuple[a: 2..2],
    #     Tuple[a: 4..7],
    #     Tuple[a: 10..17]
    #   ]
    #   r1.using(:a) * r2
    #   #=> Relation[Tuple[a: 2..2], Tuple[a: 4..7], Tuple[a: 12..12], Tuple[a: 14..17]]
    def *(other)
      join(other)
    end

    # @example
    #   s_during = Relation[
    #     Tuple[sno: 'S2', during: (1..3)],
    #     Tuple[sno: 'S2', during: (5..9)]
    #   ]
    #   s_during.restrict { |tuple| (3..7).cover?(tuple[:during]) }
    #   #=> Relation[]
    #   s_during.using(:during).restrict { |tuple| (3..7).cover?(tuple[:during]) }
    #   #=> Relation[Tuple[sno: 'S2', during: 3..3], Tuple[sno: 'S2', during: 5..7]]
    #   s_during.using(:during).restrict { |tuple| tuple[:during] == (2..2) || tuple[:during] == (5..5) || tuple[:during] == (7..7) }
    #   #=> Relation[Tuple[sno: 'S2', during: 2..2], Tuple[sno: 'S2', during: 5..5], Tuple[sno: 'S2', during: 7..7]]
    def restrict(&block)
      @relation.unpack(*@attributes).restrict(&block).pack(*@attributes)
    end

    # @example
    #   sp_during = Relation[
    #     Tuple[sno: 'S1', pno: 'P1', during: 4..10],
    #     Tuple[sno: 'S1', pno: 'P2', during: 5..10],
    #     Tuple[sno: 'S1', pno: 'P3', during: 9..10],
    #     Tuple[sno: 'S1', pno: 'P4', during: 5..10],
    #     Tuple[sno: 'S1', pno: 'P5', during: 4..10],
    #     Tuple[sno: 'S1', pno: 'P6', during: 6..10],
    #     Tuple[sno: 'S2', pno: 'P1', during: 2..4],
    #     Tuple[sno: 'S2', pno: 'P1', during: 8..10],
    #     Tuple[sno: 'S2', pno: 'P2', during: 3..3],
    #     Tuple[sno: 'S2', pno: 'P2', during: 9..10],
    #     Tuple[sno: 'S3', pno: 'P2', during: 8..10],
    #     Tuple[sno: 'S4', pno: 'P2', during: 6..9],
    #     Tuple[sno: 'S4', pno: 'P4', during: 4..8],
    #     Tuple[sno: 'S4', pno: 'P5', during: 5..10],
    #   ]
    #   sp_during.using(:during).project(:sno, :during)
    #   #=> Relation[Tuple[sno: "S1", during: 4..10], Tuple[sno: "S2", during: 2..4], Tuple[sno: "S2", during: 8..10], Tuple[sno: "S3", during: 8..10], Tuple[sno: "S4", during: 4..10]]
    def project(*attributes)
      @relation.unpack(*@attributes).project(*attributes).pack(*@attributes)
    end

    private

    def on_operator(operator, other)
      @relation
        .unpack(*@attributes)
        .public_send(operator, other.unpack(*@attributes))
        .pack(*@attributes)
    end
  end
end

class RelationVariable
  attr_reader :relation

  class KeyConstraintError < StandardError
  end

  # @attr source [RelationVariable]
  # @attr attributes [Array<[Symbol]>]
  # @attr references [RelationVariable]
  ForeignKey = Struct.new(
    :source,
    :attributes,
    :references,
    keyword_init: true,
  )

  class ForeignKeyConstraintError < StandardError
  end

  @@foreign_keys = []

  # @param keys [Array<[Set<[Symbol]>]>]
  # @param foreign_keys [Array<[{ attributes: [Array<[Symbol]>], references: [RelationVariable] }]>]
  def initialize(keys: [], foreign_keys: [])
    @keys = keys
    @@foreign_keys += foreign_keys.map do |foreign_key|
      ForeignKey.new(source: self, **foreign_key)
    end
    @relation = Relation.new
  end

  # @example
  #  rv = RelationVariable.new
  #  rv.insert(Tuple[foo: "Bar"])
  #  rv.relation
  #  #=> Relation[Tuple[foo: "Bar"]]
  #  rv_with_key = RelationVariable.new(keys: [Set[:foo]])
  #  rv_with_key.insert(Tuple[foo: "Foo", bar: "Bar"])
  #  rv_with_key.insert(Tuple[foo: "Foo", bar: "Qux"])
  #  #=> raise KeyConstraintError, "Key violation"
  def insert(tuple)
    updated = @relation + Relation[tuple]
    assert_candidate_relation_valid!(updated)
    @relation = updated
  end

  # @example
  #  rv = RelationVariable.new
  #  rv.insert(Tuple[foo: "Bar"])
  #  rv.insert(Tuple[foo: "Baz"])
  #  rv.relation
  #  #=> Relation[Tuple[foo: "Bar"], Tuple[foo: "Baz"]]
  #  rv.delete {|tuple| tuple[:foo] == "Bar"}
  #  rv.relation
  #  #=> Relation[Tuple[foo: "Baz"]]
  #  rv_with_foreign_key = RelationVariable.new(foreign_keys: [{ attributes: Set[:foo], references: rv }])
  #  rv_with_foreign_key.insert(Tuple[foo: "Bar", bar: "Qux"])
  #  #=> raise ForeignKeyConstraintError, "Foreign key violation"
  #  rv_with_foreign_key.insert(Tuple[foo: "Baz", bar: "Qux"])
  #  rv.delete { |tuple| tuple[:foo] == "Baz" }
  #  #=> raise ForeignKeyConstraintError, "Foreign key violation"
  #  rv_with_foreign_key.delete {|tuple| tuple[:foo] == "Baz"}
  #  rv.delete { |tuple| tuple[:foo] == "Baz" }
  #  rv.relation
  #  #=> Relation[]
  #  rv_with_foreign_key.relation
  #  #=> Relation[]
  def delete(&block)
    updated = @relation - @relation.restrict(&block)
    assert_candidate_relation_valid!(updated)
    @relation = updated
  end

  # @example
  #  rv = RelationVariable.new
  #  rv.insert(Tuple[foo: "Bar"])
  #  rv.insert(Tuple[foo: "Baz"])
  #  rv.relation
  #  #=> Relation[Tuple[foo: "Bar"], Tuple[foo: "Baz"]]
  #  rv.update(where: -> (tuple) { tuple[:foo] == "Bar" }) {|tuple| Tuple[foo: tuple[:foo].downcase]}
  #  rv.relation
  #  #=> Relation[Tuple[foo: "bar"], Tuple[foo: "Baz"]]
  #  rv_with_key = RelationVariable.new(keys: [Set[:foo]])
  #  rv_with_key.insert(Tuple[foo: "Foo", bar: "Bar"])
  #  rv_with_key.insert(Tuple[foo: "foo", bar: "Qux"])
  #  rv_with_key.update(where: -> (tuple) { tuple[:bar] == "Bar" }) {|tuple| Tuple[foo: tuple[:foo].downcase]}
  #  #=> raise KeyConstraintError, "Key violation"
  def update(where: proc { }, &block)
    relevant = @relation.restrict(&where)
    updated = (@relation - relevant) + relevant.extend(&block)
    assert_candidate_relation_valid!(updated)
    @relation = updated
  end

  private

  def assert_candidate_relation_valid!(candidate_relation)
    assert_keys_unique!(candidate_relation)
    assert_foreign_keys_maintained!(candidate_relation)
  end

  def assert_keys_unique!(candidate_relation)
    @keys.each do |key|
      tuples = candidate_relation.to_a.map { |tuple| tuple.slice(*key) }
      if tuples.length > Set.new(tuples).length
        raise KeyConstraintError, "Key violation"
      end
    end
  end

  def assert_foreign_keys_maintained!(candidate_relation)
    as_source = @@foreign_keys
      .select { |fk| fk.source == self }
      .map { |fk| [candidate_relation, fk.attributes, fk.references.relation] }

    as_reference = @@foreign_keys
      .select { |fk| fk.references == self }
      .map { |fk| [fk.source.relation, fk.attributes, candidate_relation] }

    (as_source + as_reference).each do |(source, attributes, references)|
      fk_values = source.project(*attributes)
      k_values = references.project(*attributes)
      if (fk_values - k_values).any?
        raise ForeignKeyConstraintError, "Foreign key violation"
      end
    end
  end
end