16

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?

philipxy
  • 14,867
  • 6
  • 39
  • 83
Ivo Flipse
  • 10,222
  • 18
  • 50
  • 63
  • This question gets asked fairly frequently. See http://stackoverflow.com/questions/7731877/can-all-sql-queries-be-represented-in-relational-algebra-domain-and-tuple-relat/7733636#7733636 The details you are asking about are in my answer to that question. – Erwin Smout Oct 19 '11 at 18:16
  • 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 – Ivo Flipse Oct 24 '11 at 20:33

9 Answers9

8

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)
)
ChrisChen3121
  • 81
  • 1
  • 1
7

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

Tamara Wijsman
  • 12,198
  • 8
  • 53
  • 82
  • 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 – Ivo Flipse Oct 19 '11 at 16:02
  • @IvoFlipse: The slide says `Compute all possible attribute pairings` for that projection. – Tamara Wijsman Oct 19 '11 at 16:39
  • Please make your post self-contained. This post makes no sense on its own. – philipxy Oct 01 '19 at 09:20
6

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

Verbeia
  • 4,400
  • 2
  • 23
  • 44
bernardo
  • 76
  • 1
3

This is the annotation of another answer. My brain was hurting and so I tried a concise and complete answer posted earlier and it worked. But that’s merely “giving a man a fish” and so I had to see what was behind it.

Here then is ChrisChen3121’s Jan 22 ‘14 solution with changes only to parenthesis, comments, and line breaks. Most parenthesis line up vertically with their match. Hopefully that makes things easy to see. Following the aesthetically re-written code, there are the intermediate relations produced in an attempt to visualize/conceptualize the solution.

Long story short:

--Find target pizzas;

--With \cross, build a fantasy super-set list as if all pizzerias served said pies;

--Subtract out from there, all “Actually-Served” pies to create a “These-Are-Missing” list;

--Finally, from [a fresh copy of] “reality”, subtract out the “missing” and... that’s about it. 

\project_{pizzeria}(Serves)// “Actual” list of what pizzerias serve. Results shown below. 
\diff
\project_{pizzeria}
(// After the diff, this is a list of "What's Missing". Results shown below
    (// Super-set of all pizzerias combined with all "over30pies". Results shown below 
     // NOTE: Some combos here do not match reality
        \project_{pizzeria}(Serves)
        \cross
        (// "over30pies": Within these parentheses produces table shown below
            //Next line is what I used, it’s effectively equivalent, yes.
            //roject_{pizza} (                \select_{age > 30 }  Person  \join Eats)
            \project_{pizza} (\project_{name}(\select_{age > 30 } (Person))\join Eats)
        )
    )
    \diff
    ( // “Actual” list of what pizzerias serve. Results shown below. 
        \project_{pizzeria,pizza}(Serves)
    )
)

// “over30pies”, target pies (those eaten by 30+ year-olds)

cheese 
supreme

// Super-Set of all pizzerias combined with all target ("over30pies") // 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

// Actual, full list of which pizzerias actually serve what 

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

//Difference (what’s left over) after the “Actual” is subtracted from the fantastical “Super-Set”. This then, represents what’s MISSING or, “These pizzeria do not serve the required pizza listed" 

Dominos | supreme
Little Caesars | supreme
Straw Hat | supreme
r2h2
  • 31
  • 3
3

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.

Lisa
  • 31
  • 1
1

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 |
+------+
Xavier John
  • 8,474
  • 3
  • 37
  • 51
1

I figured out below based on wiki.

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

techmariner
  • 11
  • 1
1

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. Did it help?

Pedro Esteves
  • 11
  • 1
  • No not really, because I didn't grasp how to express that in relational algebra. But luckily the other answers helped me solve it :-) – Ivo Flipse Nov 09 '11 at 06:30
0

Hi there I found a solution without dividing operator:

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

========================================================================

it's as simple as that. What did I do? in the second part I found 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 differed that from the original list of pizzerias and the only one that makes pizza for those above 30 is Chicago Pizza.

MaldenJ
  • 1