1.       1.           Понятие БД   1

2.       2.           Понятие и назначение СУБД   2

3.       3.           Основные модели данных  3

4.       4.           Структура базы данных  4

5.       5.           Технология «клиент-сервер»  5

6.       6.           Физическая организация хранения данных  6

7.       7.           Реляционная модель данных. Основные понятия и определения. 7

8.       8.           Реляционная модель данных. Связь отношений. 7

9.       9.           SQL. Общие сведения  9

10.   10.         SQL. Типы данных  10

11.   11.         SQL. Операторы создания схемы базы данных  10

12.   12.         SQL. Создание и удаление таблиц  10

13.   13.         SQL. Модификация таблицы: 10

14.   14.         SQL. Операторы создания и удаления индексов  10

15.   15.         SQL. Команды модификации данных. 10

16.   16.         SQL. Выборка данных  10

17.   17.         SQL. Выборка из нескольких таблиц  10

18.   18.         SQL. Вычисления внутри SELECT  10

19.   19.         SQL. Группировка данных  10

20.   20.         SQL. Сортировка данных  10

21.   21.         SQL. Операция объединения  10

22.   22.         SQL. Использование представлений  10

23.   23.         SQL. Хранимые процедуры   10

24.   24.         SQL. Триггеры   10

25.   25.         Проектирование баз данных. Цели и этапы. 10

26.   26.         Инфологическое проектирование. 10

27.   27.         Походы к инфологическому проектированию. 10

28.   28.         Использование метода «сущность-связь» при инфологическом проектировании. 10

29.   29.         Объединение локальных областей  10

30.   30.         Определение требований к операционной обстановке  10

31.   31.         Выбор СУБД и инструментальных программных средств  10

32.   32.         Логическое и физическое проектирование БД. 10

33.   33.         Автоматизация проектирования БД   10

34.   34.         Особенности проектирования реляционных БД   10

35.   35.         Аномалии модификации данных  10

36.   36.         Нормализация отношений  10

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

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

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

40.   40.         Четвертая нормальная форма (4НФ). 10

41.   41.         Способы доступа к записям   10

42.   42.         Индексирование данных  10

43.   43.         Способы организации индексов  10

44.   44.         Многоуровневые индексы на основе В-дерева  10

45.   45.         Использование индексов  10

46.   46.         Хеширование в базах данных  10

47.   47.         Методы хеширования  10

48.   48.         Разрешение коллизий  10

49.   49.         Использование хеширования  10

50.   50.         Кластеризация данных. Принцип организации кластеров  10

51.   51.         Использование кластеров  10

52.   52.         Транзакции. Общие сведения  10

53.   53.         Взаимовлияние транзакций  10

54.   54.         Блокировки  10

55.  Понятие БД

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

- добавление новой информации в существующие файлы БД;

- добавление новых пустых файлов в БД;

- изменение (модификация) информации в существующих файлах БД;

- поиск информации в БД;

- удаление информации из существующих файлов БД;

- удаление файлов из БД.

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

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

56.  Понятие и назначение СУБД

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

Если говорить более детально, то к функциям СУБД относят следующие:

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

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

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

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

57.  Основные модели данных

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

- модели, основанные на инвертированных списках;

- иерархические модели данных;

- сетевые модели данных.

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

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

В таких БД поддерживаются следующие операторы манипулирования данными:

- найти дерево БД по заданному признаку;

- перейти от одного дерева к другому;

- перейти к записи внутри дерева или в порядке обхода иерархии (сверху вниз, слева направо);

- вставить новую запись в указанную позицию;

- удалить текущую запись.

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

- найти запись по заданному признаку;

- перейти от предка к потомку по указанной связи;

- перейти от потомка к предку по некоторой связи:

- создать новую запись или удалить существующую;

- модифицировать заданную «запись;

- включить в связь или исключить из связи;

- переставить в другую связь.

58.  Структура базы данных

Понятия архитектуры и структуры является одним из важнейших в теории БД и служит основой для понимания возможностей современных СУБД. Различают три уровня архитектуры БД:

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

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

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

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

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

59.  Технология «клиент-сервер»

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

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

Таким образом, информационная система, построенная по принципу клиент/сервер, состоит обычно из трех основных компонентов:

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

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

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

60.  Физическая организация хранения данных

Файлы БД (страницы, запись, ключ, область хранения).

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

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

 

Хранимая запись. Каждой записи, определенной в схеме БД на внутреннем уровне, соответствует хранимая запись. Она состоит из двух частей — служебной и информационной.

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

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

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

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

Обновление БД (удаление, добавление, корректировка записей, обновление групповых отношений)

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

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

Удаление записей из базы данных. Существует две разновидности удаления записей: логическое и физическое.

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

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

61.  Реляционная модель данных. Основные понятия и определения.

62.  Реляционная модель данных. Связь отношений.

Структура данных. В реляционной модели достигается гораздо более высокий уровень абстракции данных, чем в иерархической или сетевой. В упомянутой статье Е.Ф.Кодда утверждается, что "реляционная модель предоставляет средства описания данных на основе только их естественной структуры, т.е. без потребности введения какой-либо дополнительной структуры для целей машинного представления". Другими словами, представление данных не зависит от способа их физической организации. Это обеспечивается за счет использования математической теории отношений (само название "реляционная" происходит от английского relation - "отношение").

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

Определения:

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

Пример: если даны два множества A (a1,a2,a3) и B (b1,b2), их декартово произведение будет иметь вид С=A*B (a1*b1, a2*b1, a3*b1, a1*b2, a2*b2, a3*b2)

Отношение: Отношением R, определенным на множествах называется подмножество декартова произведения . При этом:

множества называются доменами отношения

элементы декартова произведения называются кортежами

число n определяет степень отношения ( n=1 - унарное, n=2 - бинарное, ..., n-арное)

количество кортежей называется мощностью отношения

Пример: на множестве С из предыдущего примера могут быть определены отношения R1 (a1*b1, a3*b2) или R2 (a1*b1, a2*b1, a1*b2)

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

Рис.4.1 Основные компоненты реляционного отношения.

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

Несколько атрибутов одного отношения и даже атрибуты разных отношений могут быть определены на одном и том же домене. В примере, показанном на рис.4.1 атрибуты "Оклад" и "Премия" определены на домене "Деньги". Поэтому, понятие домена имеет семантическую нагрузку: данные можно считать сравнимыми только тогда, когда они относятся к одному домену. Таким образом, в рассматриваемом нами примере сравнение атрибутов "Табельный номер" и "Оклад" является семантически некорректным, хотя они и содержат данные одного типа.

Именнованное множество пар "имя атрибута - имя домена" называется схемой отношения. Мощность этого множества - называют степенью или "арностью" отношения. Набор именованных схем отношений представляет из себя схему базы данных.

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

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

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

