Л. Этапы проектирования базы данных

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

Весь процесс проектирования БД можно разбить на ряд взаи­мосвязанных этапов, каждый из которых обладает своими осо­бенностями и методами проведения (рис. 11.1) [79].

Рис. 11.1. Этапы проектирования БД

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

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

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

1) определение собственно сведений об объектах предметной области;

2) анализ возможных запросов к БД и требований по опера­тивности их выполнения.

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

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

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

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

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

171

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

11.2. Мифологическая модель «сущность — связь»

Мифологическая модель «сущность — связь» {entity — relationship model; ER-model) П.Чена представляет собой описательную (не­формальную) модель предметной области, семантически опреде­ляющую в ней сущности и связи [51].

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

Сущность — это собирательное понятие некоторого повторя­ющегося объекта, процесса или явления окружающего мира, о котором необходимо хранить информацию в системе [79]. Сущ­ность может определять как материальные (например, «сотруд­ник фирмы», «грузовой автомобиль» и т.п.), так и нематериаль­ные объекты (например, «экзамен», «проверка» и т.п.). Главной особенностью сущности является то, что вокруг нее сосредоточен сбор информации в конкретной предметной области. Тип сущно­сти определяет набор (класс) однородных объектов, а экземпляр сущности — конкретный объект в наборе (классе). Каждая сущ­ность в модели П.Чена именуется. Для идентификации конкрет­ного экземпляра сущности и его описания используется один или несколько атрибутов.

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

Связи в инфологической модели выступают в качестве сред­ства, с помощью которого представляются отношения между сущ­ностями, имеющими место в предметной области [79]. При ана­лизе связей между сущностями могут встречаться бинарные (между двумя сущностями) и в общем случае и-арные (между п сущно­стями) связи. Например, сущности «отец», «мать» и «ребенок» могут находиться в трехарном отношении «семья» («является чле­ном семьи»). Связи должны быть поименованы; между двумя ти­пами сущностей могут существовать несколько связей.

172

 

Наиболее распространены бинарные связи. Учитывая, что лю­бую я-арную связь можно представить в виде нескольких бинар­ных, подробнее остановимся именно на таких связях между двумя типами сущностей, устанавливающими соответствие между мно­жествами экземпляров сущностей. Различают четыре типа связей [79]: •

1) один к одному (1:1);

2) один ко многим (1: М);

3) многие к одному (М: 1);

4) многие ко многим (М: N).

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

Связь один ко многим определяет такой тип связи между типами сущностей An В, для которой одному экземпляру сущно­сти А может соответствовать нуль, один или несколько экземпля­ров сущности В, но каждому экземпляру сущности В соответству­ет один экземпляр сущности А. При этом однозначно идентифи­цировать можно только экземпляр сущности А по экземпляру сущ­ности В. Примером связи типа 1: М является связь «учится» между сущностями «учебная группа» и «студент». Для такой связи, зная конкретного студента, можно однозначно идентифицировать учеб­ную группу, в которой он учится, или, зная учебную группу, можно определить всех обучающихся в ней студентов.

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

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

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

173

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

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

Рис. 11.2. Связи между сущностями: а — двунаправленные; б — однонаправленные

Графически типы сущностей, атрибуты и связи принято изо­бражать прямоугольниками, овалами и ромбами, соответственно. На рис. 11.2 представлены примеры связей различных типов; на рис. 11.3 — фрагмент инфологической модели «Учебный процесс факультета».

174

Рис. 11.3. Фрагмент мифологической модели «Учебный процесс факультета»

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

• как связь: «входит в состав» для сущностей «студент» и «учеб­ная группа»;

• атрибут: «имеет» в составе «студент» сущность «учебная груп­па»;

• сущность: «состав учебной группы».

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

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

175

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

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

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

При определении связей между сущностями следует избегать связей типа М: N, так как они приводят к существенным затратам ресурсов ЭВМ. Устранение таких связей предусматривает введе­ние других (дополнительных) элементов — сущностей и связей. На рис. 11.5 приведен пример исключения связи «многие к мно­гим».

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

Рис. 11.4. Исключение повторяющейся группы атрибутов

176

В заключение приведем типовую последовательность работ (дей­ствий) по построению инфологической модели:

Рис. 11.5. Исключение связи типа М: N

1) выделение в предметной области сущностей;

2) введение множества атрибутов для каждой сущности и вы­деление из них ключевых;

3) исключение множества повторяющихся атрибутов (при не­обходимости);

4) формирование связей между сущностями;

5) исключение связей типа M:N (при необходимости);

6) преобразование связей в однонаправленные (по возможно­сти).

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

ГЛАВА 12. КОНЦЕПТУАЛЬНЫЕ МОДЕЛИ ДАННЫХ

Л. Модель данных

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

По существу, модель данных — это совокупность трех состав­ляющих [79]:

1) типов структур данных;

2) операций над данными;

3) ограничений целостности.

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

Типы структур данных. Среди широкого множества определе­ний, обозначающих типы структур данных, наиболее распро­странена терминология CODASYL (Conference of DAta SYstems Language) — международной ассоциации по языкам систем обра­ботки данных, созданной в 1959 г. В соответствии с этой термино­логией используют пять типовых структур (в порядке усложне­ния): 1) элемент данных; 2) агрегат данных; 3) запись; 4) набор; 5) БД.

Дадим краткие определения этих структур [79].

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

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

178

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

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

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

• БД может содержать любое количество типов записей и типов наборов;

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

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

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

