Добавляют ли подзапросы выразительную силу к запросам SQL?

29

Нужны ли SQL подзапросы?

Представьте себе достаточно обобщенную реализацию языка структурированных запросов для реляционных баз данных. Поскольку структура канонического оператора SQL на SELECTсамом деле очень важна для того, чтобы это имело смысл, я не обращаюсь непосредственно к реляционной алгебре, но вы можете сформулировать это в этих терминах, сделав соответствующие ограничения на форму выражений.

SQL - SELECTзапрос , как правило , состоит из выступа ( SELECTчасть) некоторого количества JOINопераций (далее JOINчасть), некоторое количество SELECTION операций (в SQL, в WHEREпунктах), а затем установить-накрест операции ( UNION, EXCEPT, INTERSECTи т.д.), за которым следует другой SQL- SELECTзапрос.

Соединяемые таблицы могут быть вычисленными результатами выражений; другими словами, мы можем иметь такое утверждение, как:

SELECT t1.name, t2.address
  FROM table1 AS t1 
  JOIN (SELECT id, address 
          FROM table2 AS t3 
         WHERE t3.id = t1.id) AS t2
 WHERE t1.salary > 50,000;

Мы будем ссылаться на использование вычисляемой таблицы как части запроса SQL в качестве подзапроса. В приведенном выше примере второй (с отступом) SELECTявляется подзапросом.

Могут ли все запросы SQL быть написаны таким образом, чтобы не использовать подзапросы? Пример выше может:

SELECT t1.name, t2.address
  FROM table1 AS t1 
  JOIN table2 AS t2
    ON t1.id = t2.id
 WHERE t1.salary > 50,000;

Этот пример несколько ложный или тривиальный, но можно представить случаи, когда для восстановления эквивалентного выражения может потребоваться значительно больше усилий. Другими словами, является ли это случаем, что для каждого SQL-запроса с подзапросами существует запрос без подзапросов, такой, что и гарантированно дают одинаковые результаты для тех же базовых таблиц? Давайте ограничим запросы SQL следующей формой:qqqq

SELECT <attribute>,
      ...,
      <attribute>
 FROM <a table, not a subquery>
 JOIN <a table, not a subquery>
  ...
 JOIN <a table, not a subquery>
WHERE <condition>
  AND <condition>
  ...
  AND <condition>

UNION
 -or-
EXCEPT
 -or-
<similar>

SELECT ...

И так далее. Я думаю, что левое и правое внешние соединения не добавляют много, но если я ошибаюсь, пожалуйста, не стесняйтесь указывать на это ... в любом случае, они также являются честной игрой. Что касается операций над множествами, я думаю, что все они хороши ... объединение, разность, симметричная разность, пересечение и т. Д. ... все, что полезно. Существуют ли какие-либо известные формы, к которым можно привести все запросы SQL? Удаляет ли какой-либо из этих подзапросов? Или есть случаи, когда не существует эквивалентного запроса без подзапроса? Ссылки приветствуются ... или демонстрация (доказательством) того, что они требуются или не требуются, была бы фантастической. Спасибо, и извините, если это знаменитый (или тривиальный) результат, о котором я до боли не знаю.

Patrick87
источник
5
Моя интуиция говорит мне, что вы всегда можете объединить все и выбирать там, если вам не нужны агрегированные значения. Выбор всех записей со значением, превышающим среднее значение его столбца, по-видимому, сначала требует вычисления среднего значения, поэтому требуется подзапрос.
Рафаэль
@Raphael Я вполне уверен, что вы даже можете использовать агрегированные значения, вам просто нужно делать больше самостоятельных объединений и группировок (делая это экспоненциально больше, но все же возможно). Не уверен, как я формально докажу, что ты можешь все делать таким образом.
Кевин
@Kevin Вы уверены, что количество необходимых операций не зависит от количества строк? Потому что мы не можем этого иметь, не так ли?
Рафаэль
1
Нормальный пример я для требующего подзапроса рассчитывают дубликаты: select count(*) from (select id from sometable group by id having count(*)>1) d. Потому что это включает в себя, group byя не поставил это как ответ.
Марк Херд
Кстати, в обычном SQL это ONусловие требуется для JOINs, хотя перекрестный продукт получается только через запятую.
Марк Херд

