5.2. Базы данных и субд

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

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

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

Таким образом, для реализации даже такой простой системы на базе файловой системы:

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

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

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

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

Системы управления базами данных (СУБД) берут такую работу на себя. Прикладная система обязана знать, какое состояние данных является корректным, но всю техниче­скую работу принимает на себя СУБД.

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

Таким образом, СУБД решают множество проблем, которые затруднительно или вообще невозможно решить при использо­вании файловых систем. При этом существуют:

• приложения, для которых вполне достаточно файлов;

• приложения, для которых необходимо решать, какой уро­вень работы с данными во внешней памяти для них тре­буется;

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

Модели данных и структура БД

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

Рассмотрим некоторые наиболее известные (или «замеча­тельные») модели данных — иерархическую, сетевую, реляционную.

Иерархическая МД (ИМД). Впервые реализована в СУБД IBM — IMS (Information Management System), разработанной для поддержки банка данных по программе Apollo. При данном подходе предметная область представляется в виде совокупности структур иерархического типа (граф — «дерево»).

Основные понятия ИМД:

• поле — минимальная единица данных;

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

Конкретные данные, входящие в сегмент, называются экзем­пляром сегмента.

В ИМД существуют также следующие понятия:

. брат — узел, имеющий того же родителя, что и другой узел;

. ветвь — узел дерева вместе со всеми его отпрысками, отда­ленными потомками и родительскими источниками;

• лист — узел, у которого нет отпрысков;

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

Преимущества IMS и реализованной в ней иерархической модели:

• простота модели. Принцип построения IMS легок для по­нимания. Иерархия базы данных напоминает структуру компании или генеалогическое дерево;

• использование отношений предок/потомок. СУБД IMS по­зволяла легко представлять отношения предок—потомок (или часть—целое, причина—следствие), например: «А яв­ляется частью Б» или «А владеет В»;

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

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

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

Сетевая модель данных (модель CODASYL). В предложенной CODASYL модификации иерархической модели одна запись могла участвовать в нескольких отношениях предок/потомок. В сетевой модели такие отношения называются множества­ми (set). В 70-е гг. независимые производители программного обеспечения реализовали сетевую модель в таких продуктах, как IDMS компании Cullinet, Total компании Cincom, которые при­обрели большую популярность. Сетевые БД обладали рядом пре­имуществ:

• гибкость — множественные отношения предок—потомок позволяют сетевой БД хранить данные, структура которых сложнее обычной иерархии;

• стандартизованность — соответствие стандарту CODASYL;

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

Недостаток — жесткость БД, наборы отношений и структуру записей приходилось задавать заранее. Изменение структуры данных означало перестройку всей БД.

Реляционная модель данных и операции над отношениями

В то время как иерархическая модель в своей основе являет­ся формализацией и обобщением пользовательских свойств не­которой'конкретной системы (IMS), в случае реляционной мо­дели сначала были разработаны некоторые математические ос­новы и лишь через 5—10 лет появились первые коммерчески эффективные системы.

Реляционная модель предложена сотрудником компании IBM Е. Ф. Коддом в 1970 г. В настоящее время эта модель явля­ется фактическим стандартом, на который ориентируются прак­тически все современные коммерческие СУБД.

В реляционной модели достигается гораздо более высокий уровень абстракции данных, чем в иерархической или сетевой. Это обеспечивается за счет использования математической теории отношений (само название «реляционная» проис­ходит от английского relation — «отношение»).

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

Декартово произведение', для заданных конечных множеств D\, Di, ..., D_n (не обязательно различных) декартовым (прямым) произведением D, xi), х ... х I), называется множество набо­ров: {d_u cl₂, ..., d_N), где d_] • /->.. d- е D_:, ..., d_N е О... .

Например, если даны два множества А = {а_}, а₂, а₂} и В = {b_ub₂}, их декартово произведение будет иметь вид

С=Ах В ={{Я„6,}, {яАЬ fe₃>M>

Отношение, отношением R, определенным на множествах D\, Dj, ..., Ay, называется подмножество декартова произведения D\ х D₂ х ■■• х Dк. При этом:

d,}

множества £>,, Д, ..., D_N называются доменами отношения;

элементы декартова произведения {d^ d₂, ..., кортежами;

число N определяет степень отношения (А^г= 1 — унарное, N=2 — бинарное, ..., TV-арное);

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

На множестве С из предыдущего примера могут быть опре­делены отношения

R_l = {{а,, />,}, {а₃, Ь₂}} или R₂ ={{о,, 6,}, {fl₂, |j'}, {a_v &,}}.

Отношения удобно представлять в виде таблиц. Строки таблицы называются экземплярами отношения, столб­цы — атрибутами; каждый атрибут имеет область значений, называемую доменом. На рис. 5.6 представлена таблица (отно­шение степени 5), содержащая некоторые сведения о деталях ав­томобилей.

называются

Номер_ детали	Название_детали	Количество	Вес	Материал
123-476А	Втулка	12 000	0,8	Сталь■
581-93C	Педаль	10 000	1,0	Сталь
256-3/К	Ступица	5000	0,5	Сталь
421/27Р	Передний тормоз	11 000	0,5	Алюминий
573/21К	Крыло	300	0,7	Пластмасса

С^Ямя таблицы

Имя столбца

Деталь

Материал

^Сталь Пластмасса Стекло Алюминий

Первичный ключ^> Рис 5.6. Таблица (отношение) реляционной модели данных

Домен

I

А

I

о

\J

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

значений — Сталь, Олово, Цинк, Никель И Т. д. В столбце Ко­личество содержатся целые неотрицательные числа. Значения в столбце Вес — вещественные числа, равные весу детали в ки­лограммах.

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

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

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

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

Руководитель

-Номер	Фамилия	Отдел	Стаж
5742	Васильев	26К	25
6931	Успенский	31С	27
2345	Воробьев	19И	21

Номер	Фамилия	Номер р'уководит§р?Г	Д9йжность
4781	Юдин	СЗ742^ /	/ м. н. с.
5325	Шадрин	6931 /	с. н. с.
3120	Яковлев	Cj>jATy	и. с.
1230	Кротов	2345	вед. инж.
2138	Куркин	6931	ст. инж.

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

Номер (например, табельный номер). Столбец Фамилия не может выполнять роль первичного ключа, так как в одной организации могут работать два руководителя с одинаковыми фамилиями. Любой служащий подчинен единственному руководителю, что должно быть отражено в базе данных. Таблица Служащий содер­жит столбец Номер__руководителя, и значения в этом столбце выбираются ИЗ столбца Номер таблицы Руководитель (см. рис. 5.7). Столбец Номер_Руководителя является внешним ключом В таблице Служащий.

Таблицы невозможно хранить и обрабатывать, если в базе данных отсутствуют «данные о данных» (метаданные), на­пример, описатели таблиц, столбцов и т. д. Метаданные также представлены в табличной форме и хранятся в словаре данных (DD — data dictionary) или описателе БД (DBD — data base definition) — служебном файле или системной таблице БД.

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

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

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

торые ограничения, которые называют ограничениями цело­стности (data integrity constraints).

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

Свойства отношений.

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

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

Атомарность значений атрибутов, т. е. среди зна­чений домена не могут содержаться множества значений (отно­шения).

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

Операндами реляционной алгебры являются отношения как постоянные, так и переменные.

Операции реляционной алгебры включают следующие преоб­разования отношений.

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

Б. Операции над одним отношением:

• селекция, или построение отношения-результата из отно­шения-источника путем отбора экземпляров, удовлетво­ряющих некоторому критерию отбора. Операция селекции соответствует поиску информации в БД по логическим ус­ловиям; (find ... with, find...where, locate, CM.

табл. 5.5);

• проекция, или построение результирующего отношения пу­тем отбора части атрибутов всех экземпляров исходного отноше­ния. Данной операции в реальных СУБД соответствует понятие пользовательской подсхемы и операции выдачи необходимых данных (display, view, set form to, report form...).

В. Операции над несколькими различными отношениями.

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

В СУБД соединению соответствует поиск связанных дан­ных или логическое (физическое) связывание файлов (find...coupled, set relation to, join).

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

Язык SQL

С целью стандартизации формального описания запросов к базе данных они формулируются на стандартном языке запросов (ЯМД — язык манипулирования данными), которым для многих СУБД является SQL [8].

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

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

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

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

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

Оператор	Выполняемое действие
SELECT	Выбрать строку (группу строк) из таблицы базы данных
INSERT	Добавить строку (группу) в таблицу базы данных
UPDATE	Изменить строку (группу) таблицы базы данных
DELETE	Удалить строку (группу) из базы данных
GRANT	Предоставить привилегии пользователю
REVOKE	Отменить привилегии пользователя
COMMIT	Зафиксировать текущую транзакцию

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

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

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

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

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

FROM Деталь.

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

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

SELECT *

FROM Деталь

WHERE Материал = 'Сталь'.

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

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

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

FROM Деталь

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

AND Вес < 5

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

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

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

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

FROM Деталь

WHERE Номер = 'Т14 5-А8';

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

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

Индекс создается оператором SQL create index (создать индекс) . В данном примере оператор

CREATE UNIQUE INDEX И:-:декс_детали

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

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

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

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

Язык SQL является реляционно полным, т. е. сово­купность операторов языка обеспечивает необходимый минимум операций реляционной алгебры (селекция, проекция, соедине­ние и пр.).

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

Объекты	Системы
или операции	STAIRS	ADABAS	FoxPro	Irbis	ORACLE/SQL
Открыть(закрыть сеанс,	..DIAL INiS	OP FILE,	USE FILENAME,	Пункт меню	START,
базу данных)	..OFF	CL FILE	CLEAR ALL	БАЗА ДАННЫХ	QUIT
Инверсный поиск записей	..SEARCH	FIND WITH	SEEK FIND	Все поиски	SELECT FROM... WHERE...
Сканирующий поиск	..SELECT	FIND WHERE	LOCATE (CONTINUE), EDIT, FOR, WHILE	Нет	SELECT FROM... WHERE...
Чтение в физическом по­	..BROWSE	READ BY ISN	SET INDETO	Пункт меню	ORDER BY
рядке		READ PHYSICAL	SKIP,EDIT,	СОРТИРОВАТЬ
Чтение в логическом поряд­ке, группирование записей (прерывание)	.. BROWSE	READ BY, READ LOGICAL, SORTED.. (AT BREAK...)	SET INDEX TO SORT BY	СОРТИРОВАТЬ	ORDER BY, (GROUP BY...)
Удаление записи, вставка записи, изменение записи	Для пользователя - нет	DELETE, STORE, UPDATE	DELETE, INSERT, REPLACE BY...	Для пользователя нет	DELETE, INSERT, UPDATE
Вывод строки данных	Нет	WRITE	SAY, ?,??	ПЕЧАТЬ	SQL*REPORT

о,

К)

Г

Си

а а

П |

Окончание табл. 5.5

Объекты	Системы
или операции	STAIRS	ADABAS	FoxPro	Irbis	ORACLE/SQL
Задание формата выдачи	..BROWSE	DISPLAY	CREATE FORM, CREATE REPORT	СПИСОК ФОРМАТОВ (СХЕМ)	SQL*FORM, SQL*REPORT
Вывод отчета	. BROWSE	DISPLAY	REPORT	ПРОТОКОЛ	SQL'FORM, SQL'REPORT
Вывод/ввод экрана		INPUT/ REINPUT	EDIT	ПЕЧАТЬ, ВЫВОД В ФАЙЛ	SQL*FORM, SQL'REPORT
Агрегатные функции	Подсчет числа выдан­ных документов	MAX, MIN, AVER, COUNT	Задаются при создании формата	Нет	MAX, MIN, AVER, COUNT
Создание файла, базы дан­ных	READER	LOADER	CREATE STRUCTURE	Утилита IRBISDDM	CREATE DATABASE, TABLE
Удаление файла	Нет	DBMOD	команда ОС DEL	-	DROP TABLE
Создание/ модификация структуры	Нет	LOADER FILEMOD	CREATE/' MODIFY STRUCTURE	-	ALTER TABLE (ALTER, DROP COLUMN)
Создание подсхем	Команда ..BROWSE	MAINT	CREATE/MODIFY VIEW, SCREEN	-	CREATE VIEW

К» Оо 55

Модель «сущность—связь»

Модель сущность—связь или Entity-Relationship (ER) пред­ставляет собой обобщение РМД путем разделения отношений, описывающих предметную область на две группы — сущностей и связей.

Сущность (Entity) является первичным, устойчивым объектом, описываемым некоторой совокупностью атрибутов.

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

Основные представления о структуре БД в рамках указанной модели заключаются в следующем:

а) совокупность сущностей и связей образует концептуальную схему базы данных и отражает структуру предметной области. Элементами схемы являются типы (классы) сущностей и связей; типы состоят из экземпляров, описывающихся значениями ат­рибутов. На рис. 5.8 приведен пример фрагмента диаграммы «сущность — связь», описывающей учебный процесс вуза. Здесь сущностями ЯВЛЯЮТСЯ факультет, дисциплина, специальность

(с возможными атрибутами, например наименование, про­должительность обучения, число часов И Пр.). СВЯЗЯМИ ЯВ­ЛЯЮТСЯ выпускает, включает (возможные атрибуты —

квалификация, семестр обучения и пр.);

Рис. 5.8. Пример диаграммы «сущность—связь»

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

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

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

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

Рассмотрим вкратце обобщенные логическую и физическую структуры БД.

Логическая структура БД (рис. 5.9) предполагает следующие уровни рассмотрения БД:

. база данных (database) — включает одну или несколько под­баз (файлов, таблиц, массивов), каждая из которых состоит из агрегатов данных (записей, документов) — record. Запись идентифицируется внутренним номером (ISN — internal sequential number, ВИЗ — внутренний номер записи, SDN — sequential document number и пр.);

Рис. 5.9. Основные элементы логических структур данных в БД: 1 — поля записей табличных (реляционных) баз данных (ORACLE, FoxPro, Acesss); 2 — поля записей (документов) постреляционных БД (ADABAS); 3 — поля документов ИПС (STAIRS, Dialog, IRBIS, ISIS); 4 — данные, которые мо­гут быть связаны с полями базы данных

• запись (документ) — совокупность разнотипных и разно- структурных данных, описывающих (относящихся к) объ­ект реального мира, элемент предметной области АИС. За­пись состоит из полей (field);

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

• элементарные (имеющие фиксированную или ограничен­ную длину) и не содержащие входящих в них структур данных;

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

• текстовые — поля переменной (неопределенной) длины и сложной внутренней структуры (обычно это иерархическая последовательность типа раздел-подраздел-предложе­ние-слово);

• бинарные — данные, интерпретируемые как поля, однако обычно физически не входящие в состав записей БД. Не­обходимо отметить, что поля данного типа (BLOB — Binary Large Object) фактически являются данными, до обработки которых данная СУБД еще «не доросла» и поэтому работа с ними возлагается на пользователя (прикладные програм­мы). В частности, в системах FoxBase и Clipper большие текстовые (так называемые MEMO) поля также не обраба­тываются системой и фактически оказываются в статусе BLOB;

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

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

Поля, указанные в заштрихованных прямоугольниках (см. рис. 5.9) относятся к фактографическим АИС, остальные — к до­кументальным.

Физическая структура БД в обшем случае имеет вид, приве­денный на рис. 5.10, и включает следующие компоненты:

• файл (файлы) исходных (первичных) данных (текстов, бинар­ных данных) содержит собственно объекты, подлежащие поиску, обработке и пр.;

Рис. 5.10. Обобщенная физическая структура данных в БД

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

• индекс — файл (файлы), связывающий адрес (номер) объ­екта с его содержанием (значением атрибута объекта), обычно состоит из инверсного списка и частотного слова­ря, который облегчает составление запросов на поиск и по­вышает обозримость БД;

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

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

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

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

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

• в справочно-библиографических БД текстовые данные на­ходятся во вторичном файле, а первичный отсутствует:

• в БД с полнотекстовым поиском может отсутствовать вто­ричный файл, а индексирование (построение частотных словарей и инверсных списков) проводится по первичному файлу (страницы или абзацы полных текстов);

• может отсутствовать частотный словарь или инверсный список.

Надо отметить также вариативность физической реализации и взаимосвязи лингвистического и информационного обеспече­ния АИС:

• словарь данных может физически входить в информацион­ные файлы (первичный или вторичный);

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

Обработка транзакций

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

Традиционные транзакции характеризуются четырьмя свой­ствами: атомарности, согласованности, изолиро­ванности, долговечности (прочности) — ACID (Atomicity, Consistency, Isolation, Durability). Иногда традицион­ные транзакции называют ACID-транзакциями. Упомянутые выше свойства означают следующее:

• атомарность — операции транзакции образуют нераздели­мый, атомарный блок с определенным началом и концом. Этот блок либо выполняется от начала до конца, либо не выполняется вообще. Если в процессе выполнения тран­закции произошел сбой, происходит откат (backup, воз­врат) к исходному состоянию;

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

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

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

Расширенные транзакции допускают формирование из ACID-транзакций иерархических структур. Если конкретная мо­дель ослабляет некоторые из требований ACID, то речь идет об ослабленной транзакции.

Возможны два варианта завершения транзакции. Если все операторы'выполнены успешно, и в процессе выполнения тран­закции не произошло никаких сбоев программного или аппарат­ного обеспечения, транзакция фиксируется.

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

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

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

В стандарте ANSI/ISO SQL определены модель транзакций и функции операторов commit и rollback. Стандарт определяет, что транзакция начинается с первого SQL-оператора, иниции­руемого пользователем или содержащегося в программе. Все по­следующие SQL-операторы составляют тело транзакции. 'Гран- закция завершается одним из четырех возможных способов (рис. 5.11):

• оператор commit означает успешное завершение транзак­ции; его использование делает постоянными изменения, внесенные в базу данных в рамках текущей транзакции;

• оператор rollback прерывает транзакцию, отменяя изме­нения, сделанные в базе данных в рамках этой транзакции; новая транзакция начинается непосредственно после ис­пользования rollback;

• успешное завершение программы, в которой была иниции­рована текущая транзакция, означает успешное завершение транзакции (как будто был использован оператор commit) ;

• ошибочное завершение программы прерывает транзакцию (как будто был использован оператор rollback).

Точки сохранения применяются, как правило, в протяжен­ных транзакциях и позволяют разделить транзакцию на не-

Рис. 5.11. Модель транзакции ANSI/ISO

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

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

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

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

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

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

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

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

• если две транзакции, А и В, выполняются параллельно, то

СУБД полагает, что результат будет такой же, как если бы:

• транзакция А выполнялась первой, а за ней была выпол­нена транзакция В\

• транзакция В выполнялась первой, а за ней была выпол­нена транзакция А.

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

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

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

В современной литературе часто встречается термин OLTP (On-Line Transaction Processing), который обычно переводят как «оперативная обработка транзакций», т. е. выполнение транзак­ций в режиме реального времени. Система OLTP обязана учи­тывать жесткие временные требования, следующие из специфи­ки прикладной области. Например, процедура покупки и оформления авиабилета должна происходить быстро и не задер­живать очередь. Система, регистрирующая продажи билетов, должна обрабатывать одновременно несколько сотен запросов (транзакций), поступающих от множества продавцов авиабиле­тов. Требования по скорости обработки запроса могут быть очень жесткими, однако вызваны они требованиями реальной жизни. Если говорить о прикладных областях OLTP, то это, прежде всего, центры кредитных карточек, системы резервиро­вания авиабилетов и мест в отелях, телекоммуникационные системы и т. д.

Классы и структуры систем управления базами данных

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

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

СУБД (DBMS — database management system) — комплекс языков и программ, позволяющий создавать БД и управлять ее работой. СУБД обрабатывает поступающие от пользователей и прикладных процессов обращения к БД, а затем выдает необхо­димые им сведения. СУБД характеризуется используемой моде­лью и средствами администрирования, разработки прикладных процессов, работы в информационной сети.

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

СУБД обеспечивает:

• описание и контроль данных;

• манипулирование данными (запись, поиск, выдачу, изме­нение содержания);

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

• защиту от сбоев, поддержку целостности и восстановление;

• работу с транзакциями и файлами;

• безопасность данных.

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

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

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

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

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

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

По используемому языку общения:

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

• открытые, в которых для общения с БД используется язык программирования, «расширенный» операторами языка манипулирования данными (ЯМД). В этом случае необхо­димо участие квалифицированного программиста.

По числу поддерживаемых СУБД уровней моде­лей данных: одно-, двух-, трехуровневые системы. Теоретически обоснован выбор трехуровневой архитектуры данных, однако на практике СУБД для персональных ЭВМ часто объединяют кон­цептуальный и внутренний уровни представления.

По выполняемым функциям:

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

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

По сфере применения:

• универсальные, настраиваемые на любую предметную об­ласть путем создания соответствующей БД и прикладных программ;

• проблемно-ориентированные на определенные процедуры обработки данных, присущих конкретной области приме­нения.

В структурном составе СУБД могут быть выделены ядро и среда (рис. 5.12) [14, 32].

Ядро СУБД — программный комплекс (модуль или модули), обеспечивающий непосредственное выполнение физических

ИНТЕРФЕЙСЫ

БАЗА ДАННЫХ

Рис. 5.12. Типичная структура системы управления базами данных

операций над БД (в ранних системах функции Ядра выполняли программы методов доступа ОС ЭВМ).

Среда — совокупность интерфейсных модулей, обеспечиваю­щих связь пользователей с Ядром и через него с БД. Среда включает в себя пользовательские интерфейсы и утилиты администратора БД (АБД).

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

• физическая подготовка дисковой памяти к размещению БД;

• подготовка справок о составе БД, структуре файлов, коли­честве данных и занимаемом объеме;

• загрузка файла БД из последовательного набора дан­ных ОС;

• дозагрузка (расширение существующего файла);

• модификация БД: расширение или перемещение физиче­ских наборов данных, реорганизация;

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

. выгрузка образа БД (файла таблицы) для сохранения в ар­хивном наборе данных;

• создание и ведение словаря данных и др.

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

• диалоговые интерфейсы;

• генераторы отчетов;

• система конструирования и поддержки интерактивных тех­нологий в информационных системах (ЯП АИС).

5.3. Физическая организация данных в системах управления данными

Расширим вкратце некоторые принципы физической орга­низации данных.

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

С общепринятой точки зрения к вопросам организации дан­ных относятся:

• выбор типа записи — единицы обмена в операциях вво­да-вывода;

• выбор способа размещения записей в файле и, возможно, метода оптимизации размещения;

• выбор способа адресации и метода доступа к записям.

Типы записей

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

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

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

На логическом уровне выделяют следующие типы:

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

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

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

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

Организация файлов — способ размещения записей

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

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

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

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

• ускорением или упрощением средств адресации файла (на­пример, средств прямой адресации или хэширования);

• уменьшением размера используемого индекса и сокраще­нием, таким образом, времени поиска в нем;

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

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

Можно выделить две «чистые» стратегии определения места (адреса) для размещения записей: последовательное (sequential) и произвольное (random) размещение. В этом смысле алгоритм размещения определяет тип организации файла.

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

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

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

Страничная организация

Параллельная секционная организация

Размещение соответственно

частоте использования

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

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

Рис. 5.13. Способы организации файлов

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

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

Способы адресации и методы доступа к записям

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

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

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

Основные проблемы при адресации файла можно сформули­ровать следующим образом:

• по первичному ключу определить местоположение записи с данным ключом;

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

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

Существует несколько различных способов адресации и по­иска записей, например на основе упорядочения, различных ин­дексов, преобразования «ключ—адрес».

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

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

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

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

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

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

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

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

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

• ключ записи преобразуется в псевдослучайное число, нахо-

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

• число преобразуется в адрес блока и, если в нем есть сво­бодное место, то логическая запись размещается там;

• если блок заполнен, запись должна быть размешена в бло­ке (блоках) переполнения — следующий по порядку блок либо блок отдельной области переполнения.

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

Архитектура файловой организации баз данных

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

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

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

Таким образом, БД физически состоит из нескольких фай­лов: основного, индексного, файла метаданных, файлов указате­лей и т. д. (рис. 5.10, 5.14, а). В этом случае ОС активно уча­ствует в навигации, беря на себя функции выборки, об­новления, вставки, удаления записей из физических файлов.

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

Перечислим типовые понятия страничной организации хра­нения данных (рис. 5.14, б).

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

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

1

2

N

Заголовок

Дескрипторы

Содержание

Рис. 5.14. Файл-ориентированная (о) и страничная (б) организация данных

б

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

Все страницы данных имеют одинаковую структуру, вклю­чающую:

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

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

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

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

Модели распределения данных по физическим носителям

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

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

Примером, иллюстрирующим подход с точки зрения практи­ческих компромиссов выбора решения, являются RAID-масси- вы. На рис. 5.15 приведены два варианта: RAID-0, обеспечиваю­щий максимальную производительность при «стандартной» на-