ровать кортежи на основе значений некоторых атрибутов или комбинации атрибутов. В случае операции проекции подобная группировка позволяет системе исключить кортежи-дубликаты, в случае операции соединения - найти соответствуюшие друг другу кортежи, а в случае операции обобщения - вычислить отдельные обобщенные значения (например, по фуппам). Существует несколько методов подобной фуппировки кортежей.

1. Последовательный просмотр (или метод грубой силы ).

2. Поиск по индексу.

3. Поиск по хеш-таблице.

4. Слияние.

5. Хеширование.

6. Комбинация названных выше методов.

На рис. 17.4-17.8 приведены псевдокоды процедур реализации перечисленных методов для операции соединения (операции проекции и обобщения оставлены читателю в качестве упражнения). На этих рисунках используются следующие соглашения. Прежде всего, R и S - это отношения, которые должны быть соединены, а С - их общий атрибут (возможно, составной). Предполагается, что возможен последовательный доступ к кортежам обоих отношений R и S по одному за одну операцию. Эти кортежи в последовательности доступа будут обозначаться как R[l], R[2], ..., R[m] и S[l], S[2], S[n] соответственно. Для соединенного кортежа, составленного из атрибутов кортежей R[i] и S[j]5 будет использоваться обозначение R[i] * S[j]. И наконец, переменную-отношение R будем считать внешней, а переменную-отношение S - внутренней (поскольку они управляют внешним и внутренним циклами просмотра соответственно).

Последовательный просмотр

Метод последовательного просмотра или грубой силы иногда также называют простым методом. В этом случае рассматриваются все возможные комбинации кортежей (т.е. каждый кортеж отношения R проверяется в сочетании с каждым кортежем отношения S, как показано на рис. 17.4).

Замечание. Метод последовательного просмотра часто называют методом вложенных циклов, но это название нельзя считать адекватным, поскольку вложенные циклы используются в реализациях всех названных выше методов.

do i := 1 to m ; /* Внешний цикл */

do j := 1 to n ; /* Внутренний цикл */

end ; end ;

if R[i].C = S[j].C then <K результату добавить соединенный кортеж R[i] * S[j]> ;

Рис. 17.4. Метод последовательного просмотра

Давайте проанализируем затраты, связанные с использованием метода последовательного просмотра.

Замечание. Здесь мы ограничимся только анализом затрат на выполнение операций ввода-вывода, хотя на практике может потребоваться также учесть другие параметры (например, затраты времени центрального процессора).

Прежде всего, ясно, что для реализации этого метода потребуется всего п * m операций чтения кортежей. А как в отношении операций записи кортежей? Какова кардинальность результата операции соединения? (Количество операций записи кортежа будет равно кардинальности результирующего отношения, если последнее требуется записывать на диск.)

В частном, но достаточно важном случае соединения типа многие к одному (например, соединение типа внешний ключ к соответствующему потенциальному ключу ) кардинальность результирующего отношения почти всегда точно совпадает с величиной m или п в зависимости от того, какое из отношений, R или S, расположено на стороне многие рассматриваемого соединения.

Теперь рассмотрим более общий случай соединения типа многие ко многим . Пусть dCR - количество различающихся значений атрибута С отношения R, по которому выполняется соединение, и dCS имеет тот же смысл, но для отношения S. Если предположить, что значения атрибутов распределены равномерно (т.е. любое значение атрибута С может быть встречено с той же вероятностью, что и другие значения), то для данного кортежа отношения R существует n/dCS соответствующих кортежей в отношении S со значением атрибута С, равным значению этого атрибута в рассматриваемом кортеже из отношения R. Таким образом, общее количество кортежей в соединении (т.е. кардинальность результирующего отношения) будет равно (т * n)/dCS. Или, если повторить изложенные рассуждения, начав с кортежа в отношении S, кардинальность результирующего отношения составит (п * m)/dCR. Эти две оценки будут различными, если dCS Ф dCR, т.е. если в отношении R сушествуют значения атрибута С, которые не встречаются в отношении S, и наоборот, в этом случае следует использовать худшую из оценок.

Конечно, как уже отмечалось, на практике подсчитываются операции ввода-вывода страниц, а не кортежей. Поэтому предположим, что в отношениях R и S на странице помещается соответственно pR и pS кортежей (т.е. отношения занимают m/pR и n/pS страниц соответственно). Теперь легко увидеть, что процедура, псевдокод которой показан на рис. 17.4, выполнит (m/pR) + (m*n)/pS операций чтения страниц. Аналогично, если поменять местами роли отношений R и S (отношение S считать внешним, а R - внутренним), количество операций чтения страниц составит (n/pS) + (n*m)/pR.

Для примера предположим, что m = 100, п = 10 ООО, pR = 1 и pS = 10. Тогда результатами вычисления последних двух формул будут значения 100 100 и 1 001 ООО операций чтения страниц соответственно.

Замечание. В описанном подходе в качестве внешнего отношения желательно использовать меньшее из двух исходных отношений (в данном случае понятие меньшее относится к количеству занимаемых им страниц внешней памяти).

Завершая краткое обсуждение метода последовательного просмотра, заметим, что этот прием является наихудшим из всех. В нем предполагается, что отношение S не имеет ни индекса, ни хеш-таблицы для атрибута С, по которому выполняется соединение. Эксперименты, проведенные Биттоном (Bitton) [17.7], показали, что если предполагае-

мая ситуация (отсутствие индексов и хеш-таблиц) действительно имеет место, то методы обработки можно улучшить, построив нужный индекс или хеш-таблицу динамически и продолжив обработку запроса с помощью методов поиска по индексу или хеш-таблице (см. следующие два подраздела). Как упоминается в конце следующего раздела, эта идея поддерживается и в [17.37].

Поиск по индексу

Теперь рассмотрим ситуацию, в которой для атрибута S.C внутреннего отношения S существует индекс X (рис. 17.5). Преимущество поиска по индексу по сравнению с методом последовательного просмотра состоит в том, что благодаря наличию индекса X для данного кортежа внешнего отношения R возможен переход непосредственно к соответствующему кортежу внутреннего отношения S. Общее количество операций чтения кортежей из отношений R и S будет равно кардинальности результирующего отношения операции соединения. Общее количество операций чтения страниц для отношений R и S составит (m/pR) + (mn/dCS) при наихудшем предположении, что каждая операция чтения кортежа из отношения S требует обращения к отдельной странице.

/* Использование индекса X по атрибуту S.C */

do i := 1 to m ; /* Внешний цикл */

/* Пусть для значения индексированного атрибута R[i].C */

/* существует к вхождений индекса: Х[1], .... Х[к] */

do j := 1 to к ; /* Внутренний цикл */

/* Пусть S[j] - кортеж из S, на который указывает индекс X[j] */ <к результату добавить соединенный кортеж R[i] * S[j]> ; end ; end ;

Рис. 17.5. Поиск по индексу

Если кортежи отношения S хранятся в порядке значений соединяющего атрибута С, то количество операций чтения страницы уменьшится до значения (m/pR) + (mn/dCS)/pS. Воспользовавшись теми же пробными значениями, что и выше (т = 100, п = 10 ООО, pR = 1, pS = 10), и предположив, что dCS = 100, получим в результате вычисления двух последних формул значения 10 100 и 200 соответственно. Разница между полученными значениями указывает, что кортежи хранимых отношений целесообразно размещать в подходящей физической последовательности [17.9].

Однако при оценке затрат следует учитывать и накладные расходы, связанные с выполнением операций чтения в самом индексе. Наихудшим является предположение, что при поиске соответствующих кортежей в отношении S для каждого кортежа в отношении R потребуется выполнить непредвиденный поиск по индексу, требующий чтения страницы для каждого уровня индекса. Для индекса, обладающего х уровнями, операция поиска добавит к общему количеству операций чтения страницы еще т*х операций. На практике х обычно имеет значение 3 или меньше. (Более того, весьма вероятно, что верхний уровень индекса на протяжении всей обработки данных будет находиться в памяти, что значительно сократит количество операций чтения страниц.)