Гайдамакин Н.А. Автоматизированные информационные системы, базы и банки данных. Вводный курс Учебное пособие

Подождите немного. Документ загружается.

2.2. Модели

оргашпации

данных

чом «№ отдела» и отсылаемая (связанная) таблица «Отделы» с

первичным ключом «№ отдела» (см. рис. 2.4). Если существу-

ет кортеж-запись «Иванов», работающий в отделе №

710,

то в

таблице «Отделы» обязательно должен быть кортеж-запись с

соответствующим номером отдела (каждый сотрудник должен

обязательно в каком-либо отделе хотя бы числиться).

Теоретико-множественный характер реляционных таблиц-

отношений требует также отсутствия упорядоченности кор-

тежей и отсутствия упорядоченности полей-атрибутов. От-

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

шениях усложняет поиск нужных кортежей при обработке

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

нахождения нужной записи таблицы без постоянного упорядо-

чения (переупорядочения) записей при любых изменениях дан-

ных

вводят

индексирование полей

{обычно

ключевых). Индек-

сирование полей, или лучше сказать создание

индексных

мас-

сивов, является типовой распространенной операцией

практически во всех СУБД, поддерживающих и другие, не ре-

ляционные модели данных, и заключается в

построегши

допол-

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

строго доступа к записям-кортежам.

Все операции

надданными

в реляционной модели (мани-

пуляционная составляющая) можно

рсоделить

на

две

группы—

операции обновления таблиц-отношений и операции обработ-

ки таблиц-отношений.

К операциям обновления относятся:

• операция ВКЛЮЧИТЬ

—добавляет

новый кортеж (стро-

ку-запись) в таблицу-отношение. Требует задания имени таб-

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

ловии уникальности значения ключа. Добавить новую строку-

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

невозможно;

• операция УДАЛИТЬ — удаляет одну или

фуппу

корте-

жей (строк-записей). Требует задания имени таблицы, имени

поля (группы полей) и параметров значений полей, кортежи с

которыми должны быть удалены;

2. СУБД

фактографических

информационных

систем

о операция ОБНОВИТЬ — изменяет значение не ключе-

вых полей у одного или группы кортежей. Требует задания име-

ни таблицы-отношения, имен полей и их значений для выбора

кортежей и имен изменяемых полей.

Особенностью операций обработки в реляционной модели

по сравнению с иерархической и сетевой моделью является то,

что в качестве единичного элемента обработки выступает не

запись (экземпляр объекта), а таблица в целом, т. е. множество

кортежей (строк-записей). Поэтому все операции обновления

являются операциями

надмножествами

их

результатом яв-

ляется также множество, т. е. повал таблица-отношение. К

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

а операция

ОБЪЕДИНЕНИЕ—выполняется

над двумя

односхемными

таблицами-отношениями. Результатом объеди-

нения является построенная по той же схеме таблица-отноше-

ние, содержащая все кортежи первой таблицы-отношения и все

кортежи второй таблицы-отношения. При этом кортежи-дуб-

ликаты в итоговой таблице устраняются;

а операция ПЕРЕСЕЧЕНИЕ — выполняется также над

двумя односхемными таблицами-отношениями. Результатом яв-

ляется таблица-отношение, построенная по той же схеме и со-

держащая только те кортежи первой таблицы-отношения, ко-

торые входят также в состав кортежей второй таблицы-отно-

шения. Для примера рассмотрим таблицу «Сотрудники» со

схемой (полями) «ФИО», «Год рождения», «Национальность»

и таблицу «Вкладчики банка «НАДЕЖНЫЙ» стой же схемой.

Результатом их пересечения будет новая таблица

стой

же схе-

мой, содержащая кортежи только тех сотрудников, которые

имеют вклады в банке «НАДЕЖНЫЙ», что иллюстрируется

примером, приведенным на рис. 2.5;

• операция ВЫЧИТАНИЕ

—

вьшолняется также над дву-

мя односхемными таблицами-отношениями. Результатом явля-

ется таблица-отношение, построенная по той же схеме и со-

держащая только те кортежи первой таблицы-отношения, ко-

торых нет в составе кортежей второй таблицы-отношения.

Результатом операции вычитания над таблицами в предыдущем

2.2. Модели организации данных

Первая таблица

'Сотрудники'

Вторая таблица

"Вкладчики Банка

"НАДЕЖНЫЙ"

Пересечение

"Сотрудники, имеющие

вклады в банке

Фамилия

Иванов

Петров

Сидоров

Егоров

Год

рождения

1958

1961

1972

1968

Фамилия

Иванов

Сидоров

Сергеев

Морозов

Год

рсокдения

1958

1972

1973

1956

"НАДЕЖНЫЙ"

Фамилия

Иванов

Сидоров

Год

р<зокдения

1958

1972

