Converting SQL to Relational Algebra / Calculus

Question

I have designed a schema and generated a few SQL queries. I'm using PostgreSQL.

For example:

CREATE TABLE train 
(
  train_code SERIAL PRIMARY KEY,
  name TEXT NOT NULL
); 

CREATE TABLE journey 
(
  journey_id SERIAL PRIMARY KEY, 
  int INTEGER,
  train_code REFERENCES train(train_code)
); 

CREATE TABLE price 
(
  journey_id REFERENCES journey(journey_id),
  price INTEGER
); 

Give me all train names that commence from train_code NYC or SFO that are priced $50 or more. (assume the price table is in $ already).

SELECT train.name
JOIN   train
JOIN   journey on train.train_code = journey.train_code
JOIN   price on price.journey_id = journey.journey_id 
WHERE  price.price >= 50 
AND    journey.train_code IN ('NYC', 'SFO') 
AND    journey.int = 1 -- (first train of the journey)

I am unsure how to convert this into a relational algebra and/or calculus query. I have looked at a few converters e.g. http://dbis-uibk.github.io/relax/calc.htm but in this calculator 'join' for example and 'in' is not allowed.

Answer 1

You have a number of "mistakes" in your SQL, that should be addressed before you translate it to relational algebra.

1. You don't have a FROM in your SQL. You shouldn't start by JOINing.
2. You seem to assume that train_code is a text, yet you define it as an integer.
3. Your table definitions don't define a type for train_code in the journey table, nor for journey_id in the price one.
4. The tool you're using doesn't understand SERIAL (which is not standard SQL). Just don't use it. Use INTEGER instead.

So, your table definitions just should be:

CREATE TABLE train 
(
  train_code TEXT PRIMARY KEY,
  name TEXT NOT NULL
); 

CREATE TABLE journey 
(
  journey_id INTEGER PRIMARY KEY, 
  int INTEGER,
  train_code TEXT REFERENCES train (train_code)
); 

CREATE TABLE price 
(
  journey_id INTEGER REFERENCES journey (journey_id),
  price INTEGER
); 

This is translated by RelaX to:

group: joanolo (imported from SQL)

train = {
    train_code:string, name:string
}

journey = {
    journey_id:number, int:number, train_code:string
}

price = {
    journey_id:number, price:number
}

On the query side, you need to add a FROM and you just change x IN (a, b) to (x = a OR x = b). You'll end up having the following query:

SELECT 
    train.name
FROM   
    train
    JOIN  journey on train.train_code = journey.train_code
    JOIN  price on price.journey_id = journey.journey_id 
WHERE  
    price.price >= 50 
    AND (journey.train_code = 'NYC' OR journey.train_code = 'SFO') 
    AND  journey.int = 1

This format is understood by RelaX, and will give you the result you're looking for:

π train.name σ price.price ≥ 50 and (journey.train_code = 'NYC' or journey.train_code = 'SFO' ) and journey.int = 1 train ⨝ train.train_code = journey.train_code journey ⨝ price.journey_id = journey.journey_id price

That is you have one projection (π), equivalent to your SELECT one selection (σ) that filters with the condition in your WHERE clause, and two joins (⨝) which are equivalent to SQL JOIN.