Czy podzapytania dodają ekspresyjnej mocy do zapytań SQL?

29

Czy SQL potrzebuje podkwerend?

Wyobraź sobie wystarczająco uogólnioną implementację ustrukturyzowanego języka zapytań dla baz danych relacji. Ponieważ struktura kanonicznej SELECTinstrukcji SQL jest naprawdę bardzo ważna, aby miało to sens, nie odwołuję się bezpośrednio do algebry relacyjnej, ale można to sformułować w tych kategoriach, wprowadzając odpowiednie ograniczenia dotyczące formy wyrażeń.

Instrukcja SQL SELECTzapytanie na ogół składa się z występu (stanowiącego SELECTczęść) pewnej liczby JOINoperacji (w jego JOINczęści), pewnej liczby SELECTION operacji (w SQL, WHEREwarunków), a następnie nastawiono mądry operacji ( UNION, EXCEPT, INTERSECT, itd.), A następnie kolejny SELECTZapytanie SQL .

Łączone tabele mogą być obliczonymi wynikami wyrażeń; innymi słowy, możemy mieć takie oświadczenie, jak:

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;

Będziemy odnosić się do użycia tabeli obliczeniowej jako części zapytania SQL jako podzapytania. W powyższym przykładzie drugi (wcięty) SELECTjest podzapytaniem.

Czy wszystkie zapytania SQL mogą być napisane w taki sposób, aby nie używać podkwerend? Powyższy przykład może:

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

Ten przykład jest nieco fałszywy lub trywialny, ale można sobie wyobrazić przypadki, w których odzyskanie równoważnego wyrażenia wymagałoby znacznie więcej wysiłku. Innymi słowy, czy jest tak, że dla każdego zapytania SQL z podzapytaniami istnieje zapytanie q bez podzapytań, dzięki czemu q i q mają zagwarantowane takie same wyniki dla tych samych bazowych tabel? Ograniczmy zapytania SQL do następującej formy: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 ...

I tak dalej. Myślę, że lewe i prawe zewnętrzne sprzężenia nie dodają wiele, ale jeśli się mylę, proszę zauważyć, że ... w każdym razie, są one również uczciwą grą. Jeśli chodzi o ustawione operacje, wydaje mi się, że każda z nich jest w porządku ... połączenie, różnica, różnica symetryczna, przecięcie itp. ... wszystko, co jest pomocne. Czy są jakieś znane formy, do których można ograniczyć wszystkie zapytania SQL? Czy któryś z nich eliminuje podzapytania? A może istnieją przypadki, w których nie istnieje równoważne zapytanie bez zapytania? Referencje są doceniane ... lub demonstracja (na dowód), że są lub nie są wymagane, byłaby fantastyczna. Dzięki i przepraszam, jeśli jest to słynny (lub trywialny) rezultat, którego boleśnie ignoruję.

Patrick87
źródło
5
Moja intuicja mówi mi, że zawsze możesz połączyć wszystko i wybierać stamtąd, o ile nie potrzebujesz zagregowanych wartości. Wydaje się, że wybranie wszystkich pozycji o wartości większej niż średnia w kolumnie wymaga obliczenia wartości średniej, a zatem wymaga podzapytania.
Raphael
@Raphael Jestem całkiem pewien, że możesz nawet tworzyć wartości zagregowane, po prostu musisz zrobić więcej samozłączeń i grupowań (co powoduje, że jest on wykładniczo większy, ale nadal możliwy). Nie jestem jednak pewien, jak formalnie udowodnię, że możesz zrobić wszystko w ten sposób.
Kevin
@Kevin Czy na pewno liczba wymaganych operacji nie zależy od liczby wierszy? Ponieważ nie możemy tego mieć, prawda?
Raphael
1
Normalne przykładzie jest to dla konieczności podkwerenda liczy duplikatach select count(*) from (select id from sometable group by id having count(*)>1) d. Ponieważ zawiera group by, nie podałem tego jako odpowiedzi.
Mark Hurd
BTW AFAIK w normalnym SQL, ONklauzula jest wymagana dla JOINs, chociaż iloczyn krzyżowy jest uzyskiwany tylko przecinkiem.
Mark Hurd

Odpowiedzi:

9

Istnieje pewne zamieszanie terminologiczne; blok zapytania w nawiasie

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

nazywa się widokiem wewnętrznym . Podzapytanie jest blok zapytań w obrębie albo gdzie i SELECT np

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

W obu przypadkach widok wewnętrzny lub podzapytanie można odłączyć do „płaskiego” łączenia projektu z ograniczeniem. Skorelowane podkwerendy z agregacją odplasowują się do wewnętrznych widoków z grupowaniem, które następnie odplasowują się do płaskiego zapytania.

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

Jeśli chodzi o reguły algebraiczne dotyczące optymalizacji zapytań, wiadomo, że algebra relacyjna jest aksjatyzowana w Relational Lattice, która upraszcza transformacje zapytań, jak pokazano tu i tam .

Tegiri Nenashi
źródło
Jestem ciekaw. Czy możesz dodać przykład zapytania wykorzystującego średnią z niektórych pól, np. Wybierając wszystkie wpisy o wartości powyżej średniej? Nie jest dla mnie jasne, jak by to wyglądało po spłaszczeniu.
Raphael
16

Aby przetłumaczyć twoje zdanie na algebrę relacyjną, myślę, że pyta:

σZA(ZA)σb(b)σZA(σb(ZAb))

σ

Odpowiedź brzmi „Tak” i jest to standardowa optymalizacja zapytania. Szczerze mówiąc, nie jestem pewien, jak to udowodnić, nie zadając pytań - to tylko własność wyboru i dołączenia. Możesz argumentować indukcyjnie, aby dodać dowolną liczbę warstw zagnieżdżonych zapytań.

Dodatkowo możesz zapytać:

ZAbdo(ZAb)(dore)

Ponownie odpowiedź brzmi tak, ponieważ łączenie jest asocjacyjne. Podobne stwierdzenia można również powiedzieć o projekcji.

Jednym z godnych uwagi rodzajów „podzapytań”, które moim zdaniem nie mogą być „spłaszczone”, jest with. Jednym ze sposobów na to jest zauważenie, że jeśli masz withinstrukcję, możesz mieć funkcję rekurencyjną, której nie można zapisać bez użycia podkwerend.

Podsumowując: w konkretnym przypadku, o którym wspomniałeś, nie, SQL nie potrzebuje podkwerend i możesz to udowodnić indukcyjnie. Ogólnie jednak istnieją funkcje wymagające podkwerend.

Xodarap
źródło
Zachowanie rekurencyjne withzostało wprowadzone w SQL: 1999 i sprawia, że ​​powstały język jest bardziej wyrazisty.
András Salamon
1

„Czy podzapytania dodają ekspresyjnej mocy do zapytań SQL?”

Zrobili to, przynajmniej przed wprowadzeniem EXCEPT w języku SQL.

Przed wprowadzeniem EXCEPT nie było sposobu, aby wyrazić różnicę relacyjną lub półróżność w SQL bez uciekania się do podzapytań.

Obecnie wszystkie „typowe” prymitywne operatory „algebry relacyjnej” można wyrazić bez podzapytań:

NATURALNE DOŁĄCZENIE może być wykonane przez NATURALNE DOŁĄCZENIE, lub DOŁĄCZENIE DO
UNIONU może być wykonane przez UNION
MINUS może być wykonane poprzez WYJĄTK
PROJEKTU / NAZWA / WYDŁUŻ może być wykonane przez WYBIERZ
OGRANICZENIE może być wykonane poprzez GDZIE
TREŚCI relacyjne mogą być wykonane poprzez WARTOŚCI
przechodnie mogą być zamknięte być zrobione poprzez rekurencyjne Z

Erwin Smout
źródło