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

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

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

System R Два уровня доступа:

1. Мультидоступ – корректное обесп возможности одновр работы нескольких пользователей.
   1. Логический (пользователь) — транзакция. Для БД исключительно важным понятием является логическая целостность. Транзакция должна поддерживать логическую целостность.
   2. Физический. В лог уровне транзакции от пользователя. Физ уровень – уровень поддержания структурной целостности. Должны быть такие точки, в пределах которых БД должна быть в правильном состоянии. Иногд, в пределах транзакции или более мелких операций мы не можем не нарушить физцелостность. Физ уровень – уровень системы, некрым аналогом транзакции является операция, операция уровня RSS.

Транзакция - Это некрое посл действий уровня SQL, а операция – посл команд RSS, операция – последовательность микроопераций. Пример: добавляется строка в таблицу. Микрооперации: выделение свободной памяти – достаточно большое крупное действие, втсавка строки в то местор, в которое выделили память. Если в таблице n индексов, то их надо обновить, и каждое обновление – свои микрооперациию

И то, и то имеет отношение к тому, как восстановить БД, если в процессе возникает сбой.

Понятие логической целостности. Приеняемый в Систем Р механизм был основан на механизме блокировок. Если мы говорим вставить строку, то единицей являкется строка, если удалить – тоже. Чтобы это всёреализовалось, в Сситем Р ыбли логические блокировки, и они были видны пользователю.

Логические блокировки нектоторых логических объектов.

Физическая целостность.

Физические блокировки – обычно блокировки блоков.

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

Есть дерево. Любой поиск идёт сверху вниз. А обновление идёт от листка к корню. Это очень большая неприятность, как бы хотелось работать: микрооперация читает корневой блок, смотрит, куда дальше, отпустить корневой ... до листа. А обновляем в обратном порядке. Чтение и запись несовместимы, поэтому возникает дэдлок.

На логическом уровне могут быть тупики. Любой тупик – цикл в гнрафе. Но если разрешать блокировки и там, и там, то возникают блокировки. НадоЮ, чтобы при попытке установки аппаратной блокировки не было программной.

Личный опыт лектора показывает, что вот на этом уровне – единственно возможный способ поиска тупиков – поиск циклов, то на системном уровне можно обойтись таймаутами.

Тупик возникает как правило, если выполняется операция чтения и обновление. Подходы:

1. Блокировать корень до конца микрооперации. Дерево ильно ветвистое, и вероятность того, что две операции пойдут по одному пути, маленькая, а мы накладываем ограничения,Ю которые позволяют работать с ними последовательно. Это плохой способ. А хорошего сопособа нет.
2. Блокировать поддерево. Как узнать уровень, с какого блокировать? Ничего путного от статей, посвящённых подобной блакировке, не было. Лектор сотоварищи придумали собственный метод, котороым он гордистся.ю До начала блокировок выполняется игра:напирмер, длч Вставки ключ, tid Идём оп дереву, пока не дойдём до нужного листа. По этому пути все блоки сохраняются в буфера. Начинаем играть – проигрываем оп вставки без работы с внеш память. Потом блокируем нужный блок в режиме опбновления, и проигрываем операцию ещё раз. Если выше не поднимается, то проигрываем начисто. Если же поднимается, то все блокировки снимаем и начинаем сначала. Если пут поменялся, то начимнаем совсем сначала.

Другой метод организации индексов: Про б-деревья лектор будет спрашивать всё, даже то, что не рассказывал.

[править] Хеширование

В понедельник лектор расскзаыыал хеширование физтеху и понял, что 10-15 минут достаточно.

Есть большой блок вснеш памяти, кот орый используется для размещ нек массика. Элементы – ключ/запись. Есть спецфункция, которая выбир для орг таблиц – хэш-функция. Она вырабатывает ключ, разрядность которого меньше, чем адреса. По-русски это называют хэширование рандомизацией или перемешивание. Нужно уметь выбирать такую хэшфункцию, которая равномерно разбрасыввает ключи по пространству. С тем, чтобы вероятность попадания нового ключа на занятое место мнимальна. В результате поняли, что лучше всего работает деление на число и взятие остатка. Для маленьких таблиц - 7, потом 13, потом 43. На ВМК не очень хорошо дело с математикой, но лектор надеется, что нам успели внушить, что простые числа хорошие.

Известно, это некоторый факт, который никто никогда не доказывал, но все считают, что он верный, что хэшьаблицы хорошо работают при заполненности менее 70-75 процентов. Подход:

1. Если возникает первая коллизия, и если хэш-функция, берётся новое простое число, перераскидываются все ключи – называется перестройка хэш-таблиц.
2. Создание списков в каждой ячейке таблицы. Этот подход ломает идею хеширования. За что хеширование любят: если всё хорошо, то мы попадаем в нужный элемент за 2 операции (вычисление, переход). Как только возн области переполнения, все вырождается. Ещё неприятный момент – таблица статическая, а кускочи возникают в динамике.
3. Как только нарываемся на коллизию, начинаем искать вниз первый свободный элемент, и если свободен, то пишем туда ключ. При поиске ещё страньше. Пока нет коллизий, поиск работает замечательно. Но, как только возникают коллизии, начинается хождение по кругу.

Когда идёт работа, таблица перестаёт быть хорошо перемешанной. В этом случае применяем вторичное хэширование. Лектор не знакти, есть ли какая-нибудь теория, для вторичного хэширования – тот адрес, вниз от которого нужно искать свободное место. Берётся ключ и делится на квадрат. Если применяыть такой подход, то штучки, связанные с перепонением, достаточно хорошо раскидываются по всей таблице.

