Какие модели структуризации данных были разработаны по предложениям ассоциации

Сетевая модель данных

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	09.12.2013
Размер файла	34,3 K

• посмотреть текст работы

• скачать работу можно здесь

• полная информация о работе

• весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru

1. Сетевая модель данных

2. Структуризация данных в СМД

3. Основные операции

4. Ограничения целостности

5. Достоинства и недостатки СМД

Список использованных источников

1. СЕТЕВАЯ МОДЕЛЬ ДАННЫХ

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

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

Сетевая БД состоит из набора экземпляров определенного типа записи
и набора экземпляров определенного типа связей между этими записями.

Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:

— каждый экземпляр типа записи P является предком только в одном экземпляре типа связи L;

— каждый экземпляр типа записи C является потомком не более чем в одном экземпляре типа связи L.

В 1971 группа DTBG (Database Task Group) представила в американский национальный институт стандартов отчет, который послужил в дальнейшем основой для разработки сетевых систем управления базами данных. Стандарт сетевой модели был создан в 1975 году организацией CODASYL (Conference of Data System Languages), которая определила базовые понятия модели и формальный язык описания.

Типичным представителем систем, основанных на сетевой модели данных, является СУБД IDMS (Integrated Database Management System), разработанная компанией Cullinet Software, Inc. и изначально ориентированная на использования на мейнфреймах компании IBM. Архитектура системы основана на предложениях DBTG организации CODASYL. В настоящее время IDMS принадлежит компании Computer Associates.

2. СТРУКТУРИЗАЦИЯ ДАННЫХ В СЕТЕВЫХ МОДЕЛЯХ ДАННЫХ

Структуризация данных базируется на использовании концепций «агрегации» и «обобщения». Один из первых вариантов структуризации данных был предложен Ассоциацией по языкам обработки данных ( Conference on Data Systems Languages, CODASYL):

— Элемент данных — минимальная информационная единица доступная пользователю.

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

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

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

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

Наборы бывают нескольких видов:

1. С одними и теми же типами записей, но разными типами наборов.

2. Наборы из трех записей и более, в том числе с обратной связью.

3. Сингулярный набор (только один экземпляр). У такого набора нет естественного владельца и в качестве него выступает система.
В дальнейшем такие наборы могут приобрести запись — владельца.

Рисунок 1 — Структуризация данных

Особенности построения сетевой модели данных

— База данных может состоять из произвольного количества записей и наборов различных типов.

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

— В любом наборе может быть только один владелец.

— Тип записи может быть владельцем в одних типах наборов и членом
в других типах наборов.

— Тип записи может не входить ни в какой тип наборов.

— Допускается добавление новой записи в качестве экземпляра владельца, если экземпляр-член отсутствует.

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

Реализация групповых отношений в сетевой модели осуществляется
с использованием указателей (адресов связи или ссылок), которые устанавливают связь между владельцем и членом группового отношения. Запись может состоять в отношениях разных типов (1:1, 1:M, M:M). Заметим, что если один из вариантов установления связи 1:1 очевиден (в запись — владелец отношения, поля которой соответствуют атрибутам сущности, включается дополнительное поле — указатель на запись — член отношения), то возможность представления связей 1:M и M:M таким же образом весьма проблематична. Поэтому наиболее распространенным способом организации связей в сетевых СУБД является введение дополнительного типа записей, полями которых являются указатели.

3. ОСНОВНЫЕ ОПЕРАЦИИ

сетевая модель данный

— Операция ЗАПОМНИТЬ позволяет занести в БД новую запись
и автоматически включить эту запись в групповые отношения, где она объявлена подчиненной с соответствующим режимом включения.

— Операция ВКЛЮЧИТЬ В ГРУППОВОЕ ОТНОШЕНИЕ позволяет существующю запись связать с с записью-владельцем.

— Операция ПЕРЕКЛЮЧИТЬ дает возможность подчиненную запись связать с записью-владельцем в том же групповом отношении.

— Операция ОБНОВИТЬ изменять значения элементов записей, существующих в БД. Перед выполнением этого оператора соответствующая запись предварительно должна быть извлечена.

— Операция ИЗВЛЕЧЬ позволяет последовательно (т.е. перебирая) извлечь запись. Запись можно извлечь по значению первичного ключа или используя групповые отношения, в которых они участвуют. Так, от владельца можно перейти к записям — членам, а от записи-члена перейти к владельцу группового отношения.

— Операция УДАЛИТЬ дает возможность убрать из БД ненужную запись. Если удаляемая запись объявлена владельцем в групповом отношении, то анализируется класс членства подчиненных записей. Обязательные члены должны быть предварительно откреплены от этого владельца, т.е. удалены
из группового отношения, фиксированные будут удалены вместе с ним,
а необязательные останутся в БД.

