Postgresql – Converting SQL to Relational Algebra / Calculus

postgresqlrelational-algebrarelational-calculusrelational-theory

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.

Best Answer

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

You don't have a FROM in your SQL. You shouldn't start by JOINing.
You seem to assume that train_code is a text, yet you define it as an integer.
Your table definitions don't define a type for train_code in the journey table, nor for journey_id in the price one.
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.

Related Solutions

Postgresql – Postgres multiple joins slow query, how to store default child record

You write:

Each customer can have multiple sites, but only one should be displayed in this list.

Yet, your query retrieves all rows. That would be a point to optimize. But you also do not define which site is to be picked.

Either way, it does not matter much here. Your EXPLAIN shows only 5026 rows for the site scan (5018 for the customer scan). So hardly any customer actually has more than one site. Did you ANALYZE your tables before running EXPLAIN?

From the numbers I see in your EXPLAIN, indexes will give you nothing for this query. Sequential table scans will be the fastest possible way. Half a second is rather slow for 5000 rows, though. Maybe your database needs some general performance tuning?

Maybe the query itself is faster, but "half a second" includes network transfer? EXPLAIN ANALYZE would tell us more.

If this query is your bottleneck, I would suggest you implement a materialized view.

After you provided more information I find that my diagnosis pretty much holds.

The query itself needs 27 ms. Not much of a problem there. "Half a second" was the kind of misunderstanding I had suspected. The slow part is the network transfer (plus ssh encoding / decoding, possibly rendering). You should only retrieve 100 rows, that would solve most of it, even if it means to execute the whole query every time.

If you go the route with a materialized view like I proposed you could add a serial number without gaps to the table plus index on it - by adding a column row_number() OVER (<your sort citeria here>) AS mv_id.

Then you can query:

SELECT *
FROM   materialized_view
WHERE  mv_id >= 2700
AND    mv_id <  2800;

This will perform very fast. LIMIT / OFFSET cannot compete, that needs to compute the whole table before it can sort and pick 100 rows.

pgAdmin timing

When you execute a query from the query tool, the message pane shows something like:

Total query runtime: 62 ms.

And the status line shows the same time. I quote pgAdmin help about that:

The status line will show how long the last query took to complete. If a dataset was returned, not only the elapsed time for server execution is displayed, but also the time to retrieve the data from the server to the Data Output page.

If you want to see the time on the server you need to use SQL EXPLAIN ANALYZE or the built in Shift + F7keyboard shortcut or Query -> Explain analyze. Then, at the bottom of the explain output you get something like this:

Total runtime: 0.269 ms

Database relationship refresher

Journey.CustomerIDis a foreign key to Customer.CustomerID. Journey.TrainNo is a foreign key to TrainRide.TrainNo.

The relationship here is many to many. A TrainRide can have many customers. A customer could ride many TrainRides. The table Journey is used to associate the two. You can see the same customer more than once in this table such as 834 or the same train more than once such as Amtrak 333.

Best Answer

Related Solutions

Postgresql – Postgres multiple joins slow query, how to store default child record

pgAdmin timing

Database relationship refresher

Related Question