Abstract: | We present an algorithm for converting a semantically meaningful SQL query into an equivalent algebraic expression. The relational algebra we employ consists of the following operators: union, intersection, difference, Cartesian product, selection, and projection. The SQL queries we consider can have an arbitrary level of nesting but are restricted in three ways. We assume that they do not contain an ORDER BY or a GROUP BY clause, all SELECTs are in fact SELECT DISTINCTs, and that no aggregate functions are used. The first two assumptions are made in order to remain faithful to the definition of a relation as a set of rows. The last assumption is needed since there is no standard for incorporating aggregate functions into a relational algebra. The research results in this paper will be useful in implementing an SQL user interface for database management systems that internally employ relational algebra. They can also be used in optimizing the evaluation of SQL queries. |