Модель сущность–атрибут–связь была предложена Петером Пин-Шен Ченов в 1976 г. На использовании разновидностей ER модели основано большинство современных подходов к проектированию баз данных (главным образом реляционных). Моделирование предметной области базируется на использовании графических диаграмм, включающих небольшое количество разнородных компонентов. В связи с наглядностью представления концептуальных схем баз данных ER-модели получили широкое распространение в CASE системах, поддерживающих автоматизированное проектирование реляционных баз данных.

Базовыми понятиями ER-модели являются сущность, атрибут и связь.

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

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

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

Как и сущность, связь – это типовое понятие, все экземпляры обеих пар связываемых сущностей подчиняются правилам связывания. На рис. 1. приведен пример изображения сущностей и связи между ними. Данная диаграмма может быть интерпретирована следующим образом:

Каждый СТУДЕНТ учится только в одной ГРУППЕ;

Любая ГРУППА состоит из одного или более СТУДЕНТОВ.

Рис. 1. Связь между сущностями

На рис. 2 изображена сущность ЧЕЛОВЕК с рекурсив­ной связью, связывающей ее с ней же самой. Лаконичной устной трактовкой изображенной диаграммы является следующая:

Каждый ЧЕЛОВЕК является сыном одного и только одного ЧЕЛО­ВЕКА;

Каждый ЧЕЛОВЕК может являться отцом для одного или более ЛЮ­ДЕЙ (“ЧЕЛОВЕКОВ”).

Рис. 2. Рекурсивная связь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Второй вариант – прямая реализация СУБД, основанная на какой-либо семантичес­кой модели данных.

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

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

Модели данных

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

Самый простой тип – это список – структура данных в виде линейной последовательности.

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

Рис. 3. Иерархическая древовидная структура БД

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

– все типы связей должны быть функциональными, т.е. 1:1, 1:М, М:1;

– структура связей должна быть древовидной.

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

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

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

– имеется единственная особая вершина, называемая корнем, в которую не заходит ни одно ребро;

– во все остальные вершины заходит только одно ребро, а ис­ходит произвольное количество ребер;

– нет циклов.

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

– иерархия всегда начинается с корневого узла;

– на первом уровне иерархии может находиться только корне­вой узел;

– на нижних уровнях находятся порожденные (зависимые) узлы;

– каждый порожденный узел, находящийся на уровне L, свя­зан только с одним непосредственно исходным узлом (непосредст­венно родительским узлом), находящимся на более верхнем (L – 1)-м уровне иерархии дерева;

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

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

– существует единственный иерархический путь доступа к узлу начиная от корня дерева (рис. 4).

Рис. 4. Иерархический путь доступа к узлу

Другими словами, иерархическая модель представления знаний (или дерево) – структура данных, в которой каждый узел имеет только одного “родителя”, т.е. господствующий узел (кроме самого верхнего узла) и неограниченное количество “потомков”, т.е. узлов, над которыми данный узел господствует.

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

Рис. 5. Сетевая структура

В 70-х годах начали активно проводиться теоретические иссле­дования реляционной модели данных. С появлением персональных ЭВМ реляци­онные модели стали доминировать на рынке информационных систем. Реляционное представление знаний – представление знаний в виде отношений.

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

Логическое проектирование

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

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

1. Удаление связей типа M :N .

2. Удаление сложных связей.

3. Удаление рекурсивных связей.

4. Удаление связей с атрибутами.

5. Удаление множественных атрибутов.

6. Перепроверка связей типа 1:1.

7. Удаление избыточных связей.

1. Удаление связей типа M:N. Если в концептуальной модели присутствуют связи типа M :N (“многие-ко-мно­гим”), то их следует устранить путем определения некоторой промежуточной сущно­сти. Связь типа M :N заменяется двумя связями типа 1:М , устанав­ливаемыми со вновь созданной сущностью.

В качестве примера рассмотрим следующую M :N связь: газета печатает объявления об объектах, сдаваемых в аренду (рис. 6)

Рис. 6. M:N связь

С целью устранения этой связи мы определяем промежуточную сущность ОБЪЯВЛЕНИЕ и создаем две новые связи типа 1:М . В результате связь типа M :N будет заме­нена двумя связями (рис. 7).

Рис. 7. Связи типа 1: M

2. Удаление сложных связей. Сложной называется связь, существующая между тремя и больше типами сущно­стей. Если в концептуальной модели присутствует сложная связь, ее следует устранить с помощью промежуточной сущности. Сложная связь заменяет­ся необходимым количеством бинарных связей типа 1:М , устанавливаемых со вновь созданной сущностью. Например, тройная связь “Сдается внаем” (изображается ромбом) отражает от­ношения, существующие между оформляющим аренду работником компании, зе­мельным участком и арендатором (рис. 8).

Рис. 8. Сложная связь

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

В нашем примере связь “Сдается внаем” можно устранить посредством введения новой слабой сущности с именем Соглашение. Вновь созданная сущность будет связана с исходными сущностями тремя новыми бинарными связями (рис. 9).