Рис. 2.5. Пример операции ПЕРЕСЕЧЕНИЕ

примере будет новая таблица

той же схемой, содержащая кор-

тежи только тех сотрудников, которые не имеют вкладов в бан-

ке «НАДЕЖНЫЙ»;

• операция ПРОИЗВЕДЕНИЕ (ДЕКАРТОВО) — выпол-

няется над таблицами-отношениями с разными схемами. Резуль-

татом является таблица-отношение, схема которой включает все

поля первой и все поля второй таблицы. Кортежи (строки-за-

писи) результирующей таблицы образуются путем последова-

тельного сцепления каждого кортежа первой таблицы-отноше-

ния к каждому кортежу второй таблицы-отношения. Количе-

ство кортежей результирующей таблицы

соответственно

равно

произведению количества кортежей первой таблицы на коли-

чество кортежей второй таблицы. На рис. 2.6 иллюстрируется

пример операции произведения;

а операция ВЫБОРКА (горизонтальное подмножество) —

выполняется над одной таблицей-отношением. Результатом яв-

ляется таблица-отношение той же схемы, содержащая подмно-

жество кортежей исходной таблицы-отношения, удовлетворя-

ющих условию выборки;

• операция ПРОЕКЦИЯ (ВЕРТИКАЛЬНОЕ ПОДМНО-

ЖЕСТВО)

—также

выполняется над одной таблицей-отноше-

нием. Результатом является новая таблица-отношение, схема ко-

торой содержит только некоторое

подмножество

полей исход-

ной таблицы-отношения. Каждому кортежу исходной таблицы

2. СУБД

фактографических

ппформацпопних

систем

Рис.

2.6.

Пример операции произведения

соответствует кортеж итоговой таблицы, образованный соот-

ветствующими значениями по полям, вошедшим в итоговую

таблицу-отношение.

При

этом

в итоговой таблице кортежи-дуб-

ликаты устраняются и поэтому мошрость итоговой таблицы (ко-

личество кортежей) может быть равна или меньше исходной.

На рис. 2.7 приведен пример операции проекции;

Исходная таблица Проекция на поля

"Меао

работы" и 'Банк"

"Члены неформальной группы "ДИКИЕ 'Организации и банки иеформальнойгруппы

ЭКОЛОГИ""

-ДИКИЕ

ЭКОЛОГИ""

Фаиилияи

инициалы

Быков

Б.

Б,

Волков

В,В,

Зайцев 3,3,

Лисицын

Л.

Медведев

M.W

РысинР.Р ,

Хомяков

Х,Х

Щукин Щ,Щ.

Место ра&оты

ЗАО "Дикое поле"

ЗАО'

Никое поле"

ЗАО "Дикое поле"

ОАО 'Рога и копыта'

ОАО

"Рога

и копыта"

ЗАО

"Дикое

поле'

СП "Степь"

ООО "Море"

Банк

"Надежный"

"Солидный"

"Прибыльный"

'Альтруист'

"Солидный"

"Альтруист"

"Солидный"

Место работы

ЗАО "Дикое поле"

ЗАО'

Дикое поле"

DAO

"Рога и копыта"

ОАО "Рога и копыта"

СП "Степь"

ЭОО

"Море"

Банк

"Надежный"

"Солидный"

'Прибыльный"

"Альтруист"

Солидный"

Рис.

2.7.

Пример операции проекции

• операция

СОЕДИНЕНИЕ—выполняется

над таблица-

ми-отношениями с разными схемами. В каждой таблице-отно-

шении вьщеляется поле, по которому будет осуществляться со-

единение. При этом оба поля должны быть определены на од-

ном и том же домене. Схема итоговой таблицы-отношения

включает все поля первой таблицы и все поля второй таблицы

2.2.

Модели

организации данных

(как в произведении). Кортежи итоговой таблицы-отношения

образуются путем сцепления каждого кортежа из первой таб-

лицы

теми кортежами второй таблицы, значения которых по

полю сцепления одинаковы. На рис. 2.8 приведен пример опе-

рации соединения;

Первая табпица

Документы с

охраняемыми

сведениями по

ОКГ

" Закрытая"

Рег.т

13/1

-с

251-сс

1455-с

И-43С

Тематика

Топливо

Боезаояд

Двигатель

Привод

Вторая

табпица

Журнал

выдачи

документов сотрудникам

Рег.Ля

12435

654 32

251-сс

И-43С

123-н/с

345

1455-с

675-н/с

И-43С

Да.

та

1.11

2.11

3.11

4.11

311

Фанилия

инициалы

Иванов

И.И .

Иванов

П.

Петров

П.П .

Сидоров С.С

Петров П.П.

Егоров Е.Е.

Петров П.П

Сидоров С.С

Иетсов

11.11

Соединение по

попю"