Ричард Столлман определил облик 20 века

У Столлмена дефект – слишком коммунист.

Лектору не нравится, что он на них слишком влияет в этом отношении.

С чего он начал в 85 году. Он очень обидился на мир, потому что должен подписывать NDA. У него давно есть программочка, которая по заданному набору ключей умеет подсчитать совершенную хэш-функцию.

Б-деревья хорошая структура индексации, но нужно пройти от корня до личста, а это 2-3 обмена с внеш памятью. А тут за один обмен.

Один из прогрессивных методов выполн методов соединения – hashjoin.

Широко известный в узких кругах человек – vitold li(t)vwin

С сасмого начала происходит работа с 2^n блоками. И в них помещаются ключи со ссылками на строки. Поддерживается такая шкала: 2^n бит. Как только возникает коллизия, Заводится его двойник, и хэшфункция тоже становится 2^(n+1). Как происходит работа: берётся поиск, делается поиск по ключ, делим его на 2^n, а какого размера у нас шкала. Если шкала 2 в степени (н+1), и смотрим, есть ли у него напарник, и применяем новую хэшфункцию, если нет – тсарую.

У нас она настолько популярна, что у лектора есть специальная папочка с его статьями.

Человек интересен. Живёт в Европе. Жил в Англии, потом обиделся на англичан, перебрался во Францию .В опследник годы занимается вебом.

Ещё один человек – альтернативный канадец, у него идеи, как сблизить б-деревья и хэш-таблицы. Хранить небольшое б=дерево, которое заменяет хэшфункцию. Но засчёт б-деревянных особенностей позволяет сделать линейнвй порядок. Связывают ключи, для которых одна ссылк на блок. Для лектора единственный пример метода б-деревьев в основной памяти.

все. про индексы закончил.

походите на курс Фомичёва про индексы.

Индексы хороши, когда их можно объяснять жестами.

Можно было бы двигаться в соотв с ист правдой и расскзать, как относились к транзакции 31 год назад. Лектор начнёт с тогоЮ что сегодня считают транзакцией, а потом из современной картинки лектр будет рассказывать, каак это делалось в систем р.

[править] ACID-транзакции

1. Atomicity – атомарность – свойство транзакции «всё или ничего». Транзакция – последовательность операций. Либо результат транзакции успешен и её результат остаётся в БД, либо после неё не остаётся ничего. Атмарность – важное свойство. В ряде случаев, хотя с этим не согласен Дейта, если смотреть на СКЛ, в ряде случаев с помощью отлельной операции изменения БД перевести из одного согласованного состояния в другое, использовав одну операцию .Пример: те же самые таблицы отделов, в таблице отделов хранится количество служащих, и хоть ты тресни, надо выполнить две операции, причё если выполнится только одна операция, то БД будет неправильная, поэтому эти операции будут выполняться в транзакции
2. Consitensy – целостность – значит, мы с васми уже говорили, что целостное состояние бд – главная особенность набора файлов, который считается бд. Для того, чтобы хранить сложную инфцию, файлы должны быть связаны, и что такое связь, не всегда просто определть. На саомм деле, ни одна БД не знает, когда она целостна, а когда нет. Для того, чтобы СУБД могла поддерживать целостность бд, надо сказать, при каких условиях пользователи согластны считать БД целостной. Значитт, эээ, уоль сокоро мы говрим, что, эээ, нельзя гарантировать, вообще говоря, что оно сумеет перевести БД из одного целост состояния, в другое, поэтому свойство транзакции – любая транзакция должна начинаться, когда БД находится в логичесик целостном состоянии (это состояние, коиорое удовл некоему логическому условию, которое на неё навешано),и любая транзакция обязана оставить после себя БД в целостном состоянии. Любая транзакция может оканчиваться commit (зафиксировать – этот пользователь или приложение просят проверить СУБД всё ли в порядке, и сделать так, чтобы эти изменения были видны всем остальным. Пока они не проверены,Ю они не должны влиять на работу пользователей.) или rollback (откатить – по каким-то причинам поняли, что всё, что было сделано в пределах транзакции, не верно, и нужно из бд всё это убрать. В этом случае транзакция, rollback – возврат в исходную точку, commit – проверка всех изменений и произведение некрых действий, который делают изменинея видимыми. Если коммит обламывается с проверкой, то делается rollback, и при таком подходе БД останется в целостном состоянии). Что такое проверка целостности – не надо думать, что если администратор напихал 33000 проверки целостности. На самом деле, работает компилятор, он знает смысл операций, но знает, над какими объектами БД будут они выполняться, посему знает, какие ограничения целостности могут быть нарушены, и именно они проверяются в конце транзакции. Понитие транзакции - идеальное для изоляции пользователей.
3. Isolation Изоляция – обеспечение такого режима работы, когда он не чувствует присутствия других пользователей. Когда лектор быдет это рассказывать подробно, то мы увидим, что это туфта, и пользователь во время работы видит чудеса, которые можно списать на Господа Бога, но это не Он, это Иванов, это Иванов через субд.
4. Durability – долговечность – после коммита что бы не произошло на этом свете: злостный партнё р поделил его на ноль, сумасшедший взорвал машину, весь мир может погибнуть, а транзакция может остаться целой. База данных остаётся вечной и бесконечной. В принципе, результат транзакции должен пережить Апокалипсис.

Младшие поколения начинают называть consistency консистентностью, лектор это не любит.