Рис.4.2. База данных о подразделениях и сотрудниках предприятия.

Например, связь между отношениями ОТДЕЛ и СОТРУДНИК создается путем копирования первичного ключа "Номер_отдела" из первого отношения во второе. Таким образом:

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

из таблицы ОТДЕЛ установить значение атрибута "Номер_отдела", соответствующее данному "Наименованию_отдела"

выбрать из таблицы СОТРУДНИК все записи, значение атрибута "Номер_отдела" которых равно полученному на предыдушем шаге.

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

определяем "Номер_отдела" из таблицы СОТРУДНИК

по полученному значению находим запись в таблице ОТДЕЛ.

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

63.  SQL. Общие сведения

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

Язык SQL (эта аббревиатура должна произноситься как "сикуель", однако все чаще говорят "эс-ку-эль") в настоящее время является промышленным стандартом, который в большей или меньшей степени поддерживает любая СУБД, претендующая на звание "реляционной". В то же время SQL подвергается суровой критике как раз за недостаточное соответствие реляционным принципам (см. например, статью Х. Дарвина и К.Дейта Третий манифест, опубликованную в журнале СУБД N 1 за 1996 год).

Из истории SQL: В начале 70-х годов в компании IBM была разработана экспериментальная СУБД System R на основе языка SEQUEL (Structured English Qeury Language - структурированный английский язык запросов), который можно считать непосредственным предшественником SQL. Целью разработки было создание простого непроцедурного языка, которым мог воспользоваться любой пользователь, даже не имеющий навыков программирования. В 1981 году IBM объявила о своем первом, основанном на SQL программном продукте, SQL/DS. Чуть позже к ней присоединились Oracle и другие производители. Первый стандарт языка SQL был принят Американским национальным институтом стандартизации (ANSI) в 1987 (так называемый SQL level /уровень/ 1) и несколько уточнен в 1989 году (SQL level 2). Дальнейшее развитие языка поставщиками СУБД потребовало принятия в 1992 нового расширенного стандарта (ANSI SQL-92 или просто SQL-2). В настоящее время ведется работа по подготовке третьего стандарта SQL, который должен включать элементы объекто-ориентрованного доступа к данным.

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

В SQL определены два подмножества языка:

SQL-DDL (Data Definition Language) - язык определения структур и ограничений целостности баз данных. Сюда относятся команды создания и удаления баз данных; создания, изменения и удаления таблиц; управления пользователями и т.д.

SQL-DML (Data Manipulation Language) - язык манипулирования данными: добавление, изменение, удаление и извлечение данных, управления транзакциями

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

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

64.  SQL. Типы данных

Символьные типы данных - содержат буквы, цифры и специальные символы.

CHAR или CHAR(n) -символьные строки фиксированной длины. Длина строки определяется параметром n. CHAR без параметра соответсвует CHAR(1). Для хранения таких данных всегда отводится n байт вне зависимости от реальной длины строки.

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

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

INTEGER или INT- целое, для хранения которого отводится, как правило, 4 байта. (Замечание: число байт, отводимое для хранения того или иного числового типа данных зависит от используемой СУБД и аппаратной платформы, здесь приводятся наиболее "типичные" значения) Интервал значений от - 2147483647 до + 2147483648

SMALLINT - короткое целое (2 байта), интервал значений от - 32767 до +32768

Вещественные типы данных - описывают числа с дробной частью.

FLOAT и SMALLFLOAT - числа с плавающей точкой (для хранения отводится обычно 8 и 4 байта соответсвенно).

DECIMAL(p) - тип данных аналогичный FLOAT с числом значащих цифр p.

DECIMAL(p,n) - аналогично предыдущему, p - общее количество десятичных цифр, n - количество цифр после десятичной запятой.

Денежные типы данных - описывают, естественно, денежные величины. Если в ваша система такого типа данных не поддерживает, то используйте DECIMAL(p,n).

MONEY(p,n) - все аналогично типу DECIMAL(p,n). Вводится только потому, что некоторые СУБД предусматривают для него специальные методы форматирования.

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

DATE - тип данных для хранения даты.

TIME - тип данных для хранения времени.

INTERVAL - тип данных для хранения верменного интервала.

DATETIME - тип данных для хранения моментов времени (год + месяц + день + часы + минуты + секунды + доли секунд).

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

BINARY

BYTE

BLOB

Последовательные типы данных - используются для представления возрастающих числовых последовательностей.

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

65.  SQL. Операторы создания схемы базы данных

При описании команд предполагается, что:

текст, набранный строчными буквами (например, CREATE TABLE) является обязательным

текст, набранный прописными буквами и заключенный в угловые скобки (например, <имя_базы_данных>) обозначает переменную, вводимую пользователем

в квадратные скобки (например, [NOT NULL]) заключается необязательная часть команды

взаимоисключающие элементы команды разделяются вертикальной чертой (например, [UNIQUE | PRIMARY KEY]).

Операторы базы данных

66.  SQL. Создание и удаление таблиц

Создание таблицы:

   CREATE TABLE <имя_таблицы>

        (<имя_столбца> <тип_столбца>

                          [NOT NULL]

                          [UNIQUE | PRIMARY KEY]

                          [REFERENCES <имя_мастер_таблицы> [<имя_столбца>]] , ...)

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

NOT NULL - в этом случае элементы столбца всегда должны иметь определенное значение (не NULL)

один из взаимоисключающих параметров UNIQUE - значение каждого элемента столбца должно быть уникальным или PRIMARY KEY - столбец является первичным ключом.

REFERNECES <имя_мастер_таблицы> [<имя_столбца>] - эта конструкция определяет, что данный столбец является внешним ключом и указывает на ключ какой мастер_таблицы он ссылается.

Контроль за выполнением указанных условий осуществляет СУБД.

Пример: создание базы данных publications:

   CREATE DATABASE publications;

 

   CREATE TABLE authors (au_id INT PRIMARY KEY,

                         author VARCHAR(25) NOT NULL);

   CREATE TABLE publishers (pub_id INT PRIMARY KEY,

                            publisher VARCHAR(255) NOT NULL,url VARCHAR(255));

   CREATE TABLE titles (title_id INT PRIMARY KEY,

                        title VARCHAR(255) NOT NULL,

                        yearpub INT,

                        pub_id INT REFERENCES publishers(pub_id));

   CREATE TABLE titleautors (au_id INT REFERENCES authors(au_id),

                             title_id INT REFERENCES titles(title_id));

   CREATE TABLE wwwsites (site_id INT PRIMARY KEY,

                          site VARCHAR(255) NOT NULL,

                          url VARCHAR(255));

   CREATE TABLE wwwsiteauthors (au_id INT REFERENCES authors(au_id),

                                site_id INT REFERENCES wwwsites(site_id));