Рассмотренные типы структур данных могут быть представле­ны в разной форме: графовой; табличной; в виде исходного тек­ста языка описания данных конкретной СУБД.

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

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

• найти следующие данные (запись);

• найти предыдущие данные;

179

• найти и-е данные;

• найти первые (последние) данные.

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

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

. СПЕЦИАЛЬНОСТЬ = БАЛЛИСТИКА;

. ВОЗРАСТ > 45;

.ДАТА< 19.04.2000 и т.п.

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

. (ДАТА_РОЖДЕНИЯ < 28.12.1953) И (СТАЖ > 32);

. (УЧЕНОЕ_ЗВАНИЕ = ДОЦЕНТ) ИЛИ (УЧЕНОЕ_ЗВАНИЕ = = ПРОФЕССОР) и т.п.

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

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

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

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

180

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

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

Типы моделей данных

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

1) иерархическая;

2) сетевая;

3) реляционная;

4) бинарная;

5) семантическая сеть.

181

Рассмотрим основные особенности перечисленных моделей.

Иерархическая модель данных. Исторически первой (можно сказать классической) [51] является иерархическая модель дан­ных, в основе которой лежит иерархическая структура типа дере­ва [5].

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

На рис. 12.1 показан фрагмент объектной записи в иерархиче­ской модели данных. Часто используется также упорядоченное дерево [78], в котором значим относительный порядок поддере­вьев.

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

Характерными примерами реализации иерархических структур являются язык COBOL и СУБД семейства IMS (создана в рамках проекта высадки на Луну — «Аполлон») и System 2000 (S2K).

Рис. 12.1. Иерархическая модель данных

182

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

Рис. 12.2, Сетевая модель данных

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

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

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

Известно, что применение на практике иерархических и сете­вых моделей данных в некоторых случаях требует разработки и сопровождения значительного объема кода приложения, что иногда может стать непосильным бременем для ИС [84, 85].

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

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

183

 

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

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

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

Бинарная модель не получила особо широкого распростране­ния, но в ряде случаев находит практическое применение. Так, в области ИИ уже давно ведутся исследования с целью представле­ния информации в виде бинарных отношений. Рассмотрим триаду (тройку) «объект —атрибут—значение» (см. гл. 23). Триада «Ива­нов—возраст—30» означает, что возраст некоего Иванова равен 30 годам. Эта же информация может быть выражена, например,

Рис. 12.4. Бинарное отношение

184

Рис. 12.5. Соотношение понятий в семантической сети

бинарным отношением «Возраст». Понятие «бинарное отношение» положено в основу таких моделей данных, как, например Data Semantics (автор Ж.-Р.Абриал) и DIAM II (автор М.Сенко) [51.1 Бинарные модели данных обладают возможностью представле­ния связей любой сложности (и это их несомненное преимуще­ство), но вместе с тем их ориентация на пользователя недостаточ­на [78].

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

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

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

185

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

ГЛАВА 13. РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ

Основные понятия реляционной алгебры

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

Определение любой модели данных требует описания трех эле­ментов (см. подразд. 12.1): 1) типов структур данных; 2) операций над данными; 3) ограничений целостности. Рассмотрим структу­ры данных и ограничения целостности.

Типы структур данных реляционной модели. Введем несколько основных понятий [79].

Множество возможных значений некоторой характеристики объекта называется доменом (англ. domain):

Например, в качестве домена можно рассматривать такие ха­рактеристики студента, как его фамилия, курс, рост и т.п.:

Очевидно, что можно сопоставить понятия «атрибут» инфоло-гической и «домен» реляционной моделей данных. Возможные значения характеристик объектов могут принимать числовые или текстовые значения, а их множества могут быть как конечными, так и бесконечными. Отметим, что в случае конечности домена можно организовать проверку явных ограничений целостности: в данном примере домен Z)_p0CT определяет, что все студенты долж­ны иметь рост от 160 до 230 см, а номер курса не может превы­шать пяти.

187

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

(Иванов, 1, 172);

(Сидоров, 3, 181);

(Уткин, 5, 184).

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

Декартовым произведением к доменов называется множество всех возможных значений кортежей:

D = D_lD_z..,D_k.

Пусть для того же примера определены три домена:

D_r = {Иванов, Петров};

А = {1, 4};

А = {168, 181}.

Тогда их декартовым произведением будет множество D, со­стоящее из восьми записей:

При увеличении размерности любого из доменов увеличивает­ся и размерность их декартова произведения. Так, если во втором домене определены три элемента D₂ = {1, 4, 5}, декартово произ­ведение имеет вид

188

(Иванов, 1,168) (Иванов, 1,181) (Петров, 1,168) (Петров, 1,181) (Иванов, 4,168) (Иванов, 4,181) (Петров, 4,168) (Петров, 4,181) (Иванов, 5, 168) (Иванов, 5,181) (Петров, 5,168) (Петров, 5,181

Иными словами, декартово произведение — это множество всех возможных комбинаций элементов исходных доменов.

Наконец, отношением (англ. relation) R, определенным на мно­жествах доменов D_u D₂, ..., D_b называют подмножество их де­картова произведения

R^D_xD₂...D_k.

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

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

189

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

• каждая строка таблицы является кортежем;

• порядок строк может быть любым;

• повторение строк не допускается;

• порядок столбцов в отношении фиксирован.

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

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

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

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

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

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

⇐ Предыдущая27282930313233343536Следующая ⇒

Поделиться: