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

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

Перейти к: навигация, поиск

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

Биологи работают для того, чтобы обогощать результатами математику,... Программирование же помогает другим людям со своими задачами. Это очень прикладная обцласть, не смотря на все фундаментальные вещи Так что это скорее, не раздел науки, а раздел инжинерии (ударение на предпоследний слог). И некоторые люди очень стесняются слова инжинерия, инжинер. Инжинерия требует практического созидания. Очень трудно жить с таким мировоззрением, так как денег не дают.
Лектор любит, когда определения говорят лаконично
Не надо говорить, что схемы не пересекаются. Пересечь можно всё, но результат может быть пуст или нет

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

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

Для 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 R2 Result
a1 b1 b1 a1
a1 b2 b2 a4
a1 b3 b3
a2 b1
a3 b2
a4 b1
a4 b2
a4 b3

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

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

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

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

Лектор решил всё стереть, так как это отдельная тема и нечего пистьа на грязной доске.

Алгебра А

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

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

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

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

r отношение – значение отношения
A имя атрибута отношения
T тип атрибута (тип А)
v значение T
Hr заголовок r {<A, T>} никакие два атрибута в заголовке не могут иметь одно и то же имя
tr кортеж, соотв. Hr {<A, T, v>}
Br тело r {tr}

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

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

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

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

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

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

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

Операция <NOT>

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

s = <NOT> r

  1. Заголовок результата совпадает с заголовком операнда
  2. Hs = Hr
  3. Bs = {ts : ∃ tr (tr ∉ Br and ts=tr) }

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


Базы Данных


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28


Календарь

пт чт пт чт пт чт пт чт пт чт
Сентябрь
01 07 14 15 21 22 28 29
Октябрь
  05 06 12 13 19 20 26 27
Ноябрь
  02 03 09 16 17 23 24 30
Декабрь
  07 08 14 15

Вопросы к экзамену
1999 2000 2001 2002 2003 2004 2005 2006


Дополнительная информация к экзамену


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы