Пример курсовой работы по исследованию систем управления: МЕТОДЫ ОРГАНИЗАЦИИ ДАННЫХ Вариант 27 пояснительная записка к курсовому проекту по дисциплине «Теория экономических информационных систем»

А.И.МИШЕНИН

экономических

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

систем

Издание четвертое, дополненное и переработанное

Рекомендовано Министерством образования Российской Федерации в качестве учебника

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

®

Москва «Финансы и статистика»

2002

ПРЕДИСЛОВИЕ

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

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

В дисциплине «Теория экономических информационных систем» (ТЭИС) основное внимание уделяется проблемам орга­ низации информации при решении задач на ЭВМ и техноло­ гии обработки информации.

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

Для единиц информации вводится ряд свойств, таких, как имя, значение, структура, операции над названными свой­ ствами, ограничения и методы представления значений. Деталь­ ное изучение этих свойств производится в главах 2, 3 и 4.

Моделирование внешних представлений экономической информации опирается на анализ экономических показателей. Моделирование представлений информации в ЭИС на концеп­ туальном уровне предполагает использование синтаксических

3

ОСНОВНЫЕ ПОНЯТИЯ ЭКОНОМИЧЕСКИХ ИНФОРМАЦИОННЫХ СИСТЕМ

1.1

ИНФОРМАЦИОННАЯ СИСТЕМА В ОБЩЕМ ВИДЕ

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

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

Понятие информации

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

5

широкое определение вносят элемент неясности. Поэтому вряд ли возможно сформулировать одно точное определение этого понятия.

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

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

Информация не отделима от процесса информирования, поэтому необходимо рассматривать источник информации и потребителей информации. Роль потребителей информации очерчивается в таком определении.

Информация — новые сведения, принятые, понятые и оценен­ ные конечным потребителем как полезные.

Информацией являются сведения, расширяющие запас зна­ ний конечного потребителя.

Выделяются три фазы существования информации.

1. Ассимилированная информация — представление сооб­ щений в сознании человека, наложенное на систему его поня­ тий и оценок.

2.Документированная информация — сведения, зафиксиро­ ванные в знаковой форме на каком-тофизическом носителе.

3.Передаваемая информация — сведения, рассматриваемые

вмомент передачи информации от источника к приемнику.

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

6

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

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

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

2. Семантический фильтр. Первый аспект семантического шума связан с отсутствием новизны в получаемом сообщении. Иначе говоря, сообщение не расширяет знаний потребителя. Второй аспект семантического шума связан с прохождением ложного сообщения через синтаксический фильтр. Допустим, что сообщение «Запас материала с кодом 141672 равен 956 тонн» дважды искажено так, что вместо цифры 7 воспринято 4 и вместо 9 воспринято 3. Первое искажение может быть за­ регистрировано синтаксическим фильтром, только если мате­ риал с кодом 141642 вообще не должен храниться на предпри­ ятии, а второе искажение синтаксический фильтр не заметит. Такие искажения должен обнаруживать семантический фильтр. Он проверяет соответствие контролируемого сообще­ ния с уже имеющейся информацией. Если на предприятии в нашем примере установлено, что запас любого материала дол­ жен превышать его месячную потребность, а для материала 141672 она составляет 720 тонн, то после исправления первой ошибки семантический фильтр обнаружит вторую ошибку. Существенные для семантического фильтра взаимосвязи ус­ танавливаются также предметными науками, например бух­ галтерским учетом, экономической статистикой и др.

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

7

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

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

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

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

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

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

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

8

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

ивыходные.

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

3.Функциональные признаки. Формируется классификация по функциональным подсистемам экономического объекта. Например, информация о трудовых ресурсах, производствен­ ных процессах, финансах и т. п., в другом разрезе — на данные планирования, нормирования, контроля, учета и отчетности.

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

Понятие системы

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

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

1. Структура — множество элементов системы и взаимосвя­ зей между ними. Математической моделью структуры является граф.

2. Входы и выходы — материальные потоки или потоки со­ общений, поступающие в систему или выводимые ею. Каждый входной поток характеризуется набором параметров {x(i)};

9

значения этих параметров по всем входным потокам образуют вектор-функциюX. В простейшем случае X зависит только от времени t, а в практически важных случаях значение X в мо­ мент времени t+1 зависит от X(t) и t. Функция выхода системы Y определяется аналогично.

3.Закон поведения системы — функция, связывающая из­ менения входа и выхода системы Y = F(X).

4.Цель и ограничения. Качество функционирования сис­ темы описывается рядом переменных ul, u2,.„, uN. Часть этих переменных (обычно всего одна переменная) должна поддер­ живаться в экстремальном значении, например, max ul. Фун­ кция ul = f(X,Y,t,…) называется целевой функцией, или целью. Зачастую fне имеет аналитического и вообще явного выраже­ ния. На остальные переменные могут быть наложены (в об­ щем случае двусторонние) ограничения

аК <= gK(uK) <= ЬК, где 2 <= К <= N.

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

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

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

10

зей непосредственно между всеми элементами системы. Вы­ деление подсистем проводит исследователь, и оно условно.

Свойство целостности указывает на согласованность цели функционирования всей системы с целями функционирования ее подсистем и элементов.

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

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

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

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

Автоматизация конторских работ предполагает наличие в ЭИС системы ведения картотек, системы обработки тексто­ вой информации, системы машинной графики, системы элек­ тронной почты и связи.

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

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

11

Для ЭИС соблюдаются следующие принципы их построе­ ния и функционирования.

1. Соответствие. ЭИС должна обеспечивать функциониро­ вание объекта с заданной эффективностью. Критерий эффектив­ ности должен быть количественным.

2.Экономичность. Затраты на обработку информации в ЭИС должны быть меньше экономического выигрыша на объекте при использовании этой информации.

3.Регламентность. Большая часть информации в ЭИС по­ ступает и обрабатывается по расписанию, со строгой перио­ дичностью.

4.Самоконтроль. Непрерывная работа ЭИС по обнаруже­ нию и исправлению ошибок в данных и процессах их обра­ ботки.

5.Интегральность. Однократный ввод информации в ЭИС

иее многократное, многоцелевое использование.

6.Адаптивность. Способность ЭИС изменять свою струк­ туру и закон поведения для достижения оптимального резуль­ тата при изменяющихся внешних условиях.

Среди других особенностей ЭИС следует назвать обра­ ботку больших объемов информации по сравнительно про­ стым алгоритмам, высокий удельный вес логической обра­

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

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

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

12

Величина, выбранная в качестве критерия, должна удов­ летворять ряду требований:

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

•давать наглядное представление об одной из целей сис­ темы,

•иметь сравнительно простой алгоритм расчета,

•допускать приближеннуюоценкупоэкспериментальным данным.

ЭИС обычно оценивается по комплексу критериев. Оцен­ ке подлежат:

•система в целом,

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

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

Как правило, функционирование ЭИС направлено на ус­ пешную реализацию нескольких целей.

Типичный перечень может включать следующие цели.

1. Повышение эффективности управления объектом (цели С1-СЗ):

С1 — максимальную полноту информации для обеспечения принимаемых решений;

С2 — представление информации с максимально возмож­ ной скоростью;

СЗ — максимальное удобство взаимодействия информаци­ онной системы с потребителями.

2. Эффективное использование ресурсов ЭИС (цели С4 — С6): С4сокращение расходов на создание, эксплуатацию и раз­

витие ЭИС;

CS — максимальное извлечение выходной информации из имеющегося объема данных;

С6 — сокращение избыточности в базе данных. Критериями для названных целей будут:

К1 — отношение объема информации в базе данных к объе­ му информации на объекте управления;

13

К2 — время обработки информации в ЭИС; КЗ — время, которое потребители расходуют на запрос не­

обходимой информации и ее использование в управлении; К4 — сумма капитальных вложений и текущих затрат на

создание, эксплуатацию и развитие ЭИС; К5 — отношение объемов входной и выходной информации;

Кб — доля избыточной информации в общем объеме данных. Одновременное достижение указанных целей практически неосуществимо. Например, повышение эффективности ЭИС по критериям К1 и КЗ вызывает увеличение К4 и достигнутое

состояние системы противоречит С4.

Классификация ЭИС

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

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

ЭИС, рассматриваемые в этой книге, следует отнести к адми­ нистративно-организационнымсистемам.

С функциональной точки зрения можно выделить такие клас­ сы ЭИС, как системы обработки данных (СОД), автоматизиро­ ванные системы управления (АСУ) и информационно-поисковыесистемы (ИПС). Структурные схемы названных систем показа­ ны на рис. 1.1 и рис. 1.2. Многие реальные ЭИС обладают черта­ ми нескольких из названных классов, а некакого-тоодного.

Основными функциями ЭИС являются сбор, передача, хра­ нение информации и такие операции обработки, как ввод, вы­ борка, корректировка и выдача информации. Для операций

14

Рис. 1.1. Структурные схемы системы обработки данных и автоматизированной системы управления

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

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

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

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

•входная информация, которая поступает от управляемо­ го объекта и из внешнего мира (от других предприятий и организаций),

15

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

•нормативно-справочнаяинформация,

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

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

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

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

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

16

Пользователи ^

Рис. 1.2. Схема функционирования информационно-поисковойсистемы

Под индексированием понимается процесс,, который состо­ ит из двух этапов:

•определения тем, которые отражаются в Дднном документе,

•выражения этих тем на языке, принятом, в информацион­ но-поисковойсистеме, и записи в виде поисковых обра­ зов, которые связываются с документов.

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

В ЭИС могут применяться два режима решения задач — пакетный и диалоговый.

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

17

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

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

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

По способу распределения вычислительных ресурсов вы­ деляются локальные и распределенные ЭИС. Локальная сис­ тема использует однуэлектронно-вычислительнуюмаши­ ну, а в распределенной системе организуется взаимодейст­ вие нескольких ЭВМ, соединенных между собой каналами связи.

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

18

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

Наиболее распространенными схемами связи в распреде­ ленных ЭИС являются системы с центральной ЭВМ и систе­ мы с кольцевой структурой связей ЭВМ.

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

1.2

КОМПОНЕНТЫ ЭКОНОМИЧЕСКИХ ИНФОРМАЦИОННЫХ СИСТЕМ

При решении любых задач с использованием ЭВМ требу­ ется наличие ряда компонентов:

•исходной и справочной информации для расчета,

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

•самой ЭВМ как исполнителя алгоритмов,

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

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

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

19

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

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

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

Пример сообщения На склад #2 1.02.98 поступили генераторы от завода «Дина­

мо» в количестве 50 шт. по цене 200 руб. ФОРМАТИРОВАННЫЙ ВАРИАНТ ЭТОГО СООБЩЕНИЯ:

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

Многие сообщения легко разделяются на компоненты и представляются в форматированном виде. Форматированные сообщения — это наиболее массовый вид сообщений, храни-

20

Т

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

База данных (БД) — это набор сообщений, которые

•являются истинными для соответствующей материаль­ ной системы,

•непротиворечивы по отношению друг к другу и к кон­ цептуальной схеме.

Сообщения в БД обычно являются форматированными и хранятся в виде единиц информации.

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

Если в сообщении «На склад № 2 01.02.98 поступили генера­ торы от завода «Динамо» в количестве 50 шт. по цене 200 руб.» названия параметров фиксированы, то набор символов «склад № 2, з-д«Динамо», генератор, 01.02.98, 200 руб., 50 шт.» является единицей информации. «01.02.98» также является единицей инфор­ мации.

Минимально необходимы две единицы информации — ат­ рибут и составная единица информации (СЕИ).

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

Любое сообщение записывается в форматированном виде как указание свойств (параметров) предметов, о которых мы

21

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

Составная единица информации представляет собой набор из атрибутов и, возможно, других СЕИ.

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

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

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

В рамках нашего примера можно говорить о двух едини­ цах информации — параметре (атрибуте) и таблице (СЕИ).

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

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

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

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

22

Оперативное запоминающее устройство (ОЗУ) использу­ ется для хранения программ и данных. Скорость чтения и за­ писи для ОЗУ, как правило, одинаковы, ОЗУ является наибо­ лее быстродействующим устройством ЭВМ.

Процессор выполняет команды, находящиеся в программе. Выполнение команды обычно предполагает обращение к ОЗУ.

ЭВМ может содержать любое число внешних устройств, чаще всего это внешние запоминающие устройства и устрой­ ства печати информации.

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

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

•совместное использование хранимыхданных всеми поль­ зователями ЭИС,

•стандартизацию представления данных, упрощающую проблемы эксплуатации БД и обмена данными между ЭИС,

•обеспечениепроцедурпроверкидостоверности информа­ ции и процедур ограничения доступа к данным,

•совмещение требований к использованию БД со сторо­ ны различных пользователей ЭИС.

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

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

Предметная область

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

23

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

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

Предметной областью называются элементы материальной системы, информация о которых хранится и обрабатывается вЭИС.

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

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

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

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

24

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

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

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

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

Свойством взаимодействия называется такое свойство, ко­ торое характеризует совместное поведение объектов, но не от­ носится ни к одному объекту в отдельности. Например, при производстве изделий взаимодействуют объекты Рабочий, Ма­ териал, Оборудование, Изделие. Количество изделий, произ­ веденных за определенный день, является свойством взаимо­ действия, но никак не характеризует указанные выше объекты, взятые в отдельности.

Проблема полноты отображения объектов и процессов пред­ метной области в хранимыеданные решается в ЭИС следующим образом. Предполагается, что представление объекта или про­ цесса сводится к указанию его свойств; информационным ото­ бражением свойств служат атрибуты и, следовательно, экземп­ ляр объекта или экземпляр процесса представлен в базе данных как набор пар <Имя атрибута>,<3начение атрибута>, где имена

25

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

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

В ряде случаев установление идентифицирующего свойства не является простой задачей.

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

Искусственный идентификатор, как правило, соответствует обычной нумерации экземпляров объектов, например Инвен­ тарный номер.

26

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

Детализация ЭИС

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

Классификация компонентов ЭИС приводится на рис. 1.3 и в табл. 1.1.

Предметная

область

Рис. 1.3. Компоненты экономической информационной системы

27

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

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

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

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

•управление сбытом и реализацией продукции,

•технико-экономическоепланирование,

28

•управление материально-техническимснабжением,

•бухгалтерский учет,

•оперативное управление производством,

•управление технической подготовкой производства. Пользователей экономической информационной системы

можно подразделить на пять типов:

•случайныепользователи, взаимодействие которых сЭИС не обусловлено их служебными обязанностями,

•параметрическиепользователи, которыеработаютсЭИС повседневно, в соответствии с четко определенной обла­ стью деятельности, по регламентированным процедурам,

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

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

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

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

Описание хранимой и обрабатываемой информации в ЭИС делается с разной степенью детализации. Используются три уровня представления (рис. 1.4):

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

29

П О Л Ь З О В А Т Е Л И

Концептуальное представление

Внутреннее представление

Рис. 1.4. Детализация представлений ЭИС

2.Концептуальный уровень — описание информационных потребностей на уровне понятий ЭИС.

3.Внутренний уровень — описание способа хранения ин­ формации в памяти ЭВМ и методов доступа к ней.

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

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

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

30

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

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

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

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

31

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

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

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

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

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

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

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

В ряде случаев применение СУБД не позволяет реализо­ вать все требования к ЭИС (например, высокое быстродей-

32

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

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

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

1.3

КЛАССИФИКАЦИЯ И ОСНОВНЫЕ СВОЙСТВА ЕДИНИЦ ИНФОРМАЦИИ

Существуют две основные единицы информации — атри­ бут и составная единица информации. Определение атрибута было дано в п. 1.2. Атрибут соответствует понятию перемен­ ной в языках программирования и понятию реквизита в бух­ галтерском учете.

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

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

образуют множество, называемое доменом этого атрибута. Формально атрибут с именем X представляет собой пару (X,z), где z — элемент Z. Множество Z называетсядоменом зна-

33

чений (областью определения атрибута X), величина z являет­ ся значением атрибута X в заданный момент времени.

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

type

day = 1.31;

month = (январь, февраль, март, апрель, май, июнь, июль, август, сентябрь, октябрь, ноябрь, декабрь);

year = 1900..1999;

{в описании типа атрибутов перечисляются допустимые значения атрибутов День, Месяц и Год соответственно}

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

Пример

Домен фамилий — FAM. Перечислить фамилии невозможно, поэтому ограничим FAM значениями текстового типа длиной до 20 символов. Для языка Паскаль получим:

var FAM: string[20];

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

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

34

Классификация и кодирование

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

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

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

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

В качестве примера рассмотрим различные системы коди­ рования значений атрибута Код студента. Порядковый код сту­ дента — это просто его номер в списке всех студентов. Предпо­ ложим, что необходимо различать студентов-дневников,вечерников и заочников с использованием серийной системы кодирования. Для этого последовательные номера от 1 до 5999 будем использовать при кодировании дневников, номера от 6000 до 7999 — при кодировании вечерников, от 8000 до 9999 — при кодировании заочников. Если в этих же условиях применить разрядный код, то первый знак кода будет принимать три зна­ чения (1 — дневное отделение, 2 — вечернее, 3 — заочное), а следу­ ющие 4 знака отводятся для нумерации студентов каждого от­ деления. В разрядном коде можно учесть больше признаков, например, первый знак — код отделения, второй — код факульте­ та, третий — код курса, четвертый — код группы, пятый и шестой — порядковый номер студента в группе. Обратите внимание, что, увеличивая число различимых признаков в коде, мы вынужде­ ны увеличивать и длину значения атрибута Код студента.

35

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

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

На домене FAM могут быть определены атрибуты с име­ нами: Студент, Преподаватель, Автор. Все это ролевые атри­ буты.

Атрибуты Фамилия рабочего и Табельный номер рабоче­ го неролевые, хотя описывают одних и тех же людей.

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

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

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

36

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

Свойства единиц информации представлены в табл. 1.2.

Множество атрибутов объединяется в одну СЕИ по следу­ ющим принципам:

•соответствующие атрибуты описывают один и тот же факт или экономический процесс,

37

•значения атрибутов, входящих в СЕИ, возникают одно­ временно, связаны логическими или арифметическими со­ отношениями.

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

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

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

Рассмотрим в качестве примера документа «Приходный ордер» с сокращенным составом атрибутов (рис.1.5). СЕИ приходного ор­ дера, названная Прих, содержит атрибуты Дата (дата поступления материалов), Пост (код поставщика материалов), Склад и таблицу, также включающую ряд атрибутов. Эта таблица является «другой» СЕИ в составе СЕИ Прих и названа Табл. Обратите внимание, что в экономических документах таблицы не имеют названий, названия всех элементов документа требуются при его машинной обработке.

В СЕИ Табл содержатся атрибуты Ннм (номенклатурный но­ мер материала), Кво-док(количество материала, принятое по то­варно-транспортнойнакладной),Кво-пр(количество материала, принятого на склад), Цена (цена материала), Сумма (результат перемножения значенийКво-при Цена). Размерность 3 у СЕИ

38

Табл соответствует трем строкам в таблице приходного ордера, а размерность 2 у СЕИ Прих определяется наличием двух докумен­ тов в нашем примере.

Окончательно структура СЕИ приходного ордера имеет вид: Прих(2).(Дата,Пост,Склад)Табл(3).(Ннм,Кво-док,Кво-пр,

Цена.Сумма))

Рис. 1.5. Бланки документа «Приходный ордер»

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

39

Значением СЕИ называется набор значений непосредствен­ но входящих в нее атрибутов и набор собраний непосредствен­ но входящих в нее СЕИ. Одно значение СЕИ приходного ор­ дера содержит по одному значению атрибутов Дата, Пост, Склад и собрание СЕИ Табл. Собрание Табл включает в себя три значения, в каждое значение Табл входит по одному зна­ чению атрибутов Ннм,Кво-док,Кво-пр,Цена и Сумма. Всего в нашем примере определены два значения СЕИ Прих.

Одно значение СЕИ при хранении ее в памяти ЭВМ часто называется записью.

Все языки программирования содержат средства описания структуры СЕИ.

Пример Рассмотрим аппарат описания языка Паскаль, в котором струк­

тура СЕИ соответствует понятию «тип записи».

Определение типа записи начинается зарезервированным сло­ вом record (запись), за ним следует список разделов записи. В кон­ це списка ставится зарезервированное слово end (конец). Каждый раздел записи определяет тип одного или более атрибутов. Так как компоненты записи могут быть любого типа, то допускаются кон­ струкции СЕИ с произвольной структурой:

Date = record Day:[1..31];

Month: (Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec); Year: 1900.. 1999;

end;

type rec = record

tn : 1..1000; {Табельный номер} fio : string[30]; {Фио рабочего} dr : Date; {Дата рождения}

nc : 1..9; {Номер цеха} end;

Var zap: rec;

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

40

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

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

Корректировка означает выполнение одной из операций:

•добавление нового значения СЕИ,

•исключение существующего значения СЕИ,

•замена некоторого значения СЕИ на новое значение. Декомпозиция — операция преобразования исходной СЕИ

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

Цены(Ннм,Цена) Приход(Дата,Пост,Склад,Ннм,Кво-док,Кво-пр,Сумма)

Декомпозиция, как и все операции над структурой СЕИ, одновременно производит преобразование множества значе­ ний, в частности нельзя однозначно определить размерность СЕИ Цены и Приход.

Композиция — операция преобразования нескольких СЕИ с различными структурами в одну СЕИ. Декомпозиция и ком­ позиция являются взаимообратными операциями, в частно­ сти, композиция Цены и Приход дает Прих.

Нормализация — это операция перехода от СЕИ с произ­ вольной структурой к СЕИ с двухуровневой структурой. Од­ новременно происходит перекомпоновка значений СЕИ.

Нормализация приходного ордера приводит к следующе­ му результату:

41

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

Рис. 1.6. Карточка складского учета

42

Экономические показатели

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

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

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

Атрибут-признак представляет собой информационное отображение качественного свойства некоторого объекта, предмета, процесса, аоснование является отображением их количественного свойства.

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

Как единица информации показатель является разновид­ ностью СЕИ. Схематично структура показателя П представ­ ляется выражением

n(Pl,P2,…)Pk,Q))

где Р1,Р2,…,Рк — атрибуты-признаки,Q -атрибут-основание.

43

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

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

Минимальный набор атрибутов показателя должен содер­ жать:

•атрибуты, отображающие идентификаторы объектов,

•атрибуты, отображающие признак времени,

•атрибут, отображающий некоторое количественное свойство объекта или взаимодействия.

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

2.Если значение текстовое — это признак.

3.Если атрибут обозначает предмет — это признак.

4.Если атрибут в некотором показателе является признаком (основанием), — он будет играть эту роль и в других показателях.

5.Если показатели описывают сходные процессы — их призначные части совпадают.

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

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

44

•сокращается объем памяти ЭВМ, требуемой для хране­ ния базы данных,

•сокращается трудоемкость ввода данных в ЭВМ и упро­ щаются проблемы контроля достоверности вводимой ин­ формации,

•упрощаются алгоритмы корректировки данных, так как

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

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

Пример АТРИБУТЫ ДОКУМЕНТА «ПРИХОДНЫЙ ОРДЕР».

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

У основания Кво-докнеобходимыми признаками будут Кмат (имеется в виду количество материала), Склад и Пост (склад при­ нимает материалы от конкретного поставщика) и Дата (необхо­ димо указание времени). В результате структура показателя (на­ зовем его Ш) принимает вид:

Ш ( Кмат, Склад, Пост, Дата, Кво-док)

45

При рассмотрении показателя П2 с основанием Кво-прможно использовать правило 5 (основанияКво-докиКво-прописывают сходные процессы), после чего

П2 ( Кмат, Склад, Пост, Дата, Кво-пр)

Для показателя ПЗ с основанием Цена необходимо устано­ вить, зависят ли цены материалов от предприятия-поставщикаили они постоянны. Если допустить последнее, то получаем

ПЗ (Кмат, Цена)

Сумма в показателе П4 является результатом вычисления: Сумма = Кво-пр* Цена,

поэтому согласно правилу 6 признаки показателя П4 получают­ ся в результате объединения признаков из показателей П2 и ПЗ, т.е.

П4 (Кмат, Склад, Пост, Дата, Сумма)

Указанные показатели образуют в базе данных 2 файла F1 с атрибутами Кмат, Цена

F2 с атрибутами Кмат, Склад, Пост, Дата, Кво-док,Кво-пр,| Сумма.

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

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

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

•перечень объектов, участвующих в процессе,

•название процесса,

•единицу измерения атрибута-основания,

•определение момента времени или периода времени,

•название функции управления,

•название экономической системы, в которой происходит описываемый процесс.

46

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

Показатель удобно применять как обобщающую единицу измерения объема данных.

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

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

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

Остальные показатели приходного ордера соответствуют таким переменным с индексами, как

K(i,j, m, п)дляП1 P(i,j, m, п)дляП2 S (i, j , m, n) для П4

где:

j — номер склада,

m — код поставщика, п — дата.

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

S(i,j,m,n) = P(i,j,m,n)*C(i).

47

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

1. Рассмотрим показатель с числовым значением х и мно­ жеством индексов X и показатель с числовым значением у и множеством индексов Y. Пусть @ обозначает одно из четы­ рех арифметических действий. Тогда множество индексов Z у величины z=x@y равно объединению множеств X и Y. Если множества X и Y содержат общие индексы, то необходимым условием корректности вычисления z является совпадение зна­ чений таких индексов у переменных х и у.

2. Для очень распространенных операций суммирования и умножения заимствуются правила линейной алгебры. В част­ ности:

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

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

Если индексы суммирования не указаны, то суммиро­ вание производится по всем индексам, которые под зна­ ком суммы встречаются два раза. Индексы, по которым ведется суммирование, называютсязаглушёнными, индек­ сы, по которым суммирование не ведется, называютсясво­ бодными.

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

48

Модель арифметических вычислений

Модель арифметических вычислений в ЭИС основывает­ ся на графе взаимосвязи показателей (или файлов). В графе G(S,U) множество вершин S = {s(i)} представляет собой все показатели (файлы), хранящиеся в базе данных. Дуга u(ij) от s(i) к s(j) существует в том случае, если существует расчетное соотношение для показателя s(j) и в правой части этого соот­ ношения присутствует показатель s(i).

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

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

•распределения файлов по узлам вычислительной сети. Соответствующие модели должны просчитываться зано­

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

Пример Рассмотрим модель вычислений для задачи формирования про­

граммы поставок готовой продукции.

Поток входной информации содержит следующие показатели: Пг(1j) — программа поставок i- изделияj-потребителюна внут­

ренний рынок в год,

n(ij,k) — аналогичная программа с разбивкой по кварталам (к = 1,2,3,4),

3r(ij) — программа поставок i- изделия j-потребителюна экс­ порт в год,

3(ij,k) — аналогичная программа с разбивкой по кварталам. Показатели Пг и П находятся в файле прикреплений на по­ ставку продукции П, показатели Эг и Э — в файле нарядов-зака­

зов Э. В файле цен находятся цены изделий 1Д0).

Выходные показатели:

Pr(i), P(i,k) — программы поставок i-изделияна год и на квар­ тал в натуральном выражении (файл Р).

Cr(i), C(i,k) — программы поставок i-изделияна год и на квар­ тал в стомостном выражении (файл С).

49

Основные расчетные соотношения имеют вид:

Pr(i)=mr(ij)+S3r(i,j),

p(i,k)=m(ij,k)+E3(ij,k), Cr(i)=U(i)Pr(i);C(i,k)=U(i)P(i,k).

Граф взаимосвязи файлов для указанной задачи приводит­ ся на рис. 1.7,а. В качестве новой задачи, которая расширяет состав графа, введем задачу оперативного контроля за фор­ мированием портфеля заказов с новыми файлами R (програм­ ма производства изделий на год и квартал) и Q (соответствие программы производства портфелю заказов). Расширенный граф взаимосвязи файлов показан на рис. 1.7,6.

Рис. 1.7. Граф взаимосвязи файлов для задачи формирования плана поставок готовой продукции:

а — исходный граф; б — расширенный граф

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

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

50

1.4

ЖИЗНЕННЫЙ ЦИКЛ ЭКОНОМИЧЕСКОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ

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

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

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

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

Под стадией модификации будем понимать процесс кор­ ректировки проектных решений по отдельным компонентам ЭИС.

Более детальное описание’ работ на стадии проектирова­ ния включает в себя следующие действия.

1. Обследование предметной области:

•границы предметной области и возможности ее расши­ рения,

•перечень объектов предметной области,

•информационные потребности пользователей,

51

•необходимые процессы обработки данных с указанием их периодичности,

•ЭВМ, на которой предполагается реализовать ЭИС,

•требования к функционированию ЭИС, частота поступ­ ления и корректировки информации, методы обеспече­ ния ее достоверности.

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

2. Определение объектов и их атрибутов. Для каждого объекта и процесса необходимо:

•выделить идентифицирующие свойства и провести нор­ мализацию,

•определить количество экземпляров каждого объекта и рост этой величины во времени,

•определить методы вычислений производных показате­ лей на основе значений исходных показателей.

3.Установление всех структурных связей между объекта­ ми и процессами и вычислимости на этой основе всех запро­ сов. Разработка структуры базы данных, проверка ее коррек­ тности и полноты.

4.Определение технологии работы ЭИС, т.е. определение порядка сбора, контроля и хранения данных, определение форматов ввода-выводаинформации, установление объемных

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

5.Выбор ЭВМ и программных средств для реализации ЭИС. Среди программных средств в первую очередь необхо­ димо выбрать операционную систему и СУБД. Оценка требу­ емых объемов памяти и трудоемкости разработки программ.

6.Проверка корректности проекта и определение сроков его реализации.

Итогом перечисленных выше действий становится техни­ ческий проект ЭИС.

7.На стадии рабочего проектирования необходимо:

•создать описания всех компонентов базы данных,

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

52

•разработать программы для всех приложений,

•заполнить ЭИС отладочными данными и оттестировать ее,

•составить инструкции по работе с ЭИС и обучить пользо­ вателей.

Стадия эксплуатации начинается с заполнения ЭИС реаль­ ными данными.

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

Рис. 1.8. Жизненный цикл ЭИС:

ТЗ — техническое задание; ТП — технический проект; РП — рабочий проект; Э — эксплуатация; М — модификация

На стадии эксплуатации ЭИС требуется обеспечить реор­ ганизацию БД, рестарт и восстановление, копирование БД, контроль непротиворечивости БД.

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

53

Важность исследования процессов модернизации ЭИС можно пояснить такими данными: стоимостные затраты на модернизацию ЭИС достигают примерно трети объема эк­ сплуатационных расходов, за год в ЭИС обычно меняется 10-40%первичных документов и20-50%выходных документов.

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

•изменения на объекте управления и во внешней среде (дрейф параметров предметной области),

•изменение состава рабочей нагрузки вычислительной си­ стемы, замена оборудования, рост объема файлов,

•накопление опыта работы с ЭИС,

•обнаружение проектных ошибок.

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

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

В процессе эксплуатации ЭИС производится слежение за изменением параметров ЭИС и предметной области. Для это­ го используются, например:

54

•информация об изменениях в системе документооборота

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

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

•характеристики потока запросов к БД,

•оценки пользователей о качестве получаемой информа­ ции,

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

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

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

55

Рис. 1.9. Взаимозависимость действий на стадиях эксплуатации и модификации ЭИС

Цели модификации ЭИС можно разделить на шесть боль­ ших групп:

•исправление проектных ошибок,

•улучшение эксплуатационных характеристик ЭИС,

•адаптация к изменениям в предметной области,

•разработка нового приложения,

•обеспечение совместимости с другими ИС,

•перенос БД в новую аппаратно-программнуюсреду. Конкретные методы модификации ЭИС группируются по

четырем направлениям (см. табл. 1.3):

•реструктуризация БД,

•перепрограммирование прикладных задач,

•реорганизация БД,

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

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

56

Таблица 1.3. Соответствие целей и методов модификации ЭИС

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

ВОПРОСЫ И ЗАДАНИЯ

1. Изобразите бланк документа, который соответствует описа­ нию записи zap на языке программирования Паскаль.

2.Представьте результат нормализации СЕИ со структурой С1(10).(С2(5).(Р1,Р2,РЗ),СЗ(7).(Р4,Р5,Р6))?

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

57

РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ

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

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

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

Классификация информационных конструкций (информа­ ционных объектов) тесно связана с областью их использова­ ния в ЭИС.

1. Объекты для технологии баз данных — отношения и ве­ ерные отношения.

59

2.Объекты для технологии искусственного интеллекта — предикаты, фреймы и семантические сети.

3.Объекты для технологии мультимедиа — тексты, графи­ ческие изображения, фонограммы и видеофрагменты.

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

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

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

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

•информационной конструкцией — отношением с двух­ уровневой структурой,

•допустимыми операциямипроекцией, выборкой, соеди­ нением и некоторыми другими,

•ограничениями-функциональнымизависимостямимеж-ду атрибутами отношения.

Каждому классу объектов Р материального мира ставится в соответствие некоторое множество атрибутов, например А1, А2,…,Ап. Отдельный объект класса Р описывается строкой величин (al, а2,…. an), где ai — значение атрибута Ai.

Строка (al, a2,…, an) называется кортежем. Всему классу объектов соответствует множество кортежей, называемоеот­ ношением. Обозначим отношение, описывающее класс объек­ тов Р, также через Р.

Выражение Р(А1, А2,…,Ап) называется схемой отношения Р.

60

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

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

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

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

•строке таблицы соответствует кортеж отношения,

•все строки таблицы (и соответственно все кортежи) раз­ личны,

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

ную сортировку строк).

Отношение реляционной БД может быть описано в терми­ нах теории множеств. Рассмотрим множество доменов

D={D1,D2,D3, …,Dk} и создадим декартово произведение доменов

U = D 1 D 2 D 3 . . . Dk.

Каждый элемент U имеет вид (dl, d2, d3,…,dk), где dl — эле­ мент домена Dl, d2 — элемент D2 и т.д. В множестве U пред­ ставлены всевозможные сочетания значений доменов, полу­ ченные по названному принципу. Среди элементов из U содержатся такие, которые не соответствуют реально имею­ щимся сообщениям и не могут храниться в БД. Отношение R, включающее истинные сообщения, является подмножеством U. Атрибуты отношения R используют домены из D в каче­ стве своих областей определения.

Реляционная база данных представляет собой множество отношений.

61

Схема реляционной БД содержит следующие компоненты

S(rel) = <A,R,Dom,Rel,V(s)>,

где А — множество имен атрибутов, R — множество имен отношений,

Dom — вхождение атрибутов в домены, Rel — вхождение атрибутов в отношения,

V(s) — множество ограничений (в том числе функциональных зависи­ мостей).

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

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

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

Приводимые далее операции над отношениями ориентиро­ ваны на процедурное описание процессов обработки данных.

Множество отношений и операций над ними образует ре­ ляционную алгебру.

При рассмотрении операций над отношениями будет ис­ пользоваться как алгебраическая форма записи операций, так и запись на языке реляционных СУБД семейства dBASE (для определенности — dBASE 3). Далее будут рассмотрены анало­ гичные конструкции языка SQL.

Как правило, список операций содержит проекцию, вы­ борку, объединение, пересечение, вычитание, соединение и деление.

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

62

Пример

Рассмотрим два отношения: W1, содержащее сведения о про­ даже продукции в 1998 г., и W2, в котором указаны цены на про­ дукцию и комплектующие изделия для соответствующих видов продукции.

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

XI = W1 [Магазин, Продукция, Факт] и имеет вид:

Х1

Магазин Продукция Факт

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

Х2 = W1 [Продукция, Магазин, Факт].

В СУБД DBASE проекция реализуется двумя командами и этот же пример выглядит как

use W1 && открыть отношение W1

copy to XI field Магазин, Продукция, Факт && проекция Знак && означает комментарий.

63

Следующий пример проекции — это получение справочника ХЗ цен на продукцию:

useW2

copy to ХЗfieldПродукция, Цена Значения отношения ХЗ показаны ниже:

ХЗ

Продукция Цена

Эдв-1240

Эдв-1240Эдв-3020Эдв-3020 ЗВИ 120

Значительным неудобством в ХЗ является наличие одинако­ вых строк. В реляционной алгебре требуется, чтобы результат про­ екции не содержал одинаковых строк, однако практически такие СУБД, как dBASE, не обеспечивают этого. Правильным результа­ том проекции Х4 = \У2[Продукция, Цена] является отношение

Х4

Продукция Цена

Эдв-1240 Эдв-3020 ЗВИ 120

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

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

64

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

1. Условие вида Имя_атрибута <знак сравнения> Значе­ ние, где допускаются знаки сравнения =, #, >, =>, <, <=. На­ пример, Цена > 100.

2. Условие вида Имя_атрибута_1 <знак сравнения> Имя_ _атрибута_2. Например, Факт > План.

Имена атрибутов должны содержаться в структуре исход­ ного отношения. Алгебраическая запись выборки имеет вид

T = R[p],

где R — исходное отношение;

Т — результирующее отношение;

р— условие выборки.

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

Х5’= Wl[npoflyKu™ = «Эдв-12»]

В СУБД dBASE выборка реализуется командой сору с опцией for, например,

useWl

copy to X6 for Факт — > Плац

65

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

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

Обозначим исходные отношения через R1 и R2, а резуль­ тирующее — Т.

Объединение Т = U(R1, R2) содержит строки, присутству­ ющие либо в отношении R1, либо в R2.

Пересечение Т = I(R1, R2) содержит строки, присутствую­ щие в отношениях R1 и R2 одновременно.

Вычитание Т = M(R 1, R2) содержит те строки из R1, кото­ рые отсутствуют в R2.

Если справочник цен на продукцию Х4 необходимо допол­ нить новыми сведениями из отношения W3, то надо выпол­ нить объединение

Х7 = U (X4, W3).

W3

В dBASE предусмотрена операция добавления append, ко­ торая для нашего примера реализуется командами

useX4

append from W3,

что приводит к добавлению в отношение Х4 всех строк из от­ ношения W3. Отличия добавления от объединения — создание

66

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

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

Имя_атрибута_1 <знак сравнения> Имя_атрибута_2,

где Имя_атрибута_1 находится в одном исходном отноше­ нии, а Имя_атрибута_2 — в другом. Будем использовать следу­ ющее обозначение операции соединения:

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

•знаком сравнения в условии соединения является «=»,

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

•список атрибутов результирующего отношения образу­ ется в результате объединения списков атрибутов исход­ ных отношений.

Обозначение натурального соединения не содержит усло­ вия соединения и имеет вид Т = Rl * R2.

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

67

Х8 = Wl[ Продукция = Продукция ]Х7

Первая строка из W1 и первая строка из Х7 удовлетворяют ус­ ловию Продукция = Продукция, поэтому сцепляются. Остальные строки из Х7 не будут сцепляться с первой строкой из W1 (условие не соблюдается). Вторая строка из W1 при сравнении со всеми стро­ ками из Х7 сцепится только с третьей строкой и т. д. Если приме­ нять операцию натурального соединения, то в отношении Х8 бу­ дет отсутствовать второй столбец с именем Продукция.

В СУБД DBASE для проведения соединения необходимо ис­ пользовать две области для исходных отношений:

SELECT 1

USE Wl && открытие отношения W1 SELECT 2

USE Х7 && открытие отношения Х7 SELECT 1

JOIN WITH Х7 ТО Х9 FOR Продукция=Х7->ПродукцияFIELDS Магазин, Продукция,Х7->Цена,План, Факт

Опция with называет второе исходное отношение, опция for со­ держит условие соединения, опция fields перечисляет имена атри­ бутов результирующего отношения. В приведенном примере вы­ полнено натуральное соединение и передвинут столбец Цена.

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

Х10 = Wl * W2

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

68

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

Натуральное соединение определено и в тех случаях, ког­ да соединяемые отношения совпадают по структуре или не содержат общих атрибутов. Если структура отношений R и S одинакова, то R * S выполняет фактически пересечение I(R,S).

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

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

Свойство коммутативности означает, что операции

X 1 = R * S H X 2 = S * R

порождают, в сущности, одно и то же отношение.

Свойство ассоциативности’озшчасг, что операция Y1=(R*S)*T и операция Y2=R*(S*T)

дают одинаковый результат. Различия, безусловно, состоят в неодинаковом порядке строк XI и Х2 (Y1 и Y2 соответствен­ но). Кроме того, промежуточные отношения при вычислении Y1 и Y2 могут иметь резко различающиеся размеры (число строк), хотя Y1 и Y2 содержат равное число строк.

69

нпФИО(«Си») = {«Иванов»,»Петров»,»Семин»}

im ФИО(«Фортран») = {«Иванов»,»Семин»,»Яшин»} 1тФИО(«Си»)п 1тФИО(«Фортран»)= {«Иванов»,»Семин»}

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

Условимся, что существует отношение-делимоеW(A,B) (в на­ шем примере это Y) иотношение-делительV(A). Для необходимо­ го нам запросаотношение-делительимеет вид:

Z

ЯП

Си

Фортран

Результатом операции деления является отношение Q(B), содержащее пересечение образов всех строкотношения-дели­теляV(A), вычисленных на основеотношения-делимогоW(A,B)>

Q = D (W,V),

где D — знак операции деления.

Результат деления Х12 = D (Y,Z) содержит следующие значе­ ния:

Х12

ФИО

Иванов

Семин

71

В СУБД семейства DBASE отсутствует операция деления отношений, и для реализации деления необходима специаль­ ная подпрограмма.

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

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

2.Логические связки «и», «или», «не» и знаки сравнения =,

#(не равно), >, <,.>=, <=.

3.Термы, т. е. любые константы и переменные, а также функции, аргументами которых служат термы.

4.Элементарные формулы — предикаты, аргументами ко­ торых являются термы. Предикаты, связанные операциями «и», «или», «не», также являются элементарными формулами. Элементарными формулами служат, например, выражения Фамилия = «Мишенин» и Сумма <= Итог.

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

