In SQL, EXISTS is slightly more powerful than IN

[julianhyde]

In SQL, any query that uses IN can be converted into an equivalent one that uses EXISTS. For example,

SELECT *
FROM Emp AS e
WHERE e.deptno IN (
  SELECT d.deptno
  FROM Dept AS d
  WHERE d.location = 'Oakland')

is equivalent to

SELECT *
FROM Emp AS e
WHERE EXISTS (
  SELECT *
  FROM Dept AS d
  WHERE d.deptno = e.deptno
  AND d.location = 'Oakland')

The two solutions match relational algebra and relational calculus styles of thinking:

• The IN formulation is relational algebra, which is closer to how the query is evaluated by typical engines, and tends to map fairly directly onto efficient join operators
• The EXISTS formulation is relational calculus, which is closer to logic. As is typical, the EXISTS query is correlated: there is a reference to e.deptno inside the subquery. It will need to be decorrelated, to something like the IN query, in order to be executed efficiently.

But not every EXISTS query can be converted to IN. Consider this:

SELECT *
FROM Emp AS e
WHERE EXISTS (
  SELECT *
  FROM Dept AS d
  WHERE d.deptno < e.deptno
  AND d.location = 'Oakland')

The problem is that we need to generate the list of integers values that are higher than each deptno value from the Dept table. In pseudo-syntax, it would look like this:

SELECT e.*
FROM Emp AS e,
  EXTENT(INTEGER) AS i
WHERE i.i IN (
  SELECT d.deptno
  FROM Dept AS d
  WHERE d.location = 'Oakland')
AND i < e.deptno

We have invented the EXTENT operator for this example. Its argument is a data type, and it generates the set of values of that data type. EXTENT(INTEGER) generates the set of all values of the INTEGER data type.

Clearly, it's impossible to implement EXTENT (it would return an unbounded set of values), but in this case we see that i is restricted to the values of the deptno column of the Dept table. So we can write the following:

SELECT e.*
FROM Emp AS e,
  (SELECT DISTINCT deptno FROM Dept) AS i
WHERE i.i IN (
  SELECT d.deptno
  FROM Dept AS d
  WHERE d.location = 'Oakland')
AND i < e.deptno

[julianhyde]

The suchThat operator proposed in #106 is closely related to the EXTENT operator above. The purpose of #106 is to allow people to mix Datalog (relational calculus) and functional programming (relational algebra) style fragments in the same query.

In that mixed style, people need a way to write a predicate and then work backwards, figuring out the set of arguments for which the predicate might be true. The suchThat operator allows the Morel system to generate all possible values, rather than putting the burden on the user.

We considered asking people to write

from i in extent int
where myPredicate (i)

but it would be intimidating to ask people to work with infinite sets of values, and it is unnecessary to specify the type int explicitly. So instead the syntax is

from i suchThat myPredicate (i)

[julianhyde]

Oso on twitter remarked that lack of types makes code difficult to understand. You can use type annotations if you wish:

from i: int suchThat myPredicate (i)