title: Is it possible to decorrelate all correlated SQL subqueries?
body: <p>(Note: Not a duplicate of <a href="https://stackoverflow.com/questions/3850816/sql-represent-a-subquery-in-relational-algebra">this question</a>, since that question had a specific query in mind. This is more from a general, theory perspective.)</p>
  
  <p>I am learning about databases in college, and I have learned that SQL databases, in order to execute a query, first translate it into <a href="https://en.wikipedia.org/wiki/Relational_algebra" rel="nofollow noreferrer">relational algebra</a> in order to form a plan of how to execute it. Relational algebra makes it quite easy to represent non-correlated SQL subqueries, which we can then combine into joins or set operations if needed. For instance, we can quite easily express</p>
  
  <pre><code>SELECT y FROM Table WHERE y NOT IN (SELECT x FROM AnotherTable);
  </code></pre>
  
  <p>as a set difference between two queries.</p>
  
  <p>However, as far as I have learned, relational algebra provides no mechanism to express SQL's notion of correlated subqueries, or queries that capture columns from a parent query and thus must be executed multiple times, such as this example below:</p>
  
  <pre><code>SELECT employee_number, name
    FROM employees AS emp
    WHERE salary &gt; (
      SELECT AVG(salary)
        FROM employees
        WHERE department = emp.department);
  </code></pre>
  
  <p>(In this example, the subquery in the outer <code>WHERE</code> clause is correlated to the employee's department, meaning that the subquery must be run once for each employee in order to filter results by department.)</p>
  
  <p>Like many other correlated subqueries, it is possible to decorrelate this subquery by instead using a join and a single aggregation query, which will allow the query to be perfectly expressible in RA and also cause the subquery to run only once:</p>
  
  <pre><code>SELECT emp.employee_number, emp.name
    FROM employees AS emp
    JOIN (
      SELECT department AS department, AVG(salary) AS avg_salary
      FROM employees
      GROUP BY department) AS salaries
      ON emp.department = salaries.department
    WHERE emp.salary &gt; salaries.avg_salary;
  </code></pre>
  
  <p>Is it possible, however, to express <em>all</em> correlated subqueries as decorrelated subqueries, in order to express them as relational algebra, or are there some correlated subqueries that must be expressed as such? In other words, is SQL correlation simply a convenience feature that does not add anything to SQL's expressive power, or is RA merely an implementation guideline for which SQL is more expressive because of this feature?</p>
  
  <p>If the former, what is the proof/algorithm of this? If the latter, is there a generally accepted form of RA that expresses correlation directly?</p>