Вприменяемых ниже языковых конструкциях использует­ ся синтаксис языков ALPHA и QUEL. Объявление перемен­ ной и ее привязка к определенному отношению производятся

спомощью оператора Диапазон (range) следующего вида

range of <переменная> is <отношение><квантор>

Квантор принимает одно из значений:

some, когда переменная обозначает одну из строк отноше­ ния (квантор существования);

all, когда переменная обозначает все строки отношения (квантор общности).

72

Основной формой оператора запроса Получить (get) явля­ ется выражение

get <отношение> (<целевой список>) where <условие>.

Условие соответствует формуле исчисления кортежей. В условиях можно использовать все знаки сравнения и логичес­ кие связки «и», «или», «не».

Языковая конструкция для кванторов может быть такой:

range of Z is Перевозка some.

Переменная Z при вычислении означает-однуиз строк (some — квантор существования) отношения Перевозка.

range of W is Перевозка all.

Переменная W означает все строки (all — квантор общнос­ ти) отношения Перевозка.

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

range of Z is Перевозка some

getW (Дата) where Поставщик.Код_поставщика=г.Код_поставщика and Поставщик.Город=»Киев».

Впоследнее время наиболее распространенным деклара­ тивным языком запросов является SQL (структурированный язык запросов). Центральным средством доступа к БД в SQL являются команда Select и ее параметры — From, Where, Group by, Having, Order by.

Вкоманде Select указываются имена выводимых атрибу­ тов или знак *, если надо выводить все атрибуты. Параметр From является обязательным и содержит имена требуемых для выполнения запроса отношений. Если здесь указано несколь­ ко отношений, то они будут преобразованы командами нату­ рального соединения в одно отношение. Параметр Where оп-

73

ределяет условия, которым должны удовлетворять выводимые данные. В записи условий применяются знаки сравнения (=,> и т.д.), опции All, Any, Between, Exists, Like, In и логические операторы. Параметр Group by объединяет записи с одинако­ вым значением некоторого атрибута-ключа.Параметр Having при необходимости проверяет условия внутри группы запи­ сей, выделенных с помощью Group by. Параметр Order by оп­ ределяет имена атрибутов, по которым должен быть отсорти­ рован результат.

Ранее упомянутый запрос «Получить даты поставок из го­ рода Киева» выполняется командой

Select Дата

From Перевозка, Поставщик

Where Поставщик.Город=»Киев»

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

Изделие (513,»Динамо»,800) Изделие (155,»Динамо»,600) Изделие (247,»АТЭ»,600)

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

Например, запрос «Получить список изделий с ценой 600» ре­ ализуется выражением goal (цель)

Goal: Изделие (х,_,600)

Ответ Пролога имеет вид х=155 х=247.

74

2.2

НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ

Центральная задача проектирования базы данных ЭИС — определение количества отношений (или иных составных еди­ ниц информации) и их атрибутного состава.

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

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

•корректировка отношений не должна приводить к дву­ смысленности или потере информации,

•перестройка набора отношений при добавлении в базу данных новых атрибутов должна быть минимальной.

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

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

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

75

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

Преобразование ненормализованного отношения в пред­ ставление, соответствующее 1НФ, — это операция нормализа­ ции, рассмотренная выше. Следует отметить определенное терминологическое несоответствие — нормализация СЕИ при­ водит к 1НФ, а нормализация отношений реляционной БД обычно производится до ЗНФ или 4НФ.

Реляционная база данных в целом характеризуется 1НФ, если все ее отношения соответствуют 1НФ.

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

2.2.1 Функциональные зависимости и ключи

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

Простейший случай функциональной зависимости охваты­ вает 2 атрибута. В отношении R(A,B,…)атрибут Афункцио­ нально определяет атрибут В,если в любой момент времени каждому значению Асоответствует единственное значение В

(обозначается А -»В).

Иначе говорят, что В функционально зависит от А (обо­ значается В = f(A)). Первое обозначение оказывается более удобным, когда число функциональных зависимостей растет и их взаимосвязи становятся труднообозримыми; оно и будет использоваться в дальнейшем. Отсутствие функциональной зависимости обозначается А —/—> В.

76

Можно определить ситуацию А ->В с помощью операции «образ», сказав что множество im B(a) должно содержать один элемент для любого значения а атрибута А.

Рассмотрим простой пример с атрибутами ФИО и ГР (год рож­ дения) в отношении R1.

Предположим, что в столбце ФИО представлены сведения о разных людях и соответствующие значения в столбце не повторя­ ются. Тогда можно утверждать наличие функциональной зависи­ мости ФИО -»ГР, поскольку каждому значению атрибута ФИО в отношении RI соответствует единственное значение атрибута ГР. Можно утверждать, что это ограничение будет соблюдаться и да­ лее, так как оно перефразируется в утверждение:у каждого чело­ века единственный sod рождения, которое справедливо.

Практически каждое ограничение для проверки функциональ­ ной зависимости можно преобразовать в утверждение о свойствах объектов предметной области, которое можно проверить, не ана­ лизируя множество значений соответствующего отношения. Имен­ но так мы и будем поступать в дальнейшем. Наличие в столбце ГР повторяющихся годов (1960) не опровергает установленной нами зависимости, но это означает ГР —/-»ФИО.

Одновременное соблюдение двух зависимостей вида А -»В и В—* А называетсявзаимно-однозначным соответствием и обозна­ чается А<-»В.

В качестве примера рассмотрим отношение R2 с атрибутами Магазин и Расч (номер расчетного счета).

R2

Магазин Расч

ММЗ 704098 Динамо 122095 АТЭ 440162

77

Можно утверждать, что у каждого магазина единственный но­ мер расчетного счета и каждый расчетный счет принадлежит един­ ственному магазину. Это доказываетсправедливость функциональ­ ных зависимостей Магазин -»Расчи Расч-»Магазин, т.е. Мага­ зин<-»Расч.

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

R3

ФИО Дисциплина

Петров Физика Федин Химия Алешин Физика Петров Химия

Таким образом, для атрибутов А и В некоторого отноше­ ния возможны следующие ситуации:

•от(угствиефункциональнойзависимости,

•наличие А —> В (или В-»А),но не обе зависимости вместе,

•наличиевзаимно-однозначногосоответствияА<->В.

Понятие функциональной зависимости распространяется на ситуацию с тремя и более атрибутами в следующей форме. Группа атрибутов (для определенности А,В,С) функциональ­ но определяет атрибут D в отношении T(A,B,C,D,….), если каждому сочетанию значений <а,Ь,с> соответствует единствен­ ное значение d (а — значение A, b — значение В, с — значение С, d — значение D). Наличие такой функциональной зависимос­ ти будем обозначать А,В,С -»D. Случай, когда в правой час­ ти функциональной зависимости присутствует несколько атрибутов, не нуждается в специальном рассмотрении. Взаим­но-однозначныесоответствия для трех и более атрибутов так­ же не имеют самостоятельного значения.

78

Пусть в отношении Т1 представлены сведения о закончивших­ ся экзаменах.

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

ФИО, Дата -»Дисциплина, ФИО, Дата-»Преподаватель, ФИО, Дата->ОЦЕНКА.

Существование функциональных зависимостей связано с применяемыми способами кодирования атрибутов. Так, для множества учреждений можно утверждать, что каждый отдел (как объект предметной области) относится к единственному учреждению. Однако этого недостаточно для доказательства функциональной зависимости Отдел -»Учреждение. Если в каждом учреждении отделы нумеруются последовательно, начиная с 1, то функциональная зависимость неверна. Если же код отдела, кроме номера, содержит и код учреждения (или уникальность кодов обеспечиваетсякаким-тодругим спосо­ бом), то функциональная зависимость Отдел-^Учреждениесправедлива. Зависимость ФИО->ГР в R1 соблюдается, если ФИО является атрибутомидентификатором для каждого че­ ловека, что может быть справедливо только для небольших множеств людей. Невнимание к способам кодирования атри­ бутов может привести к несоответствию функциональных за­ висимостей и хранящихся данных, что является серьезной про­ ектной ошибкой.

79

Для показателя со множеством атрибутов-признаковР= {Р1,Р2,…,Рп} иатрибутом-основаниемQ справедлива фун­ кциональная зависимость Р-»Q, хотя нельзя утверждать, что это единственная зависимость на указанных атрибутах.

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

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

Рассмотрим в качестве примера отношение ТЗ (имена и значе­ ния атрибутов — условные):

тз

Можно утверждать, что вероятным ключом отношения ТЗ яв­ ляется атрибут ZEN (значения в столбце ZEN не повторяются). I Кроме того, еще один вероятный ключ представлен парой атрибу­ тов RAM, AST.

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

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

80

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

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

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

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

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

Каждое значение первичного ключа встречается только в однойстроке отношения. Значениелюбого атрибута в этой строке также единственное. Если через К обозначить атрибуты первич­ ного ключа в отношении R(A,B,C,… J), то справедливы следую­ щие функциональные зависимости К-»А, К-»В, К-*С,…,

К -» J. Набор атрибутов первичного ключа функционально опре­ деляет любой атрибут отношения.Обратное также верно: если найдена группа атрибутов, которая функционально определяет все атрибуты отношения по отдельности, и эту группу нельзя сократить, то найден первичный ключ отношения.

81

Вернемся к отношению Т1 с функциональными зависимостями: ФИО, Дата -»Дисциплина, ФИО, Дата-»Преподаватель, ФИО, Дата-»Оценка.

Нетрудно установить, что ФИО, Дата -»ФИО, ФИО, Дата-»Дата

(в каждом сочетании значений ФИО, Дата значение ФИО встре­ чается один раз). Следовательно, первичный ключ в отношении Т1 составляют атрибуты ФИО, Дата и при поиске ключа не потре­ бовались конкретные значения Т1.

Знание ключа отношения позволяет устанавливать ряд функ­ циональных зависимостей, например, в ТЗ ZEN -»BIG, RAM, AST-»BIG.

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

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

Теорема 1

А,В ->А и А,В->В.

Доказательство основано на том, что в строке <а,Ь> для атрибутов А и В значение а (как и значение Ь) присутствует один раз.

Теорема 2

А -»В и А-»С тогда и только тогда, когда А-»ВС. Рассмотрим произвольное значение а атрибута А. Если

А — » В и А — » С , Toim В(а) и im С(а) содержат по одному эле­ менту. Предположим, что зависимость А -»ВС неверна и im ВС(а) состоит из 2 или более элементов. Тогда либо im B(a), либо im C(a) должны содержать более одного элемента. Полу­ ченное противоречие доказывает зависимость А->ВС.

82

Обратно, если А -»ВС, то im BC(a) содержит один элемент вида <Ь,с> для любого а. Зафиксируем некоторое значение al. Значение b (как и значение с) встречается в сочетании с al толь­ ко один раз, следовательно, справедливо А—•В и А->С.

Теорема 3

Если А ->В и В-»С,то А-»С.

Предположим, что зависимость А ->С неверна и множе­ ство im C(a) содержит более одного элемента. Каждому значе­ нию а соответствует единственное значение b (в силу А-»В), поэтому im C(b) содержит более одного элемента. Получилось противоречие с условием В-*С, что и доказывает теорему.

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

Теорема 4

Если А -»В, то АС-»В (С произвольно).

Доказательство

АС -»А (теорема 1), А-»В (условие), следовательно, АС-»В по теореме 3.

Теорема 5

Если А -»В, то АС->ВС (С произвольно).

Доказательство

АС ->В (теорема 4), АС-*С (теорема 1), следовательно,АС-»ВС по теореме 2.

Теорема б

Если А ->В и ВС->D, то АС-»D.

Доказательство

Из А ->В следует АС->ВС (теорема 5). ВС-»D (условие), поэтому АС-»Dпо теореме 3.

Количество теорем, которые можно доказать в таком стиле, достаточно велико, но мы ограничимся указанными шестью.

Каждой функциональной зависимости вида А -»В можно поставить в соответствие булевскую функцию вида АВ’ (знак логического умножения пропущен, через ‘ обозначено логи-

83

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

Введем сокращенные обозначения: А — ФИО, В — Дата, С — Дисциплина, D — Преподаватель, Е — Оценка.

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

ФИО, Дата -»Дисциплина,ФИО, Дата—»Преподаватель, ФИО, Дата->Оценка

булевская функция будет выглядеть как ABC +ABD’ +АВЕ’

(знаком + обозначено логическое сложение).

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

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

Можно рекомендовать следующие теоремы:

•если А -»ВС, то А-»Ви А-»С,

•если А -»В, то AD-»В,

•если А -»В и В-»С, то А-»С.

84

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

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

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

2.2.2

Вторая и третья нормальные формы отношений

Отношение имеет вторую нормальную форму (2НФ), если оно соответствует1НФ и не содержит неполных функцио­ нальных зависимостей.

Неполная функциональная зависимость — это две зависимости:

•вероятный ключ отношения функционально определяет некоторый неключевой атрибут,

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

Отношение, не соответствующее 2НФ, характеризуется избыточностью хранимых данных.

85

Ключом в Т41 служат атрибуты Магазин, Изделие, в Т42 — Изделие, и легко определить, что оба отношения соответству­ ют требованиям 2НФ.

База данных находится в 2НФ, если все ее отношения на­

Транзитивная ФЗ — это две ФЗ:

•вероятный ключ отношения функционально определяет не­ ключевой атрибут,

•этот атрибут функционально определяет другой неключе­ вой атрибут.

Если К — ключ отношения, А, В — не ключевые атрибуты и К ч А, А -»В — справедливые ФЗ, то они являются транзитивными. Частный случай транзитивной ФЗ — неполная ФЗ, когда К = С,Е и К-»Е, Е-*А.

Рассмотрим пример.

Т5

Функциональные зависимости:

(6)ФИО -> Группа,

(7)Группа -»Факультет,

(8)ФИО -»Факультет.

Ключ отношения Т5 — ФИО. Зависимости (6) и (7) вместе об­ разуют транзитивную ФЗ, поэтому Т5 находится в 2НФ, но не в ЗНФ.

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

87

Переход от Т5 к отношениям в ЗНФ дает следующие результаты: Т51=Т5[ФИО,Группа],

Т52=Т5[Группа,Факультет].

Т51

Отношения Т51, Т52 получились двухатрибутными, поэтому нарушение требований ЗНФ в них невозможно.

База данных находится в ЗНФ, если все ее отношения на­ ходятся в ЗНФ.

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

Исходными данными для алгоритма служит некоторый список атрибутов, охватывающий одно отношение, базу дан­ ных или ее часть. В любом случае предполагается (хотя бы теоретически) существование одного отношения с заданным списком атрибутов. В противном случае нельзя применять некоторые теоремы о ФЗ и нельзя гарантировать, что одна и та же ФЗ, например А -»В, справедливая в двух различных отношениях R и S, соответствует равным отношениям R[A,B] и S[A,B].

Алгоритм получения отношений в ЗНФ обладает следую­ щими свойствами:

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

ив одном из производных отношений. Это гарантирует получение осмысленных отношений с легко интерпрети­ руемой структурой,

88

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

•результат декомпозиции в ЗНФ обычно содержит мень­ ше значений атрибутов, чем исходное отношение R (про­ исходит уменьшение избыточности).

Алгоритм нормализации (к ЗНФ)

1. Получить исходное множество функциональных зави­ симостей для атрибутов рассматриваемой БД.

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

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

•по три атрибута, где первые два могут функционально определять третий,

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

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

2. Получить минимальное покрытие множества функцио­ нальных зависимостей. В минимальном покрытии должны от­ сутствовать зависимости, которые являются следствием остав­ шихся зависимостей по теоремам 1 — 6. В частности, требуется объединить функциональные зависимости с одинаковой левой частью в одну зависимость. Обозначим полученное минималь­ ное покрытие функциональных зависимостей через

F={fl,…,fi,…,fk}.

89

3.Определить первичный ключ отношения.

4.Для каждой функциональной зависимостиfiсоздать про­ екцию исходного отношения Ri = R[Xi], где Xi — объединение атрибутов из левой и правой частей fi.

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

Для практического применения алгоритма нормализации до ЗНФ существенны два вопроса:

•как учесть наличие взаимно-однозначныхсоответствий,

•как сократить объем перебора вариантов при первона­ чальном определении множества функциональных зави­ симостей.

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

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

Если А ->ВиD—/-»С, тоABD—/-»С

и правило, согласно которому функциональные зависимости

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

Пример Рассмотрим отношение со сведениями о научно-исследователь­

ских работах. Список атрибутов: НИИ, Директор, Адрес, Отдел, Ксотр, Тема, Датанач, Датакон, Приор, Заказ, Обфин, Работа, Прод ФИО.

На шаге 1 будет выделен блок взаимно-однозначныхсоответ­ ствий на атрибутах: НИИ, Директор, Адрес. Далее атрибутомпредставителем будем считать НИИ. Список функциональных за­ висимостей приводится ниже.

90

Список функциональных зависимостей Отдел ->НИИ, Отдел-»Директор, Отдел-»Ксотр,Тема-»Датанач, Тема-»Датакон,Тема-»Приор, ФИО->НИИ, ФИО-»Директор,ФИО-»Отдел,

Тема, Заказ -»Обфин, Тема, Работа, ФИО-»Прод.

Структура реляционной базы данных R1(НИИДиректорАдрес), К2(НИИ,Отдел,Ксотр), КЗ(Тема,Датанач,Датакон,Приор), Я4(ФИО,Отдел), К5(Тема,Заказ,Обфин), К6(Тема,Работа,ФИО,Прод), К7(Тёма,Заказ,Работа,ФИО).

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

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

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

91

2.2.3 Ациклические базы данных

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

В отношении R(A,B,C) существует многозначная зависи­ мость (МЗ) А —>—> В, если для любого а, являющегося значе­ нием атрибута А

im(BC)a = ira(B)a ° im(C)a,

где ° — знак декартова произведения множеств.

Положение атрибутов В и С равноценно, поэтому одно­ временно справедливо А -»-»С, т.е. многозначные зависимо­ сти всегда встречаются парами.

Отношение R(A,B,C) с многозначной зависимостью А -»-»В содержит избыточную информацию, хотя и несколько дру­ гого рода, чем отношение в 1НФ. Оказывается, что отноше­ ния R1 =R[A,B] и R2=R[A,C] вместе представляют всю инфор­ мацию из R, хотя и имеют обычно меньший объем. Справедливо соотношение R=R1 *R2, которое можно считать равноценным определению многозначной зависимости.

Прямер

Рассмотрим отношение Z(3aBQa, Изделие, Компл, План), где Компл — название комплектующего изделия для данного Изделия, а План — план выпуска Изделий. Справедлива функциональная за­ висимость Завод, Изделие -*План, и мы имеем следующие отно­ шения в ЗНФ:

Z1(Завод, Изделие, План), г2(Завод, Изделие, Компл).

Отношение Z1 содержит двухатрибутный ключ, и в нем не может быть многозначной зависимости. В Z2 существует МЗ вида Изделие -»-»Завод (и, следовательно, Изделие-*-»Компл),

92

поскольку каждое изделие комплектуется одним и тем же набо­ ром комплектующих изделий, на каком бы заводе оно ни произ­ водилось. Поэтому Z2 необходимо разделить на два отношения Z21 (Завод, Изделие) и г22(Изделие, Компл). Вся информация из Z21 содержится в Z1, поэтому окончательный список отношений состоит из Z1 и Z22.

Операция соединения позволяет получить Z=Z1*Z22.

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

Для определения понятия ациклической схемы БД введем граф соединений на множестве отношений {Sl,S2,…,Sk}. Вер­ шинами графа соединений являются имена существующих отношений SI, S2,…,Sk. Дуга графа <Si,Sj> существует, если в структуре отношений Si и Sj имеются общие атрибуты. Обо­ значим их для определенности через A(ij) и назовем весом дуги. Путь на графе соединений называетсяА-путем,если атрибут А содержится в структуре каждого отношения, лежа­ щего на пути. В графе соединений требуется, чтобы для каж­ дой пары отношений Si, Sj с общим атрибутом A(ij) существо­ валА(У)-путьмежду Si и Sj.

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

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

93

S1(A,B)-^-S2(A,C)—*-S3(A,D,E)

R5

R1 R2 R4 R7 R6

Рис. 2.1. Пример графа соединений: а, б — ациклический; в — циклический

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

Алгоритм проверки структуры БД на ацикличность

Исходные данные — список отношений с указанием атри­ бутного состава каждого отношения.

Метод

Шаг I. Если некоторый атрибут встречается только в одном отношении, вычеркнуть данный атрибут из этого отношения.

94

Шаг 2. Если все атрибуты некоторого отношения находят­ ся среди атрибутов другого отношения, то первое отношение вычеркивается из списка.

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

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

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

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

КЛ(НИИ#, Директор, Адрес), R2(HHM, Отдел#, Ксотр),

R3(TeMa#, Датанач, Датакон, Приор), R4(OHO#, Отдел),

R5(TeMa#, Заказ#, Обфин), Я6(Тема#, Работа#, ФИО#, Прод), R7(TeMa#, Заказ#, Работа#, ФИО#).

В схемах отношений атрибуты ключа отмечены знаком #. Отношения R1 и R2 имеют одноатрибутный ключ, ключи остальных отношений являются частью ключа БД из R7, сле­ довательно, эта БД ациклическая. Дерево соединений приво­ дится на рис. 2.1,6.

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

95

Рассмотрим простой пример графа соединений на рис.2.1.в. Существование цикла очевидно. Отношение Т(Служащий, От­

дел, Заказчик) может быть вычислено либо как T=R1*R2, либо в виде:

Т=(К.1*113)[Служащий, Отдел, Заказчик].

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

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

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

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

Приведем типичные варианты разделения и переименова­ ния атрибутов.

1. При структуре функциональных зависимостей вида А —»В—>С, А-»Е—»Снеобходимо установить две различные роли для атрибута С (например, С1 и С2).

Рассмотрим БД с атрибутами Студент, Группа, Куратор, Ка­ федра и зависимостями Студент -»Группа-»Кафедра, Студент->Куратор-•Кафедра. В первом случае подразумевается скорее все­ го выпускающая кафедра для группы студентов, а во втором — ка­ федра, на которой работает куратор. После разделения атрибута Кафедра получаем структуру БД в виде:

Р1 (Студент, Группа), Р2(Группа, Выпускающая_кафедра), РЗ(Студент, Куратор), Р4(Куратор, Кафедра_куратора).

96

2. Каждое применение теоремы псевдотранзитивности Т6 свидетельствует о цикличности БД.

Рассмотрим, например, зависимости Служащий -»Отдел и От­ дел, Заказчик-»Тема. Это ситуация, показанная на рис.2.1,в. Для преодоления цикличности необходимо разделить роли атрибута Отдел, например, ввести атрибут Отдел_служащего.

3. Структура функциональных зависимостей вида АВ -»С, С->В часто получается, если действия, совершаемые объек­ том, приписываются классу объектов. Необходимо в таком случае добавить в структуру БД атрибут, обозначающий этот объект.

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

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

Учитывая безусловно высокую трудоемкость приведения отношений к ЗНФ при достаточно большом числе атрибутов (в качестве границы можно назвать 12-14атрибутов), можно рекомендовать следующие действия при проектировании структуры реляционной БД:

•каждый входной документ привести к ЗНФ и установить первичный ключ в каждом случае,

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

97

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

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

2.2.4 Доступ к реляционной базе данных

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

Вкачестве типичных операций рассмотрим здесь выборку

икорректировку информации.

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

Для моделирования процесса выборки данных из БД тре­ буется провести классификацию возможных запросов. Обо­ значим через А — имя неключевого атрибута, v — одно из его значений, е — соответствующее значение первичного ключа и @ — один из знаков сравнения =,#,<,>,<=,>=. Когда величи­ ны е или v должны быть найдены, они обозначаются знаком «?». Мы приходим к трем классам запросов:

1. А(е) = ? — найти значение атрибута по известному значе­ нию ключа;

2. А(?) @ v — найти записи с заданным значением неключе­ вого атрибута.

98

3. А(?) = ? — перечислить значения данного атрибута для каждой записи.

Условия запросов второго типа могут комбинироваться с помощью логических связок «не», «и», «или».

Введем понятия оболочки и входа запроса. Оболочкой запроса называется множество имен атрибутов, упоминае­ мых в формулировке запроса.Входом запроса называется множество имен атрибутов, для которых заданы условия вида А(?) @ v.

Рассмотрим пример запроса: какие предприятия, расположен­ ные в Киеве, поставляют свою продукцию на завод ММЗ по же­ лезной дороге.

Оболочку запроса составляют атрибуты Предприятие (постав­ щик), Город (поставщика), Продукция, Завод (потребитель), Вид „транспорта. Входом запроса являются атрибуты Город, Завод, Вид „транспорта. Допустим, что запрос реализуется на отношении

Я(Предприятие, Город, Продукция, Завод, Вид_транспорта)

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

Формально будем записывать запрос в виде: Выбрать Q, где Т @ t.

Через Т обозначены имена атрибутов входа запроса, t — их значения, Q — множество атрибутов на выходе запроса (часть оболочки).

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

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

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

99

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

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

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

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

Рассмотрим свойства соединений в базе данных с ЗНФ и в ациклической БД.

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

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

Для двух произвольных отношений R1,R2 рассмотрим X- значения из R1 и Х-значенияиз R2, обозначив их R1 .X и R2.X соответственно.

100

Введем 4 ролевые зависимости:

1. Равенство. Множество Х-значенийиз R1 и множествоХ-значенийиз R2 совпадают в каждый момент времени.

2.Включение. Все значения R1.X содержатся в множестве значений R2.X.

3.Частичное включение. Множества значений R1 .X и R2.X содержат общие элементы.

4.Непересечение. Множества R1.X и R2.X не содержат общих элементов.

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

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

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

•объединение операций выборки по нескольким услови­ ям в одну операцию выборки с составным условием,

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

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

Пример Рассмотрим систему отношений:

Деталь (Код_детали, Название, Вес), Поставщик (Код_поставщика, Вид_транспорта, Город),

101

4. Получить коды всех поставщиков, поставляющих детали с кодом «1425» или «7252».

Необходимые атрибуты Код_поставщика и Код_детали нахо­ дятся в отношении Перевозка:

use Перевозка

copy to R3 for Код_детали=»1425″.ог.Код_цетали=»7252″; field Код_поставщика

Если список деталей достаточно длинный, то целесообразно хранить его в некотором отношении, например, Zl(Ko,n_jieTajiH) и применять команды:

select 1

use Перевозка select 2

useZl

join with Перевозка to R4;

for Кодлетали = Перевозка->Код_деталиfieldКод_поставшика

5. Получить коды всех поставщиков, поставляющих детали с кодом «1425» и «7252» одновременно.

Примечательно, что команды:

use Перевозка

copy to R5 for Ko;ueTMH=»1425″.and.KoAJieTanH=»7252″; field Код_поставщика

не формируют ответ на запрос (R5 будет пустым отношением). Можно рекомендовать, например, такие команды:

select 1

use Перевозка

copy to Wl for Код_детали=»1425″ field Код_поставщика copy to W2 for Код_летали=»7252″ field Код_поставщика useWl

select 2 useW2

join with Wl to R5 for Код_поставщика = Wl->Kofl_nocTaBuanca

103

field Код_поставщика, Когщетали, Название use Поставщик

select l useR4

join with Поставщик to RIO for Код_поставщика = Поставщик ->Код_поставщика;

field Код_детали, Название, Город

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

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

use Y

copy to Y3 for ЯП # «Фортран»

приводят к отношению Y3, показанному выше,

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

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

105

Известен общий метод вывода функциональных зависи­ мостей в отношении, полученном в результате соединения или выборки. Атрибуты исходных отношений последовательно нумеруются и функциональные зависимости, справедливые для них, переписываются с использованием числовых обозна­ чений атрибутов. К этим зависимостям добавляется «число­ вой» эквивалент зависимости X <-»X (для операции соедине­ ния) или зависимость 0—»В,когда производится выборка по равенству значений атрибута В. В итоге мы получаем все фун­ кциональные зависимости, справедливые в результирующем отношении.

Пример

Обозначим в R1: первичный ключ X через 1, неключевые ат­ рибуты — через 2, в R2: X через 3, первичный ключ как 3,4, неклю­ чевые атрибуты — 5. Для Rl *R2 будут справедливы функциональ­ ные зависимости

1-»2;3,4-»5;3-»1;1-»3,

откуда следует 3,4 -»2. Таким образом, атрибуты 3,4 являются первичным ключом в R1 *R2.

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

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

106

2.3 СЕТЕВАЯ И ИЕРАРХИЧЕСКАЯ МОДЕЛИ ДАННЫХ

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

Сетевая БД представляется как множество отношений и ве­ ерных отношений. Отношения разделяются на основные и за­ висимые.

Веерным отношением W(R,S) называется пара отношений, состоящая из одного основногоR, одного зависимого отноше­ нияS и связи между ними при условии, что каждое значение зависимого отношения связано с единственным значением ос­ новного отношения.

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

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

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

Ограничение двухуровневых сетей состоит в том, что каж­ дое отношение может существовать в одной из перечисленных ниже ролей:

•вне каких-либовеерных отношений,

•в качестве основного отношения в любом количестве ве­ ерных отношений,

•в качестве зависимого отношения в любом количестве ве­ ерных отношений.

107

Запрещается существование отношения в качестве основ­ ного в одном контексте и одновременно в качестве зависимо­ го в другом контексте.

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

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

Для двухуровневых сетевых СУБД вводятся еще два огра­ ничения (с теоретической точки зрения необязательные):

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

•веерное отношение существует, если первичный ключ ос­ новного отношения является частью первичного ключа зависимого отношения.

Организация веерного отношения в памяти ЭВМ

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

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

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

108

Значения основного отношения Изделие

б

Рис. 2.2. Структуры и значения веерных отношений

109

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

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

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

S(net) = <A,R,WW,Dora,Rel,Net,V(s)>,

где WW — множество веерных отношений,

Net — вхождение отношений в веерные отношения.

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

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

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

Способ исключения может быть обязательный и необяза­ тельный. Способ обязательный означает, что после того, как значение включено в основное отношение, оно становится его

ПО

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

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

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

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

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

где Xi — атрибуты ключа в файле Fi.

Дополнительно вводится граф сетевой структуры В с вер­ шинами {XI ,X2,…,Xi,…,Xn}. Дуга <Xi,Xj> в графе В существу­ ет, если Xi является частью Xj и Fj[Xi] является подмножеством Fi. Последнее условие имеет тот же смысл, что и синтаксичес­ кое включение отношений в реляционной модели данных. Здесь предполагается, что ключ основного файла содержится в зависимом файле. Граф В аналогичен графу соединений для реляционной БД.

Введем определениесетевой ациклической базыданных DBA.

База данных DBA называется ациклической, если между любыми

111

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

Для множества файлов F ациклической базы данных DBA вполне применима операция

m(DBA) = F1 & F2 & … & Fi & …& Fn,

называемая максимальным пересечением. Ее аналогом может служить последовательность соединений в реляционной БД.

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

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

Алгоритм получения двухуровневой

структуры сети

1. Для каждой функциональной зависимости вида А ->В создается файл Fi(A,B). Каждый блоквзаимно-однозначныхсоответствий также порождает файл с ключом, равным стар­ шему по объему понятия атрибуту.

В нашем примере будут созданы следующие файлы (ключи по­ мечены знаком #):

F1(HHH #, Директор, Адрес),

F2(Oraen #, НИИ, Ксотр),

F3(TeMa #, Датанач, Датакон, Приор),

F4(<DHO #, Отдел),

F5(TeMa #, Работа #, ФИО #, Прод),

F6(TeMa #, Захаз #, Обфин).

2. У всех пар файлов, полученных на шаге 1, проверяется условие для ключей (Ki является частью Kj). Если оно соблю-

112

дается, то из соответствующих файлов создается веерное от­ ношение Wij(Fi,Fj).

В нашем примере получим W35(F3,F5), W45(F4,F5), W36(F3,F6).

3.Если на шаге 2 будут получены два веерных отношения Wij и Wjk, то все атрибуты файла Fi передаются в файл Fj, и Fi вместе с Wij уничтожаются.

Внашем примере таких веерных отношений нет.

4.Атрибуты, не вошедшие в состав веерных отношений на шаге 2, добавляются в те файлы Fn (и содержащие Fn веерные отношения), где они будутнеключевыми. При наличии несколь­ ких подходящих файлов предпочтение отдается основным фай­ лам. Если требуемые Fn отсутствуют, то создается новый файл из атрибутов первичного ключа, и повторяются шаги 2, 3,4.

Внашем примере F4 расширяется атрибутами НИИ, Дирек­ тор, Адрес, Ксотр.

На рис.2.3 показана структура соответствующей двухуров­ невой БД.

Рис. 2.3. Сетевая БД со сведениями о научно-исследовательскихработах

113

Структуры основных отношений показаны в верхней час­ ти рисунка, а структуры зависимых отношений — внизу.

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

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

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

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

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

114

Сотрудник(Фамилия#, …)

Зарплата(Фамилия#, Дата#, Сумма)

Рис. 2.4. Пример сетевой базы данных для операций выборки

1. Операция OBTNM — получить запись в основном отно­ шении.

OBTNM (Сотрудник * «Иванов»)

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

2. Операция OBTNF — получить запись в зависимом отно­ шении.

ОВТОТ(Сотрудник * «Иванов», Зарпл*Осн)

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

В результате выполнения двух операторов OBTNM (Сотрудник * «Иванов») ОВТЫР(Сотрудник * «Иванов», Зарпл*Осн)

115

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

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

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

OBTNM (Сотрудник * «Иванов»)

Ml: OBTNF(CoTpyaHHK * «Иванов», Зарпл*Осн) print Зарпл

goto Ml

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

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

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

116

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

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

Иерархическая модель данных

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

Понятия отношения и веерного отношения в иерархичес­ кой модели данных не изменяются.

117

Иерархическойбазой данныхназываетсямножество отношен

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

1.Существуетединственное отношение, называемое корневым, которое не является зависимым ни в одном веерном отношении.

2.Все остальные отношения (за исключением корневого) яв­ ляются зависимыми отношениями только в одном веерном отно­ шении.

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

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

Факультет*

Группа* Кафедра*

Студент* Преподаватель*

а

Факультет*

Группа* Кафедра*

б

Рис. 2.5. Иерархическая база данных для вуза:

а— исходная структура;

б— с добавленными сведениями о группах дипломников

118

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

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

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

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

Далее эта информация организуется в линейную последо­ вательность значений, как это показано на рис. 2.6,6.

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

Правила концевого прохождения

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

2.Перечисляются все значения в том веерном отношении, на котором остановился шаг 1.

3. Перечисляются значения всех вееров этого веерного от­ ношения.

119

ФАК=01

СТ=91001…СТ=91021…СТ=87156 ПР=1101…ПР=1109…ПР=1711

а

Запись 1 ФАК=01 ГР=101 СТ=91001 СТ=91002 … СТ=91021 ГР=102 СТ=91022

Запись 2 ФАК=02 ГР=110 СТ=91188 СТ=91021 ГР=111

Рис. 2.6. Линейное представление значений

виерархической базе данных:

а— иерархическая взаимосвязь значений;

б— линейное представление данных

4.От достигнутого уровня происходит подъем на преды­ дущий уровень, и если возможно применить шаг 1, то процесс повторяется.

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

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

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

120

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

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

вого отношения должен функционально определять первичный ключ корневого отношения.

Рассмотрим алгоритм формирования иерархической БД на основе известного множества атрибутов и функциональных за­ висимостей. Исходное множество функциональных зависимос­ тей и атрибуты первичного ключа получаются так же, как при формировании множества отношений в ЗНФ. Алгоритм иллюс­ трируется тем же примером, что и в п. 2.2.2.

Алгоритм получения структуры иерархической БД

1. Для каждой функциональной зависимости вида А -»В создается отношение Si(A,B). Каждый блоквзаимно-однознач­ных соответствий также порождает отношение с ключом, рав­ ным старшему по объему понятия атрибуту.

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

S1(HHH #, Директор, Адрес), 82(Отдел #, НИИ, Ксотр), БЗ(Тема #, Датанач, Датакон, Приор), Б4(ФИО #, Отдел),

S5(TeMa #, Работа #, ФИО #, Прод), S6(TeMa #, Заказ #, Обфин).

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

121

Для отношений SI — S6 получаем две группы:

•SI, S2, S4, S5 (все ключи функционально определяют ат­ рибут НИИ);

•S3, S6, S5 (все ключи функционально определяют атри­

бут ТЕМА).

Далее шаги 3,4,5 выполняются раздельно для каждой груп­ пы. Количество групп определяет количество иерархических БД.

3.У всех пар отношений группы проверяется условие для ключей Kj -»Ki. Если оно соблюдается, то из соответствую­ щих отношений создается веерное отношение Wij(Si.Sj).

4.Найти в группе цепи веерных отношений и сцепить их в дерево. Элемент цепи образуется по условию Wij — Wjk.

Внашем примере получим:

группа 1: цепь W12(S1,S2), W24(S2,S4), W45(S4,S5) образует дерево;

группа 2: цепей нет, но W35(S3,S5) и W36(S3,S6) образуют дерево.

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

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

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

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

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

122

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

Минимальное множество вариантов выборки соответствует трем операциям.

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

2. GN — получить следующую запись на том уровне дере­ ва, где находится текущая запись после выполнения операто­ ра GU.

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

HHHGN.

Например, для запроса — получить информацию о препода­ вателе с кодом 1103 кафедры 11 факультета 01 — потребуется опе­ ратор

GU Факультет (Факультет=»01″) Кафедра (Кафедра=и11″) Преподаватель (Преподаватель=»1103″)

print Преподаватель

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

Запрос — получить список всех студентов группы 102 — реали­ зуется следующей последовательностью операторов

GU Факультет (Факультет=»01″) Группа (Группа=»Ю2″) Студент

М1: GN Студент print Студент goto Ml

123

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

Сравнение моделей данных

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

Рассматривая преимущества и недостатки известных мо­ делей данных, следует отметить ряд несомненных достоинств реляционного подхода:

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

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

•Независимость данных. Когда необходимо изменить структуру реляционной БД, это, как правило, приводит к минимальным изменениям в прикладных программах.

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

•Низкая скорость при выполнении операции соединения.

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

124

Достоинствами иерархической модели данных являются следующие.

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

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

Недостатки иерархической модели.

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

•Допустимость только навигационного принципа досту­ па к данным.

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

Необходимо отметить следующие преимущества сетевой модели данных.

•Универсальность. Выразительные возможности сетевой модели данных являются наиболее обширными в срав­ нении с остальными моделями.

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

В качестве недостатков сетевой моделиданных можно на­ звать.

•Сложность, т.е. обилие понятий, вариантов их взаимо­ связей и особенностей реализации.

•Допустимость только навигационного принципа досту­ па к данным.

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

125

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

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

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

2.4

МОДЕЛЬ ИНВЕРТИРОВАННЫХ ФАЙЛОВ И ИНФОРМАЦИОННО-ПОИСКОВЫЕСИСТЕМЫ

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

Основными информационными конструкциями в модели инвертированных файлов являются основной файл, который соответствует ранее введенному понятию «отношения», «ин­ вертированный файл» и «список связи».

Множество основных файлов базы данных обозначим че­ рез {Fl,F2,…,Fn}. Все записи файлов Fl…Fn получают в пре­ делах базы данных единую нумерацию.

126

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

Естественно, что выделенный атрибут (обозначим его А) мо­ жетпринимать в Fi несколько различных значений{а(1)д(2),…,а(к)}.

Поставим в соответствие каждому значению a(j) множество номеров записей файла Fi, в которых это значение связано с именем атрибута А.

{a(l),n(t),n(p),…} {a(2),n(g),n(h),…}

{a(j),n(x),n(y),…}

Через п с соответствующим индексом обозначены номера записей из Fi.

Определенная таким образом последовательность значений атрибута А и номеров записей основного файла Fi является инвер­ тированным файлом, которыйдалее будем обозначать через A(Fi).

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

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

Аналогия с двухуровневой сетью заключается в следующем. Связь инвертированного файла A(Fi) и файла Fi соответству­ ет типу «основной-зависимый».Отличия сводятся к тому, что

127

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

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

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

Ключевые слова А, В, С, D, Е

D 220

Е

100

140

240

Инвертированный

файл

Рис. 2.8. Связь основного и инвертированного файла

129

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

Так, при обработке запроса — найти все записи, содержа­ щие ключи Е или С, кроме А, которому в терминах теории множеств соответствует запись (Е UC)\ А, производится пос­ ледовательное вычисление

( { 100, 140, 240} U { 140, 240} ) \ { 140, 220} = { 100, 240}.

Результат означает, что запросу удовлетворяют записи с номерами 100 и 240.

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

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

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

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

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

130

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

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

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

В каждой информационно-поисковойсистеме должна при­ сутствовать административная подсистема и поисковая под­ система.

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

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

131

Рассмотрим пример базы данных ИПС с инвертированным файлом для поиска сведений об экспонатах выставок. Доку­ менты, хранящиеся в базе данных, представляют собой описа­ ния выставочных экспонатов. Среди атрибутов документа ис­ точниками дескрипторов могут быть следующие: Название экспоната, Описание экспоната, Ключевые слова, Разработ­ чик экспоната.

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

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

132

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

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

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

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

Пример 1

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

Текст команды и ответ информационно-поисковойсистемы приводятся ниже.

>Найти подшипник 1 27 Найти подшипник,

где 1 — порядковый номер запроса, 27 — количество найденных записей.

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

133

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

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

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

Пример 2

Поиск записей, содержащих в атрибуте Название экспоната слово подшипник.

>Найти подшипник/Название 2 19 Найти подшипник/Название

Для просмотра предоставляются 19 записей, в которых слово подшипник встречается в значениях атрибута Название экспоната.

В большинстве поисковых систем реализованы три логи­ ческие операции: И (конъюнкция), ИЛИ (дизъюнкция), НЕ (конъюнкция плюс отрицание).

Пример 3

>Найти подшипник НЕ роликовый 3 10 Найти подшипник НЕ роликовый

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

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

134

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

Пример 4 Использование скобок. Команда

>Найти подшипник ИЛИ ротор И электродвигатель аналогична команде >Найти (подшипник ИЛИ ротор) И электродвигатель

Измененный порядок скобок приведет к другой команде поис­ ка с другим результатом.

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

Для указания произвольного символа в поисковом терми­ не используется восклицательный знак «!». Этот знак не мо­ жет замещать первый символ термина.

>Найти т!л проводится поиск терминов типа тол, тыл и так далее.

>Найти маши?

проводится поиск терминов типа машина, машинный, маши­ ностроение и так далее.

Возможности информационно-поисковыхсистем по обра­ ботке множества отобранных в результате выполнения запро­ са документов здесь не рассматриваются.

Кроме поисковых операций, для современных информа­ ционных систем очень важна реализация возможности «дви­ жения» по базе данных «вверх-вниз-направо-налево»и пере­ ход к смежным разделам базы данных. В этих случаях указание

135

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

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

Пример

Рассмотрим структуру ВУЗа. Из всех видов деятельности ВУЗа рассматривается только научно-исследовательскаяработа (рис. 2.9).

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

•главная запись (сведения о руководстве ВУЗа);

•отношение Person с данными о преподавателях. Сведения о преподавателях нумеруются — Person(l), Person(2), Person(3) и т. д. Сведения о факультетах являются самостоятельными иерархичес­ кими базами данных. Их количество равно числу факультетов.

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

•сведения о руководстве факультета;

•список преподавателей факультета.

Рис. 2.9. Логическая структура информационно-поисковойсистемы вуза

136

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

В базе данных о кафедре есть главная запись (руководство ка­ федры) и отношение Research, в котором отдельные темы исследо­ ваний занумерованы как Research(l), Research(2), Research(3) и т. д.

Ссылки на другие разделы базы данных реализуются через но­ мера строк в отношении Person.

Например, содержимое главной записио ВУЗе:

<Н2>Руководство</Н2>

<DL>

<DT><B>PeKTop</B><DD>Person(l)

<ОТ><В>Проректор по учебной pa6oTe</B><DD>Person(2) <DT><B>npopeKTop по научной pa6oTe</B><DD>Person(3) <DT><B>Проректор по социально-экономическимвопроcaM</B><DD>Person(4)

<DT><B>ripopeKTop по административно-хозяйственнойра6oTe</B><DD>Person(5)

<ОТ><В>Ученый секретарь CoBeTa</B><DD>Person(6) </DL>

Список преподавателей факультета 01.

Person(l)

Person(4)

Person(2011)

Person(lOOl)

Person(1002)

Person(1043) Запись Research(3):

Ыате(Региональные проблемы рыночной экономики) Chief(1001)

BEGIN

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

END

137

Ссылка Chief(1001) означает, что научным руководителем темы является преподаватель, информация о котором хранится как Person(lOOl). Этот преподаватель работает на факультете 01.

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

ВОПРОСЫ И ЗАДАНИЯ

1. Сведения об учебном процессе зафиксированы в четырех от­ ношениях:

Студ(Гр,Зач,ФИО)

Оценка(Гр,Зач,Дисц,Дата,Пр,Оц)

Расп(Дата,Гр,Дисц,Пр)

Преп(Дисц,Пр,Каф)

В задании используются следующие обозначения: Студ — студент Гр — номер группы

Зач — номер зачетной книжки ФИО — фамилия студента Дисц — дисциплина Пр — фамилия преподавателя Оц — оценка Расп — расписание

Преп — преподаватель Каф — название кафедры

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

1) Найдите фамилии преподавателей, ведущих занятия в груп­ пах 30S и 307 одновременно.

2)Какие оценки получил студент Федоров?

3)У каких студентов преподает Иванов?

4)Какие студенты сдали те же экзамены, что и Федоров?

5)Какие преподаватели работают 10.10.98?

6)Какие преподаватели ведут занятия в тех же группах, что и Иванов?

7)По каким предметам сдается зачет, а не экзамен?

138

8)Какие студенты изучают дисциплину ВМ 10.10.98?

9)Какие дисциплины преподаются на кафедре ВМ?

10)Какие преподаватели преподают дисциплину ВМ?

11)Какие преподаватели поставили удовлетворительные оцен­ ки в группе 305?

12)Какие экзамены сданы у всех студентов группы 305?

13)Какие кафедры ведут занятия в группе 305?

14)Какие преподаватели работают в те же дни, что и Иванов?

15)Какие преподаватели поставили отличные оценки студенту Федорову?

16)По каким дисциплинам студент Федоров получил отличные оценки?

17)Какие студенты учатся в той же группе, что и Федоров?

2.Разработайте программы реализации операций вычитания

иделения отношений для СУБД семейства dBASE. Требуемые име­ на, файлов и атрибутов передавайте как параметры.

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

4.Какой нормальной форме соответствует база данных, приве­ денная в задании 1?

5.Определите отношения в ЗНФ для известного списка атрибу­ тов БД и функциональных зависимостей.

б. Определите отношения в ЗНФ для известного списка атрибу­ тов БД и функциональных зависимостей.

139

МЕТОДЫ ОРГАНИЗАЦИИ ДАННЫХ

3.1

АНАЛИЗ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ

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

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

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

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

141

горитмы, эффективные для одних методов организации дан­ ных, становятся неприемлемыми для других методов.

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

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

Адреса промежуточных записей фиксированной длины в массиве задаются формулой

A(i) = A(l)+(i-l)*L,

где А(1) — начальный адрес первой записи; A(i) — начальный адрес i-йзаписи;

L — длина одной записи.

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

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

142

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

Рис. 3.1. Последовательная организация данных

Ключевые атрибуты в записях обозначаются через p(i), где i — номер записи, общее число записей в массиве обозначается через М.

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

р (0 < = р (i + 1) — упорядоченность по возрастанию; p(i) >= p(i+l) — упорядоченность по убыванию.

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

143

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

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

Упорядоченные данные эффективны для организации бы­ строго поиска информации. Выходные документы, выводимые на печать, полученные на основе отсортированных данных, удобны для дальнейшего использования человеком. Многие алгоритмы задач управления вообще рассчитаны на исполь­ зование только упорядоченных данных. Отсортированные данные позволяют организовать быструю обработку несколь­ ких массивов. Далее будем считать все массивы упорядочен­ ными по возрастанию значений одного атрибута, когда для ключа i-йзаписи p(i) справедливо условие p(i)<=p(i+l).

Критерии эффективности алгоритмов

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

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

•время поиска данных. Как известно, условия поиска (вы­ борки) на практике могут быть достаточно разнообраз­ ные. Анализируется обычно простейший и наиболее рас­ пространенный случай (поиск по совпадению) — найти записи, у которых значение ключевого атрибута равно заранее известной величине q;

144

•время корректировки данных. Из всех возможных вари­ антов корректировки учитывается включение или исклю­ чение одной записи;

•объем дополнительной памяти, расходуемой под служеб­ ную информацию (например, адреса связи).

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

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

•распределение значений ключевых атрибутов в массиве из М записей — равномерное;

•значение q при поиске по совпадению выбрано случай­ но: это означает, что поиск с одинаковой вероятностью 1/М может закончиться на любой записи массива;

•положение включаемой (исключаемой) записи при кор­ ректировке определяется теми же вероятностями, что и при поиске.

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

145

состояния, будем называть случайным массивом. Все его М! состояний равновозможны. Через М! обозначено произведе­ ние1-2-…М.

Таким образом, минимальное число сравнений, необходи­ мое для упорядочения массива из М записей, определяется как

С = log M!,

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

После преобразований по формуле Стирлинга получаем:

C=M(logM-1.43).

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

Соответствующее преобразование выглядит как С ~ М • log M (читается: С пропорционально М • logM). Значением коэффи­ циента пропорциональности в этом контексте мы интересо­ ваться не будем. Разумеется, справедлива запись выражения для времени сортировки Т ~ М • log M.

Поиск в последовательном массиве

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

Простейшим условием поиска является поиск по совпаде­ нию, т. е. равенство значения ключевого атрибутаi-йзаписи р(0 и некоторого заранее заданного значения q. Алгоритмы всех разновидностей поиска можно получить из алгоритмов поиска по совпадению, которые и рассматриваются в даль­ нейшем.

146

Базовым методом доступа к массиву является ступенча­ тый поиск. Этот метод предполагает упорядоченность обра­ батываемых записей, причем безразлично, по возрастанию или по убыванию. Для определенности будем считать, что массив отсортирован по возрастанию значений ключевого атрибута p(i).

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

program poisk; const M=20; var i,q:integer;

p: array[l..M] of integer; begin

шгке(‘ввод q’); readln(q); fori:=l toM do begin

>&тке(‘ввод’, i,’ элемента массива’); readln(p[i]) end;

i:=l;

while q < p[i] do i:= i+1;

if q <> p[ij then writeln(‘B массиве нет значения’, q) else writeln(‘HOMep ‘,i,’ значение’, q)

end.

Число сравнений в цикле while может быть выражено как С= Z i*r(i), где суммирование по i ведется в пределах от 1 до М.

Поиск с одинаковой вероятностью r(i)=l/M может окон­ читься на любой записи, поэтому

С = (1/М)- Е i = (М + 1)/2 или С ~ М.

147

Рассмотрим двухступенчатый поиск в массиве, состоящем из М записей. Для заданного М выбирается константа dl, на­ зываемая шагом поиска. Если необходимо отыскать запись со значением ключевого атрибута, равным q, производятся сле­ дующие действия.

Значение q последовательно сравнивается с рядом величин р(1), p(l+dl), p(l+2*dl),…, p(l+k*dl) до тех пор, пока будет впервые достигнуто неравенство p(l+m*dl)=>q. Здесь закан­ чивается первая ступень поиска. На второй ступени q после­ довательно сравнивается со всеми ключами, которые имеют номер l+m*dl и больше, до тех пор, пока в процессе сравне­ ний будет достигнут ключ, больший, чем q. Извлеченные при этом записи с ключом q образуют результат поиска.

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

C = M/(2*dl) + dl/2.

Параметр dl выбираемый и естественно выбрать его так, чтобы минимизировалось С. Будем считать dl непрерывной переменной и вычислим производную

C’=-M/(2*dlA2)+l/2.

Из условия С’= 0 получаем dl=SQR(M). Вторая производ­ ная С» в точке х = dl положительна, следовательно, достигну­ то минимальное значение С.

При п-ступенчатомпоиске заранее выбираются констан­ ты п и S. На первом этапе ключевые атрибуты для сравнения с искомым ключом q выбираются из массива по закону ариф­ метической прогрессии, начиная с р(1) и шагом dl=M/S (ок­ ругление в меньшую сторону). Когда будет впервые достиг­ нут ключ p(k) > q, выбирается шаг d2 = dl/S и организуются сравнения с этим шагом, начиная сp(k-dl).Описанные дей­ ствия повторяются п раз,-причемшаг на последней ступени поиска dn= 1.

Минимальное число сравнений достигается при S=MA(l/n), и, кроме того, существует оптимальное п=1п(М).

148

Ступенчатый поиск имеет важный частный вариант —

бинарный поиск, когда S=2.

Для бинарного поиска вводятся левая граница интервала поиска А и правая граница В. Первоначально интервал охва­ тывает весь массив, т. е. А=0, В=М+1. Вычисляется середина интервала i по формуле i=(A+B)/2 с округлением в меньшую сторону. Ключ i-йзаписи p(i) сравнивается с искомым значе­ нием q. Если p(i) =q, то поиск заканчивается. В случае p(i)>q записи с номерами i+1, i+2,…, М заведомо не содержат ключа q, и надо сократить интервал поиска, приняв B=i. Аналогич­ но при p(i)<q надо взять A=i. Далее середина интервала вы­ числяется заново, и все действия повторяются. Если будет до­ стигнут нулевой интервал, то требуемой записи в массиве нет.

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

program bin; const M=10;

var i,A,B,q: integer; p:array[l..M] of integer; begin

write(‘BBOfl q’); readln(q); fori:=l toMdo begin

write(‘BBOfl\ i,’ элемента массива’); readln(p[i]) end;

A:=0;B:=M+1;

i:=(A+B) div 2; {определение середины интервала} {цикл до встречи p[i]=q или до нулевого интервала A=i} while (p{i]<>q) and (A<i) do

begin

ifq>p[i] then A:=i else B:=i;

i:=(A+B) div 2; {середина нового интервала} end;

149

if A=i then writeln(‘B массиве нет значения’, q) else writeln(‘HOMep \i,’ значение’,^

end.

Достаточно легко оценить максимальное число сравнений Cm при поиске данных бинарным методом. Сокращение ин­ тервала поиска на каждом шаге в худшем случае приведет к интервалу нулевой длины, что соответствует отсутствию в массиве искомого значения ключевого атрибута. После пер­ вого сравнения интервал поиска составит М/2 записей, после второго — М/4 и т. д. Когда интервал поиска впервые станет меньше 1, применяемая схема округления результата деления даст нулевой интервал и поиск закончится. Это соответствует неравенству

М/(2АСга)<=1

(знак Л обозначает возведение в степень), откуда Cm~log M. Среднее число сравнений при бинарном поиске составля­ ет C=log(M)-1.Для обоснования представим все возможные

разветвления алгоритма бинарного поиска в видедерева. Чис­ ло уровней дерева соответствует Ст. Половина возможных сравнений расположена на последнем уровне и половина— на первых (log(M)-l)уровнях.

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

• для последовательного поиска Т1~МилиТ1=к1*М;

•для двухступенчатого поиска T2~SQR(M) или T2=k2(SQR(M));

•для бинарного поиска

ТЗ-logMили T3=k3*logM.

150

Коэффициенты пропорциональности в каждом случае не­ известны (они определяются в зависимости от быстродействия ЭВМ и применяемого языка программирования). Однако оче­ видно, что функция логарифма растет с увеличением М мед­ леннее, чем две другие функции (для Т1 и Т2), как это показа­ но на рис. 3.2.

Рис. 3.2. Сравнение методов поиска данных в массиве

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

Корректировка последовательного массива

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

151

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

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

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

Tk=logM+ML,

где L — длина одной записи массива.

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

Tk~ML.

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

152

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

Массив записей, подвергающихся изменениям, называет­ ся основным. Изменения, которые необходимо внести в основ­ ной массив, накапливаются в специальном упорядоченном массиве изменений, рассчитанном на 1<=ш<=М записей. Обычно m составляет несколько процентов от М. При необ­ ходимости обработки основного массива он объединяется с массивом изменений.

При объединении основного массива с массивом измене­ ний выполняются следующие операции (алгоритм слияния):

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

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

Цепная (списковая) организация данных

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

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

153

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

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

1. Определение адресов связи как начальных адресов за­ писей:

type ref=Anode; node=record

key: integer; {ключевой атрибут записи} other: string[30]; {остальные атрибуты} next: ref {адрес связи}

end;

2. Определение адресов связи как номеров записей:

const M=12; type node=record

key: integer; {ключевой атрибут записи} other: string[30]; {остальные атрибуты} next: integer {адрес связи}

end;

var t:array(l..M] of node;

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

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

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

154

6 Записи

Рис. 3.3. Варианты списковой организации данных:

а— совместное хранение записей и адресов связи;

б— раздельное хранение записей и адресов связи (0 — конец

списка)

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

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

При формировании упорядоченного списка записей воз­ можны два варианта:

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

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

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

В итогевремя формирования упорядоченного списка пропор­ ционально T~M-logM.

155

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

Дляпоиска данных воднонаправленномспискеиспользуетсяедин ственный метод — последовательный поиск.Ключевой атрибут пер­ вой записи (ее адрес извлекается из указателя списка) сравнивается

с искомым значением q, затем такое же сравнение выполняетсядля ключа второй записи, которая извлекается по адресу связи первой записи, и т. д. Время поиска, естественно, пропорционально Т~М.

Неэффективность бинарного поиска для списковой органи­ зации данных объясняется тем обстоятельством, что для дости­ жения середины интервала требуется последовательное движе­ ние в соответствии с адресами связи и суммарное количество переходов от записи к записи достаточно велико. Число перехо­ дов отзаписи к записи придоступе к серединам интервалов пред­ ставляется величиной МУ2+М/4+М/8+…, что практически состав­ ляет М.

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

Рис. 3.4. Организация списков:

а — двунаправленного; б — кольцевого

156

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

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

Цепной каталог

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

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

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

const M=9; type node=record

key: integer; {ключевой атрибут записи} next: integer {адрес связи}

end;

var t:array[l..MJ of node;

Первоначальное состояние.каталога показано на рис. 3.5,а.

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

157

Рис. 3.5. Операции корректировки в цепном каталоге:

— ставка записи с ключом 61; б — удаление записи с ключом 30

Алгоритм вставки записи с ключом F в цепной каталог. 1. Найти в каталоге запись с ключом непосредственно мень­

ше, чем F (предшествующая запись).

2.Поместить запись с ключом F в первую позицию сво­ бодной памяти.

3.Заменить указатель свободной памяти (УСП) на адрес связи новой записи, этот адрес — на адрес связи предшествую­ щей записи, а последний — на первоначальное значение УСП.

На рис. 3.5,а вставляется запись с ключом F=61.

158

/ / \N

нi

Рис. 3.6. Пример древовидной организации данных (а) и представление его в памяти ЭВМ (б)

159

Алгоритм удаления записи с ключом W из каталога.

1. Найти в каталоге запись с ключом непосредственно мень­ ше, чем W (предшествующая запись).

2. Заменить УСП на адрес связи предшествующей записи, этот адрес — на адрес связи исключаемой записи, а последний — на первоначальное значение УСП.

На рис. 3.5,6 удаляется запись с ключом W=30.

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

Древовидная организация данных

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

•на 1-муровне расположена только одна запись (корень дерева),

•к любой записи i-roуровня ведет адрес связи только от одной записи уровняi-1.

В данном определении понятия «дерево» и «уровень» вво­ дятся одновременно. Если записи получат номера уровней, соответствующие определению, то они получат и древовид­ ную организацию.

Количество уровней в дереве называется рангом. Записи дерева, которые адресуются от общей записи(i-l)-roуровня, образуютгруппу. Максимальное число элементов в группе называетсяпорядком дерева. В дереве на рис. 3.6,а порядок равен 3 и ранг составляет 4 (записи дерева обозначены заглав-

160

ными латинскими буквами). Деревья обычно формируются двунаправленными, адрес связи от записи уровня i+1 к записи i-ro уровня называетсяобратным.

При размещении дерева в памяти ЭВМ каждая запись мо­ жет занимать произвольное место.

Назовем звеном связи набор адресов связи, принадлежа­ щих одной записи. Если порядок дерева равен р, то звено связи состоит из р+1 адресов (один адрес обратный, опреде­ ляющий связь с записью непосредственно более высокого уровня). Корень дерева адресуется из специального указате­ ля дерева. Незанятые адреса связи содержат признак конца списка. В качестве примера размещения дерева в памяти ЭВМ на рис. 3.6,6 показан один из возможных вариантов представления дерева с рис. 3.6,а, обратные адреса связи не показаны.

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

Чтобы определить понятие упорядоченности бинарных деревьев, требуется ввести ряд новых понятий. В качестве при­ мера рассмотрим бинарное дерево на рис. 3.7 (внутри показа­ ны значения ключевого атрибута). Запись А — корень дерева. Записи, у которых заполнены два адреса связи, называются полными, записи с одним заполненным адресом —неполными, записи с двумя незаполненными адресами —концевыми. На рис. 3.7 записи А, В, Е, F — полные, С — неполная, D, H, I, J, К — концевые. Адреса связи делятся на левые и правые. Так, адрес от Е к Н —левый, от Е к I —правый. Каждая запись имеет левую и правую ветви. Правую (левую) ветвь записи образует подде­ рево, адресованное из этой записи через правый (левый) адрес связи. У записи С правая ветвь состоит из записей F, I, К, ле­ вая ветвь пустая.

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

161

Рис. 3.7. Пример бинарного дерева

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

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

Алгоритм построения упорядоченного бинарного дерева

1. Первая запись массива с ключом р(1) становится корнем дерева.

2. Значение ключа второй записи р(2) сравнивается с р(1), находящимся в корне дерева. Если р(2)<р(1), то вторая запись помещается на левой от корня ветви, в противном случае — на правой ветви. Сейчас получено упорядоченное дерево из пер­ вых двух записей, далее на каждом шаге создается упорядо­ ченное дерево из первых i записей.

162

3. Выбор места i-йзаписи массива производится следую­ щим образом. Ключ p(i) сравнивается с корневым значением, и выполняется переход по левому адресу (если p(l)>p(i)), а при p(l)<=p(i) — по правому адресу. Ключ достигнутой записи так­ же сравнивается с p(i), и снова организуется переход по лево­ му или правому адресу и т. д. Когда будет достигнут незапол­ ненный адрес связи, то он должен адресовать запись с ключом p(i). Указанные действия повторяются до исчерпания всех за­ писей исходного массива.

Например, упорядоченное дерево на рис. 3.7 получается из массива записей с ключевыми атрибутами 23, 10, 18, 27, 15,32, 8,30,32,21.

В процессе поиска данных по совпадению в упорядочен­ ном бинарном дереве просматривается некоторый путь по де­ реву, начинающийся всегда в его корне. Искомое значение ключа q сравнивается со значением корня р(1). Если p(l)>q, просмотр дерева продолжается по левой ветви корня, если p(l)<=q — по правой. Для произвольной записи дерева с клю­ чом p(i) результаты сравнения означают:

•p(i)=q — запись, удовлетворяющая условию поиска, най­ дена, и поиск продолжается по правой ветви p(i);

•p(i)>q — производится переход к записи, расположенной на левой ветви p(i);

•p(i)<q — производится переход к записи, расположенной на правой ветви p(i).

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

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

163

Если обозначить через Е(М) сумму длин всех ветвей дерева с учетом выхода на нулевые адреса связи, то среднее число срав­ нений при поиске в упорядоченном бинарном дереве С'(М) составит

С'(М)=Е(М)/(М+1).

Дерево с М-1вершиной отличается от дерева с М верши­ нами, полученного из него, отсутствием одной концевой за­ писи или (применительно к величине Е) двумя нулевыми ад­ ресами связи. Поэтому Е (М) — Е (М-1)=2. Вычислим разность

Е(М)-Е(М-1)

dL = С'(М) — С'(М-1)=——— — = 2/(М+1). М+1

Математическое ожидание средней длины пути при поис­ ке С'(М) равно сумме математических ожиданий dL от 1 до М. Приближенно заменяя суммирование интегрированием, получаем:

С'(М) = 21п(М+1).

При замене натурального логарифма на двоичный (1п2 = 0,7) получаем оценку числа сравнений при поиске в упо­ рядоченном бинарном дереве:

С = 1,4 log М или С — log M.

При формировании упорядоченного бинарного дерева в среднем производится

С= l,4M*logM

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

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

164

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

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

Способ нахождения соседней справа записи очень простой. Если исключаемая запись имеет ключ q, то от нее происходит переход по правой ветви дерева и нроизводится поиск от дос­ тигнутой записи значения q. Запись, на которой остановится поиск, будет соседней. Она пересылается на место исключае­ мой записи, а сама соседняя запись исключается. Это уже про­ стая задача, так как соседняя запись не может быть полной.

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

Списки

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

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

165

буквами, а списки заключаются в круглые скобки. Список, включенный в другой список, называется подсписком. Пере­ числение всех списков из записей al, a2,…,aN, образующих множество L0, сводится к следующему.

Обозначим через Li’ множество всех кортежей с элемента­ ми из Li. Введем последовательность множеств:

L1=L0’+L0 (+ здесь означает знак объединения множеств) L2=L1’+L1

L3=L2’+L2

Все списки содержатся в множестве L=L0+Ll+…Li+…

Пример

Пусть L0= {a, b}. Тогда LI = {(a,b),(a),(b).a,b}

L2={((a, b), (a), (b), a, b),((a, b), (a), (b), a),…) и т. д.

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

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

ные участки в памяти ЭВМ. Адреса связи, принадлежащие каждой записи, образуют звено связи. В звене связи однонап­ равленного списка два адреса: первый указывает на следую­ щий элемент списка, второй — на подсписок или запись. В звене связи двунаправленного списка четыре адреса связи: два из них обеспечивают прямое и обратное направление в списке, третий и четвертый адресуют начало н конец под­ списка. Однонаправленный список ((a,b),b,((c),c)) показан на рис. 3.8.

Дерево тоже имеет формулу, так как существует эквива­ лентный ему список,

166

Указатель списка

Записи

Рис. 3.8. Представление списка ((a, b), b, ((с,) с)) в памяти ЭВМ

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

В табл. 3.1 собраны все оценки методов организации дан­ ных, что позволяет сделать ряд выводов.

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

памяти

167

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

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

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

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

3.2

МЕТОДЫ УСКОРЕНИЯ ДОСТУПА К ДАННЫМ

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

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

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

168

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

Адресная функция

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

Адресной функцией называется зависимость

Адресная функция може’г вырабатывать одинаковое зна­ чение i для значений р, принадлежащих разным записям, ко­ торые в этом случае называются синонимами. К функции f предъявляются следующие требования:

•она должна быть задана аналитически и вычисляться до­ статочно быстро;

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

•число записей-синонимовдолжно составлять10-20%от общего числа записей.

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

i = p — a ,

где а — константа.

169

Пусть известны минимальное значение ключевого атрибута в массиве р’ и максимальное значение р » . Тогда а = р’ — 1. Необходимый участок памяти для данных оценивается в

р » — р ‘ +1 запись. Записи-синонимысвязываются в цепочки

спомощью адресов связи, они занимают дополнительную (ре­ зервную) память.

Пример размещения записей с ключами 13,11,14,11,15,18, 14,16 согласно адресной функции i = р — а показан на рис. 3.9.

Рис. 3.9. Организация записей в соответствии с адресной функцией i = р — а

При доступе к записи с ключом q вычисляется i=f(q) и про­ изводится обращение к i-йзаписи. При необходимости с по­ мощью адресов связи извлекаются все синонимы.

Недостаток адресной функции вида i = р — а — большой объем неиспользуемой памяти, если р » — р ‘много больше, чем количество записей М.

Указанного недостатка лишена функция вида i = OCT(p/m).

Здесь m — целое число; ОСТ — остаток от деления р на т . Вычисление i на языке Паскаль производится с помощью

оператора i: =p mod m.

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

Выделяются 2 зоны памяти — основная и резервная. Основ­ ная зона содержит m записей.Резервная зона предназначена для размещениязаписей-синонимов.

170

Рис. ЗЛО. Организация записей в соответствии с адресной функцией i = OCT (p/m)

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

Например, для массива ключей со значениями 17, 9, 4, 14, 25, 21, 20, 11 необходимо выбрать щ=7, поскольку М=8 (возможно также т=19). Содержимое основной и резервной зон иллюстриру­ ет рис.3.10. Резервная зона заполняется последовательно. При по­ иске значения, например q=l 1, вычисляется i = ОСТ(11/7)=4, и да­ лее последовательно сравниваются 4 и 11,25 и 11и т. д. В рассмат­ риваемом примере число записей-синонимовсоставляет 3/8.

Индексы

Для ускорения поиска записей в массиве используется до­ полнительная информация, организованная в виде массива индексов.

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

171

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

Имеются три важные разновидности индексов:

•информация о каждой записи основного массива попа­ дает в индекс (сплошная индексация);

•номера записей, информация о которых выносится в ин­ декс, образуют арифметическую прогрессию с шагом d> 1. Основной массив, дополненный таким индексом, обыч­ но называется индексно-последовательным;

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

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

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

В индекс выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d. На рис. 3:11 показаны ключевые атрибуты основного массива и состояние массива индексов для d=3.

Индекс