Алгоритм нахождения нужных записей "подчиненного" файла
Шаг 1. Ищется запись в "основном" файле в соответствии с его организацией (с помощью функции хэширования, или с использованием индексов, или другим образом). Если требуемая запись найдена, то переходим к шагу 2, в противном случае выводим сообщение об отсутствии записи основного файла.
Шаг 2. Анализируем указатель в основном файле если он пустой, то есть стоит прочерк, значит, для этой записи нет ни одной связанной с ней записи в "подчиненном файле", и выводим соответствующее сообщение, в противном случае переходим к шагу 3.
Шаг 3. По ссылке-указателю в найденной записи основного файла переходим прямым методом доступа по номеру записи на первую запись в цепочке "Подчиненного" файла. Переходим к шагу 4.
Шаг 4. Анализируем текущую запись на содержание если это искомая запись, то мы заканчиваем поиск, в противном случае переходим к шагу 5.
Шаг 5. Анализируем указатель на следующую запись в цепочке если он пуст, то выводим сообщение, что искомая запись отсутствует, и прекращаем поиск, в противном случае По ссылке-указателю переходим на следующую запись в "подчиненном файле" и снова переходим к шагу 4.
Использование цепочек записей позволяет эффективно организовывать модификацию взаимосвязанных файлов.
Алгоритм удаления записи из цепочки "подчиненного" файла
Шаг 1. Ищется удаляемая запись в соответствии с ранее рассмотренным алгоритмом. Единственным отличием при этом является обязательное сохранение в специальной переменной номера предыдущей записи в цепочке, допустим, это переменная NP.
Шаг 2. Запоминаем в специальной переменной указатель на следующую запись в найденной записи, например, заносим его в переменную NS. Переходим к шагу 3.
Шаг 3. Помечаем специальным символом, например символом звездочка (*), найденную запись, то есть в позиции указателя на следующую запись в цепочке ставим символ "*" - это означает, что данная запись отсутствует, а место в файле свободно и может быть занято любой другой записью.
Шаг 4. Переходим к записи с номером, который хранится в NP, и заменяем в ней указатель на содержимое переменной NS.
Для того чтобы эффективно использовать дисковое пространство при включении новой записи в "подчиненный файл", ищется первое свободное место, т. е. запись, помеченная символом "*", и на ее место заносится новая запись, после этого производится модификация соответствующих указателей. При этом необходимо различать 3 случая:
180
Добавление записи на первое место в цепочке.
Добавление записи в конец цепочки.
Добавление записи на заданное место в цепочке.
Архитектура базы данных. Физическая и логическая независимость
Терминология в СУБД, да и сами термины "база данных" и "банк данных" частично заимствованы из финансовой деятельности. Это заимствование - не случайно и объясняется тем, что работа с информацией и работа с денежными массами во многом схожи, поскольку и там и там отсутствует персонификация объекта обработки: две банкноты достоинством в сто рублей столь же неотличимы и взаимозаменяемы, как два одинаковых байта (естественно, за исключением серийных номеров). Вы можете положить деньги на некоторый счет и предоставить возможность вашим родственникам или коллегам использовать их для иных целей. Вы можете поручить банку оплачивать ваши расходы с вашего счета или получить их наличными в другом банке, и это будут уже другие денежные купюры, но их ценность будет эквивалентна той, которую вы имели, когда клали их на ваш счет.
В процессе научных исследований, посвященных тому, как именно должна быть устроена СУБД, предлагались различные способы реализации. Самым жизнеспособным из них оказалась предложенная американским комитетом по стандартизации ANSI (American National Standards Institute) трехуровневая система организации БД, изображенная на рис. 2.1:
Рис. 2.1. Трехуровневая модель системы управления базой данных, предложенная ANSI
Уровень внешних моделей - самый верхний уровень, где каждая модель имеет свое "видение" данных. Этот уровень определяет точку зрения на БД отдельных приложений. Каждое приложение видит и обрабатывает только те данные, которые необходимы именно этому приложению. Например, система распределения работ использует сведения о квалификации сотрудника, но ее
не интересуют сведения об окладе, домашнем адресе и телефоне сотрудника, и наоборот, именно эти сведения используются в подсистеме отдела кадров.
21
Концептуальный уровень - центральное управляющее звено, здесь база данных представлена в наиболее общем виде, который объединяет данные, используемые всеми приложениями, работающими с данной базой данных. Фактически концептуальный уровень отражает обобщенную модель предметной области (объектов реального мира), для которой создавалась база данных.
Как любая модель, концептуальная модель отражает только существенные, с точки зрения обработки, особенности объектов реального мира.
Физический уровень - собственно данные, расположенные в файлах или в страничных структурах, расположенных на внешних носителях информации.
Эта архитектура позволяет обеспечить логическую (между уровнями 1 и 2) и физическую (между уровнями 2 и 3) независимость при работе с данными. Логическая независимость предполагает возможность изменения одного приложения без корректировки других приложений, работающих с этой же базой данных. Физическая независимость предполагает возможность переноса хранимой информации с одних носителей на другие при сохранении работоспособности всех приложений, работающих с данной базой данных. Это именно то, чего не хватало при использовании файловых систем.
Выделение концептуального уровня позволило разработать аппарат централизованного управления базой данных.
Архитектура разделяемой памяти
По причинам объективно существующей разницы в скорости работы процессоров, оперативной памяти и устройств внешней памяти (эта разница в скорости существовала, существует и будет существовать всегда) буферизация страниц базы данных в оперативной памяти - единственный реальный способ достижения удовлетворительной эффективности СУБД.
Операционные системы создают специальные системные буферы, которые служат для кэширования пользовательских процессов. Однако стратегия буферизации, применяемая в операционных средах, не соответствует целям и задачам СУБД, поэтому для оптимизации обработки данных одной из главных задач СУБД является создание эффективной системы управления процессом буферизации.
Разделяемая память, управляемая СУБД, состоит из нескольких типов буферов:
Буферы страниц данных, которые содержат копии страниц данных, с которыми работает СУБД.
Буферы страниц журнала транзакций, которые отражают процесс выполнения транзакции - последовательности операций над БД, переводящей БД из одного непротиворечивого состояния в другое непротиворечивое состояние.
Системные буферы, которые содержат общую информацию о БД, о пользователях, о физической структуре БД, о базе метаданных.
Информация в буферах взаимосвязана, и требуется эффективная система поддержки единой работы всех частей разделяемой памяти.
Если бы запись об изменении базы данных реально немедленно записывалась во внешнюю память, это привело бы к существенному замедлению работы системы.
196
Поэтому записи в журнал тоже буферизуются: при нормальной работе очередная страница выталкивается во внешнюю память журнала только при полном заполнении записями.
Но реальная ситуация является более сложной. Имеются два вида буферов -буфер журнала и буфер страниц оперативной памяти, которые содержат связанную информацию. И те и другие буферы могут выталкиваться во внешнюю память. Проблема состоит в выработке некоторой общей политики выталкивания, которая обеспечивала бы возможности восстановления состояния базы данных после сбоев.
Буфера не выделяются для каждого пользовательского процесса, они выделяются для всех процессов сервера БД. Это позволяет увеличить степень параллелизма при исполнении клиентских процессов.
Разделяемая память наиболее эффективно используется вспомогательными процессами сервера, иногда называемыми демонами, которые используются для синхронизации взаимодействующих процессов на сервере.
На этом мы закончили рассмотрение физических моделей, применяемых в базах данных. Физические модели большей частью скрыты от пользователей. Однако в SQL существует команда создания индексных файлов. При этом по умолчанию стандартно создаются индексные файлы для первичных ключей, для вторичных ключей индексные файлы создаются дополнительной командой CREATE INDEX, которая имеет следующий формат:
CREATE [UNIQUE] INDEX ON
( [] |
[.[]...])
- уникальный идентификатор в системе.
::={ASC | DESC}
Здесь ASC - признак упорядочения по возрастанию, DESC - признак упорядочения по убыванию значений соответствующего столбца в индексе.
Индекс может быть удален командой DROP, которая имеет следующий формат:
DROP INDEX
Даталогическое проектирование
В реляционных БД даталогическое или логическое проектирование приводит к разработке схемы БД, то есть совокупности схем отношений, которые адекватно моделируют абстрактные объекты предметной области и семантические связи между этими объектами. Основой анализа корректности схемы являются так называемые функциональные зависимости между атрибутами БД. Некоторые зависимости между атрибутами отношений являются нежелательными из-за побочных эффектов и аномалий, которые они вызывают при модификации БД. При этом под процессом модификации БД мы понимаем внесение новых данных в БД или удаление некоторых данных из БД, а также обновление значений некоторых атрибутов.
Однако этап логического или даталогического проектирования не заканчивается проектированием схемы отношений. В общем случае в результате выполнения этого этапа должны быть получены следующие результирующие документы:
Описание концептуальной схемы БД в терминах выбранной СУБД.
Описание внешних моделей в терминах выбранной СУБД.
Описание декларативных правил поддержки целостности базы данных.
Разработка процедур поддержки семантической целостности базы данных.
110
Однако перед тем как описывать построенную схему в терминах выбранной СУБД, нам надо выстроить эту схему. Именно этому процессу и посвящен данный раздел.
Мы должны построить корректную схему БД, ориентируясь на реляционную модель данных.
| ОПРЕДЕЛЕНИЕ | |
Корректной назовем схему БД, в которой отсутствуют нежелательные зависимости между атрибутами отношений.
Процесс разработки корректной схемы реляционной БД называется логическим проектированием БД.
Проектирование схемы БД может быть выполнено двумя путями:
путем декомпозиции (разбиения), когда исходное множество отношений, входящих в схему БД заменяется другим множеством отношений (число их при этом возрастает), являющихся проекциями исходных отношений;
путем синтеза, то есть путем компоновки из заданных исходных элементарных зависимостей между объектами предметной области схемы БД.
Классическая технология проектирования реляционных баз данных связана с теорией нормализации, основанной на анализе функциональных зависимостей между атрибутами отношений. Понятие функциональной зависимости является фундаментальным в теории нормализации реляционных баз данных. Мы определим его далее, а пока коснемся смысла этого понятия. Функциональные зависимости определяют устойчивые отношения между объектами и их свойствами в рассматриваемой предметной области. Именно поэтому процесс поддержки функциональных зависимостей, характерных для данной предметной области, является базовым для процесса проектирования.
Процесс проектирования с использованием декомпозиции представляет собой процесс последовательной нормализации схем отношений, при этом каждая последующая итерация соответствует нормальной форме более высокого уровня и обладает лучшими свойствами по сравнению с предыдущей.
Каждой нормальной форме соответствует некоторый определенный набор ограничений, и отношение находится в некоторой нормальной форме, если удовлетворяет свойственному ей набору ограничений.
В теории реляционных БД обычно выделяется следующая последовательность нормальных форм:
первая нормальная форма (1NF);
вторая нормальная форма (2NF);
третья нормальная форма (3NF);
нормальная форма Бойса - Кодда (BCNF);
четвертая нормальная форма (4NF);
пятая нормальная форма, или форма проекции - соединения (5NF или PJNF).
111
Основные свойства нормальных форм:
каждая следующая нормальная форма в некотором смысле улучшает свойства предыдущей;
при переходе к следующей нормальной форме свойства предыдущих нормальных форм сохраняются.
В основе классического процесса проектирования лежит последовательность переходов от предыдущей нормальной формы к последующей. Однако в процессе декомпозиции мы сталкиваемся с проблемой обратимости, то есть возможности восстановления исходной схемы. Таким образом, декомпозиция должна сохранять эквивалентность схем БД при замене одной схемы на другую.
| ОПРЕДЕЛЕНИЕ | |
Функциональные зависимости определяют не текущее состояние БД, а все возможные ее состояния, то есть они отражают те связи между атрибутами, которые присущи реальному объекту, который моделируется с помощью БД.
Поэтому определить функциональные зависимости по текущему состоянию БД можно только в том случае, если экземпляр БД содержит абсолютно полную информацию (то есть никаких добавлений и модификации БД не предполагается). В реальной жизни это требование невыполнимо, поэтому набор функциональных зависимостей задает разработчик, системный аналитик, исходя из глубокого системного анализа предметной области.
Приведем ряд основных определений.
Функциональной зависимостью набора атрибутов В отношения R от набора атрибутов А того же отношения, обозначаемой как
R.A -> R.B или А -> В
называется такое соотношение проекций R[A] и R[B], при котором в каждый момент времени любому элементу проекции R[A] соответствует только один элемент проекции R[B] , входящий вместе с ним в какой-либо кортеж отношения R.
Функциональная зависимость R.A -> R.B называется полной, если набор атрибутов В функционально зависит от А и не зависит функционально от любого подмножества А, то есть
R.A -> R.B называется полной, если:
? А1 ? А ? R.A -/-> R.B,
что читается следующим образом:
для любого А1, являющегося подмножеством A, R.B функционально не зависит от R.A, в противном случае зависимость R.A -> R.B называется неполной.
112
Функциональная зависимость R.A -> R.B называется транзитивной, если существует набор атрибутов С такой, что:
С не является подмножеством А.
С не включает в себя В.
Существует функциональная зависимость R.A -> R.C.
Не существует функциональной зависимости R.C -> R.A.
Существует функциональная зависимость R.C -> R.B.
Возможным ключом отношения называется набор атрибутов отношения, который полностью и однозначно (функционально полно) определяет значения всех остальных атрибутов отношения, то есть возможный ключ - это набор атрибутов, однозначно определяющий кортеж отношения, и при этом при удалении любого атрибута из этого набора его свойство однозначной идентификации кортежа теряется.
А может ли быть ситуация, когда отношение не имеет возможного ключа? Давайте вспомним определение отношения: отношение - это подмножество декартова произведения множества доменов. И в полном декартовом произведении все наборы значений различны, тем более в его подмножестве. Значит, обязательно для каждого отношения всегда существует набор атрибутов, по которому можно однозначно определить кортеж отношения. В вырожденном случае это просто полный набор атрибутов отношения, потому что если мы зададим для всех атрибутов конкретные значения, то, по определению отношения, мы получим только один кортеж.
В общем случае в отношении может быть несколько возможных ключей.
Среди всех возможных ключей отношения обычно выбирают один, который считается главным и который называют первичным ключом отношения.
Неключевым атрибутом называется любой атрибут отношения, не входящий в состав ни одного возможного ключа отношения.
Взаимно-независимые атрибуты - это такие атрибуты, которые не зависят функционально один от другого.
Если в отношении существует несколько функциональных зависимостей, то каждый атрибут или набор атрибутов, от которого зависит другой атрибут, называется детерминантом отношения.
Для функциональных зависимостей как фундаментальной основы проекта БД были проведены исследования, позволяющие избежать избыточного их представления. Ряд зависимостей могут быть выведены из других путем применения правил, названных аксиомами Армстронга, по имени исследователя, впервые сформулировавшего их.
Это три основных аксиомы:
Рефлексивность: если В является подмножеством А, то А->В
Дополнение: если А->В , то АС->BC
Транзитивность: если А->В и В->С , то А->С.
113
Доказано, что данные правила являются полными и исчерпывающими, то есть, применяя их, из заданного множества функциональных зависимостей можно вывести все возможные функциональные зависимости.
Множество всех возможных функциональных зависимостей, выводимое из заданного набора исходных функциональных зависимостей, называется его замыканием.
| ОПРЕДЕЛЕНИЕ | |
| Преподаватель | День недели | Номер пары | Название дисциплины | Тип занятий | Группа |
| Петров В. И. | Понед. | 1 | Теор. выч. проц. | Лекция | 4906 |
| Вторник | 1 | Комп. графика | Лаб. раб. | 4907 | |
| Вторник | 2 | Комп. графика | Лаб. раб. | 4906 | |
| Киров В. А. | Понед. | 2 | Теор. информ. | Лекция | 4906 |
| Вторник | 3 | Пр-е на C++ | Лаб. раб. | 4907 | |
| Вторник | 4 | Пр-е на C++ | Лаб. раб. | 4906 | |
| Серов А. А. | Понед. | 3 | Защита инф. | Лекция | 4944 |
| Среда | 3 | Пр-е на VB | Лаб. раб. | 4942 | |
| Четверг | 4 | Пр-е на VB | Лаб. раб. | 4922 |
Для приведения отношения "Расписание" к первой нормальной форме необходимо дополнить каждую строку фамилией преподавателя.
| ОПРЕДЕЛЕНИЕ | |
| Преподаватель | День недели | Номер пары | Название дисциплины | Тип занятий | Группа |
| Петров В. И | Понед. | 1 | Теор. выч. проц. | Лекция | 4906 |
| Петров В. И | Вторник | 1 | Комп. графика | Лаб. раб. | 4907 |
| Петров В. И | Вторник | 2 | Комп. графика | Лаб. раб. | 4906 |
| Киров В. А. | Понед. | 2 | Теор. информ. | Лекция | 4906 |
| Киров В. А. | Вторник | 3 | Пр-е на C++ | Лаб. раб. | 4907 |
| Киров В. А. | Вторник | 4 | Пр-е на C++ | Лаб. раб. | 4906 |
| Серов А. А. | Понед, | 3 | Защита инф. | Лекция | 4944 |
| Серов А. А. | Среда | 3 | Пр-е на VB | Лаб. раб. | 4942 |
| Серов А. А. | Четверг | 4 | Пр-е на VB | Лаб. раб. | 4922 |
(ФИО. Номер зач.кн.. Группа, Дисциплина, Оценка)
Так как каждый студент сдает целый набор дисциплин в процессе сессии, то первичным ключом отношения может быть (Номер, зач.кн., Дисциплина), который однозначно определяет каждую стоку отношения. С другой стороны, атрибуты ФИО и Группа зависят только от части первичного ключа - от значения атрибута Номер зач. кн., поэтому мы должны констатировать наличие неполных функциональных зависимостей в данном отношении. Для приведения данного отношения ко второй нормальной форме следует разбить его на проекции, при этом должно быть соблюдено условие восстановления исходного отношения без потерь. Такими проекциями могут быть два отношения:
(ФИО, Номер.зач.кн., Группа)
(Номер зач.кн., Дисциплина. Оценка)
Этот набор отношений не содержит неполных функциональных зависимостей, и поэтому эти отношения находятся во второй нормальной форме.
А почему надо приводить отношения ко второй нормальной форме? Иначе говоря, какие аномалии или неудобства могут возникнуть, если мы оставим исходное отношение и не будем его разбивать на два? Давайте рассмотрим ситуацию, когда студент переведен из одной группы в другую. Тогда в первом случае (если мы не разбивали исходное отношение на два) мы должны найти все записи с данным студентом и в них изменить значение атрибута Группа на новое. Во втором же случае меняется только один кортеж в первом отношении. И конечно, опасность нарушения корректности (непротиворечивости содержания) БД в первом случае выше. Может получиться так, что часть кортежей поменяет значения атрибута Группа, а часть по причине сбоя в работе аппаратуры останется в старом состоянии. И тогда наша БД будет содержать записи, которые относят одного студента одновременно к разным группам. Чтобы этого не произошло, мы должны принимать дополнительные непростые меры, например организовывать процесс согласованного изменения с использованием сложного механизма
115
транзакций, который мы будем рассматривать в главах, посвященных вопросам распределенного доступа к БД. Если же мы перешли ко второй нормальной форме, то мы меняем только один кортеж. Кроме того, если у нас есть студенты, которые еще не сдавали экзамены, то в исходном отношении мы вообще не можем хранить о них информацию, а во второй схеме информация о студентах и их принадлежности к конкретной группе хранится отдельно от информации, которая связана со сдачей экзаменов, и поэтому мы можем в этом случае отдельно работать со студентами и отдельно хранить и обрабатывать информацию об успеваемости и сдаче экзаменов, что в действительности и происходит.
| ОПРЕДЕЛЕНИЕ | |
(ФИО, Номер зач.кн..
Группа. Факультет, Специальность, Выпускающая кафедра)
Первичным ключом отношения является Номер зач.кн., однако рассмотрим остальные функциональные зависимости. Группа, в которой учится студент, однозначно определяет факультет, на котором он учится, а также специальность и выпускающую кафедру. Кроме того, выпускающая кафедра однозначно определяет факультет, на котором обучаются студенты, выпускаемые по данной кафедре. Но если мы предположим, что одну специальность могут выпускать несколько кафедр, то специальность не определяет выпускающую кафедру. В этом случае у нас есть следующие функциональные зависимости:
Номер зач.кн. -> ФИО
Номер зач.кн. -> Группа
Номер зач.кн. -> Факультет
Номер зач.кн. -> Специальность
Номер зач.кн. -> Выпускающая кафедра
Группа -> Факультет
Группа -> Специальность
Группа -> Выпускающая кафедра
Выпускающая кафедра -> Факультет
И эти зависимости образуют транзитивные группы. Для того чтобы избежать этого, мы можем предложить следующий набор отношений:
(Номер.зач.кн., ФИО. Специальность. Группа)
(Группа. Выпускающая кафедра)
(Выпускающая кафедра. Факультет)
Первичные ключи отношений выделены.
116
Теперь необходимо удостовериться, что при естественном соединении мы не потеряем ни одной строки и не получим лишних кортежей. И это упражнение я предлагаю выполнить вам самостоятельно.
Полученный набор отношений находится в третьей нормальной форме.
| ОПРЕДЕЛЕНИЕ | |
Отношение, которое моделирует сдачу текущей сессии, имеет следующую структуру:
(Номер зач.кн.. Идентификатор_студента. Дисциплина. Дата, Оценка)
Возможными ключами отношения являются Номер_зач.кн, Дисциплина, Дата и Идентификатор_студента, Дисциплина, Дата.
Какие функциональные зависимости у нас имеются?
Номер_зач кн, Дисциплина. Дата -> Оценка:
Идентификатор_студента. Дисциплина. Дата -> Оценка;
Номер зач.кн. -> Идентификатор_студента:
Идентификатор_студента -> Номер зач.кн
Откуда взялись две последние функциональные зависимости? Но ведь мы предварительно описали, что каждому студенту ставится в соответствие один номер зачетной книжки и один Идентификатор_студента, поэтому по значению Номер зач.кн. можно однозначно определить Идентификатор_студента (это третья зависимость) и обратно (и это четвертая зависимость). Оценим это отношение.
Это отношение находится в третьей нормальной форме, потому что неполных функциональных зависимостей непервичных атрибутов от атрибутов возможного ключа здесь не присутствует и нет транзитивных зависимостей. А как же третья и четвертая зависимости, разве они не являются неполными? Нет, потому что зависимым не является непервичный атрибут, то есть атрибут, не входящий ни в один возможный ключ. Поэтому придраться к этому мы не можем. Но вот под четвертую нормальную форму наше отношение не подходит, потому что у нас есть два детерминанта Номер зач.кн. и Идентификатор_студента, которые не являются возможными ключами отношения. Для приведения отношения к нормальной форме Бойса - Кодда надо разделить отношение, например, на два со следующими схемами:
117
(Идентификатор_студента, Дисциплина. Дата, Оценка)
(Номер зач.кн.. Идентификатор_студента)
или наоборот:
(Номер зач.кн., Дисциплина. Дата. Оценка)
(Номер зач.кн., Идентификатор_студента)
Эти схемы равнозначны с точки зрения теории нормализации, поэтому выбирать проектировщикам следует исходя Из некоторых дополнительных рассуждений. Ну, например, если учесть, что зачетные книжки могут теряться, то как они будут восстанавливаться: если с тем же самым номером, то нет разницы, но если с новым номером, то тогда первая схема предпочтительней.
В большинстве случаев достижение третьей нормальной формы или даже формы Бойса - Кодда считается достаточным для реальных проектов баз данных, однако в теории нормализации существуют нормальные формы высших порядков, которые уже связаны не с функциональными зависимостями между атрибутами отношений, а отражают более тонкие вопросы семантики предметной области и связаны с другими видами зависимостей. Прежде чем перейти к рассмотрению нормальных форм высших порядков, дадим еще несколько определений.
| ОПРЕДЕЛЕНИЕ | |
(Номер зач.кн., Группа. Дисциплина)
Перечень дисциплин, которые должен сдавать студент, однозначно определяется не его фамилией, а номером группы (то есть специальностью, на которой он учится),
В данном отношении существуют следующие две многозначные зависимости:
Группа - > > Дисциплина
Группа - > > Номер зач.кн.
Это означает, что каждой группе однозначно соответствует перечень дисциплин по учебному плану и номер группы определяет список студентов, которые в этой группе учатся.
Если мы будем работать с исходным отношением, то мы не сможем хранить информацию о новой группе и ее учебном плане - перечне дисциплин, которые
118
должна пройти группа до тех пор, пока в нее не будут зачислены студенты.
При изменении перечня дисциплин по учебному плану, например при добавлении новой дисциплины, внести эти изменения в отношение для всех студентов, занимающихся в данной группе, весьма затруднительно. С другой стороны, если мы добавляем студента в уже существующую группу, то мы должны добавить множество кортежей, соответствующих перечню дисциплин для данной группы. Эти аномалии модификации отношения как раз и связаны с наличием двух многозначных зависимостей.
В теории реляционных баз данных доказывается, что в общем случае в отношении R (А, В, С) существует многозначная зависимость R.A - > > R.B в том и только в том случае, когда существует многозначная зависимость R.A - > > R.C.
Дальнейшая нормализация отношений, подобных нашему, основывается на теореме Фейджина.
| ТЕОРЕМА ФЕЙДЖИНА | |
| ОПРЕДЕЛЕНИЕ | |
(Номер зач.кн., Группа)
(Группа. Дисциплина)
Оба эти отношения находятся в 4NF и свободны от отмеченных аномалий. Действительно, обе операции модификации теперь упрощаются: добавление нового студента связано с добавлением всего одного кортежа в первое отношение, а добавление новой дисциплины выливается в добавление одного кортежа во второе отношение, кроме того, во втором отношении мы можем хранить любое количество групп с определенным перечнем дисциплин, в которые пока еще не зачислены студенты.
Последней нормальной формой является пятая нормальная форма 5NF, которая связана с анализом нового вида зависимостей, зависимостей "проекции соединения" (project-join зависимости, обозначаемые как PJ - зависимости). Этот вид
119
зависимостей является в некотором роде обобщением многозначных зависимостей.
| ОПРЕДЕЛЕНИЕ | |
| ОПРЕДЕЛЕНИЕ | |
R1 Преподаватель. Кафедра. Дисциплина)
Предположим, что каждый преподаватель может работать на нескольких кафедрах и на каждой кафедре может вести несколько дисциплин. В этом случае ключом отношения является полный набор из трех атрибутов. В отношении отсутствуют многозначные зависимости, и поэтому отношение находится в 4NF.
Введем следующие обозначения наборов атрибутов:
ПК (Преподаватель. Кафедра)
ПД (Преподаватель. Дисциплина)
КД (Кафедра. Дисциплина)
Допустим, что отношение R1 удовлетворяет зависимости проекции соединения (ПК, ПД, КД). Тогда отношение R1 не находится в NF/PJ, потому что единственным ключом его является полный набор атрибутов, а наличие зависимости PJ связано с наборами атрибутов, которые не составляют возможные ключи отношения R1. Для того чтобы привести это отношение к NF/PJ, его надо представить в виде трех отношений:
R2 (Преподаватель. Кафедра)
R3 (Преподаватель. Дисциплина)
R4 (Кафедра, Дисциплина)
Пятая нормальная форма редко используется на практике.В большей степени она является теоретическим исследованием. Очень тяжело определить само наличие зависимостей "проекции - соединения", потому что утверждение о наличии такой зависимости делается для всех возможных состояний БД, а не только для текущего экземпляра отношения R1. Однако знание о возможном наличии подобных зависимостей, даже теоретическое, нам все же необходимо.
Динамический SQL
Возможности операторов встроенного SQL, описанные ранее, относятся к статическому SQL. В статическом SQL вся информация об операторе SQL известна на момент компиляции. Однако очень часто в диалоговых программах требуется более гибкая форма выполнения операторов SQL. Фактически, сам текст оператора SQL формируется уже во время выполнения программы.
Сформированный таким образом текст SQL - оператора поступает в СУБД, которая должна его скомпилировать и выполнить "на лету", в процессе работы приложения. Если мы снова вернемся к этапам выполнения SQL - операторов, то первые четыре действия, связанные с синтаксическим анализом, семантическим анализом, построением и оптимизацией плана выполнения запроса, выполняются на этапе компиляции. В момент исполнения этого оператора СУБД просто изымает хранимый план выполнения этого оператора и исполняет его.
В случае динамического SQL ситуация абсолютно иная. На момент компиляции мы не видим и не знаем текст оператора SQL и не можем выполнить ни одного из четырех обозначенных этапов. Все этапы СУБД должна будет выполнять с ходу, без предварительной подготовки в момент исполнения программы.
На рис. 12.5 представлены условные временные диаграммы выполнения SQL-операторов в статическом SQL и в динамическом SQL. Конечно, динамический SQL гораздо менее эффективен в смысле производительности, по сравнению со статическим SQL. Поэтому во всех случаях, когда это возможно, необходимо избегать динамического SQL. Но бывают случаи, когда отказ от динамического SQL серьезно усложняет приложение. Например, в случае с поиском по произвольному множеству параметров невозможно заранее предусмотреть все возможные комбинации запросов, даже если возможных параметров два десятка. А если их больше, то именно динамический SQL становится наиболее удобным методом решения необъятной проблемы.
Наиболее простой формой динамического SQL является оператор непосредственного выполнения EXECUTE IMMEDIATE. Этот оператор имеет следующий синтаксис:
EXECUTE IMMEDIATE
Базовая переменная содержит текст SQL оператора.
Однако оператор непосредственного выполнения пригоден для выполнения операций, которые не возвращают результаты. Так же как в статическом SQL, для работы с множеством записей вводится понятие курсора и добавляются операторы но работе с курсором, и в динамическом SQL должны быть определены подобные структуры.
Прежде всего было предложено разделить выполнение SQL - оператора в динамическом SQL на два отдельных этапа. Первый этап называется подготовительным, он фактически включает 4 первых этапа выполнения SQL - операторов, рассмотренные нами ранее: синтаксический и семантический анализ, построение и оптимизация плана выполнения оператора.
Этот этап выполняется оператором PREPARE, синтаксис которого приведен ниже:
PREPARE FROM
- это идентификатор базового языка.
Далее на втором этане этот определенный на первом этапе оператор может быть выполнен операцией EXECUTE, которая имеет синтаксис:
EXECUTE USING { |
DESCRIPTOR }
Здесь DESCRIPTOR - это некоторая структура, которая описывается на клиенте, но создается и управляется сервером. Дескриптор представляет совокупность элементов данных, принадлежащих СУБД. Программное обеспечение СУБД должно содержать и поддерживать набор операций над дескрипторами. Эта структура была введена в стандарт SQL2 для типизации динамического SQL.
В стандарт SQL2 введены следующие операции над дескрипторами:
ALLOCATE DESCRIPTOR [WITH МАХ ] - оператор связывает имя дескриптора с числом его базовых элементов и обеспечивает выделение памяти под данный дескриптор.
DEALLOCATE DESCRIPTOR - оператор освобождает разделяемую память СУБД, занятую хранением описания данного дескриптора. После выполнения данного оператора невозможно обратиться к дескриптору ни с одной операцией.
SET DESCRIPTOR {COUNT = | VALUE (= [...]}} - оператор занесения в дескриптор описания передаваемых параметров. Описания передаются СУБД, которая их обрабатывает, внося соответствующие изменения в область данных, отведенную под дескриптор.
GET DESCRIPTOR { = COUNT | VALUE {=[...]} - оператор получения информации из дескрипторов после выполнения запроса.
DESCRIBE [ INPUT | OUTPUT] USING SQL DESCRIPTOR - оператор, позволяющий получить описания таблиц результатов запросов (DESCRIBE OUTPUT) или входных параметров (DESCRIBE INPUT).
OPEN [USING USING SQL DESCRIPTOR ] - динамический оператор открытия курсора.
FETCH [USING | USING SQL DESCRIPTOR ] - динамический оператор перемещения но курсору.
DEALLOCATE PREPARE - оператор уничтожает ранее подготовленный план выполнения оператора SQL и освобождает разделяемую память СУБД, связанную с хранением этого плана. Этот оператор имеет смысл применять, если вы не будете больше применять команду выполнения к подготовленному ранее оператору SQL.
Следует отметить, что в настоящий момент большинство СУБД реализуют динамический SQL несколько отличными от стандарта способами, однако в ближайшем будущем все поставщики вынуждены будут перейти к стандарту, так как именно это привлекает пользователей и делает переносимым разрабатываемое прикладное программное обеспечение.
Двухуровневые модели
Двухуровневая модель фактически является результатом распределения пяти указанных функций между двумя процессами, которые выполняются на двух платформах: на клиенте и на сервере. В чистом виде почти никакая модель не существует, однако рассмотрим наиболее характерные особенности каждой двухуровневой модели.
Файловые структуры, используемые для хранения информации в базах данных
В каждой СУБД по-разному организованы хранение и доступ к данным, однако существуют некоторые файловые структуры, которые имеют общепринятые способы организации и широко применяются практически во всех СУБД.
В системах баз данных файлы и файловые структуры, которые используются для хранения информации во внешней памяти, можно классифицировать следующим образом (см. рис. 9.1).
Рис. 9.1. Классификация файлов, используемых в системах баз данных
С точки зрения пользователя, файлом называется поименованная линейная последовательность записей, расположенных на внешних носителях. На рис. 9.2 представлена такая условная последовательность записей.
Так как файл - это линейная последовательность записей, то всегда в файле можно определить текущую запись, предшествующую ей и следующую за ней. Всегда существует понятие первой и последней записи файла. Не будем вдаваться в особенности физической организации внешней памяти, выделим в ней те черты, которые существенны для рассмотрения нашей темы.
В соответствии с методами управления доступом различают устройства внешней памяти с произвольной адресацией (магнитные и оптические диски) и устройства с последовательной адресацией (магнитофоны, стримеры).
На устройствах с произвольной адресацией теоретически возможна установка головок чтения-записи в произвольное место мгновенно. Практически существует время позиционирования головки, которое весьма мало по сравнению со временем считывания - записи.
В устройствах с последовательным доступом для получения доступа к некоторому элементу требуется "перемотать (пройти)" все предшествующие ему элементы информации. На устройствах с последовательным доступом вся память рассматривается как линейная последовательность информационных элементов (см. рис. 9.3).
163
Рис. 9.2. Файл как линейная последовательность записей
Рис. 9.3. Модель хранения информации на устройстве последовательного доступа
Файлы с постоянной длиной записи, расположенные, на устройствах прямого доступа (УПД), являются файлами прямого доступа.
В этих файлах физический адрес расположения нужной записи может быть вычислен по номеру записи (NZ).Каждая файловая система СУФ - система управления файлами поддерживает некоторую иерархическую файловую структуру, включающую чаще всего неограниченное количество уровней иерархии в представлении внешней памяти (см. рис. 9.4).
Для каждого файла в системе хранится следующая информация:
имя файла;
тип файла (например, расширение или другие характеристики);
размер записи;
количество занятых физических блоков;
базовый начальный адрес;
164
ссылка на сегмент расширения;
способ доступа (код защиты).
Рис. 9.4. Иерархическая организация файловой структуры хранения
Для файлов с постоянной длиной записи адрес размещения записи с номером К может быть вычислен по формуле:
BA + (К - 1) * LZ + 1,
где BA - базовый адрес, LZ - длина записи.
И как мы уже говорили ранее, если можно всегда определить адрес, на который необходимо позиционировать механизм считывания-записи, то устройства прямого доступа делают это практически мгновенно, поэтому для таких файлов чтение произвольной записи практически не зависит от ее номера. Файлы прямого доступа обеспечивают наиболее быстрый доступ к произвольным записям, и их использование считается наиболее перспективным в системах баз данных.
На устройствах последовательного доступа могут быть организованы файлы только последовательного доступа.
Файлы с переменной длиной записи всегда являются файлами последовательного доступа. Они могут быть организованы двумя способами:
1. Конец записи отличается специальным маркером.
| Запись 1 | ? | Запись 2 | ? | Запись3 | ? |
| LZ1 | Запись1 | LZ2 | Запись2 | LZ3 | Запись 3 |
165
Файлы с прямым доступом обеспечивают наиболее быстрый способ доступа. Мы не всегда можем хранить информацию в виде файлов прямого доступа, но главное - это то, что доступ по номеру записи в базах данных весьма неэффективен. Чаще всего в базах данных необходим поиск по первичному или возможному ключам, иногда необходима выборка по внешним ключам, но во всех этих случаях мы знаем значение ключа, но не знаем номера записи, который соответствует этому ключу.
При организации файлов прямого доступа в некоторых очень редких случаях возможно построение функции, которая по значению ключа однозначно вычисляет адрес (номер записи файла).
NZ = F(K),
где NZ - номер записи, К - значение ключа, F( ) - функция.
Функция F( ) при этом должна быть линейной, чтобы обеспечивать однозначное соответствие (см. рис. 9.5).
Рис. 9.5. Пример линейной функции пересчета значения ключа в номер записи
Однако далеко не всегда удается построить взаимно-однозначное соответствие между значениями ключа и номерами записей.
Часто бывает, что значения ключей разбросаны по нескольким диапазонам (см. рис. 9.6).
Рис. 9.6. Допустимые значения ключа
В этом случае не удается построить взаимно-однозначную функцию, либо эта функция будет иметь множество незадействованных значений, которые соответствуют
166
недопустимым значениям ключа. В подобных случаях применяют различные методы хэширования (рандомизации) и создают специальные хэш - функции. Суть методов хэширования состоит в том, что мы берем значения ключа ( или некоторые его характеристики) и используем его для начала поиска, то есть мы вычисляем некоторую хэш - функцию h(k) и полученное значение берем в качестве адреса начала поиска. То есть мы не требуем полного взаимно - однозначного соответствия, но, с другой стороны, для повышения скорости мы ограничиваем время этого поиска (количество дополнительных шагов) для окончательного получения адреса. Таким образом, мы допускаем, что нескольким разным ключам может соответствовать одно значение хэш - функции (то есть один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами.
Поэтому при использовании хэширования как метода доступа необходимо принять два независимых решения:
выбрать хэш - функцию;
выбрать метод разрешения коллизий.
Файлы и файловые системы
Важным шагом в развитии именно информационных систем явился переход к использованию централизованных систем управления файлами. С точки зрения прикладной программы, файл - это именованная область внешней памяти, в которую можно записывать и из которой можно считывать данные. Правила именования файлов, способ доступа к данным, хранящимся в файле, и структура этих данных зависят от конкретной системы управления файлами и, возможно,
11
от типа файла. Система управления файлами берет на себя распределение внешней памяти, отображение имен файлов в соответствующие адреса во внешней памяти и обеспечение доступа к данным.
Конкретные модели файлов, используемые в системе управления файлами, мы рассмотрим далее, когда перейдем к физическим способам организации баз данных, а на этом этапе нам достаточно знать, что пользователи видят файл как линейную последовательность записей и могут выполнить над ним ряд стандартных операций:
создать файл (требуемого типа и размера);
открыть ранее созданный файл;
прочитать из файла некоторую запись (текущую, следующую, предыдущую, первую, последнюю);
записать в файл на место текущей записи новую, добавить новую запись в конец файла.
В разных файловых системах эти операции могли несколько отличаться, но общий смысл их был именно таким. Главное, что следует отметить, это то, что структура записи файла была известна только программе, которая с ним работала, система управления файлами не знала ее. И поэтому для того, чтобы извлечь некоторую информацию из файла, необходимо было точно знать структуру записи файла с точностью до бита. Каждая программа, работающая с файлом, должна была иметь у себя внутри структуру данных, соответствующую структуре этого файла. Поэтому при изменении структуры файла требовалось изменять структуру программы, а это требовало новой компиляции, то есть процесса перевода программы в исполняемые машинные коды. Такая ситуации характеризовалась как зависимость программ от данных. Для информационных систем характерным является наличие большого числа различных пользователей (программ), каждый из которых имеет свои специфические алгоритмы обработки информации, хранящейся в одних и тех же файлах.
Изменение структуры файла, которое было необходимо для одной программы, требовало исправления и перекомпиляции и дополнительной отладки всех остальных программ, работающих с этим же файлом. Это было первым существенным недостатком файловых систем, который явился толчком к созданию новых систем хранения и управления информацией.
Далее, поскольку файловые системы являются общим хранилищем файлов, принадлежащих, вообще говоря, разным пользователям, системы управления файлами должны обеспечивать авторизацию доступа к файлам. В общем виде подход состоит в том, что по отношению к каждому зарегистрированному пользователю данной вычислительной системы для каждого существующего файла указываются действия, которые разрешены или запрещены данному пользователю. В большинстве современных систем управления файлами применяется подход к защите файлов, впервые реализованный в ОС UNIX. В этой ОС каждому зарегистрированному пользователю соответствует пара целочисленных идентификаторов: идентификатор группы, к которой относится этот пользователь, и его собственный идентификатор в группе. При каждом файле хранится полный идентификатор пользователя, который создал этот файл, и фиксируется, какие
12
действия с файлом может производить его создатель, какие действия с файлом доступны для других пользователей той же группы и что могут делать с файлом пользователи других групп. Администрирование режимом доступа к файлу в основном выполняется его создателем-владельцем. Для множества файлов, отражающих информационную модель одной предметной области, такой децентрализованный принцип управления доступом вызывал дополнительные трудности. И отсутствие централизованных методов управления доступом к информации послужило еще одной причиной разработки СУБД.
Следующей причиной стала необходимость обеспечения эффективной параллельной работы многих пользователей с одними и теми же файлами. В общем случае системы управления файлами обеспечивали режим многопользовательского доступа. Если операционная система, поддерживает многопользовательский режим, вполне реальна ситуация, когда два или более пользователя одновременно пытаются работать с одним и тем же файлом.
Если все пользователи собираются только читать файл, ничего страшного не произойдет. Но если хотя бы один из них будет изменять файл, для корректной работы этих пользователей требуется взаимная синхронизация их действий по отношению к файлу.
В системах управления файлами обычно применялся следующий подход. В операции открытия файла (первой и обязательной операции, с которой должен начинаться сеанс работы с файлом) среди прочих параметров указывался режим работы (чтение или изменение). Если к моменту выполнения этой операции некоторым пользовательским процессом PR1 файл был уже открыт другим процессом PR2 в режиме изменения, то в зависимости от особенностей системы процессу PR1 либо сообщалось о невозможности открытия файла, либо он блокировался до тех пор, пока в процессе PR2 не выполнялась операция закрытия файла.
При подобном способе организации одновременная работа нескольких пользователей, связанная с модификацией данных в файле, либо вообще не реализовывалась, либо была очень замедлена.
Эти недостатки послужили тем толчком, который заставил разработчиков информационных систем предложить новый подход к управлению информацией. Этот подход был реализован в рамках новых программных систем, названных впоследствии Системами Управления Базами Данных (СУБД), а сами хранилища информации, которые работали под управлением данных систем, назывались базами или банками данных (БД и БнД).
Файлы с неплотным индексом, или индексно-последовательные файлы
Попробуем усовершенствовать способ хранения файла: будем хранить его в упорядоченном виде и применим алгоритм двоичного поиска для доступа к произвольной записи. Тогда время доступа к произвольной записи будет существенно меньше. Для нашего примера это будет:
Т = log2KBO = log212500 = 14 обращений к диску.
И это существенно меньше, чем 12 500 обращений при произвольном хранении записей файла. Однако и поддержание основного файла в упорядоченном виде также операция сложная.
Неплотный индекс строится именно для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов имеет следующий вид:
| Значение ключа первой записи блока | Номер блока с этой записью |
В индексной области мы теперь ищем нужный блок по заданному значению первичного ключа. Так как все записи упорядочены, то значение первой записи блока позволяет нам быстро определить, в каком блоке находится искомая запись. Все остальные действия происходят в основной области. На рис. 9.8 представлен пример заполнения основной и индексной областей, если первичным ключом являются целые числа.
174
Рис. 9.8. Пример заполнения индексной и основной области при организации неплотного индекса
Время сортировки больших файлов весьма значительно, но поскольку файлы поддерживаются сортированными с момента их создания, накладные расходы в процессе добавления новой информации будут гораздо меньше.
Оценим время доступа к произвольной записи для файлов с неплотным индексом. Алгоритм решения задачи аналогичен.
Сначала определим размер индексной записи. Если ранее ссылка рассчитывалась исходя из того, что требовалось ссылаться на 100 000 записей, то теперь нам требуется ссылаться всего на 12 500 блоков, поэтому для ссылки достаточно двух байт. Тогда длина индексной записи будет равна:
LI = LK + 2 = 14 + 2 = 14 байт.
Тогда количество индексных записей в одном блоке будет равно:
KIZB = LB/LI = 1024/14 = 73 индексные записи в одном блоке.
Определим количество индексных блоков, которое необходимо для хранения требуемых индексных записей:
KIB - KBO/KZIB - 12500/73 = 172 блока.
Тогда время доступа по прежней формуле будет определяться:
Тпоиска = log2KIB + 1 = log2172 + 1=8+1=9 обращений к диску.
Мы видим, что при переходе к неплотному индексу время доступа уменьшилось практически в полтора раза. Поэтому можно признать, что организация неплотного индекса дает выигрыш в скорости доступа.
Рассмотрим процедуры добавления и удаления новой записи при подобном индексе.
Здесь механизм включения повой записи принципиально отличен от ранее рассмотренного. Здесь новая запись должна заноситься сразу в требуемый блок на требуемое место, которое определяется заданным принципом упорядоченности на множестве значений первичного ключа. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить новую запись, а потом этот блок считывается, затем в оперативной памяти корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, так же как и
175
в первом случае, должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL server этот процент называется Full-factor и используется при формировании кластеризованных индексов. Кластеризованными называются как раз индексы, в которых исходные записи физически упорядочены по значениям первичного ключа. При внесении новой записи индексная область не корректируется.
Количество обращений к диску при добавлении новой записи равно количеству обращений, необходимых для поиска соответствующего блока плюс одно обращение, которое требуется для занесения измененного блока на старое место.
Тдобавления = log2N +1 + 1 обращений.
Уничтожение записи происходит путем ее физического удаления из основной области, при этом индексная область обычно не корректируется, даже если удаляется первая запись блока. Поэтому количество обращений к диску при удалении записи такое же, как и при добавлении новой записи.
Файлы с плотным индексом, или индексно-прямые файлы
Рассмотрим файлы с плотным индексом. В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:
| Значение ключа | Номер записи |
Здесь значение ключа - это значение первичного ключа, а номер записи - это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.
170
Так как индексные файлы строятся для первичных ключей, однозначно определяющих запись, то в них не может быть двух записей, имеющих одинаковые значения первичного ключа. В индексных файлах с плотным индексом для каждой записи в основной области существует одна запись из индексной области. Все записи в индексной области упорядочены по значению ключа, поэтому можно применить более эффективные способы поиска в упорядоченном пространстве.
Длина доступа к произвольной записи оценивается не в абсолютных значениях, а в количестве обращений к устройству внешней памяти, которым обычно является диск. Именно обращение к диску является наиболее длительной операцией по сравнению со всеми обработками в оперативной памяти.
Наиболее эффективным алгоритмом поиска на упорядоченном массиве является логарифмический, или бинарный, поиск. Очень хорошо изложил этот алгоритм барон Мюнхгаузен, когда он объяснял, как поймать льва в пустыне. При этом все пространство поиска разбивается пополам, и так как оно строго упорядочено, то определяется сначала, не является ли элемент искомым, а если нет, то в какой половине его надо искать. Следующим шагом мы определенную половину также делим пополам и производим аналогичные сравнения, и т. д., пока не обнаружим искомый элемент. Максимальное количество шагов поиска определяется двоичным логарифмом от общего числа элементов в искомом пространстве поиска:
Тn = log2N,
где N - число элементов.
Однако в нашем случае является существенным только число обращений к диску при поиске записи по заданному значению первичного ключа.
Давайте рассмотрим конкретный пример и сравним время доступа при последовательном просмотре и при организации плотного индекса.
Допустим, что мы имеем следующие исходные данные:
171
Длина записи файла (LZ) - 128 байт. Длина первичного ключа (LK) - 12 байт. Количество записей в файле (KZ) - 100000. Размер блока (LB) - 1024 байт.
Рассчитаем размер индексной записи. Для представления целого числа в пределах 100000 нам потребуется 3 байта, можем считать, что у нас допустима только четная адресация, поэтому нам надо отвести 4 байта для хранения номера записи, тогда длина индексной записи'будет равна сумме размера ключа и ссылки на номер записи, то есть:
LI - LK + 4 - 14 + 4 - 16 байт.
Определим количество индексных блоков, которое требуется для обеспечения ссылок на заданное количество записей. Для этого сначала определим, сколько индексных записей может храниться в одном блоке:
KIZB = LB/LI = 1024/16 = 64 индексных записи в одном блоке.
Теперь определим необходимое количество индексных блоков:
KIB = KZ/KZIB = 100000/64 - 1563 блока.
Мы округлили в большую сторону, потому что пространство выделяется целыми блоками, и последний блок у нас будет заполнен не полностью.
А теперь мы уже можем вычислить максимальное количество обращений к диску при поиске произвольной записи:
Тпоиска = log2KIB + 1 = log21563 +1 = 11 + 1 = 12 обращений к диску.
Логарифм мы тоже округляем, так как считаем количество обращений, а оно должно быть целым числом.
Следовательно, для поиска произвольной записи по первичному ключу при организации плотного индекса потребуется не более 12 обращений к диску. А теперь оценим, какой выигрыш мы получаем, ведь организация индекса связана с дополнительными накладными расходами на его поддержку, поэтому такая организация может быть оправдана только в том случае, когда она действительно дает значительный выигрыш. Если бы мы не создавали индексное пространство, то при произвольном хранении записей в основной области нам бы в худшем случае было необходимо просмотреть все блоки, в которых хранится файл, временем просмотра записей внутри блока мы пренебрегаем, так как этот процесс происходит в оперативной памяти.
Количество блоков, которое необходимо для хранения всех 100 000 записей, мы определим по следующей формуле:
KBO = KZ/(LB/LZ) - 100000/(1024/128) - 12500 блоков.
И это означает, что максимальное время доступа равно 12500 обращений к диску. Да, действительно, выигрыш существенный.
Рассмотрим, как осуществляются операции добавления и удаления новых записей.
При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область (процент расширения) (рис. 9.7):
172
Рис. 9.7. Пример организации файла с плотным индексом
После определения блока, в который должен быть занесен индекс, этот блок копируется в оперативную память, там он модифицируется путем вставки в нужное мести новой записи (благо в оперативной памяти это делается на несколько порядков быстрее, чем на диске) и, измененный, записывается обратно на диск.
Определим максимальное количество обращений к диску, которое требуется при добавлении записи, - это количество обращений, необходимое для поиска записи плюс одно обращение для занесения измененного индексного блока и плюс одно обращение для занесения записи в основную область.
Тдобавления = log2N +1 + 1 + 1.
173
Естественно, в процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны два решения: либо перестроить заново индексную область, либо организовать область переполнения для индексной области, в которой будут храниться не поместившиеся в основную область записи. Однако первый способ потребует дополнительного времени на перестройку индексной области, а второй увеличит время на доступ к произвольной записи и потребует организации дополнительных ссылок в блоках на область переполнения.
Именно поэтому при проектировании физической базы данных так важно заранее как можно точнее определить объемы хранимой информации, спрогнозировать ее рост и предусмотреть соответствующее расширение области хранения.
При удалении записи возникает следующая последовательность действий: запись в основной области помечается как удаленная (отсутствующая), в индексной области соответствующий индекс уничтожается физически, то есть записи, следующие за удаленной записью, перемещаются на ее место и блок, в котором хранился данный индекс, заново записывается на диск. При этом количество обращений к диску для этой операции такое же, как и при добавлении новой записи.
Физическая согласованность базы данных
Каким же образом можно обеспечить наличие точек физической согласованности базы данных, то есть как восстановить состояние базы данных в момент tpc? Для этого используются два основных подхода: подход, основанный на использовании
227
теневого механизма, и подход, в котором применяется журнализация постраничных изменений базы данных.
При открытии файла таблица отображения номеров его логических блоков в адреса физических блоков внешней памяти считывается в оперативную память. При модификации любого блока файла во внешней памяти выделяется новый блок. При этом текущая таблица отображения (в оперативной памяти) изменяется, а теневая - сохраняется неизменной. Если во время работы с открытым файлом происходит сбой, во внешней памяти автоматически сохраняется состояние файла до его открытия. Для явного восстановления файла достаточно повторно считать в оперативную память теневую таблицу отображения.
Общая идея теневого механизма показана на рис. 11.4.
Рис. 11.4. Использование теневых таблиц отображения информации
В контексте базы данных теневой механизм используется следующим образом. Периодически выполняются операции установления точки физической согласованности базы данных (checkpoints). Для этого все логические операции завершаются, все буферы оперативной памяти, содержимое которых не соответствует содержимому соответствующих страниц внешней памяти, выталкиваются. Теневая таблица отображения файлов базы данных заменяется на текущую (правильнее сказать, текущая таблица отображения записывается на место теневой).
Восстановление к tpc происходит мгновенно: текущая таблица отображения заменяется на теневую (при восстановлении просто считывается теневая таблица отображения). Все проблемы восстановления решаются, но за счёт слишком большого перерасхода внешней памяти. В пределе может потребоваться вдвое больше внешней памяти, чем реально нужно для хранения базы данных. Теневой механизм - это надежное, но слишком грубое средство. Обеспечивается
228
согласованное состояние внешней памяти в один общий для всех объектов момент времени.
На самом деле достаточно иметь совокупность согласованных наборов страниц, каждому из которых может соответствовать свои временные отсчеты.
Для выполнения такого более слабого требования наряду с логической журнализацией операций изменения базы данных производится журнализация постраничных изменений. Первый этап восстановления после мягкого сбоя состоит в постраничном откате незакончившихся логических операций. Подобно тому как это делается с логическими записями по отношению к транзакциям, последней записью о постраничных изменениях от одной логической операции является запись о конце операции.
В этом подходе имеются два метода решения проблемы. При использовании первого метода поддерживается общий журнал логических и страничных операций. Естественно, наличие двух видов записей, интерпретируемых абсолютно по-разному, усложняет структуру журнала. Кроме того, записи о постраничных изменениях, актуальность которых носит локальный характер, существенно (и не очень осмысленно) увеличивают журнал.
Поэтому все более популярным становится поддержание отдельного (короткого) журнала постраничных изменений. Такая техника применяется, например, в известном продукте Informix Online.
Предположим, что некоторым способом удалось восстановить внешнюю память базы данных к состоянию на момент времени tpc (как это можно сделать - немного позже). Тогда:
Для транзакции Т1 никаких действий производить не требуется. Она закончилась до момента tpc, и все ее результаты отражены во внешней памяти базы данных.
Для транзакции Т2 нужно повторно выполнить оставшуюся часть операций (redo). Действительно, во внешней памяти полностью отсутствуют следы операций, которые выполнялись в транзакции Т2 после момента tpc. Следовательно, повторная прямая интерпретация операций Т2 корректна и приведет к логически согласованному состоянию базы данных (поскольку транзакция Т2 успешно завершилась до момента мягкого сбоя, в журнале содержатся записи обо всех изменениях, произведенных этой транзакцией).
Для транзакции Т3 нужно выполнить в обратном направлении первую часть операций (undo). Действительно, во внешней памяти, базы данных полностью отсутствуют результату операций Т3, которые были выполнены после момента tpc, С другой стороны, во внешней памяти гарантированно присутствуют результаты операций Т3, которые были выполнены до момента tpc. Следовательно, обратная интерпретация операций Т3 корректна и приведет к согласованному состоянию базы данных (поскольку транзакция Т3 не завершилась к моменту мягкого сбоя, при восстановлении необходимо устранить все последствия ее выполнения).
Для транзакции Т4, которая успела начаться после момента tpc и закончиться до момента мягкого сбоя, нужно выполнить полную повторную прямую интерпретацию операций (redo).
229
Наконец, для начавшейся после момента tpc и не успевшей завершиться к моменту мягкого сбоя транзакции Т5 никаких действий предпринимать не требуется. Результаты операций этой транзакции полностью отсутствуют во внешней памяти базы данных.
Основные понятия и определения
Современные авторы часто употребляют термины "банк данных" и "база данных" как синонимы, однако в общеотраслевых руководящих материалах по созданию банков данных Государственного комитета по науке и технике (ГКНТ), изданных в 1982 г., эти понятия различаются. Там приводятся следующие определения банка данных, базы данных и СУБД:
Банк данных (БнД) - это система специальным образом организованных данных - баз данных, программных, технических, языковых, организационно - методических средств, предназначенных для обеспечения централизованного накопления и коллективного многоцелевого использования данных.
База данных (БД) - именованная совокупность данных, отражающая состояние объектов и их отношений в рассматриваемой предметной области.
Система управления базами данных (СУБД) - совокупность языковых и программных средств, предназначенных для создания, ведения и совместного использования БД многими пользователями.
Сухой канцелярский язык труден для восприятия, но эти определения четко разграничивают назначение всех трех базовых понятий, и мы можем принять их за основу.
Программы, с помощью которых пользователи работают с базой данных, называются приложениями. В общем случае с одной базой данных могут работать множество различных приложений. Например, если база данных моделирует некоторое предприятие, то для работы с ней может быть создано приложение, которое обслуживает подсистему учета кадров, другое приложение может быть посвящено работе подсистемы расчета заработной платы сотрудников, третье приложение работает как подсистемы складского учета, четвертое приложение посвящено планированию производственного процесса. При рассмотрении приложений, работающих с одной базой данных, предполагается, что они могут работать параллельно и независимо друг от друга, и именно СУБД призвана обеспечить работу множества приложений с единой базой данных таким образом, чтобы каждое из них выполнялось корректно, но учитывало все изменения в базе данных, вносимые другими приложениями.
20
20 :: Содержание
Теоретико - графовые модели данных
Как уже упоминалось ранее, эти модели отражают совокупность объектов реального мира в виде графа взаимосвязанных информационных объектов. В зависимости от типа графа выделяют иерархическую или сетевую модели. Исторически эти модели появились раньше, и в настоящий момент они используются реже, чем более современная реляционная модель данных. Однако до сих пор существуют системы, работающие на основе этих моделей, а одна из концепций развития объектно-ориентированных баз данных предполагает объединение принципов сетевой модели с концепцией реляционной.
Проектирование реляционных БД на основе принципов нормализации
Что такое проект? Это схема - эскиз некоторого устройства, который в дальнейшем будет воплощен в реальность. Что такое проект реляционной базы данных? Это набор взаимосвязанных отношений, в которых определены все атрибуты, заданы первичные ключи отношений и заданы еще некоторые дополнительные свойства отношений, которые относятся к принципам поддержки целостности и будут более подробно рассмотрены в главе 9. Почему именно взаимосвязанных отношений? Потому что при выполнении запросов мы производим объединение отношений и одни и те же значения должны в разных отношениях-таблицах обозначаться одинаково. Действительно, если мы в одной таблице оценки будем обозначать цифрами, а в другой словами "отлично", "хорошо" и т. д., то мы не сможем объединить эти таблицы по столбцу Оценка, хотя по смыслу это для нас одно и то же, но то, что интуитивно понятно человеку, совсем не понятно "умному" компьютеру. Это проблема систем с искусственным интеллектом, которые могут решать весьма сложные интеллектуальные задачи, трудные для рядового инженера, но иногда пасуют перед простейшими интуитивными ассоциациями, понятными любому школьнику. И это необходимо учитывать. Поэтому проект базы данных должен быть очень точен и выверен. Фактически проект базы данных - это фундамент будущего программного комплекса, который будет использоваться достаточно долго и многими пользователями. И как в любом здании, можно достраивать мансарды, переделывать крышу, можно даже менять окна, но заменить фундамент, не разрушив всего здания, невозможно. Этапы жизненного цикла базы данных изображены на рис. 6.1. Они аналогичны, в основном, развитию любой программной системы, однако в них есть определенная специфика, касающаяся только баз данных. Более подробно мы будем рассматривать этапы жизненного цикла БД в следующих разделах учебного пособия, потому что термины, которые мы вынуждены применять при этом описании, пока еще неизвестны нашим читателям.
104
Рис. 6.1. Этапы жизненного цикла БД
Процесс проектирования БД представляет собой последовательность переходов от неформального словесного описания информационной структуры предметной области к формализованному описанию объектов предметной области в терминах некоторой модели. В общем случае можно выделить следующие этапы проектирования:
Системный анализ и словесное описание информационных объектов предметной области.
Проектирование инфологической модели предметной области - частично формализованное описание объектов предметной области в терминах некоторой семантической модели, например, в терминах Е-модели.
Даталогическое или логическое проектирование БД, то есть описание БД в терминах принятой даталогической модели данных.
Физическое проектирование БД, то есть выбор эффективного размещения БД на внешних носителях для обеспечения наиболее эффективной работы приложения.
Если мы учтем, что между вторым и третьим этапами необходимо принять решение, с использованием какой стандартной СУБД будет реализовываться наш проект, то условно процесс проектирования БД можно представить последовательностью выполнения пяти соответствующих этапов (см. рис. 6.2). Рассмотрим более подробно этапы проектирования БД.
105
Рис. 6.2. Этапы проектирования БД
Инфологическое моделирование
Инфологическая модель применяется на втором этапе проектирования БД, то есть после словесного описания предметной области. Зачем нужна инфологическая модель и какую пользу она дает проектировщикам? Еще раз хотим напомнить, что процесс проектирования длительный, он требует обсуждений с заказчиком, со специалистами в предметной области. Наконец, при разработке серьезных корпоративных информационных систем проект базы данных является тем фундаментом, на котором строится вся система в целом, и вопрос о возможном кредитовании часто решается экспертами банка на основании именно грамотно сделанного инфологического проекта БД. Следовательно, инфологическая модель должна включать такое формализованное описание предметной области, которое легко будет "читаться" не только специалистами по базам данных. И это описание должно быть настолько емким, чтобы можно было оценить глубину и корректность проработки проекта БД, и конечно, как говорилось раньше, оно не должно быть привязано к конкретной СУБД. Выбор СУБД - это отдельная задача, для корректного ее решения необходимо иметь проект, который не привязан ни к какой конкретной СУБД.
Инфологическое проектирование прежде всего связано с попыткой представления семантики предметной области в модели БД. Реляционная модель данных в силу своей простоты и лаконичности не позволяет отобразить семантику, то есть смысл предметной области. Ранние теоретико - графовые модели в большей степени отображали семантику предметной области. Они в явном виде определяли иерархические связи между объектами предметной области.
Проблема представления семантики давно интересовала разработчиков, и в семидесятых годах было предложено несколько моделей данных, названных семантическими моделями. К ним можно отнести семантическую модель данных, предложенную Хаммером (Hammer) и Мак - Леоном (McLeon) в 1981 году, функциональную модель данных Шипмана (Shipman), также созданную в 1981 году, модель "сущность-связь", предложенную Ченом (Chen) в 1976 году, и ряд других моделей.
У всех моделей были свои положительные и отрицательные стороны, но испытание временем выдержала только последняя. И в настоящий момент именно модель Чена "сущность - связь", или "Entity Relationship", стала
121
фактическим стандартом при инфологическом моделировании баз данных. Общепринятым стало сокращенное название ER-модель, большинство современных CASE-средств содержат инструментальные средства для описания данных в формализме этой модели. Кроме того, разработаны методы автоматического преобразования проекта БД из ER-модели в реляционную, при этом преобразование выполняется в даталогическую модель, соответствующую конкретной СУБД. Все CASE - системы имеют развитые средства документирования процесса разработки БД, автоматические генераторы отчетов позволяют подготовить отчет о текущем состоянии проекта БД с подробным описанием объектов БД и их отношений как в графическом виде, так и в виде готовых стандартных печатных отчетов, что существенно облегчает ведение проекта.
В настоящий момент не существует единой общепринятой системы обозначений для ER - модели и разные CASE - системы используют разные графические нотации, но разобравшись в одной, можно легко понять и другие нотации.
Принципы поддержки целостности в реляционной модели данных
Одним из основополагающих понятий в технологии баз данных является понятие целостности. В общем случае это понятие прежде всего связано с тем, что база данных отражает в информационном виде некоторый объект реального мира или совокупность взаимосвязанных объектов реального мира. В реляционной модели объекты реального мира представлены в виде совокупности взаимосвязанных отношений. Под целостностью будем понимать соответствие информационной модели предметной области, хранимой в базе данных, объектам реального мира и их взаимосвязям в каждый момент времени. Любое изменение в предметной области, значимое для построенной модели, должно отражаться в базе данных, и при этом должна сохраняться однозначная интерпретация информационной модели в терминах предметной области.
Мы отметили, что только существенные или значимые изменения предметной области должны отслеживаться в информационной модели. Действительно, модель всегда представляет собой некоторое упрощение реального объекта, в модели мы отражаем только то, что нам важно для решения конкретного набора задач. Именно поэтому в информационной системе "Библиотека" мы, например, не отразили место хранения конкретных экземпляров книг, потому что мы не ставили задачу автоматической адресации библиотечных стеллажей. И в этом случае любое перемещение книг с одного места на другое не будет отражено в модели, это перемещение несущественно для наших задач. С другой стороны, процесс взятия, книги читателем или возврат любой книги в библиотеку для нас важен, и мы должны его отслеживать в соответствии с изменениями в реальной предметной области. И с этой точки зрения наличие у экземпляра книги указателя на его отсутствие в библиотеке и одновременное отсутствие записи о конкретном номере читательского билета, за которым числится этот экземпляр книги, является противоречием, такого быть не должно. И в модели данных должны
135
быть предусмотрены средства и методы, которые позволят нам обеспечивать динамическое отслеживание в базе данных согласованных действий, связанных с согласованным изменением информации. Именно этим вопросам и посвящена данная глава.
136
135 :: 136 :: Содержание
Физические модели баз данных
Физические модели баз данных определяют способы размещения данных в среде хранения и способы доступа к этим данным, которые поддерживаются на физическом уровне. Исторически первыми системами хранения и доступа были файловые структуры и системы управления файлами (СУФ), которые фактически являлись частью операционных систем. СУБД создавала над этими файловыми моделями свою надстройку, которая позволяла организовать всю совокупность файлов таким образом, чтобы она работала как единое целое и получала централизованное управление от СУБД. Однако непосредственный доступ осуществлялся на уровне файловых команд, которые СУБД использовала при манипулировании всеми файлами, составляющими хранимые данные одной или нескольких баз данных.
Однако механизмы буферизации и управления файловыми структурами не приспособлены для решения задач собственно СУБД, эти механизмы разрабатывались просто для традиционной обработки файлов, и с ростом объемов хранимых данных они стали неэффективными для использования СУБД. Тогда постепенно произошел переход от базовых файловых структур к непосредственному управлению размещением данных на внешних носителях самой СУБД. И пространство внешней памяти уже выходило из-под владения СУФ и управлялось непосредственно СУБД. При этом механизмы, применяемые в файловых системах, перешли во многом и в новые системы организации данных во внешней памяти, называемые чаще страничными системами хранения информации. Поэтому наш раздел, посвященный физическим моделям данных, мы начнем с обзора файлов и файловых структур, используемых для организации физических моделей, применяемых в базах данных, а в конце ознакомимся с механизмами организации данных во внешней памяти, использующими страничный принцип организации.
162
162 :: Содержание
Распределенная обработка данных
При размещении БД на персональном компьютере, который не находится в сети, БД всегда используется в монопольном режиме. Даже если БД используют несколько пользователей, они могут работать с ней только последовательно, и поэтому вопросов о поддержании корректной модификации БД в этом случае здесь не стоит, они решаются организационными мерами - то есть определением требуемой последовательности работы конкретных пользователей с соответствующей БД. Однако даже в некоторых настольных БД требуется учитывать последовательность изменения данных при обработке, чтобы получить корректный результат: так, например, при запуске программы балансного бухгалтерского отчета все бухгалтерские проводки - финансовые операции должны быть решены заранее до запуска конечного приложения.
Однако работа на изолированном компьютере с небольшой базой данных в настоящий момент становится уже нехарактерной для большинства приложений. БД отражает информационную модель реальной предметной области, она растет по объему и резко увеличивается количество задач, решаемых с ее использованием, и в соответствии с этим увеличивается количество приложений, работающих с единой базой данных. Компьютеры объединяются в локальные сети, и необходимость распределения приложений, работающих с единой базой данных по сети, является несомненной.
Действительно, даже когда вы строите БД для небольшой торговой фирмы, у вас появляется ряд специфических пользователей БД, которые имеют свои бизнес-функции и территориально могут находиться в разных помещениях, но все они должны работать с единой информационной моделью организации, то есть с единой базой данных.
Параллельный доступ к одной БД нескольких пользователей, в том случае если БД расположена на одной машине, соответствует режиму распределенного доступа к централизованной БД. (Такие системы называются системами распределенной обработки данных.)
198
Если же БД распределена по нескольким компьютерам, расположенным в сети, и к ней возможен параллельный доступ нескольких пользователей, то мы имеем дело с параллельным доступом к распределенной БД. Подобные системы называются системами распределенных баз данных. В общем случае режимы использования БД можно представить в следующем виде (см. рис. 10.1).
Рис. 10.1. Режимы работы с базой данных
Определим терминологию, которая нам потребуется для дальнейшей работы. Часть терминов нам уже известна, но повторим здесь их дополнительно.
Модели транзакций
Транзакцией называется последовательность операций, производимых над базой данных и переводящих базу данных из одного непротиворечивого (согласованного) состояния в другое непротиворечивое (согласованное) состояние.
Транзакция рассматривается как некоторое неделимое действие над базой данных, осмысленное с точки зрения пользователя. В то же время это логическая единица работы системы. Рассмотрим несколько примеров. Что может быть названо транзакцией? Кем определяется, какая последовательность операций над базой данных составляет транзакцию? Конечно, однозначно именно разработчик определяет, какая последовательность операций составляет единое целое, то есть транзакцию. Разработчик приложений или хранимых процедур определяет это исходя из смысла обработки данных, именно семантика совокупности операций над базой данных, которая моделирует с точки зрения разработчика некоторую одну неразрывную работу, и составляет транзакцию. Допустим, выделим работу по вводу данных о поступивших книгах, новых книгах, которых не было раньше в библиотеке. Тогда эту операцию можно разбить на две последовательные: сначала ввод данных о книге - это новая строка в таблице BOOKS, а потом ввод данных обо всех экземплярах новой книги - это ввод набора новых строк в таблицу EXEMPLAR в количестве, равном количеству поступивших экземпляров книги. Если эта последовательность работ будет прервана, то наша база данных не будет соответствовать реальному объекту, поэтому желательно выполнять ее как единую работу над базой данных.
Следующий пример, который связан с принятием заказа в фирме на изготовление компьютера. Компьютер состоит из комплектующих, которые сразу резервируются за данным заказом в момент его формирования. Тогда транзакцией будет вся последовательность операций, включающая следующие операции:
ввод нового заказа со всеми реквизитами заказчика;
изменения состояния для всех выбранных комплектующих на складе на "занято" с привязкой их к определенному заказу;
подсчет стоимости заказа с формированием платежного документа типа выставляемого счета к оплате;
включение нового заказа в производство.
216
С точки зрения работника, это единая последовательность операций; если она будет прервана, то база данных потеряет свое целостное состояние.
Еще один пример, который весьма характерен для учебных заведений. При длительной болезни преподавателя или при его увольнении перед администрацией кафедры встает задача перераспределения всей нагрузки, которую ведет преподаватель, по другим преподавателям кафедры. Видов нагрузки может быть несколько: чтение лекций и проведение занятий по текущему расписанию, руководство квалификационными работами бакалавров, руководство дипломными проектами специалистов, руководство магистерскими диссертациями, индивидуальная научно-исследовательская работа со студентами. И для каждого вида нагрузки необходимо найти исполнителей и назначить им дополнительную нагрузку.
217
216 :: 217 :: Содержание
Встроенный SQL
Язык SQL, как мы уже видели в главе 5, предназначен для организации доступа к базам данных. При этом предполагается, что доступ к БД может быть осуществлен в двух режимах: в интерактивном режиме и в режиме выполнения прикладных программ (приложений).
Эта двойственность SQL создает ряд преимуществ:
Все возможности интерактивного языка запросов доступны и в прикладном программировании.
Можно в интерактивном режиме отладить основные алгоритмы обработки информации, которые в дальнейшем могут быть готовыми вставлены в работающие приложения.
SQL действительно является языком по работе с базами данных, но в явном виде он не является языком программирования. В нем отсутствуют традиционные операторы, организующие циклы, позволяющие объявить и использовать внутренние переменные, организовать анализ некоторых условий и возможность изменения хода программы в зависимости от выполненного условия. В общем случае можно назвать SQL подъязыком, который служит исключительно для управления базами данных. Для создания приложений, настоящих программ необходимо использовать другие, базовые языки программирования, в которые операторы языка SQL будут встраиваться.
Базовыми языками программирования могут быть языки С, COBOL, PL/1, Pascal.
Существуют два способа применения SQL в прикладных программах:
Встроенный SQL. При таком подходе операторы SQL встраиваются непосредственно в исходный текст программы на базовом языке. При компиляции программы со встроенными операторами SQL используется специальный препроцессор SQL, который преобразует исходный текст в исполняемую программу.
Интерфейс программирования приложений (API application program interface). При использовании данного метода прикладная программа взаимодействует с СУБД путем применения специальных функций. Вызывая эти функции, программа передает СУБД операторы SQL и получает обратно результаты запросов. В этом случае не требуется специализированный препроцессор.
248
Процесс выполнения операторов SQL может быть условно разделен на 5 этапов (см.
Рис. 12.1. Процесс выполнения операторов SQL
На первом этапе выполняется синтаксический анализ оператора SQL. На этом этапе проверяется корректность записи SQL-оператора в соответствии с правилами синтаксиса.
На этом этапе проверяется корректность параметров оператора SQL: имен отношений, имен полей данных, привилегий пользователя по работе с указанными объектами. Здесь обнаруживаются семантические ошибки.
На этом этапе проводится оптимизация запроса. СУБД проводит разделение целостного запроса на ряд минимальных операций и оптимизирует последовательность их выполнения с точки зрения стоимости выполнения запроса. На этом этапе строится несколько планов выполнения запроса и выбирается из них один - оптимальный для данного состояния БД.
На четвертом этапе СУБД генерирует двоичную версию оптимального плана запроса, подготовленного на этапе 3. Двоичный план выполнения запроса в СУБД фактически является эквивалентом объектного кода программы.
И наконец, только на пятом этапе СУБД реализует (выполняет) разработанный план, тем самым выполняя оператор SQL.
249
Следует отметить, что перечисленные этапы отличаются по числу обращений к БД и по процессорному времени, требуемому для их выполнения. Синтаксический анализ проводится очень быстро, он не требует обращения к системным каталогам БД. Семантический анализ уже требует работы с базой мета - данных, то есть с системными каталогами БД, поэтому при выполнении этого этапа происходит обращение к системному каталогу и серьезная работа с ним. Этап, связанный с оптимизаций плана запроса, требует работы не только с системным каталогом, но и со статистической информацией о БД, которая характеризует текущее состояние всех отношений, используемых в запросе, их физическое расположение на страницах и сегментах внешней памяти. В силу указанных причин этап оптимизации наиболее трудоемкий и длительный в процессе выполнения запроса. Однако если не проводить этап оптимизации, то стоимость (время) выполнения неоптимизированного запроса может в несколько раз превысить стоимость оптимизированного запроса.Время, потраченное на оптимизацию запроса, с лихвой компенсирует затраты на выполнение неоптимизированного запроса.
Этапы выполнения операторов SQL одни и те же как в интерактивном режиме, так и внутри приложений. Однако при работе с готовым приложением многие этапы СУБД может выполнить заранее.
Защита информации в базах данных
В современных СУБД поддерживается один из двух наиболее общих подходов к вопросу обеспечения безопасности данных: избирательный подход и обязательный подход. В обоих подходах единицей данных или "объектом данных", для которых должна быть создана система безопасности, может быть как вся база данных целиком, так и любой объект внутри базы данных.
Эти два подхода отличаются следующими свойствами:
В случае избирательного управления некоторый пользователь обладает различными правами (привилегиями или полномочиями) при работе с данными объектами. Разные пользователи могут обладать разными правами доступа к одному и тому же объекту. Избирательные права характеризуются значительной гибкостью.
В случае избирательного управления, наоборот, каждому объекту данных присваивается некоторый классификационный уровень, а каждый пользователь обладает некоторым уровнем допуска. При таком подходе доступом к определенному объекту данных обладают только пользователи с соответствующим уровнем допуска.
Для реализации избирательного принципа предусмотрены следующие методы. В базу данных вводится новый тип объектов БД - это пользователи. Каждому пользователю в БД присваивается уникальный идентификатор. Для дополнительной защиты каждый пользователь кроме уникального идентификатора снабжается уникальным паролем, причем если идентификаторы пользователей в системе доступны системному администратору, то пароли пользователей хранятся чаще всего в специальном кодированном виде и известны только самим пользователям.
Пользователи могут быть объединены в специальные группы пользователей. Один пользователь может входить в несколько групп. В стандарте вводится понятие группы PUBLIC, для которой должен быть определен минимальный стандартный набор прав. По умолчанию предполагается, что каждый вновь создаваемый пользователь, если специально не указано иное, относится к группе PUBLIC.
276
Привилегии или полномочия пользователей или групп - это набор действий (операций), которые они могут выполнять над объектами БД.
В последних версиях ряда коммерческих
В последних версиях ряда коммерческих СУБД появилось понятие "роли". Роль - это поименованный набор полномочий. Существует ряд стандартных ролей, которые определены в момент установки сервера баз данных. И имеется возможность создавать новые роли, группируя в них произвольные полномочия. Введение ролей позволяет упростить управление привилегиями пользователей, структурировать этот процесс. Кроме того, введение ролей не связано с конкретными пользователями, поэтому роли могут быть определены и сконфигурированы до того, как определены пользователи системы.
Пользователю может быть назначена одна или несколько ролей.
Объектами БД, которые подлежат защите, являются все объекты, хранимые в БД: таблицы, представления, хранимые процедуры и триггеры. Для каждого типа объектов есть свои действия, поэтому для каждого типа объектов могут быть определены разные права доступа.
На самом элементарном уровне концепции обеспечения безопасности баз данных исключительно просты. Необходимо поддерживать два фундаментальных принципа: проверку полномочий и проверку подлинности (аутентификацию).
Проверка полномочий основана на том, что каждому пользователю или процессу информационной системы соответствует набор действий, которые он может выполнять по отношению к определенным объектам. Проверка подлинности означает достоверное подтверждение того, что пользователь или процесс, пытающийся выполнить санкционированное действие, действительно тот, за кого он себя выдает.
Система назначения полномочий имеет в некотором роде иерархический характер. Самыми высокими правами и полномочиями обладает системный администратор или администратор сервера БД. Традиционно только этот тип пользователей может создавать других пользователей и наделять их определенными полномочиями.
СУБД в своих системных каталогах хранит как описание самих пользователей, так и описание их привилегий по отношению ко всем объектам.
Далее схема предоставления полномочий строится по следующему принципу. Каждый объект в БД имеет владельца - пользователя, который создал данный объект.
Владелец объекта обладает всеми правами-полномочиями на данный объект, в том числе он имеет право предоставлять другим пользователям полномочия по работе с данным объектом или забирать у пользователей ранее предоставленные полномочия.
В ряде СУБД вводится следующий уровень иерархии пользователей - это администратор БД. В этих СУБД один сервер может управлять множеством СУБД (например, MS SQL Server, Sybase).
277
В СУБД Oracle применяется однобазовая архитектура, поэтому там вводится понятие подсхемы - части общей схемы БД и вводится пользователь, имеющий доступ к подсхеме.
В стандарте SQL не определена команда создания пользователя, но практически во всех коммерческих СУБД создать пользователя можно не только в интерактивном режиме, но и программно с использованием специальных хранимых процедур. Однако для выполнения этой операции пользователь должен иметь право на запуск соответствующей системной процедуры.
В стандарте SQL определены два оператора: GRANT и REVOKE соответственно предоставления и отмены привилегий.
Оператор предоставления привилегий имеет следующий формат:
GRANT ( | ALL PRIVILEGES }
ON ТО { | PUBLIC }
[WITH GRANT OPTION ]
Здесь список действий определяет набор действий из общедопустимого перечня действий над объектом данного типа.
Параметр ALL PRIVILEGES указывает, что разрешены все действия из допустимых для объектов данного тина.
- задает имя конкретного объекта: таблицы, представления, хранимой процедуры, триггера.
или PUBLIC определяет, кому предоставляются данные привилегии.
Параметр WITH GRANT OPTION является необязательным и определяет режим, при котором передаются не только права па указанные действия, но и право передавать эти права другим пользователям. Передавать права в этом случае пользователь может только в рамках разрешенных ему действий.
Рассмотрим пример, пусть у нас существуют три пользователя с абсолютно уникальными именами user1, user2 и user3. Все они являются пользователями одной БД.
User1 создал объект Tabl, он является владельцем этого объекта и может передать права на работу с эти объектом другим пользователям.
Допустим, что пользователь user2 является оператором, который должен вводить данные в Tabl (например, таблицу новых заказов), а пользователь user3 является большим начальником (например, менеджером отдела), который должен регулярно просматривать введенные данные.
Для объекта типа таблица полным допустимым перечнем действий является набор из четырех операций: SELECT. INSERT. DELETE. UPDATE. При этом операция обновление может быть ограничена несколькими столбцами.
Общий формат оператора назначения привилегий для объекта типа таблица будет иметь следующий синтаксис:
GRANT {[SELECT][.INSERT][.DELETE][.UPDATE ()]}
ON
278
ТО { | PUBLIC }
[WITH GRANT OPTION ]
Тогда резонно будет выполнить следующие назначения:
GRANT INSERT
ON Tabl
TO user2
GRANT SELECT
ON Tabl
TO user3
Эти назначения означают, что пользователь user2 имеет право только вводить новые строки в отношение Tabl, а пользователь user3 имеет право просматривать все строки в таблице Tabl.
При назначении прав доступа на операцию модификации можно уточнить, значение каких столбцов может изменять пользователь. Допустим, что менеджер отдела имеет право изменять цену на предоставляемые услуги. Предположим, что цена задается в столбце COST таблицы Tabl. Тогда операция назначения привилегий пользователю user3 может измениться и выглядеть следующим образом:
GRANT SELECT, UPDATE (COST)
ON Tabl
TO user3
Если наш пользователь user1 предполагает, что пользователь user4 может его замещать в случае его отсутствия, то он может предоставить этому пользователю все права по работе с созданной таблицей Tabl.
GRANT ALL PRIVILEGES
ON Tabl
TO user4
WITH GRANT OPTION
В этом случае пользователь user4 может сам назначать привилегии по работе с таблицей Tabl в отсутствие владельца объекта пользователя userl. Поэтому в случае появления нового оператора пользователя user3 он может назначить ему права на ввод новых строк в таблицу командой
GRANT INSERT
ON Tabl
TO user5
Если при передаче полномочий набор операций над объектом ограничен, то пользователь, которому переданы эти полномочия, может передать другому пользователю только те полномочия, которые есть у него, или часть этих полномочий.
Поэтому если пользователю user4 были делегированы следующие полномочия:
279
GRANT SELECT. UPDATE, DELETE
ON Tabl
TO user4
WITH GRANT OPTION.
то пользователь user4 не сможет передать полномочия на ввод данных пользователю user3, потому что эта операция не входит в список разрешенных для него самого.
Кроме непосредственного назначения прав по работе с таблицами эффективным методом защиты данных может быть создание представлений, которые будут содержать только необходимые столбцы для работы конкретного пользователя и предоставление прав на работу с данным представлением пользователю.
Так как представления могут соответствовать итоговым запросам, то для этих представлений недопустимы операции изменения, и, следовательно, для таких представлений набор допустимых действий ограничивается операцией SELECT. Если же представления соответствуют выборке из базовой таблицы, то для такого представления допустимыми будут все 4 операции: SELECT, INSERT, UPDATE и DELETE.
Для отмены ранее назначенных привилегий в стандарте SQL определен оператор REVOKE. Оператор отмены привилегий имеет следующий синтаксис:
REVOKE { | ALL PRIVILEGES}
ON
FROM { | PUBLIC } {CASCADE | RESTRICT }
Параметры CASCADE или RESTRICT определяют, каким образом должна производиться отмена привилегий. Параметр CASCADE отменяет привилегии не только пользователя, который непосредственно упоминался в операторе GRANT при предоставлении ему привилегий, но и всем пользователям, которым этот пользователь присвоил привилегии, воспользовавшись параметром WITH GRANT OPTION.
Например, при использовании операции:
REVOKE ALL PRIVILEGES
ON Tabl
TO user4 CASCADE
будут отменены привилегии и пользователя user3, которому пользователь user4 успел присвоить привилегии.
Параметр RESTRICKT ограничивает отмену привилегий только пользователю, непосредственно упомянутому в операторе REVOKE. Но при наличии делегированных привилегий этот оператор не будет выполнен. Так, например, операция:
REVOKE ALL PRIVILEGES
ON Tabl
TO user4 RESTRICT
280
не будет выполнена, потому что пользователь user4 передал часть своих полномочий пользователю user5.
Посредством оператора REVOKE можно отобрать все или только некоторые из ранее присвоенных привилегий по работе с конкретным объектом. При этом из описания синтаксиса оператора отмены привилегий видно, что можно отобрать привилегии одним оператором сразу у нескольких пользователей или у целой группы PUBLIC.
Поэтому корректным будет следующее использование оператора REVOKE:
REVOKE INSERT
ON Tabl
TO user2.user4 CASCADE
При работе с другими объектами изменяется список операций, которые используются в операторах GRANT и REVOKE.
По умолчанию действие, соответствующее запуску (исполнению) хранимой процедуры, назначается всем членам группы PUBLIC.
Если вы хотите изменить это условие, то после создания хранимой процедуры необходимо записать оператор REVOKE.
REVOKE EXECUTE
ON COUNT_EX
TO PUBLIC CASCADE
И теперь мы можем назначить новые права пользователю user4.
GRANT EXECUTE
ON COUNT_EX
TO user4
Системный администратор может разрешить некоторому пользователю создавать и изменять таблицы в некоторой БД. Тогда он может записать оператор предоставления прав следующим образом:
GRANT CREATE TABLE. ALTER TABLE. DROP TABLE
ON DB_LIB
TO user1
В этом случае пользователь userl может создавать, изменять или удалять таблицы в БД DB_LIB, однако он не может разрешить создавать или изменять таблицы в этой БД другим пользователям, потому что ему дано разрешение без права делегирования своих возможностей.
В некоторых СУБД пользователь может получить права создавать БД. Например, в MS SQL Server системный администратор может предоставить пользователю main_user право на создание своей БД на данном сервере. Это может быть сделано следующей командой:
GRANT CREATE DATABASE
ON SERVER_0
TO main user
281
По принципу иерархии пользователь main_user, создав свою БД, теперь может предоставить права на создание или изменение любых объектов в этой БД другим пользователям.
В СУБД, которые поддерживают однобазовую архитектуру, такие разрешения недопустимы. Например, в СУБД Oracle на сервере создается только одна БД, но пользователи могут работать на уровне подсхемы (части таблиц БД и связанных с ними объектов). Поэтому там вводится понятие системных привилегий. Их очень много, 80 различных привилегий.
Для того чтобы разрешить пользователю создавать объекты внутри этой БД, используется понятие системной привилегии, которая может быть назначена одному или нескольким пользователям. Они выдаются только на действия и конкретный тип объекта. Поэтому, если вы, как системный администратор, предоставили пользователю право создания таблиц (CREATE TABLE), то для того чтобы он мог создать триггер для таблицы, ему необходимо предоставить еще одну системную привилегию CREATE TRIGGER. Система защиты в Oracle считается одной из самых мощных, но это имеет и обратную сторону - она весьма сложная. Поэтому задача администрирования в Oracle требует хорошего знания как семантики принципов поддержки прав доступа, так и физической реализации этих возможностей.
Обобщенная архитектура СУБД
Мы рассмотрели отдельные аспекты работы СУБД. Теперь попробуем кратко обобщить все, что узнали, и построим некоторую условную обобщенную структуру СУБД. На рис. 14.1 изображена такая структура. Здесь условно показано, что СУБД должна управлять внешней памятью, в которой расположены файлы с данными, файлы журналов и файлы системного каталога.
С другой стороны, СУБД управляет и оперативной памятью, в которой располагаются буфера с данными, буфера журналов, данные системного каталога, которые необходимы для поддержки целостности и проверки привилегий пользователей. Кроме того, в оперативной памяти во время работы СУБД располагается информация, которая соответствует текущему состоянию обработки запросов, там хранятся планы выполнения скомпилированных запросов и т. д.
Модуль управления внешней памятью обеспечивает создание необходимых структур внешней памяти как для храпения данных, непосредственно входящих в БД, так и для служебных целей, например для ускорения доступа к данным в некоторых случаях (обычно для этого используются индексы). Как мы рассматривали ранее, в некоторых реализациях СУБД активно используются возможности существующих файловых систем, в других работа производится вплоть до уровня устройств внешней памяти. Но подчеркнем, что в развитых СУБД пользователи в любом случае не обязаны знать, использует ли СУБД файловую систему, п если использует, то как организованы файлы. В частности, СУБД поддерживает собственную систему именования объектов БД.
Модуль управления буферами оперативной памяти предназначен для решения задач эффективной буферизации, которая используется практически для выполнения всех остальных функций СУБД.
Условно оперативную память, которой управляет СУБД, можно представить как совокупность буферов, хранящих страницы данных, буферов, храпящих страницы журналов транзакций и область совместно используемого пула (см. рис. 14.2). Последняя область содержит фрагменты системного каталога, которые необходимо постоянно держать в оперативной памяти, чтобы ускорить обработку запросов пользователей, и область операторов SQL с курсорами.
Фрагменты
286
системного каталога в некоторых реализациях называются словарем данных. В стандарте SQL2 определены общие требования к системному каталогу.
Рис. 14.1. Обобщенная структура СУБД
Рис. 14.2. Оперативная память, управляемая СУБД
Системный каталог в реляционных СУБД представляет собой совокупность специальных таблиц, которыми владеет сама СУБД. Таблицы системного каталога создаются автоматически при установке программного обеспечения сервера БД. Все системные таблицы обычно объединяются некоторым специальным "системным идентификатором пользователя". При обработке SQL - запросов СУБД постоянно обращается к этим таблицам. В некоторых СУБД разрешен ограниченный доступ пользователей к ряду системных таблиц, однако только в режиме чтения. Только системный администратор имеет некоторые права на модификацию данных в некоторых системных таблицах.
Каждая таблица системного каталога содержит информацию об отдельных структурных элементах БД. В стандарте SQL2 определены следующие системные таблицы:
287
Таблица 14.1. Содержание системного каталога по стандарту SQL2
| Системная таблица | Содержание |
| USERS | Одна строка для каждого идентификатора пользователя с зашифрованным паролем |
| SCHEMA | Одна строка для каждой информационной схемы |
| DATA_TYPE_DESCRIPTION | Одна строка для каждого домена или столбца, имеющего определенный тип данных |
| DOMAINS. | Одна строка для каждого домена |
| DOMAIN_CONSTRAINS | Одна строка для каждого ограничивающего условия, наложенного на домен |
| TABLES | Одна строка для каждой таблицы с указанием имени, владельца, количества столбцов, размеров данных столбцов, и т. д. |
| VIEWS | Одна строка для каждого представления с указанием имени, имени владельца, запроса, который определяет представление и т. д. |
| COLUMNS | Одна строка для каждого столбца с указанием имени столбца, имени таблицы или представления, к которому он относится, типа данных столбца, его размера, допустимости или недопустимости неопределенных значений (NULL ) и т. д. |
| VIEW_TABLE_USAGE | Одна строка для каждой таблицы, на которую имеется ссылка в каком-либо представлении (если представление многотабличное, то для каждой таблицы заносится одна строка) |
| VIEW_COLUMN_USAGE | Одна строка для каждого столбца, на который имеется ссылка в некотором представлении |
| TABLE_CONSTRAINS | Одна строка для каждого условия ограничения, заданного в каком-либо определении таблицы |
| KEY_COLUMN_USAGE | Одна строка для каждого столбца, на который наложено условие уникальности и который присутствует в определении первичного или внешнего ключа (если первичный или внешний ключ заданы несколькими столбцами, то для каждого из них задается отдельная строка) |
| REFERENTIAL_CONSTRAINTS | Одна строка для каждого внешнего ключа, присутствующего в определении таблицы |
| CHECK_ CONSTRAINTS | Одна строка для каждого условия проверки, заданного в определении таблицы |
| CHECK_TABLE_USAGE | Одна строка для каждой таблицы, на которую имеется ссылка в условиях проверки, ограничительном условии для домена или всей таблицы |
288
| Системная таблица | Содержание |
| CHECK_COLUMN_USAGE | Одна строка для каждого столбца, на который имеется ссылка в условии проверки, ограничительном условии для домена или ином ограничительном условии |
| ASSERTIONS | Одна строка для каждого декларативного утверждения целостности |
| TABLE_PRIVILEGES | Одна строка для каждой привилегии, предоставленной на какую-либо таблицу |
| COLUMN_PRIVILEGES | Одна строка для каждой привилегии, предоставленной на какой-либо столбец |
| USAGE_PRIVILEGES | Одна строка для каждой привилегии, предоставленной на какой-либо домен, набор символов и т. д. |
| CHARACTER_SETS | Одна строка для каждого заданного набора символов |
| COLLATIONS | Одна строка для заданной последовательности |
| TRANSLATIONS | Одна строка для каждого заданного преобразования |
| SQL_LAGUAGES | Одна строка для каждого заданного языка, поддерживаемого СУБД |
Стандарт SQL2 не требует, чтобы СУБД в точности поддерживала требуемый набор системных таблиц. Стандарт ограничивается требованием того, чтобы для рядовых пользователей были доступны некоторые специальные представления системного каталога. Поэтому системные таблицы организованы по-разному в разных СУБД и имеют различные имена, но большинство СУБД предоставляют ряд основных представлений рядовым пользователям.
Кроме того, системный каталог отражает некоторые дополнительные возможности, предоставляемые конкретными СУБД. Так, например, в системном каталоге Oracle присутствуют таблицы синонимов.
Область SQL содержит данные связывания, временные буферы, дерево разбора и план выполнения для каждого оператора SQL, переданного серверу БД. Область разделяемого пула ограничена в размере, поэтому, возможно, в ней не могут поместиться все операторы SQL, которые были выполнены с момента запуска сервера БД. Ядро СУБД удаляет старые, давно не используемые операторы, освобождая память под новые операторы SQL. Если пользователь выполняет запрос, план выполнения которого уже хранится в разделяемом пуле, то СУБД не производит его разбор и построение нового плана, она сразу запускает его на выполнение, возможно, с новыми параметрами.
Модуль управления транзакциями поддерживает механизмы фиксации и отката транзакций, он связан с модулем управления буферами оперативной памяти и обеспечивает сохранение всей информации, которая требуется после мягких или жестких сбоев в системе. Кроме того, модуль управления транзакциями содержит специальный механизм поиска тупиковых ситуаций или взаимоблокировок и реализует одну из принятых стратегий принудительного завершения транзакций для развязывания тупиковых ситуаций.
289
Особое внимание надо обратить на модуль поддержки SQL. Это практически транслятор с языка SQL и блок оптимизации запросов.
В общем, оптимизация запросов может быть разделена на синтаксическую и семантическую.
Горизонтальное представление
Этот вид представления широко применяется для уменьшения объема реальных таблиц в обработке и ограничения доступа пользователей к закрытой для них информации. Так, например, правилом хорошего тона считается, что руководитель подразделения в некоторой фирме может видеть оклады и результаты работы только своих сотрудников, в этом случае для него создается горизонтальное представление, в которое загружены строки общей таблицы сотрудников, работающих в его подразделении.
Например, у нас есть таблица "Сотрудник" (EMPLOYEE) с полями "Табельный номер" (T_NUM), "ФИО" (NAME), "должность"(РOSITION), "оклад"(SALARY), "надбавка"(PREMIUM), "отдел" (DEPARTMENT).
Для приложения, с которым работает начальник отдела продаж, будет создано представление
CREATE VIEW SAL_DEPT
AS
SELECT *
FROM EMPLOYEE
WHERE DEPARTMENT" "Отдел продаж"
159
159 :: Содержание
Гранулированные синхронизационные захваты
Мы уже говорили, что объектами блокирования могут быть объекты разного уровня, начиная с целой БД и заканчивая кортежем.
Понятно, что чем крупнее объект синхронизационного захвата (неважно, какой природы этот объект - логический или физический), тем меньше синхронизационных захватов будет поддерживаться в системе, и при этом, соответственно, будут меньшие накладные расходы. Более того, если выбрать в качестве уровня объектов для захватов файл или отношение, то будет решена даже проблема фантомов (если это не ясно сразу, посмотрите еще раз на формулировку проблемы фантомов и определение двухфазного протокола захватов).
Но вся беда в том, что при использовании для захватов крупных объектов возрастает вероятность конфликтов транзакций и тем самым уменьшается допускаемая степень их параллельного выполнения. Фактически при укрупнении
242
объекта синхронизационного захвата мы умышленно огрубляем ситуацию и видим конфликты в тех ситуациях, когда на самом деле конфликтов нет. Действительно, если транзакция Т1 обрабатывает первую, пятую и двадцатую строку в таблице R1, но блокирует всю таблицу, то транзакция Т2, которая обрабатывает шестую и восьмую строки той же таблицы не сможет получить к ним доступ, хотя на уровне строк никаких конфликтов нет.
В большинстве современных систем используются покортежные, то есть построковые синхронизационные захваты.
Однако нелепо было бы применять покортежную блокировку в случае выполнения, например, операции удаления всего отношения или удаления всех строк в отношении.
Подобные рассуждения привели к понятию гранулированных синхронизационных захватов и разработке соответствующего механизма.
При применении этого подхода синхронизационные захваты могут запрашиваться по отношению к объектам разного уровня: файлам, отношениям и кортежам. Требуемый уровень объекта определяется тем, какая операция выполняется (например, для выполнения операции уничтожения отношения объектом синхронизационного захвата должно быть все отношение, а для выполнения операции удаления кортежа - этот кортеж).
Объект любого уровня может быть захвачен в режиме s (разделяемом) или x (монопольном). Вводится специальный протокол гранулированных захватов и определены новые типы захватов: перед захватом объекта в режиме s или x соответствующий объект более высокого уровня должен бить захвачен в режиме IS. IX или SIX.
IS (Intented for Shared lock, предваряющий разделяемую блокировку) по отношению к некоторому составному объекту 0 означает намерение захватить некоторый входящий в 0 объект в совместном режиме. Например, при намерении читать кортежи из отношения R это отношение должно быть захвачено в режиме IS (а до этого в таком же режиме должен быть захвачен файл).
IX (Intented for exclusive lock, предваряющий жесткую блокировку) по отношению к некоторому составному объекту 0 означает намерение захватить некоторый входящий в 0 объект в монопольном режиме. Например, при намерении удалять кортежи из отношения R это отношение должно быть захвачено в режиме IX (а до этого в таком же режиме должен быть захвачен файл).
SIX (Shared, Intented for exclusive lock, разделяемая блокировка объекта, предваряющая дальнейшие жесткие блокировки его составляющих) по отношению к некоторому составному объекту О означает совместный захват всего этого объекта с намерением впоследствии захватывать какие-либо входящие в него объекты в монопольном режиме. Например, если выполняется длинная операция просмотра отношения с возможностью удаления некоторых просматриваемых кортежей, то экономичнее всего захватить это отношение в режиме SIX (а до этого захватить файл в режиме IS).
Весьма трудно описать словами все возможные ситуации. Приведем полную таблицу совместимости захватов, анализируя которую можно выявить все случаи (см. табл. 11.2).
243
Таблица 11.2. Матрица совместимости блокировок.
| L1\L2 | X | S | IX | IS | SIX |
| Нет блокировки | Да | Да | Да | Да | Да |
| X | Нет | Нет | Нет | Нет | Нет |
| S | Нет | Да | Нет | Да | Нет |
| IX | Нет | Нет | Да | Да | Нет |
| IS | Нет | Да | Да | Да | Да |
| SIX | Нет | Нет | Нет | Да | Нет |
Протокол гранулированных захватов требует соблюдения следующих правил:
Прежде чем транзакция установит S - блокировку на данный кортеж, она должна установить блокировку IS или другую, более сильную блокировку на отношение, в котором содержится данный кортеж.
Прежде чем транзакция установит Х - блокировку на данный кортеж, она должна установить IХ - блокировку или другую более сильную блокировку на отношение, в которое входит кортеж.
Блокировка L1 называется более сильной по отношению к блокировке L2 тогда и только тогда, когда для любой конфликтной ситуации (Нет - недопустимо) в столбце блокировки L2 в некоторой строке матрицы совместимости блокировок (см. табл. 11.2) существует также конфликт в столбце блокировки L1 в той же строке.
Диаграмма приоритетов блокировок приведена на рис. 11.12.
Рис. 11.12. Диаграмма приоритета блокировок различных типов
Хранимые процедуры
С точки зрения приложений, работающих с БД, хранимые процедуры (Stored Procedure) - это подпрограммы, которые выполняются на сервере. По отношению к БД - это объекты, которые создаются и хранятся в БД. Они могут быть вызваны из клиентских приложений. При этом одна процедура может быть использована в любом количестве клиентских приложений, что позволяет существенно сэкономить трудозатраты на создание прикладного программного обеспечения и эффективно применять стратегию повторного использования кода. Так же как и любые процедуры в стандартных языках программирования, хранимые процедуры могут иметь входные и выходные параметры или не иметь их вовсе.
Хранимые процедуры могут быть активизированы не только пользовательскими приложениями, но и триггерами.
Хранимые процедуры пишутся на специальном встроенном языке программирования, они могут включать любые операторы SQL, а также включают некоторый набор операторов, управляющих ходом выполнения программ, которые во многом схожи с подобными операторами процедурно ориентированных языков программирования. В коммерческих СУБД для написания текстов хранимых процедур используются собственные языки программирования, так, в СУБД Oracle для этого используется язык PL /SQL, а в MS SQL Server и System 11 фирмы Sybase используется язык Transact SQL. В последних версиях Oracle объявлено использование языка Java для написания хранимых процедур.
259
Хранимые процедуры являются объектами БД. Каждая хранимая процедура компилируется при первом выполнении, в процессе компиляции строится оптимальный план выполнения процедуры. Описание процедуры совместно с планом ее выполнения хранится в системных таблицах БД.
Для создания хранимой процедуры применяется оператор SQL CREATE PROCEDURE.
По умолчанию выполнить хранимую процедуру может только ее владелец, которым является владелец БД, и создатель хранимой процедуры. Однако владелец хранимой процедуры может делегировать права на ее запуск другим пользователям.
Имя хранимой процедуры является идентификатором в языке программирования, на котором она пишется, и должно удовлетворять всем требованиям, которые предъявляются к идентификаторам в данном языке.
В MS SQL Server хранимая процедура создается оператором:
CREATE PRO[EDURE] [;]
[{@параметр1 тип_данных}
[VARYING] [= ] [OUTPUT]]
[, .параметрN...]
[ WITH
{ RECOMPILE
| ENCRYPTION
| RECOMPILE, ENCRYPTION}]
[FOR REPLICATION]
AS
Тело процедуры
Здесь необязательное ключевое слово VARYING определяет заданное значение по умолчанию для определенного ранее параметра.
Ключевое слово RECOMPILE определяет режим компиляции создаваемой хранимой процедуры. Если задано ключевое слово RECOMPILE, то процедура будет перекомпилироваться каждый раз, когда она будет вызываться на исполнение. Это может резко замедлить исполнение процедуры. Но, с другой стороны, если данные, обрабатываемые данной хранимой процедурой, настолько динамичны, что предыдущий план исполнения, составленный при ее первом вызове, может быть абсолютно неэффективен при последующих вызовах, то стоит применять данный параметр при создании этой процедуры.
Ключевое слово ENCRYPTION определяет режим, при котором исходный текст хранимой процедуры не сохраняется в БД. Такой режим применяется для того, чтобы сохранить авторское право на интеллектуальную продукцию, которой и являются хранимые процедуры. Часто такой режим применяется, когда вы ставите готовую базу заказчику и не хотите, чтобы исходные тексты разработанных вами хранимых процедур были бы доступны администратору БД, работающему у заказчика. Однако надо помнить, что если вы захотите отредактировать текст хранимой процедуры сами, то вы его не сможете извлечь из БД тоже, его
260
надо будет хранить отдельно в некотором текстовом файле. И это не самое плохое, но вот в случае восстановления БД после серьезной аварии для перекомпиляции потребуются первоначальные исходные тексты всех хранимых процедур. Поэтому защита вещь хорошая, но она усложняет сопровождение и модификацию хранимых процедур.
Однако кроме имени хранимой процедуры все остальные параметры являются необязательными. Процедуры могут быть процедурами или процедурами-функциями. И эти понятия здесь трактуются традиционно, как в языках программирования высокого уровня.
Хранимая процедура- функция возвращает значение, которое присваивается переменной, определяющей имя процедуры. Процедура в явном виде не возвращает значение, но в ней может быть использовано ключевое слово OUTPUT, которое определяет, что данный параметр является выходным.
Рассмотрим несколько примеров простейших хранимых процедур.
/* процедура проверки наличия экземпляров данной книги
параметры:
@ISBN шифр книги
процедура возвращает параметр, равный количеству экземпляров
Если возвращается ноль, то это значит, что нет свободных экземпляров данной
книги в библиотеке.
*/
CREATE PROCEDURE COUNT_EX (@ISBN varchar(12))
AS
/* определим внутреннюю переменную */
DECLARE @TEK_COUNT int
/* выполним соответствующий оператор SELECT
Будем считать только экземпляры, которые в настоящий момент находятся
не на руках у читателей, а в библиотеке */
select @TEK_COUNT = select count(*) FROM EXEMPLAR WHERE ISBN = @ISBN
AND READER_ID Is NULL AND EXIST = True
/* 0 - ноль означает, что нет ни одного свободного экземпляра данной книги
в библиотеке */
RETURN @TEK_COUNT
Хранимая процедура может быть вызвана несколькими способами. Простейший способ - это использование оператора:
EXEC ...
...
При этом все входные и выходные параметры должны быть заданы обязательно и в том порядке, в котором они определены в процедуре.
261
Например, если мне надо найти число экземпляров книги "Oracle8. Энциклопедия пользователя", которая имеет ISBN 966-7393-08-09, то текст вызова ранее созданной хранимой процедуры может быть следующим:
/*определили две переменные
@Ntek - количество экземпляров данной книги в наличие в библиотеке
@ISBN - международный шифр книги */
declare @Ntek int
DECLARE @ISBN VARCHAR(14)
/* Присвоим значение переменной @ISBN */
Select @ISBN = ?966-7393-08-09?
/* Присвоим переменной @Ntek результаты выполнения хранимой процедуры
COUNT_EX */
EXEC @Ntek - COUNT_EX @ISBN
Если у вас определено несколько версий хранимой процедуры, то при вызове вы можете указать номер конкретной версии для исполнения.
Так, например, в версии 2 процедуры COUNT_EX последний оператор исполнения этой процедуры имеет вид: /
EXEC @Ntek = COUNT_EX:2 @ISBN
Однако если в процедуре определены значения входных параметров по умолчанию, то при запуске процедуры могут быть указаны значения не всех параметров. В этом случае оператор вызова процедуры может быть записан в следующем виде:
EXEC =...
=...
Например, создадим процедуру, которая считает количество книг, изданных конкретным издательством в конкретном году. При создании процедуры зададим для года издания по умолчанию значение текущего года.
CREATE PROCEDURE COUNT_BOOKS (@YEARIZD Int - Year(GetDate( )).
@PUBLICH varchar(20))
/* процедура подсчета количества книг конкретного издательства, изданных
в конкретном году
параметры:
@YEARIZD Int год издания
@PUBLICH название издательства
*/
AS
DECLARE @TEK_Count int
Select @TEK count - Select COUNT(ISBN)
262
From BOOKS
Where YEARIZD = @YEARIZD AND PUBLICH =@PUBLICH
/* одновременно с исполнением оператора Select мы присваиваем результаты его работы определенной ранее переменной @TEK_Count */
/* при формировании результата работы нашей процедуры мы должны учесть,
что в нашей библиотеке, возможно, нет ни одной книги некоторого издательства
для заданного года. Результат выполнения запроса SELECT в этом случае будет
иметь неопределенное значение, но анализировать все-таки лучше числовые
значения. Поэтому в качестве возвращаемого значения мы используем результаты
работы специальной встроенной функции Transact SQL COALESCE (nl.n2, ... ,nm).
которая возвращает первое конкретное, то есть не равное NULL, значение из
списка значений nl.n2, ... ,nm. */
Return COALESCE (@TEK_Count.O)
Теперь вызовем эту процедуру, для этого подготовим переменную, куда можно поместить результаты выполнения процедуры.
declare @N int •
Exec @N - COUNT_BOOKS @PUBLICH = ?Питер?
В переменной @N мы получим количество книг в нашей библиотеке, изданных издательствам "Питер" в текущем году.
Мы можем обратиться к этой процедуре и задав все параметры:
Exec @N = COUNT_BOOKS @PUBLICH = ?BHW?. @YEARIZD = 1999
Тогда получим количество книг, изданных издательством "BHW" в 1999 году и присутствующих в нашей библиотеке.
Если мы задаем параметры по именам, то нам необязательно задавать их в том порядке, в котором они описаны при создании процедуры.
Каждая хранимая процедура является объектом БД. Она имеет уникальное имя и уникальный внутренний номер в системном каталоге. При изменении текста хранимой процедуры мы должны сначала уничтожить данную процедуру как объект, хранимый в БД, и только после этого записать на ее место новую. Следует отметить, что при удалении хранимой процедуры удаляются одновременно все ее версии, нельзя удалить только одну версию хранимой процедуры.
Для того чтобы автоматизировать процесс уничтожения старой процедуры и замены ее на новую, в начале текста хранимой процедуры можно выполнить проверку наличия объекта типа "хранимая процедура" с данным именем в системном каталоге и при наличии описания данного объекта удалить его из системного каталога. В этом случае текст хранимой процедуры предваряется специальным оператором проверки и может иметь, например, следующий вид:
/* проверка существования в системном каталоге объекта с данным именем
и типом, созданного владельцем БД */
if exists (select * from sysobjects where id = object_id(?dbo.NEW_BOOKS?) and sysstat & Oxf = 4)
263
/* если объект существует, то сначала его удалим из системного каталога */
drop procedure dbo.NEW_BOOKS
GO
CREATE PROCEDURE NEW_BOOKS (@ISBN varchar(12).@TITL varchar(255).@AUTOR varchar(30),@COAUTOR varchar(30),@YEARIZD Int.SPACES INT,@NUM_EXEMPL INT)
/* процедура ввода новой книги с указанием количества экземпляров данной книги параметры
@ISBN varchar(12) шифр книги
@TITL varchar(255) название
@AUTOR varcharOO) автор
@COAUTOR varcharOO) соавтор
@YEARIZD Int год издания
@PAGES INT количество страниц
@NUM_EXEMPL INT количество экземпляров
*/
AS
/*опишем переменную, в которой будет храниться количество оставшихся
не оприходованных экземпляров книги, т.е. таких, которым еще не заданы
инвентарные номера */
DECLARE @ТЕК int
/ *вводим данные о книге в таблицу BOOKS */
INSERT INTO BOOKS VALUES(@ISBN.@TITL.@AUTOR.@COAUTOR.@YEARIZD.@PAGES)
/* назначение значения текущего счетчика оставшихся к вводу экземпляров*/
SELECT @TEK = @NUM_EXEMPL
/* организуем цикл для ввода новых экземпляров данной книги */
WHILE @TEK>0 /* пока количество оставшихся экземпляров больше нуля */
BEGIN
/* так как для инвентарного номера экземпляра книги мы задали свойство
IDENTITY, то нам не надо вводить инвентарный номер. СУБД сама автоматически
вычислит его, добавив единицу к предыдущему, введет при выполнении оператора
ввода INSERT.
Поле, определяющее присутствие экземпляра в библиотеке (EXIST) - логическое
поле, мы введем туда значение TRUE,которое соответствует присутствию
экземпляра книги в библиотеке.
Даты взятия и возврата мы можем не заполнять, тогда по умолчанию СУБД
подставит туда значение, соответствующее 1 января 1900 года, если мы не хотим
хранить такие бессмысленные данные, то можем ввести для обоих полей дата
время, значения текущей даты. */
264
Insert Into EXEMPLAR (ISBN.DATA_IN,DATA_OUT,EXIST)
VALUES (@ISBN.GetDate().GetDate()).TRUE)
/* изменение текущего значения счетчика количества оставшихся экземпляров */
SELECT @ТЕК = @ТЕК - 1
End /* конец цикла ввода данных о экземпляре книги*/
GO
Если мы не использовали инкрементное поле в качестве инвентарного номера экземпляра, то мы могли бы сами назначать инвентарный номер, увеличивая на единицу номер последнего хранимого в библиотеке экземпляра книги. Можно было бы попробовать просто сосчитать количество существующих экземпляров в библиотеке, но мы могли удалить некоторые, и тогда номер нового экземпляра может быть уже использован, и мы не сможем ввести данные, система не позволит нам нарушить уникальность первичного ключа.
Текст процедуры в этом случае будет иметь вид:
/* проверка существования в системном каталоге объекта с данным именем
и типом, созданного владельцем БД */
If exists (select * from sysobjects where Id = object_id(?dbo.NEW_BOOKS?) and sysstat & Oxf = 4)
/* если объект существует, то сначала его удалим из системного каталога */
drop procedure dbo.NEW_BOOKS
CREATE PROCEDURE NEW_BOOKS (@SBN varchar(12).@TITL varchar(255).@AUTOR
varchar(30),@COAUTOR varchar(30).@YEARIZD 1nt,@PAGES INT,@NUM_EXEMPL INT)
/* процедура ввода новой книги с указанием количества экземпляров данной книги
параметры
@ISBN varchar(12) шифр книги
@TITL varchar(255) название
@AUTOR varcharOO) автор
@COAUTOR varcharOO) соавтор
@YEARIZD int год издания
@PAGES INT количество страниц
@NUM_EXEMPL INT количество экземпляров
*/
AS
DECLARE @TEK int
declare @INV int
INSERT INTO BOOKS VALUES(@ISBN.@TITL.@AUTOR.@COAUTOR,@YEARIZD.@PAGES)
/* назначение значения текущего счетчика оставшихся к вводу экземпляров*/
SELECT @ТЕК = @NUM_EXEMPL
/* определение максимального значения инвентарного номера в библиотеке */
265
SELECT @INV - SELECT MAX( ID_EXEMPLAR) FROM EXEMPLAR
/* организуем цикл для ввода новых экземпляров данной книги */
WHILE @TEK>0 /* пока количество оставшихся экземпляров больше нуля */
BEGIN
insert Into EXEMPLAR (IDJXEMPLAR.ISBN.DATA_IN.DATA_OUT.EXIST)
VALUES (@INV,@ISBN.GETDATE().GetDate(). TRUE)
/* изменение текущих значений счетчика и инвентарного номера */
SELECT @ТЕК = @ТЕК - 1
SELECT @INV = @INV + 1
End /* конец цикла ввода данных о экземпляре книги*/
GO
Хранимые процедуры могут вызывать одна другую. Создадим хранимую процедуру, которая возвращает номер читательского билета для конкретного читателя.
if exists (select * from sysobjects where id = object_id(?dbo. CK_READER?) and sysstat & Oxf = 4)
/* если объект существует, то сначала его удалим из системного каталога */
drop procedure dbo.CK_READER
/* Процедура возвращает номер читательского билета, если читатель есть и 0 в
противном случае.
В качестве параметров передаем фамилию и дату рождения */
CREATE PROCEDURE CK_READER (@FIRST_NAME varchar(30) ,@BIRTH_DAY varchar(12))
AS
/*опишем переменную, в которой будет храниться номер читательского билета*/
DECLARE @NUM_READER INT
/* определение наличия читателя */
select @NUM_READER = select NUM_READER from READERS
WHERE FIRST_NAME = @ FIRST_NAME AND
AND convert (varchar (8) .BIRTH_DAY.4)=@BIRTH_DAY
RETURN COALESCE(@NUM_READER.0)
Мы здесь использовали функцию преобразования типа данных dataTime в тип данных varchar(8). Это было необходимо сделать для согласования типов данных при выполнении операции сравнения. Действительно, входная переменная @BIRTH_DAY имеет символьный тип (varchar), а поле базы данных BIRTH_DAY имеет тип SmallDateTime.
Хранимые процедуры допускают наличие нескольких выходных параметров. Для этого каждый выходной параметр должен после задания своего типа данных иметь дополнительное ключевое слово OUTPUT. Рассмотрим пример хранимой процедуры с несколькими выходными параметрами.
266
Создадим процедуру ввода нового читателя, при этом внутри процедуры выполним проверку наличия в нашей картотеке данного читателя, чтобы не назначать ему новый номер читательского билета. При этом выходными параметрами процедуры будут номер читательского билета, признак того, был ли ранее записан читатель с данными характеристиками в нашей библиотеке, а если он был записан, то сколько книг за ним числится.
/* проверка наличия данной процедуры в нашей БД*/
if exists (select * from sysobjects where id =
object_id(N?[dbo] [NEW_READER]?) and OBJECTPROPERTYdd. N?sProcedure?) = 1)
drop procedure [dbo] [NEW_READER]
GO
/* процедура проверки существования читателя с заданными значениями вводимых
параметров
Процедура возвращает новый номер читательского билета, если такого читателя не
было сообщает старый номер и количество книг которое должен читатель в
противном случае */
CREATE PROCEDURE NEW_READER (@NAME_READER varchar(30).@ADRES
va rcha r(40).@HOOM_PHONE char(9).@WORK_PHONE char(9).
@BIRTH_DAY varchar(8),
@NUM_READER int OUTPUT,
/* выходной параметр, определяющий номер читательского билета*/
@Y_N int OUTPUT.
/* выходной параметр, определяющий был ли читатель ранее записан
в библиотеку*/
@COUNT_BOOKS int OUTPUT
/* выходной параметр, определяющий количество книг, которое числится
за читателем*/)
AS
/* переменная, в которой будет храниться номер читательского билета,
если читатель уже был записан в библиотеку */
DECLARE @N_R int
/* определение наличия читателя */
EXEC @N_R = CK_READER @NAME_READER,@BIRTH_DAY
IF @N_R= 0 Or @N_R Is Null
/* если читатель с заданными характеристиками не найден, т. е. переменной
@N_R присвоено значение нуль или ее значение неопределено, перейдем
к назначению для нового читателя нового номера читательского билета */
BEGIN
/* так как мы номер читательского билета определили как инкрементное поле,
то в операторе ввода мы его не указываем система сама назначит новому
читателю очередной номер */
267
INSERT INTO READER(NAME_READER,ADRES.HOOM_PHONE.WORK_PHONE.ВIRTH_DAY)
VALUES (@NAME_READER.@ADRES.@HOOM_PHONE.@WORK_PHONE.Convert(smal1datetime,
@BIRTH_DAY.4) )
/* в операторе INSERT мы должны преобразовать символьную переменную @BIRTH_DAY
в тип данных sma11datetime, который определен для поля дата рождения
BIRTH_DAY. Это преобразование мы сделаем с помощью встроенной функции
Transact SQL Convert */
/* теперь определим назначенный номер читательского билета */
select @NUM_READER = NUM_READER FROM READER
WHERE NAME_READER = @NAME_READER
AND convert(varchar(8),BIRTH_DAY.4)=@BIRTH_DAY
/* здесь мы снова используем функцию преобразования типа, но в этом случае
нам необходимо преобразовать поле BIRTH_DAY из типа smalldatetime
к типу varchar(8), в котором задан входной параметр @BIRTH_DAY */
Select @Y_N =0
/* присваиваем выходному параметру @Y_N значение 0 (ноль), что
соответствует тому,что данный читатель ранее в нашей библиотеке
не был записан */
Select @COUNT_BOOKS = 0
/* присваиваем выходному параметру, хранящему количество книг, числящихся
за читателем значение ноль */
Return 1
END
else
/* если значение переменной @ N_R не равно нулю, то читатель с заданными
характеристиками был ранее записан в нашей библиотеке */
BEGIN
/* определение количества книг у читателя с найденным номером читательского
билета */
select @COUNT_BOOKS = COUNT(INV_NUMBER) FROM EXEMPLAR WHERE
NUM_READER = @N_R
select @Count_books = COALESCE( @COUNT_BOOKS.0)
/* присваиваем выходному параметру @COUNT_BOOKS значение, равное количеству
книг, которые числятся за нашим читателем, если в предыдущем запросе
@COUNT_BOOKS было присвоено неопределенное значение, то мы заменим его
на ноль, используя для этого встроенную функцию COALESCE(@COUNT_BOOKS.0),
которая возвращает первое определенное значение из списка значений,
заданных в качестве ее параметров */
Select @Y_N = 1
/* присваиваем выходному параметру @Y_N значение 1, что соответствует тому,
что данный читатель ранее в нашей библиотеке был записан */
268
Select @NUM_READER = @N_R
/* присваиваем выходному параметру @NUM_READER определенный ранее номер
читательского билета */
return 0
end
Теперь посмотрим, как работает наша новая процедура, для этого в режиме интерактивного выполнения запросов (то есть в Query Analyzer MS SQL Server 7.0) запишем следующую последовательность команд:
-- пример использования выходных параметров при вызове процедуры
-- new reader
-- зададим необходимые нам переменные
Declare @K int. @N int. @B int
exec NEW_READER ?Пушкин В.В.?.?Литовский 22-90?.
?333-55-99?. ?444-66-88?. ?01.06.83?. @NUM_READER =@K OUTPUT.
@Y_N = @N OUTPUT.@COUNT_BOOKS = @B OUTPUT
-- теперь выведем результаты работы нашей процедуры используя ранее
-- определенные нами переменные
Select ?номер билета?,@К.?да - нет?,@N.?кол-во книг?.@В
Мы получим результат:
| Номер билета | да - нет | кол-во книг |
| 18 | 0 | 0 |
| Номер билета | да - нет | кол-во книг |
| 18 | 1 | 0 |
Теперь обратимся к оценке эффективности применения хранимых процедур.
Если рассмотреть этапы выполнения одинакового текста части приложения, содержащего SQL-операторы, самостоятельно на клиенте и в качестве хранимой процедуры, то можно отметить, что на клиенте выполняются все 5 этапов выполнения SQL-операторов, а хранимая процедура может храниться в БД в уже скомпилированном виде, и ее исполнение займет гораздо меньше времени (см. рис. 12.2).
Кроме того, хранимые процедуры, как уже упоминалось, могут быть использованы несколькими приложениями, а встроенные операторы SQL должны быть включены в каждое приложение повторно.
269
Рис. 12.2. Процесс выполнения операторов SQL на клиенте и процесс выполнения хранимой процедуры
Хранимые процедуры также играют ключевую роль в повышении быстродействия при работе в сети с архитектурой "клиент - сервер".
На рис. 12.3 показан пример выполнения последовательности операторов SQL на клиенте, а на рис. 12.4 показан пример выполнения той же последовательности операторов SQL, оформленных в виде хранимой процедуры. В этом случае клиент обращается к серверу только для выполнения команды запуска хранимой процедуры. Сама хранимая процедура выполняется на сервере. Объем пересылаемой по сети информации резко сокращается во втором случае.
Рис. 12.3. Сетевой трафик при выполнении встроенных SQL - операторов
270
Рис. 12.4. Сетевой трафик при выполнении хранимой процедуры на сервере
Иерархическая модель данных
Иерархическая модель данных является наиболее простой среди всех даталогических моделей. Исторически она появилась первой среди всех диалогических моделей: именно эту модель поддерживает первая из зарегистрированных промышленных СУБД IMS фирмы IBM.
Появление иерархической модели связано с тем, что в реальном мире очень многие связи соответствуют иерархии, когда один объект выступает как родительский, а с ним может быть связано множество подчиненных объектов. Иерархия проста и естественна в отображении взаимосвязи между классами объектов.
Основными информационными единицами в иерархической модели являются: база данных (БД), сегмент и поле. Поле данных определяется как минимальная, неделимая единица данных, доступная пользователю с помощью СУБД. Например, если в задачах требуется печатать в документах адрес клиента, но не требуется дополнительного анализа полного адреса, то есть города, улицы, дома, квартиры, то мы можем принять весь адрес за элемент данных, и он будет храниться полностью, а пользователь сможет получить его только как полную строку символов из БД. Если же в наших задачах существует анализ частей, составляющих адрес, например города, где расположен клиент, то нам необходимо выделить город как отдельный элемент данных, только в этом случае пользователь может
31
получить к нему доступ и выполнить, например, запрос на поиск всех клиентов, которые проживают в конкретном городе, например в Париже. Однако если пользователю понадобится и полный адрес клиента, то остальную информацию по адресу также необходимо хранить в отдельном поле, которое может быть названо, например, Сокращенный адрес. В этом случае для каждого клиента в БД хранится как Город, так и Сокращенный адрес.
Сегмент в терминологии Американской Ассоциации по базам данных DBTG (Data Base Task Group) называется записью, при этом в рамках иерархической модели определяются два понятия: тип сегмента или тип записи и экземпляр сегмента или экземпляр записи.
Тип сегмента - это поименованная совокупность типов элементов данных, в него входящих.
Экземпляр сегмента образуется из конкретных значений полей или элементов данных, в него входящих. Каждый тип сегмента в рамках иерархической модели образует некоторый набор однородных записей. Для возможности различия отдельных записей в данном наборе каждый тип сегмента должен иметь ключ или набор ключевых атрибутов (полей, элементов данных). Ключом называется набор элементов данных, однозначно идентифицирующих экземпляр сегмента. Например, рассматривая тип сегмента, описывающий сотрудника организации, мы должны выделить те характеристики сотрудника, которые могут его однозначно идентифицировать в рамках БД предприятия. Если предположить, что на предприятии могут работать однофамильцы, то, вероятно, наиболее надежным будет идентифицировать сотрудника по его табельному номеру. Однако если мы будем строить БД, содержащую описание множества граждан, например нашей страны, то, скорее всего, нам придется в качестве ключа выбрать совокупность полей, отражающих его паспортные данные.
В иерархической модели сегменты объединяются в ориентированный древовидный граф. При этом полагают, что направленные ребра графа отражают иерархические связи между сегментами: каждому экземпляру сегмента, стоящему выше по иерархии и соединенному с данным типом сегмента, соответствует несколько (множество) экземпляров данного (подчиненного) типа сегмента. Тип сегмента, находящийся на более высоком уровне иерархии, называется логически исходным по отношению к типам сегментов, соединенным с данным направленными иерархическими ребрами, которые в свою очередь называются логически подчиненными по отношению к этому типу сегмента. Иногда исходные сегменты называют сегментами-предками, а подчиненные сегменты называют сегментами - потомками.
Рис. 3.1. Пример иерархических связей между сегментами
На концептуальном уровне определяется понятие схемы БД в терминологии иерархической модели.
32
Схема иерархической БД представляет собой совокупность отдельных деревьев, каждое дерево в рамках модели называется физической базой данных.
Каждая физическая БД удовлетворяет следующим иерархическим ограничениям:
в каждой физической БД существует один корневой сегмент, то есть сегмент, у которого нет логически исходного (родительского) типа сегмента;
каждый логически исходный сегмент может быть связан с произвольным числом логически подчиненных сегментов;
каждый логически подчиненный сегмент может быть связан только с одним логически исходным (родительским ) сегментом.
Очень важно понимать различие между сегментом и типом сегмента - оно такое же, как между типом переменной и самой переменной: сегмент является экземпляром типа сегмента. Например, у нас может быть тип сегмента Группа (Номер, Староста) и сегменты этого типа, такие как (4305, Петров Ф. И.) или (383, Кустова Т. С.).
Между экземплярами сегментов также существуют иерархические связи. Рассмотрим, например, иерархический граф, представленный на рис. 3.2.
Рис. 3.2. Пример структуры иерархического дерева
Каждый тип сегмента может иметь множество соответствующих ему экземпляров. Между экземплярами сегментов также существуют иерархические связи.
На рис. 3.3 представлены 2 экземпляра иерархического дерева соответствующей структуры.
Рис. 3.3. Пример двух экземпляров данного дерева
33
Экземпляры - потомки одного типа, связанные с одним экземпляром сегмента-предка, называют "близнецами". Так, для нашего примера экземпляры b1, b2 и b3 являются "близнецами", но экземпляр b4 подчинен другому экземпляру родительского сегмента, и он не является "близнецом" по отношению к экземплярам b1, b2 и b3. Набор всех экземпляров сегментов, подчиненных одному экземпляру корневого сегмента, называется физической записью. Количество экземпляров-потомков может быть разным для разных экземпляров родительских сегментов, поэтому в общем случае физические записи имеют разную длину. Так, используя принцип линейной записи иерархических графов, пример на рис. 3.3 можно представить в виде двух записей:
| a1b1b2b3c1d1d2e1 | a2b4b5c2d3d4e2e3e4 |
| Запись 1 | Запись 2 |
Индексные файлы
Несмотря на высокую эффективность хэш - адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. В некоторых коммерческих системах индексными файлами называются также и файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. Мы будем придерживаться классической интерпретации индексных файлов и надеемся, что если вы столкнетесь с иной
169
интерпретацией, то сумеете разобраться в сути, несмотря на некоторую путаницу в терминологии. Наверное, это отчасти связано с тем, что область баз данных является достаточно молодой областью знаний, и несмотря на то, что здесь уже выработалась определенная терминология, многие поставщики коммерческих СУБД предпочитают свой упрощенный сленг при описании собственных продуктов. Иногда это связано с тем, что в целях рекламы они не хотят ссылаться на старые, хорошо известные модели и методы организации информации в системе, а изобретают новые названия при описании своих моделей, тем самым пытаясь разрекламировать эффективность своих продуктов. Хорошее знание принципов организации данных поможет вам объективно оценивать решения, предлагаемые поставщиками современных СУБД, и не попадаться на рекламные крючки.
Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл, а основная область образует файл, для которого создается индекс. Но нам удобнее рассматривать эти две части совместно, так как именно взаимодействие этих частей и определяет использование механизма индексации для ускорения доступа к записям.
Мы предполагаем, что сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.
В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом. Эти файлы имеют еще дополнительные названия, которые напрямую связаны с методами доступа к произвольной записи, которые поддерживаются данными файловыми структурами.
Файлы с плотным индексом называются также индексно - прямыми файлами, а файлы с неплотным индексом называются также индексно - последовательными файлами. Смысл этих названий нам будет ясен после того, как мы более подробно рассмотрим механизмы организации данных файлов.
170
169 :: 170 :: Содержание
Индивидуальный откат транзакции
Для того чтобы можно было выполнить по общему журналу индивидуальный откат транзакции, все записи в журнале по данной транзакции связываются в обратный список. Началом списка для незакончившихся транзакций является запись о последнем изменении базы данных, произведенном данной транзакцией. Для закончившихся транзакций (индивидуальные откаты которых уже невозможны) началом списка является запись о конце транзакции, которая обязательно вытолкнута во внешнюю память журнала. Концом списка всегда служит первая запись об изменении базы данных, произведенном данной транзакцией. Обычно в каждой записи проставляется уникальный идентификатор транзакции, чтобы можно было восстановить прямой список записей об изменениях базы данных данной транзакцией.
Итак, индивидуальный откат транзакции (еще раз подчеркнем, что это возможно только для незакончившихся транзакций) выполняется следующим образом:
Выбирается очередная запись из списка данной транзакции.
Выполняется противоположная по смыслу операция: вместо операции INSERT; выполняется соответствующая операция DELETE, вместо операции DELETE выполняется INSERT и вместо прямой операции UPDATE обратная операция UPDATE, восстанавливающая предыдущее состояние объекта базы данных.
226
Любая из этих обратных операций также заносится в журнал. Собственно, для индивидуального отката это не нужно, но при выполнении индивидуального отката транзакции может произойти мягкий сбой, при восстановлении после которого потребуется откатить такую транзакцию, для которой не полностью выполнен индивидуальный откат.
При успешном завершении отката в журнал заносится запись о конце транзакции. С точки зрения журнала такая транзакция является зафиксированной.
227
226 :: 227 :: Содержание
Инвертированные списки
До сих пор мы рассматривали структуры данных, которые использовались для ускорения доступа по первичному ключу. Однако достаточно часто в базах данных требуется проводить операции доступа по вторичным ключам. Напомним, что вторичным ключом является набор атрибутов, которому соответствует набор искомых записей. Это означает, что существует множество записей, имеющих одинаковые значения вторичного ключа. Например, в случае нашей БД "Библиотека" вторичным ключом может служить место издания, год издания. Множество книг могут быть изданы в одном месте, и множество книг могут быть изданы в один год.
Для обеспечения ускорения доступа по вторичным ключам используются структуры, называемые инвертированными списками, которые послужили основой организации индексных файлов для доступа по вторичным ключам.
Инвертированный список в общем случае - это двухуровневая индексная структура. Здесь на первом уровне находится файл или часть файла, в которой упорядочение расположены значения вторичных ключей. Каждая запись с вторичным ключом имеет ссылку на номер первого блока в цепочке блоков, содержащих номера записей с данным значением вторичного ключа. На втором уровне находится цепочка блоков, содержащих номера записей, содержащих одно и то же значение вторичного ключа. При этом блоки второго уровня упорядочены по значениям вторичного ключа.
И наконец, на третьем уровне находится собственно основной файл.
Механизм доступа к записям по вторичному ключу при подобной организации записей весьма прост. На первом шаге мы ищем в области первого уровня заданное значение вторичного ключа, а затем по ссылке считываем блоки второго уровня, содержащие номера записей с заданным значением вторичного ключа, а далее уже прямым доступом загружаем в рабочую область пользователя содержимое всех записей, содержащих заданное значение вторичного ключа.
На рис. 9.11 представлен пример инвертированного списка, составленного для вторичного ключа "Номер группы" в списке студентов некоторого учебного
заведения. Для более наглядного представления мы ограничили размер блока пятью записями (целыми числами).Рис. 9.11. Построение инвертированного списка по номеру группы для списка студентов
183
Для одного основного файла может быть создано несколько инвертированных списков по разным вторичным ключам.
Следует отметить, что организация вторичных списков действительно ускоряет поиск записей с заданным значением вторичного ключа. Но рассмотрим вопрос модификации основного файла.
При модификации основного файла происходит следующая последовательность действий:
Изменяется запись основного файла.
Исключается старая ссылка на предыдущее значение вторичного ключа.
Добавляется новая ссылка на новое значение вторичного ключа.
При этом следует отметить, что два последних шага выполняются для всех вторичных ключей, по которым созданы инвертированные списки. И, разумеется, такой процесс требует гораздо больше временных затрат, чем просто изменение содержимого записи основного файла без поддержки всех инвертированных списков.
Поэтому не следует безусловно утверждать, что введение индексных файлов (в том числе и инвертированных списков) всегда ускоряет обработку информации в базе данных. Отнюдь, если база данных постоянно изменяется, дополняется, модифицируется содержимое записей, то наличие большого количества инвертированных списков или индексных файлов по вторичным ключам может резко замедлить процесс обработки информации.
Можно придерживаться следующей позиции: если база данных достаточно стабильна и ее содержимое практически не меняется, то построение вторичных индексов действительно может ускорить процесс обработки информации.
История развития баз данных
В истории вычислительной техники можно проследить развитие двух основных областей ее использования. Первая область - применение вычислительной техники для выполнения численных расчетов, которые слишком долго или вообще невозможно производить вручную. Развитие этой области способствовало интенсификации методов численного решения сложных математических задач, появлению языков программирования, ориентированных на удобную запись численных алгоритмов, становлению обратной связи с разработчиками новых архитектур ЭВМ. Характерной особенностью данной области применения вычислительной техники является наличие сложных алгоритмов обработки, которые применяются к простым по структуре данным, объем которых сравнительно невелик.
Вторая область, которая непосредственно относится к нашей теме, - это использование средств вычислительной техники в автоматических или автоматизированных информационных системах. Информационная система представляет собой программно-аппаратный комплекс, обеспечивающий выполнение следующих функций:
надежное хранение информации в памяти компьютера;
выполнение специфических для данного приложения преобразований информации и вычислений;
предоставление пользователям удобного и легко осваиваемого интерфейса.
Обычно такие системы имеют дело с большими объемами информации, имеющей достаточно сложную структуру. Классическими примерами информационных систем являются банковские системы, автоматизированные системы управления предприятиями, системы резервирования авиационных или железнодорожных билетов, мест в гостиницах и т. д.
Вторая область использования вычислительной техники возникла несколько позже первой. Это связано с тем, что на заре вычислительной техники возможности компьютеров по хранению информации были очень ограниченными. Говорить о надежном и долговременном хранении информации можно только при наличии запоминающих устройств, сохраняющих информацию после выключения
10
электрического питания. Оперативная (основная) память компьютеров этим свойством обычно не обладает.
В первых компьютерах использовались два вида устройств внешней памяти - магнитные ленты и барабаны. Емкость магнитных лент была достаточно велика, но по своей физической природе они обеспечивали последовательный доступ к данным. Магнитные же барабаны (они ближе всего к современным магнитным дискам с фиксированными головками) давали возможность произвольного доступа к данным, но имели ограниченный объем хранимой информации.
Эти ограничения не являлись слишком существенными для чисто численных расчетов. Даже если программа должна обработать (или произвести) большой объем информации, при программировании можно продумать расположение этой информации во внешней памяти (например, на последовательной магнитной ленте), обеспечивающее эффективное выполнение этой программы. Однако в информационных системах совокупность взаимосвязанных информационных объектов фактически отражает модель объектов реального мира. А потребность пользователей в информации, адекватно отражающей состояние реальных объектов, требует сравнительно быстрой реакции системы на их запросы. И в этом случае наличие сравнительно медленных устройств хранения данных, к которым относятся магнитные ленты и барабаны, было недостаточным.
Можно предположить, что именно требования нечисловых приложений вызвали появление съемных магнитных дисков с подвижными головками, что явилось революцией в истории вычислительной техники. Эти устройства внешней памяти обладали существенно большей емкостью, чем магнитные барабаны, обеспечивали удовлетворительную скорость доступа к данным в режиме произвольной выборки, а возможность смены дискового пакета на устройстве позволяла иметь практически неограниченный архив данных.
С появлением магнитных дисков началась история систем управления данными во внешней памяти. До этого каждая прикладная программа, которой требовалось хранить данные во внешней памяти, сама определяла расположение каждой порции данных на магнитной ленте или барабане и выполняла обмены между оперативной памятью и устройствами внешней памяти с помощью программно-аппаратных средств низкого уровня (машинных команд или вызовов соответствующих программ операционной системы).Такой режим работы не позволяет или очень затрудняет поддержание на одном внешнем носителе нескольких архивов долговременно хранимой информации. Кроме того, каждой прикладной программе приходилось решать проблемы именования частей данных и структуризации данных во внешней памяти.
История развития SQL
SQL (Structured Query Language) - Структурированный Язык Запросов - стандартный язык запросов по работе с реляционными БД. Язык SQL появился после реляционной алгебры, и его прототип был разработан в конце 70-х годов в компании IBM Research. Он был реализован в первом прототипе реляционной СУБД фирмы IBM System R. В дальнейшем этот язык применялся во многих коммерческих СУБД и в силу своего широкого распространения постепенно стал стандартом "де-факто" для языков манипулирования данными в реляционных СУБД.
Первый международный стандарт языка SQL был принят в 1989 г. (далее мы будем называть его SQL/89 или SQL1). Иногда стандарт SQL1 также называют стандартом ANSI/ISO, и подавляющее большинство доступных на рынке СУБД поддерживают этот стандарт полностью. Однако развитие информационных технологий, связанных с базами данных, и необходимость реализации переносимых приложений потребовали в скором времени доработки и расширения первого стандарта SQL.
В конце 1992 г. был принят новый международный стандарт языка SQL, который в дальнейшим будем называть SQL/92 или SQL2. И он не лишен недостатков, но в то же время является существенно более точным и полным, чем SQL/89. В настоящий момент большинство производителей СУБД внесли изменения в свои продукты так, чтобы они в большей степени удовлетворяли стандарту SQL2.
В 1999 году появился новый стандарт, названный SQL3. Если отличия между стандартами SQL1 и SQL2 во многом были количественными, то стандарт SQL3 соответствует качественным серьезным преобразованиям. В SQL3 введены новые типы данных, при этом предполагается возможность задания сложных
66
структурированных типов данных, которые в большей степени соответствуют объектной ориентации. Наконец, добавлен раздел, который вводит стандарты на события и триггеры, которые ранее не затрагивались в стандартах, хотя давно уже широко использовались в коммерческих СУБД. В стандарте определены возможности четкой спецификации триггеров как совокупности события и действия.
В качестве действия могут выступать не только последовательность операторов SQL, но и операторы управления ходом выполнения программы. В рамках управления транзакциями произошел возврат к старой модели транзакций, допускающей точки сохранения (savepoints), и возможность указания в операторе отката ROOLBACK точек возврата позволит откатывать транзакцию не в начало, а в промежуточную ранее сохраненную точку. Такое решение повышает гибкость реализации сложных алгоритмов обработки информации.
А зачем вообще нужны эти стандарты? Зачем их изобретают и почему надо изучать их? Текст стандарта SQL2 занимает 600 станиц сухого формального текста, это очень много, и кажется, что это просто происки разработчиков стандартов, а не то, что необходимо рядовым разработчикам. Однако ни один серьезный разработчик, работающий с базами данных, не должен игнорировать стандарт, и для этого существуют весьма веские причины. Разработка любой информационной системы, ориентированной на технологию баз данных (а других информационных систем на настоящий момент и не бывает), является трудоемким процессом, занимающим несколько десятков и даже сотен человеко - месяцев. Следует отдавать себе отчет, что нельзя разработать сколько-нибудь серьезную систему за несколько дней. Кроме того, развитие вычислительной техники, систем телекоммуникаций и программного обеспечения столь стремительно, что проект может устареть еще до момента внедрения. Но развивается не только вычислительная техника, изменяются и реальные объекты, поведение которых моделируется использованием как самой БД, так и процедур обработки информации в ней, то есть конкретных приложений, которые составляют реальное наполнение разрабатываемой информационной системы. Именно поэтому проект информационной системы должен быть рассчитан на расширяемость и переносимость на другие платформы. Большинство поставщиков аппаратуры и программного обеспечения следуют стратегии поддержки стандартов, в противном случае пользователи просто не будут их покупать.
Однако каждый поставщик стремится улучшить свой продут введением дополнительных возможностей, не входящих в стандарт. Выбор разработчиков, следовательно, таков: ориентироваться только на экзотические особенности данного продукта либо стараться в основном придерживаться стандарта. Во втором случае весь интеллектуальный труд, вкладываемый в разработку, становится более защищенным, так как система приобретает свойства переносимости. И в случае появления более перспективной платформы проект, ориентированный в большей степени на стандарты, может быть легче перенесен на нее, чем тот, который в основном ориентировался на особенности конкретной платформы. Кроме того, стандарты - это верный ориентир для разработчиков, так как все поставщики СУБД в своих перспективных разработках обязательно следуют стандарту, и можно быть уверенным, что в конце концов стандарт будет реализован практически во всех перспективных СУБД. Так произошло со стандартом SQL1, так происходит со стандартом SQL2 и так будет происходить со стандартом SQL3.
67
Для поставщиков СУБД стандарт - это путеводная звезда, которая гарантирует правильное направление работ. А вот эффективность реализации стандарта -это гарантия успеха.
SQL нельзя в полной мере отнести к традиционным языкам программирования, он не содержит традиционные операторы, управляющие ходом выполнения программы, операторы описания типов и многое другое, он содержит только набор стандартных операторов доступа к данным, хранящимся в базе данных. Операторы SQL встраиваются в базовый язык программирования, которым может быть любой стандартный язык типа C++, PL, COBOL и т. д. Кроме того, операторы SQL могут выполняться непосредственно в интерактивном режиме.
Язык манипулирования данными в иерархических базах данных
Для доступа к базе данных у пользователя должна быть сформирована специальная среда окружения, поддерживающая в явном виде имеющиеся навигационные операции. Для этого в ней должны храниться:
шаблоны всех записей логических баз данных, доступных пользователю;
указатели на текущий экземпляр сегмента данного типа - для всех типов сегментов.
Язык манипулирования данными в иерархической модели поддерживает в явном виде навигационные операции. Эти операции связаны с перемещением указателя, который определяет текущий экземпляр конкретного сегмента.
Все операторы в языке манипулирования данными можно разделить на 3 группы. Первую группу составляют операторы поиска данных.
Язык манипулирования данными в сетевой модели
Все операции манипулирования данными в сетевой модели делятся на навигационные операции и операции модификации.
Навигационные операции осуществляют перемещение по БД путем прохождения по связям, которые поддерживаются в схеме БД. В этом случае результатом является новый единичный объект, который получает статус текущего объекта.
Операции модификации осуществляют как добавление новых экземпляров отдельных типов записей, так и экземпляров новых наборов, удаление экземпляров записей и наборов, модификацию отдельных составляющих внутри конкретных экземпляров записей. Средства модификации данных сведены в табл. 3.1:
Таблица 3.1. Операторы манипулирования данными в сетевой модели
| Операция | Назначение |
| READY | Обеспечение доступа данного процесса или пользователя к БД (сходна по смыслу с операцией открытия файла) |
| FINISH | Окончание работы с БД |
| FIND | Группа операций, устанавливающих указатель найденного объекта на текущий объект |
| GET | Передача найденного объекта в рабочую область. Допустима только после FIND |
| STORE | Помещение в БД записи, сформированной в рабочей области |
| CONNECT | Включение текущей записи в текущий экземпляр набора |
| DISCONNECT | Исключение текущей записи из текущего экземпляра набора |
| MODIFY | Обновление текущей записи данными из рабочей области пользователя |
| ERASE | Удаление экземпляра текущей записи |
В рабочей области пользователя хранятся шаблоны записей, программные переменные и три типа указателей текущего состояния:
текущая запись процесса (код или ключ последней записи, с которой работала данная программа);
текущая запись типа записи (для каждого типа записи ключ последней записи, с которой работала программа);
текущая запись типа набор (для каждого набора с владельцем Т1 и членом Т2 указывается, Т1 или Т2 были последней обрабатываемой записью).
На рис. 3.7 представлена концептуальная модель торгово - посреднической организации.
44
Рис. 3.7. Схема БД "Торговая фирма"
При необходимости возможно описание элементов данных, которые не принадлежат непосредственно данной записи, но при ее обработке часто используются.
Для этого используется тип VIRTUAL с обязательным указанием источника данного элемента данных.
RECORD Цены
02 Цена TYPE REAL
02 Товар VIRTUAL
SOURCE IS Товары.Наименование Товара
OF OWNER OF Товар - Цены SET
Наиболее интересна операция поиска (FIND), так как именно она отражает суть навигационных методов, применяемых в сетевой модели. Всего существует семь типов операций поиска:
1. По ключу (запись должна быть описана через CALC USING ...):
FIND RECORD BY CALC KEY
2. Последовательный просмотр записей данного типа:
FIND DUPLICATE RECORD BY CALC KEY
3. Найти владельца текущего экземпляра набора:
FIND OWNER OF CURRENT SET
4. Последовательный просмотр записей-членов текущего экземпляра набора:
FIND (FIRST | NEXT) RECORD IN CURRENT SET
45
5. Просмотр записей - членов экземпляра набора, специфицированных рядом полей:
FIND [DUPLICATE] RECORD IN CURRENT SET USING
6. Сделать текущей записью процесса текущий экземпляр набора:
FIND CURRENT OF SET
7. Установить текущую запись процесса:
FIND CURRENT OF RECORD
Например, алгоритм и программа печати заказов, сделанных Петровым, будут выглядеть так:
| ФИО = "Петров" FIND Люди RECORD BY CALC KEY FIND FIRST Заказы RECORD IN CURRENT Люди-Заказы SET WHILE NOT FAIL DO FIND OWNER OF CURRENT Товары-Заказы SET GET Товары PRINT Найм Товара FIND NEXT Заказы RECORD IN CURRENT Люди-Заказы SET END |
Язык описания данных иерархической модели
В рамках иерархической модели выделяют языковые средства описания данных (DDL, Data Definition Language) и средства манипулирования данными (DML, Data Manipulation Language).
Каждая физическая база описывается набором операторов, определяющих как ее логическую структуру, так и структуру хранения БД. Описание начинается с оператора DBD (Data Base Definition):
DBD Name = < имя БД>, ACCESS = < способ доступа>
Способ доступа определяет способ организации взаимосвязи физических записей. Определено 5 способов доступа: HSAM - hierarchical sequential access method (иерархически последовательный метод), HISAM - hierarchical index sequential access method (иерархически индексно - последовательный метод), HDAM - hierarchical direct access method (иерархически прямой метод), HIDAM -hierarchical index direct access method (иерархически индексно - прямой метод), INDEX - индексный метод.
Далее идет описание наборов данных, предназначенных для хранения БД:
DATA SET DD1 = < имя оператора, определяющего хранимый набор данных>.
DEVICE =< устройство хранения БД>,
[OVFLW = < имя области переполнения >]
Так как физические записи имеют разную длину, то при модификации данных запись может увеличиться и превысит исходную длину записи до модификации. В этом случае при определенных методах хранения может понадобиться дополнительное пространство хранения, где и будут размещены дополнительные данные. Это пространство и называется областью переполнения.
34
После описания всей физической БД идет описание типов сегментов, ее составляющих, в соответствии с иерархией. Описание сегментов всегда начинается с описания корневого сегмента. Общая схема описания типа сегмента такова:
SEGM NAME = < имя сегмента>. BYTES =< размер в байтах>.
FREQ =
PARENT =
Параметр FREQ определяет среднее количество экземпляров данного сегмента, связанных с одним экземпляром родительского сегмента. Для корневого сегмента это число возможных экземпляров корневого сегмента.
Для корневого сегмента параметр PARENT равен 0 (нулю).
Далее для каждого сегмента дается описание полей:
FIELD NAME = {( [. SEQ],{U | M}) | }.
START = < номер байта, с которого начинается значения поля >,
BYTES = ,
TYPE = {X | Р | С}
Признак SEQ - задается для ключевого поля, если экземпляры данного сегмента физически упорядочены в соответствии со значениями данного поля.
Параметр U задается, если значения ключевого поля уникальны для всех экземпляров данного сегмента, М - в противном случае. Если ноле является ключевым, то его описание задается в круглых скобках, в противном случае имя поля задается без скобок. Параметр TYPE определяет тип данных. Для ранних иерархических моделей были определены только три типа данных: X - шестнадцатеричный, Р - упакованный десятичный, С - символьный.
Заканчивается описание схемы вызовом процедуры генерации:
DBDGEN - указывает на конец последовательности управляющих операторов описания БД;
FINISH - устанавливает ненулевой код завершения при обнаружении ошибки;
END - конец.
В системе может быть несколько физических БД (ФБД), но каждая из них описывается отдельно своим DBD и ей присваивается уникальное имя. Каждая ФБД содержит только один корневой сегмент. Совокупность ФБД образует концептуальную модель данных.
Язык описания данных в сетевой модели
Язык описания данных в сетевой модели имеет несколько разделов:
описание базы данных - области размещения;
описания записей - элементов и агрегатов (каждого в отдельности);
описания наборов (каждого в отдельности).
SCHEMA IS
AREA NAME IS
RECORD NAME IS
Для каждой записи определяется способ размещения экземпляров записи данного типа:
LOCATION MODE IS {DIRECT (напрямую) |
CALC USING ]
42
DUPLICATE ARE [NOT] ALLOWED
VIA SET (рядом с записями владельца)
SYSTEM (решать будет система)}
Каждый тип записи должен быть приписан к некоторой физической области размещения:
WITHIN AREA
После описания записи в целом идет описание внутренней структуры:
Номер уровня определяет уровень вложенности при описании элементов и агрегатов данных. Первый уровень - сама запись. Поэтому элементы пли агрегаты данных имеют уровень начиная со второго. Если данное соответствует агрегату, то любая его составляющая добавляет один уровень вложенности.
Если агрегат является вектором, то он описывается как
а если - повторяющейся группой, то следующим образом:
.OCCURS TIMES
где N - среднее количество элементов в группе.
Описание набора и порядка включения членов в него выглядит следующим образом:
SET NAME IS ;
OWNER IS ( | SYSTEM).
Далее указывается порядок включения новых экземпляров члена данного набора в экземпляр набора:
ORDER PERMANENT INSERTION IS {SORTED | NEXT | PREV | LAST | FIRST}
После этого описывается член набора с указанием способа включения и способа исключения экземпляра - члена набора из экземпляра набора.
MEMBER IS {AUTOMATIC | MANUAL} {MANDATORY | OPTIONAL} KEY IS (ACCENDING | DESCENDING)
При автоматическом включении каждый новый экземпляр члена набора автоматически попадает в текущий экземпляр набора в соответствии с заданным ранее порядком включения. При ручном способе экземпляр члена набора сначала попадает в БД, а только потом командой CONNECT может быть включен в конкретный экземпляр набора.
Если задан способ исключения MANDATORY, то экземпляр записи, исключаемый из набора, автоматически исключается и из базы данных. Иначе просто разрываются связи.
Внешняя модель при сетевой организации данных поддерживается путем описания части общего связного графа.
43
42 :: 43 :: Содержание
Эпоха персональных компьютеров
Персональные компьютеры стремительно ворвались в нашу жизнь и буквально перевернули наше представление о месте и роли вычислительной техники в жизни общества. Теперь компьютеры стали ближе и доступнее каждому пользователю. Исчез благоговейный страх рядовых пользователей перед непонятными и сложными языками программирования. Появилось множество программ, предназначенных для работы неподготовленных пользователей. Эти программы были просты в использовании и интуитивно понятны: это прежде всего различные редакторы текстов, электронные таблицы и другие. Простыми и понятными стали операции копирования файлов и перенос информации с одного компьютера на другой, распечатка текстов, таблиц и других документов. Системные программисты были отодвинуты на второй план. Каждый пользователь мог себя почувствовать полным хозяином этого мощного и удобного устройства, позволяющего автоматизировать многие аспекты деятельности. И, конечно, это сказалось и на работе с базами данных. Появились программы, которые назывались системами управления базами данных и позволяли хранить значительные объемы информации, они имели удобный интерфейс для заполнения данных, встроенные средства для генерации различных отчетов. Эти программы позволяли автоматизировать многие учетные функции, которые раньше велись вручную. Постоянное снижение цен на персональные компьютеры сделало их доступными не только для организаций и фирм, но и для отдельных пользователей. Компьютеры стали инструментом для ведения документации и собственных учетных функций. Это все сыграло как положительную, так и отрицательную роль в области развития баз данных. Кажущаяся простота и доступность персональных компьютеров и их программного обеспечения породила множество дилетантов. Эти разработчики, считая себя знатоками, стали проектировать недолговечные базы данных, которые не учитывали многих особенностей объектов реального мира. Много было создано систем-однодневок, которые не отвечали законам развития и взаимосвязи реальных объектов.
Однако доступность персональных компьютеров заставила пользователей из многих областей знаний, которые ранее не применяли вычислительную технику в своей деятельности, обратиться к ним. И спрос на развитые удобные программы обработки данных заставлял поставщиков программного обеспечения поставлять все новые системы, которые принято называть настольными (desktop) СУБД. Значительная конкуренция среди поставщиков заставляла совершенствовать эти системы, предлагая новые возможности, улучшая интерфейс и быстродействие систем, снижая их стоимость. Наличие на рынке большого числа СУБД, выполняющих сходные функции, потребовало разработки методов экспорта-импорта данных для этих систем и открытия форматов хранения данных.
15
Но и в этот период появлялись любители, которые вопреки здравому смыслу разрабатывали собственные СУБД, используя стандартные языки программирования. Это был тупиковый вариант, потому что дальнейшее развитие показало, что перенести данные из нестандартных форматов в новые СУБД было гораздо труднее, а в некоторых случаях требовало таких трудозатрат, что легче было бы все разработать заново, но данные все равно надо было переносить на новую более перспективную СУБД. И это тоже было результатом недооценки тех функций, которые должна была выполнять СУБД.
Особенности этого этапа следующие:
Все СУБД были рассчитаны на создание БД в основном с монопольным доступом. И это понятно. Компьютер персональный, он не был подсоединен к сети, и база данных на нем создавалась для работы одного пользователя. В редких случаях предполагалась последовательная работа нескольких пользователей, например, сначала оператор, который вводил бухгалтерские документы, а потом главбух, который определял проводки, соответствующие первичным документам.
Большинство СУБД имели развитый и удобный пользовательский интерфейс. В большинстве существовал интерактивный режим работы с БД как в рамках описания БД, так и в рамках проектирования запросов. Кроме того, большинство СУБД предлагали развитый и удобный инструментарий для разработки готовых приложений без программирования.
Инструментальная среда состояла из готовых элементов приложения в виде шаблонов экранных форм, отчетов, этикеток (Labels), графических конструкторов запросов, которые достаточно просто могли быть собраны в единый комплекс.
Во всех настольных СУБД поддерживался только внешний уровень представления реляционной модели, то есть только внешний табличный вид структур данных.
При наличии высокоуровневых языков манипулирования данными типа реляционной алгебры и SQL в настольных СУБД поддерживались низкоуровневые языки манипулирования данными на уровне отдельных строк таблиц.
В настольных СУБД отсутствовали средства поддержки ссылочной и структурной целостности базы данных. Эти функции должны были выполнять приложения, однако скудость средств разработки приложений иногда не позволяла это сделать, и в этом случае эти функции должны были выполняться пользователем, требуя от него дополнительного контроля при вводе и изменении информации, хранящейся в БД.
Наличие монопольного режима работы фактически привело к вырождению функций администрирования БД и в связи с этим - к отсутствию инструментальных средств администрирования БД.
И, наконец, последняя и в настоящий момент весьма положительная особенность - это сравнительно скромные требования к аппаратному обеспечению со стороны настольных СУБД. Вполне работоспособные приложения, разработанные, например, на Clipper, работали на PC 286.
16
В принципе, их даже трудно назвать полноценными СУБД. Яркие представители этого семейства - очень широко использовавшиеся до недавнего времени СУБД Dbase (DbaseIII+, DbaseIV), FoxPro, Clipper, Paradox.
Карты распределения блоков
В данных картах хранится информация о распределении блоков. Карта распределения блоков состоит из стандартного заголовка и одного битового массива в 64 000 битов. Каждый бит характеризует один блок. Поэтому одна страница карты распределения описывает пространство в 64 000 блоков или 4 Гбайт данных.
Карты распределения блоков делятся на два типа:
Глобальная карта распределения (Global allocation map, GAM) хранит информацию об Использовании блоков. Если бит установлен в 0, то блок занят данными, если в 1 - то блок свободен.
Вторичная глобальная карта распределения (Secondary global allocation map, SGAM) хранит информацию о типе блоков. Если бит установлен в 1, то блок смешанный и минимум одна страница в нем свободна, в остальных случаях (блок свободен, блок смешанный, но свободных страниц нет, блок однородный) бит равен 0.
При отведении пространства сервер использует обе карты распределения.
Карты размещения
Для организации связи между блоками и расположенными на них объектами используются индексные карты размещения (Index Allocation Map, IAM). Каждая таблица или индекс имеют одну или более страниц IAM. В каждом файле, в котором размещаются таблица или индекс, существует минимум одна карта размещения для этой таблицы или индекса. Страницы IAM размещаются произвольно внутри файла и отводятся по мере необходимости. IAM объединены друг с другом в цепочку двунаправленными ссылками. Указатель на первую карту размещения содержится в поле FirstlAM системной таблицы Sysindex.
Каждая IAM описывает некоторый диапазон блоков и представляет собой битовую карту: если бит установлен в 1, то в данном блоке есть страницы, принадлежащие данному объекту, если в 0 - то нет.
Все страницы размещения не связаны напрямую с некоторым объектом БД, они соответствуют некоторой системной информации, поэтому параметр "идентификатор объекта" для всех этих страниц одинаков и равен 99.
Карты свободного пространства
Степень заполнения страниц B SQL 7.0 отслеживает специальный механизм -карты свободного пространства (Page free space page, PFS). Каждая PFS-страница хранит информацию о 8000 страниц, по 1 байту на страницу. Каждый байт представляет собой битовую карту, которая сообщает о степени занятости страницы и о том, принадлежит ли она объекту.
Первые страницы файла БД всегда используются под карты распределения. Страница № 1 состоит из двух частей. После стандартного заголовка страницы следует заголовок файла, содержащий его описание, затем размещается блок PFS. Страницы PFS повторяются через каждые 8000 страниц, если размер файла
193
превосходит один блок. Страница № 2 - это GAM, страница № 3 - это SGAM. Карты распределения блоков повторяются через каждые 512 000 страниц. Кроме того, каждая девятая страница первичного файла - это загрузочная страница БД (database boot page), содержащая описание БД и параметры конфигурации.
Классификация моделей данных
Одними из основополагающих в концепции баз данных являются обобщенные категории "данные" и "модель данных".
Понятие "данные" в концепции баз данных - это набор конкретных значений, параметров, характеризующих объект, условие, ситуацию или любые другие факторы. Примеры данных: Петров Николай Степанович, $30 и т. д. Данные не обладают определенной структурой, данные становятся информацией тогда, когда пользователь задает им определенную структуру, то есть осознает их смысловое содержание. Поэтому центральным понятием в области баз данных является понятие модели. Не существует однозначного определения этого термина, у разных авторов эта абстракция определяется с некоторыми различиями, но тем не менее можно выделить нечто общее в этих определениях.
Модель данных - это некоторая абстракция, которая, будучи приложима к конкретным данным, позволяет пользователям и разработчикам трактовать их уже как информацию, то есть сведения, содержащие не только данные, но и взаимосвязь между ними.
На рис. 2.3 представлена классификация моделей данных.
В соответствии с рассмотренной ранее трехуровневой архитектурой мы сталкиваемся с понятием модели данных по отношению к каждому уровню. И действительно, физическая модель данных оперирует категориями, касающимися организации внешней памяти и структур хранения, используемых в данной операционной среде. В настоящий момент в качестве физических моделей используются различные методы размещения данных, основанные на файловых структурах: это организация файлов прямого и последовательного доступа, индексных файлов и инвертированных файлов, файлов, использующих различные методы хэширования, взаимосвязанных файлов. Кроме того, современные СУБД широко используют страничную организацию данных. Физические
27
модели данных, основанные на страничной организации, являются наиболее перспективными.
Рис. 2.3. Классификация моделей данных
Наибольший интерес вызывают модели данных, используемые на концептуальном уровне.
По отношению к ним внешние модели называются подсхемами и используют те же абстрактные категории, что и концептуальные модели данных.
Кроме трех рассмотренных уровней абстракции при проектировании БД существует еще один уровень, предшествующий им. Модель этого уровня должна выражать информацию о предметной области в виде, независимом от используемой СУБД. Эти модели называются инфологическими, или семантическими, и отражают в естественной и удобной для разработчиков и других пользователей форме информационно-логический уровень абстрагирования, связанный с фиксацией и описанием объектов предметной области, их свойств и их взаимосвязей.
Инфологические модели данных используются на ранних стадиях проектирования для описания структур данных в процессе разработки приложения, а даталогические модели уже поддерживаются конкретной СУБД.
Документальные модели данных соответствуют представлению о слабоструктурированной информации, ориентированной в основном на свободные форматы документов, текстов на естественном языке.
Модели, основанные на языках разметки документов, связаны прежде всего со стандартным общим языком разметки - SGML (Standart Generalised Markup
28
Language), который был утвержден ISO в качестве стандарта еще в 80-х годах. Этот язык предназначен для создания других языков разметки, он определяет допустимый набор тегов (ссылок), их атрибуты и внутреннюю структуру документа. Контроль за правильностью использования тегов осуществляется при помощи специального набора правил, называемых DTD-описаниями, которые используются программой клиента при разборе документа. Для каждого класса документов определяется свой набор правил, описывающих грамматику соответствующего языка разметки. С помощью SGML можно описывать структурированные данные, организовывать информацию, содержащуюся в документах, представлять эту информацию в некотором стандартизованном формате. Но ввиду некоторой своей сложности SGML использовался в основном для описания синтаксиса других языков (наиболее известным из которых является HTML), и немногие приложения работали с SGML-документами напрямую.
Гораздо более простой и удобный, чем SGML, язык HTML позволяет определять оформление элементов документа и имеет некий ограниченный набор инструкций - тегов, при помощи которых осуществляется процесс разметки. Инструкции HTML в первую очередь предназначены для управления процессом вывода содержимого документа на экране программы-клиента и определяют этим самым способ представления документа, но не его структуру. В качестве элемента гипертекстовой базы данных, описываемой HTML, используется текстовый файл, который может легко передаваться по сети с использованием протокола HTTP. Эта особенность, а также то, что HTML является открытым стандартом и огромное количество пользователей имеет возможность применять возможности этого языка для оформления своих документов, безусловно, повлияли на рост популярности HTML и сделали его сегодня главным механизмом представления информации в Интернете.
Однако HTML сегодня уже не удовлетворяет в полной мере требованиям, предъявляемым современными разработчиками к языкам подобного рода. И ему на смену был предложен новый язык гипертекстовой разметки, мощный, гибкий и, одновременно с этим, удобный язык XML. В чем же заключаются его достоинства?
XML (Extensible Markup Language) - это язык разметки, описывающий целый класс объектов данных, называемых XML-документами. Он используется в качестве средства для описания грамматики других языков и контроля за правильностью составления документов. То есть сам по себе XML не содержит никаких тегов, предназначенных для разметки, он просто определяет порядок их создания.
Тезаурусные модели основаны на принципе организации словарей, содержат определенные языковые конструкции и принципы их взаимодействия в заданной грамматике. Эти модели эффективно используются в системах-переводчиках, особенно многоязыковых переводчиках. Принцип хранения информации в этих системах и подчиняется тезаурусным моделям.
Дескрипторные модели - самые простые из документальных моделей, они широко использовались на ранних стадиях использования документальных баз данных.В этих моделях каждому документу соответствовал дескриптор - описатель. Этот дескриптор имел жесткую структуру и описывал документ в
29
соответствии с теми характеристиками, которые требуются для работы с документами в разрабатываемой документальной БД. Например, для БД, содержащей описание патентов, дескриптор содержал название области, к которой относился патент, номер патента, дату выдачи патента и еще ряд ключевых параметров, которые заполнялись для каждого патента. Обработка информации в таких базах данных велась исключительно по дескрипторам, то есть по тем параметрам, которые характеризовали патент, а не по самому тексту патента.
Контрольные вопросы
Найдите сходства первого и четвертого этапов развития.
Найдите отличия первого и третьего этапов развития.
Если при использовании файловых систем для параллельного доступа пользователей создавать копии файлов для каждого пользователя, может ли это ускорить параллельную работу с информацией?
19
19 :: Содержание
Метод временных меток
Альтернативный метод сериализации транзакций, хорошо работающий в условиях редких конфликтов транзакций и не требующий построения графа ожидания транзакций, основан на использовании временных меток.
Основная идея метода (у которого существует множество разновидностей) состоит в следующем: если транзакция Т1 началась раньше транзакции Т2, то система обеспечивает такой режим выполнения, как если бы Т1 была целиком выполнена до начала Т2.
Для этого каждой транзакции Т предписывается временная метка t, соответствующая времени начала Т. При выполнении операции над объектом г транзакция Т помечает его своей временной меткой и типом операции (чтение или изменение).
Перед выполнением операции над объектом г транзакция Т1 выполняет следующие действия:
Проверяет, не закончилась ли транзакция Т, пометившая этот объект. Если Т закончилась, Т1 помечает объект г и выполняет свою операцию.
Если транзакция Т не завершилась, то Т1 проверяет конфликтность операций. Если операции неконфликтны, при объекте r остается или проставляется временная метка с меньшим значением, и транзакция Т1 выполняет свою операцию.
Если операции Т1 и Т конфликтуют, то если t(T) > t(T1) (то есть транзакция Т является более "молодой", чем Т1), производится откат Т и Т1 продолжает работу.
Если же t(T) < t(Tl) (Т "старше" Т1), то Т1 получает новую временную метку и начинается заново.
К недостаткам метода временных меток относятся потенциально более частые откаты транзакций, чем в случае использования синхронизационных захватов. Это связано с тем, что конфликтность транзакций определяется более грубо.
246
Кроме того, в распределенных системах не очень просто вырабатывать глобальные временные метки с отношением полного порядка (это отдельная большая наука).
Но в распределенных системах эти недостатки окупаются тем, что не нужно распознавать тупики, а как мы уже отмечали, построение графа ожидания в распределенных системах стоит очень дорого.
247
246 :: 247 :: Содержание
Методы семантической оптимизации запросов
Рассмотренные ранее методы никак не связаны с семантикой конкретной БД, они применимы к любой БД, вне зависимости от ее конкретного содержания. Семантические методы оптимизации основаны как раз на учете семантики конкретной БД. Таких методов в различных реализациях может быть множество, мы с вами коснемся лишь некоторых из них:
293
Преобразование запросов с учетом семантической информации. Это прежде всего относится к запросам, которые выполняются над представлениями. Само представление представляет собой запрос. В БД представление хранится в виде скомпилированного плана выполнения запроса, то есть в нем в некоторой канонической форме представлены уже все предикаты и сам план выполнения запроса. При преобразовании внешнего запроса производится объединение внешнего запроса с внутренней формой запроса, составляющего основу представления, и строится обобщенная каноническая форма, объединяющая оба запроса. Для этой новой формы проводится анализ и преобразование предикатов. Поэтому при выполнении запроса над представлением будет выполнено не два, а только один запрос, оптимизированный но обобщенным параметрам запроса.
Использование ограничений целостности при анализе запросов. Ограничения целостности связаны с условиями, которые накладываются на значения столбцов таблицы. При выполнении запросов над таблицами условия запросов объединяются специальным образом с условиями ограничений таблицы и полученные обобщенные предикаты уже анализируются. Допустим, что мы ищем в нашей библиотеке читателей с возрастом более 100 лет, но если у нас есть ограничение, заданное для таблицы READERS, которое ограничивает дату рождения наших читателей, так чтобы читатель имел дату рождения в пределах от 17 до 100 лет включительно. Поэтому оптимизатор запроса, сопоставив два эти предиката, может сразу определить, что результатом запроса будет пустое множество.
После оптимизации запрос имеет непроцедурный вид, то есть в нем не определен жесткий порядок выполнения элементарных операций над исходными объектами.
На следующем этапе строятся все возможные планы выполнения запросов и для каждого из них производятся стоимостные оценки. Оценка планов выполнения запроса основана на анализе текущих объемов данных, хранящихся в отношениях БД, и на статистическом анализе хранимой информации. В большинстве СУБД ведется учет диапазона значений отдельного столбца с указанием процентного содержания для каждого диапазона. Поэтому при построении плана запроса СУБД может оценить объем промежуточных отношений и построить план таким образом, чтобы на наиболее ранних этапах выполнения запроса минимизировать количество строк, включаемых в промежуточные отношения.
Кроме ядра СУБД каждый поставщик обеспечивает специальные инструментальные средства, облегчающие администрирование БД и разработку новых проектов БД и пользовательских приложений для данного сервера. В последнее время практически все утилиты и инструментальные средства имеют развитый графический интерфейс.
Для разработки приложений пользователи могут применять не только инструментальные средства, поставляемые вместе с сервером БД, но и средства сторонних поставщиков. Так, в нашей стране получила большую популярность инструментальная среда Delphi, которая позволяет разрабатывать приложения для различных серверов БД. За рубежом более популярными являются инструментальные системы быстрой разработки приложений (RAF Rapid Application Foundation) продукты компании Advanced Information System, инструментальной среды Power Builder фирмы Power Soft, системы SQL Windows фирмы Gupta (Taxedo).
Методы синтаксической оптимизации запросов
Методы синтаксической оптимизации запросов связаны с построением некоторой эквивалентной формы, называемой иногда канонической формой, которая требует меньших затрат на выполнение запроса, по дает результат, полностью эквивалентный исходному запросу.
К методам, используемым при синтаксической оптимизации запросов, относятся следующие:
Логические преобразования запросов. Прежде всего это относится к преобразованию предикатов, входящих в условие выборки. Предикаты, содержащие операции сравнения простых значений. Такой предикат имеет вид арифметическое выражение ОС арифметическое выражение, где ОС - операция сравнения, а арифметические выражения левой и правой частей в общем случае содержат имена полей отношений и константы (в языке SQL среди констант могут встречаться и имена переменных объемлющей программы, значения которых становятся известными только при реальном выполнении запроса).
Канонические представления могут быть различными для предикатов разных типов. Если предикат включает только одно имя поля, то его каноническое представление может, например, иметь вид имя поля ОС константное арифметическое выражение (эта форма предиката - простой предикат селекции -очень полезна при выполнении следующего этапа оптимизации). Если начальное представление предиката имеет вид
(n+12)*R. В ОС 100
здесь n - переменная языка, R.B - имя столбца В отношения R, ОС - допустимая операция сравнения.
Каноническим представлением такого предиката может быть
R.B ОС 100/(n+12)
В этом случае мы один раз для заданного значения переменной п вычисляем выражение в скобках и правую часть операции сравнения 100/(n +12), а потом каждую строку можем сравнивать с полученным значением.
Если предикат включает в точности два имени поля разных отношений (или двух разных вхождений одного отношения), то его каноническое представление может иметь вид имя поля ОС арифметическое выражение, где арифметическое выражение в правой части включает только константы и второе имя поля (это тоже форма, полезная для выполнения следующего шага оптимизации, - предикат соединения; особенно важен случай эквисоединения, когда ОС - это равенство). Если в начальном представлении предикат имеет вид:
12*(Rl.A)-n*(R2.B) ОС m.
то его каноническое представление:
R1.A ОС (m+n*(R2.B)/12
В общем случае желательно приведение предиката к каноническому представлению вида арифметическое выражение ОС константное арифметическое выражение, где выражения правой и левой частей также приведены к каноническому представлению. В дальнейшем можно произвести поиск общих арифметических выражений в разных предикатах запроса. Это оправдано, поскольку при выполнении запроса вычисление арифметических выражений будет производиться при выборке каждого очередного кортежа, то есть потенциально большое число раз.
При приведении предикатов к каноническому представлению можно вычислять константные выражения и избавляться от логических отрицаний.
Еще один класс логических преобразований связан с приведением к каноническому виду логического выражения, задающего условие выборки запроса. Как правило, используются либо дизъюнктивная, либо конъюнктивная нормальные формы. Выбор канонической формы зависит от общей организации оптимизатора.
При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия) и упрощать логическое выражение за счет, например, выявления конъюнкции взаимно противоречащих предикатов.
Преобразования запросов с изменением порядка реляционных операций. В традиционных оптимизаторах распространены логические преобразования, связанные с изменением порядка выполнения реляционных операций.
Например, имеем следующий запрос:
R1 NATURAL JOIN R2
WHERE R1.A ОС a AND
R2.B С b
Здесь а и b некоторые константы, которые ограничивают значение атрибутов отношений R1 и R2.
Если мы его рассмотрим в терминах реляционной алгебры, то это естественное соединение отношений R1 и R2, в которых заданы внутренние ограничения на кортежи каждого отношения.
Для уменьшения числа соединяемых кортежей резоннее сначала произвести операции выборки на каждом отношении и только после этого перейти в операции естественного соединения.
291
Поэтому данный запрос будет эквивалентен следующей последовательности операций реляционной алгебры:
R3 = R1[R1.A ОС а]
R4 = R2[R2.B С b]
R5 = R3*[ ]*R4
Хотя немногие реляционные системы имеют языки запросов, основанные в чистом виде на реляционной алгебре, правила преобразований алгебраических выражений могут быть полезны и в других случаях. Довольно часто реляционная алгебра используется в качестве основы внутреннего представления запроса. Естественно, что после этого можно выполнять и алгебраические преобразования.
В частности, существуют подходы, связанные с преобразованием запросов на языке SQL к алгебраической форме. Особенно важно то, что реляционная алгебра более проста, чем язык SQL. Преобразование запроса к алгебраической форме упрощает дальнейшие действия оптимизатора по выборке оптимальных планов. Вообще говоря, развитый оптимизатор запросов системы, ориентированной на SQL, должен выявить все возможные планы выполнения любого запроса, но "пространство поиска" этих планов в общем случае очень велико; в каждом конкретном оптимизаторе используются свои эвристики для сокращения пространства поиска. Некоторые, возможно, наиболее оптимальные планы никогда не будут рассматриваться. Разумное преобразование запроса на SQL к алгебраическому представлению сокращает пространство поиска планов выполнения запроса с гарантией того, что оптимальные планы потеряны не будут.
Приведение запросов с вложенными подзапросами к запросам с соединениями. Основным отличием языка SQL от языка реляционной алгебры является возможность использовать в логическом условии выборки предикаты, содержащие вложенные подзапросы. Глубина вложенности не ограничивается языком, то есть, вообще говоря, может быть произвольной. Предикаты с вложенными подзапросами при наличии общего синтаксиса могут обладать весьма различной семантикой.
Единственным общим для всех возможных семантик вложенных подзапросов алгоритмом выполнения запроса является вычисление вложенного подзапроса всякий раз при вычислении значения предиката. Поэтому естественно стремиться к такому преобразованию запроса, содержащего предикаты со вложенными подзапросами, которое сделает семантику подзапроса более явной, предоставив тем самым в дальнейшем оптимизатору возможность выбрать способ выполнения запроса, наиболее точно соответствующий семантике подзапроса.
Каноническим представлением запроса на п отношениях называется запрос, содержащий n - 1 предикат соединения и не содержащий предикатов с вложенными подзапросами. Фактически каноническая форма - это алгебраическое представление запроса.
Например, запрос с вложенным подзапросом:
292
(SELECT R1.A
FROM R1
WHERE R1.B IN
(SELECT R2.B FROM R2 WHERE R1.C = R2.D)
)
эквивалентен
(SELECT R1.A
FROM R1. R2
WHERE R1.A = R2.B AND R1.C - R2.D)
Второй запрос:
(SELECT R1.A FROM R1 WHERE R1.K =
(SELECT AVG (R2.B) FROM R2 WHERE R1.C = R2.D)
или
(SELECT R1.A
FROM R1. R3
WHERE R1.C = R3.D AND R1.K = R3.L)
R3 = SELECT R2.D, L AVG (R2.B)
FROM R2
GROUP BY R2.D
При использовании подобного подхода в оптимизаторе запросов не обязательно производить формальные преобразования запросов. Оптимизатор должен в большей степени использовать семантику обрабатываемого запроса, а каким образом она будет распознаваться - это вопрос техники.
Заметим, что в кратко описанном нами подходе имеются некоторые тонкие семантические некорректности. Известны исправленные методы, но они слишком сложны технически, чтобы рассматривать их в данном пособии.
Модель сервера баз данных
Для того чтобы избавиться от недостатков модели удаленного доступа, должны быть соблюдены следующие условия:
Необходимо, чтобы БД в каждый момент отражала текущее состояние предметной области, которое определяется не только собственно данными, но и связями между объектами данных. То есть данные, которые хранятся в БД, в каждый момент времени должны быть непротиворечивыми.
БД должна отражать некоторые правила предметной области, законы, по которым она функционирует (business rules). Например, завод может нормально работать только в том случае, если на складе имеется некоторый достаточный запас (страховой запас) деталей определенной номенклатуры, деталь может быть запущена в производство только в том случае, если на складе имеется в наличии достаточно материала для ее изготовления, и т. д.
206
Необходим постоянный контроль за состоянием БД, отслеживание всех изменений и адекватная реакция на них: например, при достижении некоторым измеряемым параметром критического значения должно произойти отключение определенной аппаратуры, при уменьшении товарного запаса ниже допустимой нормы должна быть сформирована заявка конкретному поставщику на поставку соответствующего товара.
Необходимо, чтобы возникновение некоторой ситуации в БД четко и оперативно влияло на ход выполнения прикладной задачи.
Одной из важнейших проблем СУБД является контроль типов данных. В настоящий момент СУБД контролирует синтаксически только стандартно-допустимые типы данных, то есть такие, которые определены в DDL (data definition language) - языке описания данных, который является частью SQL. Однако в реальных предметных областях у нас действуют данные, которые несут в себе еще и семантическую составляющую, например, это координаты объектов или единицы различных метрик, например рабочая неделя в отличие от реальной имеет сразу после пятницы понедельник.
Данную модель поддерживают большинство современных СУБД: Informix, Ingres, Sybase, Oracle, MS SQL Server. Основу данной модели составляет механизм хранимых процедур как средство программирования SQL - сервера, механизм триггеров как механизм отслеживания текущего состояния информационного хранилища и механизм ограничений на пользовательские типы данных, который иногда называется механизмом поддержки доменной структуры.
Модель сервера баз данных представлена на рис. 10.6.
Рис. 10.6. Модель активного сервера БД
В этой модели бизнес-логика разделена между клиентом и сервером. На сервере бизнес - логика реализована в виде хранимых процедур - специальных программных модулей, которые хранятся в БД и управляются непосредственно СУБД. Клиентское приложение обращается к серверу с командой запуска хранимой процедуры, а сервер выполняет эту процедуру и регистрирует все изменения в БД, которые в ней предусмотрены. Сервер возвращает клиенту данные, релевантные его запросу, которые требуются клиенту либо для вывода на
207
экран, либо для выполнения части бизнес - логики, которая расположена на клиенте. Трафик обмена информацией между клиентом и сервером резко уменьшается.
Централизованный контроль в модели сервера баз данных выполняется с использованием механизма триггеров. Триггеры также являются частью БД.
Термин "триггер" взят из электроники и семантически очень точно характеризует механизм отслеживания специальных событий, которые связаны с состоянием БД. Триггер в БД является как бы некоторым тумблером, который срабатывает при возникновении определенного события в БД. Ядро СУБД проводит мониторинг всех событий, которые вызывают созданные и описанные триггеры в БД, и при возникновении соответствующего события сервер запускает соответствующий триггер. Каждый триггер представляет собой также некоторую программу, которая выполняется над базой данных. Триггеры могут вызывать хранимые процедуры.
Механизм использования триггеров предполагает, что при срабатывании одного триггера могут возникнуть события, которые вызовут срабатывание других триггеров. Этот мощный инструмент требует тонкого и согласованного применения, чтобы не получился бесконечный цикл срабатывания триггеров.
В данной модели сервер является активным, потому что не только клиент, но и сам сервер, используя механизм триггеров, может быть инициатором обработки данных в БД.
И хранимые процедуры, и триггеры хранятся в словаре БД, они могут быть использованы несколькими клиентами, что существенно уменьшает дублирование алгоритмов обработки данных в разных клиентских приложениях.
Для написания хранимых процедур и триггеров используется расширение стандартного языка SQL, так называемый встроенный SQL. Встроенный SQL мы рассмотрим в главе 12.
Недостатком данной модели является очень большая загрузка сервера. Действительно, сервер обслуживает множество клиентов и выполняет следующие функции:
осуществляет мониторинг событий, связанных с описанными триггерами;
обеспечивает автоматическое срабатывание триггеров при возникновении связанных с ними событий;
обеспечивает исполнение внутренней программы каждого триггера;
запускает хранимые процедуры по запросам пользователей;
запускает хранимые процедуры из триггеров;
возвращает требуемые данные клиенту;
обеспечивает все функции СУБД: доступ к данным, контроль и поддержку целостности данных в БД, контроль доступа, обеспечение корректной параллельной работы всех пользователей с единой БД.
Если мы переложили на сервер большую часть бизнес - логики приложений, то требования к клиентам в этой модели резко уменьшаются. Иногда такую модель называют моделью с "тонким клиентом", в отличие от предыдущих моделей,
208
где на клиента возлагались гораздо более серьезные задачи. Эти модели называются моделями с "толстым клиентом".
Для разгрузки сервера была предложена трехуровневая модель.
Модель сервера приложений
Эта модель является расширением двухуровневой модели и в ней вводится дополнительный промежуточный уровень между клиентом и сервером. Архитектура трехуровневой модели приведена на рис. 10.7. Этот промежуточный уровень содержит один или несколько серверов приложений.
Рис. 10.7. Модель сервера приложений
В этой модели компоненты приложения делятся между тремя исполнителями:
Клиент обеспечивает логику представления, включая графический пользовательский интерфейс, локальные редакторы; клиент может запускать локальный код приложения клиента, который может содержать обращения к локальной БД, расположенной на компьютере-клиенте. Клиент исполняет коммуникационные функции front-end части приложения, которые обеспечивают доступ клиенту в локальную или глобальную сеть. Дополнительно реализация взаимодействия между клиентом и сервером может включать в себя управление распределенными транзакциями, что соответствует тем случаям, когда клиент также является клиентом менеджера распределенных транзакций.
Серверы приложений составляют новый промежуточный уровень архитектуры. Они спроектированы как исполнения общих незагружаемых функций для клиентов. Серверы приложений поддерживают функции клиентов как частей взаимодействующих рабочих групп, поддерживают сетевую доменную операционную среду, хранят и исполняют наиболее общие правила бизнес - логики, поддерживают каталоги с данными, обеспечивают обмен сообщениями и поддержку запросов, особенно в распределенных транзакциях.
Серверы баз данных в этой модели занимаются исключительно функциями СУБД: обеспечивают функции создания и ведения БД, поддерживают целостность реляционной БД, обеспечивают функции хранилищ данных (warehouse services). Кроме того, на них возлагаются функции создания резервных копий БД и восстановления БД после сбоев, управления выполнением транзакций и поддержки устаревших (унаследованных) приложений (legacy application).
209
Отметим, что эта модель обладает большей гибкостью, чем двухуровневые модели. Наиболее заметны преимущества модели сервера приложений в тех случаях, когда клиенты выполняют сложные аналитические расчеты над базой данных, которые относятся к области OLAP-приложений. (On-line analytical processing.) В этой модели большая часть бизнес - логики клиента изолирована от возможностей встроенного SQL, реализованного в конкретной СУБД, и может быть выполнена на стандартных языках программирования, таких как С, C++, SmallTalk, Cobol. Это повышает переносимость системы, ее масштабируемость.
Функции промежуточных серверов могут быть в этой модели распределены в рамках глобальных транзакций путем поддержки ХА - протокола (X/Open transaction interface protocol), который поддерживается большинством поставщиков СУБД.
210
209 :: 210 :: Содержание
Модель "сущность - связь"
Как любая модель, модель "сущность - связь" имеет несколько базовых понятий, которые образуют исходные кирпичики, из которых строятся уже более сложные объекты по заранее определенным правилам.
Эта модель в наибольшей степени согласуется с концепцией объектно-ориентированного проектирования, которая в настоящий момент несомненно является базовой для разработки сложных программных систем, поэтому многие понятия вам могут показаться знакомыми, и если это действительно так, то тем проще вам будет освоить технологию проектирования баз данных, основанную на ER-модели.
В основе ER - модели лежат следующие базовые понятия:
Сущность, с помощью которой моделируется класс однотипных объектов. Сущность имеет имя, уникальное в пределах моделируемой системы. Так как сущность соответствует некоторому классу однотипных объектов, то предполагается, что в системе существует множество экземпляров данной сущности. Объект, которому соответствует понятие сущности, имеет свой набор атрибутов - характеристик, определяющих свойства данного представителя класса. При этом набор атрибутов должен быть таким, чтобы можно было различать конкретные экземпляры сущности. Например, у сущности Сотрудник может быть следующий набор атрибутов: Табельный номер, Фамилия, Имя, Отчество, Дата рождения, Количество детей, Наличие родственников за границей. Набор атрибутов, однозначно идентифицирующий конкретный экземпляр сущности, называют ключевым. Для сущности Сотрудник ключевым будет атрибут Табельный номер, поскольку для всех сотрудников данного предприятия табельные номера будут различны. Экземпляром сущности Сотрудник будет описание конкретного сотрудника предприятия. Одно из общепринятых графических обозначений сущности - прямоугольник, в верхней части которого записано имя сущности, а ниже перечисляются атрибуты,
122
причем ключевые атрибуты помечаются, например, подчеркиванием или специальным шрифтом (рис. 7.1):
Рис. 7.1. Пример определения сущности в модели ER
Между сущностями могут быть установлены связи - бинарные ассоциации, показывающие, каким образом сущности соотносятся или взаимодействуют между собой.
Связь может существовать между двумя разными сущностями или между сущностью и ей же самой (рекурсивная связь). Она показывает, как связаны экземпляры сущностей между собой. Если связь устанавливается между двумя сущностями, то она определяет взаимосвязь между экземплярами одной и другой сущности. Например, если у нас есть связь между сущностью "Студент" и сущностью "Преподаватель" и эта связь - руководство дипломными проектами, то каждый студент имеет только одного руководителя, но один и тот же преподаватель может руководить множеством студентов-дипломников. Поэтому это будет связь "один - ко - многим" (1:М), один со стороны "Преподаватель" и многие со стороны "Студент" (см. рис. 7.2).
Рис. 7.2. Пример отношения "один - ко - многим" при связывании сущностей "Студент" и "Преподаватель"
В разных нотациях мощность связи изображается по-разному. В нашем примере мы используем нотацию CASE системы POWER DESIGNER, здесь множественность изображается путем разделения линии связи на 3. Связь имеет общее имя "Дипломное проектирование" и имеет имена ролей со стороны обеих сущностей. Со стороны студента эта роль называется "Пишет диплом под руководством", со стороны преподавателя эта связь называется "Руководит".
123
Графическая интерпретация связи позволяет сразу прочитать смысл взаимосвязи между сущностями, она наглядна и легко интерпретируема. Связи делятся на три типа по множественности: один - к - одному (1:1), один - ко - многим (1:М), многие - ко - многим (М:М). Связь один - к - одному означает, что экземпляр одной сущности связан только с одним экземпляром другой сущности. Связь 1: М означает, что один экземпляр сущности, расположенный слева по связи, может быть связан с несколькими экземплярами сущности, расположенными справа по связи. Связь "один - к - одному" (1:1) означает, что один экземпляр одной сущности связан только с одним экземпляром другой сущности, а связь "многие - ко - многим" (М:М) означает, что один экземпляр первой сущности может быть связан с несколькими экземплярами второй сущности, и наоборот, один экземпляр второй сущности может быть связан с несколькими экземплярами первой сущности.
Например, если мы рассмотрим связь типа "Изучает" между сущностями "Студент" и "Дисциплина", то это связь типа "многие - ко - многим" (М:М), потому что каждый студент может изучать несколько дисциплин, но и каждая дисциплина изучается множеством студентов. Такая связь изображена на рис. 7.3.
Между двумя сущностями может быть задано сколько угодно связей с разными смысловыми нагрузками. Например, между двумя сущностями "Студент" и "Преподаватель" можно установить две смысловые связи, одна -рассмотренная уже ранее "Дипломное проектирование", а вторая может быть условно названа "Лекции", и она определяет, лекции каких преподавателей слушает данный студент и каким студентам данный преподаватель читает лекции. Ясно, что это связь типа многие - ко - многим. Пример этих связей приведен на рис. 7.3.
Рис. 7.3. Пример моделирования связи "многие - ко - многим"
Связь любого из этих типов может быть обязательной, если в данной связи должен участвовать каждый экземпляр сущности, необязательной - если не каждый экземпляр сущности должен участвовать в данной связи. При этом связь может быть обязательной с одной стороны и необязательной с другой стороны. Обязательность связи тоже по-разному обозначается в разных нотациях. Мы снова используем нотацию POWER DESIGNER. Здесь необязательность связи обозначается пустым кружочком на конце связи, а обязательность перпендикулярной линией, перечеркивающей связь. И эта нотация имеет простую интерпретацию. Кружочек означает, что ни один экземпляр не может участвовать в этой связи. А перпендикуляр интерпретируется как то, что по крайней мере один экземпляр сущности участвует в этой связи.
124
Рассмотрим для этого ранее приведенный пример связи "Дипломное проектирование". На нашем рисунке эта связь интерпретируется как необязательная с двух сторон. Но ведь на самом деле каждый студент, который пишет диплом, должен иметь своего руководителя дипломного проектирования, но, с другой стороны, не каждый преподаватель должен вести дипломное проектирование.
Поэтому в данной смысловой постановке изображение этой связи изменится и будет выглядеть таким, как представлено на рис. 7.4.
Рис. 7.4. Пример обязательной и необязательной связи между сущностями
Кроме того, в ER - модели допускается принцип категоризации сущностей. Это значит, что, как и в объектно-ориентированных языках программирования, вводится понятие подтипа сущности, то есть сущность может быть представлена в виде двух или более своих подтипов - сущностей, каждая из которых может иметь общие атрибуты и отношения и/или атрибуты и отношения, которые определяются однажды на верхнем уровне и наследуются на нижнем уровне. Все подтипы одной сущности рассматриваются как взаимоисключающие, и при разделении сущности на подтипы она должна быть представлена в виде полного набора взаимоисключающих подтипов. Если на уровне анализа не удается выявить полный перечень подтипов, то вводится специальный подтип, называемый условно ПРОЧИЕ, который в дальнейшем может быть уточнен. В реальных системах бывает достаточно ввести подтипизацию на двух-трех уровнях.
Сущность, на основе которой строятся подтипы, называется супертипом. Любой экземпляр супертипа должен относиться к конкретному подтипу. Для графического изображения принципа категоризации или типизации сущности вводится специальный графический элемент, называемый узел - дискриминатор, в нотации POWER DESIGNER он изображается в виде полукруга, выпуклой стороной обращенного к суперсущности. Эта сторона соединяется направленной стрелкой с суперсущностью, а к диаметру этого круга стрелками подсоединяются подтипы данной сущности (см. рис. 7.5).
125
Рис. 7.5. Диаграмма подтипов сущности ТЕСТ
Эту диаграмму можно расшифровать следующим образом. Каждый тест в некоторой системе тестирования является либо тестом проверки знаний языка SQL, либо некоторой аналитической задачей, которая выполняется с использованием заранее написанных Java - апплетов, либо тестом по некоторой области знаний, состоящим из набора вопросов и, набора ответов, предлагаемых к каждому вопросу.
В результате построения модели предметной области в виде набора сущностей и связей получаем связный граф. В полученном графе необходимо избегать циклических связей - они выявляют некорректность модели.
В качестве примера спроектируем инфологическую модель системы, предназначенной для хранения информации о книгах и областях знаний, представленных в библиотеке. Описание предметной области было приведено ранее. Разработку модели начнем с выделения основных сущностей.
Прежде всего, существует сущность "Книги", каждая книга имеет уникальный шифр, который является ее ключом, и ряд атрибутов, которые взяты из описания предметной области. Множество экземпляров сущности определяет множество книг, которые хранятся в библиотеке. Каждый экземпляр сущности "Книги" соответствует не конкретной книге, стоящей на полке, а описанию некоторой книги, которое дается обычно в предметном каталоге библиотеке. Каждая книга может присутствовать в нескольких экземплярах, и это как раз те конкретные книги, которые стоят на полках библиотеки. Для того чтобы отразить это, мы должны ввести сущность "Экземпляры", которая будет содержать описания всех экземпляров книг, которые хранятся в библиотеке. Каждый экземпляр сущности "Экземпляры" соответствует конкретной книге на полке. Каждый экземпляр имеет уникальный инвентарный номер, однозначно определяющий конкретную книгу. Кроме того, каждый экземпляр книги может находиться либо в библиотеке, либо на руках у некоторого читателя, и в последнем случае для данного экземпляра указываются дополнительно дата взятия книги читателем и дата предполагаемого возврата книги.
Между сущностями "Книги" и "Экземпляры" существует связь "один - ко - многим" (1:М), обязательная с двух сторон. Чем определяется данный тип связи? Мы можем предположить, что каждая книга может присутствовать в библиотеке в нескольких экземплярах, поэтому связь "один - ко - многим". При этом если в библиотеке нет ни одного экземпляра данной книги, то мы не будем хранить
126
ее описание, поэтому если книга описана в сущности "Книги", то по крайней мере один экземпляр этой книги присутствует в библиотеке. Это означает, что со стороны книги связь обязательная. Что касается сущности "Экземпляры", то не может существовать в библиотеке ни одного экземпляра, который бы не относился к конкретной книге, поэтому и со стороны "Экземпляры" связь тоже обязательная.
Теперь нам необходимо определить, как в нашей системе будет представлен читатель. Естественно предложить ввести для этого сущность "Читатели", каждый экземпляр которой будет соответствовать конкретному читателю. В библиотеке каждому читателю присваивается уникальный номер читательского билета, который будет однозначно идентифицировать нашего читателя. Номер читательского билета будет ключевым атрибутом сущности "Читатели". Кроме того, в сущности "Читатели" должны присутствовать дополнительные атрибуты, которые требуются для решения поставленных задач, этими атрибутами будут: "Фамилия Имя Отчество", "Адрес читателя", "Телефон домашний" и "Телефон рабочий". Почему мы ввели два отдельных атрибута под телефоны? Потому что надо в разное время звонить по этим телефонам, чтобы застать читателя, поэтому администрации библиотеки будет важно знать, к какому типу относится данный телефон. В описании нашей предметной области существует ограничение на возраст наших читателей, поэтому в сущности "Читатели" надо ввести обязательный атрибут "Дата рождения", который позволит нам контролировать возраст наших читателей.
Из описания предметной области мы знаем, что каждый читатель может держать на руках несколько экземпляров книг. Для отражения этой ситуации нам надо провести связь между сущностями "Читатели" и "Экземпляры". А почему не между сущностями "Читатели" и "Книги"? Потому что читатель берет из библиотеки конкретный экземпляр конкретной книги, а не просто книгу.
А как же узнать, какая книга у данного читателя? А это можно будет узнать по дополнительной связи между сущностями "Экземпляры" и "Книги", и эта связь каждому экземпляру ставит в соответствие одну книгу, поэтому мы в любой момент можем однозначно определить, какие книги находятся на руках у читателя, хотя связываем с читателем только инвентарные номера взятых книг. Между сущностями "Читатели" и "Экземпляры" установлена связь "один - ко - многим", и при этом она не обязательная с двух сторон. Читатель в данный момент может не держать ни одной книги на руках, а с другой стороны, данный экземпляр книги может не находиться ни у одного читателя, а просто стоять на полке в библиотеке.
Теперь нам надо отразить последнюю сущность, которая связана с системным каталогом. Системный каталог содержит перечень всех областей знаний, сведения по которым содержатся в библиотечных книгах. Мы можем вспомнить системный каталог в библиотеке, с которого мы обычно начинаем поиск нужных нам книг, если мы не знаем их авторов и названий. Название области знаний может быть длинным и состоять из нескольких слов, поэтому для моделирования системного каталога мы введем сущность "Системный каталог" с двумя атрибутами: "Код области знаний" и "Название области знаний". Атрибут "Код области знаний" будет ключевым атрибутом сущности.
127
Из описания предметной области нам известно, что каждая книга может содержать сведения из нескольких областей знаний, а с другой стороны, из практики известно, что в библиотеке может присутствовать множество книг, относящихся к одной и той же области знаний, поэтому нам необходимо установить между сущностями "Системный каталог" и "Книги" связь "многие - ко - многим", обязательную с двух сторон. Действительно, в системном каталоге не должно присутствовать такой области знаний, сведения по которой не представлены ни в одной книге нашей библиотеки, противное было бы бессмысленно.И обратно, каждая книга должна быть отнесена к одной или нескольким областям знаний для того, чтобы читатель мог ее быстрее найти.
Инфологическая модель предметной области "Библиотека" представлена на рис. 7.6.
Рис. 7.6. Инфологическая модель "Библиотека"
Инфологическая модель "Библиотека" разработана нами под те задачи, которые были перечислены ранее. В этих задачах мы не ставили условие хранения истории чтения книги, например, с целью поиска того, кто раньше держал книгу и мог нанести ей вред или забыть в ней случайно большую сумму денег. Если бы мы ставили перед собой задачу хранения и этой информации, то наша инфологическая модель была бы другой. Я оставлю эту задачу для вашего самостоятельного творчества.