— Операция ИСКЛЮЧИТЬ ИЗ ГРУППОВОГО ОТНОШЕНИЯ позволяет разорвать связь между записью-владельцем и записью-членом группового отношения, сохранив обе в БД.

Использования сетевой модели

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

СУБД, поддерживающие сетевую модель, широко использовались на вычислительных системах серии IBM 360/370 (ЕС ЭВМ). В качестве примеров таких систем можно указать IDMS, UNIBAD (БАНК), аналоги СЕДАН, СЕТОР. На персональных компьютерах сетевые СУБД не получили широкого распространения. Примером сетевой СУБД для персонального компьютера является db_VISTA III. Отметим, что система db_VISTA реализована на языке С и поэтому является переносимой. Система может эксплуатироваться на ПЭВМ типа IBM PC, SUN, Macintosh.

4. ОГРАНИЧЕНИЯ ЦЕЛОСТНОСТИ

Ограничения целостности — это правила, которым должны удовлетворять значения элементов данных. Ограничения целостности делятся на:

* явные (включаются в структуру базы данных с помощью средств языка контроля данных (DCL, Data Control Language))

*неявные (определяются самой структурой данных).

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

5. ДОСТОИНСТВА И НЕДОСТАТКИ СМД

1.Стандартизация. Появление стандарта CODASYL, который определил базовые понятия модели и формальный язык описания.

2.Быстродействие. Быстродействие сетевых баз данных сравнимо
с быстродействием иерархических баз данных.

3.Гибкость. Множественные отношения предок/потомок позволяют сетевой базе данных хранить данные, структура которых была сложнее простой иерархии.

4.Универсальность. Выразительные возможности сетевой модели данных являются наиболее обширными в сравнении с остальными моделями.

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

1. Жесткость. Наборы отношений и структуру записей необходимо задавать наперёд. Изменение структуры базы данных ведет за собой перестройку всей базы данных. Связи закреплены в записях в виде указателей. При появлении новых аспектов использования этих же данных может возникнуть необходимость установления новых связей между ними. Это требует введения в записи новых указателей, т.е. изменения структуры БД, и, соответственно, переформирования всей базы данных.

2. Сложность. Сложная структура памяти.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Сетевая модель данных [электронный ресурс] — Режим доступа http://ru.wikipedia.org/wiki/Сетевая_модель_данных

2. Кузнецов С.Д. Базы данных. Вводный курс. — М.: Майор,2008. — 176с.

Размещено на Allbest.ru

Подобные документы

Виды и модели данных

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

Основные типы моделей данных

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

Работа с базами данных

Характеристика реляционной, иерархической и сетевой моделей баз данных. Анализ методов проектирования (декомпозиция, синтез, объектная связь), организации, обновления, восстановления, ограничений, поддержания целостности данных на примере СУБД Ms Access.

Особенности построения базы данных

Преимущества и недостатки иерархической модели данных. Целостная часть реляционной модели данных. Базовые требования целостности сущностей и по ссылкам. Ограничения целостности сущности и по ссылкам. Аксиомы Армстронга, аномалии обновления и их виды.

Реляционная модель данных

Сущность и характеристика типов моделей данных: иерархическая, сетевая и реляционная. Базовые понятия реляционной модели данных. Атрибуты, схема отношения базы данных. Условия целостности данных. Связи между таблицами. Общие представления о модели данных.

Сетевая модель данных TCP/IP

Сущность и предназначение сетевой модели данных TCP/IP. Уровень приложений TCP/IP. Схема работы веб-браузера. Транспортный уровень TCP/IP. Схема использования служб Ethernet протоколом IP. Этапы передачи данных узлом в реальной физической среде сети.

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

Базы данных и их использование в вычислительной технике. Особенности и основная конструктивная единица сетевой модели данных. Иерархическая модель, объекты предметной области. Реляционная модель, ее наглядность, представление данных в табличной форме.

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам

Системы, использующие базы данных.

Целью курса «Системы баз данных» является изучение теоретических основ построения баз данных (БД), основных операций над данными, методов организации поиска и обработки данных, языковых средств описания и манипулирования данными, принципов построения основных моделей данных и их использование в современных системах управления базами данных (СУБД) Для изучения выбрана полнофункциональная реляционная система управления базами данных – MS Аccess 2003, на примере которой вы будете разрабатывать приложения с использованием основных объектов, языка структурированных запросов SQL, а также ознакомитесь с технологией создания макросов и модулей.

Теория БД –сравнительно молодая область знаний. Возраст ее составляет немногим более 30 лет. В 1968 г. Была введена в эксплуатацию первая промышленная СУБД система IMS фирмы IBM. В 1975 году появился первый стандарт ассоциации по языкам систем обработки данных — Conference of Data System Languages (CODASYL), который определил ряд фундаментальных понятий в теории систем БД (для сетевой модели). В дальнейшем развитие теории БД связано с именем американского математика Эдгара Ф.Кодда, который является создателем реляционных БД.

С самого начала развития вычислительной техники образовались два основных направления ее использования.

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

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

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

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

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

Первая развитая файловая система была разработана фирмой IBM для ее серии 360. В этой системе поддерживались как чисто последовательные, так и индексно-последовательные файлы, а реализация во многом опиралась на возможности только появившихся к этому времени контроллеров управления дисковыми устройствами. Если учесть к тому же, что понятие файла в OS/360 было выбрано как основное абстрактное понятие, которому соответствовал любой внешний объект, включая внешние устройства, то работать с файлами на уровне пользователя было очень неудобно.

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

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

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

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

Как уже упоминалось выше, предшественницами СУБД были файловые системы. Однако появление СУБД не привело к полному исчезновению файловых систем. Для выполнения некоторых специализированных задач подобные файловые системы ис­пользуются до сих пор. Считается, что развитие СУБД началось еще в 60-е годы, ко­гда разрабатывался проект полета корабля Apollo на Луну. Этот проект был начат по инициативе президента США Дж. Ф. Кеннеди, поставившего задачу высадить чело­века на Луну к концу десятилетия. В то время не существовало никаких систем, способных обрабатывать или как-либо управлять тем огромным количеством данных, которое было необходимо для реализации этого проекта.

В результате специалисты основного подрядчика – фирмы North American Aviation (теперь эта фирма называется Rockwell International) – разработали про­граммное обеспечение под названием GUAM (Generalized Update Access Method).

Основная идея GUAM была построена на том, что малые компоненты объединяют­ся вместе как части более крупных компонентов до тех пор, пока не будет собран воедино весь проект. Эта соответствующая инвертированному дереву структура часто называетсяиерархической структурой. В середине 60-х годов корпорация IBM присоединилась к фирме NAA для совместной работы над GUAM, в результате чего была создана система IMS (Information Management System). Причина, по которой корпорация IBM ограничила функциональные воз­можности IMS только управлением иерархиями записей, заключалась в том, что необходимо было обеспечить работу с устройствами хранения с последовательным доступом, а именно с магнитными лентами, которые были основным типом носи­теля в то время. Спустя некоторое время это ограничение удалось преодолеть. Не­смотря на то, что IMS является самой первой из всех коммерческих СУБД, она до сих пор остается основной иерархической СУБД, используемой на большинстве крупных мейнфреймов.

Другим заметным достижением середины 60-х годов было появление системыIDS(Integrated Data Store) фирмы General Electric.

Работу над ней возглавлял один из пионеров исследований в области систем управления базами данных – Чарльз Бачман. Развитие этой системы привело к созданию нового типа сис­тем управления базами данных –сетевых (network) СУБД, что оказало сущест­венное влияние на информационные системы того поколения. Сетевая СУБД созда­валась для представления более сложных взаимосвязей между данными, чем те, которые можно было моделировать с помощью иерархических структур, а также для формирования стандарта баз данных. Для создания таких стандартов в 1965 году на конференции организацииCODASYL (Conference on Data Systems Languages), прохо­дившей при участии представителей правительства США и бизнесменов, была сфор­мирована рабочая группа List Processing Task Force, переименованная в 1967 году в группу Data Base Task Group (DBTG). В компетенцию группы DBTG входило опреде­ление спецификаций среды, которая допускала бы разработку баз данных и управле­ние данными. Предварительный вариант отчета этой группы был опубликован в 1969 году, а первый полный вариант – в 1971 году.

Предложения группы DBTG содер­жали три компонента:

· язык управления данными.

Сетевая схема – это логическая организация всей базы данных в целом (с точки зрения администратора базы данных), которая включает определение имени базы данных, типа каждой записи и компонентов записей каждого типа.

Подсхема – это часть базы данных, как она видится пользователям или приложениям.

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

Группа DBTG также предложила стандартизировать три различных языка:

1. язык определения данных (Data Definition Language – DDL) для схемы, который позволит описать ее;

2. язык определения данных (также DDL) для подсхемы, который позволит оп­ределять в приложениях те части базы данных, доступ к которым будет необ­ходим;

3. язык манипулирования данными (Data Manipulation Language – DML),предназначенный для управления данными.

Несмотря на то, что этот отчет официально не был одобрен Национальным инсти­тутом стандартизации США (American National Standards Institute – ANSI), боль­шое количество систем было разработано в полном соответствии с этими предложе­ниями группы DBTG. Теперь они называются CODASYL-системами, или DBTG-системами. CODASYL-системы и системы на основе иерархических подходов пред­ставляют собой СУБДпервого поколения.

Однако этим двум моделям присущи следующие недостатки:

– для выполнения простых запросов с использованием переходов и досту­пом к определенным записям необходимо создавать достаточно сложные про­граммы;

– независимость от данных существует лишь в минимальной степени;

– отсутствуют общепризнанные теоретические основы.

В 1970 году Э.Ф. Кодд (Е.F. Codd), работавший в исследовательской лаборатории корпорации IBM, опубликовал очень важную и весьма своевременную статью о реля­ционной модели данных, позволявшей устранить недостатки прежних моделей. Вслед за этим появилось множество экспериментальных реляционных СУБД, а пер­вые коммерческие продукты появились в конце 70-х – начале 80-х годов. Особенно следует отметить проект System R, разработанный в исследовательской лаборатории корпорации IBM, расположенной в городе Сан-Хосе, штат Калифорния, и созданный в конце 70-х годов. Этот проект был задуман с целью доказать практичность реляционной модели, что достигалось посредством реализации преду­смотренных ею структур данных и требуемых функциональных возможностей. На основе этого проекта были получены важнейшие результаты:

• разработан структурированный язык запросов SQL, который с тех пор стал стандартным языком любых реляционных СУБД;

• в 80-х годах созданы различные коммерческие реляционные СУБД, на­пример DB2, или SQL/DS корпорации IBM или Oracle корпорации Oracle Corporation.

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

В качестве примера многопользовательских СУБД может служить система CA-OpenIngres фирмы Computer Associates и система Informix фирмы Informix Software, Inc.

Примерами реляционных СУБД для персональных компьютеров являются Access и FoxPro фир­мы Microsoft, Paradox и Visual dBase фирмы Borland, а также R:Base фирмы Microrim.

Реляционные СУБД относятся к СУБДвторого поколения.

Однако реляционная модель также обладает некоторыми недостатками, в частно­сти, ограниченными возможностями моделирования. Для решения этой проблемы был выполнен большой объем исследовательской работы.

В 1976 году Чен предложил мо­дель “сущность-связь” (Entity-Relationship model – ER-модель), которая в настоящее время стала самой распространенной технологией проектирования баз данных В 1979 году Кодд сделал попытку устранить недостатки собственной основополагающей работы и опубликовал расширенную версию реляционной модели – RM/T (1979), затем еще одну версию – RM/V2 (1990). Попытки создания модели дан­ных, позволяющей более точно описывать реальный мир, нестрого называютсеманти­ческим моделированием данных (semantic data modeling). В ответ на все возрастающую сложность приложений баз данных появились две новые системы: объектно-ориентированные СУБД, или OOСУБД (Object-Oriented DBMS – OODBMS), и объектно-реляционные СУБД, или ОРСУБД (Object-Relational DBMS – ORDBMS).

02 Лекция — Основные модели данных

ция либо выполняется полностью, т.е. выполняются все входящие в неё операции, либо не выполняется совсем, если в процессе её выполнения возникает ошибка. 2.1.3. Ограничения целостности Ограничения целостности – это правила, которым должны удовлетворять значения элементов данных. Ограничения целостности делятся на явные и неявные . Неявные ограничения определяются самой структурой данных. Например, тот факт, что запись типа СОТРУДНИК имеет поле Дата рождения , служит, по существу, ограничением целостности, означающим, что каждый сотрудник организации имеет дату рождения, причём только одну. Явные ограничения включаются в структуру базы данных с помощью средств языка контроля данных (DCL, Data Control Language). В качестве явных ограничений чаще всего выступают условия, накладываемые на значения данных. Например, номер паспорта является уникальным, заработная плата не может быть отрицательной, а дата приёма сотрудника на работу обязательно будет меньше, чем дата его перевода на другую работу. Также различают статические и динамические ограничения целостности. Статические ограничения присущи всем состояниям ПО, а динамические определяют возможность перехода ПО из одного состояния в другое. Примерами статических ограничений целостности могут служить требование уникальности индивидуального номера налогоплательщика (ИНН) или задание ограниченного множества значений атрибута «Пол» (‘м’ и ‘ж’). В качестве примера динамического ограничения целостности можно привести правило, которое распространяется на поля-счётчики: значение счётчика не может уменьшаться. За выполнением ограничений целостности следит СУБД в процессе своего функционирования. Она проверяет ограничения целостности каждый раз, когда они могут быть нарушены (например, при добавлении данных, при удалении данных и т.п.), и гарантирует их соблюдение. Если какая-либо команда нарушает ограничение целостности, она не будет выполнена и система выдаст соответствующее сообщение об ошибке. Например, если задать в качестве ограничения правило «Остаток денежных средств на счёте не может быть отрицательным», то при попытке снять со счёта денег больше, чем там есть, система выдаст сообщение об ошибке и не позволит выполнить эту операцию. Таким образом, ограничения целостности обеспечивают логическую непротиворечивость данных при переводе БД из одного состояния в другое. В настоящее время разработано много различных моделей данных. Основные – это сетевая, иерархическая и реляционная модели. 2.2. Сетевая модель данных (СМД) Сетевая модель позволяет организовывать БД, структура которых представляется графом общего вида (пример СМД – на рис. 2.4). Организация данных в сетевой модели соответствует структуризации данных по версии

