Convert SQL Query to Relational Algebra

Question

I need some help converting an SQL query into relational algebra.

Here is the SQL query:

SELECT * FROM Customer, Appointment
WHERE Appointment.CustomerCode = Customer.CustomerCode
    AND Appointment.ServerCode IN
    (
        SELECT ServerCode FROM Appointment WHERE CustomerCode = '102'
    )
;

I'm stuck because of the IN subquery in the above example.

Can anyone demonstrate for me how to express this SQL query in relational algebra?

Many thanks.

EDIT: Here is my proposed solution in relational algebra. Is this correct? Does it reproduce the SQL query?

Scodes ← ΠServerCode(σCustomerCode='102'(Appointment))

Ccodes ← ΠCustomerCode(Appointment ⋉ Scodes)

Result ← (Customer ⋉ Ccodes)

Answer 1

Your SQL code will result in duplicate columns for CustomerCode and the use of SELECT [ALL] is likely to result in duplicate rows. Because the result is not a relation, it cannot be expressed in relational algebra.

These problems are easily fixed in SQL:

SELECT DISTINCT * 
  FROM Customer NATURAL JOIN Appointment
 WHERE Appointment.ServerCode IN
    (
        SELECT ServerCode FROM Appointment WHERE CustomerCode = '102'
    )
;

You didn't specify which relational algebra you are intereted in. Date and Darwen proposed an algebra named A, specified an A language named D, and designed a D language named Tutorial D.

Tutorial D uses operators JOIN for natural join, WHERE for restriction and MATCHING for semijoin, The slight complication is the comparison in SQL:

CustomerCode = '102'

The comparison of a CustomerCode value to a CHAR value in SQL is possible because of implicit coercion. Tutorial D is stricter -- type safe, if you will -- requiring you to overload the equality operator or, more practically, define a selector operator for CHAR, which would typically have the same name as the type.

Therefore, the above (revised) SQL may be written in Tutorial D as:

( Customer JOIN Appointment ) 
   MATCHING ( ( Appointment WHERE CustomerCode = CustomerCode ( '102' ) ) { ServerCode } )

Answer 2

"How do I represent my query in this standard form of RA?"

It's not so much a question of "type of algebra" as it is of "type of notation".

Notation using greek symbols typically uses sigma, the restrict condition in subscript appended to the sigma character, and then the subject of the restriction (the relational expression that is subjected to the restrict condition).

Date avoid that notation, because typesetting and/or creating text using such notations is usually a lot harder than it is using just the western alphabet (a math teacher of mine once told us that math textbooks contain the most errors of all).

σ <cond> (<rel exp>) thus denotes the very same algebra expression as (Date's syntax) "<rel exp> WHERE <cond>".

Similarly, with greek symbols, projection is typically denoted using the letter Pi, with the list of retained attributes in subscript appended to the Pi, and the expression that is the subject of the projection following that.

Π <attr list> (<rel exp>) thus denotes the very same algebra expression as (Date's syntax) "<rel exp> { <attr list> }".

The join family of operators is usually denoted, in "greek" symbols, using (variations of) the Unicode BOWTIE character, or that character consisting of a lowercase letter 'x' surrounded by a full circle (usually used to denote full cartesian product, cross-product, ... whatever your algebra course happens to name it).

Some courses provide a "greek-symbol" notation for rename, using the greek letter Rho. Appended in subscript is the rename list, in the form a1->b1,a2->b2,... Appended after that comes the relational expression that is subjected to the rename. Likewise, Date has a non-greek-symbol equivalent syntax : <rel exp> RENAME a1 AS b1, a2 AS b2 , ...

The important thing is to see that these differences are merely differences in syntactical notation, not "different algebrae".

EDIT

One could imagine that the greek symbols notation would be the way to program relational algebra into an APL engine, Date's syntax would be the way to program relational algebra into a cobol-like or PL/1-like engine (there effectively exists such an engine called Rel), and the way to program relational algebra into an OO-like engine, could look something like relation.NaturalJoin(otherRelation).Matching(yetOtherRelation.Restrict(condition).project(attributesList)).