67.  SQL. Модификация таблицы:

Добавить столбцы	ALTER TABLE <имя_таблицы> ADD (<имя_столбца> <тип_столбца> [NOT NULL] [UNIQUE | PRIMARY KEY] [REFERENCES <имя_мастер_таблицы> [<имя_столбца>]],...)
Удалить столбцы	ALTER TABLE <имя_таблицы> DROP (<имя_столбца>,...)
Модификация типа столбцов	ALTER TABLE <имя_таблицы> MODIFY (<имя_столбца> <тип_столбца> [NOT NULL] [UNIQUE | PRIMARY KEY] [REFERENCES <имя_мастер_таблицы> <имя_столбца>]],...)

68.  SQL. Операторы создания и удаления индексов

Создание индекса:

CREATE [UNIQUE] INDEX <имя_индекса> ON <имя_таблицы> (<имя_столбца>,...)

Эта команда создает индекс с заданным именем для таблицы <имя_таблицы> по столбцам, входящим в список, указанный в скобках. Индекс часто представляет из себя структуру типа B-дерева (см. параграф 1.2), но могут использоваться и другие структуры. Создание индексов значительно ускоряет работу с таблицами. В случае указания необязательного параметра UNIQUE СУБД будет проверять каждое значение индекса на уникальность.

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

CREATE INDEX au_names ON authors (author);

Создание индексов для первичных ключей:

CREATE INDEX au_index ON authors (au_id);

CREATE INDEX title_index ON titles (title_id);

CREATE INDEX pub_index ON publishers (pub_id);

CREATE INDEX site_index ON wwwsites (site_id);

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

Удаление индекса:

69.  SQL. Команды модификации данных.

К этой группе относятся операторы добавления, изменения и удаления записей.

Добавить новую запись в таблицу:

INSERT INTO <имя_таблицы> [ (<имя_столбца>,<имя_столбца>,...) ]

                                VALUES (<значение>,<значение>,..)

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

INSERT INTO publishers VALUES (16,"Microsoft Press","http://www.microsoft.com");

Пример с указанием списка столбцов:

INSERT INTO publishers (publisher,pub_id) 

VALUES ("Super Computer Publishing",17);

Модификация записей:

UPDATE <имя_таблицы> SET <имя_столбца>=<значение>,... [WHERE <условие>]

Если задано ключевое слово WHERE и условие, то команда UPDATE применяется только к тем записям, для которых оно выполняется. Если условие не задано, UPDATE применяется ко всем записям. Пример:

     UPDATE publishers SET url="http://www.superpub.com" WHERE pub_id=17;

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

операции сравнения: > , < , >= , <= , = , <> , != . В SQL эти операции могут применяться не только к числовым значениям, но и к строкам ( "<" означает раньше, а ">" позже в алфавитном порядке) и датам ( "<" раньше и ">" позже в хронологическом порядке).

оперции проверки поля на значение NULL: IS NULL, IS NOT NULL

операции проверки на вхождение в диапазон: BETWEEN и NOT BETWEEN.

операции проверки на вхождение в список: IN и NOT IN

операции проверки на вхождение подстроки: LIKE и NOT LIKE

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

Подробно все эти ключевые слова будут описаны и проиллюстрированы в параграфе, посвященном оператору SELECT. Здесь мы ограничимся приведением несложного примера:

     UPDATE publishers SET url="url not defined" WHERE url IS NULL;

Эта команда находит в таблице publishers все неопределенные значения столбца url и заменяет их строкой "url not defined".

Удаление записей

DELETE FROM <имя_таблицы> [ WHERE <условие> ]

Удаляются все записи, удовлетворяющие указанному условию. Если ключевое слово WHERE и условие отстутствуют, из таблицы удаляются все записи. Пример:

    DELETE FROM publishers WHERE publisher = "Super Computer Publishing";

70.  SQL. Выборка данных

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

SELECT [ALL | DISTINCT] <список_выбора>

FROM <имя_таблицы>, ... [ WHERE <условие> ]

           [ GROUP BY <имя_столбца>,... ]

              [ HAVING <условие> ]

           [ORDER BY <имя_столбца> [ASC | DESC],... ]

Порядок предложений в операторе SELECT должен строго соблюдаться (например, GROUP BY должно всегда предшествовать ORDER BY), иначе это приведет к появлению ошибок.

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

Этот оператор всегда начинается с ключевого слова SELECT. В кострукции <список_выбора> определяется столбец или столбцы, включаемые в результат. Он может состоять из имен одного или нескольких столбцов, или из одного символа * (звездочка), определяющего все столбцы. Элементы списка разделяются запятыми.

Пример: получить список всех авторов

        SELECT author FROM authors;

получить список всех полей таблицы authors:

        SELECT * FROM authors;

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

        SELECT title FROM titles WHERE yearpub > 1996;

Допустим теперь, что нам надо найти все публикации за интервал 1995 - 1997 гг. Это условие можно записать в виде:

        SELECT title FROM titles WHERE yearpub>=1995 AND yearpub<=1997;

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

        SELECT title FROM titles WHERE yearpub BETWEEN 1995 AND 1997;

При использовании конструкции NOT BETWEEN находятся все строки, не входящие в указанный диапазон.

Еще один вариант этой команды можно построить с помощью логической операции проверки на вхождение в список:

SELECT title FROM titles WHERE yearpub IN (1995,1996,1997);

Здесь мы задали в явном виде список интересующих нас значений. Конструкция NOT IN позволяет найти строки, не удовлетворяющие условиям, перечисленным в списке.

Наиболее полно преимущества ключевого слова IN проявляются во вложенных запросах, также называемых подзапросами. Предположим, нам нужно найти все издания, выпущенные компанией "Oracle Press". Наименования издательских компаний содержатся в таблице publishers, названия книг в таблице titles. Ключевое слово NOT IN позволяет объединить обе таблицы (без получения общего отношения) и извлечь при этом нужную информацию:

  SELECT title FROM titles WHERE pub_id IN

     (SELECT pub_id FROM publishers WHERE publisher='Oracle Press');

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

Некоторые задачи нельзя решить с использованием только операторов сравнения. Например, мы хоти найти web-site издательтва "Wiley", но не знаем его точного наименования. Для решения этой задачи предназначено ключевое слово LIKE, его синтаксис имеет вид:

   WHERE <имя_столбца> LIKE <образец> [ ESCAPE <ключевой_символ> ]

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

% (знак процента) - заменяет любое количество символов

_ (подчеркивание) - заменяет одиночный символ.

Попробуем найти искомый web-site:

SELECT publiser, url FROM publishers WHERE publisher LIKE '%Wiley%';

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

       SELECT title FROM titles WHERE title LIKE 'SQL%';

В том случае, когда надо найти значение, которое само содержит один из символов шаблона, используют ключевое слово ESCAPE и <ключевой_символ>. Литерал, следующий в шаблоне после ключевого символа, рассматривается как обычный символ, все последующие символы имеют обычное значение. Например, нам надо найти ссылку на web-страницу, о которой известно, что в ее url содержится подстрока "my_works":

      SELECT site, url FROM wwwsites WHERE url LIKE '%my@_works%' ESCAPE '@';

71.  SQL. Выборка из нескольких таблиц

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

|название_книги | год_выпуска | издательство   |

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

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

    SELECT titles.title,titles.yearpub,publishers.publisher

        FROM titles,publishers

        WHERE titles.pub_id=publishers.pub_id;

А вот пример, где одновременно задаются условия и слияния, и выборки (результат предыдущего запроса ограничивается изданиями после 1996 года):

    SELECT titles.title,titles.yearpub,publishers.publisher

        FROM titles,publishers

        WHERE titles.pub_id=publishers.pub_id AND

              titles.yearpub>1996;

Следует обратить внимание на то, что когда в разных таблицах присутствуют одноименные поля, то для устранения неоднозначности перед именем поля указывается имя таблицы и знак "." (точка). (Хорошее правило: имя таблицы указывать всегда!)

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

 SELECT authors.author,titles.title,titles.yearpub,publishers.publisher

   FROM titles,publishers,titleauthors

   WHERE titleauthors.au_id=authors.au_id AND

         titleauthors.title_id=titles.title_id AND

         titles.pub_id=publishers.pub_id AND

72.  SQL. Вычисления внутри SELECT

SQL позволяет выполнять различные арифметические операции над столбцами результирующего отношения. В конструкции <список_выбора> можно использовать константы, функции и их комбинации с арифметическими операциями и скобками. Например, чтобы узнать сколько лет прошло с 1992 года (год принятия стандарта SQL-92) до публикации той или иной книги можно выполнить команду:

     SELECT title, yearpub-1992 FROM titles WHERE yearpub > 1992;

В арифметических вражения допускаются операции сложения (+), вычитания (-), деления (/), умножения (*), а также различные функции (COS, SIN, ABS - абсолютное значение и т.д.). Также в запрос можно добавить строковую константу:

     SELECT 'the title of the book is', title, yearpub-1992 

            FROM titles WHERE yearpub > 1992;

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

AVG(<имя поля>) - среднее по всем значениям данного поля

COUNT(<имя поля>) или COUNT (*) - число записей

MAX(<имя поля>) - максимальное из всех значений данного поля

MIN(<имя поля>) - минимальное из всех значений данного поля

SUM(<имя поля>) - сумма всех значений данного поля

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

           SELECT MIN(yearpub) FROM titles;

подсчитать количество книг в нашей базе данных:

           SELECT COUNT(*) FROM titles;

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

73.  SQL. Группировка данных

Группировка данных в операторе SELECT осуществляется с помощью ключевого слова GROUP BY и ключевого слова HAVING, с помощью которого задаются условия разбиения записей на группы.

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

      SELECT publishers.publisher, count(titles.title)

          FROM titles,publishers

          WHERE titles.pub_id=publishers.pub_id

          GROUP BY publisher;

Kлючевое слово HAVING работает следующим образом: сначала GROUP BY разбивает строки на группы, затем на полученные наборы накладываются условия HAVING. Например, устраним из предыдущего запроса те издательства, которые имеют только одну книгу:

      SELECT publishers.publisher, count(titles.title)

         FROM titles,publishers

         WHERE titles.pub_id=publishers.pub_id

         GROUP BY publisher

           HAVING COUNT(*)>1;

Другой вариант использования HAVING - включить в результат только те издательтва, название которых оканчивается на подстроку "Press":

    SELECT publishers.publisher, count(titles.title)

         FROM titles,publishers

         WHERE titles.pub_id=publishers.pub_id

         GROUP BY publisher

            HAVING publisher LIKE '%Press';

74.  SQL. Сортировка данных

Для сортировки данных, получаемых при помощи оператора SELECT служит ключевое слово ORDER BY. С его помощью можно сортировать результаты по любому столбцу или выражению, указанному в <списке_выбора>. Данные могут быть упорядочены как по возрастанию, так и по убыванию. Пример: сортировать список авторов по алфавиту:

SELECT author FROM authors ORDER BY author;

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

 

 SELECT authors.author,titles.title,titles.yearpub,publishers.publisher

       FROM authors,titles,publishers,titleauthors

       WHERE titleauthors.au_id=authors.au_id AND

             titleauthors.title_id=titles.title_id AND

              titles.pub_id=publishers.pub_id 

       ORDER BY authors.author ASC, titles.yearpub DESC;

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

В SQL предусмотрена возможность выполнения операции реляционной алгебры "ОБЪЕДИНЕНИЕ" (UNION) над отношениями, являющимися результатами оператора SELECT. Естественно, эти отношения должны быть определены по одной схеме.Пример: получить все Интеренет-ссылки, хранимые в базе данных publications. Эти ссылки хранятся в таблицах publishers и wwwsites. Для того, чтобы получить их в одной таблице, мы должны построить следующие запрос:

       SELECT publisher,url FROM publishers

       UNION

76.  SQL. Использование представлений

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

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

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

Представление определяется с помощью команды

      CREATE VIEW <имя_представления> [<имя_столбца>,...]

             AS <запрос>

При этом должны соблюдаться следующие ограничения:

представление должно базироваться на единcтвенном запросе (UNION не допустимо)

выходные данные запроса, формирующего представление, должны быть не упорядочены (ORDER BY не допустимо)

Создадим представление, хранящее информацию об авторах, их книгах и издателях этих книг:

 

 CREATE VIEW books AS

 SELECT authors.author,titles.title,titles.yearpub,publishers.publisher

   FROM authors,titles,publishers,titleauthors

   WHERE titleauthors.au_id=authors.au_id AND

         titleauthors.title_id=titles.title_id AND

         titles.pub_id=publishers.pub_id

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

   SELECT titles FROM books WHERE author LIKE '%Date'

   SELECT author,count(title) FROM books GROUP BY author

(Права пользователей на доступ в представлениям назначаются также с помощью команд GRANT / REVOKE.)

Из приведенного выше примера достаточно ясен смысл использования представлений. Если запросы типа "выбрать все книги данного автора с указанием издательств" выполняются достаточно часто, то создание представляемой таблицы books значительно сократит накладные расходы на выполнение соединеия четырех базовых таблиц authors, titles, publishers и titleauthors. Кроме того, в представлении может быть представлена информация, явно не хранимая ни в одной из базовых таблиц. Например, один из столбцов представления может быть вычисляемым:

      CREATE VIEW amount (publisher, books_count) AS

      SELECT publishers.publisher, count(titles.title)

          FROM titles,publishers

          WHERE titles.pub_id=publishers.pub_id

          GROUP BY publisher;

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

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

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

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

Удаление представления производится с помощью оператора:

77.  SQL. Хранимые процедуры

Практический опыт создания приложений обработки данных показывает, что ряд операций над данными, реализующих общую для всех пользователей логику и не связанных с пользовательским интерфейсом, целесообразно вынести на сервер. Однако, для написания процедур, реализующих эти операции стандартных возможностей SQL не достаточно, поскольку здесь необходимы операторы обработки ветвлений, циклов и т.д. Поэтому многие поставщики СУБД предлагают собственные процедурные расширения SQL (PL/SQL компании Oracle и т.д.). Эти расширения содержат логические операторы (IF ... THEN ... ELSE), операторы перехода по условию (SWITCH ... CASE ...), операторы циклов (FOR, WHILE, UNTIL) и операторы предачи управления в процедуры (CALL, RETURN). С помощью этих средств создаются функциональные модули, которые хранятся на сервере вместе с базой данных. Обычно такие модули называют хранимые процедуры. Они могут быть вызваны с передачей параметров любым пользователем, имеющим на то соотвествующие права. В некоторых системах хранимые процедуры могут быть реализованы и в виде внешних по отношению к СУБД модулей на языках общего назначения, таких как C или Pascal. Пример для СУБД PostgreSQL:

 

          CREATE FUNCTION <имя_функции> ([<тип_параметра1>,...<тип_параметра2>])

              RETURNS <возвращаемые_типы>

              AS [ <SQL_оператор> | <имя_объектного_модуля> ]

              LANGUAGE 'SQL' | 'C' | 'internal'

78.  SQL. Триггеры

Для каждой таблицы может быть назначена хранимая процедура без параметров, которая вызывается при выполнении оператора модификации этой таблицы (INSERT, UPDATE, DELETE). Такие хранимые процедуры получили название триггеров. Триггеры выполняются автоматически, независимо от того, что именно является причиной модификации данных - действия человека оператора или прикладной программы. "Усредненный" синтаксис оператора создания триггера:

           CREATE TRIGGER <имя_триггера>

                    ON <имя_таблицы>

                    FOR { INSERT | UPDATE | DELETE }

                         [, INSERT | UPDATE | DELETE ] ...

                    AS <SQL_оператор>

79.  Проектирование баз данных. Цели и этапы.

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

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

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

1. Корректность схемы БД, т.е. база должна быть гомоморфным образом моделируемой ПО, где каждому объекту ПО соответствуют данные в памяти ЭВМ, а каждому процессу – адекватные процедуры обработки данных.

2. Обеспечение ограничений (на объёмы внешней и оперативной памяти и другие ресурсы вычислительной системы).

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

4. Защита данных (от сбоев и несанкционированного доступа).

5. Простота и удобство эксплуатации.

6. Гибкость, т.е. возможность развития и адаптации к изменениям ПО и/или требований пользователей.

Удовлетворение первых 4-х требований обязательно для принятия проекта.

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

Процесс проектирования БД включает в себя следующие этапы:

1. Информационно-логическое (инфологическое) проектирование.

2. Определение требований к операционной обстановке, в которой будет функционировать информационная система.

3. Выбор СУБД и других инструментальных программных средств.

4. Логическое проектирование БД.

80.  Инфологическое проектирование.

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

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

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

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

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

используемых методов анализа предметной области;

правил именования и обозначения объектов ПО, атрибутов и связей;

содержания и формата создаваемых ими документов.

Примечание. В тексте данного пособия используются следующие обозначения:

Имя отношения выделяется курсивом и подчеркиванием и пишется прописными буквами, например:      СОТРУДНИКИ.

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

Ключевые атрибуты отношения выделяются полужирным шрифтом, например:     Табельный номер.

81.  Походы к инфологическому проектированию.

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

1. Функциональный подход к проектированию БД.

Этот метод является наиболее распространённым. Он реализует принцип "от задач" и применяется в том случае, когда известны функции некоторой группы лиц и/или комплекса задач, для обслуживания информационных потребностей которых создаётся рассматриваемая БД.

2. Предметный подход к проектированию БД.

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

82.  Использование метода «сущность-связь» при инфологическом проектировании.

83.  Объединение локальных областей

Метод "сущность–связь" (Entity–Relation, ER–method) был разработан в 1976 г. П.Ченом (Chen P.P.). Он является комбинацией двух предыдущих и обладает достоинствами обоих. Этап инфологического проектирования начинается с моделирования ПО. Проектировщик разбивает ПО на ряд локальных областей, каждая из которых (в идеале) включает в себя информацию, достаточную для обеспечения информационных потребностей одной группы будущих пользователей или решения отдельной задачи. Каждое локальное представление моделируется отдельно, а затем выполняется их объединение. Выбор локального представления зависит от масштабов ПО. Обычно ПО разбивается на локальные области так, чтобы каждая из них соответствовала отдельному внешнему приложению и содержала 6-7 сущностей (т.е. объектов, о которых в системе будет накапливаться информация).

Сущности, существование которых не зависит от существования других сущностей, называются базовыми, остальные сущности – зависимыми. Например, сущность ЛЕКЦИЯ зависит от базовых сущностей ГРУППА,  ПРЕПОДАВАТЕЛЬ,  ДИСЦИПЛИНА.

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

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

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

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

объединение в единое целое фрагментарных представлений о различных свойствах одного и того же объекта;

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

образование классов и подклассов подобных объектов (например, класс "изделие" и подклассы типов изделий, производимых на предприятии).

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

1. Идентичность. Два или более элементов модели идентичны, если они имеют одинаковое семантическое значение.

2. Агрегация. Позволяет рассматривать связь между элементами как новый элемент. Например, связь экзамен между сущностями СТУДЕНТ, ДИСЦИПЛИНА, ПРЕПОДАВАТЕЛЬ может быть представлена агрегированной сущностью ЭКЗАМЕН с атрибутами Название дисциплины, Фамилия преподавателя, Фамилия студента, Оценка.

3. Обобщение. Позволяет образовывать многоуровневую иерархию обоб-щений. Например, в объединяемых представлениях присутствуют следующие сущности:

ДЕТАЛИ СОБСТВЕННОГО ПРОИЗВОДСТВА

ДЕТАЛИ ПОКУПНЫЕ

СБОРОЧНЫЕ ЕДИНИЦЫ ПОКУПНЫЕ

СБОРОЧНЫЕ ЕДИНИЦЫ СОБСТВЕННОГО ПРОИЗВОДСТВА

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

Рис.3.1. Использование обобщений при объединении

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

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

На этапе анализа ПО также решаются следующие задачи:

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

2. Выделение групп пользователей системы. Каждая группа выполняет определённые задачи и обладает разными правами доступа к системе.

84.  Определение требований к операционной обстановке

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

Выбор зависит от таких следующих показателей:

примерный объём данных в БД;

динамика роста объёма данных;

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

интенсивность запросов к данным по типам запросов;

85.  Выбор СУБД и инструментальных программных средств

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

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

тип модели данных, которую поддерживает данная СУБД, адекватность модели данных структуре рассматриваемой ПО;

характеристики производительности СУБД;

запас функциональных возможностей для дальнейшего развития информационной системы;

степень оснащенности СУБД инструментарием для персонала администрирования данными;

удобство и надежность СУБД в эксплуатации;

86.  Логическое и физическое проектирование БД.

Логическое проектирование БД.

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

Физическое проектирование БД

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

Более подробно процесс проектирования баз данных освещен в [9].

87.  Автоматизация проектирования БД

Функциональное ядро систем автоматизированного проектирования (САПР) БД строится как совокупность взаимосвязанных модулей инфологического моделирования, проектирования схемы, подсхем и физической организации БД.

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

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

88.  Особенности проектирования реляционных БД

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

Каждое отношение соответствует одной сущности ПО и в него вносятся все атрибуты объекта, связанные с ним отношением 1:1.

Связь типа 1:n реализуется с помощью внешнего ключа.

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

89.  Аномалии модификации данных

В качестве примера возьмём отношение со следующими атрибутами (ключевые атрибуты выделены подчёркиванием):

ПОСТАВКИ (Номер поставки, Название товара, Цена товара, Количество, Дата поставки, Название поставщика, Адрес поставщика)

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

1. Аномалия обновления: в отношении ПОСТАВКИ она может возникнуть, если у какого-либо поставщика изменился адрес. Изменения должны быть внесены во все кортежи, соответствующие поставкам этого поставщика; в противном случае данные будут противоречивы.

2. Аномалия удаления: при удалении записей обо всех поставках одного поставщика все данные о поставщике будут утеряны.

3. Аномалия добавления: в нашем примере она возникнет, если с поставщиком заключен договор, но поставок от него еще не было. Информация о таком поставщике не может быть внесена в отношение ПОСТАВКИ, т.к. для него не определён ключ (номер поставки и название товара) и другие обязательные поля.

90.  Нормализация отношений

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

Декомпозицией схемы отношения R называется замена её совокупностью схем отношений А_i таких, что

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

Полнота - декомпозиция не должна приводить к потере зависимостей между атрибутами сущностей.

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

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

Покажем нормализацию на примере отношения КНИГИ (табл. 3.1):

Id      – идентификатор (первичный ключ),

Code  – шифр рубрики,

Theme– название рубрики,

Title   – название книги,

Author– автор,

Editor – редактор,

Type  – тип издания (учебник, учебное пособие, сборник и.т.п.),

Year   – год издания,

Pg     – количество страниц.

Таблица 3.1. Исходное отношение КНИГИ

ID	Code	Theme	Author	Title	Editor	Type	Year	Pg
200	681.3	ПО ВТ	Бочков С.	Язык СИ	Садчиков П.	учебник	1990	384
			Субботин Д.
100	681.3	ПО ВТ	Джехани Н.	Язык АДА		учебник	1960	552
300	621.5	МО	Крон Г.	Диакоптика	Баранов А.	учебник	1972	544
876	007	ИИ	Гик Е.Я.	Шахматы и математика	Кикоин И.	учебное пособие	1983	176
					Капица С.
440	32.97	ВТ		ПУ для ПЭВМ	Витенберг А.	справочник	1992	208
385	001.8	Инфор-матика	Фролов Г.	Элементы информатики	Храмов А.	учебное пособие	1989	304
			Кузнецов Э.		Рожков П.

Примечание. В таблице 3.1 используются следующие сокращения:

ВТ – вычислительная техника;

ПО ВТ – программное обеспечение вычислительной техники;

МО – математическое обеспечение;

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

Отношение приведено к 1НФ, если все его атрибуты простые.

Отношение КНИГИ содержит сложные атрибуты Author ("Авторы") и Editor ("Редакторы"). Для приведения к 1НФ требуется сделать ключ отношения составным – атрибуты ID, Author и Editor (табл. 3.2).

Таблица 3.2. Отношение КНИГИ, приведённое к 1НФ

ID	Code	Theme	Author	Title	Editor	Type	Year	Pg
200	681.3	ПО ВТ	Бочков С.	Язык СИ	Садчиков П.	учебник	1990	384
200	681.3	ПО ВТ	Субботин Д.	Язык СИ	Садчиков П.	учебник	1990	384
100	681.3	ПО ВТ	Джехани Н.	Язык АДА		учебник	1960	552
300	621.5	МО	Крон Г.	Диакоптика	Баранов А.	учебник	1972	544
876	007	ИИ	Гик Е.Я.	Шахматы и математика	Кикоин И.	учебное пособие	1983	176
876	007	ИИ	Гик Е.Я.	Шахматы и математика	Капица С.	учебное пособие	1983	176
440	32.97	ВТ		ПУ для ПЭВМ	Витенберг А.	спра-вочник	1992	208
385	001.8	Инфор-матика	Фролов Г.	Элементы информатики	Храмов А.	учебное пособие	1989	304
385	001.8	Инфор-матика	Кузнецов Э.	Элементы информатики	Рожков П.	учебное пособие	1989	304

Введём понятие функциональной зависимости. Пусть X и Y – атрибуты (группы атрибутов) некоторого отношения. Говорят, что Y функционально зависит от X, если в любой момент времени каждому значению X=х соответствует единственное значение Y=y (X®Y). (При этом любому значению Y=y может соответствовать несколько значений Х=(х₁, х₂,…)).

Атрибут X в функциональной зависимости X®Y называется детерминантом отношения.

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

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

Для того чтобы привести отношение ко 2НФ, нужно:

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

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

Ключом отношения КНИГИ (табл. 3.2) является комбинация полей (ID, Author, Editor). Все поля, не входящие в состав ключа, зависят только от идентификатора книги. Поэтому отношение должно быть разбито на два: КНИГИ (табл. 3.3) и КНИГИ–АВТОРЫ–РЕДАКТОРЫ (табл. 3.4). Эти отношения связаны по внешнему ключу, которым является поле ID.

Таблица 3.3. Отношение КНИГИ, приведённое к 2НФ

Таблица 3.4. Отношение КНИГИ–АВТОРЫ–РЕДАКТОРЫ (2НФ)

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

Отношение находится в 3НФ, если оно находится во 2НФ и в нем отсутствуют транзитивные зависимости.

Для отношения КНИГИ (табл. 3.3) атрибут Theme зависит от атрибута Code, а не от ключа (хотя название рубрики, естественно, соответствует её шифру). Поэтому для приведения отношения к 3НФ (табл. 3.5) нужно выделить из него ещё одно отношение РУБРИКАТОР (табл. 3.6).

Таблица 3.5. Отношение КНИГИ, приведённое к 3НФ

Таблица 3.6. Отношение РУБРИКАТОР, приведённое к 3НФ

Введём понятие многозначной зависимости. Многозначная зависимость существует, если заданным значениям атрибута X соответствует множество, состоящее из нуля (или более) значений атрибута Y (X–»Y). Если в отношении присутствуют многозначные зависимости, то схема отношения должна находиться в 4НФ.

94.  Четвертая нормальная форма (4НФ).

Отношение находится в 4НФ, если оно находится в 3НФ и в нем отсутствуют нетривиальные многозначные зависимости.

Для отношения КНИГИ–АВТОРЫ–РЕДАКТОРЫ (табл. 3.4) атрибуты Author и Editor зависит образуют две многозначные зависимости от первичного ключа, и при этом значения этих атрибутов не зависят друг от друга. Поэтому для приведения отношения к 4НФ нужно разбить его на два отношения КНИГИ–АВТОРЫ и КНИГИ–РЕДАКТОРЫ (табл. 3.7, 3.8).

Таблица 3.7. Отношение КНИГИ–АВТОРЫ (4НФ)

Таблица 3.8. Отношение КНИГИ–РЕДАКТОРЫ (4НФ)

95.  Способы доступа к записям

Рассмотрим основные способы доступа к данным.

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

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

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

96.  Индексирование данных

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

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

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

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

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

Различают одиночные индексы и составные. Составной индекс включает два или более столбца одной таблицы (рис. 6.2). Последовательность вхождения столбцов в индекс определяется при создании индекса.

Таблица

Индекс

97.  Способы организации индексов

Существует множество способов организации индексов:

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

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

98.  Многоуровневые индексы на основе В-дерева

B-дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами B-дерева являются порядок n и количество уровней. Порядок – это количество ссылок из вершины i-го уровня на вершины (i+1)-го уровня. Каждое B-дерево должно удовлетворять следующим условиям:

1. Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с меньшими по значению ключами, а вправо – к вершине с большими ключами.

2. Любая неконечная вершина имеет не менее n/2 подчинённых вершин.

3. Если неконечная вершина содержит k (k£ n) ключей, то ей подчинена (k+1) вершина на следующем уровне иерархии.

4. Все конечные вершины расположены на одном уровне.

Алгоритм формирования B-дерева порядка n предполагает, что сначала заполняется корневая вершина. Затем при появлении новой записи корневая вершина делится, образуются подчинённые ей вершины. При запоминании каждой новой записи поиск места для неё начинается с корневой вершины. Если в существующем на данный момент B-дереве нет места для размещения нового ключа, происходит сдвиг ключей вправо или влево, если это невозможно – осуществляется перестройка дерева. Пример построения B-дерева порядка 3 приведён на рис. 6.3.

 

Рис. 6.3. Пример построения B-дерева порядка 3

Индексирование в виде B-дерева используется, например, в СУБД Oracle (рис. 6.4).

 

Рис. 6.4. Пример индексного блока СУБД Oracle

Организация индексов в СУБД Oracle несколько отличается от рассмотренной выше классической организации B-дерева, но принцип остаётся тот же: одинаковое количество уровней на любом пути и автоматическая сбалансированность. Верхние блоки содержат данные индекса, которые ссылаются на блоки индекса нижних уровней. Самый нижний n–й уровень содержит блоки индекса (блоки-листья), которые содержат непосредственно данные индекса (ключи) и соответствующие идентификаторы строк ROWID (row identification, КБД), используемые для нахождения самих строк. Блоки-листья связаны между собой указателями.

Поиск по ключу осуществляется следующим образом. Блок верхнего уровня (уровень 1) содержит некоторое значение X и указатели на верхнюю и нижнюю части индекса. Если значение искомого ключа больше X, то происходит переход к верхней части индекса (по левому указателю), иначе – к нижней части. Блоки второго и последующих уровней (кроме двух последних) хранят начальное X₀ и конечное значения X_к ключа, а также три указателя. Если значение искомого ключа больше, чем X₀, то происходит обращение по левому указателю; если оно меньше, чем X_к, то происходит обращение по правому указателю; если оно попадает в диапазон X_0¸X_к – по среднему указателю.

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

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

Индекс в виде B-дерева автоматически поддерживается в сбалансированном виде. Это означает, что при переполнении какого-либо из блоков индекса происходит перераспределение значений ключей индекса (без физического перемещения записей данных). Например, если при добавлении новой записи с ключом "Горин" возникает переполнение соответствующего блока индекса (рис. 6.4), система может перераспределить значения ключей так, как показано на рис. 6.5.

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

 

Рис. 6.5. Пример перераспределения данных индексного блока СУБД Oracle

Структура B-дерева имеет следующие преимущества:

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

B-дерево автоматически поддерживается в сбалансированном виде.

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

Добавление, обновление и удаление строк выполняется достаточно эффективно.

Производительность B-дерева одинаково хороша для маленьких и больших таблиц, и не меняется существенно при росте таблицы.

99.  Использование индексов

В системах, поддерживающих язык SQL, индекс создаётся командой CREATE INDEX. Индексы повышают производительность запросов, которые выбирают относительно небольшое число строк из таблицы. Для определения целесообразности создания индекса нужно проанализировать запросы, обращённые к таблице, и распределение данных в индексируемых столбцах.

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

SELECT * FROM emp WHERE name = 'Даль';

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

Обращение к составному индексу возможно только в том случае, если в условиях выбора участвуют столбцы, представляющие собой лидирующую часть составного индекса. Например, если индекс строится по столбцам (X, Y, Z), то обращение к индексу будет происходить в тех случаях, когда в условии запроса участвуют столбцы XYZ, XY или X.

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

Выбор индексируемых столбцов определяется следующими соображениями:

В первую очередь выбираются столбцы, которые часто встречаются в критериях поиска.

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

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

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

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

В некоторых случаях использование составного индекса предпочтительнее, чем одиночного:

Несколько столбцов с низкой селективностью в комбинации с друг с другом могут дать гораздо более высокую селективность.

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

100.                     Хеширование в базах данных

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

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

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

101.                     Методы хеширования

Многочисленные эксперименты с реальными файлами выявили удовлетворительную работу двух основных типов хеш-функций. Один из них основан на делении, другой – на умножении. Все рассуждения ведутся в предположении, что хеш-функция h(K): 0£ h(K)£ N для всех ключей K, где N – размер памяти (количество ячеек).

Метод деления использует остаток от деления на М:

h(K)= К mod M.

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

М ¹r^k ±a

где k и a – небольшие числа, а r – "основание системы счисления" для большинства используемых литер (как правило, 64, 256 или 100), т.к. остаток от деления на такое число оказывается обычно простой суперпозицией цифр ключа. Чаще всего в качестве М берут простое число, например, вполне удовлетворительные результаты даёт М = 1009.

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

 

где w – размер машинного слова (обычно, 2³¹), А – целое число простое по отношению к w, а M – некоторая степень основания системы счисления ЭВМ (2^m). Таким образом, в качестве значения функции берутся m правых значащих цифр дробной части произведения значения ключа и числа A/w. Вычисление произведения обычно выполняется быстрее, чем деление. Число А выбирают так, чтобы значение Q каждого из его байтов лежало в "хорошем" диапазоне (6.1) и не было слишком близким к значениям других байтов или их дополнениям.

                     (6.1)

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

102.                     Разрешение коллизий

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

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

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

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

3. Многократное хеширование. Заключается в том, что при возникновении коллизии для поиска другого адреса (возможно, на коллизионных страницах) применяется другая функция хеширования.

103.                     Использование хеширования

Хеширование таблицы полезно в следующих случаях:

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

SELECT … WHERE unique_key = …;

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

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

Хеширование не рекомендуется в следующих случаях:

Большинство запросов выбирают строки в некотором интервале. Хеширование не даёт здесь преимуществ, т.к. строки не упорядочены (в отличие от индексирования).

Таблица быстро меняется и постоянно растёт.

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

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

104.                     Кластеризация данных. Принцип организации кластеров

Кластеризация является методом совместного хранения родственных данных (таблиц). Кластер – это структура памяти, в которой хранится набор таблиц (в одних и тех же блоках данных). Эти таблицы должны иметь общие столбцы, используемые для соединения (например, первичный ключ таблицы ТОВАРЫ и внешний ключ таблицы ПОСТАВКИ, рис. 6.6,б).

 

Рис. 6.6. Некластеризованные (а) и кластеризованные (б) данные

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

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

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

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

Два основных преимущества кластеров:

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

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

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

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

если данные в кластерном ключе этих таблиц часто обновляются;

если часто требуется полный просмотр отдельной таблицы.

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

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

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

106.                     Транзакции. Общие сведения

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

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

7.1. Механизм транзакций

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

Транзакция обладает следующими свойствами:

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

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

2. Согласованность: транзакция начинается на согласованном множестве данных и после её завершения множество данных также согласовано.

3. Изолированность, т.е. отсутствие влияния транзакций друг на друга. (На самом деле это влияние существует и регламентируется стандартом: см. раздел 7.2. "Взаимовлияние транзакций").

4. Продолжительность: результаты зафиксированной транзакции не могут быть потеряны. Возврат БД в предыдущее состояние может быть достигнут только путём запуска компенсирующей транзакции.

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

– фиксация транзакции:         COMMIT [WORK];

– откат транзакции:                ROLLBACK [WORK];

– точка сохранения:                SAVEPOINT <имя_точки_сохранения>;

(Ключевое слово WORK необязательно). Предложение SAVEPOINT запоминает промежуточную "текущую копию" состояния базы данных для того, чтобы впоследствии, при необходимости, можно было вернуться к состоянию БД в точке сохранения: откатить работу от текущего момента до точки сохранения (rollback to <имя_точки>) или зафиксировать работу от начала транзакции до точки сохранения (commit to <имя_точки>).

Начало транзакции соответствует появлению первого исполняемого SQL-оператора. Транзакция завершается при наступлении одного из следующих событий:

Поступила команда COMMIT или ROLLBACK (результаты транзакции соответственно зафиксируются или откатываются).

Выдана и успешно проанализирована одна из команд языка описания данных (DDL, Data Definition Language), таких как CREATE, DROP или ALTER. При этом фиксируется предыдущая транзакция.

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

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

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

Фиксация транзакции заключается в следующем:

1. Изменения, внесённые транзакцией, делаются постоянными.

2. Уничтожаются все точки сохранения для данной транзакции.

3. Завершается транзакция (уничтожаются системные записи о транзакции в оперативной памяти).

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

107.                     Взаимовлияние транзакций

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

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

потери изменений;

чернового чтения;

неповторяемого чтения;

фантомов.

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

Например, почти одновременно начали выполняться две транзакции:

транзакция 1 –     UPDATE    СОТРУДНИКИ    SET   Оклад = 9200

WHERE     Номер = 1123

транзакция 2 –     UPDATE    СОТРУДНИКИ

SET  Должность = "старший экономист", ЕТС = 14

WHERE     Номер = 1123

Обе транзакции считали одну и ту же запись (1123, "Рудин В.П.", "экономист", 12, 8300) и внесли каждая свои изменения: в бухгалтерии изменили оклад (транзакция 1), в отделе кадров – должность и ставку по ЕТС (транзакция 2). Результаты транзакции 1 будут потеряны (рис. 7.1).

 

Рис. 7.1. Взаимовлияние транзакций: потеря изменений

СУБД не допускает такого взаимовлияния транзакций, при котором возможна потеря изменений.

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

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

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

7.3. Уровни изоляции транзакций

С целью обеспечения предсказуемости работы приложений для многопользовательских БД стандарт ANSI/ISO для SQL устанавливает различные уровни изоляции для операций, выполняемых над базами данных. Уровень изоляции определяет, может ли транзакция "видеть" результаты работы других одновременно выполняемых завершённых и/или незавершённых транзакций (табл. 7.1).

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

Таблица 7.1. Уровни изоляции по стандарту ANSI / ISO        

По умолчанию обычно используется уровень Read Commited.

108.                     Блокировки

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

Различают следующие типы блокировок:

по степени доступности данных: разделяемые и исключающие;

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

по способу установки: автоматические и явные.

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

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

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

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

Блокировки могут стать причиной бесконечного ожидания и тупиковых ситуаций. Бесконечное ожидание возможно в том случае, если не соблюдается очередность обслуживания транзакций и транзакция, поступившая раньше других, всё время отодвигается в конец очереди. Решение этой проблемы основывается на выполнении правила FIFO: "первый пришел – первый ушел".

Тупиковые ситуации (deadlocks) возникают при взаимных блокировках транзакций, выполняющихся на пересекающихся множествах данных. На рис. 7.2 приведён пример взаимной блокировки трех транзакций T_i на отношениях R_j.

 

Рис. 7.2. Взаимная блокировка трех транзакций

Транзакция T₁ заблокировала данные B₁ в отношении R₁ и ждёт освобождения данных B₂ в отношении R₂, которые заблокированы транзакцией T₂, ожидающей освобождения данных B₃ в отношении R₃, заблокированных транзакцией T₃, которая не может продолжить выполнение из-за транзакции T₁.

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

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

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