CODASYL. Каждая вершина графа хранит экземпляры сущностей (записи одного типа) и сведения о групповых отношениях с сущностями других типов. Каждая запись может хранить произвольное количество значений атрибутов (элементов данных и агрегатов), характеризующих экземпляр сущности. Для каждого типа записи выделяется первичный ключ – атрибут, значение которого позволяет однозначно идентифицировать запись среди экземпляров записей данного типа. Связи между записями в СМД выполняются в виде указателей , т.е. каждая запись хранит ссылку на другую однотипную запись (или признак конца списка) и ссылки на списки подчинённых записей, связанных с ней групповыми отношениями. Таким образом, в каждой вершине записи хранятся в виде связного списка. Если список организован как однонаправленный, запись имеет ссылку на следующую однотипную запись в списке; если список двунаправленный – то на следующую и предыдущую однотипные записи. Групповые отношения характеризуются следующими признаками: 1. Способ упорядочения подчинённых записей. Поддерживаются три способа упорядочения: Очередь – добавление в конец списка (FIFO – first input, first output). Стек – добавление в начало списка (LIFO – last input, first output). Сортировка по значению ключа. При этом задаётся ключевое поле (группа полей), и вновь поступившая запись добавляется в упорядоченный список в соответствии со значением этого поля (значением ключа). 2. Режим включения подчинённых записей. Режим включения бывает автоматический и ручной . При автоматическом режиме подчинённая запись связана с записьювладельцем обязательной связью, поэтому она включается в групповое отношение и прикрепляется к записи-владельцу в момент внесения в БД. (Из этого следует, что запись-владелец должна быть внесена в базу данных до внесения первого экземпляра подчинённой записи.) При ручном режиме включения подчинённая запись может находиться в БД и не быть прикрепленной к записи-владельцу. Она вручную включается в групповое отношение тогда, когда это отношение (связь) возникает. 3. Режим исключения подчинённых записей. Режим исключения определяется классом членства . Различают три класса членства – фиксированный, обязательный и необязательный: Записи с обязательным членством должны быть удалены до удаления за- писи–владельца: владелец, к которому прикреплена хотя бы одна запись с обязательным членством, не может быть удалён. Записи с фиксированным членством удаляются вместе с записью–вла- дельцем. Записи с необязательным членством при удалении записи–владельца останутся в БД.

Рассмотрим фрагмент БД «Предприятие» (рис. 2.5). Здесь записи типов ОТДЕЛЫ и ОРГАНИЗАЦИИ-ЗАКАЗЧИКИ являются владельцами записей

типа ПРОЕКТЫ и они связаны групповыми отношениями соответственно вы- полняют и заказывают . Записи типов ОТДЕЛЫ и ПРОЕКТЫ являются вла- дельцами записей типа СОТРУДНИКИ и они связаны групповыми отношени- ями работают и выполняются . Записи типа СОТРУДНИКИ являются вла- дельцами записей типа ДЕТИ .

ОТДЕЛЫ	ОРГАНИЗАЦИИ-ЗАКАЗЧИКИ
работают	выполняют		заказывают
СОТРУДНИКИ	выполняются	ПРОЕКТЫ
имеют
	ДЕТИ
Рис.2.5. Пример фрагмента сетевой БД «Предприятие»

Групповые отношения чаще всего описывают связь «один-ко-многим»: один владелец, много подчинённых. Например, отношение работают подразумевает, что каждый сотрудник работает в одном отделе, но в каждом отделе могут работать несколько сотрудников. С другой стороны, групповое отношение выполняются отражает связь «многие-ко-многим»: каждый сотрудник может участвовать в выполнении нескольких проектов, каждый проект могут выполнять несколько человек. Что касается классов членства подчинённых записей, то связь «сотрудники–дети» относится к фиксированному классу членства, связь «сотрудники–проекты» – к необязательному, а все остальные – к обязательному классу членства. Режим включения для связи «сотрудники– проекты» ручной, для всех остальных – автоматический. В СМД связи 1:n между разными сущностями реализуются с помощью групповых отношений, а связи 1:n между атрибутами сущности – в рамках записи. Для реализации связей типа n:m вводится вспомогательный тип записи и две связи 1:n. В СМД применяются следующие операции над данными: запомнить : внесение информации в БД; включить в групповое отношение: установление связей между данными; переключить : переход члена набора к другому владельцу; обновить : модификация данных; извлечь : чтение данных; удалить : физическое или логическое удаление данных; исключить из группового отношения : разрыв связей между данными. В сетевой модели данных предусмотрены специальные способы навигации и манипулирования данными. Аппарат навигации в графовых моделях служит для установления тех записей, к которым будет применяться очередная операция манипулирования данными. Такие записи называются текущими . В СМД возможны переходы:

от текущего экземпляра записи определённого типа к следующему экземпляру записи этого же типа; из текущей вершины в любую вершину, с которой текущая связана группо- вым отношением. Навигация в СМД может начинаться с любой записи. Наиболее распространенной и стандартизованной из реализаций СМД является модель CODASYL. В соответствии с ней описание схемы БД осуществляется на языке COBOL, а манипулирование данными – с помощью включающего языка программирования высокого уровня. Примером сетевой СУБД является система Integrated Database Management System (IDMS). СМД является наиболее полной с точки зрения реализации различных типов связей и ограничений целостности, но она является достаточно сложной для проектирования и поддержки. В этой модели не обеспечивается физическая независимость данных, т.к. наборы организованы с помощью физических ссылок. Также в СМД не обеспечивается независимость данных от программ. Из-за этих недостатков эта модель не получила широкого распространения. 2.3. Иерархическая модель данных (ИМД) Иерархическая модель позволяет строить БД с иерархической древовидной структурой. Структура ИМД описывается в терминах, аналогичных терминам сетевой модели данных (версия CODASYL). Группу в ИМД принято называть сегментом . В основе ИМД лежит понятие дерева. Дерево – это связный неориентированный граф, который не содержит циклов. При работе с деревом выделяют какую-то конкретную вершину, определяют её как корень дерева и рассматривают особо – в эту вершину не заходит ни одно ребро. В этом случае дерево становится ориентированным, ориентация определяется от корня. Дерево как ориентированный граф определяется так: имеется единственная особая вершина, называемая корнем, в которую не заходит ни одно ребро; во все остальные вершины заходит только одно ребро, а исходит произвольное количество ребер; граф не содержит циклов. Конечные вершины, то есть вершины, из которых не выходит ни одной дуги, называются листьями дерева. Количество вершин на пути от корня к листьям в разных ветвях дерева может быть различным. В иерархических моделях данных используется ориентация древовидной структуры от корня к листьям. Графическая диаграмма концептуальной схемы базы данных называется деревом определения . Пример иерархической базы данных приведён на рис. 2.6. Каждая некорневая вершина в ИМД связана с родительской вершиной (сегментом) иерархическим групповым отношением. Каждая вершина дерева соответствует типу сущности ПО. Тип сущности характеризуется произвольным количеством атрибутов, связанных с ней

отношением 1:1. Атрибуты, связанные с сущностью отношением 1:n, образуют отдельную сущность (сегмент) и переносятся на следующий уровень иерархии. Реализация связей типа n:m не поддерживается. ФАКУЛЬТЕТ Шифр_факультета, Название_факультета

КУРС Номер_курса ГРУППА Номер_группы, Год_образования СТУДЕНТ Номер_зачетной_книжки, ФИО_студента, Паспортные_данные

КАФЕДРА Шифр_кафедры, Название_кафедры ПРЕПОДАВАТЕЛЬ ФИО_преподавателя, Должность, Паспортные_данные

