Реляционные базы данных позволяют хранить информацию в нескольких «плоских» (двухмерных) таблицах, связанных между собой посредством совместно используемых полей данных, называемых ключами. Реляционные базы данных предоставляют более простой доступ к оперативно составляемым отчетам (обычно через SQL) и обеспечивают повышенную надежность и целостность данных благодаря отсутствию избыточной информации

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

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

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

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

Данные создают проблемы

В самых простых базах данных каждая запись занимает одну строку, иными словами, телефонной компании необходимо заводить отдельный столбец для каждого фрагмента бухгалтерской информации. То есть одну - для второго абонента «спаренного» телефона, еще одну - для третьего и т. д., в зависимости от того, сколько дополнительных абонентов понадобится.

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

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

Мощные связи

Эдгар Кодд, сотрудник исследовательской лаборатории корпорации IBM в Сан-Хосе, по существу, создал и описал концепцию реляционных баз данных в своей основополагающей работе «Реляционная модель для крупных, совместно используемых банков данных» (A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, июнь 1970).

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

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

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

Кодд сформулировал 12 правил для реляционных баз данных, большинство которых касаются целостности и обновления данных, а также доступа к ним. Первые два достаточно понятны даже пользователям, не обладающим техническими навыками.

Правило 1, информационное правило, указывает, что вся информация в реляционной базе данных представляется как набор значений, хранящихся в таблицах.

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

Суть работы Кодда заключалась в том, что предлагалось с реляционными базами данных использовать декларативные, а не процедурные языки программирования. Декларативные языки, такие как язык запросов SQL (Structured Query Language), дают пользователям возможность, по существу, сообщить компьютеру: «Я хочу получить следующие биты данных из всех записей, которые удовлетворяют определенному набору критериев». Компьютер сам «поймет», какие необходимо совершить шаги, чтобы получить эту информацию из базы данных.

Для работы с огромным количеством активно используемых баз данных применяются программные системы управления реляционными базами данных, созданные такими авторитетными производителями, как Oracle, Sybase, IBM, Informix и Microsoft.

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

Реляционная модель

Реляционная база данных использует набор таблиц, связанных друг с другом посредством определенного ключа (в данном случае это поле PhoneNumber)

База данных (БД) - это поименованная совокупность структурированных данных, относящихся к определенной предметной области и предназначенных для хранения, накопления и обработки с помощью ЭВМ.

Реляционная База Данных (РБД) - это набор отношений, имена которых совпадают с именами схемотношений в схеме БД.

Основные понятия реляционных баз данных:

· Тип данных – тип значений конкретного столбца.

· Домен (domain) – множество всех допустимых значений атрибута.

· Атрибут (attribute) – заголовок столбца таблицы, характеризующий поименованное свойство объекта, например, фамилия студента, дата оформления заказа, пол сотрудника и т.п.

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

· Отношение (relation) – таблица, отражающая информацию об объектах реального мира, например, о студентах, заказах, сотрудниках, жителях и т.д.

· Первичный ключ (primary key) – поле (или набор полей) таблицы, однозначно идентифицирующий каждую из ее записей.

· Альтернативный ключ – это поле (или набор полей), несовпадающее с первичным ключом и уникально идентифицирующий экземпляр записи.

· Внешний ключ – это поле (или набор полей), чьи значения совпадают с имеющимися значениями первичного ключа другой таблицы. При связи двух таблиц с первичным ключом первой таблицы связывается внешний ключ второй таблицы.

· Реляционная модель данных (РМД) - организация данных в виде двумерных таблиц.

Каждая реляционная таблица должна обладать следующими свойствами:

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

2. Каждое значение, записывается на пересечении строки и столбца - является атомарным (неразделимым).

3. Значения каждого поля должны быть одного типа.

4. Каждое поле имеет уникальное имя.

5. Порядок расположения записей несущественен.

Основные элементы БД:

Поле - элементарная единица логической организации данных. Для описания поля используются следующие характеристики:

· имя, например, Фамилия, Имя, Отчество, Дата рождения;

· тип, например, строковый, символьный, числовой, датовый;

· длина, например, в байтах;

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

Запись - совокупность значений логически связанных полей.

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

Целостность данных – это средство защиты данных по полям связи, позволяющее поддерживать таблицы в согласованном (непротиворечивом) состоянии (то есть не допускающее существование в подчиненной таблице записей, не имеющих соответствующих записей в родительской таблице).

Запрос – сформулированный вопрос к одной или нескольким взаимосвязанным таблицам, содержащий критерии выборки данных. Запрос осуществляется с помощью структурированного языка запросов SQL (Srtructured Query Language). В результате выборки данных из одной или нескольких таблиц может быть получено множество записей, называемое представлением.

Представление данных – сохраняемый в базе данных именованный запрос на выборку данных (из одной или нескольких таблиц).

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

Отчет – компонент системы, основное назначение которого – описание и вывод на печать документов на основе информации из БД.

Общая характеристика работы с РБД:

Наиболее распространенная трактовка реляционной модели данных, по-видимому, принадлежит Дейту, который воспроизводит ее (с различными уточнениями) практически во всех своих книгах. Согласно Дейту реляционная модель состоит из трех частей, описывающих разные аспекты реляционного подхода: структурной части, манипуляционной части и целостной части.

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

В манипуляционной части модели утверждаются два фундаментальных механизма манипулирования реляционными БД - реляционная алгебра и реляционное исчисление. Первый механизм базируется в основном на классической теории множеств (с некоторыми уточнениями), а второй - на классическом логическом аппарате исчисления предикатов первого порядка. Заметим, что основной функцией манипуляционной части реляционной модели является обеспечение меры реляционности любого конкретного языка реляционных БД: язык называется реляционным, если он обладает не меньшей выразительностью и мощностью, чем реляционная алгебра или реляционное исчисление.

28. АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ. ТРАНСЛЯТОРЫ (ИНТЕРПРЕТАТОРЫ И КОМПИЛЯТОРЫ). АЛГОРИТМИЧЕСКИЙ ЯЗЫК БЕЙСИК. СТРУКТУРА ПРОГРАММЫ. ИДЕНТИФИКАТОРЫ. ПЕРЕМЕННЫЕ. ОПЕРАТОРЫ. ОБРАБОТКА ОДНОМЕРНЫХ И ДВУХМЕРНЫХ МАССИВОВ. ФУНКЦИИ ПОЛЬЗОВАТЕЛЯ. ПОДПРОГРАММЫ. РАБОТА С ФАЙЛАМИ ДАННЫХ.

Язык высокого уровня - язык программирования, понятия и структура которого удобны для восприятия человеком.

Алгоритмический язык (Algorithmic language) - язык программирования - искусственный (формальный) язык, предназначенный для записи алгоритмов. Язык программирования задается своим описанием и реализуется в виде специальной программы: компилятора или интерпретатора. Примерами алгоритмических языков служат – Borland Pascal, C++, Basic и т.д.

Основные понятия алгоритмического языка:

Состав языка :

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

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

Выражения - это последовательность элементарных конструкций и символов,

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

Описание языка:

Описание символов заключается в перечислении допустимых символов языка. Под описанием элементарных конструкций понимают правила их образования. Описание выражений - это правила образования любых выражений, имеющих смысл в данном языке. Описание операторов состоит из рассмотрения всех типов операторов, допустимых в языке. Описание каждого элемента языка задается его СИНТАКСИСОМ и СЕМАНТИКОЙ.

Синтаксические определения устанавливают правила построения элементов языка.

Семантика определяет смысл и правила использования тех элементов языка, для которых были даны синтаксические определения.

Символы языка - это основные неделимые знаки, в терминах которых пишутся все тексты на языке.

Элементарные конструкции - это минимальные единицы языка, имеющие самостоятельный смысл. Они образуются из основных символов языка.

Выражение в алгоритмическом языке состоит из элементарных конструкций и символов, оно задает правило вычисления некоторого значения.

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

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

Трансляторы - (англ. translator - переводчик) - это программа-переводчик. Она преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд.

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

Существуют два основных способа трансляции - компиляция и интерпретация.

1.Компиляция: Компилятор (англ. compiler - составитель, собиратель) читает всю программу целиком, делает ее перевод и создает законченный вариант программы на машинном языке, который затем и выполняется.

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

2. Интерпретация: Интерпретатор (англ. interpreter - истолкователь, устный переводчик) переводит и выполняет программу строка за строкой.

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

Откомпилированные программы работают быстрее, но интерпретируемые проще исправлять и изменять

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

С другой стороны, Бейсик создавался как язык для начинающих программистов, для которых построчное выполнение программы имеет неоспоримые преимущества.

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

• Перевод

Примечание переводчика: хоть статья довольно старая (опубликована 2 года назад) и носит громкое название, в ней все же дается хорошее представление о различиях реляционных БД и NoSQL БД, их преимуществах и недостатках, а также приводится краткий обзор нереляционных хранилищ.

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

Если это правда, значит ли это, что могучие реляционные БД стали уязвимы? Значит ли это, что дни реляционных БД проходят и скоро совсем пройдут? В этой статье мы рассмотрим популярное течение нереляционных баз данных применительно к различным ситуациям и посмотрим, повлияет ли это на будущее реляционных БД.

Реляционные базы данных существуют уже около 30 лет. За это время вспыхивало несколько революций, которые должны были положить конец реляционным хранилищам. Конечно, ни одна из этих революций не состоялась, и одна из них ни на йоту не поколебала позиции реляционных БД.

Начнем с основ

Реляционная база данных представляет собой набор таблиц (сущностей). Таблицы состоят из колонок и строк (кортежей). Внутри таблиц могут быть определены ограничения, между таблицами существуют отношения. При помощи SQL можно выполнять запросы, которые возвращают наборы данных, получаемых из одной или нескольких таблиц. В рамках одного запроса данные получаются из нескольких таблиц путем их соединения (JOIN), чаще всего для соединения используются те же колонки, которые определяют отношения между таблицами. Нормализация - это процесс структурирования модели данных, обеспечивающий связность и отсутствие избыточности в данных.

Доступ к реляционным базам данных осуществляется через реляционные системы управления базами данных (РСУБД). Почти все системы баз данных, которые мы используем, являются реляционными, такие как Oracle, SQL Server, MySQL, Sybase, DB2, TeraData и так далее.

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

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

Проблемы реляционных БД

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

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

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

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

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

Новая волна

Такой тип баз данных принято называть хранилище типа ключ-значение (key-value store). Фактически, никакого официального названия не существует, поэтому вы можете встретить его в контексте документо-ориентированных, атрибутно-ориентированных, распределенных баз данных (хотя они также могут быть реляционными), шардированных упорядоченных массивов (sharded sorted arrays), распределенных хэш-таблиц и хранилищ типа ключ-значения. И хотя каждое из этих названий указывает на конкретные особенности системы, все они являются вариациями на тему, которую мы будем назвать хранилище типа ключ-значение.

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

Характеристики хранилищ

Реляционная БД	Хранилище типа ключ-значение
База данных состоит из таблиц, таблицы содержат колонки и строки, а строки состоят из значений колонок. Все строки одной таблицы имеют единую структуру.	Для доменов можно провести аналогию с таблицами, однако в отличие от таблиц для доменов не определяется структура данных. Домен – это такая коробка, в которую вы можете складывать все что угодно. Записи внутри одного домена могут иметь разную структуру.
Модель данных 1 определена заранее. Является строго типизированной, содержит ограничения и отношения для обеспечения целостности данных.	Записи идентифицируются по ключу, при этом каждая запись имеет динамический набор атрибутов, связанных с ней.
Модель данных основана на естественном представлении содержащихся данных, а не на функциональности приложения.	В некоторых реализация атрибуты могут быть только строковыми. В других реализациях атрибуты имеют простые типы данных, которые отражают типы, использующиеся в программировании: целые числа, массива строк и списки.
Модель данных подвергается нормализации, чтобы избежать дублирования данных. Нормализация порождает отношения между таблицами. Отношения связывают данные разных таблиц.	Между доменами, также как и внутри одного домена, отношения явно не определены.

Никаких join’ов

Хранилища типа ключ-значение ориентированы на работу с записями. Это значит, что вся информация, относящаяся к данной записи, хранится вместе с ней. Домен (о котором вы можете думать как о таблице) может содержать бессчетное количество различных записей. Например, домен может содержать информацию о клиентах и о заказах. Это означает, что данные, как правило, дублируются между разными доменами. Это приемлемый подход, поскольку дисковое пространство дешево. Главное, что он позволяет все связанные данные хранить в одном месте, что улучшает масштабируемость, поскольку исчезает необходимость соединять данные из различных таблиц. При использовании реляционной БД, потребовалось бы использовать соединения, чтобы сгруппировать в одном месте нужную информацию.

Хотя для хранения пар ключ-значение потребность в отношения резко падает, отношения все же нужны. Такие отношения обычно существуют между основными сущностями. Например, система заказов имела бы записи, которые содержат данные о покупателях, товарах и заказах. При этом неважно, находятся ли эти данные в одном домене или в нескольких. Суть в том, что когда покупатель размещает заказ, вам скорее всего не захочется хранить информацию о покупателе и о заказе в одной записи.
Вместо этого, запись о заказе должна содержать ключи, которые указывают на соответствующие записи о покупателе и товаре. Поскольку в записях можно хранить любую информацию, а отношения не определены в самой модели данных, система управления базой данных не сможет проконтролировать целостность отношений. Это значит, что вы можете удалять покупателей и товары, которые они заказывали. Обеспечение целостности данных целиком ложится на приложение.

Доступ к данным

Реляционная БД	Хранилище типа ключ-значение
Данные создаются, обновляются, удаляются и запрашиваются с использованием языка структурированных запросов (SQL).	Данные создаются, обновляются, удаляются и запрашиваются с использованием вызова API методов.
SQL-запросы могут извлекать данные как из одиночной таблица, так и из нескольких таблиц, используя при этом соединения (join’ы).	Некоторые реализации предоставляют SQL-подобный синтаксис для задания условий фильтрации.
SQL-запросы могут включать агрегации и сложные фильтры.	Зачастую можно использовать только базовые операторы сравнений (=, !=, <, >, <= и =>).
Реляционная БД обычно содержит встроенную логику, такую как триггеры, хранимые процедуры и функции.	Вся бизнес-логика и логика для поддержки целостности данных содержится в коде приложений.

Взаимодействие с приложениями

Хранилища типа ключ-значение: преимущества

Есть два четких преимущества таких систем перед реляционными хранилищами.

Подходят для облачных сервисов

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

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

Более естественная интеграция с кодом

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

Другие аргументы в пользу использования хранилищ типа ключ-значение, наподобие «Реляционные базы могут стать неуклюжими» (кстати, я без понятия, что это значит), являются менее убедительными. Но прежде чем стать сторонником таких хранилищ, ознакомьтесь со следующим разделом.

Хранилища типа ключ-значение: недостатки

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

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

И не забудьте о совместимости. В отличие от реляционных БД, хранилища, ориентированные на использование в «облаке», имеют гораздо меньше общих стандартов. Хоть концептуально они и не отличаются, они все имеют разные API, интерфейсы запросов и свою специфику. Поэтому вам лучше доверять вашему вендору, потому что в случае чего, вы не сможете легко переключиться на другого поставщика услуг. А учитывая тот факт, что почти все современные хранилища типа ключ-значение находятся в стадии бета-версий 2 , доверять становится еще рискованнее, чем в случае использования реляционных БД.

Ограниченная аналитика данных

Обычно все облачные хранилища строятся по типу множественной аренды , что означает, что одну и ту же систему использует большое количество пользователей и приложений. Чтобы предотвратить «захват» общей системы, вендоры обычно каким-то образом ограничивают выполнение запросов. Например, в SimpleDB запрос не может выполняться дольше 5 секунд. В Google AppEngine Datastore за один запрос нельзя получить больше, чем 1000 записей 3 .

Эти ограничения не страшны для простой логики (создание, обновление, удаление и извлечение небольшого количества записей). Но что если ваше приложение становится популярным? Вы получили много новых пользователей и много новых данных, и теперь хотите сделать новые возможности для пользователей или каким-то образом извлечь выгоду из данных. Тут вы можете жестко обломаться с выполнением даже простых запросов для анализа данных. Фичи наподобие отслеживания шаблонов использования приложения или системы рекомендаций, основанной на истории пользователя, в лучшем случае могут оказаться сложны в реализации. А в худшем - просто невозможны.

В таком случае для аналитики лучше сделать отдельную базу данных, которая будет заполняться данными из вашего хранилища типа ключ-значение. Продумайте заранее, каким образом это можно будет сделать. Будете ли вы размещать сервер в облаке или у себя? Не будет ли проблем из-за задержек сигнала между вами и вашим провайдером? Поддерживает ли ваше хранилище такой перенос данных? Если у вас 100 миллионов записей, а за один раз вы можете взять 1000 записей, сколько потребуется на перенос всех данных?

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

Облачные хранилища

Множество поставщиков веб-сервисов предлагают многопользовательские хранилища типа ключ-значение. Большинство из них удовлетворяют критериям, перечисленным выше, однако каждое обладает своими отличительными фичами и отличается от стандартов, описанных выше. Давайте взглянем на конкретные пример хранилищ, такие как SimpleDB, Google AppEngine Datastore и SQL Data Services.

Amazon: SimpleDB

SimpleDB - это атрибутно-ориентированное хранилище типа ключ-значение, входящее в состав Amazon WebServices. SimpleDB находится в стадии бета-версии; пользователи могут пользовать ей бесплатно - до тех пор пока их потребности не превысят определенный предел.

У SimpleDB есть несколько ограничений. Первое - время выполнения запроса ограничено 5-ю секундами. Второе - нет никаких типов данных, кроме строк. Все хранится, извлекается и сравнивается как строка, поэтому для того, чтобы сравнить даты, вам нужно будет преобразовать их в формат ISO8601. Третье - максимальные размер любой строки составляет 1024 байта, что ограничивает размер текста (например, описание товара), который вы можете хранить в качестве атрибута. Однако поскольку структура данных гибкая, вы можете обойти это ограничения, добавляя атрибуты «ОписаниеТовара1», «Описание товара2» и т.д. Но количество атрибутов также ограничено - максимум 256 атрибутов. Пока SimpleDB находится в стадии бета-версии, размер домена ограничен 10-ю гигабайтами, а вся база не может занимать больше 1-го терабайта.

Одной из ключевых особенностей SimpleDB является использование модели конечной констистенции (eventual consistency model). Эта модель подходит для многопоточной работы, однако следует иметь в виду, что после того, как вы изменили значение атрибута в какой-то записи, при последующих операциях чтения эти изменения могут быть не видны. Вероятность такого развития событий достаточно низкая, тем не менее, о ней нужно помнить. Вы же не хотите продать последний билет пяти покупателям только потому, что ваши данные были неконсистентны в момент продажи.

Google AppEngine Data Store

Google"s AppEngine Datastore построен на основе BigTable, внутренней системе хранения структурированных данных от Google. AppEngine Datastore не предоставляет прямой доступ к BigTable, но может восприниматься как упрощенный интерфейс взаимодействия с BigTable.

AppEngine Datastore поддерживает большее число типов данных внутри одной записи, нежели SimpleDB. Например, списки, которые могут содержать коллекции внутри записи.

Скорее всего вы будете использовать именно это хранилище данных при разработке с помощью Google AppEngine. Однако в отличии от SimpleDB, вы не сможете использовать AppEngine Datastore (или BigTable) вне веб-сервисов Google.

Microsoft: SQL Data Services

SQL Data Services является частью платформы Microsoft Azure . SQL Data Services является бесплатной, находится в стадии бета-версии и имеет ограничения на размер базы. SQL Data Services представляет собой отдельное приложение - надстройку над множеством SQL серверов, которые и хранят данные. Эти хранилища могут быть реляционными, однако для вас SDS является хранилищем типа ключ-значение, как и описанные выше продукты.

Необлачные хранилища

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

CouchDB

CouchDB - это свободно распространяемая документо-ориентированная БД с открытым исходным кодом. В качестве формата хранения данных используется JSON. CouchDB призвана заполнить пробел между документо-ориентированными и реляционными базами данных с помощью «представлений». Такие представления содержат данные из документов в виде, схожим с табличным, и позволяют строить индексы и выполнять запросы.

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

Проект Voldemort

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

Mongo

Mongo - это база данных, разрабатываемая в 10gen Гейром Магнуссоном и Дуайтом Меррименом (которого вы можете знать по DoubleClick). Как и CouchDB, Mongo - это документо-ориентированная база данных, хранящая данные в JSON формате. Однако Mongo скорее является объектной базой, нежели чистым хранилищем типа ключ-значение.

Drizzle

Drizzle представляет совсем другой подход к решению проблем, с которыми призваны бороться хранилища типа ключ-значение. Drizzle начинался как одна из веток MySQL 6.0. Позже разработчики удалили ряд функций (включая представления, триггеры, скомпилированные выражения, хранимые процедуры, кэш запросов, ACL, и часть типов данных), с целью создания более простой и быстрой СУБД. Тем не менее, Drizzle все еще можно использовать для хранения реляционных данных. Цель разработчиков - построить полуреляционную платформу, предназначенную для веб-приложений и облачных приложений, работающих на системах с 16-ю и более ядрами.

Решение

В конечном счете, есть четыре причины, по которым вы можете выбрать нереляционное хранилище типа ключ-значение для своего приложения:

1. Ваши данные сильно документо-ориентированны, и больше подходят для модели данных ключ-значение, чем для реляционной модели.
2. Ваша доменная модель сильно объектно-ориентированна, поэтому использования хранилища типа ключ-значение уменьшит размер дополнительного кода для преобразования данных.
3. Хранилище данных дешево и легко интегрируется с веб-сервисами вашего вендора.
4. Ваша главная проблема - высокая масштабируемость по запросу.

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

Для всех остальных требований лучше выбрать старые добрые реляционные СУБД. Так обречены ли они? Конечно, нет. По крайней мере, пока.

1 - по моему мнению, здесь больше подходит термин «структура данных», однако оставил оригинальное data model.
2 - скорее всего, автор имел в виду, что по своим возможностям нереляционные БД уступают реляционным.
3 - возможно, данные уже устарели, статья датируется февралем 2009 года.

Добавить метки

Реляционная модель

Реляционная модель базы данных была предложена в 1969 г. математиком и научным сотрудником фирмы IBM Э.Ф. Коддом (E.F. Codd). Некоторые начальные сведения о реляционных базах данных содержатся в обзорной статье “БД и СУБД ” 2. Поскольку в настоящее время именно реляционные базы данных являются доминирующими, в этой статье (а также в статьях “Описание данных ”, “Обработка данных ” и “Проектирование БД ” 2) подробно рассматриваются наиболее существенные понятия реляционной модели.

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

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

Нередко слово “реляционная” (relational ) в термине “реляционная модель” трактуют, основываясь на том, что в реляционной базе данных устанавливаются связи (relate ) между таблицами. Такое объяснение удобно, но оно не является точным. В оригинальной системе терминов Кодда термины связи (relations ), атрибуты (attributes ) и кортежи (tuples ) употреблялись там, где большинство из нас пользуется более привычными терминами таблицы, столбцы (поля) и строки (записи).

При построении инфологической модели предметной области (см. “БД и СУБД ”, “Проектирование БД ” 2) выделяются сущности (объекты), описываются их свойств а (характеристики, атрибуты), существенные для целей моделирования, и устанавливаются связи между сущностями. На этапе перехода от инфологической к даталогической реляционной модели как раз и появляются таблицы. Как правило, каждая сущность представляется одной таблицей. Каждая строка таблицы (одна запись) соответствует одному экземпляру сущности, а каждое поле описывает некоторое свойство (атрибут) .

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

Таблица “Человек”

Реляционная модель требует, чтобы каждая строка таблицы была уникальной, т.е. чтобы любые две строки различались значением хотя бы одного атрибута.

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

Ключи

Ключом таблицы называется поле или группа полей, содержащие уникальные в рамках данной таблицы значения . Ключ однозначно определяет соответствующую строку таблицы. Если ключ состоит из одного поля, его часто называют простым , если из нескольких - составным . В приведенном выше примере ключом является поле ИНН (мы считаем известным тот факт, что ИНН в пределах страны являются уникальными).

Рассмотрим пример таблицы с составным ключом. На сайтах прогнозов погоды нередко представляют информацию следующим образом: для каждой даты указывают прогнозируемую температуру ночью, утром, днем и вечером. Для хранения указанной информации можно использовать таблицу следующего вида:

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

Нередко встречается ситуация, в которой выбор ключа не является однозначным. Вернемся к первому примеру. Допустим, в дополнение к фамилии, имени, отчеству, ИНН, дате рождения требуется хранить серию и номер общегражданского паспорта и серию и номер заграничного паспорта. Таблица будет иметь следующий вид.

В этой таблице можно выбрать целых три ключа. Один из них - простой (ИНН), два другие - составные (Серия+Номер общегражданского паспорта и Серия+Номер заграничного паспорта). В такой ситуации разработчик выбирает наиболее удобный с точки зрения организации БД ключ (в общем случае - ключ, на поиск значения которого требуется наименьшее время). Выбранный ключ в этом случае часто называют главным, или первичным , ключом, а другие комбинации столбцов, из которых можно сделать ключ, - возможными , или альтернативными, ключами. Отметим, что хотя бы один возможный ключ в таблице имеется всегда, так как строки не могут повторяться и, следовательно, комбинация всех столбцов гарантированно является возможным ключом.

При изображении таблиц первичные ключи таблиц принято выделять. Например, соответствующие поля часто подчеркивают. А Microsoft Access выделяет ключевые поля полужирным шрифтом.

Еще чаще, чем с неоднозначностью выбора ключа, разработчики сталкиваются с отсутствием ключа среди данных, которые требуется хранить. Подобный факт может быть установлен в процессе анализа предметной области. Например, если требуется хранить простой список людей - имена, фамилии, отчества и даты рождения, то ключа в этом наборе атрибутов нет вовсе - мыслимой является ситуация, когда у двух различных людей указанные данные совпадают полностью. В таком случае приходится искусственно вводить дополнительное поле, например, уникальный номер человека. Такой ключ в литературе иногда называют суррогатным . Нередко суррогатный ключ вводят и из соображений эффективности. Если, например, в таблице имеется длинный составной ключ, то разработчики часто вводят дополнительный короткий числовой суррогатный ключ и именно его делают первичным. Нередко так поступают даже при наличии простого ключа, имеющего “неудобный” (неэффективный для поиска) тип данных, например, строковый. Подобные операции уже не имеют отношения к теории, но сплошь и рядом встречаются на практике.

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

Нормальные формы, нормализация

Не всякая таблица, которую мы можем нарисовать на бумаге или в Word’е, может быть таблицей реляционной базы данных. И не всякая таблица, которая может использоваться в реляционной базе данных, является правильной с точки зрения требования реляционной модели.

Во-первых, требуется, чтобы все данные в пределах одного столбца имели один и тот же тип (о типах см. “Описание данных ” 2). С этой точки зрения приведенный ниже пример не имеет смысла даже обсуждать:

Во-вторых, требуется, чтобы в таблице был назначен первичный ключ .

Указанные требования являются необходимыми, но недостаточными. В теории реляционных баз данных вводятся понятия так называемых “нормальных форм” - требований к организации данных в таблицах. Нормальные формы нумеруются последовательно, по мере ужесточения требований. В правильно спроектированной БД таблицы находятся как минимум в третьей нормальной форме. Соответственно, мы рассмотрим первые три нормальные формы. Напомним, что мы имеем дело с таблицами, удовлетворяющими двум сформулированным выше основным требованиям.

Первая нормальная форма (1НФ)

Первая нормальная форма предписывает, что все данные, содержащиеся в таблице, должны быть атомарными (неделимыми ). Перечень соответствующих атомарных типов данных определяется СУБД. Требование 1НФ совершенно естественное. Оно означает, что в каждом поле каждой записи должна находиться только одна величина, но не массив и не какая-либо другая структура данных. Приведем осмысленный пример таблицы, которая не находится в 1НФ. Пусть у нас имеются списки оценок учеников по некоторому предмету.

Так как значение поля Оценки не является атомарным, таблица не соответствует требованиям 1НФ.

О возможном способе представления списка оценок написано в методических рекомендациях к статье “Проектирование БД” 2.

Вторая нормальная форма (2НФ)

Говорят, что таблица находится во второй нормальной форме, если она находится в 1НФ и каждый не ключевой столбец полностью зависит от первичного ключа. Другими словами, значение каждого поля должно полностью определяться значением первичного ключа. Важно отметить, что зависимость от первичного ключа понимается именно как зависимость от ключа целиком, а не от отдельной его составляющей (в случае составного ключа). Приведем пример таблицы, которая не находится во 2НФ. Для этого вернемся к примеру прогноза погоды и дополним таблицу еще одним столбцом - временем восхода солнца (это вполне правдоподобный пример, такого рода информация часто приводится на сайтах прогноза погоды).

Как мы помним, данная таблица имеет составной ключ Дата+Время суток. Поле Температура полностью зависит от первичного ключа - с ним проблем нет. А вот поле Восход зависит лишь от поля Дата, Время суток на время восхода естественным образом не влияет.

Здесь уместно задаться вопросом: а в чем практический смысл 2НФ? Какая польза от этих ограничений? Оказывается - большая. Допустим, что в приведенном выше примере разработчик проигнорирует требования 2НФ. Во-первых, скорее всего возникнет так называемая избыточность - хранение лишних данных. Ведь если для одной записи с данной датой уже хранится время восхода, то для всех других записей с данной датой оно должно быть таким же и хранить его, вообще говоря, незачем.

Обратим внимание на слова “должно быть”. А если не будет? Ведь на уровне БД это никак не контролируется - ключ в таблице составной, одинаковые даты могут быть (и по смыслу скорее всего будут). И никакие формальные ограничения (а наше понимание, что “такого не может быть”, к таковым не относится) не запрещают указать разное время восхода для одной и той же даты.

Третья нормальная форма (3НФ)

Говорят, что таблица находится в 3НФ, если она соответствует 2НФ и все не ключевые столбцы взаимно независимы.

Взаимную зависимость столбцов удобно понимать следующим образом: столбцы являются взаимно зависимыми, если нельзя изменить один из них, не изменяя другой.

Приведем пример таблицы, которая не находится в 3НФ. Рассмотрим пример простой записной книжки для хранения домашних телефонов людей, проживающих, возможно, в различных регионах страны.

В этой таблице присутствует зависимость между не ключевыми столбцами Город и Код города, следовательно, таблица не находится в 3НФ.

Отметим, что наличие указанной выше зависимости разработчик определяет, анализируя предметную область, - никакими формальными методами подобную коллизию увидеть нельзя. При изменении свойств предметной области зависимость между столбцами может и исчезнуть. Например, если в пределах одного города вводятся различные коды (как 495 и 499 в Москве), соответствующие столбцы перестают быть связанными с точки зрения нарушения требований 3НФ.

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

Нормализация БД

Нормализация представляет собой процесс приведения таблиц базы данных к выбранной нормальной форме. Нормализация до 2НФ, как правило, сводится к декомпозиции - разбиению одной таблицы на несколько. Нормализация до 3НФ обычно может быть выполнена удалением зависимых (вычисляемых) столбцов. В некоторых случаях при нормализации до 3НФ приходится также производить декомпозицию.

Многотабличные БД, связи между таблицами, внешние ключи

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

Не ставя целью полное проектирование БД, рассмотрим пример, позволяющий продемонстрировать связи в многотабличных БД.

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

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

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

В результате мы получим следующий набор таблиц, соответствующих описываемым сущностям.

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

Чтобы отнести ученика к некоторому классу, заведем в таблице “Ученик” дополнительное поле Номер класса. (Понятно, что его тип должен полностью совпадать с типом поля Номер класса в таблице “Класс”.) Теперь мы можем связать таблицы “Ученик” и “Класс” по совпадающим значениям полей Номер класса (мы не случайно назвали эти поля одинаково, на практике так часто поступают, чтобы легко ориентироваться в связывающих полях). Заметим, что одной записи в таблице “Класс” может соответствовать много записей в таблице “Ученик” (и на практике скорее всего соответствует - трудно представить себе класс из одного ученика). О таких таблицах говорят, что они связаны отношением “один ко многим ”. А поле Номер класса в таблице “Ученик” называют внешним ключом . Как видим, назначение внешних ключей - связывание таблиц. Отметим, что внешний ключ всегда ссылается на первичный ключ связанной таблицы (т.е. внешний ключ находится на стороне “многих”). Связанный с внешним первичный ключ называют родительским , хотя этот термин используется реже.

Проиллюстрируем сказанное схемой в стиле Microsoft Access (подробнее о “Схеме данных” Access написано в статье “Описание данных” 2).

Теперь вспомним об учителях и предметах. Анализируя предметную область (только так - ведь истинное положение вещей из самой формальной модели извлечь невозможно), мы замечаем, что тип связи между сущностями “учитель” и “предмет” иной, нежели рассмотренный выше. Ведь не только один предмет могут вести много учителей, но и один учитель может вести много предметов. Таким образом, между этими сущностями имеется связь “многие ко многим ”. Тут уже не обойтись введением дополнительных полей (попробуйте!). Связи “многие ко многим” всегда разрешаются посредством введения дополнительной таблицы. А именно, организуем таблицу “Учитель-Предмет”, имеющую следующую структуру:

Таблица “Учитель-Предмет”

Эта таблица имеет составной ключ, образованный из двух ее полей. И таблица “Учитель”, и таблица “Предмет” связаны с данной таблицей отношением “один ко многим” (разумеется, в обоих случаях “многие” находятся на стороне “Учитель-Предмет”). Соответственно, в таблице “Учитель-Предмет” имеются два внешних ключа (оба - части составного первичного ключа, что не воспрещается), служащие для связи с соответствующими таблицами.

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

Допустим, мы храним очень много разнообразной информации о людях - данные их всевозможных документов, телефоны, адреса и пр. Скорее всего боRльшая часть этих данных будет использоваться очень редко. А часто нам потребуются лишь фамилия, имя, отчество и телефон. Тогда имеет смысл организовать две таблицы и связать их отношением “один к одному”. В одной (небольшой) таблице хранить часто используемую информацию, в другой - остальную. Естественно, что таблицы, связанные отношением “один к одному”, имеют один и тот же первичный ключ.

Правила целостности

Реляционная модель определяет два общих правила целостности базы данных: целостность объектов и ссылочная целостность.

Правило целостности объектов очень простое. Оно требует, чтобы первичные ключи таблиц не содержали неопределенных (пустых) значений .

Правило ссылочной целостности требует, чтобы внешние ключи не содержали несогласованных с родительскими ключами значений . Возвращаясь к рассмотренному выше примеру, мы должны потребовать, например, чтобы ученики относились лишь к классу, номер которого указан в таблице “Классы”.

Большинство СУБД умеют следить за целостностью данных (разумеется, это требует соответствующих усилий и от разработчика на этапе описания структур данных). В частности, для поддержания ссылочной целостности используются механизмы каскадирования операций. Каскадирование подразумевает, в частности, то, что при удалении записи из “родительской” таблицы, связанной с другой таблицей отношением “один ко многим”, из таблицы “многих” автоматически (самой СУБД, без участия пользователя) удаляются все связанные записи. И это естественно, ведь такие записи “повисают в воздухе”, они более ни с чем не связаны.

Индексация

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

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

Разумеется, и речи не идет о том, чтобы излагать теорию реляционных баз данных в рамках базового курса информатики! Тем не менее эта статья очень важна для нашей энциклопедии, поскольку в данном случае мы имеем дело с материалом, который не может быть в полном объеме изложен на уроках, но учитель владеть им должен. Почему?

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

Во-вторых, выполняя с детьми простые запросы к базам данных (соответствующий материал изложен в статье “Обработка данных” 2), необходимо иметь дело с правильными с точки зрения реляционной теории таблицами. Не требуется объяснять ученикам, что эти таблицы правильные, а “вот если бы…, то таблица была бы неправильной”, но недопустимо использовать плохие примеры.

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

Моделируемые предметные области должны быть не слишком большими;

Они должны быть очень хорошо знакомы учащимся (в этом смысле изрядно поднадоевший всем проект “Школа” - не худший выбор!);

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

Все современные БД используют CBO (Cost Based Optimization), стоимостную оптимизацию. Суть её заключается в том, что для каждой операции определяется её «стоимость», а затем общая стоимость запроса уменьшается с помощью использования наиболее «дешёвых» цепочек операций.

Для лучшего понимания стоимостной оптимизации мы рассмотрим три распространённых способа объединения двух таблиц и увидим, как даже простой запрос на объединение может превратиться в кошмар для оптимизатора. В нашем рассмотрении мы будем ориентироваться на временнỳю сложность, хотя оптимизатор вычисляет «стоимость» в ресурсах процессора, памяти и операциях ввода/вывода. Просто временнáя сложность - понятие приблизительное, а для определения необходимых ресурсов процессора нужно подсчитывать все операции, включая добавление, операторы if, умножение, итерации и т.д.

Кроме того:

• Для выполнения каждой высокоуровневой операции процессор выполняет разное количество низкоуровневых операций.
• Стоимость процессорных операций (с точки зрения циклов) разная у разных видов процессоров, то есть она зависит от конкретной архитектуры ЦПУ.

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

Мы говорили о них, когда рассматривали В-деревья. Как вы помните, индексы уже отсортированы. К слову, есть и другие виды индексов, например, битовые (bitmap index). Но они не дают выигрыша с точки зрения использования процессора, памяти и дисковой подсистемы по сравнению с индексами В-деревьев. Кроме того, многие современные БД могут динамически создавать временные индексы для текущих запросов, если это поможет уменьшить стоимость выполнения плана.

4.4.2. Способы обращений

Прежде чем применять операторы объединения, нужно сначала получить необходимые данные. Сделать это можно следующими способами.

• Полное сканирование. БД просто считывает целиком таблицу или индекс. Как вы понимаете, для дисковой подсистемы индекс читать дешевле, чем таблицу.
• Сканирование диапазона. Используется, например, когда вы используете предикаты наподобие WHERE AGE > 20 AND AGE < 40. Конечно, для сканирования диапазона индекса вам нужно иметь индекс для поля AGE.

  В первой части статьи мы уже выяснили, что временнáя сложность запроса диапазона определяется как M + log(N), где N - количество данных в индексе, а М - предположительное количество строк внутри диапазона. Значения обеих этих переменных нам известны благодаря статистике. При сканировании диапазона считывается лишь часть индекса, поэтому данная операция стоит меньше по сравнению с полным сканированием.

• Сканирование по уникальным значениям. Используется в тех случаях, когда вам нужно получить из индекса только какое-то одно значение.
• Обращение по ID строки. Если БД использует индекс, то бόльшую часть времени она будет заниматься поиском связанных с ним строк. Например, мы делаем такой запрос:

  SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28
  Если у нас есть индекс для колонки возраста, то оптимизатор воспользуется индексом для поиска всех 28-летних, а затем запросит ID соответствующих строк таблицы, поскольку индекс содержит информацию только о возрасте.

  Допустим, у нас другой запрос:

  SELECT TYPE_PERSON.CATEGORY from PERSON, TYPE_PERSON WHERE PERSON.AGE = TYPE_PERSON.AGE
  Для объединения с TYPE_PERSON будет использоваться индекс по колонке PERSON. Но поскольку мы не запрашивали информацию у таблицы PERSON, то и обращаться к ней по ID строк никто не будет.

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

• Другие способы . О них можно почитать в документации Oracle . В разных БД могут использоваться разные названия, но принципы везде одни и те же.

4.4.3. Операции объединения

Итак, мы знаем, как получить данные, пришла пора их объединить. Но сначала давайте определимся с новыми терминами: внутренние зависимости и внешние зависимости . Зависимостью может быть:

• таблица,
• индекс,
• промежуточный результат предыдущей операции (например, предыдущего объединения).

Когда мы объединяем две зависимости, алгоритмы объединения управляют ими по-разному. Допустим, A JOIN B является объединением А и В, где А является внешней зависимостью, а В - внутренней.

Чаще всего стоимость A JOIN B не равна стоимости B JOIN A.

Предположим, что внешняя зависимость содержит N элементов, а внутренняя - М. Как вы помните, оптимизатору известны эти значения благодаря статистике. N и M являются кардинальными числами зависимостей .

• Объединение с помощью вложенных циклов. Это простейший способ объединения.

  

  Работает он так: для каждой строки внешней зависимости ищутся совпадения по всем строкам внутренней зависимости.

  Пример псеводокода:

  Nested_loop_join(array outer, array inner) for each row a in outer for each row b in inner if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for
  Поскольку здесь двойная итерация, временнáя сложность определяется как О(N*M).

  Для каждой из N строк внешней зависимости нужно считать М строк внешней зависимости. То есть этот алгоритм требует N + N*M чтений с диска. Если внутренняя зависимость достаточно мала, то можно поместить её целиком в память, и тогда на долю дисковой подсистемы придётся только M + N чтений. Так что рекомендуется делать внутреннюю зависимость как можно компактнее, чтобы загнать в память.

  С точки зрения временнόй сложности разницы никакой.

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

  • Вместо чтения обеих зависимостей построчно, они считываются группами строк (bunch), при этом в памяти сохраняется по одной группе из каждой зависимости.
  • Строки из этих групп сравниваются между собой, а найденные совпадения сохраняются отдельно.
  • Затем в память подгружаются новые группы и тоже сравниваются друг с другом.
  И так далее, пока группы не закончатся.

  Пример алгоритма:

  // improved version to reduce the disk I/O. nested_loop_join_v2(file outer, file inner) for each bunch ba in outer // ba is now in memory for each bunch bb in inner // bb is now in memory for each row a in ba for each row b in bb if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for end for end for
  В данном случае временнáя сложность остаётся той же, зато снижается количество обращений к диску: (количество групп внешней + количество групп внешней * количество групп внутренней). С увеличением размера групп ещё больше уменьшается количество обращений к диску.

  Примечание: в этом алгоритме при каждом обращении считывается больший объём данных, но это не играет роли, поскольку обращения последовательные.

• Хэш-объединение. Это более сложная операция, но во многих случаях её стоимость ниже.

  

  Алгоритм следующий:

  1. Считываются все элементы из внутренней зависимости.
  2. В памяти создаётся хэш-таблица.
  3. Один за другим считываются все элементы из внешней зависимости.
  4. Для каждого элемента вычисляется хэш (с помощью соответствующей функции из хэш-таблицы), чтобы можно было найти соответствующий блок во внутренней зависимости.
  5. Элементы из блока сравниваются с элементами из внешней зависимости.
  Чтобы оценить этот алгоритм с точки зрения временнόй сложности, нужно сделать несколько допущений:
  • Внутренняя зависимость содержит Х блоков.
  • Хэш-функция распределяет хэши почти одинаково для обеих зависимостей. То есть все блоки имеют идентичный размер.
  • Стоимость поиска соответствия между элементами внешней зависимости и всеми элементами внутри блока равна количеству элементов внутри блока.
  Тогда временнáя сложность будет равна:

  (М / Х) * (N / X) + стоимость_создания_хэш-таблицы(М) + стоимость_хэш-функции * N

  А если хэш-функция создаёт достаточное маленькие блоки, то временнáя сложность будет равна О(М + N).

  Есть ещё один способ хэш-объединения, более экономно расходующий память и не требующий больше операций ввода/вывода:

  1. Вычисляются хэш-таблицы для обеих зависимостей.
  2. Кладутся на диск.
  3. А затем сравниваются поведёрно друг с другом (один блок загружается в память, а второй считывается построчно).
  Объединение слиянием. Это единственный способ объединения, в результате которого данные получаются отсортированными. В рамках этой статьи мы рассматриваем упрощённый случай, когда зависимости не делятся на внешнюю и внутреннюю, поскольку ведут себя одинаково. Однако в жизни они могут различаться, скажем, при работе с дубликатами.

  Операцию объединения можно разделить на два этапа:

  1. (Опционально) сначала осуществляется объединение сортировкой, когда оба набора входных данных сортируются по ключам объединения.
  2. Затем осуществляется слияние.
  Сортировка

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

  Но бывает, что наборы данных поступают уже отсортированными, например:

  • Если таблица организована нативно.
  • Если зависимость является индексом при наличии условия объединения.
  • Если объединение происходит с промежуточным отсортированным результатом.
  Объединение слиянием

  

  Эта операция очень похожа на операцию слияния при процедуре сортировки слиянием. Но вместо выбора всех элементов обеих зависимостей мы выбираем только равные элементы.

  1. Сравниваются два текущих элемента обеих зависимостей.
  2. Если они равны, то заносятся в результирующую таблицу, и далее сравниваются два следующих элемента, по одному из каждой зависимости.
  3. Если они не равны, то сравнение повторяется, но вместо наименьшего из двух элементов берётся следующий элемент из той же зависимости, поскольку вероятность совпадения в этом случае выше.
  4. Шаги 1-3 повторяются, пока на закончатся элементы одной из зависимостей.
  Если обе зависимости уже отсортированы, то временнáя сложность равна О(N + M).

  Если обе зависимости ещё нужно отсортировать, то временнáя сложность равна O(N * Log(N) + M * Log(M)).

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

  MergeJoin(relation a, relation b) relation output integer a_key:=0; integer b_key:=0; while (a!=null and b!=null) if (a < b) a_key++; else if (a > b) b_key++; else //Join predicate satisfied write_result_in_output(a,b) //We need to be careful when we increase the pointers integer a_key_temp:=a_key; integer b_key_temp:=b_key; if (a != b) b_key_temp:= b_key + 1; end if if (b != a) a_key_temp:= a_key + 1; end if if (b == a && b == a) a_key_temp:= a_key + 1; b_key_temp:= b_key + 1; end if a_key:= a_key_temp; b_key:= b_key_temp; end if end while

Какой алгоритм выбрать?

Если бы существовал самый лучший способ объединения, то не существовало бы всех этих разновидностей. Так что ответ на этот вопрос зависит от кучи факторов:

• Объём доступной памяти . Если её мало, забудьте о мощном хэш-объединении. По крайне мере, о его выполнении целиком в памяти.
• Размер двух наборов входных данных. Если у вас одна таблица большая, а вторая очень маленькая, то быстрее всего сработает объединение с помощью вложенных циклов, потому что хэш-объединение подразумевает дорогую процедуру создания хэшей. Если у вас две очень большие таблицы, то объединение с помощью вложенных циклов поглотит все ресурсы процессора.
• Наличие индексов. Если у вас два индекса В-деревьев, то лучше использовать объединение слиянием.
• Нужно ли сортировать результат. Возможно, вы захотите использовать дорогое объединение слиянием (с сортировкой), если работаете с несортированными наборами данных. Тогда на выходе вы получите сортированные данные, которые удобнее объединить с результатами другого объединения. Или потому что запрос косвенно или явно предполагает получение данных, отсортированных операторами ORDER BY/GROUP BY/DISTINCT.
• Отсортированы ли выходные зависимости . В данном случае лучше использовать объединение слиянием.
• Зависимости каких типов вы используете . Объединение по эквивалентности (таблицаА.колонка1 = таблицаБ.колонка2)? Внутренние зависимости, внешние, декартово произведение или самообъединение (self-join)? В разных ситуациях некоторые способы объединения не работают.
• Распределение данных . Если данные отклонены по условию объединения (например, вы объединяете людей по фамилиям, но часто встречаются однофамильцы), то ни в коем случае нельзя использовать хэш-объединение. Иначе хэш-функция будет создавать корзины с очень плохим внутренним распределением.
• Нужно ли выполнять объединение в несколько процессов/потоков.

Алчущие знаний могут углубиться в документацию по DB2 , ORACLE и SQL Server .

4.4.4. Упрощённые примеры

Допустим, нам нужно объединить пять таблиц, чтобы получить полное представление о неких людях. Каждый человек может иметь:

• Несколько номеров мобильных телефонов.
• Несколько адресов электронной почты.
• Несколько физических адресов.
• Несколько номеров банковских счетов.

То есть нужно быстро дать ответ на этот запрос:

SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS WHERE PERSON.PERSON_ID = MOBILES.PERSON_ID AND PERSON.PERSON_ID = MAILS.PERSON_ID AND PERSON.PERSON_ID = ADRESSES.PERSON_ID AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
Оптимизатору нужно найти наилучший способ обработки данных. Но есть две проблемы:

1. Какой способ объединения использовать? Есть три варианта (хэш-объединение, объединение слиянием, объединение с помощью вложенных циклов), с возможностью использования 0, 1 или 2 индексов. Не говоря уже о том, что индексы тоже могут быть разными.
2. В каком порядке нужно производить объединение?

Например, ниже представлены возможные планы для трёх объединений четырёх таблиц:

Исходя из описанного, какие есть варианты действий?

1. Использовать брутфорс-подход. С помощью статистики подсчитать стоимость каждого из возможных планов исполнения запроса и выбрать самый дешёвый. Но вариантов довольно много. Для каждого порядка объединения можно использовать три разных способа объединения, итого 34=81 возможных планов исполнения. В случае с бинарным деревом задача выбора порядка объединения превращается в задачу о перестановках, и количество вариантов равно (2 * 4)! / (4 + 1)!.. В результате, в данном очень упрощённом примере общее количество возможных планов исполнения запроса составляет 34 * (2 * 4)! / (4 + 1)! = 27 216. Если добавить к этому варианты, когда при объединении слиянием используется 0, 1 или 2 индекса В-дерева, то количество возможных планов повышается до 210 000. Мы уже упоминали, что это ОЧЕНЬ ПРОСТОЙ запрос?
2. Поплакать и уволиться. Очень соблазнительно, но непродуктивно, да и деньги нужны.
3. Попробовать несколько планов и выбрать самый дешёвый. Раз обсчитать стоимость всех возможных вариантов не получается, можно взять произвольный тестовый набор данных и прогнать по нему все виды планов, чтобы оценить их стоимость и выбрать лучший.
4. Применить «умные» правила для уменьшения количества возможных планов.
   Есть два типа правил:
   1. «Логические», с помощью которых можно исключить бесполезные варианты. Но они далеко не всегда применимы. Например, «при объединении с помощью вложенных циклов внутренняя зависимость должна являться наименьшим набором данных».
   2. Можно не искать наиболее выгодное решение и применить более жёсткие правила для уменьшения числа возможных планов. Скажем, «если зависимость мала, используем объединение с помощью вложенных циклов, но никогда - объединение слиянием или хэш-объединение».

Даже столь простой пример ставит нас перед огромным выбором. А в реальных запросах могут присутствовать и другие операторы отношения: OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT и т.д. То есть количество возможных планов исполнения будет ещё больше.

Так как же БД делает выбор?

4.4.5. Динамическое программирование, «жадный» алгоритм и эвристика

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

Брутфорс может подойти в случае с маленькими запросами. А благодаря способам исключения ненужных вычислений даже для запросов среднего размера можно использовать грубую мужскую силу. Это называется динамическим программированием.

Его суть заключается в том, что многие планы исполнения очень похожи.

На этой иллюстрации все четыре плана используют поддерево A JOIN B. Вместо вычисления его стоимости для каждого плана, мы можем посчитать его лишь раз и затем использовать эти данные столько, сколько нужно. Иными словами, с помощью мемоизации мы решаем проблему перекрытия, то есть избегаем лишних вычислений.

Благодаря такому подходу вместо временнόй сложности (2*N)!/(N+1)! мы получаем «всего лишь» 3 N . Применительно к предыдущему примеру с четырьмя объединениями это означает уменьшение количества вариантов с 336 до 81. Если взять запрос с 8 объединениями (небольшой запрос), то уменьшение сложности будет с 57 657 600 до 6 561.

Если вы уже знакомы с динамическим программированием или алгоритмизацией, можете поиграться с этим алгоритмом:

Procedure findbestplan(S) if (bestplan[S].cost infinite) return bestplan[S] // else bestplan[S] has not been computed earlier, compute it now if (S contains only 1 relation) set bestplan[S].plan and bestplan[S].cost based on the best way of accessing S /* Using selections on S and indices on S */ else for each non-empty subset S1 of S such that S1 != S P1= findbestplan(S1) P2= findbestplan(S - S1) A = best algorithm for joining results of P1 and P2 cost = P1.cost + P2.cost + cost of A if cost < bestplan[S].cost bestplan[S].cost = cost bestplan[S].plan = “execute P1.plan; execute P2.plan; join results of P1 and P2 using A” return bestplan[S]
Динамическое программирование можно использовать и для более крупных запросов, но придётся вводить дополнительные правила (эвристику), чтобы уменьшить число возможных планов:


Жадные алгоритмы

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

В данном случае план исполнения запроса строится пошагово с помощью некоего правила (эвристики). Благодаря ему жадный алгоритм ищет наилучшее решение для каждого этапа по отдельности. План начинается с оператор JOIN, а затем на каждом этапе добавляется новый JOIN в соответствии с правилом.

Рассмотрим простой пример. Возьмём запрос с 4 объединениями 5 таблиц (A, B, C, D и E). Несколько упростим задачу и представим, что единственным вариантом является объединение с помощью вложенных алгоритмов. Будем использовать правило «применять объединение с наименьшей стоимостью».

• Начинаем с одной из таблиц, например, А.
• Вычисляем стоимость каждого объединения с А (она будет как в роли внешней, так и внутренней зависимости).
• Находим, что дешевле всего нам обойдётся A JOIN B.
• Затем вычисляем стоимость каждого объединения с результатом A JOIN B (его тоже рассматриваем в двух ролях).
• Находим, что выгоднее всего будет (A JOIN B) JOIN C.
• Опять делаем оценку возможных вариантов.
• В конце получаем такой план исполнения запроса: (((A JOIN B) JOIN C) JOIN D) JOIN E)/

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

Данный алгоритм называется «алгоритм ближайшего соседа ».

Не будем углубляться в подробности, но при хорошем моделировании сложности сортировки N*log(N) данная проблема может быть . Временнáя сложность алгоритма равна О(N*log(N)) вместо О(3 N) для полной версии с динамическим программированием. Если у вас большой запрос с 20 объединениями, то это будет 26 против 3 486 784 401. Большая разница, верно?

Но есть нюанс. Мы предполагаем, что если найдём наилучший способ объединения двух таблиц, то получим самую низкую стоимость при объединении результатом предыдущих объединений со следующими таблицами. Однако даже если A JOIN B будет самым дешёвым вариантом, то (A JOIN C) JOIN B может иметь стоимость ниже, чем (A JOIN B) JOIN C.

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

Другие алгоритмы

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

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

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

В качестве примера можно привести генетические алгоритмы:

• Каждое решение представляет собой план полного исполнения запроса.
• Вместо одного решения (плана) алгоритм на каждом этапе формирует Х решений.
• Сначала создаётся Х планов, делается это случайным образом.
• Из них сохраняются только те планы, чья стоимости удовлетворяет некоему критерию.
• Затем эти планы смешиваются, что бы создать Х новых планов.
• Некоторые из новых планов модифицируются случайным образом.
• Предыдущие три шага повторяются Y раз.
• Из планов последнего цикла мы получаем наилучший.

Чем больше циклов, тем более дешёвый план можно рассчитать. Естественный отбор, закрепление признаков, вот это всё.
Кстати, генетические алгоритмы интегрированы в PostgreSQL .

В БД используются и такие эвристические алгоритмы, как симулированная нормализация (Simulated Annealing), итеративное улучшение (Iterative Improvement), двухфазная оптимизация (Two-Phase Optimization). Но не факт, что они применяются в корпоративных системах, возможно, их удел - исследовательские продукты.

4.4.6. Настоящие оптимизаторы

Тоже необязательная глава, можно и пропустить.

Давайте отойдём от теоретизирования и рассмотрим реальные примеры. Например, как работает оптимизатор SQLite . Это «лёгкая» БД, использующая простую оптимизацию на основе жадного алгоритма с дополнительными правилами:

• SQLite никогда не меняет порядок таблиц в операции CROSS JOIN.
• Используется объединение с помощью вложенных циклов.
• Внешние объединения всегда оцениваются в том порядке, в котором они осуществлялись.
• Вплоть до версии 3.8.0 для поиска наилучшего плана исполнения запроса используется жадный алгоритм «ближайшего соседа» (Nearest Neighor). А с версии 3.8.0 применяется «N ближайших соседей » (N3, N Nearest Neighbors).

А вот другой пример. Если почитать документацию IBM DB2, то мы узнаем, что её оптимизатор используется 7 разных уровней оптимизации:

• Жадные алгоритмы:
  • 0 - минимальная оптимизация. Используется сканирование индекса, объединение с помощью вложенных циклов и исключение перезаписи некоторых запросов.
  • 1 - низкая оптимизация
  • 2 - полная оптимизация
• Динамическое программирование:
  • 3 - средняя оптимизация и грубая аппроксимация
  • 5 - полная оптимизация, используются все эвристические методики
  • 7 - то же самое, но без эвристики
  • 9 - максимальная оптимизация любой ценой, без оглядки на затрачиваемые усилия. Оцениваются все возможные способы объединения, включая декартовы произведения.

По умолчанию применяется уровень 5. Сюда входит:

• Сбор всей возможной статистики, включая частотные распределения и квантили.
• Применение всех правил перезаписи запросов, включая составление табличного маршрута для материализованных запросов). Исключение составляют правила, требующие интенсивных вычислений, применяемые для очень ограниченного числа случаев.
• При переборе вариантов объединения с помощью динамического программирования:
  • Ограниченно используется составная внутренняя зависимость.
  • Для звездообразных схем с таблицами преобразования ограниченно используются декартовы произведения.
• Рассматривается широкий диапазон способов доступа, включая предварительную выборку списка (об этом ниже), специальную операцию с индексами AND и составление табличного маршрута для материализованных запросов.

Конечно, разработчики не делятся подробностями об эвристике, используемой в их продукте, ведь оптимизатор - едва ли не самая важная часть БД. Однако известно, что по умолчанию для определения порядка объединения используется динамическое программирование, ограничиваемое эвристикой.

Прочие условия (GROUP BY, DISTINCT и т.д.) обрабатываются простыми правилами.

4.4.7. Кэш плана запросов

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

Исполнитель запросов

На данном этапе наш план уже оптимизирован. Он перекомпилируется в исполняемый код и, если ресурсов достаточно, исполняется. Операторы, содержащиеся в плане (JOIN, SORT BY и т.д.) могут обрабатываться как последовательно, так и параллельно, решение принимает исполнитель. Для получения и записи данных он взаимодействует с диспетчером данных.

5. Диспетчер данных

Диспетчер запросов исполняет запрос и нуждается в данных из таблиц и индексов. Он запрашивает их у диспетчера данных, но тут есть две трудности:

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

5.1. Диспетчер кэша

Как уже не раз говорилось, самым узким местом в БД является дисковая подсистема. Поэтому для увеличения производительности используется диспетчер кэша.

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

• Последовательный доступ (полное сканирование) или случайный (доступ по ID строки).
• Читать или записывать.

Также большое значение имеет тип накопителей, используемых в дисковой системе: «винчестеры» с разной скоростью вращения шпинделя, SSD, наличие RAID в разных конфигурациях. Но можно сказать, что использование памяти в 100-100 000 раз быстрее, чем диска.

Однако тут мы сталкиваемся с другой проблемой. Диспетчеру кэша нужно положить данные в память ДО того, как они понадобятся исполнителю запросов. Иначе тому придётся ждать их получения с медленного диска.

5.1.1. Упреждение

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

Когда исполнитель обрабатывает первую порцию данных, он просит диспетчер кэша заранее подгрузить следующую порцию. А когда переходит к её обработке, то просит ДК подгрузить третью и подтверждает, что первую порцию можно удалить из кэша.

Диспетчер кэша хранит эти данные в буферном пуле. Он также добавляет к ним сервисную информацию (триггер, latch), чтобы знать нужны ли они ещё в буфере.

