SQL query (in SQL, relational algebra and tuple relational calculus)

Question

Im doing a test exam where I've gotten stuck on one particular query, in both its SQL code, relational algebra and tuple relational calculus.

The query states: Find the (city,state) pairs which house a branch of every type which is listed in the Branch relation.

Where Branch is:

Branch_ID (Primary key)
Branch_City
Branch_State
Branch_Type

and City is:

City_Name (Primary key)
State_Name (Primary key)
Population

And Branch_City and Branch_State is a foreign key to City_Name and State_Name respectively.

The "rules" are that aggregate functions, such as COUNT,MAX etc may not be used.

The query must be "understood" by MySQL and PostgreSQL however functions like EXCEPT, INTERSECT available in PostgreSQL but not in MySQL can be used.

No subqueries in the FROM clause

As said, it would be greatly appreciated if answers could be provided for sQL, relational algebra and tuple relational calculus. Those questions has stalled me.

Thanks in advance!

Pieter Geerkens · Answer 1 · 2013-03-23T10:58:32.670

This is SQL Server syntax, because I do not have MySql or PostGresSQL, but is should give you the idea:

with branches as (
  select * from ( values
    ('Perth',1),
    ('Toronto',1), ('Toronto',2), ('Toronto',3),
    ('Hamilton',2), ('Hamilton',3)
  ) branches(City,  Branch_Type)
)

  select distinct
    City
  from branches
except
  select distinct 
    b.City
  from branches t 
  cross join branches b 
  left join branches b2 on b2.Branch_Type = t.Branch_Type and b2.City = b.City
  where b2.Branch_Type is null

I have trimmed it down to the bare minimum to demonstrate the necessary set operations.

The top half of the query returns all three cities; the second half returns only Hamilton and Perth; so that the whole query returns only Toronto.

I haven't used either Relational Algebra or Relational Calculus in 30 years, but exxpressing the above query in those dialects is simply a translation exercise.

Update - for MySQL:

with branches as (
  select * from ( values
    ('Perth',1),
    ('Toronto',1), ('Toronto',2), ('Toronto',3),
    ('Hamilton',2), ('Hamilton',3)
  ) branches(City,  Branch_Type)
)

select distinct
  City
from branches
where City not in (
  select distinct 
    b.City
  from branches t 
  cross join branches b 
  left join branches b2 on b2.Branch_Type = t.Branch_Type and b2.City = b.City
  where b2.Branch_Type is null
  )

Since the sub-query is in the WHERE clause instead of the FROM clause this shold be legitimate. It could be expressed as a left join, but I think that moves the sub query into the FROM clause.

@GustavDanell: Consider a matrix with the City,State combintions as the rows, and the Branch_Types as the columns. Initially the Branches table only has records for some of the matrix cells. The cross join distinct generates the complete matrix, from which we select those rows which have missing cells in Branches. — Pieter Geerkens, Mar 23 '13 at 12:26

wildplasser · Accepted Answer · 2013-03-23T13:25:47.593

-- The query states: Find the (city,state) pairs which house a branch of every type which is listed in the Branch relation.
--                                               ((((                    ^^^^^ ^^^^    ))
-- This is equivalent to: Find cities for which "There does NOT EXIST a branchType that is NOT PRESENT in this City"
-- This leads to the double "NOT EXISTS (NOT EXISTS())" solution to relational devision.::
SELECT  * -- city,state
FROM city c
WHERE NOT EXISTS (
        -- find a branchtype that is not present in our city
        SELECT * FROM Branch b
        WHERE NOT EXISTS (
                -- same city for this  branchtype
                SELECT * FROM Branch nx
                WHERE nx.Branch_City = c.City_Name AND nx.Branch_State = c.State_Name
                AND nx.Branch_Type = b.Branch_Type
                )
        )
        ;

Relational division is the term for this type of operation.

BTW: the composite (city,state) primary key for the city table is only there to confuse you. Normally, you would use a numerical (surrogate) city_id as a primary key for the city table, and also use that as a foreign key in the branches table.

SQL query (in SQL, relational algebra and tuple relational calculus)

2 Answers2