Fügen Unterabfragen SQL-Abfragen Ausdruckskraft hinzu?

29

Benötigt SQL Unterabfragen?

Stellen Sie sich eine ausreichend verallgemeinerte Implementierung der strukturierten Abfragesprache für Beziehungsdatenbanken vor. Da die Struktur der kanonischen SQL- SELECTAnweisung eigentlich ziemlich wichtig ist, damit dies sinnvoll ist, appelliere ich nicht direkt an die relationale Algebra, aber Sie könnten dies in diesen Begriffen einrahmen, indem Sie die Form der Ausdrücke entsprechend einschränken.

Eine SQL - SELECTAbfrage besteht im allgemeinen aus einem Vorsprung (der SELECTTeil) eine bestimmte Anzahl von JOINOperationen (der JOINTeil), eine bestimmte Anzahl von SELECTION Operationen (in SQL, die WHEREKlauseln), und dann gesetzt weise Operationen ( UNION, EXCEPT, INTERSECT, etc.), gefolgt von einem anderen SQL- SELECTAbfrage.

Tabellen, die verknüpft werden, können die berechneten Ergebnisse von Ausdrücken sein. Mit anderen Worten, wir können eine Aussage haben wie:

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;

Wir werden uns auf die Verwendung einer berechneten Tabelle als Teil einer SQL-Abfrage als Unterabfrage beziehen. Im obigen Beispiel ist die zweite (eingerückte) SELECTeine Unterabfrage.

Können alle SQL-Abfragen so geschrieben werden, dass keine Unterabfragen verwendet werden? Das obige Beispiel kann:

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

Dieses Beispiel ist etwas fälschlich oder trivial, aber man kann sich Fälle vorstellen, in denen erheblich mehr Aufwand erforderlich ist, um einen äquivalenten Ausdruck wiederherzustellen. Mit anderen Worten, gibt es für jede SQL-Abfrage mit Unterabfragen eine Abfrage ohne Unterabfragen, so dass und garantiert dieselben Ergebnisse für dieselben zugrunde liegenden Tabellen liefern? Beschränken wir SQL-Abfragen auf das folgende Formular: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 ...

Und so weiter. Ich denke, linke und rechte äußere Verknüpfungen tragen nicht viel dazu bei, aber wenn ich mich irre, können Sie gerne darauf hinweisen ... auf jeden Fall handelt es sich auch um faires Spiel. Was die Mengenoperationen angeht, sind wohl alle in Ordnung ... Vereinigung, Differenz, symmetrische Differenz, Schnittmenge usw. ... alles, was hilfreich ist. Gibt es bekannte Formen, auf die alle SQL-Abfragen reduziert werden können? Beseitigen diese Unterabfragen? Oder gibt es Fälle, in denen keine äquivalente Abfrage ohne Unterabfrage vorhanden ist? Referenzen sind erwünscht ... oder eine Demonstration (durch Nachweis), dass sie erforderlich sind oder nicht, wäre fantastisch. Danke, und tut mir leid, wenn dies ein gefeiertes (oder triviales) Ergebnis ist, von dem ich schmerzlich nichts weiß.

Patrick87
quelle
5
Mein Darm sagt mir, dass Sie immer alles zusammenfügen und von dort auswählen können, solange Sie keine aggregierten Werte benötigen. Die Auswahl aller Einträge mit einem Wert, der größer als der Durchschnitt der Spalte ist, erfordert anscheinend zuerst die Berechnung des Durchschnitts, weshalb eine Unterabfrage erforderlich ist.
Raphael
@Raphael Ich bin mir ziemlich sicher, dass Sie sogar aggregierte Werte erstellen können. Sie müssen nur mehr Self-Joins und Group-Bys erstellen (was es exponentiell größer macht, aber immer noch möglich). Ich bin mir nicht sicher, wie ich formal beweisen würde, dass Sie alles so machen können.
Kevin
@ Kevin Sind Sie sicher, dass die Anzahl der erforderlichen Operationen nicht von der Anzahl der Zeilen abhängt? Weil wir das nicht haben können, oder?
Raphael
1
Das normale Beispiel I für die Erstellung einer Unterabfrage zählt Duplikate: select count(*) from (select id from sometable group by id having count(*)>1) d. Weil es beinhaltet, habe group byich dies nicht als Antwort gegeben.
Mark Hurd
BTW AFAIK in normalem SQL ist die ONKlausel für JOINs erforderlich , obwohl ein Kreuzprodukt nur mit einem Komma erhalten wird.
Mark Hurd

Antworten:

9

Es gibt einige terminologische Verwirrungen. der Abfrageblock in Klammern

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

heißt innere Sicht . Eine Unterabfrage ist ein Abfrageblock innerhalb der WHERE- oder SELECT-Klausel, z

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

In beiden Fällen kann die innere Ansicht oder Unterabfrage nicht in die "flache" Projekteinschränkungsverknüpfung eingebunden werden. Korrelierte Unterabfrage mit Aggregation verschachtelt sich in innere Ansichten mit Gruppierung, die sich dann in flache Abfragen verschachtelt.

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

Bezüglich der algebraischen Regeln für die Abfrageoptimierung ist bekannt, dass die relationale Algebra in ein relationales Gitter axiomatisiert wird, was die hier und da gezeigten Abfragetransformationen vereinfacht .

Tegiri Nenashi
quelle
Ich bin neugierig. Können Sie ein Beispiel für eine Abfrage hinzufügen, die einige Felder als Durchschnitt verwendet, z. B. alle Einträge mit einem überdurchschnittlichen Wert auswählen? Mir ist nicht klar, wie das nach dem Abflachen aussehen würde.
Raphael
16

Um Ihre Aussage in die relationale Algebra zu übersetzen, fragt sie meiner Meinung nach:

σEIN(EIN)σB(B)σEIN(σB(EINB))

σ

Die Antwort lautet "Ja" und es handelt sich um eine Standard-Abfrageoptimierung. Um ehrlich zu sein, ich bin mir nicht sicher, wie ich das ohne Fragen beweisen kann - es ist nur eine Eigenschaft der Auswahl und des Beitritts. Sie können induktiv argumentieren, um beliebig viele Ebenen verschachtelter Abfragen hinzuzufügen.

Zusätzlich könnten Sie fragen:

EINBC(EINB)(CD)

Wieder ist die Antwort ja, weil verbinden assoziativ ist. Ähnliche Aussagen können auch zur Projektion gemacht werden.

Eine bemerkenswerte Art von "Unterabfrage", von der ich denke, dass sie nicht "abgeflacht" werden kann, ist with. Eine Möglichkeit, dies zu erkennen, besteht darin, zu beachten, dass Sie, wenn Sie eine withAnweisung haben, eine rekursive Funktion haben können, die nicht ohne die Verwendung von Unterabfragen geschrieben werden kann.

Zusammenfassend lässt sich sagen, dass SQL in dem von Ihnen erwähnten speziellen Fall keine Unterabfragen benötigt und dass Sie dies induktiv beweisen können. Im Allgemeinen gibt es jedoch Funktionen, für die Unterabfragen erforderlich sind.

Xodarap
quelle
Das rekursive Verhalten über withwurde in SQL: 1999 eingeführt und macht die resultierende Sprache deutlich ausdrucksstärker.
András Salamon
1

Msgstr "Fügen Unterabfragen SQL - Abfragen Ausdruckskraft hinzu?"

Sie taten es zumindest vor der Einführung von EXCEPT in der SQL-Sprache.

Vor der Einführung von EXCEPT gab es keine Möglichkeit, einen relationalen Unterschied oder eine Halbdifferenz in SQL auszudrücken, ohne auf Unterabfragen zurückzugreifen.

Heutzutage können alle "typischen" primitiven Operatoren der "relationalen Algebra" ohne Unterabfragen ausgedrückt werden:

NATURAL JOIN kann über NATURAL JOIN oder JOIN ON
UNION über UNION
MINUS über EXCEPT
PROJECT / RENAME / EXTEND über SELECT
RESTRICT über VALUES durchgeführt werden, wobei
relationale Literale über
Transitive Closures durchgeführt werden können erfolgt durch rekursives WITH

Erwin Smout
quelle