Базы Данных, 08 лекция (от 29 сентября)

Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Это очень фундаментальное определние, но оно очень не конструктивно.

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

Для theta-сооединения существует только один алгоритм, достаточно известный, который называется nested loops. Пусть нужно реализовать операцию расшир дек произведи, имея foreach. Решение – сделать два вложенных цикла, снаружи обходить первое множество, внутри второе, и наружу выдаются пары. Для случая соединения это единственный алгоритм. Недостатки – очень большая операция.

Эквисоединение

Эквисоединение — соединение с условием по равенству. Достоинства: наиболее часто используемый вид соединения, есть хороший алгоритм. Нет хороших алгоритмов для соединений общего вида. Эквисоединение – очень хорошее, и для него есть три вида алгоритмов:

1. Nested loops. Хорошо работает, когда один из операндов имеет небольшую мощность. Если он помещается в память, то по нему пускается внутренний цикл. В тех случаях, когда одно из отношний имеет небольшую можность, его пытаются использовать
2. Sort-merge. Позаимствован из алгоритмов внешней сортировки. На первом шаге оба отношения сортируютсся по атрибуту, по которому они соединяются. Предположим, образовалось два списка. Работает только на отношении равно. Плох тем, что работает только на сортированных списках.Выбирается, как правило, в тех случаях, когда к моменту сеодинения мы имеем отсортированный список.
3. Hashjoin. Для потроения таблиц в основной памяти. Нужно организовать данные таким образом, чтобы, зная ключ, получить доступ к данным за одно обращение. Каждая запись имеет вид ключ-данные. Выбирается функция, называющаяся хэш-функция. Единственное требование к ней — генерировать ключи не длиннее длины ключа. Идея хеширования состоит в том, что по ключу делаем его свёртку. Есть хэш-таблица, в которой для каждого ключа есть значение хэш-функция. Если плотность таблицы маленькая, то мы действительно получаем доступ ха одно обращение. Если таблица заполнена, то возникают коллизии. Как ни странно, есть много людей, которые не могут сказать ни одну хорошую хэш-функцию, а может этому мешает наш любимый перл, в котором есть много полуфабрикатов. Наиболее часто используемая функция — получающая от деления на простое число. Множество остатков от деления на простые числа — поле. Хорошее хэширование — когда элементы разразываются равномерно по области. Идея hashjoin: выбирается хэш-функция, которая работает для обоих отношений, применяется к атрибуту а, и все полученные значения помещаются в bucketы, они попадают в кортежи, для которых свётрка даёт одно и то же значение. Пусть у R1 образовалось n bucket'ов (p₁, …, p_n), у R2 — m (q₁...q_m). Кортежи смогут соединится только тогда, когда значения хэш-функции совпадают. Чем хорош алгоритм — дешёвая операция, если есть ;l bucketов первого и второго отношения, которе образуются, которые соединяются, то их можно запустить параллельно. А если хорошо выбрана hash-функция, то bucket'ы могут быть маленькими. Алгоритм придумал Дэвид Де Вито.

Theta-соединение (и, в частности, эквисоедниненние) — проекция ограничения расширенного декартового соединения. Последовательность действий:

1. Rename
2. Times
3. Where
4. Project

Вспомним пример из второй лекции. Там такая очень простенькая ИС рассматривалась — кадровая. Мы пытались поддерживать информацию о всех служащих и, в частности, информация об отделе. Потом поняли,что хранить информацию об отделе для каждого невыгодно. Оказывается, этот процесс, когда берем большое множество аттрибутов и улучшаем его свойства путём проектирования — стандартный способ проектирования, при котором есть много внешних ключей. При таком нормальном проектировании имя внешнего ключа равна возможному ключу.

Эквисоединение двух отношений, у которых есть совпадающие атрибуты, с последним действием в виде проецирования, в результате оставляем один экземпляр атрибута. Используется в подавляющем большинстве случаев. В алгебре А соединение — базовая операция. Алгебра А — настоящая алгебра.

Деление

Операция определяется для двух отношений, одно из которыз бинарное, другое унарное. Результат — те и только те значения кортежей атрибута a, для которого множество значений второго включает в себя тело кортежа R2.

R1(AB) DIVIDE BY R2(B) = R(A)

Запрос, в котором мы хотим квантифицированный результат — найти таких людей, которые учавствуют во всех проектах.

Операция реляционного деления выражается через другие операции алгебры Кодда.

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

Алгебра А

Схема рассмотрения

1. Базовый набор операций
2. Полнота алгебры — как можно вывести все операции алгебры Кодда
3. Избыточность — эту алгебру можно сократить до трёх операций — аналоги проекции, присваивания, ??? (лектор её называть не будет, так как это ничего не даст)

Следующая тема — исчисление кортежей, которая основана на исчислении предикатов, там будет определяться, что такое правильно построенная формула, здесь же будет их примеры.

Некоторые обозначения

Почти для каждого B_r, существует t_r, которое удовлетворяет (соответствует) заголовку, но не входит в его тело, кроме B_r, которое включает все возможные заголовки.

Три множества: заголовок, кортеж — множество триплетов, тело — множество кортежей.

Могут существовать отношения с пустым заголовком, и/или не содержат кортежей.

У отношения с пустым заголовком может быть два тела — либо пустое множество кортежей, либо один пустой кортеж. По этому поводу сделана наука, которая рассматривает свойства этих двух отношений. И рассматреваемая алгебра фактически булевская на этих двух отношениях.

∃ t_r (...) — true, если найдётся хотя бы один кортеж, который удовлетворяет внутреннему условию.

and, or, minus, union — операции алгебры множеств.

Для обозначения понятий алгебры А используются < >. В оригинальной книжке там треугольники закрашенные.

Операция <NOT>

пусть применяется к r, s — результат операции.

s = <NOT> r

1. Заголовок результата совпадает с заголовком операнда
2. H_s = H_r
3. B_s = {t_s : ∃ t_r (t_r ∉ B_r and t_s=t_r) }

Очень похоже на соединение, только попадает не склейка, а кусочек, спроецированный на первый операнд.