<commit_before>= Veritas

Simplifies querying of structured data using relational algebra

== Usage

  relation = Veritas::Relation.new([ [ :id, Integer ] ], [ [ 1 ] ])

  # Relational Operators
  # --------------------

  # projection
  new_relation = relation.project([ :a, :b, :c ])

  # removal
  new_relation = relation.remove([ :a, :b, :c ])

  # rename
  new_relation = relation.rename(:a => :b, :c => :d)

  # natural join
  new_relation = relation.join(other)        # OR relation + other

  # product
  new_relation = relation.product(other)     # OR relation * other

  # intersection
  new_relation = relation.intersect(other)   # OR relation & other

  # union
  new_relation = relation.union(other)       # OR relation | other

  # difference
  new_relation = relation.difference(other)  # OR relation - other

  # restriction
  new_relation = relation.restrict(relation.name.eq('other'))
  new_relation = relation.restrict { |r| r[:a].eq('other').and(r[:b].gte(42)) }

  # theta-join
  new_relation = relation.join(other, relation[:a].gte(other[:b]))
  new_relation = relation.join(other) { |r| r[:a].gte(r[:b]) }

  # NOTE: theta-join is effectively restricting a product of the relations

  # extend
  new_relation = relation.extend { |r| r.add(:total, r[:unit_price] * r[:quantity]) }
  new_relation = relation.extend { |r| r.add(:total) { |t| t[:unit_price] * t[:quantity] } }

  # summarize
  new_relation = relation.summarize(relation.project([ :name ])) { |r| r.add(:count, r[:name].count)
  new_relation = relation.summarize(relation.project([ :name ])) { |r| r.add(:count) { |acc, t| acc.to_i + 1 } }

  # Non-Relational Operators
  # ------------------------

  # returns a set that represents the relation header
  header = relation.header

  # simplifies and normalizes the relation operations
  optimized_relation = relation.optimize

  # a relation is Enumerable
  relation = relation.each { |tuple| ... }

  # order by attribute and direction
  new_relation = relation.order([ relation[:a].desc, relation[:b] ])
  new_relation = relation.order { |r| [ r[:a].desc, r[:b] ] }

  # reverse the relation (only allowed if ordered)
  new_relation = relation.reverse

  # offset (only allowed if ordered)
  new_relation = relation.drop(5)

  # limiting (only allowed if ordered)
  new_relation = relation.take(10)

  # get the first n tuples (only allowed if ordered)
  new_relation = relation.first     # default is 1
  new_relation = relation.first(5)

  # get the last n tuples (only allowed if ordered)
  new_relation = relation.last      # default is 1
  new_relation = relation.last(5)

  # CRUD Operators
  # --------------

  # can only modify relations that project all candidate keys for the base relations
  new_relation = relation.create(:a => 'test', :b => 'other', :c => 'yet another')
  new_relation = relation.update(:a => 'test', :b => 'other', :c => 'yet another')
  new_relation = relation.delete

== Goals

The purpose of this project is to expand my knowledge of relational algebra by attempting to implement a simple query system using the primitive operations defined in relational algebra.

Most of the design is heavily inspired from koios[https://github.com/carllerche/koios] and arel[https://github.com/rails/arel]. The reason I decided to write my own and not just build on top of those systems was not so much because I don't like the code/API in those projects, it's more because I wanted to gain a depth of understanding that can only be earned by trying to solve the problem myself.

I should note though that I don't plan to just re-implement those systems with a different API, or different internals, I plan to make something that surpasses them in several areas. For example, I want to be able to join information from multiple datastores and represent it as a single relation. I want to be able to insert, update or delete from that relation and have those changes propagated back to the right datastore. This is not an easy feat, since it is basically the writable view problem that RDBMS' struggle with. While I do think there are some cases where relations will become read-only, I think it will be possible to propagate writes properly in this manner. I certainly think for the current use cases in DataMapper this should work quite well.

The ability to join data from multiple datastores and have it presented in a consistent manner will solve one of the longest standing problems in DataMapper, namely how do we do cross repository joins. It should be possible to construct one query for one datastore, and then another query for another datastore and then join them. Since they are using different engines veritas will know to perform each query *natively* and then join the results in-memory seamlessly. It should also be possible to reorganize the queries so that as much work as possible is done natively as opposed to in-memory, which is considered the last resort.

Not only does this work nicely with associations, but it will allow DataMapper to perform mapping in a more powerful way. You'll be able to construct a join from multiple datastores, and set that as the base for your model. Each DM Resource would work as normal, but again writes could be propagated back to the appropriate datastore. You'd be able to split your data up between different datastores, but assemble it into one coherent view.

=== Phase 1: In-Memory Operations

The first phase of this project will be to implement all the operations listed below using in-memory data structures. I'm focusing on the API, and making sure the specs ensure the desired results are obtained from each operation.

This is 100% complete now.

=== Phase 2: RDBMS Engines

The second phase of this project will be to add an RDBMS based engine, and move the in-memory matching to it's own engine. I'll also be working on a system where if the primary engine cannot carry out some operation, that it first look at alternate forms (eg. using a join instead of an intersection), and then fall-back to in-memory matching. I also want to look at re-arranging queries so that all the operations that can be performed natively are "pushed down" the hierarchy and then the in-memory matching is performed last.

This is 30% complete. I am currently working on the veritas-sql-compiler[https://github.com/dkubb/veritas-sql-compiler] which is a visitor that walks the AST and produces SQL. Most of the Unary options work, and I am about to begin work on the binary options. Further refactoring will need to be performed to keep the Visitor class from growing huge (it has one method for each "node type").
<commit_msg>Updated status of veritas-sql-compiler (80% done)<commit_after>= Veritas

Simplifies querying of structured data using relational algebra

== Usage

  relation = Veritas::Relation.new([ [ :id, Integer ] ], [ [ 1 ] ])

  # Relational Operators
  # --------------------

  # projection
  new_relation = relation.project([ :a, :b, :c ])

  # removal
  new_relation = relation.remove([ :a, :b, :c ])

  # rename
  new_relation = relation.rename(:a => :b, :c => :d)

  # natural join
  new_relation = relation.join(other)        # OR relation + other

  # product
  new_relation = relation.product(other)     # OR relation * other

  # intersection
  new_relation = relation.intersect(other)   # OR relation & other

  # union
  new_relation = relation.union(other)       # OR relation | other

  # difference
  new_relation = relation.difference(other)  # OR relation - other

  # restriction
  new_relation = relation.restrict(relation.name.eq('other'))
  new_relation = relation.restrict { |r| r[:a].eq('other').and(r[:b].gte(42)) }

  # theta-join
  new_relation = relation.join(other, relation[:a].gte(other[:b]))
  new_relation = relation.join(other) { |r| r[:a].gte(r[:b]) }

  # NOTE: theta-join is effectively restricting a product of the relations

  # extend
  new_relation = relation.extend { |r| r.add(:total, r[:unit_price] * r[:quantity]) }
  new_relation = relation.extend { |r| r.add(:total) { |t| t[:unit_price] * t[:quantity] } }

  # summarize
  new_relation = relation.summarize(relation.project([ :name ])) { |r| r.add(:count, r[:name].count)
  new_relation = relation.summarize(relation.project([ :name ])) { |r| r.add(:count) { |acc, t| acc.to_i + 1 } }

  # Non-Relational Operators
  # ------------------------

  # returns a set that represents the relation header
  header = relation.header

  # simplifies and normalizes the relation operations
  optimized_relation = relation.optimize

  # a relation is Enumerable
  relation = relation.each { |tuple| ... }

  # order by attribute and direction
  new_relation = relation.order([ relation[:a].desc, relation[:b] ])
  new_relation = relation.order { |r| [ r[:a].desc, r[:b] ] }

  # reverse the relation (only allowed if ordered)
  new_relation = relation.reverse

  # offset (only allowed if ordered)
  new_relation = relation.drop(5)

  # limiting (only allowed if ordered)
  new_relation = relation.take(10)

  # get the first n tuples (only allowed if ordered)
  new_relation = relation.first     # default is 1
  new_relation = relation.first(5)

  # get the last n tuples (only allowed if ordered)
  new_relation = relation.last      # default is 1
  new_relation = relation.last(5)

  # CRUD Operators
  # --------------

  # can only modify relations that project all candidate keys for the base relations
  new_relation = relation.create(:a => 'test', :b => 'other', :c => 'yet another')
  new_relation = relation.update(:a => 'test', :b => 'other', :c => 'yet another')
  new_relation = relation.delete

== Goals

The purpose of this project is to expand my knowledge of relational algebra by attempting to implement a simple query system using the primitive operations defined in relational algebra.

Most of the design is heavily inspired from koios[https://github.com/carllerche/koios] and arel[https://github.com/rails/arel]. The reason I decided to write my own and not just build on top of those systems was not so much because I don't like the code/API in those projects, it's more because I wanted to gain a depth of understanding that can only be earned by trying to solve the problem myself.

I should note though that I don't plan to just re-implement those systems with a different API, or different internals, I plan to make something that surpasses them in several areas. For example, I want to be able to join information from multiple datastores and represent it as a single relation. I want to be able to insert, update or delete from that relation and have those changes propagated back to the right datastore. This is not an easy feat, since it is basically the writable view problem that RDBMS' struggle with. While I do think there are some cases where relations will become read-only, I think it will be possible to propagate writes properly in this manner. I certainly think for the current use cases in DataMapper this should work quite well.

The ability to join data from multiple datastores and have it presented in a consistent manner will solve one of the longest standing problems in DataMapper, namely how do we do cross repository joins. It should be possible to construct one query for one datastore, and then another query for another datastore and then join them. Since they are using different engines veritas will know to perform each query *natively* and then join the results in-memory seamlessly. It should also be possible to reorganize the queries so that as much work as possible is done natively as opposed to in-memory, which is considered the last resort.

Not only does this work nicely with associations, but it will allow DataMapper to perform mapping in a more powerful way. You'll be able to construct a join from multiple datastores, and set that as the base for your model. Each DM Resource would work as normal, but again writes could be propagated back to the appropriate datastore. You'd be able to split your data up between different datastores, but assemble it into one coherent view.

=== Phase 1: In-Memory Operations

The first phase of this project will be to implement all the operations listed below using in-memory data structures. I'm focusing on the API, and making sure the specs ensure the desired results are obtained from each operation.

This is 100% complete now.

=== Phase 2: RDBMS Engines

The second phase of this project will be to add an RDBMS based engine, and move the in-memory matching to it's own engine. I'll also be working on a system where if the primary engine cannot carry out some operation, that it first look at alternate forms (eg. using a join instead of an intersection), and then fall-back to in-memory matching. I also want to look at re-arranging queries so that all the operations that can be performed natively are "pushed down" the hierarchy and then the in-memory matching is performed last.

This is 80% complete. I have finished a first pass on the veritas-sql-compiler[https://github.com/dkubb/veritas-sql-compiler] which is a visitor that walks the AST and produces SQL for every operation except extend and summarize. To finish those I will need to add function support to veritas that are introspectable (i.e. not Proc objects). Once I can introspect them, then I can serialize them to SQL and other query languages.

{'fraction_non_alphanumeric': 0.08548097093197483, 'fraction_numerical': 0.0028468684447108183, 'mean_word_length': 3.9005139500734214, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 19, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '557811', 'n_tokens_mistral': 3630, 'n_tokens_neox': 3481, 'n_words': 1741}