Рис. 9. Упрощение сложной связи

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

4. Удаление связей с атрибутами. Если в концептуальной модели присутствуют связи, имеющие собственные атри­буты, они должны быть преобразованы путем создания новой сущности. Например, рассмотрим ситуацию, когда требуется фиксировать количест­во рабочих часов, отработанных временным персоналом каждого из отделений пред­приятия. Связь “Работает в” имеет атрибут с именем “Отработано часов”. Преобразуем связь “Работает в” в сущность с именем “Распределение по отделам”, которой назначим атрибут “Отработано часов”, после чего создадим две новых связи типа 1:М .

5. Удаление множественных атрибутов. Множественными называют атрибуты, которые могут иметь одновременно не­сколько значений для одного и того же экземпляра сущности. Если в концептуальной модели присутствует множественный атрибут, его следует преоб­разовать путем определения новой сущности. Например, для отображения ситуации, когда одно и то же отделение компании имеет несколько телефонных номеров, в концептуальной модели был определен множественный атрибут “Телефонный номер”, относящийся к сущности “Отделение компании”. Этот множественный атрибут сле­дует удалить, определив новую сущность “Телефон”, имеющую единственный простой атрибут “Телефонный номер”, и создав новую связь типа 1.

6. Перепроверка связей типа 1:1. В процессе определения сущностей могли быть созданы две различные сущности, которые на самом деле представляют один и тот же объект в предметной области приложения. Например, могли быть созданы две сущности “Отдел” и “Департамент”, ко­торые на самом деле представляют один и тот же тип объекта. Другими словами, имя “Отдел” является синонимом имени “Департамент”. В подобном случае следует объе­динить эти две сущности в одну. Если первичные ключи объединяемых сущностей различны, выберите один из них в качестве первичного, а другой укажите как аль­тернативный ключ.

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

При устранении избыточности доступа большое значение имеют временные пока­затели. Например, рассмотрим ситуацию, когда необходимо смоделировать связи между сущностями “Мужчина”, “Женщина” и “Ребенок”. Очевидно, что между сущностями “Мужчина” и “Ребенок” имеется два пути доступа: один – через непосредственную связь “ Является отцом” и другой – через связи “ Женат на” и “Является матерью”. На первый взгляд кажет­ся, что связь “ Является отцом” избыточна. Однако это утверждение может оказать­ся ошибочным по двум причинам. Во-первых, отец может иметь детей от предыду­щего брака, а мы моделируем только текущий брак отца (через связь 1:1). Во-вторых, отец и мать могут быть вообще не женаты или отец может быть женат на женщине, которая не является матерью данного ребенка (или же мать может быть замужем за мужчиной, который не является отцом ребенка). Поэтому все сущест­вующие взаимоотношения не могут быть смоделированы без использования связи типа “Является отцом” (рис. 10).

Рис. 10. Связь между сущностями “Мужчина”, “Женщина”, “Ребенок”

Похожая информация.

ЛЕКЦИЯ

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

Основные понятия: Сущность, Свойства, Связи.

Представление сущностей, свойств, связей

9.1. Модель «Сущность-Связь»

Наиболее распространенным средством моделирования предметной области систем, ориентированных на обработку фактографической информации, является модель «сущность-связь» (Entity - Relationship Model - ER М ), впервые предложенная Питером Пин-Шэн Ченом в 1976 г. Эта модель традиционно используется в структурном анализе и проектировании, но, по существу, реализует объектный подход к моделированию предметной области.

Модель “сущность-связь” положена в основу значительного количества коммерческих CASE-продуктов, поддерживающих полный цикл разработки систем баз данных или отдельные его стадии. При этом многие из них не только поддерживают стадию концептуального проектирования предметной области разрабатываемой системы, но и позволяют осуществить на основе построенной их средствами модели стадию логического проектирования путем автоматической генерации концептуальной схемы базы данных для выбранной СУБД, например, схемы базы данных для какого-либо SQL-сервера или объектной СУБД.

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

Семантическую основу ER -модели составляют следующие предположения:

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

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

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

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

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

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

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

На слайде 3 приведенный пример представления сущности, который не является полным и не претендует на точное соответствие какой либо версии построения ER -диаграмм.

ER -модель, как описание предметной области, должна определить объекты и взаимосвязи между ними, т.е. установить связи следующих двух типов:

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

2. связи между объектами, задающие характер и функциональную природу их взаимозависимости.

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

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

Сущность имеет имя , уникальное в пределах модели. При этом имя сущности - это имя типа , а не некоторого конкретного экземпляра.

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

Свойства(слайд 4)

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

Свойство может быть множественным или единичным – т.е. атрибут, задающий свойство, может одновременно иметь несколько значений или, соответственно, только одно. Например, сотрудник может иметь несколько специальностей, но единственное значение «Таб. номер».

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

В некоторых случаях полезно различать базовые и производные свойства. Например, «Поставщик» может иметь свойство «Общее количество поставляемых деталей», которое вычисляется суммированием количества деталей, поставляемых им по проекту.

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

Значения свойств могут быть постоянными - статическими , или динамическими , т.е. меняться со временем. Например, свойство «Таб. номер» является статическим, а «Адрес» - динамическим. Свойство может быть неопределенным , если оно является динамическим, но его текущее значение еще не задано.

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

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

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

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

Если каждый экземпляр сущности участвует, по крайней мере, в одном экземпляре связи, то такое участие этой сущности называется полным (или обязательным ); в противном случае – неполным (или необязательным ).

Количественный характер участия экземпляров сущностей (один или многие) задается типом связи (или мощностью связи ). Возможны следующие типы: «один к одному» (1:1), «один ко многим» (1: М), «многие к одному» (М:1), «многие ко многим» (М:М ) (Слайды 5, 6, 7) .

Следует отметить, что инструмент связей - это средство представления сложных объектов , каждый из которых может рассматриваться как множество некоторым образом взаимосвязанных простых объектов . Деление на простые и сложные объекты, также как и характер взаимосвязи, является условным и определяется особенностям анализа предметной области, т.е. в конце концов – характером использования данных о предметах в решаемых прикладных задачах. При этом с точки зрения, например, конструктора, ДЕТАЛЬ является сложным объектом, а с точки зрения поставщика – простым.

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

Отношение «часть-целое» используются для представления составных объектов . Например, МАШИНЫ состоят из УЗЛОВ, УЗЛЫ состоят из ДЕТАЛЕЙ. Здесь возможны как отношения «один ко многим», так и «многие ко многим».

Отношение «род-вид» - для представления обобщенных объектов . Например, СОТРУДНИКИ подразделяются по профессии на КОНСТРУКТОРОВ, ПРОГРАММИСТОВ, РАБОЧИХ; ПРОГРАММИСТЫ – на ПРИКЛАДНЫХ ПРОГРАММИСТОВ и СИСТЕМНЫХ ПРОГРАММИСТОВ. Иерархические отношения, и, в частности – «родо-видовые », обычно используются как основа классификации объектов по наборам характеристических признаков. Причем «видовые» объекты наследуют свойства «родовых».

Другой широко используемой разновидностью взаимосвязи является агрегирование – объединение простых объектов в сложный по принципу их принадлежности агрегату или их совместного участия в некотором процессе. Агрегирование, рассматриваемое здесь как более общий случай иерархических отношений, объединяет объекты разной природы с единственным общим свойством «совместное участие». Агрегированные объекты именуются обычно отглагольными существительными, например, «Состав »: ПОДРАЗДЕЛЕНИЕ состоит из СОТРУДНИКОВ; «Поставка »: ПОСТАВЩИК поставляет ДЕТАЛИ.

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

Сущность, на основе которой определяются подтипы, называется супертипом . Подтипы должны образовывать полное множество, т.е. любой экземпляр супертипа должен относиться к некоторому подтипу. Иногда для полноты множества надо определять дополнительный подтип, например ПРОЧИЕ.

Подтип наследует свойства и связи супертипа . Например, тип сущности ПРОГРАММИСТ является подтипом сущности СОТРУДНИК. Программисты обладают всеми свойствами сотрудников и участвуют во всех связях, однако обратные утверждения неверны.

Тип сущности, его подтипы, подтипы этих подтипов и т.д. образуют иерархию типов сущности , пример которой приведен на Слайде 8.

9.2. ER- диаграмма

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

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

Сущности .Каждый тип сущности в ER-диаграммах представляется в виде прямоугольника, содержащего имя сущности. В качестве имени обычно используются существительные (или обороты существительного) в единственном числе. Для отражения сущностей слабых типов используются прямоугольники, стороны которых рисуются двойными линиями. Например, в представленной на слайде 9 ER-диаграмме ПОДЧИНЕННЫЙ – сущность слабого типа.

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

Имена ключевых свойств подчеркиваются. Например, свойство «Таб.н омер» сущности СОТРУДНИК.

Контур эллипса рисуется двойной линией, если свойство многозначное. Например, свойство «специальность» сущности СОТРУДНИК.

Контур эллипса рисуется штриховой линией, если свойство производное. Например, свойство «кол-во» сущности ПОСТАВЩИК.

Эллипс соединяется пунктирной линией, если свойство условное. Например, свойство «Ин. я зык» сущности СОТРУДНИК.

Если свойство составное, то составляющие его свойства отображаются другими эллипсами, соединенными с эллипсом составного. Например, свойство «Адрес» сущности СОТРУДНИК состоит из простых свойств «Город», «Улица», «Дом».

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

Стороны ромба рисуют двойными линиями, если это связь сущности слабого типа с сущностью от которой она зависит. Например, связь «Подчинение», связывающая сущность слабого типа ПОДЧИНЕННЫЙ с сущностью СОТРУДНИК, от которой она зависит.

Участники связи соединены со связью линиями. Двойная линия обозначает полное участие сущности в связи с данной стороны. Например, связь «Подчинение», со стороны сущности ПОДЧИНЕННЫЙ.

Связь может быть модифицирована указанием роли. Например, для рекурсивной связи «Состав», указаны роли: «Деталь состоит из …» и «Деталь входит в состав …».

Тип связи указывается индексами «1» или «М» над соответствующей линией. Например, связь «Руководство» имеет тип «один ко многим»: один сотрудник может руководить многими проектами; связь «Участие» имеет тип «многие ко многим»: один сотрудник может участвовать во многих проектах, и в проекте могут участвовать многие сотрудники.

Пример нормализованной формы ER-диаграммы приведен на слайде 10.

Одна из разновидностей модели «сущность-связь» используется в нотации IDEF1Х, входящем в семейство стандартов IDEF.

Графический язык модели и пример диаграммы представлены на слайде 11 .

Необязательные связи между сущностями Отдел и Сотрудник, Сотрудник и Подчиненный имеют мощность «один ко многим» (конец связи «многие» обозначен жирной точкой), а обязательная связь между сущностями Сотрудник и Проект имеет мощность «многие ко многим».

Графические элементы основных нотаций модели «сущность-связь» представлены на слайде 12 .

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

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

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

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

2.1 Семантические модели и когнитивный аспект

2.1.1 Семантические модели данных

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

Но если в базе хранятся только данные, то, как же хранятся смыслы? Прежде всего, смыслы -это тоже данные, связанные с теми данными, смысл которых они представляют.

Выделим следующие виды смыслов:

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

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

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

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

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

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

Детально семантика данных будет рассмотрена в лекции "Семантика баз данных" учебника.

Самая известная семантическая модель "сущность-связь" ("entity-rela-tionship" - ER) была предложена Питером Пин Шен Ченом (Peter Chen) в 1976 году.

2.1.2 Когнитивный аспект

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

2.1.3 Уровни модели

В соответствии с подходом Питера Чена, изложенным в основополагающей работе по диаграммам "сущность-связь", выделим четыре уровня представления моделей данных, несколько изменив их определения:

1. Информация об объектах и связях предметной области (ПО), излагаемая в терминах ПО (концептуальная модель).
2. Структурированная информация о ПО, излагаемая в терминах информационных систем (логическая модель).
3. Структуры данных, не зависящие от способа доступа, то есть не связанные со структурами данных, поиском, индексацией и т. д. (физическая модель).
4. Структуры данных, зависящие от способа доступа (модель аппаратного уровня).

Забегая вперед, заметим, что реляционная модель относится к уровням 2 и 3. Сетевая и иерархическая модели, в том виде как они существовали 20 лет назад, работают в основном на уровне 3 и 4. UML -это уровни 1, 2 и 3, но UML далеко выходит за рамки описания данных. Модель "сущность-связь" работает на уровнях 1 и 2.

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

Наиболее распространенным средством моделирования данных (предметной области) является модель «сущность-связь» (ERM). Она была впервые введена Питером Ченом в 1976 г. Базовыми понятиями ERM являются сущность, связь и атрибут.

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

Каждая сущность должна иметь наименование, выраженное существительным в единственном числе. Примерами сущностей могут быть такие классы объектов, как «Поставщик», «Сотрудник», «Заказ». Каждая сущность в модели изображается в виде прямоугольника с наименованием (рис. 2.23).

Рис. 2.23. Графическое представление сущности

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

Экземпляр сущности - это конкретный представитель данной сущности. Например, экземпляром сущности «Сотрудник» может быть «Сотрудник Иванов».

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

· иметь уникальное имя; к одному и тому же имени должна всегда применяться одна и та же интерпретация; одна и та же интерпретация не может применяться к различным именам, если только они не являются псевдонимами;

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

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

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

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

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

Примерами атрибутов сущности «Сотрудник» могут быть такие атрибуты, как «Табельный номер», «Фамилия», «Имя», «Отчество», «Должность», «Зарплата» и т.п.

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

Рис. 2.24. Сущность с атрибутами

Виды атрибутов :

· простой - состоит из одного элемента данных;

· составной - состоит из нескольких элементов данных;

· однозначный - содержит одно значение для одной сущности;

· многозначный - содержит несколько значений для одной сущности;

· необязательный - может иметь пустое (неопределенное) значение;

· производный - представляет значение, производное от значения связанного с ним атрибута.

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

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

Рис. 2.25. Сущность с уникальным идентификатором

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

Степенью связи называется количество сущностей, участвующих в связи. Связь степени 2 называется бинарной , степени N- N-арной . Связь, в которой одна и та же сущность участвует в разных ролях, называется рекурсивной , или унарной . Один из возможных вариантов графического изображения связи показан на рис. 2.26.

Рис. 2.26. Обозначение сущностей и связи

Пары чисел на диаграмме отражают две важные характеристики связи - мощность связи (второе число) и класс принадлежности (первое число).

Мощностью связи называется максимальное число экземпляров сущности, которое может быть связано с одним экземпляром данной сущности. Мощность связи может быть равна 1, N (любое число) и может быть конкретным числом. Мощности связи на рис. 2.26 означают: каждый сотрудник может работать не более чем в одном отделе, а в каждом отделе может работать любое число сотрудников.

Класс принадлежности характеризует обязательность участия экземпляра сущности в связи. Класс принадлежности может принимать значение 0 (необязательное участие - экземпляр одной сущности может быть связан с одним или несколькими экземплярами другой сущности, а может быть и не связан ни с одним экземпляром) или 1 (обязательное участие - экземпляр одной сущности должен быть связан не менее чем с одним экземпляром другой сущности). Классы принадлежности на рис. 2.26 означают: каждый сотрудник обязательно работает в каком-либо отделе, а в некоторых отделах может и не быть сотрудников.

Связь может иметь один из следующих трех типов (в зависимости от значения мощности):

1. Один-к-одному (обозначается 1:1), показана на рис. 2.27.

Рис. 2.27. Связь типа 1:1

2. Один-ко-многим (обозначается 1:п), показана на рис. 2.26.

3. Многие-ко-многим (обозначается m:n), показана на рис. 2.28.

Рис. 2.28. Связь типа min

Модель данных «сущность-связь» ввел в 1976 г. П. П. Чен. Она имеет много общего с иерархической и сетевой моделями данных и в силу своей ориентации на процесс проектирования может рассматриваться как обобщение и развитие ранее рассмотренных моделей. Описываемая модель допускает непосредственное представле­ние связей типа М: N.

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

Каждая сущность принадлежит к некоторому классу или ему соответствует некоторый тип. Между сущностями имеются связи, за которыми пользователь закрепляет какой-то класс (тип). Таким образом, класс сущностей и класс связей определяют множества конкретных объектов и связей между ними. Заметим, что некоторая сущность может принадлежать более чем к одному классу (например, поставщик может одновременно быть и потребителем). В каждый момент времени состояние связи S между классами сущностей E 1 , Е 2 ..., Е n определяется отношением между множествами DOM E 1 , DOM E 2 , ..., DOM Е n , где DOM Е i , i = - множество объектов типа Е i .

Множество связей в модели «сущность - связь» можно представить в виде математического отношения п классов объектов:

где е i - сущность, принадлежащая множеству сущностей Е i , кортеж <e 1 e 2 ... е п > - связь из множества связей R. Необязательно, чтобы все E i , на которых определено R, были различными. Совокупность сущностей и классов связей образует верхний уровень модели.

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

Графически модель «cущность - связь» представляется в виде схемы, в которой каждому классу объектов соответствует прямоугольник, а классу связей - шестиугольник (рис. 2.7). Под прямоугольником и шестиугольником указываются имена атрибутов сущностей и связей.

Рис. 2.7. Графическое представление модели «сущность-связь»:

а) класс сущностей; б) класс связей;

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

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

типы связей между классами задаются парами (1:1, 1: N, N: 1, М: N). Когда значения М и N уточнены, берется максимальное значение;

одна связь может относиться ко многим сущностям и одна сущность может иметь много связей. В случае связей типа 1:1, 1: N, N: 1 не всегда нужно указывать имя связи.

Рассмотрим пример представления концептуальной схемы БД с помощью модели «сущность-связь» (рис. 2.8). Пусть имеются следующие приложения: управление поставками, складом, производством и договорами. Эти приложения могут использовать такие классы сущностей: ПОСТАВЩИК (поставщики), БАЗ-ДЕТ (базовые детали), ИЗД-УЗЕЛ (изделия и узлы), ДОГОВОР (договоры), СЛУЖАЩИЙ (служащие), ОТДЕЛ (отделы).

Рис. 2.8. Пример схемы модели «сущность-связь»

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

ВЫБРАТЬ - позволяет выбрать поставщика базового продукта в зависимости от условий продажи и поставки (эти условия задаются на схеме);

СБОРКА-БД - указывает базовые детали (материалы), которые непосредственно используются для производства изделия или узла, а также их число;

СБОРКА-УЗЕЛ - указывает узлы, непосредственно входящие в другие узлы или изделия, а также их число;

ПОСТ-БАЗ - связывает в договоре поставщиков с базовыми деталями;

НАЗНАЧИТЬ - характеризует в договоре изделия и узлы;

ОТВЕЧАЕТ - указывает ответственного за договор;

УЧАСТВУЕТ - связывает договор и людей, которые участвуют в его реализации;

РАБОТАЕТ - связывает отдел и людей, которые в нем работают;

РУКОВОДИТ - указывает руководителя данного отдела.

Схема модели «сущность-связь» может быть описана в виде, представленном на рис. 2.8.

Классы сущностей:

E1/ПОСТАВЩИК [НОМ-ПОСТ, ФАМ-ПОСТ, АДРЕС];

Е2/БАЗ-ДЕТ [НОМ-БДЗ-ДЕТ, НАИМ-БАЗ-ДЕТ, КОЛИЧ-НА-СКЛАДЕ, МИНИМ-КОЛИЧ];

Е3/ДОГОВОР [НОМ-ДОГ, ДАТА];

Классы связей:

L 1/ПОСТ-БАЗ L2 /ВЫБРАТЬ L3 /СБОРКА-БД

[ПОСТАВЩИК, БАЗ-ДЕТ, ДОГОВОР];

[ПОСТАВЩИК, БАЗ-ДЕТ: ЦЕНА, СРОК-ПОСТ];

[БАЗ-ДЕТ, ИЗД-УЗЕЛ: КОЛИЧ-БД];

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

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

1. Связь может относиться к нескольким классам сущностей, например, связь ПОСТ-БАЗ соединяет классы сущностей ПОСТАВЩИК, БАЗ-ДЕТ, ДОГОВОР.

2. Связь может многократно относиться к одному классу сущностей, например связь СБОРКА-УЗЕЛ.

3. Многие связи могут относиться к одному классу сущностей, например связи РАБОТАЕТ и РУКОВОДИТ между сущностями СЛУЖАЩИЙ и ОТДЕЛ.

4. Модель отображает различные связи типа 1:1, 1: N , М: N.

5. Наличие двух классов сущностей для деталей БАЗ-ДЕТ и ИЗД-УЗЕЛ позволяет управлять: поставками деталей и находить поставщиков, опираясь на класс БАЗ-ДЕТ; процессом производства изделий, используя класс ИЗД-УЗЕЛ.

6. Два класса сущностей БАЗ-ДЕТ и ИЗД-УЗЕЛ имеют общие и специфические для них атрибуты. Наличие общих атрибутов приводит к некоторой избыточности данных. Специфические атрибуты требуются областью применения объектов.

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

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

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

Рис. 2.9. Схема прямой и обратной связей

Например, в связи между сущностями СЛУЖАЩИЙ и ОТДЕЛ (рис. 2.9) прямая связь РАБОТАЕТ указывает на то, что служащий работает только в одном отделе; обратная связь СОДЕРЖИТ указывает на то, что отдел содержит не менее одного служащего (обычно много служащих). Другими словами, связь L между двумя классами сущностей А и В указывает на то, что сущность А связана, как минимум, с M и, как максимум, с N сущностями В. Иногда N может быть не определено.

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

Реляционная модель

Основные понятия

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

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

2. Все столбцы в таблице однородные. Это означает, что элементы столбца имеют одинаковую природу. Столбцам присвоены имена;

3. В таблице нет двух одинаковых строк;

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

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

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

Приведем ряд терминов, применяющихся в реляционной модели:

· Отношением (relation) называется двумерное множество – таблица, удовлетворяющая вышеперечисленным требованиям;

· Атрибут – это свойство, характеризующие объект. В структуре таблицы каждый атрибут имеет имя и ему соответствует заголовок некоторого столбца таблицы. Количество атрибутов называется степенью отношения ;

· Кортежом (tuple) называется строка таблицы. В общем случае кортежи представляют собой набор пар <атрибут>, <значение>. Каждое значение должно быть атомарным, т.е. не может быть многозначным или составным. Следовательно, многозначные и составные атрибуты в реляционной модели не поддерживаются. Количество кортежей называется кардинальным числом ;

· Домен представляет собой множество всех возможных значений определенного атрибута отношения.

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

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

Свойством уникальности. Нет одинаковых кортежей с теми же значениями потенциальных ключей;

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

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

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

Исходя их вышеприведенных понятий, математически отношение можно описать следующим образом. Пусть даны n множеств Dl, D2, D3,..., Dn . Тогда отношение R есть множество упорядоченных кортежей<d1 , d2 , d3 ,..., dn >, где dk ÎDk , dk – атрибут, a Dk – домен отношения R.

В середине 70-х годов инженером IBM Коддом (Codd) была предложена модель данных, основанная на математических операциях исчисления отношений и реляционной алгебре. Основной структурной единицей этой модели являлось отношение (relation). Поэтому такая модель данных получила название реляционной. Коддом был также разработан язык манипулирования данных, представленных в виде отношений. Он предложил два эквивалентных между собой по своим выразительным возможностям варианта языка манипулирования данными:

5. Реляционная алгебра . Это процедурный язык, так как отношение, являющееся результатом запроса к реляционной БД, вычисляется при выполнении последовательности реляционных операторов, применяемых к отношениям. Операторы состоят из операндов, в роли которых выступают отношения, и реляционных операций. Результатом реляционной операции является отношение. Операции реляционной алгебры можно разделить на две группы. Первую группу составляют операции над множествами, к которым относятся операции объединения, пересечения, разности, деления и декартова произведения. Вторую группу составляют специальные операции над отношениями: проекция, выборка и соединение.

6. Реляционное исчисление . Это непроцедурный язык описательного или декларативного характера, содержащий лишь информацию о желаемом результате. Процесс получения этого результата скрыт от пользователя. К языкам такого типа относятся SQL и QBE. Первый основан на реляционном исчислении кортежей, второй – на реляционном исчислении доменов.

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

Отношения

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

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

Помимо элементов система включает в себя связи, отношения между ними. Так, числа а и b могут быть равны (а = b ) , не равны (а ≠ b ), а больше или равно b (а ≥ b ); фигуры А и В могут быть конгруэнтны (А = В ), А может содержать В (A B ); две прямые А и В могут быть параллельны (А || В ), перпендикулярны (). Студент а относится (принадлежит) к множеству А (студенты кафедры).

Все перечисленные отношения касаются двух объектов и поэтому называются бинарными отношениями или просто отношениями . Отношения между тремя объектами называются тернарными , а между n объектами - n-арными . Так, тернарным является отношение между объектами ЗАКАЗЧИК, ПОСТАВЩИК, ТОВАР.

Бинарным отношением R между множествами А и В (обозначается R (A , В )) называется любое множество упорядоченных пар (а , b ), где а А , b В . Если (а ,b ) R , то говорят, что а находится в отношении R к b , и записывают aRb , Поскольку множество упорядоченных пар (а , b ), где а A , b В , является декартовым произведением A ×В , то бинарным отношением будет любое подмножество этого произведения.

Пример 2.1. Возьмем множество поставщиков и множество предлагаемых товаров. Любое подмножество связей ПОСТАВЩИК - ТОВАР является бинарным отношением.

Пример 2.2. Пусть даны множества A = {1, 2, 3} и В = {2, 3, 4, 5, 6}. Декартово произведение A ×В - это множество пар:

(1, 2), (1, 3), …, (1, 6),

(2, 2), (2, 3), …, (2, 6),

(3, 2), (3, 3), …, (3, 6).

Построим бинарное отношение R , у которого первый элемент является делителем второго. Получим следующее бинарное отношение: R ={(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3,6)}.

Пример 2.3. Пусть Ольга (О), Павел (П), Иван (И) - имена детей в семье. Отношением а - брат b будет:

R = {(П, О), (И, О), (П, И), (И, П)}.

В отношении R (A , В ) множество А , т.е. совокупность всех первых координат, называют областью определения отношения R , а множество B , т. е. множество всех вторых координат, - областью его значений . Так, для примера 3.3 область определения - множество {П, И}, а область значений- множество {О, П, И}.

Дополнением к бинарному отношению R будем называть отношение , которое определяет подмножество

= (A ×B )\R ,

т.е. a b тогда и только тогда, когда {a , b ) R . Так, для примера 2.2

= {(2, 3), (2, 5), (3, 2), (3, 4), (3, 5)}.

Бинарные отношения можно задавать различными способами: матрицами, графами, таблицами (сечениями). Отношение R (A , В ), где А = {а 1, а 2 , ..., a m }; B = {b 1, b 2 , ..., b n }, можно представить матрицей смежностей, строки которой соответствуют элементам A , а столбцы - элементам В ; на пересечении а i -й строки и b j -го столбца записана 1, если a i Rb j , и 0, если a i Rb j . Матрицы смежности для отношений R и для примера 2.2 имеют вид

R

Бинарное отношение R (A , В ) можно представить в виде ориентированного графа. Элементы множества А и В - вершины графа, причем ребром соединяются те и только те элементы а А , b В , для которых (a , b ) R. Так, в виде графа на рис. 2.10 представлено отношение для примера:

Рис. 2.10. Представление отношения R в виде графа

Пусть даны три множества А , В , С и два отношения R (A , В ) и S (B , С ). Композицией , или умножением , отношений R и S называют бинарное отношение RS (или R *S ) между элементами множеств А и С такое, что aRSc тогда и только тогда, когда существует хотя бы один элемент b В , при котором истинны aRb и bSc .

Пример 2.4. Рассмотрим множества

А = {а 1, а 2 , а 3 }, В = {b 1 , b 2 , b 3 }, С = {с 1 , c 2 , c 3 , c 4 }

и отношения

R (A , B ) = {(a 1 , b 2), (a 2 , b 1), (a 2 , b 3), (a 3 , b 4)},

S (B , C ) = {(b 1 , c 2), (b 2 , c 1)}.

Умножение отношений RS можно представить в виде графа (рис. 2.11.).

Умножение бинарных отношений ассоциативно, т. е. (RS )T = R (ST ). Пусть даны отношения R (A , В ), S (B , С ) и Т (С , D ). Тогда a (RS )Td = aR (ST )d , т.е. элемент а A тогда и только тогда находится в каждом из отношений (RS )T и R (ST ) к элементу d D , когда существуют такие элементы b В и c С , что aRb , bSc , cTd . Умножение отношений, однако, не является в общем случае коммутативным (перестановочным), т.е. RS ≠SR . Эта операция имеет место только в частных случаях (в этом случае говорят, что R и S перестановочны).

Пример2.5. Пусть даны множества

A = {a, b}, B = {a, b, c}, C = {b, c}

и отношения R (A , В ) = {(а , b ), (b , с )}, S (B , C ) = {(b , с ), (а , b )}. Тогда aRSc = aSRc для любых а А и c С .

Умножение k отношений R на множестве H , т.е. k -я степень R , обозначаемая R k , рекурсивно определяется следующим образом:

1) aR l b истинно, когда истинно aRb ;

2) aR i b для i >0 истинно, когда существует такое с А ,
что aRc и cR i - l b истинны.

Пусть имеем aR 3 b . Тогда существует такое с 1, что aRc 1 и c 1 R 2 b . Для c 1 R 2 b найдется такое с 2 , что c 1 Rc 2 и c 2 Rb , т. е. для аR 3 b есть такое с 1, с 2 А , что аRс 1 , c 1 Rc 2 и с 2 Rb .

Пусть в одном или нескольких множествах даны от­ношения R i (i пробегает множество индексов I ) и S . Тогда

, (2.1)

Согласно a [(UR i )S ]с существует такой элемент b , что a (Ri )b и bSc . А это, в свою очередь, равносильно существованию такого индекса i 0 , что a R b и bSc , т.е.

Рис. 2.11.Представление операции умножения отношений RS в виде графа

a(R S) c и поэтому a (R i S )c . Заметим, что в равенствах (3.1) объединение нельзя заменить пересечением. Из (3.1) следует, что если даны отношения R , R " и S , причем R R ", то

RS R "S , SR SR ". (2.2)

Действительно, так как R R ’ то R R " = R ", что приводит к равенству (R R ’) S = RS R ’S = R ’S , которое равносильно включению RS R "S .а, если для функционального отношения R симметричное ему отношение тоже функционально.

Всякому отношению R (A , В ) можно поставить в соответствие функцию f (x ), если его сечение по каждому х А либо пусто, либо есть элемент множества В . Если f (x ) всюду определена, т. е. область определения функции совпадает с А , то говорят, что отношение R (A , В ) есть отображение множества А в В . Функциональное отношение R (A , В ) вызывается отображением А в В , если для каждого а A существует один и только один элемент

Рис. 2.12. Представление функционального отношения R(A, В) в виде графа

b B , удовлетворяющий отношению aRb . Элемент b называется образом элемента а и обозначается aR , а элемент а - прообразом элемента b при отображении R . Совокупность всех прообразов элемента b в А при отображении R называется полным прообразом этого элемента в А .

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

определяет отображение множества {1, 2, 3, 4} в множество {2, 5, 1, 4}. При этом 1R = 2, 2R = 5, 3R =1, 4R = 4.

Пусть Р - отображение А в В , Q - отображение В в С . Умножение отображения PQ будет отображением А в С , и для любого x ?А справедливо x (PQ ) = (xP )Q . Действительно, пусть x (PQ )=c . Тогда для некоторого у В имеем хРу и yQc , откуда хР = у и поэтому с = (xP )Q . Обратно, из (xP )Q следует x (PQ ).

Умножение отображений, заданных таблицами, покажем на примере:

Отображение R называют сюръективным (сюръекцией ) или отображением множества А на множество В , когда каждый элемент b ?В имеет хотя бы один прообраз из А .

Пример 2.6. Пусть А и В - множества вещественных чисел. Отображением (сюръективным) А на В может быть функция, определенная формулой х → Зх + 5, т. е. х переходит в y = 3x + 5.

Функция х →у =х 2 определяет отображение множества A в Б , которое не является сюръективным, так как отрицательные числа из В не являются образами элементов из А .

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

Взаимно однозначное отображение, для которого R всюду определено, называют инъективным (инъекцией ).

Пример 2.7. Пусть А - множество действительных чисел, В - множество положительных действительных чисел. Отображение х →у = е х является взаимно однозначным, так как каждому у соответствует х = ln y . Таким образом, имеем инъективное отображение, обратным для которого будет отображение у →х =ln y .

Взаимно однозначное отображение R между элементами одного множества, для которого R и R - l всюду определены, называется отображением на себя или биективным отображением . Биективное отображение является одновременно сюръективным и ииъективным.

При отображении некоторого множества самого в себя говорят, что отображение aRb переводит точку а в точку b . При aRa точку а называют неподвижной точкой отображения R . Если все точки множества A при отображении неподвижны, то отображение называют тождественным и обозначают Е А . Очевидно, что Е -1 =Е и для любого отображения R RE =ER = R . При задании отображения в себя с помощью сечений в нижней строке таблицы будут такие же элементы, как и в верхней (возможно, в другом порядке), и каждый из них встречается один и только один раз:

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

R

Представление отображения в себя в виде графа состоит из циклов (конечных или бесконечных).