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

Способы структуризации данных

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

При структуризации данных применяются три типа абст­ракции - идентичность, обобщение и агрегация.

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

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

Рис.10.1. Пример иерархии обобщений

Агрегация позволяет рассмотреть связь между элементами данных как новый элемент более высокого уровня. Например, связь между сущностями СТУДЕНТ, ДИСЦИПЛИНА, ПРЕПОДАВАТЕЛЬ, ОЦЕНКА, имеющая смысловое описание «сту­дент по фамилии___________________ получил на экзамене по дисциплине_____ ___ у преподавателя по фами­лии __________ оценку ____», может быть представлена агрегатированным элементом ЭКЗАМЕН:

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

32. Типы структур данных. Понятия: агрегат данных, запись, база данных. (Тема 10, стр. 70).

Типы структур данных

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

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

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

Плоская структура данных включает следующие составля­ющие (рис. 10.2):

поле - наименьшая поименованная единица данных;

запись - поименованная совокупность полей;

файл - поименованная совокупность экземпляров записей;

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

Рис. 10.2. Плоская структура данных

Широко распространена структура данных КОДАСИЛ. КОДАСИЛ - Ассоциация по языкам систем обработки данных. На рис. 10.3 представлена структура данных этой модели.

Рис. 10.3. Структура данных КОДАСИЛ

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

Агрегат данных (АД) - поименованная совокупность ЭД. АД может быть простым, если состоит только из ЭД, или состав­ным, если включает в свой состав другие агрегаты (рис. 10,4, 10.5).

Рис. 10.4. Пример простого агрегата

Рис.10.5. Пример составного агрегата

Различают два вида АД - векторы и повторяющиеся груп­пы. Вектор представляет собой последовательность ЭД, имею­щих идентичные характеристики. Например, АД «Недельный объем самостоятельной учебной работы студента ____________ курса по дисциплине _______________». В нем экземпляр ЭД повторяется столько раз, сколько недель в семестре. Повторяющаяся группа -это совокупность данных, которая может повторяться (рис. 10.6). Такая совокупность может состоять из ЭД, векторов и повторяю­щихся групп.

Рис. 10.6. Пример агрегата «повторяющаяся группа»

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

Рис. 10.7. Пример набора:

а) тип набора, в котором «тип записи 1» - владелец, прочие

типы записи - члены набора; б) тип набора «Сессия»

База данных - это поименованная совокупность записей и наборов. Описание БД задается ее схемой.

Исследования КОДАСИЛ в области разработки общей си­стемы понятий для различных МД привели к созданию такого базисного набора типов структур данных, с помощью которого удалось описать известные к 1969 г. СУБД. В порядке возраста­ния уровня данный набор включает элемент данных, группу, групповое отношение и базу данных.

Понятие «элемент данных» соответствует аналогичному понятию модели КОДАСИЛ.

Понятие «группа» соответствует двум понятиям модели КОДАСИЛ - «агрегат» и «запись».

Понятие «групповое отношение» используется для зада­ния бинарных связей между группами.

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

33. Операции над данными. Навигационная и спецификационная операции Понятия: селекция, действие, процедура БД, ограничения целостности. (Тема 10, стр. 72-73).