# Relational algebra statement for a query

For the following schema

Country ("countryID", cName)
CoffeeShop ("shopID", sName, countryID, city)
Product ("productID", size)
Serves ("shopID", "productID")
ProductNames ("productID", "countryID", pName)


where attributes in quotation marks are primary keys, I must write a relational algebra statement for the following query:

List names of products that have same names in all countries they are served.


The thing that made me stuck on this problem is the fact that the product must not necessarily be served in all countries, but rather have the same name in all countries it is served. Without comparing for an initial value, I couldn't get a solution that makes more sense and that is possible to be written as a relational algebra statement.

• It sounds like a division. Do you know it ? en.wikipedia.org/wiki/Relational_algebra#Division_.28.C3.B7.29 Oct 24, 2013 at 12:55
• For a given productID, you can list the shopID of those that serve it. From this, you get the countries where the product is supplied. (There can be duplicates, but this does not matter.) This list gives you all the names in the relevant countries, you can check uniqueness.
– user16034
Sep 19, 2022 at 11:02

Hint: A product has the same names in all countries if for every two countries, it has the same name in both countries.

• IMO a misleading advice, which will make the OP consider pairs of countries.
– user16034
Sep 19, 2022 at 11:05
• A complication: a product may have multiple names, even in the same country. Sep 14, 2023 at 15:58

Try to systematically reformulate the query into tuple calculus (or domain calculus).

This is effectively a normalization operation on the natural language statement. Recasting it into tuple calculus makes it much longer, but unambiguous and much closer to relational algebra.

Use the fact that $$\forall = \neg\exists\neg$$.

Once you're done, you can similarly try a piecewise transformation into relational algebra.

For instance,

• products with the same names in all countries they are served

is the same thing as

• products for which there is no name that is used in some but not all countries the product is served

which is the same thing as

• products for which there is no name that is used in one country it is served, but not in another (Yuval Filmus's hint)

which is the same thing as

• products for which there is no name such that there are two countries such that (...)

which is the same thing as

• products for which it is not the case that there is a name such that (...)

and so forth.

I'm not writing these statements down in tuple/domain calculus syntax, but it is a good idea to do so.

If all is well, you will end up with a long statement (and a tuple calculus expression) that will be easy to transform into relational algebra.