How to find all pizzerias that serve every pizza eaten by people over 30?

Ivo Flipse picture Ivo Flipse · Oct 19, 2011 · Viewed 13.7k times · Source

I'm following the Stanford Database course and there's a question where we have Find all pizzerias that serve every pizza eaten by people over 30 using Relational Algebra only.

The problem consist of a small database with four relations:

Person(name, age, gender)       // name is a key
Frequents(name, pizzeria)       // [name,pizzeria] is a key
Eats(name, pizza)               // [name,pizza] is a key
Serves(pizzeria, pizza, price)  // [pizzeria,pizza] is a key

I know how to find which pizza's people over 30 eat and make a cross-product of them, so I could check which pizzeria has both.

I can make a list of all the pizzeria's that serve those pizza's, but I have no idea how to remove any pizzeria that only have one combination (like Dominos).

Chicago Pizza   cheese  cheese
Chicago Pizza   cheese  supreme
Chicago Pizza   supreme cheese
Chicago Pizza   supreme supreme
Dominos         cheese  cheese
Dominos         cheese  supreme

The Q&A forums tell us to use division and point us to several presentations. While I get what the result of the action would be, I don't really understand how to translate the formula's into relational algebra syntax.

Could anyone explain me what I'm missing, hopefully without giving the solution outright?

Answer

ChrisChen3121 picture ChrisChen3121 · Jan 22, 2014

Definitely this is the concept of division operator in relational algebra.

But I tried on that course. The RA Relational Algebra Syntax doesn't support dev operator. So I used diff and cross instead. Here is my solution:

\project_{pizzeria}(Serves)
\diff
\project_{pizzeria}(
    (\project_{pizzeria}(Serves) 
    \cross 
    \project_{pizza}(\project_{name}(\select_{age>30}(Person))\join Eats))
    \diff
    \project_{pizzeria,pizza}(Serves)
)