Les sous-requêtes ajoutent-elles une puissance expressive aux requêtes SQL?

SQL a-t-il besoin de sous-requêtes?

Imaginez une implémentation suffisamment généralisée du langage de requête structuré pour les bases de données de relations. Étant donné que la structure de l' SELECTinstruction SQL canonique est en fait assez importante pour que cela ait un sens, je ne fais pas directement appel à l'algèbre relationnelle, mais vous pouvez l'encadrer en ces termes en faisant des restrictions appropriées sur la forme des expressions.

Un SQL SELECTrequête est généralement constitué d'une saillie (la SELECTpartie) un certain nombre d' JOINopérations (la JOINpartie), un certain nombre d' SELECTION opérations (en SQL, les WHEREclauses), puis mis en fonctionnement à goutte ( UNION, EXCEPT, INTERSECT, etc.), suivie d' une autre Requête SELECTSQL.

Les tables jointes peuvent être les résultats calculés d'expressions; en d'autres termes, nous pouvons avoir une déclaration telle que:

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;

Nous ferons référence à l'utilisation d'une table calculée dans le cadre d'une requête SQL en tant que sous-requête. Dans l'exemple ci-dessus, le second (en retrait) SELECTest une sous-requête.

Toutes les requêtes SQL peuvent-elles être écrites de manière à ne pas utiliser de sous-requêtes? L'exemple ci-dessus peut:

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

Cet exemple est quelque peu faux ou trivial, mais on peut imaginer des cas où beaucoup plus d'efforts pourraient être nécessaires pour récupérer une expression équivalente. En d'autres termes, est-il vrai que pour chaque requête SQL avec sous-requêtes, il existe une requête q ' sans sous-requêtes telle que q et q ' sont garantis pour produire les mêmes résultats pour les mêmes tables sous-jacentes? Limitons les requêtes SQL au formulaire suivant:$q$$q'$$q$$q'$

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 ...

Etc. Je pense que les jointures externes gauche et droite n'ajoutent pas grand-chose, mais si je me trompe, n'hésitez pas à le signaler ... en tout cas, elles sont également équitables. En ce qui concerne les opérations d'ensemble, je suppose que l'une d'entre elles est correcte ... union, différence, différence symétrique, intersection, etc. tout ce qui est utile. Existe-t-il des formulaires connus auxquels toutes les requêtes SQL peuvent être réduites? L'un de ces éléments élimine-t-il les sous-requêtes? Ou existe-t-il des cas où il n'existe pas de requête sans sous-requête équivalente? Les références sont appréciées ... ou une démonstration (par preuve) qu'elles sont ou non requises serait fantastique. Merci et désolé si c'est un résultat célèbre (ou insignifiant) dont je suis douloureusement ignorant.

Il y a une certaine confusion terminologique; le bloc de requête entre parenthèses

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

est appelé vue intérieure . Une sous -requête est un bloc de requête dans la clause WHERE ou SELECT, par exemple

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

Dans les deux cas, la vue intérieure ou la sous-requête peut être non imbriquée dans le projet-restrict-join "plat". La sous-requête corrélée avec agrégation se déroule dans les vues internes avec le regroupement, qui se décompose ensuite en requête plate.

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

Quant aux règles algébriques pour l'optimisation des requêtes, l'algèbre relationnelle est connue pour être axiomatisée en réseau relationnel, ce qui simplifie les transformations de requête comme démontré ici et là .

Pour traduire votre déclaration en algèbre relationnelle, je pense qu'elle demande:

$\sigma_A(A)\bowtie \sigma_B(B)$$\sigma_A(\sigma_B(A\bowtie B))$

$\sigma$$\bowtie$

La réponse est "Oui" et il s'agit d'une optimisation de requête standard. Pour être honnête, je ne sais pas comment le prouver d'une manière qui ne pose pas de questions - c'est juste une propriété de sélection et d'adhésion. Vous pouvez argumenter de manière inductive pour ajouter autant de couches de requêtes imbriquées que vous le souhaitez.

De plus, vous pourriez demander:

$A\bowtie B\bowtie C\bowtie\dots$$(A\bowtie B)\bowtie(C\bowtie D)$

Encore une fois, la réponse est oui, car join est associative. Des déclarations similaires peuvent également être faites à propos de la projection.

Un type notable de "sous-requête" qui, je pense, ne peut pas être "aplani" est with. Une façon de voir cela est de noter que si vous avez une withinstruction, vous pouvez avoir une fonction récursive, qui ne peut pas être écrite sans utiliser de sous-requêtes.

Donc, pour résumer: dans le cas spécifique que vous avez mentionné, non, SQL n'a pas besoin de sous-requêtes, et vous pouvez le prouver par induction. Cependant, en général, certaines fonctionnalités nécessitent des sous-requêtes.

"Les sous-requêtes ajoutent-elles une puissance expressive aux requêtes SQL?"

Ils l'ont fait, au moins avant l'introduction d'EXCEPT dans le langage SQL.

Avant l'introduction de EXCEPT, il était impossible d'exprimer une différence relationnelle ou une demi-différence en SQL sans recourir à des sous-requêtes.

De nos jours, tous les opérateurs primitifs "typiques" de "l'algèbre relationnelle" peuvent être exprimés sans sous-requêtes:

NATURAL JOIN peut être fait via NATURAL JOIN, ou JOIN ON
UNION peut être fait via UNION
MINUS peut être fait via EXCEPT
PROJECT / RENAME / EXTEND peut être fait via SELECT
RESTRICT peut être fait via OERE
les littéraux relationnels peuvent être effectués via VALUES
fermetures transitives peuvent être fait par récursif AVEC