This is a summary largely based on the ‘Alice’ book: http://webdam.inria.fr/Alice/.
The non-redundant set of operations for a maximally effective Relational Algebra that is restricted to safe, domain independent, non-recursive, type safe queries is:
- Select (restrict/where)
- Project
- Rename
- Join (natural)
- Union
This set is referred to as SPRJU. This set is incomplete but ‘safe’ because it excludes negation. It can be completed by adding:
- Minus (set difference).
This set could be referred to as SPRJUM, and from this foundation all the other operations of the Relational Algebra can be created. That includes other set operations, and other kinds of join such as Antijoin or Not Matching.
To this the authors propose the addition of
- While (recursion)
The complete set could be referred to as SPRJUMW. It is able to handle recursive joins, similar to the SQL Recursive Common Table Expression.
This is the endpoint for domain-independent queries. There is nothing to add (or take away). This is a complete Relational Algebra, capable of the full range of safe, domain-independent queries (including recursive queries).
However, this Algebra is unable to perform a range of familiar tasks based on computation, which means that it cannot return any attribute values that are not already in the database and it cannot perform computation-like activities such as counting. It is not Turing Complete, and cannot be made so.
Computation requires abandoning domain-independence. To compute, one needs a type system. The SELECT of SQL and the EXTEND of Tutorial D require computation and a type system. These issues are not directly addressed in this book or anywhere else that I know of.
Some useful extensions that lie outside the domain-independent Relational Algebra include:
- Introducing an attribute type system and calculated attributes (EXTEND in Tutorial D, SELECT in SQL)
- Introducing algorithmic or calculated relations (see Hall-Hitchcock-Todd or Appendix A)
- An extended While (see book for details).
Appendix A shows that the addition of calculated relations can provide a substitute for Select/Restrict/Where. Operators that provide recursion can substitute for While. Ordering or relaxing type safety provide further choices. At some point there are just too many options available. However, aggregation is not adequately treated in any of the above. The Alice book has a brief section of little practical value.
It is my view that this is an adequate theoretical foundation for a Relational Algebra that is complete within the limits of safe, domain-independent, type safe queries. A foundation for the various methods of introducing computation is still lacking, especially with respect to aggregation and ordering.