Рег.Ш"

Сотрудники, работавшие с

документами, содержащими

охраняемые сведения

Рег^Уо

251-сс

1455-с

И-43С

И-4

3с

Тематика

Боезаряд

Двигатель

Привод

Да-

та

2.11

4.11

2.11

3.11

Фсеиилия

инициалы

Петров П.П.

"идороЕ

С.С

Петров П.П.

Рис. 2.8. Прюмер операции соединения

• операция ДЕЛЕНИЕ — выполняется над двумя табли-

цами-отношениями, первая из которых называется делимым, а

вторая делителем. При этом схема таблицы-делителя должна

состоять из подмножества полей таблицы делимого. Схема ито-

говой таблицы-отношения содержит только те поля таблицы-

делимого, которых нет во второй

таблице-делителе.

Кортежи

итоговой таблицы-отношения образуются на

основе

кортежей

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

итоговую таблицу при условии того, что если взять произведе-

ние (декартово) итоговой таблицы-отношения и второй табли-

цы-отношения (делителя), то образуются соответствующие кор-

тежи первой таблицы (делимого). На рис. 2.9 приведен пример

операции деления.

В своем исходном виде манипуляционная составляющая

реляционной модели не предусматривает операции над поля-

ми-атрибутами и схемами таблиц-отношений. Однако на прак-

тике применение рассмотренных выше операций манипулиро-

2. СУБД

фактографических

ииформациоииых

систе м

Таблица-делимое

Поездки граждан г.

Урюпинасав

Германию

Таблица-делитель Итоговая таблица

Граждане с

Требуемое сочетание требуемым

турфирм и городов сочетанием

Германии турфирм и городов

Ф.И.О.

Иванов И.И.

Петров П.П.

СИДОРОВ

С^

Сидоров С.

Турфирма

"Евротур'

"Веси*

"Евротур"

"Веси"

Евр'ЭТУР '

"Веси'

Город

Берлин

Гамбург

Берлин

Берл:

Гамбург"

Турфирма

"Евротур"

"Беси"

Город

Берлин

Гамбург

Ф.И.О.

Иванов

И И

Сидоров

С.С .

Рис.

2.9.

Пример операции деления

вания данными может приводить к временным нарушениям тре-

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

специальными операциями переименования, удаления, добав-

ления полей-атрибутов.

Реляционная модель организации данных сыграла трудно

переоценимую роль в развитии программного обеспечения

АИС. Именно реляционные СУБД были тем программным ин-

струментарием, на основе которого происходила массовая ин-

форматизация малых и средних предприятий и организаций в

80-х годах. В начале 90-х годов реляционные СУБД

ст^ши

фак-

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

формационных систем. Вместе

тем проявились и определен-

ные ограничения реляционной модели, которые не позволяют

адекватно описывать такие сложные предметные области, как

конструирование, производственные технологические процес-

сы и др. Поэтому в 90-х годах были предприняты попытки со-

здания новых усовершенствованных моделей организации дан-

ных в виде постреляционпых СУБД и объекпто-ориептировап-

ных СУБД. К сожалению, до сей поры ни одна из попыток

создания и описания новых моделей описания данных не

стандартизована, и количество коммерческих СУБД, основан-

ных на новых моделях данных, исчисляется единицами.

2.3. Внутренняя

схема

баз данных фактографических АИС

2.3. Внутренняя схема баз данных

фактографических АИС

Изначально и по сей день программное обеспечение АИС

(СУБД) в качестве места физического размещения данных ори-

ентировано на внешнюю (дисковую) память. Как уже отмеча-

лось, размещение данных во внешней памяти, точнее эффек-

тивность доступа к ним во внешней памяти, существенно вли-

яет на

э{1)фективность

обработки данных. В

результате

важным

аспектом АИС является внутренняя схема базы данных, кото-

рую организует и поддерживает СУБД.

В общем плане внутренняя схема базы данных включает

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

2.10.

Системная

информация по БД

(каталог

БД)

структура БД

- ограничения

целостности данных

Информационные массивы

Дамних

Индексов

•X,

Прикладная

интерфейсная

часть

'запросы

- процедуры

соЕс^пня

• првгипа

- код интерфейса

Единьй

файл или совокупность файлов

Рис.

2.10.

Состав внутренней схемы базы данных

Центральным компонентом внутренней схемы являются ин-

формационные массивы, включающие собственно данные (ин-

формационных объектов логической схемы БД, т. е. в реляци-

онных СУБД таблиц), и массивы индексов, являющихся специ-

альными дополнительными конструкциями для ускорения

доступа к данным основных информационных объектов. Ин-

формационные массивы в большинстве СУБД состоят из од-

ной или нескольких так называемых страниц, каждая из кото-

2. СУБД

фактографических

ииформацпоипых

систем

