Руководство по созданию эффективных запросов

с
очетание
 
отношений
Настоящая мощь реляционной теории и баз данных SQL основана на соче-
тании данных из нескольких таблиц.
В этом разделе описываются алгоритмы операций, сочетающие данные, 
в том числе декартово произведение, соединение, объединение, пересече-
ние и даже группировка. Удивительно, но большинство этих операций мож-
но реализовать с помощью практически идентичных алгоритмов. По этой 
причине мы обсуждаем алгоритмы, а не операции, которые они реализуют. 
Мы будем использовать имена 
R
и 
S
для входных таблиц при описании этих 
алгоритмов.

---

52

Еще больше теории: алгоритмы
Вложенные циклы
Первый алгоритм предназначен для получения декартова произведения, то 
есть множества всех пар строк из входных таблиц. Самый простой способ 
вычислить произведение – перебрать строки таблицы 
R
и для каждой строки 
из 
R
перебрать строки таблицы 
S
. Псевдокод этого простого алгоритма пред-
ставлен в лис тинге 3.4, а графическое представление алгоритма показано 
на рис. 3.8.
Листинг 3.4 

Псевдокод для вложенных циклов
FOR row1 IN table1 LOOP
FOR row2 IN table2 LOOP
output (row)
END LOOP
END LOOP
Время, необходимое для этого простого алгоритма, пропорционально про-
изведению размеров таблиц ввода: 
rows(R)*rows(S)
.
Интересный теоретический факт состоит в том, что любой алгоритм, вы-
числяющий декартово произведение, не может работать лучше; то есть стои-
мость любого алгоритма будет пропорциональна произведению размеров 
его входов или выше. Конечно, некоторые вариации этого алгоритма могут 
работать лучше, чем другие, но стоимость остается пропорциональной про-
изведению.
Небольшие модификации алгоритма вложенного цикла позволяют вы-
числить практически любую логическую операцию, сочетающую данные из 
двух таблиц. Псевдокод из лис тинга 3.5 реализует соединение.