Why is it harder to query for entities with more than every vs less than some?

Question

This is the database, bold primary key.

works (person_name, company_name, salary)

Suppose we have this problem:

Find the names of all employees who earn more than every employee of Small Bank Corporation.

Proposed solution:

We cannot easily compute the set of employees that earn more than every employee of Small Bank Corporation, but we can compute the set of employees that earn less than some employees of Small Bank Corporation. We subtract this set from the set of all employees. Note the less than or equal and that we remove records with the same name.

temp ← ∏person_name(σp(works⨯ρd(works)))

where p is

works.person_name ≠ d.person_name ∧
works.salary ≤ d.salary ∧
d.company_name = "Small Bank Corporation"

Then the answer is:

∏person_name(works) − temp

Why can't we easily compute the set of people that earn more than every employee of Small Bank Corporation? And why CAN we easily compute the set of people that earn less? I don't understand this. What does works.salary <= d.salary exactly do? Does it loop for every works.salary entity through all the d.salary entities and look if it is <= for ALL d.salary entities?

If you are looking for a solution in SQL, there are many different ways to express this query. — Gordon Linoff, Dec 05 '15 at 12:23
Who proposed the solution? Or are you asking why your solution is not easy? — Emacs User, Dec 05 '15 at 18:31
@EmacsUser The question is not what the query is, the question is why are two queries that are so similar in one sense (meaning) so different in another (algebra/sql expression). — philipxy, Dec 05 '15 at 21:54
Your projections should be on `works.person_name` or `d.person_name`. — philipxy, Dec 05 '15 at 21:56

score 2 · Answer 1 · answered Dec 05 '15 at 13:20

2

The query can be expressed pretty easily like this:

select person_name
from works
where salary > (
    select max(salary) 
    from works 
    where company_name = 'Small Bank Corporation')

answered Dec 05 '15 at 13:20

D'Arcy Rittich

167,292
40
290
283

score 1 · Answer 2 · edited May 23 '17 at 12:15

We cannot easily compute the set of employees that earn more than every employee of Small Bank Corporation, but we can compute the set of employees that earn less than some employees of Small Bank Corporation.

It's not the inequalities that make a difference. (You can see this by just changing them in your σ.) It's the FOR EVERY/ALL vs FOR SOME.

A predicate is a true-or-false fill-in-the-(named-)blanks statement).

-- person [W.P] works for company [W.C] for salary [W.S]
W (W.P,W.C,W.S)

Notice that the name plus its attributes is a shorthand version of the predicate. We call the predicate of a relation variable, constant or expression its meaning.

Suppose relation expressions e & f hold the rows that make predicate expressions E & F true (respectively). The algebra operators were designed so that:

R holds the rows satisfying R(R.X,...)
ρS(ewith attributes R.X) holds the rows satisfying E with R.X replaced by S.X
e⨯f holds the rows satisfying E AND F
e-f holds the rows satisfying E AND NOT F
eUf holds the rows satisfying E OR F
σcondition(e) holds the rows satisfying E AND condition
πA(e) holds the rows satisfying FOR SOME all attributes but A: E

It just so happens that for each small change in relation there is a small change in meaning. Notice that the list does not include expression ~(e) ("complement") which holds rows where NOT E, ie the rows that aren't in e. Because (in general) that's a lot of rows and impractical to calculate. But it turns out that if we never want those rows as a query result (and we generally don't) then we can rewrite using other operators. FOR ALL A: E means NOT FOR SOME A: NOT E. So queries involving FOR ALL are complicated and we can't (in general) have FORALL on the outside. The original meaning isn't complicated, but we have to rearrange it to a complex phrasing that is calculated by a complex relation expression.

So the answer is, it happens that the relation where FOR SOME A: E is simple to calculate and visualize, but the relation where FOR ALL A: E uses complicated calls of inexpensive opertators to calculate inexpensively and isn't a human-obvious rearrangement of e.

(There are various special cases of using FOR ALL that translate directly to simple calls of various "division" operators. But then the special cases do not have simple meanings! It turns out that it is simpler to express FOR ALL queries using relation subset operators.)

(See my answers & their questions here re predicates & algebra and here re sql.)

What does works.salary <= d.salary exactly do? Does it loop for every works.salary entity through all the d.salary entities and look if it is <= for ALL d.salary entities?

It appears in a σ call (selection/restriction). The call outputs rows that make the argument relation value true and that make the condition (a predicate) true. Ie the rows that make the AND (conjunction) of the two predicates true. Ie the roews in its input that make the condition true. All it has to do with the overall result is that it calculates something along the way.

You can translate your query to natural language. Although the way you wrote it is by (informally) translating if from natural language. That will turn out to be talking about a maximum. Eg temp is rows that satisfy:

-- temp ← ∏works.person_name(σp(works⨯ρd(works)))
FOR SOME works.company_name, works.salary,
    d.person_name, d.company_name, d.salary:
        person [works.person_name] works for company [works.company_name]
            for salary [works.salary]
    AND person [d.person_name] works for company [d.company_name]
            for salary [d.salary]
    AND [works.salary] <= [d.salary]
    AND ...

This is rows where person [works.person_name] works for company [works.company_name] for salary [works.salary] and person [d.person_name] works for company [d.company_name] for some salary [d.salary] AND [works.salary] <= [d.salary] AND ..., for some values for attributes other than works.person_name. So it's a list of people where there exists some other (≠) person with at least as big a salary at Small Bank Corporation.

(Your query would be simpler if you ignored person names and just asked for people pairs where the works-person has a smaller salary than the d-person. If their salary is not equal to yours then they're not you.)

Why is it harder to query for entities with more than every vs less than some?

2 Answers2