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

Question

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?

Lachellelaches

This question gets asked fairly frequently. See #7732377 The details you are asking about are in my answer to that question. – British

I don't know, but your answer wasn't very helpful. I had problems translating my own data into a division query, so sending me to yet another example that's completely unrelated didn't help me solve it – Lachellelaches

Answer 1

The solution is the join div operator http://en.wikipedia.org/wiki/Relational_algebra#Division_.28.C3.B7.29

See http://oracletoday.blogspot.com/2008/04/relational-algebra-division-in-sql.html

Matron

Oh wow, finally an example that even uses relational algebra as well! – Lachellelaches

Answer 2

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)
)

Lehman

Answer 3

1. On slide 6, note that n is (3 1 7).

2. On the next slide, o / n results in (4 8).

3. If o would also have (12 3) and (12 1) but not (12 7), 12 would not be part of o / n.

You should be able to fill in an example in the formula on Slide 16 and work it out.

1. In your case, we take ɑ to be:

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

2. Then we take β to be:

   cheese cheese
   cheese supreme
   supreme cheese
   supreme supreme
   

3. The result of ɑ / β would then be:

   Chicago Pizza
   

Dominos is not part of this because it misses (supreme cheese) and (supreme supreme).

Characterize

If that would be alpha, then what would be the projection of A-B of alpha be (see slide 18)? I'm still having some difficulties translating that formula into something concrete – Lachellelaches

@IvoFlipse: The slide says Compute all possible attribute pairings for that projection. – Characterize

Please make your post self-contained. This post makes no sense on its own. – Wira

Answer 4

Try doing a join using conditions rather than a cross. The conditions would be sure that you match up the records correctly (you only include them if they are in both relations) rather than matching every record in the first relation to every record in the second relation.

Baptlsta

Answer 5

Here is ChrisChen3121’s solution with changes only to parentheses, comments, and line breaks. Most parentheses line up vertically with their match. Following the aesthetically re-written code are the intermediate relations produced in an attempt to visualize/conceptualize the solution.

• Find the "Over-30-Pizzas" target list (those eaten by 30+-year-olds);

• With \cross, build a "Fantasy-Superset" list of all pizzerias combined with Over-30-Pizzas, as if all pizzerias served the target Over-30-Pizzas;

• Subtract out from there the "Actually-Served" list of what pizzerias serve in reality to create a "What's-Missing" list;

• From [a fresh copy of] what's Actually-Served, subtract out pizzerias appearing in What's-Missing.

    // "Actually-Served" list of what pizzerias serve in reality. Results shown below.
    \project_{pizzeria}(Serves)
\diff
    \project_{pizzeria}
        (// "What's-Missing" list. Results shown below.
            (// "Fantasy-Superset" list of all pizzerias combined with Over-30-Pizzas. Results shown below.
             // NOTE: Some combos here do not match reality.
                // all pizzarias
                \project_{pizzeria}(Serves)
            \cross
                // "Over-30-Pizzas" target list (those eaten by 30+-year-olds). Results shown below.
                \project_{pizza}(\project_{name}(\select_{age > 30 }(Person)) \join Eats)
                // What I used instead, it’s equivalent.
                // \project_{pizza}(\select_{age > 30} Person \join Eats)
            )
        \diff
            // "Actually-Served" list of what pizzerias serve in reality. Result shown below.
            \project_{pizzeria,pizza}(Serves)
        )

// "Over-30-Pizzas" target list (those eaten by 30+-year-olds).

cheese 
supreme

// "Fantasy-Superset" list of all pizzerias combined with Over-30-Pizzas.
// NOTE: some combos do not match reality.

Chicago Pizza  | cheese
Chicago Pizza  | supreme
Dominos        | cheese
Dominos        | supreme
Little Caesars | cheese
Little Caesars | supreme
New York Pizza | cheese
New York Pizza | supreme
Pizza Hut      | cheese
Pizza Hut      | supreme
Straw Hat      | cheese
Straw Hat      | supreme

// "Actually-Served" list of what pizzerias serve in reality.

Chicago Pizza  | cheese
Chicago Pizza  | supreme
Dominos        | cheese
Dominos        | mushroom
Little Caesars | cheese
Little Caesars | mushroom
Little Caesars | pepperoni
Little Caesars | sausage
New York Pizza | cheese
New York Pizza | pepperoni
New York Pizza | supreme
Pizza Hut      | cheese
Pizza Hut      | pepperoni
Pizza Hut      | sausage
Pizza Hut      | supreme
Straw Hat      | cheese
Straw Hat      | pepperoni
Straw Hat      | sausage

\\ "What's-Missing" list. Difference (what’s left over) after the Actually-Served is subtracted from the Fantasy-Superset. "These pizzerias do not serve the required pizza listed."

Dominos        | supreme
Little Caesars | supreme
Straw Hat      | supreme

Undesigning

Answer 6

Based on the assumption that all pizzerias serve at least one type of pizza, we will find that the group of pizzas that people over 30 do NOT EAT will be sold by all the pizzerias EXCEPT the one(s) who sell exclusively pizzas which people over 30 do EAT.

Saturday

No not really, because I didn't grasp how to express that in relational algebra. But luckily the other answers helped me solve it :-) – Lachellelaches

Answer 7

Here is the conversion of http://oracletoday.blogspot.com/2008/04/relational-algebra-division-in-sql.html to MySQL

    mysql>create table parts (pid integer);
    mysql>create table catalog (sid integer,pid integer);
    mysql>insert into parts values ( 1), (2), (3), (4), (5);
    mysql>insert into catalog values (10,1);

mysql>select * from catalog;
+------+------+
| sid  | pid  |
+------+------+
|   10 |    1 |
|    1 |    1 |
|    1 |    2 |
|    1 |    3 |
|    1 |    4 |
|    1 |    5 |
+------+------+


mysql> select distict sid,pid from (select sid from catalog) a  join parts;
+------+------+
| sid  | pid  |
+------+------+
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    4 |
|   10 |    5 |
|    1 |    1 |
|    1 |    2 |
|    1 |    3 |
|    1 |    4 |
|    1 |    5 |
+------+------+


mysql>select * from 
(select distinct sid,pid from (select sid from catalog) a ,parts)  b where
not exists (select 1 from catalog c where b.sid = c.sid and b.pid = c.pid);

+------+------+
| sid  | pid  |
+------+------+
|   10 |    2 |
|   10 |    3 |
|   10 |    4 |
|   10 |    5 |
+------+------+


mysql>select distinct sid from catalog c1
where not exists (
   select null from parts p
   where not exists (select null from catalog where pid=p.pid and c1.sid=sid));
+------+
| sid  |
+------+
|    1 |
+------+

Barriebarrientos

Answer 8

R:=
\project_{pizzeria, pizza} (\select_{age>30} (Person \join Eats \join Serves))

S:=
\project_{pizza} (\select_{age>30} (Person \join Eats \join Serves))

Final solution:

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

Attila

Answer 9

A solution without the division operator:

\project_{pizzeria}Serves
\diff
\project_{pizzeria}((\project_{pizza}(\select_{age < 30}Person\joinEats)
\diff\project_{pizza}(\select_{age > 30}Person\joinEats))\joinServes);

In the second part I found a pizza list that did not include pizzas that are eaten by those above 30.

I joined them with pizzerias in order to see which pizzerias make pizza for younger people also.

I subtracted that from the original list of pizzerias and the only one that makes pizza for those above 30 is Chicago Pizza.

Coleman