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

Question

Нужны ли 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 $ Q $ с подразделениями существует запрос $ Q '$ без подразделений, так что $ Q $ и $ Q' $ гарантированно даст одни и те же результаты для тех же базовых столы? Давайте ограничим запросы SQL следующей формой:

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? Что -нибудь из них устраняет подборы? Или есть некоторые случаи, когда нет эквивалентных, без подборов запросов? Ссылки ценится ... или демонстрация (по доказательствам), что они или не требуются, была бы фантастической. Спасибо, и извините, если это знаменитый (или тривиальный) результат, который я мучительно невежественен.

Answer 1

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

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

называется Внутренний вид. Анкет А подпрограмма Является ли блок запросов в пункте, где или выберите, например,

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

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

Answer 2

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

Можем ли мы переписать $ sigma_a (a) bowtie sigma_b (b) $ как $ sigma_a ( sigma_b (a bowtie b)) $?

(Где $ sigma $ выбрана, а $ bowtie $ присоединяется.)

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

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

Можно ли писать каждую последовательность соединений как $ a bowtie b bowtie c bowtie dots $ [в отличие от, скажем, $ (a bowtie b) bowtie (c bowtie d) $]?

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

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

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

Answer 3

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

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

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

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

Естественное соединение может быть сделано с помощью естественного соединения или присоединиться к
Союз можно сделать через профсоюз
Минус можно сделать через
Project/rename/extend можно сделать через
Ограничение может быть сделано через то, где
Реляционные литералы могут быть сделаны с помощью ценностей
переходные закрытия могут быть сделаны через рекурсивное с