tehnologia (1018792), страница 23
Текст из файла (страница 23)
4.19, а) и кортежи (рис. 4.19, б). Наиболеесущественная характеристика элемента данных в этих структурах — его принадлежностьнекоторому набору, т. е. отношение вхождения. Данные абстрактные структуры используют,если никакие другие отношения элементов не являются существенными для описываемыхобъектов.Ко второй группе относят векторы, матрицы, массивы (многомерные), записи,строки, а также таблицы, включающие перечисленные структуры в124качестве частей. Использование этих абстрактных типов может означать, что существеннымявляется не только вхождение элемента данных в некоторую структуру, но и их порядок, атакже отношения иерархии структур, т. е. вхождение структуры в структуру более высокойстепени общности (рис.
4.20).В тех случаях, когда существенны связи элементов данных между собой, в качествемодели структур данных используют графы [55]. На рис. 4.21 показаны различные вариантыграфовых моделей.Очень существенно, что в реальности возможно вложение структур данных, в томчисле и разных типов, а потому для их описания могут потребоваться специальные модели.В зависимости от описываемых типов отношений модели структур данных принято делитьна иерархические и сетевые.Иерархические модели позволяют описывать упорядоченные или не упорядоченныеотношения вхождения элементов данных в компонент более высокого уровня, т.е.множества, таблицы и их комбинации.
К иерархическим моделям относят модель ДжексонаОрра, для графического представления которой можно использовать:• диаграммы Джексона, предложенные в составе методики проектированияпрограммного обеспечения того же автора в 1975 г.;• скобочные диограммы Орра, предложеные в составе методики проектированияпрограммного обеспечения Варнье-0рра(1974).125Сетевые модели основаны на графах, а потому позволяют описывать связностьэлементов данных независимо от вида отношения, в том числе комбинации множеств,таблиц и графов. К сетевым моделям, например, относят модель «сущность-связь» (ER Entity-Relationship), обычно используемую при разработке баз данных.Диаграммы Джексона.
В основе диаграмм Джексона лежит предположение о том,что структуры данных, так же, как и программ, можно строить т элементов сиспользованием всего трех основных конструкций: последовательности, выбора иповторения.Каждая конструкция представляется в виде двухуровневой иерархии, на верхнемуровне которой расположен блок конструкции, а на нижнем - блоки элементов. Испанииконструкций различаются специальными символами в правом верхнем углу блоковэлементов.
В изображении последовательности дополнительный символ отсутствует. Визображении выбора ставится символ «о» (латинское) - сокращение английского «или» (or).Конструкции последовательности и выбора должны содержать но два или более элементоввторого уровня. В изображении повторения в блоке единственного (повторяющеюся)элемента ставится символ «*».Так схема, показанная на рис. 4.22, а, означает, что конструкция А состоит изэлементов В, С и D, следующих в указанном порядке. Схема на рис.
4.22, б означает, чтоконструкция S состоит либо из элемента P, либо из126элемента Q, либо из элемента R. Схема, изображенная на рис. 4.22, в, показывает, чтоконструкция I может не содержать элементов или содержать один или более элементов X.В случае, если необходимо показать, что конструкция повторения должна включатьодин или более элементов, используют комбинацию из двух структур последовательности иповторения (рис.
4.23).Скобочные диаграммы Орра. Диаграмма Орра базируется на том жепредположении о сходстве структур программ и данных, что и диаграмма Джексона.Отличие состоит лишь в нотации. Автор предлагает для представления конструкций данныхиспользовать фигурные скобки (рис.
4.24).127Пример 4.6. Рассмотрим описание структуры данных файла «Электроннаяведомость», содержащего сведения о сдаче экзаменов студентами. Файл состоит из записей орезультатах сдачи сессии студентами одной группы. Он имеет следующую структуру: номергруппы, записи об успеваемости студентов (ФИО студента, название предмета и оценка,полученная студентом, в завершении записи специальный символ «конец записи») испециальный символ «конец файла».
На рис. 4.25 показано, как выглядит описание даннойструктуры с использованием диаграммы Джексона, а на рис. 4.26 - с использованием скобокОрра.Сетевая модель данных. Сетевые модели данных используют в тех случаях, еслиотношение между компонентами данных не исчерпываются включением. Для графическогопредставления разновидностей этой модели используют несколько нотаций. Наиболееизвестны из них следующие:• нотация П. Чена;• нотация Р. Баркера;• нотация IDEF1 (более современный вариант этой нотации - IDEF1X используется вCASE-системах, например в системе ERWin).Нотация Баркера является наиболее распространенной.
Далее в настоящем разделебудем придерживаться именно этой нотации.128Базовыми понятиями сетевой модели данных являются: сущность, атрибут и связь.Сущность - реальный или воображаемый объект, имеющий существенное значениедля рассматриваемой предметной области.Каждая сущность должна:• иметь уникальное имя;• обладать одним или несколькими атрибутами, которые либо принадлежат сущности,либо наследуются через связь;• обладать одним или несколькими атрибутами, которые однозначно идентифицируюткаждый экземпляр сущности.Сущность представляет собой множество экземпляров реальных или абстрактныхобъектов (людей, событий, состояний, предметов и т. п.). Имя сущности должно отражатьтип или класс объекта, а не его конкретный экземпляр (Аэропорт, а не Внуково).На диаграмме в нотации Баркера сущность изображается прямоугольником, иногда сзакругленными углами (рис.
4.27. а).Каждая сущность обладает одним или несколькими атрибутами. Атрибут-любаяхарактеристика сущности, значимая для рассматриваемой предметной области ипредназначенная для квалификации, идентификации, классификации, количественнойхарактеристики или выражения состояния сущности (рис. 4.27, б).В сетевой модели атрибуты ассоциируются с конкретными сущностями, и,соответственно, экземпляр сущности должен обладать единственным определеннымзначением для ассоциированного атрибута. Атрибут, таким образом, представляет собойнекоторый тип характеристик или свойств, ассоциированных с множеством реальных илиабстрактных объектов.
Экземпляр атрибута- определенная характеристика конкретногоэкземпляра сущности. Он определяется типом характеристики и ее значением, называемымзначением атрибута.129Атрибуты делятся на ключевые, т. е. входящие в состав уникального идентификатора,который называют первичным ключом, и описательные - прочие.Первичный ключ - это атрибут или совокупность атрибутов и/или связей,предназначенная для уникальной идентификации каждого экземпляра сущности(совокупность признаков, позволяющих идентифицировать объект).
Ключевые атрибутыпомещают в начало списка и помечают символом «#» (рис. 4.27, в).Описательные атрибуты бывают обязательными или необязательными. Обязательныеатрибуты для каждой сущности всегда имеют конкретное значение, необязательные — могутбыть не определены. Обязательные и необязательные описательные атрибуты помечаютсимволами «*» и «о» соответственно.Для сущностей определено понятие супертип и подтип. Супертип- сущностьобобщающая некую группу сущностей (подтипов). Супертип характеризуется общими дляподтипов атрибутами и отношениями. Например, для некоторых задач супертип «учащийся»обобщает подтипы «школьник» и «студент» (рис.
4.28).Связь - поименованная ассоциация между двумя или более сущностями, значимая длярассматриваемой предметной области. Связь, таким образом, означает, что каждыйэкземпляр одной сущности ассоциирован с произвольным (в том числе и нулевым)количеством экземпляров второй сущности и наоборот. Если любой экземпляр однойсущности связан хотя бы с одним экземпляром другой сущности, то связь являетсяобязательной (рис. 4.29.
а). Необязательная связь представляет собой условное отношениемежду сущностями (рис. 4.29, б).Каждая сущность может быть связана любым количеством связей с другимисущностями модели. Связь предполагает некоторое отношение сущностей, котороехарактеризуется количеством экземпляров сущности, участвующих в связи с каждойстороны.130Различают три типа отношений (рис. 4.30):1*1 - «один-к-одному» - одному экземпляру первой сущности соответствует одинэкземпляр второй;1*n - «один-ко-многим» - одному экземпляру первой сущности соответствуютнесколько экземпляров второй;n*m - «многие-ко-многим» - каждому экземпляру первой сущности можетсоответствовать несколько экземпляров второй и, наоборот, каждому экземпляру второйсущности может соответствовать несколько экземпляров первой.Кроме того, сущности бывают независимыми, зависимыми и ассоциированными.Независимая сущность представляет независимые данные, которые всегда присутствуют всистеме. Они могут быть связаны или Не связаны с другими сущностями той же системы.Зависимая сущность представляет данные, зависящие от других сущностей системы,поэтому она всегда должна быть связана с другими сущностями.Ассоциированная сущность представляет данные, которые ассоциируются сотношениями между двумя и более сущностями.
Обычно данный вид сущностейиспользуется в модели для разрешения отношения «многие-ко-многим» (рис. 4.31).Если экземпляр сущности полностью идентифицируется своими ключевымиатрибутами, то говорят о полной идентификации сущности. В противном случаеидентификация сущности осуществляется с использованием атрибутов связанной сущности,что указывается черточкой на линии связи (рис. 4.32).131Кроме этого, модель включает понятия взаимно исключающих, рекурсивных инеперемещаемых связей. При наличии взаимно исключающей связи экземпляр сущностиучаствует только в одной связи из некоторой группы связей (рис.
4.33. а). Рекурсивная связьпредполагает, что сущность может быть связана сама с собой (рис. 4.33, б). Неперемещаемаясвязь означает, что экземпляр сущности не может быть перенесен из одного экземплярасвязи в другой (рис. 4.33. в).Пример 4.7. Рассмотрим структуру базы данных для системы учета успеваемостистудентов. Основными сущностями для решения указанной задачи являются: Студент иПредмет (изучаемый учебный курс).132Отношение между ними относится к типу «многие-ко-многим». Для разрешения этогоотношения введем ассоциированную сущность Экзамен/Зачет, которая отражает текущеевыполнение предметов учебного плана студентом.Предметы, которые изучает и по которым отчитывается студент, запланированыкафедрой в учебном плане.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
