Skip to content

Instantly share code, notes, and snippets.

@bradparker
Last active June 1, 2022 04:22
Show Gist options
  • Save bradparker/243e5537685a1c674961b7d8fa07b269 to your computer and use it in GitHub Desktop.
Save bradparker/243e5537685a1c674961b7d8fa07b269 to your computer and use it in GitHub Desktop.
Notes from going through Time and Relational Theory by C.J. Date, Hugh Darwen and Nikos A. Lorentzos
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment