Реляционная база данных — основные понятия. Как работает реляционная бд

Реляционная база данных - основные понятия

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

Действительно, в узком смысле слова, база данных - это некоторый набор данных, необходимых для работы (актуальные данные). Однако данные - это абстракция; никто никогда не видел "просто данные"; они не возникают и не существуют сами по себе. Данные суть отражение объектов реального мира. Пусть, например, требуется хранить сведения о деталях, поступивших на склад. Как объект реального мира - деталь - будет отображена в базе данных? Для того, чтобы ответить на этот вопрос, необходимо знать, какие признаки или стороны детали будут актуальны, необходимы для работы. Среди них могут быть название детали, ее вес, размеры, цвет, дата изготовления, материал, из которого она сделана и т.д. В традиционной терминологии объекты реального мира, сведения о которых хранятся в базе данных, называются сущностями - entities (пусть это слово не пугает читателя - это общепринятый термин), а их актуальные признаки - атрибутами (attributes).

Каждый признак конкретного объекта есть значение атрибута. Так, деталь "двигатель" имеет значение атрибута "вес", равное "50", что отражает тот факт, что данный двигатель весит 50 килограммов.

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

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

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

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

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

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

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

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

Реляционной считается такая база данных, в которой все данные представлены для пользователя в виде прямоугольных таблиц значений данных, и все операции над базой данных сводятся к манипуляциям с таблицами. Таблица состоит из строк и столбцов и имеет имя, уникальное внутри базы данных. Таблица отражает тип объекта реального мира (сущность), а каждая ее строка - конкретный объект. Так, таблица Деталь содержит сведения о всех деталях, хранящихся на складе, а ее строки являются наборами значений атрибутов конкретных деталей. Каждый столбец таблицы - это совокупность значений конкретного атрибута объекта. Так, столбец Материал представляет собой множество значений "Сталь", "Олово", "Цинк", "Никель" и т.д. В столбце Количество содержатся целые неотрицательные числа. Значения в столбце Вес - вещественные числа, равные весу детали в килограммах.

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

Каждый столбец имеет имя, которое обычно записывается в верхней части таблицы (Рис. 1 ). Оно должно быть уникальным в таблице, однако различные таблицы могут иметь столбцы с одинаковыми именами. Любая таблица должна иметь по крайней мере один столбец; столбцы расположены в таблице в соответствии с порядком следования их имен при ее создании. В отличие от столбцов, строки не имеют имен; порядок их следования в таблице не определен, а количество логически не ограничено.

Рисунок 1. Основные понятия базы данных.

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

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

Рисунок 2. Взаимосвязь таблиц базы данных.

Таблицы невозможно хранить и обрабатывать, если в базе данных отсутствуют "данные о данных", например, описатели таблиц, столбцов и т.д. Их называют обычно метаданными. Метаданные также представлены в табличной форме и хранятся в словаре данных (data dictionary).

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

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

Для того, чтобы гарантировать корректность и взаимную непротиворечивость данных, на базу данных накладываются некоторые ограничения, которые называют ограничениями целостности (data integrity constraints).

Существует несколько типов ограничений целостности. Требуется, например, чтобы значения в столбце таблицы выбирались только из соответствующего домена. На практике учитывают и более сложные ограничения целостности, например, целостность по ссылкам (referential integrity). Ее суть заключается в том, что внешний ключ не может быть указателем на несуществующую строку в таблице. Ограничения целостности реализуются с помощью специальных средств, о которых речь пойдет в Разд. Сервер базы данных .

Язык SQL

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

Появление и развития этого языка как средства описания доступа к базе данных связано с созданием теории реляционных баз данных. Прообраз языка SQL возник в 1970 году в рамках научно-исследовательского проекта System/R, работа над которым велась в лаборатории Санта-Тереза фирмы IBM. Ныне SQL - это стандарт интерфейса с реляционными СУБД. Популярность его настолько велика, что разработчики нереляционных СУБД (например, Adabas), снабжают свои системы SQL-интерейсом.

Язык SQL имеет официальный стандарт - ANSI/ISO. Большинство разработчиков СУБД придерживаются этого стандарта, однако часто расширяют его для реализации новых возможностей обработки данных. Новые механизмы управления данными, которые будут описаны в Разд. Сервер базы данных , могут быть использованы только через специальные операторы SQL, в общем случае не включенные в стандарт языка.

SQL не является языком программирования в традиционном представлении. На нем пишутся не программы, а запросы к базе данных. Поэтому SQL - декларативный язык. Это означает, что с его помощью можно сформулировать, что необходимо получить, но нельзя указать, как это следует сделать. В частности, в отличие от процедурных языков программирования (Си, Паскаль, Ада), в языке SQL отсутствуют такие операторы, как if-then-else, for, while и т.д.

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

Запрос на языке SQL состоит из одного или нескольких операторов, следующих один за другим и разделенных точкой с запятой. Ниже в таблице 1перечислены наиболее важные операторы, которые входят в стандарт ANSI/ISO SQL.

Таблица 1. Основные операторы языка SQL.

В запросах на языке SQL используются имена, которые однозначно идентифицируют объекты базы данных. В частности это - имя таблицы (Деталь), имя столбца (Название), а также имена других объектов в базе, которые относятся к дополнительным типам (например, имена процедур и правил), о которых речь пойдет в Разд. Сервер базы данных . Наряду с простыми, используются также сложные имена - например, квалификационное имя столбца (qualified column name) определяет имя столбца и имя таблицы, которой он принадлежит (Деталь.Вес). Для простоты в примерах имена будут записаны на русском языке, хотя на практике этого делать не рекомендуется.

Каждый столбец в любой таблице хранит данные определенных типов. Различают базовые типы данных - строки символов фиксированной длины, целые и вещественные числа, и дополнительные типы данных - строки символов переменной длины, денежные единицы, дату и время, логические данные (два значения - "ИСТИНА" и "ЛОЖЬ"). В языке SQL можно использовать числовые, строковые, символьные константы и константы типа "дата" и "время".

Рассмотрим несколько примеров.

Запрос "определить количество деталей на складе для всех типов деталей" реализуется следующим образом:

SELECT Название, Количество

FROM Деталь;

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

Запрос "какие детали, изготовленные из стали, хранятся на складе?", сформулированный на языке SQL, выглядит так:

FROM Деталь

WHERE Материал = "Сталь";

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

Запрос "определить название и количество деталей на складе, которые изготовлены из пластмассы и весят меньше пяти килограммов" будет записан следующим образом:

SELECT Название, Количество

FROM Деталь

WHERE Материал = "Пластмасса"

AND Вес < 5;

Результат запроса - таблица из двух столбцов - Название, Количество, которая содержит название и число деталей, изготовленных из пластмассы и весящих менее 5 кг. По сути, операция выборки является операцией образования сначала горизонтальной проекции (найти все строки таблицы Деталь, у которых Материал = "Пластмасса" и Вес < 5), а затем вертикальной проекции (извлечь Название и Количество из выбранных ранее строк).

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

Допустим, что сформулирован запрос к базе данных Склад:

SELECT Название Количество, Материал

FROM Деталь

WHERE Номер = "Т145-А8";

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

Если же был предварительно создан индекс по столбцу Номер таблицы Деталь, то время поиска в таблице будет сокращено до минимума. Индекс будет содержать значения из столбца Номер и ссылку на строку с этим значением в таблице Деталь. При выполнении запроса СУБД вначале найдет в индексе значение "Т145-А8" (и сделает это быстро, так как индекс упорядочен, а его строки невелики), а затем по ссылке в индексе определит физическое расположение искомой строки.

Индекс создается оператором SQL CREATE INDEX (СОЗДАТЬ ИНДЕКС). В данном примере оператор

CREATE UNIQUE INDEX Индекс детали

ON Деталь (Номер);

позволит создать индекс с именем "Индекс детали" по столбцу Номер таблицы Деталь.

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

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

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

Завершая обсуждение языка SQL, еще раз подчеркнем, что это - язык запросов. На нем нельзя написать сколько-нибудь сложную прикладную программу, которая работает с базой данных. Для этой цели в современных СУБД используется язык четвертого поколения (Forth Generation Language - 4GL), обладающий как основными возможностями процедурных языков третьего поколения (3GL), таких как Си, Паскаль, Ада, так и возможностью встроить в текст программы операторы SQL, а также средствами управления интерфейсом пользователя (меню, формами, вводом пользователя и т.д.). Сегодня язык 4GL - это один из фактических стандартов средств разработки приложений, работающих с базами данных.

Реляционные базы данных позволяют хранить информацию в нескольких «плоских» (двухмерных) таблицах, связанных между собой посредством совместно используемых полей данных, называемых ключами. Реляционные базы данных предоставляют более простой доступ к оперативно составляемым отчетам (обычно через 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-сайтами и реляционными базами данных дает конечным пользователям возможность добавлять новые записи и обновлять существующие, а также создавать отчеты для самых разных служб, таких как выполнение интерактивных торговых операций и доступ к интерактивным библиотечным каталогам.

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

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

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

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

Рис. 1. Названия объектов в таблице

Для работы с данными используются системы управления базами данных (СУБД). Основные функции СУБД:

Определение данных (описание структуры баз данных);

Обработка данных;

Управление данными.

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

Любая СУБД позволяет выполнять следующие операции с данными:

Добавление записей в таблицы;

Удаление записей из таблицы;

Обновление значений некоторых полей в одной или нескольких записях в таблицах БД;

Поиск одной или нескольких записей, удовлетворяющих заданному условию.

Для выполнения этих операций применяется механизм запросов. Результатом выполнения запросов является либо отобранное по определенным критериям множество записей, либо изменения в таблицах. Запросы к базе формируются на специально созданном для этого языке, который так и называется «язык структурированных запросов» (SQL - Structured Query Language).

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

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

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

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

Чаще всего стоимость 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)? В разных ситуациях некоторые способы объединения не работают.
• Распределение данных . Если данные отклонены по условию объединения (например, вы объединяете людей по фамилиям, но часто встречаются однофамильцы), то ни в коем случае нельзя использовать хэш-объединение. Иначе хэш-функция будет создавать корзины с очень плохим внутренним распределением.
• Нужно ли выполнять объединение в несколько процессов/потоков.

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. Можно не искать наиболее выгодное решение и применить более жёсткие правила для уменьшения числа возможных планов. Скажем, «если зависимость мала, используем объединение с помощью вложенных циклов, но никогда - объединение слиянием или хэш-объединение».

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

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)/

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

Не будем углубляться в подробности, но при хорошем моделировании сложности сортировки 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 раз.
• Из планов последнего цикла мы получаем наилучший.

В БД используются и такие эвристические алгоритмы, как симулированная нормализация (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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Диспетчер транзакций

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

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

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

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

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

• Атомарность позволяет быть уверенным, что какое бы событие не произошло в ходе Т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. Диспетчер логов

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

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

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

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

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

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

Большинство продуктов (в частности, 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 . Способ повтора операции.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

II. Сетевая модель

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

запись поле

иерархических и сетевых моделей внешних ключей

4. Реляционная модель данных

Реляционная БД

* Отношение

* Атрибут столбца (поля) таблицы.

* Тип данных

* Связь ключом.

* Объединение

Основными функциями РСУБД являются:

· Определение данных

· Обработка данных

· Управление данными

Microsoft Access

Окно БД в Access

Режимы работы с объектами

Кнопки для работы с объектами БД расположены на Панели инструментов окна БД:

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

Конструктор – обеспечивает переход к режиму настройки выбранного объекта.

Создать – позволяет приступить к созданию нового объекта выбранного типа.

7. Работа с таблицами

Чтобы создать таблицу, нужно перейти к списку таблиц и нажать кнопку Создать . Появится новое диалоговое окно Новая таблица :

Таблицу в Access можно создать несколькими способами:

· построить новую таблицу «с нуля», воспользовавшись Конструктором ;

· запустить Мастер таблиц – специальную программу, предлагающую создать таблицу в пошаговом режиме на базе типовых решений, имеющихся в Access;

· импортировать таблицу БД из файла какой-либо программы, например, FoxPro или Excel.

Задание имени поля

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

Определение типа данных

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

Ø Текстовый – для хранения обычного текста с максимальным количеством символов 255.

Ø Поле MEMO – для хранения больших объемов текста до 65 535 символов.

Ø Числовой – для хранения действительных чисел.

Ø Дата/время – для хранения календарных дат и текущего времени.

Ø Денежный – эти поля содержат денежные суммы.

Ø Счетчик – для определения уникального системного ключа таблицы. Обычно используется для порядковой нумерации записей. При добавлении в таблицу новой записи значение этого поля увеличивается на 1 (единицу). Значения в таких полях не обновляются.

Ø Логический – для хранения данных, принимающих значения: Да или Нет.

Ø Поле объекта OLE – для хранения объектов, созданных в других приложениях.

Описание свойств полей

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

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

Если тип данных – числовой, допустимы следующие значения свойства Размер поля :

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

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

Ø Число десятичных знаков – задает для числового и денежного типа данных число десятичных знаков после запятой.

Ø Маска ввода – определяет форму, в которой данные вводятся в поле (средство автоматизации ввода данных).

Ø Подпись – обозначение для поля, которое будет использоваться для отображения поля в таблице, форме или отчете. Если это значение не определено, в качестве подписи будет взято имя поля.

Ø Значение по умолчанию – стандартное значение, которое автоматически вводится в поле при формировании новой записи данных.

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

Ø Сообщение об ошибке – задает текст сообщения, выводимый на экран в случае нарушения условия на значение.

Ø Обязательное поле – определяет, может ли данное поле содержать значения Null (т.е. оставаться пустым), или нужно обязательно вводить в это поле данные.

Ø Индексированное поле – используется для операций поиска и сортировки записей по значению, хранящемуся в данном поле, а также для автоматического исключения дублирования записей. Поля типа MEMO , Объект OLE и Гиперссылка не могут индексироваться.

Определение ключевого поля

После задания характеристик всех полей следует выбрать, по крайней мере, одно ключевое поле. Как правило, в качестве ключевых полей указываются поля, которые имеют неповторяющиеся данные или создаются поля с типом данных Счетчик . В любом случае, поле ключа не должно содержать повторяющихся данных. Чтобы определить ключ, необходимо выделить нужное поле (или поля) и нажать кнопку Ключевое поле Правка . Слева от маркера появится изображение ключа.

Сохранение таблицы

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

Если выбирается ответ «Да », то Access создаст автоматически поле с именем «Код» и типом данных Счетчик , если «Нет », – то таблица будет создана без ключевого поля. В этом случае необходимо открыть созданную таблицу в режиме Конструктора и определить «вручную» ключевое поле.

Ввод данных

Чтобы перевести таблицу в режим ввода информации, нужно перейти в режим Таблицы . Поля заполняются последовательно. Переход от одного поля к другому удобно выполнять клавишей Tab (или комбинацией Shift+Tab – в обратном направлении). Если при проектировании таблицы для некоторых полей были предусмотрены значения по умолчанию, эти значения автоматически появятся в соответствующих полях. Записи в таблице можно перемещать, копировать и удалять теми же способами, что и в электронных таблицах, то есть сначала выделить строки, а потом выполнить необходимую операцию. Столбец можно выделить щелчком мыши по заголовку. Столбцы можно перемещать вправо и влево, пользуясь методом drag and drop (перетащить и бросить).

При необходимости можно вернуться в режим Конструктора . Это дает возможность что-либо подправить в структуре таблицы.

Сортировка данных в таблице

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

8. Создание связей между таблицами БД

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

Замечания.

Ø Оба связываемых поля должны иметь одинаковый тип данных .

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

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

Целостность данных

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

Эти правила включают:

Ø В подчиненной таблице нельзя вводить записи, которые не связаны с записью главной таблицы.

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

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

Каскадные операции

Целостность данных в связанных таблицах обеспечивают каскадные операции двух видов:

Ø операции каскадного обновления;

Ø операции каскадного удаления.

Эти операции можно включать и выключать путем установки соответствующих флажков: «Каскадное обновление связанных полей» и «Каскадное удаление связанных полей».

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

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

Удаление (изменение) связей

Ø Открыть окно Схема данных ;

Ø активизировать левой кнопкой мыши связь, которую необходимо удалить (изменить);

Ø правой кнопкой мыши вызвать контекстно-зависимое меню и выбрать команду Удалить (Изменить ) соответственно.

9. Типы отношений между таблицами

Существует три типа отношений между таблицами:

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

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

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

Если между таблицами имеются связи типа М:М, создается дополнительная таблица пересечений, с помощью которой связь М:М будет сведена к двум связям типа 1:М. Accеss не позволяет определить прямую связь М:М между двумя таблицами.

10. Формирование запросов

Запуск запроса

Для запуска запроса на исполнение из окна Конструктора надо на панели инструментов нажать кнопку «Запуск » ! или выполнить команду Запрос/Запуск . Результаты выборки данных по запросу выводятся на экран в режиме таблицы.

Формирование Условий отбора

Список операторов используемых при задании выражений следующий:

Ø операторысравнения:

= (равно)

<> (не равно)

> (больше)

>= (не меньше)

< (меньше)

<= (не больше)

BETWEEN – позволяет задать диапазон значений. Синтаксис: Between «Выражение»And «Выражение» (например: BETWEEN 10 And 20 означает тоже, что и логическое выражение>= 10 AND <= 20).

IN – позволяет задавать используемый для сравнения список значений (операндом является список, заключенный в круглые скобки). Например: IN ("Брест", "Минск", "Гродно") означает тоже самое, что и логическое выражение "Брест" OR "Минск" OR "Гродно".

Ø логические операторы:

АND (например: >=10 AND <=20)

OR (например: <50 OR >100)

NOT (например: Is Not Null – поле, содержащее какое-либо значение).

Ø операторLIKE – проверяет соответствие текстового или Memo поля по заданному шаблону символов.

Таблица символов шаблона

Примеры использования оператора Like :

LIKE "С *" – строки, начинающиеся с символа С;

LIKE "[ A - Z ] #" – любой символ от А до Z и цифра;

LIKE "[! 0 - 9 ABC] * # #" – строки, начинающиеся с любого символа кроме цифры или букв А, В, С и заканчивающиеся на 2 цифры;

Сложные критерии выборки

Часто приходится выбирать записи по условию, которое задается для нескольких полей таблицы или по нескольким условиям для одного поля. В этом случае применяются «И-запросы» (выбор записей только при условии выполнения всех условий) и«ИЛИ-запросы» (выбор записей при выполнении хотя бы одного из условий).

При задании «ИЛИ-запроса » каждое условие выборки должно размещаться на отдельной строке Бланка запроса .

При задании «И-запроса » каждое условие выборки должно размещаться на одной строке, но в разных полях Бланка запроса .

Эти операции могут быть заданы явно с помощью операторовOR иAND соответственно.

Функции Iif() и Format()

Функция IIf(условие; еслиИстина; еслиЛожь) – возвращает один из двух аргументов в зависимости от результата вычисления выражения.

Функция Format(выражение; инструкция форматирования) – возвращает строку, содержащую выражение, отформатированное согласно инструкциям форматирования.

Для выражений даты/времени можно применять следующие символы в инструкции форматирования:

I. Иерархическая модель

II. Сетевая модель

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

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

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

4. Реляционная модель данных

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

Реляционная модель данных была предложена Е. Коддом, известным американским специалистом в области баз данных. Основные концепции этой модели были впервые опубликованы в 1970 г. Будучи математиком по образованию, Кодд предложил использовать для обработки данных аппарат теории множеств (объединение, пересечение, разность, декартово произведение). Он показал, что любое представление данных сводится к совокупности двумерных таблиц особого вида, известного в математике как отношение (по-английски – relation, отсюда и название – реляционные базы данных).

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

Базовые понятия реляционных баз данных (РБД)

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

* Атрибут – определенная часть информации о некотором объекте – например, адрес клиента или зарплата сотрудника. Атрибут обычно хранится в виде столбца (поля) таблицы.

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

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

* Объединение – процесс объединения таблиц или запросов на основе совпадающих значений определенных атрибутов.

Правила (нормализации) построения реляционной БД

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

1. Каждое поле любой таблицы должно быть уникальным.

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

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

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

5. Системы управления базами данных (СУБД)

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

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

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

Реляционная система управления базами данных (РСУБД)

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

Основными функциями РСУБД являются:

· Определение данных – какая информация будет храниться, задать структуру БД и их тип.

· Обработка данных – можно выбирать любые поля, сортировать и фильтровать данные. Можно объединять данные и подводить итоги.

· Управление данными – корректировать и добавлять данные.

6. Общая характеристика СУБД ACCESS

Microsoft Access – это функционально полная реляционная СУБД, в которой предусмотрены все необходимые средства для определения и обработки данных, а также для управления ими при работе с большими объемами информации. Различные ее версии входят в состав программного пакета MS Office и работают в среде Windows (3.11/95/98/2000/XP).

Окно БД в Access

После создания нового файла БД или открытия существующего в рабочей области окна Access появляется окно базы данных: