Algebra dotazů
Operátor Značka Příkaz SQL
Sjednocení (union) R  S UNION
Průnik (intersection) R  S INTERSECT
Rozdíl (difference) R - S EXCEPT
Výběr (selection) C(R) WHERE
Projekce (projection) L(R) SELECT
Součin (product) R × S FROM
Spojení (join) R S = L(C(R × S)) SELECT FROM WHERE
­ přirozené R S
­ theta R
C
S
equijoin C : x = y
Vypuštění duplicit (R)
(duplicity elimination) (SELECT) DISTINCT
Sdružování (grouping) L(R) GROUP BY
Třídění (sorting) L(R) ORDER BY
Množinové operace vždy ve dvou variantách: bag (B), set (S)
Paramery operací
* B(R) ­ počet bloků relace R
* T(R) ­ počet záznamů relace R
* V (R, L) ­ počet různých hodnot na atributech L
tj. V (R, L) = T((L(R))
* M ­ velikost potřebné paměti (v blocích)
Iterátory
Operace: Open, Close, GetNext
1
Složitosti základních operátorů
Jednoprůchodové algoritmy
Operátor Potřebné M Přístupy na disk
,  1 B
,  B B
, , -, ×, min(B(R), B(S)) B(R) + B(S)
(nested-loop) M  2 B(R)B(S)/M
Jednoprůchodové algoritmy na setříděném vstupu
Operátor Potřebné M Přístupy na disk
,  B B
, , -, 2 B(R) + B(S)
Dvouprůchodové algoritmy založené na třídění
Operátor Potřebné M Přístupy na disk
, 

B 3B
, , - B(R) + B(S) 3(B(R) + B(S))
max(B(R), B(S)) 5(B(R) + B(S))
(sort-join) B(R) + B(S) 3(B(R) + B(S))
Dvouprůchodové algoritmy založené na hashování
Operátor Potřebné M Přístupy na disk
, 

B 3B
, , - B(S) 3(B(R) + B(S))
B(S) 3(B(R) + B(S))
(hash-join) B(S) (3 - 2M/B(S))(B(R) + B(S))
2