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

Материал из ESyr's Wiki pages.

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

На нек-рое время будем считать, что СУБД работает в однопольз режиме.

Человечек представляет собой большой класс пользователей, который видит БД как большой набор данных, которые предст именами.

Имена:

• Основнеон – имена таблицы
• Имена столбцов
• Кроме того могут быть представления, которые есть СКЛ-запросы, которые видятся как таблицы
• И мена представлений
• Ещё в начлае сентября мы говорили, что набор файлов можно считать БД, если над ним опред огранич целостносчти. Они тоже проименованы
• Имена огранич целостности
• БД начиная с System R обладает свойством активности. Можно опред хранимые процедуры, которые срабатывают при опред условиях, и ими тоже можно управлять
• Триггеры

С этой стороны БД видна как набор именованных объектов., вот на интерфейсе СКЛ-РСС имён нет, там используется покортежный доступ, и используются не имена, а внутр идентификаторы. Про природу идентификаторов лектор рассказывать не будет, потому что у него нет времени. По идентификатору можно легко определить, где находится объект на диске, для столбца, где он нахддится на внутр памяти и т. д.

Всё это (переывод имён в идентифик) делает компилятор.

Задача компилятора SQL – выработать такую процедуру, у которой основные команды – команды вот этого интерфейса.

Одна из первых его функций – когда делается синт анализ, и вот тут забавная история, вотлич от Яп, компилятор ЯП по входному файлу может узнать, что означ все имена в этой программе. Либо это имена. которые определены в программе, либо это внешние имена. Здесь область определния имён – База Данных. Поэтому окмпилятор работает в среде БД. Компилятор SQL вне БД бессммысленен.

До Системы Р у них была БД, в которой хранились данные пользователя, и была отдельная БД, которая азывалась словарём-справочником, где были все имена. И те языковые средства которые поддерж в дореляц системах, работали именно с ней. И компиляторы работали именно с ним.

Одно из открытий, которые сделалли разработчики Систем Р, структура отношений, структура таблиц, она очень хорошо опдходит для храниения катоаложной информации. И можно всю информацию о БД сделать частью БД. Все вещи, которые работают с SQL, состоят из двух частей:

1. Интенсиональная часть (метаданные) – данные, которые описывают структуру и семантику
2. Экстенсиональная чатсь ()данные.

Если вспомнить УМЛ, то интенс часть – модель. В терминологии БД это схема.SQL который позволяет определить эти данные – метамодель. Метаметамодель – стандарт языка SQL.

Какие таблицы существуют:

Есть таблицы, которые содержат описание всех таблиц – SYSTABLES, в том числе и она сама

Таблицы, которые описывают все столбцы всех таблиц – SYSCOLUMNS, в том числе и её столбцы.

SYSVIEWS,

SYSCONSTRAINS

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

При этом компилятор ведёт себя как обычное приложение, и вытаскивает из RSS описательные таблицы. Вопрос, как он добирается до таблицы SYSTABLES, чтобы узнать, где находится таблицы SYSTABLES. Идея первого знакомства – любой приличный человек для того, чтобы познакомиться с человеком, должен иметь общего знакомого. Тут хороший знакомый – системные таблицы. И у них можно сделать предопр идентификатор: у SYSTABLES – 1, SYSCOLUMNS – 2, и т д.

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

Основные два класса операций:

1. Операция сканирования базовой таблицы
   1. Открыть сканирование
   2. fetch – дать следующую строку таблицы в порядке обхода
   3. Закрыть Сканирование – послед просмотр таблицы. Два осн способа:
      1. Просмотр от начала до конца, это позволяет таблицу просомтреть
      2. Сканирование через индекс - таблице может быть определно рроизв количество индексов, которое позволяет ассоциативно обащ к таблице. На самом деле, индексы позволяют ключи как по одиночному знач ключа, так и по диапазону, в частности от макс до мин. Индексы в Систем Р позволяют просмотреть таблицу в порядке возрастания ключа ндекса. Для некрых запросов это очень важное свойство.