Ответы:

9

Есть некоторая путаница в терминологии; блок запроса в скобках

SELECT t1.name, t2.address
  FROM table1 
  JOIN (SELECT id, address 
          FROM table2 AS t3 
         WHERE t3.id = t1.id) 

называется внутренним видом . Подзапрос является блок запроса в пределах либо WHERE или ВЫБРАТЬ положение, например ,

select deptno from dept
where 3 < (select count(1) from emp 
           where dept.deptno=emp.deptno)

В любом случае внутреннее представление или подзапрос могут быть не вложены в «плоский» проект-ограничение-соединение. Коррелированный подзапрос с агрегацией превращается во внутренние представления с группировкой, которая затем превращается в плоский запрос.

select deptno from dept d
    where 3 < (select avg(sal) from emp e
               where d.deptno=e.deptno)

select d.deptno from dept d, ( 
    select deptno from emp e
    group by deptno
    having avg(sal) > 3
) where d.deptno=e.deptno

select d.deptno from dept d, emp e
where d.deptno=e.deptno 
group by d.deptno
having avg(sal) > 3

Что касается алгебраических правил для оптимизации запросов, то известно, что реляционная алгебра аксиоматизируется в реляционную решетку, которая упрощает преобразования запросов, как показано здесь и там .

Тегири Ненаши
источник
Мне интересно. Можете ли вы добавить пример запроса, который использует некоторые поля среднего значения, например, выбрать все записи со значением выше среднего? Мне не ясно, как это будет выглядеть после сплющивания.
Рафаэль
16

Чтобы перевести ваше утверждение в реляционную алгебру, я думаю, что оно спрашивает:

Можем ли мы переписать как ?σ A ( σ B ( A B ) )σA(A)σB(B)σA(σB(AB))

(Где - это выбор, а - это соединение.)σ

Ответ «Да», и это стандартная оптимизация запросов. Честно говоря, я не уверен, как это доказать, не задавая вопросов - это просто свойство выбора и присоединения. Вы можете спорить индуктивно, чтобы добавить сколько угодно слоев вложенных запросов.

Кроме того, вы можете спросить:

Может ли каждая последовательность соединений быть записана как [В отличие от, скажем, ]?( A B ) ( C D )ABC(AB)(CD)

Опять же, ответ да, потому что объединение является ассоциативным. Аналогичные утверждения можно сделать и о проекции.

Один заметный тип «подзапроса», который, я думаю, не может быть «расплющен» with. Один из способов увидеть это - заметить, что если у вас есть withоператор, то вы можете иметь рекурсивную функцию, которая не может быть написана без использования подзапросов.

Итак, подведем итог: в конкретном случае, который вы упомянули, нет, SQL не требует подзапросов, и вы можете доказать это индуктивно. В общем, есть функции, которые требуют подзапросов.

Xodarap
источник
Рекурсивное поведение via withбыло введено в SQL: 1999 и делает результирующий язык более выразительным.
Андрас Саламон
1

"Добавляют ли подзапросы выразительную мощь к запросам SQL?"

Они сделали, по крайней мере, до введения EXCEPT на языке SQL.

До появления EXCEPT не было никакого способа выразить реляционную разницу или полуразличие в SQL без обращения к подзапросам.

В наши дни все «типичные» примитивные операторы «реляционной алгебры» можно выразить без подзапросов:

ЕСТЕСТВЕННОЕ СОЕДИНЕНИЕ может быть выполнено через ЕСТЕСТВЕННОЕ СОЕДИНЕНИЕ, или СОЕДИНЕНИЕ В СОЕДИНЕНИИ
может быть сделано через СОЮЗ
МИНУС может быть выполнен через ИСКЛЮЧИТЬ
ПРОЕКТ / ПЕРЕИМЕНОВАНИЕ / РАСШИРИТЬ может быть сделано через ВЫБРАТЬ
ОГРАНИЧЕНИЕ может быть сделано через ГДЕ
реляционные литералы могут быть выполнены через ЗНАЧЕНИЯ
транзитивные замыкания могут быть сделано через рекурсивный СО

Эрвин Смут
источник