This is a sketch - may be scrapped later

The Relational Algebra is an algebra that formalizes the representation, manipulation and optimization of database queries. Another succinct overview can be found here.

The object-relational mapping used in most OODB's relates objects to tables and slots to attributes. Joins combine attributes from multiple tables using a common attribute. In object land, a join can be expressed in a similar fashion or by direct reference (object reference).

Once we transform the query expression into algebraic form, we can apply rewrite rules to reorder the query tree into more efficient forms.

• Basic Operations
  • Selection (select <op> <attr> <attr-or-value> <nset>)
  • Projection project <attr-list> <nset>)
  • Set-union (union <attr-list> <set1> <set2>)
  • Set-difference (difference <attr-list> <nset> <nset>)
  • Rename (rename <nset> <nset>) This is probably not necessary
  • Product (product <attr-list> <nset> <nset>)
• Derived Operations
  • Set-intersection (intersection <attr-list> <nset> <nset>)
  • Theta-join (theta-join <op> <attr1> <nset1> <attr2> <nset2>)

Surface syntax is parsed into a query tree of RA operations. This query tree is then manipulated by valid transformations under the algebra to create more efficient query trees. The resultant tree is passed to the planner.

Example commutivity theorems:

(select P1 (select P2 R1)) = (select P2 (select P1 R1)) 
(join attr2 (join attr1 R1 attr2 R2) attr3 R3) = (join attr1 R1 attr2 (join attr2 R2 attr3 R3))

These theorems are used to perform the following kinds of optimizations:

• Selection pushing: Move a select from the output of a join to an input
• Selection splitting: select(R,(and A B)) = select(select(R,A),B)
• Projection pushing: similar to select pushing iff domains exist in each relation and result of push does not remove join domains

These optimizations serve to reduce the size of the sets contributing to joins and improve query efficiency.