2. Insert
3. Delete – удалить текущую строку сканир
4. Update – обновить текущую строку

RSS – абсолютно тупая система с абсолютно тупым интерфейсом, все права проверяются в СКЛ, и это делает компилятор.

В СКЛ принят такой опдход – для обесп безопасности данных необходимо две процедуры – аутентификация – процедура, при выполнении которой она пытается понять, не жулик ли Вы. Лектор не будет говорить про неё, так как в тех СУБД, которые лектор знает, она доверяется ОС, которая проверила, что Петя это Петя, а не Вася или Буниковский.

Идентификация – список идентиф, которые записаны в таблице пользователей.

Что такое уник идентиф пользователя, нигде это не зафиксировано. В ЮНИХ это УИД.

Вторая часть – авторизация. Если какой-то аутентиФИЦ ПОЛЬХователь собирается выполнить некрую операцию над некрыми объектами БД, то нужно проверить, имеет ли он на это право. Это берёт на себя СКЛ. На пальцах: первая идея – чято если ккой-то пользователь создаёт какой-то объект БД (базовую таблицу), то он становится её владельцем и он может выполнить любые действия над ней. Одно из прав владельца таблица – передать все или часть прав другому пользователю ()GRANT. Я. авторизованный Петя, и авторизованный на передачу своих Прпав Васи передаю право читать из таблицы и право передавать право читать другим пользователям. Получается сложный граф. Если будет бльше времени на СКЛ, то весной лектор расскажет подробно об этом.

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

Как это реализовано: есть таблица привилегий пользователей, и компилятор в неё лезет. Если прав хватает, то всё хорошо, если прав нет, то возникает вопрос безопасности – что говорить.

Есть одна задача безопасности, которую лектор не знает, как решать. Представьте себе, что мы хотим сделать очекнь безопаснубюю БД, из которой нельзя домтаваьт данные, но можно делать агрегатные запросы, например «сколько человек уверены в том, что они буддисты». Как доказать, что выполнив в произвольном порядке подобные запросы, не дать получить точную информацию.

Статист БД существуют много лет, но никто не задавался подобным уровнем надёжности.

Представления

Это текст на языке SQL, который сохраняется в БД, и пользователи его могут использовать как имя базовой таблицы. При работе с представлением система должна вести себя так, что как если бы выполнялся запрос, формировалась таблица и уже с ней производилась работа. Но реально так не делают. ДелаетсЯ vieew sybstitution, в место, где стоит представление, вставляется его текст, и оказывается, что если так сделать, то запрос выполняется гораздо эффективнее. Аналогичяным образом происходит обработка огранич целостности и триггеров.

Структуры данных

Систем Рвские:

БД в Систем Р представляла собой набор сегментов внешней памяти. Не ищите аналогий с терминами из существующих систем, лектор использыет термины, которые исп 30 лет назад в том смысле, в котором они исп. Сегмент 0 область магнитного диска или файл. Существенное требование – сегомент долджен целиком находмиться на одном диске. Каждый сегмент делился на набор блоков. Все блоки для однои БД одного и того же размера. Функционально и по структ данным сегменты делились на два класса: 1.Сегменты данных 2.Сегменты журнала - оставляем на потом Сегменты данных осдержат базовые таблицы и индексы. Требование такое – любая таблица целиком находится в одном сегменте, и все индексы там же.

В систем-Р впервые была использована техика В-деревьев для организации индексов.

Опыт показывает, что про В-деревья писано-переписано 33000 раз, публика знает их плохо.

Есть множество наборов одного сегмента, и будем считать, что они связаны списков.

Блок данных:

<n, i> = tid (triple identifier)

//нужно дополнить!

Значение идентификатора строки не меняется за всё время существования строки.

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

В качества бонуса тем, кто ходит на лекции, вопрос, который лектор любит задавть на экзамене: Как можно было бы делать – все блоки побить на части, первые 25 – описательные локи, а остальное распред динамически. Но это не классно, так как из-за этих варчаров можно напихать много маленьких строк или мало больших. В систем Р для этого делали две динамических области. Как делать менеджер памяти? Очень просто – с двух строн, одну сверху, другую снизу. Как только сошлись – память в блоке кончилась.

Здесь нет проблем фрагментации – считается, что все операции в основной памяти дешёвые, и все сдвижки делаются там. Из-за этой косвености это делается легко.

Из n, i делается ссылка в m, j, а если переползает ещё раз, то старое место очищается, и там ставится ссылка в k, l.

Ровно такая схема используется в mobile ip. Есть постоянный адрес, но устройство двигается по миру, и можно через фик ип добраться до устройства, и нужно менять одну запись.

Придумали это мы, а не сетевики.

Сколько же в мире идиотво, которые не могут придумать простых вещей. Кроме немногих, которым это удаётся.

Таблица занимает кучу-кучу блоков, в каждом блоке куча стргок. В Систем Р было динамич изменение структуры таблицы, и можно добавить динамич новый столбец. Ещё одна вещь, которая делалась в СКЛ с Систем Р – значение по умолчанию. Можно придумать, что при выполнении такой операции берутся все блоки, все переезжают, начинается жуткая свистопляска. На самом деле не так. есть систаблес и сисколумнс. В действительности описание нового столбца попадает только в каталог. Как добиться того, чтобы при выборке из БД можно было понять сколько реальтно столбцов. Для этого делается простая вещь – при каждой строке нужно писать, сколько там реально хранится столбцов. И добавлять в строку новые столбцы, только когда её явно обновляешь. Ещё один вопрос. Систем Р нереляционная система, потому что там допускались неопр знач. Если в принципе в БД допуск неопр значения, то во вмех столбцах, кроме возм ключей они будут допускаться. Это значит, что могут быть такие строки, что задано только возм ключ, и всё. Как это хранить, Например, битовые данные, там разрешаются все знач, и нечем их покрасить. Тем не менее, многие призводителей СУБД и хранили для неопр знач по 1-2-3 байта. Лектор приписывает его Систем Р из благородных соображ, но на самом деле лектор подозр, что оно наше. Вместо числа хранить шкалу. ! означает, что она есть, 0, что неопр значение. И длину шкалы хранить. Лекторр умоляет, просит, усвоить это.

Правило хорошего тона – не выносить интимные вещи наружу. В этом случае это tidы. Почему это нехорошо – тиды не меняются и живут всегда, но это преувеличение, и иногда тиды меняются. Это бывает при восстановлении. Но Оракл это разрешает.

Индексы

Лектор перечислит основные требования, которые естественно предъявлять к системам поддержки индексов.

1. прямой доступ к строкам по значению уникального ключа – первичная потребность.
2. Доступ к набору строк по неуникальному индексу
3. Упорядоч доступ по диапазону ключей C1 <= a <=C2
4. Время не должно зависеть от значения ключа

На самом деле, так называемый компилятор, который лектору стыдно называть компилятором, потому что там всего намешано, и больше всего искуственного интеллекта именно там.

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

Б в В-деревьях не от слова Байер.

В-деревья полностью сбалансированы. Узлом в В-дереве является блок во внешней памяти. Они могут быть сильно ветвистыми. В-деревья строятся таким образом, что длина пути одно и та же для всех ветвей. Сбалансированные деревья АВЛ не сбалансированы – запомнить. Они почти сбалансированы. Сдесь балансировка полная. И из-за этого удослветворяется последнее свойство. Сильная ветвистость нужна для небольшой глубины. Глубина дерева – Наташа по основанию Маши (logm(n)).

• 4096 байт - блок
• 32-разряд – ссылка

Лектора судьба баловала – он был первым человеком в СССР, который сделал реализацию в В-дереве для ФС, и впервые исп. для БД.

При глубине 2 можно индексировать таблицы до 100 мегабайт. При 3 – 100 гигабайт, при длине 4 – терабайты.

Ещё одна вещь, которая делается в БД – буферизация в осн. памяти. тек блоки, котрые около корня, обычно всегда сидят в памяти, и посему даже для терабайтных таблиц не больше 3 обращений к внеш памяти.