2.3.3. Основные математические понятия

Пусть имеются множества А и В. Отношение А R В указывает на связь между отдельными элементами этих множеств. Различают рефлексивные отношения А R А (связи между элементами одного и того же множества), транзитивные (опосредованные связи) и т. д. На практике используется некоторая смысловая интерпретация связей между множествами и кардинальных чисел этих связей (т. е. числа элементов в экземпляре связи). Множества могут соответствовать атрибутам или типам записей. Связи могут быть функциональными, т. е. удовлетворяющими определению математической функции. Кардинальные числа связей используются также для определения типа отображения между парами множеств. Существуют отображения один-к-одному (1:1), один-ко-многим (1 : М) и многие-ко-многим (М :N).

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

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

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

б) служащие могут иметь дома;

в) некоторые служащие имеют подчиненных;

г) поставщики поставляют (продают) детали;

д) тип дома, в котором живет служащий, можно определить по его стоимости.

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

Рис. 1

Исследуя типы связей на рис. 1, можно сделать следующие замечания:

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

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

Область понятий		Область информационных моделей
Сущности	Свойства	Типы записей (список атрибутов)
Служащие	Номер страхового свидетельства, номер служащего, имя, зарплата	Служащие (НОМЕР-СТРАХОВОГО-СВИДЕТЕЛЬСТВА, НОМЕР-СЛУЖАЩЕГО ИМЯ, ЗАРПЛАТА)
Дома	Номер участка, тип. стоимость	Дома (НОМЕР-УЧАСТКА, ТИП, СТОИМОСТЬ)
Поставщики	Номер поставщика, имя, город	Поставщик (НОМЕР-ПОСТАВЩИКА, ИМЯ-ПОСТАВЩИКА, ГОРОД)
Детали	Номер детали, описание детали, наличие деталей	Детали (НОМЕР-ДЕТАЛИ, ОПИСАНИЕ-ДЕТАЛИ, НАЛИЧИЕ-ДЕТАЛЕЙ)

3. На рис. 1,а приведен пример отображения 1:1 между соответствующими множествами. Это пример взаимно однозначного отображения.

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

5. Из рис. 1,б видно, что некоторые служащие могут руководить другими служащими и что каждый служащий имеет руководителя (у Е₂ есть подчиненный Е₁, который также является руководителем). Исключение составляет президент компании, руководящий сам собой (или руководимый советом директоров!).

6. Из рис. 1,г видно, что все поставщики являются «активными», т. е. все они поставляют детали. При этом каждый поставщик может поставлять несколько деталей, а некоторые детали могут поставляться несколькими поставщиками.

7. На рис. 1,д показано, что стоимость дома определяет его тип.

На рис. 2 приведено изображение межсущностной связи (рис. 2,б), использующее диаграмму сущность/связь (Entity/Relationship - E/R)

Рис. 2

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

Пусть D и R множества. Математическая функция f: D R есть отображение множества D на множество R. Множество D называется областью определения, а множество R — областью значений функции f.

Функция является подмножеством декартова произведения (D  R) множеств D и R причем если [х, у] и [х, z] упорядоченные пары в f, то у и z должны быть равны друг другу, т. е. элемент из D всегда отображается в единственную точку в R. Функция f называется всюду определенной или полной, если {х | [х, у]  f} = D, т. е. каждому элементу из D соответствует некоторый элемент в R. Функция f называется частичной, если f определена на некотором подмножестве D. Если исследовать связи на рис. 1, то можно сделать следующие выводы:

1. На рис. 1,а связь между атрибутами НОМЕР-СТРАХО-ВОГО-СВИДЕТЕЛЬСТВА и НОМЕР-СЛУЖАЩЕГО является функциональной и всюду определенной. Данное свойство выполняется для обоих направлений связи. Таким образом, каждое значение первого атрибута отображается на единственное значение второго, и наоборот. Это свойство отображения 1:1.

2. На рис. 1,в свойством функциональности обладает только отображение «руководимый», обратное к отображению «руководит», так как отображение множества служащих на множество руководителей относится к типу N : 1.

3. На рис. 1,д показано всюду определенное функциональное отображение стоимостей домов на их типы.

Для всех функциональных связей справедливо, что атрибут (или сущность), являющийся областью определения, однозначно определяет атрибут (или сущность) области значений. (Например, «если вы назовете стоимость дома, то можно однозначно определить его тип».) Говорят, что атрибут области определения определяет атрибут области значений, или иначе — что последний зависит от первого. Это приводит к понятию функциональной зависимости в теории баз данных. Функциональные зависимости играют большую роль в проектировании баз данных. Армстронг выделил некоторые свойства функциональных зависимостей и сформулировал их в виде аксиом. Эти аксиомы называются также правилами вывода, так как, используя их, можно вывести или получить из известных функциональных зависимостей ряд других. Это важно при проектировании и исследовании баз данных. Были сформулированы следующие правила вывода:

Основные правила

1. Рефлексивность. Пусть задано множество Х и У  Х, тогда Х  Х или Х  У. Это тривиальные функциональные зависимости, означающие, что множество определяет любое свое подмножество.

2. Транзитивность. Если Х  У, У  Z, то Х  Z.

3. Дополнительность. Если Х  У и Х  W, то W  Y

Следствия из основных правил

1. Аддитивность (объединение). Если Х  Y и W  Z, то ХW  УZ, или X  Y и X  Z, то Х  YZ.

2. Проективность (декомпозиция). Если Х  YZ, то Х  Y и X  Z

3. Псевдотранзитивность. Если Х  У и YW  Z, то XW  Z.

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

ИЕРАРХИЧЕСКИЕ СИСТЕМЫ

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

Рис.1

На рис. 1,в приведено несколько экземпляров иерархических записей базы данных, соответствующих дереву определений. Экземпляр дерева базы данных не обязательно должен содержать все свои сегменты. (Примерами являются первое дерево R₁ и предпоследнее дерево R_n-1. При необходимости можно добавлять или удалять экземпляры типов записей в соответствии с требованиями приложения. Предположим, что типы записей А, В, С, D и Е интерпретируются как типы записей «Курс», «Предварительная регистрация», «Семестр», «Преподаватель» и «Студент». Информация о некотором курсе может отсутствовать (например, R_n-1), либо для курса может быть известна лишь предварительная регистрация (R₁). В качестве упражнения читатель может предложить содержательную интерпретацию оставшихся экземпляров деревьев базы данных. (Предположите, что распределение преподавателей по курсам в различные семестры и предварительная регистрация студентов на курсы проводятся независимо, а решение о необходимости чтения курса принимается позже.)

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

НЕКОТОРЫЕ СВОЙСТВА ИЕРАРХИЧЕСКИХ СИСТЕМ

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

Рис.2

В иерархических СУБД способ реализации операции поиска ориентирован на древовидную структуру. В связи с этим поиск начинается с корня и продолжается в направлении порожденных узлов. Если в конкретной реализации кроме последовательного просмотра всего дерева отсутствует какой-либо способ прямого доступа к конкретному типу записи, то положение узла в дереве имеет важное значение для доступа к нему. В базе данных «поставщики — детали» имеется отображение М : N между типами записей. Если не известен наиболее часто используемый тип записи, то в целях общности и гибкости необходимо при наличии ресурсов памяти хранить оба варианта (рис. 2,б и 2,в). В противном случае должен быть выбран один из вариантов, что может вызвать трудности. Так, в случае 2,б гораздо легче ответить на вопрос о всех поставляемых данным поставщиком деталях, чем на вопрос о всех поставщиках, поставляющих данную деталь (что легко сделать без просмотра всех листьев в случае 2,в). Следовательно, в иерархических СУБД реализация сложных связей требует дублирования данных и/или больших затрат на поиск.

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

МОДЕЛИ ДАННЫХ

СЕТЕВЫЕ СИСТЕМЫ

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

Приведенное определение является слишком общим для целей реализации, так как в нем отсутствуют ограничения на способы соединения типов записей в схеме базы данных. Рабочая группа по базам данных (РГБД) ассоциации КОДАСИЛ (CODASYL) сформулировала некоторые ограничения на сетевую модель данных, рассматриваемые в следующем разделе.

Рис.3.