Вордовские лекции (1121814), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

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

1. Nested loops. Хорошо работает, когда один из операндов имеет небольшую мощность. Если он помещается в память, то по нему запускается внутренний цикл. В тех случаях, когда одно из отношний имеет небольшую можность, его пытаются использовать

2. Sort-merge. Позаимствован из алгоритмов внешней сортировки. На первом шаге оба отношенифя сортируютсся по атрибуту, по которому они соединяются. Предположим, образовалось два списка. Работает только на отношении равно. Плох тем, что работает только на сортированных списках.Выбирается, как правило, в тех случаях, когда к моменту сеодинения мы имеем отсортированный список.

3. Hashjoin. Для потроения таблиц в основной памяти. Нужно организовать данные таким образом, чтобы, зная ключ, получить доступ к данным за одно обращение. Каждая запись имеет вид ключ-данные. Выбирается функция, называющаяся хэш-функция. Единственное требование к ней – генерировать ключи не длиннее длины ключа. Идея хеширования состоит в том, что по ключу делаем его свёртку. Есть хэш=таблица, в которой для каждого ключа есть значение хэш=функция. Если плотность таблицы маленькая, то мы действительно получаем доступ ха одно обращение. Если таблица заполнена, то возникают коллизии. Как ни странно, есть много людей, которые не могут сказать ни одну хорошую хэш-функцию, а может этому мешает наш любимый перл, в котором есть много полуфабрикатов. Наиболее чатсо используемая функция – получающая от деления на простое число. Множесвто остатков от деления на простые числа – поле. Хорошее хэширование – когда элементы разразываются равномерно по области. Идея hashjoin: выбирается хэш-функция, ктороая работтает для обоих отношений, применяется к атрибуту а, и все полученные значения помещаются в bucketы, они попадают в кортежи, лдля которых свётрка даёт одно и то же значение. Пусть у R1 образовалось n bucketов (p1...pn), у R2 – m (q1...qm). Кортежи смогут соединится только тогда, когда значения хэш-функции совпадают. Чем хорош алгоритм – дешёвая операция, если есть ;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. Избыточность – эту алгебру можно сократить до трёх операций – аналоги проекции, присваивания, ??? (лектор её называть не будет, так как это ничего не даст)

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

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

r – отношение – значение отношения

A – имя атрибута отношения

T – тип атрибута (тип А)

v – значение T

(r) - индекс

H(r) – заголовок r {<A, T>} никакие два атрибута в заголовке не могут иметь одно и то же имя

t(r) – кортеж, соотв. H(r) {<A, T, v>}

B(r) – тело r {t(r)}

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

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

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

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

Exists – квантор существования. Exists t(r) (...) - тру, если найдётся хотя бы один кортеж, который удовлетворяет внутреннему условию.

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

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

Операция <NOT>

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

s = <NOT> r

1. Заголовок результата совпадает с заголовком операнда

H(s) = H(r)

1. B(s) = {t(s) : exists t(r) (t(r) не принадлежит B(r) and t(s)=t(r)) }

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

Базы данных 05.10.06

Алгебра А

Операция отрицания:

S = <NOT> r

H(s) = H(r)

B(s) = {t(s) : exist t(r) (t(r) не принадлежит B(r) and t(s) = t(r))}

Самая интеересная операция – операция реляционной конъюнкции.

До этого ещё будут опередлены две операции.

Удаление атрибутов – операция, аналогичная операции проекции. Но тут указываются не те аттрибуты, которые остаются, а те, которые удаляются.

<REMOVE>

s = r <REMOVE> A //A – атрибут заголовка H(r)

тебуется, чтобы чуществовал тип Т, такой, что <A, T> Принадлежит H(r). Но в этом месте физтеховцы (лектор читает сокращеннуб версию курса пятикурсникам физтеха) прижучили – операции должны выполняться для любых операндов, и понятно, что можно её переделать так, чтобы оно так и было (ничего не делать). Третий манифест говорит, что пустые подмножества равноправны.

H(s) = H(r) minus {<A, T>}

B(s) = {t(s) : exists t(r) exists v (t(r) принадлежит B(r) and v принадлежит Т and <A, T ,v> принадлежит t(r) and t(s) = t(r) minus {<A, T, v>})} //v – значение типа Т

Это (NOT?) формула, которую будем использовать при вычислении кортежей. Это (REMOVE) смешанная формула, в которой жве кортежные переменные и одна доменная. Обе формулы являются формулами исчисления предикатов первого порядка. Предикаты только на русском языке называются переменными. Чем старше тсановишься, тем больше задумываешься, что же такое понимал до сих пор (что аткое переменная). На английском – предикат – placeholder – заменитель.

Кстати, чтобы мы не жумали, чот вот, если человек чиатет эту алгкбру А. Пришедший со стороны, думает, что люди, которые писали алгебру А, аткие умные, написали такие определения. На саомм деле Это не Дейта и ... придумали, им помог математик, который занимался аналогичной вещью.

Переименование:

<RENAME>

s = r <RENAME> (A, B) //А прееименовывается в В

условие: существует Т такой, что (<A, T> принадлежит H(r) and <B, T> не принадлежит H(r))

H(s) = (H(r) minus {<A, T>}) union {<B, T>}

B(s) = {t(s) : exists t(r) exists v (t(r) принадлежит B(r) and v принадлежит T and <A, T, v> принадлежит t(r) and t(r) = (t(r) minus {<a, T, v>} union {<B, T, v>})}

Конъюнкция:

<AND>

s = r1 <AND> r2

условие: Если атрибут <A, T1> принадлежит H(r1) и <A, T2> принадлежит H(r2), то тип T1 = T2. Знак равенства означкет тождественность, эквивалентность, равны т и т т к являются одним объектом.

H(s) = H(r1) union H(r2)

B(s) = {t(s) : exists t(r1) exists t(r2) (t(r1) принадлежит B(r1) and t(r2) принадлежит B(r2) and t(s) = t(r1) union t(r2))}

n – степень H(r1)

m – степеннь H(r2)

k – число совпадающих атрибутов

Тогда степень результата – n+m-k

Сначала рассмотрим ситуацию, когда общих атрибутов нет, то есть пересечение пусто. Тогда степень объелинения – n+m. Тогда степень кортежа – n+m. Тогда для любых двух кортежей, которые принадлежат ... . Получим расширенное декартово произведение.

Тогда пусть n=m=k. Тогда мы получим результат степени n=m=k. Тогда мы получим результат, когда при опрелделении кортежей мы получим ... . То есть пересечение.

Характеристики

Список файлов лекций