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

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

[[Базы Данных, 07 лекция (от 28 сентября)|Предыдущая лекция]] | [[Базы Данных, 09 лекция (от 05 октября)|Следующая лекция]]

<div class="comment">Биологи работают для того, чтобы обогощать результатами математику,... Программирование же помогает другим людям со своими задачами. Это очень прикладная область, не смотря на все фундаментальные вещи Так что это скорее, не раздел науки, а раздел инженерии (ударение на предпоследний слог). И некоторые люди очень стесняются слова инженерия, инжинер. Инженерия требует практического созидания. Очень трудно жить с таким мировоззрением, так как денег не дают.</div>

<div class="comment">Лектор любит, когда определения говорят лаконично</div>

<div class="comment">Не надо говорить, что схемы не пересекаются. Пересечь можно всё, но результат может быть пуст или нет</div>

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

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

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

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

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

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

<div class="comment">Естественное соединение стоит того, чтобы перед ним покурить.</div>

Theta-соединение (и, в частности, эквисоедниненние)&nbsp;&mdash; проекция ограничения расширенного декартового соединения.  Последовательность действий:
# [[Переименование (Алгебра Кодда)|Rename]]
# [[Декартово произведение (Алгебра Кодда)|Times]]
# [[Ограничение (Алгебра Кодда)|Where]]
# [[Проекция (Алгебра Кодда)|Project]]

<div class="comment">Лектор ответил на один из своих любимых вопросов на экзамене.</div>

Вспомним пример из [[Базы Данных, лекция 02 (от 07 сентября)|второй лекции]]. Там такая очень простенькая ИС рассматривалась&nbsp;&mdash; кадровая. Мы пытались поддерживать информацию о всех служащих и, в частности, информация об отделе. Потом поняли,что хранить информацию об отделе для каждого невыгодно. Оказывается, этот процесс, когда берем большое множество аттрибутов и улучшаем его свойства путём проектирования&nbsp;&mdash; стандартный способ проектирования, при котором есть много внешних ключей. При таком нормальном проектировании имя внешнего ключа равна возможному ключу.

<div class="comment">Одна из околокомпьютерных дам полюбила Советский союз, когда ещё он им был, и она&nbsp;&mdash; хороший мастер придумывать анекдоты:

Реляционные БД напоминают мне гараж для автомобили, и чтобы поставить туда машину, надо её разобрать, разложив по коробочкам все винты болты и т. д, а потом, когда надо её вытащить, её надо собрать, причем помня, какой куда болтик.</div>

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

===Деление===
<div class="comment">Лектор не любит писать на доске, и рисовать картинки особенно противно.</div>

Операция определяется для двух отношений, одно из которыз бинарное, другое унарное. Результат&nbsp;&mdash; те и только те значения кортежей атрибута 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)

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

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

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

<div class="comment">Лектор решил всё стереть, так как это отдельная тема и нечего пистьа на грязной доске.</div>

==Алгебра А==

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

# Базовый набор операций
# Полнота алгебры&nbsp;&mdash; как можно вывести все операции алгебры Кодда
# Избыточность&nbsp;&mdash; эту алгебру можно сократить до трёх операций&nbsp;&mdash; аналоги проекции, присваивания, ??? (лектор её называть не будет, так как это ничего не даст)

<div class="comment">Лектору кажется, что стиль, в котором он будет рассказывать лучше, чем у Дейты. Рассказывет её уже пятый или шестой год, и в первый раз было тркдно, и не было ощущения, чот было понятно, теперь он заставляет понять. Трудность в том, что определение операций формально. Используется класс формул, с помощью которого определяютс яоперации. Почему от них не хочет отказываться лектор&nbsp;&mdash; к формулам надо привыкать.</div>

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

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

{|
 |r
 |отношение &ndash; значение отношения
 |-
 |A
 |имя атрибута отношения
 |-
 |T 
 |тип  атрибута (тип А)
 |-
 |v
 |значение T
 |-
 |H<sub>r</sub>
 |заголовок r {&lt;A, T&gt;} никакие два атрибута в заголовке не могут иметь одно и то же имя
 |-
 |t<sub>r</sub>
 |кортеж, соотв. H<sub>r</sub> {&lt;A, T, v&gt;}
 |-
 |B<sub>r</sub>
 |тело r {t<sub>r</sub>}
 |-
 |}

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

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

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

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

&exist; t<sub>r</sub> (...)&nbsp;&mdash; true, если найдётся хотя бы один кортеж, который удовлетворяет внутреннему условию.

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

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

====Операция &lt;NOT&gt;====

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

s = &lt;NOT&gt; r

# Заголовок результата совпадает с заголовком операнда
# H<sub>s</sub> = H<sub>r</sub>
# B<sub>s</sub>&nbsp;= {t<sub>s</sub>&nbsp;: &exist; t<sub>r</sub> (t<sub>r</sub> &notin; B<sub>r</sub> and t<sub>s</sub>=t<sub>r</sub>) }

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

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.us/wiki/%D0%91%D0%B0%D0%B7%D1%8B_%D0%94%D0%B0%D0%BD%D0%BD%D1%8B%D1%85%2C_08_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_29_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 21: / Строка 21: @@
 # Nested loops. Хорошо работает, когда один из операндов имеет небольшую мощность. Если он помещается в память, то по нему пускается внутренний цикл. В тех случаях, когда одно из отношний имеет небольшую можность, его пытаются использовать
 # Sort-merge. Позаимствован из алгоритмов внешней сортировки. На первом шаге оба отношения сортируютсся по атрибуту, по которому они соединяются. Предположим, образовалось два списка. Работает только на отношении равно. Плох тем, что работает только на сортированных списках.Выбирается, как правило, в тех случаях, когда к моменту сеодинения мы имеем отсортированный список.
-# Hashjoin. Для потроения таблиц в основной памяти. Нужно организовать данные таким образом, чтобы, зная ключ, получить доступ к данным за одно обращение. Каждая запись имеет вид ключ-данные. Выбирается функция, называющаяся хэш-функция. Единственное требование к ней&nbsp;&mdash; генерировать ключи не длиннее длины ключа. Идея хеширования состоит в том, что по ключу делаем его свёртку. Есть хэш-таблица, в которой для каждого ключа есть значение хэш-функция. Если плотность таблицы маленькая, то мы действительно получаем доступ ха одно обращение. Если таблица заполнена, то возникают коллизии. Как ни странно, есть много людей, которые не могут сказать ни одну хорошую хэш-функцию, а может этому мешает наш любимый перл, в котором есть много полуфабрикатов. Наиболее часто используемая функция&nbsp;&mdash; получающая от деления на простое число. Множество остатков от деления на простые числа&nbsp;&mdash; поле. Хорошее хэширование&nbsp;&mdash; когда элементы разразываются равномерно по области. Идея hashjoin: выбирается хэш-функция, которая работает для обоих отношений, применяется к атрибуту а, и все полученные значения помещаются в bucketы, они попадают в кортежи, для которых свётрка даёт одно и то же значение. Пусть у R1 образовалось n bucket'ов (p<sub>1</sub>, &hellip;, p<sub>n</sub>), у R2&nbsp;&mdash; m (q<sub>1</sub>...q<sub>m</sub>). Кортежи смогут соединится только тогда, когда значения хэш-функции совпадают. Чем хорош алгоритм&nbsp;&mdash; дешёвая операция, если есть ;l bucketов первого и второго отношения, которе образуются, которые соединяются, то их можно запустить параллельно. А если хорошо выбрана hash-функция, то bucket'ы могут быть маленькими. Алгоритм придумал Дэвид Де Вито.
+# Hashjoin. Для потроения таблиц в основной памяти. Нужно организовать данные таким образом, чтобы, зная ключ, получить доступ к данным за одно обращение. Каждая запись имеет вид ключ-данные. Выбирается функция, называющаяся хэш-функция. Единственное требование к ней&nbsp;&mdash; генерировать ключи не длиннее длины ключа. Идея хеширования состоит в том, что по ключу делаем его свёртку. Есть хэш-таблица, в которой для каждого ключа есть значение хэш-функция. Если плотность таблицы маленькая, то мы действительно получаем доступ ха одно обращение. Если таблица заполнена, то возникают коллизии. Как ни странно, есть много людей, которые не могут сказать ни одну хорошую хэш-функцию, а может этому мешает наш любимый перл, в котором есть много полуфабрикатов. Наиболее чатсо используемая функция&nbsp;&mdash; получающая от деления на простое число. Множество остатков от деления на простые числа&nbsp;&mdash; поле. Хорошее хэширование&nbsp;&mdash; когда элементы разразываются равномерно по области. Идея hashjoin: выбирается хэш-функция, ктороая работтает для обоих отношений, применяется к атрибуту а, и все полученные значения помещаются в bucketы, они попадают в кортежи, лдля которых свётрка даёт одно и то же значение. Пусть у R1 образовалось n bucket'ов (p<sub>1</sub>, &hellip;, p<sub>n</sub>), у R2&nbsp;&mdash; m (q<sub>1</sub>...q<sub>m</sub>). Кортежи смогут соединится только тогда, когда значения хэш-функции совпадают. Чем хорош алгоритм&nbsp;&mdash; дешёвая операция, если есть ;l bucketов первого и второго отношения, которе образуются, которые соединяются, то их можно запустить параллельно. А если хорошо выбравна hash-функция, то bucket'ы могут быть маленькими. Алгоритм придумал Дэвид Де Вито.
 <div class="comment">Естественное соединение стоит того, чтобы перед ним покурить.</div>