Структуры данных

Структуризация данных базируется на использовании концепций типа «агрегация» и «обобщение». Например, в файловых систе­мах, которые реализуют модель типа «плоский файл» с понятий­ным базисом из четырех основных типов логических структур данных: а) поле -наименьшая поименованная единица данных; б) запись -поименованная совокупность полей; в) файл -поименованная совокупность экземпляров записей одного типа; г) набор файлов или библиотека -поименованная совокупность файлов обрабатываемых в системе. Агрегация используется для композиции полей в запись, а обобщение -для представления множества экземпляров записей одного типа одной общей структурой более высокого уровня -файлом. В ряде систем допускается объединение в файл экземпляров записей нескольких заданных типов. Обобщение также используется для выборки из файла прикладной программой некоторого подмножества экземпляров записей, удовлетворяющих заданному критерию выборки. Существует большое количество терминов, используемых для начения определенных типов структур данных. Широко распространена терминология, предложенная КОДАСИЛ- Ассоциация по языкам систем обработки данных

Элемент данных - наименьшая поименованная единица дан­ных (аналог поля в файловых системах). Элемент данных -это минимальная единица данных, к которой СУБД может адресоваться непосредственно и с помощью которой выполняется по строение всех остальных структур. Элементы данных обычно не пользуются для представления отдельных элементарных свойств объектов, например ТАБЕЛЬНЫЙ-НОМЕР, ШИФР-ДЕТАЛИ ГОД-РОЖДЕНИЯ и т. п.

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

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

Различают агрегаты типа «вектор» и типа «повторяющаяся группа» Агрегат, повторяющаяся компонента которого является простым элементом данных, называется вектором.. Например, агрегат ЗАРАБОТНАЯ-ПЛАТА, в котором экземпляр элемента данных может повториться до 12 раз (за каждый месяц года). Агрегат, повторяющаяся компонента которого представлена со­вокупностью данных, называется повторяющейся группой. В пов­торяющуюся группу могут входить отдельные элементы данных, векторы, агрегаты или другие повторяющиеся группы. Например, агрегат ЗАКАЗ-НА-ПОКУПКУ имеет в своем составе повто­ряющуюся группу ПАРТИЯ-ТОВАРА. Максимальное количество экземпляров для вектора и для повторяющейся группы ограничено и задается при спецификации схемы записи.

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

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

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

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

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

Элемент данных соответствует определению, приведенному в терминологии КОДАСИЛ.

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

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

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

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

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

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

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

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

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