Системантика

Вид материала

Монография

Содержание 1. Представление данных Пример объектно-характеристической таблицы

1. Представление данных

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

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

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

Все структуры данных могут быть разделены на иерархические, неиерархические и смешанные.

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

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

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

Смешанные структуры являются комбинацией иерархических и неиерархических структур.

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

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

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

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

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

Группа, содержащая атрибуты и другие группы, называется составной (рис. 39).




Рис. 38. Схема простой группы




Рис. 39. Схема составной группы


Простая группа служит средством обращения к набору атрибутов.

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

Группы могут быть повторяющимися и неповторяющимися. Повторяющиеся допускают переменное число экземпляров.

Следующим элементом структуры является групповое отношение, под которым понимается отношение соответствия между двумя множествами групп. Группы из первого множества называются родительскими, а из второго – зависимыми. Групповое отношение в конкретных приложениях отражает отношения между объектами, которым эти группы соответствуют (см. рис. 40, 41).

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


имена служащих ← М номер отдела


Рис. 40. Групповые отношения




Рис. 41. Схема группового отношения и экземпляр схемы


Существует три главных типа статей:

1. статья-группа;
   
2. статья-дерево;
   
3. статья-сплетение.
   

Статья-группа содержит единственную составную группу. Иерархические отношения между элементами устанавливаются посредством вложений групп. Схема статьи-группы совпадает со схемой группы, определяющей статью (рис. 42).



Рис. 42. Схема статьи-группы


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



Рис. 43. Схема статьи-дерева


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

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



Рис. 44. Схема файлов с несколькими схемами статей


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

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

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

Ранг дерева равен числу уровней (4);

момент – числу узлов (5);

вес – числу листьев (15).

Древовидная структура имеет вид, представленный на рис. 45.




Рис. 45. Древовидная структура


Двоичное дерево приведено на рис. 46. Схема и экземпляр схемы двоичной структуры показаны на рис. 47, экземпляр схемы бинарной древовидной структуры – на рис. 48.

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

Пример базы данных некоторого учебного процесса показан на рис. 51, 52.



Рис. 46. Двоичное дерево




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



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




Рис. 49. Сбалансированные деревья




Рис. 50. Несбалансированные древовидные структуры



Рис. 51. Иерархическая логическая схема



Рис. 52. Экземпляр иерархической схемы


Сетевой структурой называется такая структура, в которой любой элемент может быть связан с любым другим элементом и порожденный элемент имеет более одного исходного (см. рис. 53, 54, 55, 56).

Различают простые и сложные сетевые структуры (см. рис. 57, 58). Любую сетевую структуру можно представить в виде древовидной структуры путем введения избыточности (см. рис. 59).



Рис. 53. Сетевая структура с указанием направления отношений





Рис. 54. Сетевая структура без указания направления отношений




Рис. 55. Сетевая структура с четырьмя исходными элементами




Рис. 56. Типичная сетевая структура




Рис. 57. Простые и сложные сетевые структуры




Рис. 58. Сложная сетевая структура из двух типов записей




Рис. 59. Представление сложной сетевой структуры из двух типов записей в виде сумы древовидных структур


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

Таблица 1

Пример объектно-характеристической таблицы

Шифр изделия	Наименование изделия	Единица измерения	Цена изделия	Наименование поставщика
08451	Станок 32М	шт.	3585	«Станколит»
10581	Станок 15К	шт.	51320	«Инструмент»
48391	Двигатель 5А	шт.	485	«Электросила»
38549	Автокран ЭМБ	шт.	12540	ЗИЛ

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

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

Порядок отношения равен длине кортежа, измеряемой числом элементов, входящих в кортеж.

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




Рис. 60. Пример декартова произведения