Рис.2.6. Пример фрагмента иерархической базы данных Тип вершины определяется типом сущности и набором её атрибутов. Каждая вершина дерева хранит экземпляры сущностей – записи. Следствием внутренних ограничений иерархической модели является то, что каждому экземпляру зависимой группы в БД соответствует уникальное множество экземпляров родительских записей – по одному экземпляру (записи) каждого типа вершин вышестоящих уровней. По сравнению с СМД иерархическая имеет ограниченный набор режимов включения и исключения подчинённых записей. Это определяется обязательностью связей: в дереве не может быть «висячих» вершин, не связанных с вершиной верхнего уровня (кроме корневой). Поэтому ИМД не поддерживает необязательный класс членства и ручной режим включения записей. В ИМД предусмотрены специальные способы навигации. Передвижение по дереву всегда начинается с корневой вершины, от которой можно перейти на конкретный экземпляр записи любой вершины следующего уровня. Эта вершина становится текущей вершиной, а экземпляр – текущей записью. От этой записи можно перейти к другой записи данной вершины, к экземпляру записи родительской вершины или к экземпляру записи подчинённой вершины. Т.о., попасть в любую вершину можно, только проделав полный путь по дереву от корня. Связи между записями в ИМД обычно выполнены в виде ссылок (т.е. хранятся адреса связанных записей). Корневая запись дерева должна содержать ключ с уникальным значением. Ключи некорневых записей должны иметь уникальные значения только в экземплярах групповых отношений, т.е. на одном и том же уровне иерархии в разных ветвях дерева могут быть экземпляры записей с одинаковыми ключами. Это объясняется тем, что каждая запись идентифицируется полным сцепленным ключом , который образуется путём конкатенации всех ключей экземпляров родительских записей. Например, для студента (рис. 2.6) ключ –

это (Шифр_факультета+Номер_курса+Номер_группы+Номер_зачётной_книжки). Основным недостатком ИМД является дублирование данных. Оно вызвано тем, что каждая сущность (атрибут) может относиться только к одной родительской сущности. Например, если в БД хранятся данные о детях сотрудников, а на предприятии работает и отец, и мать ребёнка, то сведения об этом ребёнке нужно хранить дважды. Аналогичная ситуация возникает, если нужно отразить в БД связь «многие-ко-многим». Дублирование данных может вызвать нарушение логической целостности БД при внесении изменений в эти данные. Если данные имеют естественную древовидную структуризацию, то использование иерархической модели данных не вызывает проблем. Но на практике часто требуется реализовать структуры данных, отличные от иерархической. Для решения этих задач конкретные СУБД, основанные на ИМД, включают дополнительные средства, облегчающие представление произвольно организованных данных. В качестве примера типичного представителя иерархических СУБД можно привести систему IMS (Information Management System, IBM). Сетевая и иерархическая модели данных относятся к базам данных I-го поколения (60-е – начало 70-х гг. XX века). 2.4. Основные достоинства и недостатки ранних СУБД Сильные места ранних СУБД: Развитые средства управления данными во внешней памяти на низком уровне; Возможность построения вручную эффективных прикладных систем; Возможность экономии памяти за счет разделения подобъектов (в сетевых системах). Недостатки: Слишком сложно пользоваться; Фактически необходимы знания о физической организации; Прикладные системы зависят от этой организации; Их логика перегружена деталями организации доступа к БД. Таким образом, эти модели не смогли в полной мере реализовать независимость данных от программ. Из-за особенностей их организации структура запросов к данным в таких системах определяется наличием связей между записями. Следующее, II-е поколение баз данных основано на реляционной мо- дели.

Информационное обеспечение САПР (окончание)

Как было сказано выше, сетевая модель данных реализует связи типа «многие ко многим». Сетевые базы данных разрабатывались Ассоциацией по языкам систем обработки данных КОДАСИЛ 1 От англ. «The Conference on Data System Languages» — CODASYL; рабочая группа DATA Base Task Group — DBTG. и ее рабочей группой DBTG. Первые исследования этой группы были направлены на создание языков программирования задач обработки данных, в частности, языка КОБОЛ. В дальнейшем были разработаны специальные предложения DBTG для систем управления сетевыми базами данных.

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

Сформулируем основные определения ЯОД КОДАСИЛ и укажем на соответствие определений в сетевых и реляционных БД . Пример структуры сетевой базы данных приведен на рис. 11.1. Там же условно показаны основные термины сетевой БД .

Элемент данных — наименьшая единица поименованных данных, представляемых в БД значением, — соответствует значению атрибута в реляционной БД (РБД).

Агрегат данных — совокупность элементов данных внутри одной записи — соответствует домену в РБД.

Рис. 11.1. Структура сетевой базы данных

Запись — совокупность элементов данных , состоящая из элементов или агрегатов данных — соответствует кортежу в РБД. Она характеризуется типом записи , которому соответствует произвольное число ее экземпляров.

Набор — совокупность записей — соответствует отношению в РБД; характеризуется типом набора (имя отношения в РБД). Каждый экземпляр набора должен содержать один экземпляр объявленного для него типа записи — владельца — и один или несколько типов записей — членов набора . Например, если тип набора ТРАНЗИСТОРЫ СВЧ, то тип записи для владельца набора — ТРАНЗИСТОРЫ; тип записей членов набора — марки транзисторов СВЧ ( рис. 11.1).

Область — совокупность записей , не сохраняющая соответствия «владелец — член набора «. Область может содержать экземпляры одного (или более) типа записей , а экземпляры одного типа записи могут находиться в нескольких областях ( рис. 11.1); конкретный же экземпляр записи может приписываться только одной области.

Схема БД — глобальное описание сетевой БД в приведенных терминах с точки зрения администратора базы данных .

Подсхема БД — часть схемы БД с точки зрения прикладного программиста, ограничивающая сферу действия последнего. Это предохраняет от случайных изменений в тех частях БД , к которым он не должен обращаться.

База данных представляет собой совокупность всех записей , наборов и областей, управляемых некоторой схемой.

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

Последовательные структуры данных являются простейшими из них и представлены в БД одним набором , члены которого упорядочены определенным образом. В древовидных структурах — иерархических — каждая запись (кроме одной, называемой корневой ) связана с нулем или несколькими различными записями , расположенными ниже ее по иерархии, и с одной записью , расположенной выше. Корнем дерева служит запись наивысшего уровня, например, ТРАНЗИСТОРЫ на рис. 11.1. Так как каждый набор может иметь произвольное число записей (членов этого набора ) и допускается произвольное число типов наборов , дерево может быть любой ширины и глубины.

Циклы — замкнутые структуры в БД . Различают однотипные и многотипные циклы . В однотипных циклах один и тот же тип записи объявляется и владельцем, и членом одного и того же типа набора . Например, тип набора СОСТОИТ ИЗ ( рис. 11.1), означает, что каждый прибор может, в свою очередь , состоять из других приборов. В многотипных циклах владелец одного типа набора является членом предыдущего.

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

Разработан синтаксис ЯОД КОДАСИЛ, включающий в себя различные типы сетей описания данных, схемы, области, записи и набора .

11.3. Иерархическая модель базы данных

Иерархические модели баз данных исторически возникли одними из первых. В качестве примера рассмотрим иерархическую БД — Information Management Systems ( IMS ), разработанную в 1967 году. Существуют соответствия терминов, описывающих сетевые модели БД КОДАСИЛ и иерархическую IMS , в частности: тип набора — связь ; тип записи — тип сегмента; запись — владелец набора — исходный сегмент; запись — член набора — порожденный сегмент и т. д. ( рис. 11.2).

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

В иерархической структуре любой тип записи не может иметь более одного владельца (порожденный сегмент). Поэтому и не нужно вводить понятие «тип набора «.

Рис. 11.2. Структура иерархической модели баз данных

Была рассмотрена физическая база данных . Однако существуют еще и логические отношения, связывающие две (или более) физические БД дерева ( рис. 11.2). С введением этого понятия могут быть связаны два исходных сегмента: один из них, находящийся в той же базе данных, что и рассматриваемый сегмент, называют физически исходным сегментом, другой — логически исходным сегментом. Логические связи на рис. 11.2 показаны пунктирными линиями. С помощью иерархических структур и логических отношений можно представить и некоторые сетевые структуры. Существуют некоторые ограничения на взаимное расположение физически и логически исходных и порожденных сегментов.

В памяти ЭВМ файлы иерархической базы данных IMS могут быть представлены четырьмя способами: HSAM — последовательный метод доступа , HISAM — индексно-последовательный, HDAM — прямой , HI DAM — индексно-прямой 2 От обозначений: AM ( Access Method ) — метод доступа, Н (Hierarhical) — иерархический, I (Indexed) — индексный, S (Sequental) — последовательный, D (Direct) — прямой. .

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

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

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

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

Контрольные вопросы и упражнения

1. Каково назначение и состав ИО САПР?
2. Что входит в банк данных?
3. Для чего предназначены СУБД?
4. Перечислите требования, предъявляемые к базе данных.
5. Приведите примеры информационного согласования программ при построении баз данных.
6. Какие базы данных называют сетевыми?
7. Какие базы данных называют реляционными?
8. Приведите основные операции реляционной алгебры .
9. Перечислите основные понятия для различных уровней представления данных.
10. Укажите основные особенности и характеристики трех моделей представления данных.
11. Докажите необходимость оптимизации запросов к базам данных.
12. Приведите основные характеристики и параметры сетевых СУБД.
13. Приведите основные характеристики и параметры иерархических СУБД.
14. Что составляет кортеж отношения?
15. Что означает » арность кортежа»?
16. Что называют доменом?