Иногда исполнитель не знает, какие данные ему будут нужны, или некоторые БД не имеют подобного функционала. Тогда используется спекулятивное упреждение (speculative prefetching) (например, если исполнитель запрашивает данные 1, 3, 5, то наверняка запросит в будущем 7, 9, 11) или последовательное упреждение (sequential prefetching) (в данном случае ДК просто подгружает с диска следующую по порядку порцию данных.

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

5.1.2. Стратегии замены буфера

Большинство БД (по крайне мере, SQL Server, MySQL, Oracle и DB2) используют для этого алгоритм LRU (Least Recently Used). Он предназначен для поддержания в кэше тех данных, которые недавно использовались, а значит велика вероятность, что они могут понадобиться снова.

Для облегчения понимания работы алгоритма примем, что данные в буфере не блокируются триггерами (latch), а значит могут быть удалены. В нашем примере буфер может хранить три порции данных:

1. Диспетчер кэша используется данные 1 и кладёт их в пустой буфер.
2. Затем он использует данные 4 и тоже отправляет их в буфер.
3. То же самое делается и с данными 3.
4. Далее берутся данные 9. Но буфер-то уже заполнен. Поэтому из него удаляются данные 1, так как они не использовались дольше всего. После этого в буфер помещаются данные 9.
5. Диспетчер кэша снова использует данные 4. Они уже есть в буфере, поэтому помечаются как последние использованные.
6. Снова становятся востребованы данные 1. Чтобы их поместить в буфер, из него удаляются данные 3, как не использовавшиеся дольше всего.

Это хороший алгоритм, но у него есть некоторые ограничения. Что если у нас осуществляется полное сканирование большой таблицы? Что будет, если размер таблицы/индекса превосходит объём буфера? В этом случае алгоритм удалит из кэша вообще всё его содержимое, таким образом данные полного сканирования, скорее всего, будут использоваться лишь один раз.

Улучшения алгоритма

Чтобы этого не произошло, в некоторых БД используются специальные правила. Согласно документации Oracle :

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

Также используется улучшенная версия LRU - LRU-K. В SQL Server применяется LRU-K при К = 2. Суть этого алгоритма в том, что при оценке ситуации он учитывает больше информации о прошлых операциях, а не только запоминает последние использованные данные. Буква К в названии означает, что алгоритм принимает во внимание, какие данные использовались последние К раз. Им присваивается определённый вес. Когда в кэш загружаются новые данные, то старые, но часто используемые не удаляются, потому что их вес выше. Конечно, если данные больше не используются, то они всё-таки будут удалены. И чем дольше данные остаются невостребованными, тем сильнее уменьшается со временем их вес.

Вычисление веса довольно накладно, поэтому в SQL Server используется LRU-K при К равном всего лишь 2. При некотором увеличении значения К эффективность алгоритма улучшается. Вы можете ближе познакомиться с ним благодаря .

Другие алгоритмы

Конечно, LRU-K не единственное решение. Существуют также 2Q и CLOCK (оба похожи на LRU-K), MRU (Most Recently Used, в котором используется логика LRU, но применяется другое правило, LRFU (Least Recently and Frequently Used) и т.д. В некоторых БД можно выбирать, какой алгоритм будет использоваться.

5.1.3. Буфер записи

Мы говорили только о буфере чтения, но БД используют и буферы записи, которые накапливают данные и сбрасывают на диск порциями, вместо последовательной записи. Это позволяет экономить операции ввода/вывода.
Помните, что буферы хранят страницы (неделимые единицы данных), а не ряды из таблиц. Страница в буферном пуле называется «грязной», если она модифицирована, но не записана на диск. Есть много разных алгоритмов, с помощью которых выбирается время записи грязных страниц. Но это во многом связано с понятием транзакций.

5.2. Диспетчер транзакций

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

5.2.1. «Под кислотой» (игра слов, если кто не понял)

ACID-транзакция (Atomicity, Isolation, Durability, Consistency) - это элементарная операция, единица работы, которая удовлетворяет 4 условиям:

• Атомарность (Atomicity). Нет ничего «меньше» транзакции, никакой более мелкой операции. Даже если транзакция длится 10 часов. В случае неудачного выполнения транзакции система возвращается в состояние «до», то есть транзакция откатывается.
• Изолированность (Isolation) . Если в одно время выполняются две транзакции А и В, то их результат не должен зависеть от того, завершилась ли одна из них до, во время или после исполнения другой.
• Надёжность (Durability). Когда транзакция зафиксирована (commited), то есть успешно завершена, использовавшиеся ею данные остаются в БД вне зависимости от возможных происшествий (ошибки, падения).
• Консистентность (согласованность) (Consistency). В БД записываются только валидные данные (с точки зрения реляционных и функциональных связей). Консистентность зависит от атомарности и изолированности.

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

• Т1 берёт $100 со счёта А и отправляет их на счёт Б.
• Т2 берёт $50 со счёта А и тоже отправляет их на счёт Б.

Теперь рассмотрим эту ситуацию с точки зрения ACID-свойств:

• Атомарность позволяет быть уверенным, что какое бы событие не произошло в ходе Т1 (падение сервера, сбой сети), не может случиться так, что $100 будут списаны с А, но не придут на Б (в противном случае говорят о «несогласованном состоянии»).
• Изолированность говорит о том, что даже если Т1 и Т2 осуществляются одновременно, в результате с А будет списано $100 и та же сумма поступит на Б. Во всех остальных случаях опять говорят о несогласованном состоянии.
• Надёжность позволяет не беспокоиться о том, что Т1 исчезнет, если база упадёт сразу после коммита Т1.
• Консистентность предотвращает возможность создания денег или их уничтожения в системе.

Ниже можно не читать, это уже не важно для понимания остального материала.

Многие БД не обеспечивают полную изолированность по умолчанию, поскольку это приводит к огромным издержкам в производительности. В SQL используется 4 уровня изолированности:

• Сериализуемые транзакции (Serializable). Наивысший уровень изолированности. По умолчанию используется в SQLite. Каждая транзакция исполняется в собственной, полностью изолированной среде.
• Повторяемое чтение (Repeatable read). По умолчанию используется в MySQL. Каждая транзакция имеет свою среду, за исключением одной ситуации: если транзакция добавляет новые данные и успешно завершается, то они будут видимы для других, всё ещё выполняющихся транзакций. Но если транзакция модифицирует данные и успешно завершается, то эти изменения будут не видны для всё ещё выполняющихся транзакций. То есть для новых данных принцип изолированности нарушается.

  Например, транзакция А выполняет

  SELECT count(1) from TABLE_X
  Потом транзакция Б добавляет в таблицу Х и коммитит новые данные. И если после этого транзакция А снова выполняет count(1), то результат будет уже другим.

  Это называется фантомным чтением.

• Чтение зафиксированных данных (Read commited) . По умолчанию используется в Oracle, PostgreSQL и SQL Server. Это то же самое, что и повторяемое чтение, но с дополнительным нарушением изолированности. Допустим, транзакция А читает данные; затем они модифицируются или удаляются транзакцией Б, которая коммитит эти действия. Если А снова считает эти данные, то она увидит изменения (или факт удаления), сделанные Б.

  Это называется неповторяемым чтением (non-repeatable read).

• Чтение незафиксированных данных (Read uncommited). Самый низкий уровень изолированности. К чтению зафиксированных данных добавляется новое нарушение изолированности. Допустим, транзакция А читает данные; затем они модифицируются транзакцией Б (изменения не коммитятся, Б всё ещё выполняется). Если А считает данные снова, то увидит сделанные изменения. Если же Б будет откачена назад, то при повторном чтении А не увидит изменений, словно ничего и не было.

  Это называется грязным чтением.

Большинство БД добавляют собственные уровни изолированности (например, на основе снэпшотов, как в PostgreSQL, Oracle и SQL Server). Также во многих БД не реализованы все четыре вышеописанных уровня, особенно чтение незафиксированных данных.

Пользователь или разработчик может сразу же после установления соединения переопределить уровень изолированности по умолчанию. Для этого достаточно добавить очень простую строчку кода.

5.2.2. Управление параллелизмом

Главное, для чего нам нужны изолированность, согласованность и атомарность, это возможность осуществлять операции записи над одними и теми же данными (добавлять, обновлять и удалять).

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

Это называется управлением параллелизмом.

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

Идеальный способ решения проблемы выглядит так (при каждом создании или отмене транзакции):

• Мониторить все операции каждой транзакции.
• Если две и более транзакции конфликтуют из-за чтения/изменения одних и тех же данных, то менять очерёдность операций внутри участников конфликта, чтобы свести к минимуму количество причин.
• Выполнять конфликтующие части транзакций в определённом порядке. Неконфликтующие транзакции в это время выполняются параллельно.
• Иметь в виду, что транзакции могут быть отменены.

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

5.2.3. Диспетчер блокировок

Для решения вышеописанной проблемы во многих БД используются блокировки (locks) и/или версионность данных.
Если транзакции нужны какие-то данные, то она блокирует их. Если другой транзакции они тоже потребовались, то её придётся ждать, пока первая транзакция не снимет блокировку.

Это называется эксклюзивной блокировкой.

Но слишком расточительно использовать эксклюзивные блокировки в случаях, когда транзакциям нужно всего лишь считать данные. Зачем мешать чтению данных? В таких случаях используются совместные блокировки. Если транзакции нужно считать данные, они применяет к ним совместную блокировку и читает. Это не мешает другим транзакциям тоже применять совместные блокировки и читать данные. Если же какой-то из них нужно изменить данные, то ей придётся подождать, пока все совместные блокировки не будут сняты. Только после этого она сможет применить эксклюзивную блокировку. И тогда уже всем остальным транзакциям придётся ждать её снятия, чтобы считывать эти данные.

Диспетчер блокировок - это процесс, который применяет и снимает блокировки. Они хранятся в хэш-таблице (ключами являются блокируемые данные). Диспетчер знает для всех данных, какие транзакции применили блокировки или ждут их снятия.

Взаимная блокировка (deadlock)

Использование блокировок может привести к ситуации, когда две транзакции бесконечно ожидают снятия блокировок:

Здесь транзакция А эксклюзивно заблокировала данные 1 и ожидает освобождения данных 2. В то же время транзакция Б эксклюзивно заблокировала данные 2 и ожидает освобождения данных 1.

При взаимной блокировке диспетчер выбирает, какую транзакцию отменить (откатить назад). И решение принять не так просто:

• Будет ли лучше убить транзакцию, которая изменила последний набор данных (а значит, откат будет наименее болезненным)?
• Будет ли лучше убить самую молодую транзакцию, поскольку пользователи других транзакций прождали дольше?
• Будет ли лучше убить транзакцию, которой требуется меньше времени для завершения?
• На сколько других транзакций повлияет откат?

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

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

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

Двухфазная блокировка

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

В DB2 и SQL Server применяется протокол двухфазной блокировки, при котором транзакция делится на две фазы:

• Фазу подъёма (growing phase) , когда транзакция может только применять блокировки, но не снимать их.
• Фазу спада (shrinking phase) , когда транзакция может только снимать блокировки (с данных, которые уже обработаны и не будут обрабатываться снова), но не применять новые.

Частый конфликт, случающийся в отсутствие двухфазной блокировки:

До транзакции А X = 1 и Y = 1. Она обрабатывает данные Y = 1, которые были изменены транзакцией В уже после начала транзакции А. В связи с принципом изолированности транзакция А должна обрабатывать Y = 2.

Цели, решаемые с помощью этих двух простых правил:

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

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

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

Версионность данных

Ещё один способ решения проблемы конфликта транзакций - использование версионности данных.

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

Это позволяет увеличить производительность, поскольку:

• Читающие транзакции не блокируют записывающие, и наоборот.
• Неповоротливый диспетчер блокировок не оказывает влияния.

В общем, всё что угодно будет лучше, чем блокировки, за исключением случаев, когда две транзакции записывают одни и те же данные. Причём это может привести к огромному перерасходу дискового пространства.

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

В некоторых БД (DB2 до версии 9.7, SQL Server) используются только блокировки. Другие, вроде PostgreSQL, MySQL и Oracle, используются комбинированные подходы.

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

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

Как обычно, за более подробной информацией обращайтесь к документации: MySQL , PostgreSQL , Oracle .

5.2.4. Диспетчер логов

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

Конечно, можно всё писать на диск, но при падении вы останетесь с недописанными данными, а это уже нарушение принципа атомарности.

Любые изменения, записанные транзакцией, должны быть отменены или завершены.

Это делается двумя способами:

• Теневые копии/страницы. Каждая транзакция создаёт собственную копию БД (или её часть), и работает с этой копией. В случае ошибки копия удаляется. Если всё прошло успешно, то БД мгновенно переключается на данные из копии с помощью одной уловки на уровне файловой системы, а потом удаляет «старые» данные.
• Лог транзакции. Это специальное хранилище. Перед каждой записью на диск БД пишет информацию в лог транзакции. Так что в случае сбоя БД будет знать, как удалить или завершить незавершённую транзакцию.

WAL

В больших БД с многочисленными транзакциями теневые копии/страницы занимают невероятно много места в дисковой подсистеме. Поэтому в современных БД используется лог транзакции. Он должен размещаться в защищённом от сбоев хранилище.

Большинство продуктов (в частности, Oracle, SQL Server , DB2 , PostgreSQL , MySQL и SQLite) работают с логом транзакции через протокол WAL (Write-Ahead Logging). Данные протокол содержит три правила:

1. Каждая модификация в БД должна сопровождаться записью в лог, и она должна вноситься ДО того, как данные будут записаны на диск.
2. Записи в логе должны располагаться в соответствии с очерёдностью соответствующих событий.
3. Когда транзакция коммитится, запись об этом должна вноситься в лог ДО момента успешного завершения транзакции.

За выполнением этих правил следит диспетчер логов. Логически он расположен между диспетчером кэша и диспетчером доступа к данным. Диспетчер логов регистрирует каждую операцию, выполняемую транзакциями, до момента записи на диск. Вроде верно?

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

ARIES

В 1992 год исследователи из IBM создали расширенную версию WAL, которую назвали ARIES. В том или ином виде ARIES используется большинством современных БД. Если вы захотите поглубже изучить этот протокол, можете проштудировать соответствующую работу .

Итак, ARIES расшифровывается как A lgorithms for R ecovery and I solation E xploiting S emantics. У этой технологии две задачи:

1. Обеспечить хорошую производительность при записи логов.
2. Обеспечить быстрое и надёжное восстановление.

Есть несколько причин, по которым БД приходится откатывать транзакцию:

1. Пользователь отменил её.
2. Ошибка сервера или сети.
3. Транзакция нарушила целостность БД. Например, вы применили к колонке условие UNIQUE, а транзакция добавила дубликат.
4. Наличие взаимных блокировок.

Но иногда БД может и восстанавливать транзакцию, допустим, в случае сетевой ошибки.

Как это возможно? Чтобы ответить на это, нужно сначала разобраться с тем, какая информация сохраняется в логе.

Логи
Каждая операция (добавления/удаления/изменения) во время выполнения транзакции ведёт к появлению записи в логе. Запись содержит:

• LSN (Log Sequence Number) . Это уникальный номер, значение которого определяется хронологическим порядком. То есть если операция А произошла до операции Б, LSN для А будет меньше LSN для Б. В реальности способ генерирования LSN сложнее, поскольку он связан и со способом хранения лога.
• TransID. Идентификатор транзакции, осуществившей операцию.
• PageID . Место на диске, где находятся изменённые данные.
• PrevLSN . Ссылка на предыдущую запись в логе, созданную той же транзакцией.
• UNDO . Способ отката операции.

  Например, если была проведена операция обновления, то в UNDO записывается предыдущее значение/состояние изменённого элемента (физический UNDO) или обратная операция, позволяющая вернуться в предыдущее состояние (логический UNDO). В ARIES используется только логический, с физическим работать очень тяжело.

• REDO . Способ повтора операции.

Кроме того, каждая страница на диске (для хранения данных, а не лога) содержит LSN последней операции, модифицировавшиеся содержащиеся здесь данные.

Насколько известно, UNDO не используется только в PostgreSQL. Вместо этого используется сборщик мусора, убирающий старые версии данных. Это связано с реализацией версионности данных в этой СУБД.

Чтобы вам было легче представить состав записи в логе, вот визуальный упрощённый пример, в котором выполняется запрос UPDATE FROM PERSON SET AGE = 18;. Пусть он исполняется в транзакции номер 18:

Каждый лог имеет уникальный LSN. Связанные логи относятся к одной и той же транзакции, причём линкуются они в хронологическом порядке (последний лог списка относится к последней операции).

Буфер логов
Чтобы запись в лог не превратилась в узкое место системы, используется буфер логов.

Когда исполнитель запросов запрашивает модифицированные данные:

1. Диспетчер кэша хранит их в буфере.
2. Диспетчер логов хранит в собственном буфере соответствующий лог.
3. Исполнитель запросов определяет, завершена ли операция, и, соответственно, можно ли запрашивать изменённые данные.
4. Диспетчер логов сохраняет нужную информацию в лог транзакции. Момент внесения этой записи задаётся алгоритмом.
5. Диспетчер кэша записывает изменения на диск. Момент осуществления записи также задаётся алгоритмом.

Когда транзакция коммитится, это означает, что выполнены все шаги с 1 по 5. Запись в лог транзакции осуществляется быстро, поскольку представляет собой «добавление лога куда-то в лог транзакции». В то же время запись данных на диск представляет собой более сложную процедуру, при этом учитывается, что данные впоследствии должны быть быстро считаны.

Политики STEAL и FORCE

Для увеличения производительности шаг номер 5 нужно делать после коммита, поскольку в случае сбоя всё ещё возможно восстановить транзакцию с помощью REDO. Это называется «политика NO-FORCE».

Но БД может выбрать и политику FORCE ради уменьшения нагрузки во время восстановления. Тогда шаг номер 5 выполняется до коммита.

Также БД выбирает, записывать ли данные на диск пошагово (политика STEAL) или, если диспетчер буфера должен дождаться коммита, записать всё разом (NO-STEAL). Выбор зависит от того, что вам нужно: быструю запись с долгим восстановлением или быстрое восстановление?

Как упомянутые политики влияют процесс восстановления:

• Для STEAL/NO-FORCE нужны UNDO и REDO. Производительность высочайшая, но более сложная структура логов и процессов восстановления (вроде ARES). Эту комбинацию политик использует большинство БД.
• Для STEAL/FORCE нужен только UNDO.
• Для NO-STEAL/NO-FORCE - только REDO.
• Для NO-STEAL/FORCE вообще ничего не нужно. Производительность в данном случае самая низкая, и требуется огромное количество памяти.

Восстановление

Итак, как нам можно использовать наши замечательные логи? Предположим, что новый сотрудник порушил БД (правило №1: всегда виноват новичок!). Вы её перезапускаете и начинается процесс восстановления.
ARIES восстанавливает в три этапа:

1. Анализ . Считывается весь лог транзакции, чтобы можно было восстановить хронологию событий, произошедших в процессе падения базы. Это помогает определить, какую транзакцию нужно откатить. Откатываются все транзакции без приказа о коммите. Также система решает, какие данные должны были записаться на диск во время сбоя.
2. Повтор . Для обновления БД до состояния перед падением используется REDO. Его логи обрабатываются в хронологическом порядке. Для каждого лога считывается LSN страницы на диске, содержащей данные, которые нужно изменить.

   Если LSN(страницы_на_диске)>=LSN(записи_в_логе), то значит данные уже были записаны на диск перед сбоем. Но значение было перезаписано операцией, которая была выполнена после записи в лог и до сбоя. Так что ничего не сделано, на самом деле.

   Если LSN(страницы_на_диске)

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

3. Отмена. На этом этапе откатываются все незавершённые на момент сбоя транзакции. Процесс начинается с последних логов каждой транзакции и обрабатывает UNDO в обратном хронологическом порядке с помощью PrevLSN.

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

Если транзакция отменена «вручную», или диспетчером блокировок, или из-за сбоя сети, то этап анализа не нужен. Ведь информация для REDO и UNDO содержится в двух таблицах, размещённых в памяти:

• В таблице транзакций (тут хранятся состояния всех текущих транзакций).
• В таблице грязных страниц (здесь содержится информация о том, какие данные нужно записать на диск).

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

Этап анализа нужен как раз для восстановления обеих таблиц с помощью информации из лога транзакций. Для ускорения этого этапа в ARIES используются контрольные точки. На диск время от времени записывается содержимое обеих таблиц, а также последний на момент записи LSN. Так что во время восстановления анализируются только логи, следующие после этого LSN.

6. Заключение

В качестве дополнительного обзорного чтива про базы данных можно порекомендовать статью Architecture of a Database System . Это хорошее введение в тему, написанное довольно понятным языком.

Если вы внимательно прочитали весь вышеизложенный материал, то наверняка получили представление о том, насколько велики возможности баз данных. Однако в этой статье не затронуты другие важные проблемы:

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

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

Итак, если вас кто-нибудь спросит, а как же работают базы данных, то вместо того, чтобы плюнуть и уйти, вы можете ответить:

Теги: Добавить метки