Функции СУБД.

Функции СУБД бывают высокого и низкого уровня.

Функции высокого уровня:

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

2. Обработка данных. Информация может обрабатываться разными способами: выборка, фильтрация, сортировка, объединение одной информации с другой, вычисление итоговых значений.

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

Функции низкого уровня:

1. Управление данными во внешней памяти;

2. Управление буферами оперативной памяти;

3. Управление транзакциями;

4. Введение журнала изменений в БД;

5. Обеспечение целостности и безопасности БД.

Транзакцией называется неделимая последовательность операций, которая отслеживается СУБД от начала и до завершения, и в которой при невыполнении одной операции отменяется вся последовательность.

Журнал СУБД – особая БД или часть основной БД, недоступная пользователю и используемая для записи информации обо всех изменениях базы данных.

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

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

Классификация СУБД.

СУБД можно классифицировать:

1. По видам программ:

a. Серверы БД (например, MS SQL Server, InterBase (Borland)) – предназначены для организации центров обработки данных в сетях ЭВМ и реализуют функции управления базами данных, запрашиваемые клиентскими программами с помощью операторов SQL (т.е. программы, которые отвечают на запросы);

b. Клиенты БД – программы, которые запрашивают данные. В качестве клиентских программ могут использоваться ПФСУБД, электронные таблицы, текстовые процессоры, программы электронной почты;

c. Полнофункциональные БД (MS Access, MS Fox Pro) – программа, имеющая развитый интерфейс, позволяющий создавать и модифицировать таблицы, вводить данные, создавать и форматировать запросы, разрабатывать отчёты и выводить их на печать.

2. По модели данных СУБД (как и БД):

a. Иерархические – основаны на древовидной структуре хранения информации и напоминают файловую систему компьютера; основной недостаток - невозможность реализовать отношение многие - ко – многим;

b. Сетевые – которые пришли на смену иерархическим и просуществовали недолго т. к. основной недостаток – сложность разработки серьёзных приложений. Основное отличие сетевой от иерархической в том, что в иерархической структура «запись – потомок» имеет только одного предка, а в сетевой потомок может иметь любое количество предков;

c. Реляционные – данные которых размещены в таблицах, между которыми существуют определённые связи;

d. Объектно – ориентированные – в них данные хранятся в виде объектов и основное преимущество при работе с ними в том, что к ним можно применить объектно – ориентированный подход;

e. Гибридные, т. е. объектно – реляционные – совмещают в себе возможности реляционных и объектно – ориентированных баз данных. Примером такой базы данных является Oracle (ранее она была реляционной).

3. В зависимости от расположения отдельных частей СУБД различают:

a. локальные – все части которой располагаются на одном компьютере;

b. сетевые.

К сетевым относятся:

- с организацией файл – сервер ;

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

- с организацией клиент – сервер;

Сервер БД принимает запрос от клиента, отыскивает в данных нужную запись и передаёт её клиенту. Запрос к серверу формируется на языке структурированных запросов SQL, поэтому серверы БД называют SQL – серверами.

- распределённые СУБД содержат несколько десятков и сотен серверов, размещённых на значительной территории.

Основные положения реляционной модели БД.

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

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

1. Данные хранятся в таблицах, состоящих из столбцов и строк;

2. На пересечении каждого столбца и строки находится одно значение;

3. У каждого столбца - поля есть своё имя, которое служит его названием - атрибут, и все значения в одном столбце, имеют один тип;

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

Терминология реляционной базы данных:

Элемент реляционной БД	Форма представления
1. База данных	Набор таблиц
2. Схема базы данных	Набор заголовков таблиц
3. Отношение	Таблица
4. Схема отношения	Строка заголовков столбцов таблицы
5. Сущность	Описание свойств объекта
6. Атрибут	Заголовок столбца
7. Домен	Множество допустимых значений атрибута
8. Первичный ключ	Уникальный идентификатор, однозначно определяющий каждую запись в таблице
9. Тип данных	Тип значений элементов в таблице
10. Кортеж	Строка (запись)
11. Кардинальность	Количество строк в таблице
12. Степень отношения	Количество полей
13. Тело отношения	Множество кортежей отношения

При проектировании реляционной БД данные размещают в нескольких таблицах. Между таблицами устанавливают связи с помощью ключей. При связывании таблиц выделяют основную и дополнительную (подчинённую) таблицу.

Существуют следующие виды связей между таблицами:

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

2. Связь вида 1:М (один ко многим) означает, что каждой записи в основной таблице соответствует несколько записей в дополнительной таблице и, наоборот, каждой записи в дополнительной таблице соответствует только одна запись в основной таблице.

3. Связь вида М:1 (многим к одному) означает, что одной или нескольким записям в основной таблице соответствует только одна запись в дополнительной таблице.

4. Связь вида М:М (многим ко многим) – это, когда нескольким записям основной таблицы соответствует несколько записей дополнительной и наоборот.

5. Основные компоненты MS Access.

Основными компонентами (объектами) MS Access являются:

1. Таблицы;

3. Формы;

4. Отчёты;

5. Макросы:

Модули.

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

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

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

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

Макрос – одна или несколько макрокоманд, которые можно использовать для автоматизации конкретной задачи. Макрокоманда – основной строительный блок макроса; самостоятельная инструкция, которая может быть объединена с другими макрокомандами, чтобы автоматизировать выполнение задачи.

Модуль – набор описаний, инструкций и процедур, сохранённых под одним именем. В MS Access имеется три вида модулей:модуль формы, отчёта и общий модуль. Модули формы и отчётов содержат локальную программу для форм и отчётов.

6. Таблицы в MS Access.

В MS Access существуют следующие методы создания таблиц:

1. Режим таблицы;

2. Конструктор;

3. Мастер таблиц;

4. Импорт таблиц;

5. Связь с таблицами.

В режиме таблицы данные вводятся в пустую таблицу. Для ввода данных предоставляется таблица с 30 полями. После её сохранения MS Access сам решает, какой тип данных присвоить каждому полю.

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

Для определения поля в режиме Конструктор задаются:

1. Имя поля , которое в каждой таблице должно иметь уникальное имя, являющееся комбинацией букв, цифр, пробелов и специальных символов, за исключением «.!” “ ». Максимальная длина имени 64 символа.

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

Типы данных MS Access

Тип данных	Описание
Текстовый	Текст и числа, например, имена и адреса, номера телефонов, почтовые индексы (до 255 символов).
Поле Memo	Длинный текст и числа, например комментарии и пояснения (до 64000 символов).
Числовой	Общий тип данных для числовых данных, допускающих проведение математических расчётов, за исключением денежных расчётов.
Дата / время	Значения даты и времени. Пользователь может выбирать стандартные формы или создавать специальный формат.
Денежный	Денежные значения. Для денежных расчётов не рекомендуется использовать числовые типы данных, т.к. они могут округляться при расчётах. Значения типа «денежный» всегда выводятся с указанным числом десятичных знаков после запятой.
Счётчик	Автоматически выставляющиеся последовательные номера. Нумерация начинается с 1. Поле счётчика удобно для создания ключа. Это поле является совместимым с полем числового типа, для которого в свойстве Размер указано значение «Длинное целое».
Логический	Значения «Да / Нет», «Истинно / Ложь», «Вкл / Выкл», одно из двух возможных значений.
Поле объекта OLE	Объекты, созданные в других программах, поддерживающие протокол OLE.

3. Наиболее важные свойства полей:

- Размер поля задаёт максимальный размер данных, сохраняемых в поле.

- Формат поля является форматом отображения заданного типа данных и задаёт правила представления данных при выводе их на экран или печать.

- Подпись поля задаёт текст, который выводится в таблицах, формах, отчётах.

- Условие на значение позволяет осуществлять контроль ввода, задаёт ограничения на вводимые значения, при нарушении условий запрещает ввод и выводит текст, заданный свойством Сообщение об ошибке;

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

Тип элемента управления – свойство, которое задаётся на закладке Подстановка в окне конструктора таблиц. Это свойство определяет, будет ли отображаться поле в таблице и в какой форме – в виде поля или поля со списком.

Уникальный (первичный) ключ таблицы может быть простым или составным, включающим несколько полей.

Для определения ключа выделяются поля, составляющие ключ, и на панели инструментов нажимается кнопка ключевое поле или выполняется команда Правка / ключевое поле .

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-16

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

«отношение» – «таблица» (иногда файл), «кортеж» – «строка» (иногда запись), «атрибут» – «столбец», «поле».

При этом принимается, что «запись» означает «экземпляр записи», а «поле» означает «имя и тип поля».

Реляционная база данных

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

Каждая таблица состоит из однотипных строк и имеет уникальное имя; Строки имеют фиксированное число полей (столбцов) и значений (мно-

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

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

Столбцам таблицы однозначно присваиваются имена, и в каждом из них размещаются однородные значения данных (даты, фамилии, целые числа или денежные суммы);

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

тия до 12 ч).

Манипулирование реляционными данными

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

Рис. 1.5. Некоторые операции реляционной алгебры

Созданы языки манипулирования данными, позволяющие реализовать все операции реляционной алгебры и практически любые их сочетания. Среди них наиболее распространены SQL (Structured Query Language – структуриро-

ванный язык запросов) и QBE (Quere-By-Example – запросы по образцу) . Оба от-

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

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

Проектирование реляционных баз данных, цели проектирования

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

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

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

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

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

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

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

Основная цель проектирования БД – это сокращение избыточности хранимых данных, а следовательно, экономия объема используемой памяти, уменьшение затрат на многократные операции обновления избыточных копий и устранение возможности возникновения противоречий из-за хранения в разных местах сведений об одном и том же объекте. Так называемый, «чистый» проект БД ("Каждый факт в одном месте") можно создать, используя методологию нормализации отношений.

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

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

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

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

– «полностью нормализованная», который означает, что в проекте не нарушаются никакие принципы нормализации.

Теперь в дополнение к 1НФ можно определить дальнейшие уровни нор-

мализации – вторую нормальную форму(2НФ), третью нормальную форму

(3НФ )и т.д. По существу, таблица находится в 2НФ, если она находится в 1НФ

и удовлетворяет, кроме того, некоторому дополнительному условию, суть которого будет рассмотрена ниже. Таблица находится в 3НФ, если она находится в 2НФ и, помимо этого, удовлетворяет еще другому дополнительному условию

и т.д.

Таким образом, каждая нормальная форма является в некотором смысле более ограниченной, но и более желательной , чем предшествующая. Это связано с тем, что «(N+1)-я нормальная форма» не обладает некоторыми непривлекательными особенностями, свойственными «N-й нормальной форме». Общий смысл дополнительного условия, налагаемого на (N+1)-ю нормальную форму по отношению к N-й нормальной форме, состоит в исключении этих непривлекательных особенностей.

Теория нормализации основывается на наличии той или иной зависимости между полями таблицы. Определены два вида таких зависимостей: функ-

циональные и многозначные.

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

Полная функциональная зависимость. Поле В находится в полной функ-

циональной зависимости от составного поля А, если оно функционально зависит от А и не зависит функционально от любого подмножества поля А.

Многозначная зависимость . Поле А многозначно определяет поле В той

Все современные БД используют 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-базы очень хороши. Но они ещё далеки от совершенства и могут помочь только в решении специфических проблем, связанных с некоторыми приложениями.

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

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

2. Принципы реляционной модели

Принципы реляционной модели баз данных, отношение (relation), таблица (table), набор результатов (result set), кортеж, мощность, атрибут, размерность, заголовок, тело, домен

Реляционная модель была разработана в конце 1960-х годов Е.Ф.Коддом (сотрудник IBM) и опубликованы в 1970 г. Она определяет способ представления данных (структуру данных), методы защиты данных (целостность данных), и операции, которые можно выполнять с данными (манипулирование данными).

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

Основные принципы реляционных баз данных можно сформулировать так:

· все данные на концептуальном уровне представляются в виде упорядоченной организации, определенной в виде строк и столбцов и называемой отношением (relation). Более распространенный синоним слова "отношение" - таблица (или "набор записей", или набор результатов - result set. Именно от этого и происходит термин "реляционные базы данных", а вовсе не от отношений между таблицами;

· все значения являются скалярами. Это значит, что для любой строки и столбца любого отношения существует одно и только одно значение;

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

Теперь - про формальную терминологию:

· отношение (relation ) - это вся структура целиком, набор записей (в обычном понимании - таблица).

· кортеж - это каждая строка, содержащая данные. Более распространенный, но менее формальный термин - запись.

· мощность - число кортежей в отношении (проще говоря, число записей);

· атрибут - это столбец в отношении;

· размерность - это число атрибутов в отношении (в данном случае - 3);

· каждое отношение можно разделить на две части - заголовок и тело . На простом языке заголовок отношения - это список столбцов, а тело - это сами записи (кортежи).

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

· тело отношения состоит из неупорядоченного набора кортежей (его число может быть любым - от 0 до бесконечно большого).

Мельникова 620000 Россия, Свердловская обл., г. Екатеринбург. +7 953 039 559 1 info@сайт

Реляционная база данных — это связанная информация, представленная в виде двумерных таблиц. Представьте себе адресную книгу. Она содержит множество строк, каждая из которых соответствует данному индивидууму. Для каждого из них в ней представлены некоторые независимые данные, например, имя, номер телефона, адрес. Представим такую адресную книгу в виде таблицы, содержащей строки и столбцы. Каждая строка (называемая также записью) соответствует определенному индивидууму, каждый столбец содержит значения соответствующего типа данных: имя, номер телефона и адрес, представленных в каждой строке. Адресная книга может выглядеть таким образом:

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

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

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

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

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

Порядок строк произволен

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

Рассмотрим вторую таблицу. Содержащуюся в ней информацию иногда удобно рассматривать упорядоченной по имени, иногда — в порядке возрастания или убывания баланса (Balance), а иногда — сгруппированной по доктору. Внушительное множество возможных порядков строк помешало бы пользователю проявить гибкость в работе с данными, поэтому строки предполагаются неупорядоченными. Именно по этой причине вы не можете просто сказать: «Меня интересует пятая строка таблицы». Независимо от порядка включения данных или какого-либо другого критерия, этой пятой строки не существует по определению. Итак, строки таблицы предполагаются расположенными в произвольном порядке.

Идентификация строк (первичный ключ)

По этой и ряду других причин, необходимо иметь столбец таблицы, который однозначно идентифицирует каждую строку. Обычно этот столбец содержит номер, например, приписанный каждому пациенту. Конечно, можно использовать для идентификации строк имя пациента, но ведь может случиться так, что имеется несколько пациентов с именем Mary Smith. В подобном случае нет простого способа их различить. Именно по этой причине обычно используются номера. Такой уникальный столбец (или их группа), используемый для идентификации каждой строки и обеспечивающий различимость всех строк, называется первичным ключом таблицы (primary key of the table).

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

Столбцы поименованы и пронумерованы

В отличие от строк, столбцы таблицы (также называемые полями (fields) упорядочены и поименованы. Следовательно, в нашей таблице, соответствующей адресной книге, можно сослаться на столбец «Address» как на «столбец номер три». Естественно, это означает, что каждый столбец данной таблицы должен иметь имя, отличное от других имен, для того, чтобы не возникло путаницы. Лучше всего, когда имена определяют содержимое поля. В этой книге мы будем использовать аббревиатуру для именования столбцов в простых таблицах, например: cname — для имени покупателя (customer name), odate — для даты поступления (order date). Предположим также, что таблица содержит единственный цифровой столбец, используемый как первичный ключ.

Таблицы 1.1, 1. 2, 1.3 образуют реляционную базу данных, которая достаточно мала для того, чтобы можно было понять ее смысл, но и достаточно сложна для того, чтобы иллюстрировать на ее примере важные понятия и практические выводы, связанные с применением SQL.

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

Например, поле snum в таблице Customers определяет, каким продавцом (salespeople) обслуживается конкретный покупатель (customer). Номер поля snum устанавливает связь с таблицей Salespeople, которая дает информацию об этом продавце (salespeople). Очевидно, что продавец, который обслуживает данного покупателя, существует, т.е. значение поля snum в таблице Customers присутствует также и в таблице Salespeople. В этом случае мы говорим, что система находится в состоянии ссылочной целостности (referential integrity).

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

Перед вами объяснение столбцов таблицы 1.1:

Таблица 1.2 содержит следующие столбцы:

И, наконец, столбцы таблицы 1.3.