рых содержит совокупность некоторых единичных элементов,

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

элементом внутренней схемы баз данных АИС является физи-

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

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

СУБД

с табличной

строкой.

Способы организации записей в страницах (расположение,

добавления, корректировка, удаление) составляют физические

структуры

данных,

которые образуют третий (низший) уро-

вень представления информации в информационной системе

(см. рис.

1.4).

Важным компонентом внутренней структуры является ка-

талог БД, в котором размещается системная информация по

логической структуре БД, включающая описание основных ин-

формационных объектов (имена, структура, параметры, связи)

и ограничения целостности данных. Организация системной

информации БД определяется особенностями конкретной

СУБД,

а сам каталог может входить непосредственно в файлы

данных (область описателей данных) или составлять отдель-

ный информационный массив.

Как уже отмечалось, в состав автоматизированного банка

данных АИС помимо самой базы данных входит и прикладной

компонент, образуемый совокупностью интерфейсных элемен-

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

сов и процедур обработки данных, а также «событий» и «пра-

вил», отражающих правила и специфику предметной области

АИС (так называемые «правила бизнеса»). Соответственно во

внутренней схеме БД выделяется специальная область, в кото-

рой размещается информация по прикладному компоненту

АИС.

Все три части внутренней структуры и их составные эле-

менты (например, информационные массивы отдельных инфор-

мационных объектов БД) могут размещаться в одном едином

файле базы данных или в разных файлах. Во втором случае

внутренняя схема БД определяется совокупностью и порядком

расположения данных файлов.

2.3. Внутренняя

схема

баз данных фактографических АИС

2.3.1. Физические структуры данных

Страничная организация информационных массивов БД оп-

ределяется общей спецификой доступа к данным больших объе-

мов. Доступ к физическим записям во внешней памяти в боль-

шинстве СУБД осуществляется через считывание в оператив-

ную память страниц файла данных, содержащих

соответствующие записи. Непосредственная обработка записей

производится в оперативной памяти, для чего СУБД образует и

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

торых временно размещаются страницы, содержащие обраба-

тываемые записи. После завершения обработки страница с со-

ответствующими записями «выталкивается» из буфера и фик-

сируется в дисковом файле.

Аналогичным образом осуществляется размещение и дос-

туп к индексным массивам. В итоге общий принцип организа-

ции доступа к данным во внешней памяти можно проиллюст-

рировать схемой, приведенной на рис.

2.11.

Физические структуры организации файлов данных под-

разделяются на линейные и нелинейные.

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

ных объединяются записи-кортежи одной таблицы (информа-

ционного объекта), которые располагаются в последователь-

ном (линейном) порядке друг за другом. Каких-либо ссылок,

указателей на связи между записями не предусматривается.

Если не применяется специального порядка размещения за-

писей в страницах (так называемая «расстановка» записей), то

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

структурах каждая новая запись помещается непосредственно

за последней записью. Если страница файла

данных

заполня-

ется, то для соответствующей таблицы выделяется дополни-

тельная страница.

Удаление записей в линейных структурах может произво-

диться двумя способами. В первом способе при удалении запи-

си сразу же осуществляется автоматическое перезаписывание

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

2. СУБД

фактографических

ипформацнопных

систе м

ОПЕРАТИШЬЧЛ

]ЬУ.МЯТ1»<03У)

1>}||>0|>Ы

1-1

]>:|111111

Стр.1

Запись !

Запись2

Запиа З

Стр.2

Запись1

Запись2

ЗащсьЗ'

шг^

^^: .

Обмен

страницами

•4

Считывание

страниц

с нужными

записям

•

Вьггапкивание

и фикса191я

страниц

УСТРОЙСТВО

ДИСКОВОЙ

(ВНЕШНЕЙ) ПАМЯТИ

Фанл(ы)

данных н

1Шдексов

Данные

Стр.1

Запись !

Запись2

Стр.2

Запись !

Запись2

Индексы

Стр.1

Стр,2

Рис.

2.11.

Общий принцип организации

впутрсппей

схемы базы

данных

с целью уплотнения и ликвидации появляющихся пустых мест.

Подобный подход обеспечивает максимальную эффективность

использования

дискового пространства, но вызывает существен-

ные накладные расходы при любых операциях по удалению

записей. Поэтому другим, достаточно распространенным спо-

собом является простое «вычеркивание» удаляемой записи без

перезаписывания всех записей, лежащих за удаляемой, с соот-

ветствующим появлением пустых мест в страницах файла дан-

ных. Ведение базы данных в этом случае может быть организо-

вано так, чтобы при превышении общего объема пустых мест в

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

ЗО'М))

специальный компонент СУБД автоматически производил деф-

рагментацию страниц, устраняя пустые места по ранее удален-

ным записям. В некоторых СУБД запуск данной процедуры