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

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

Документы

Содержание Совокупность функций СУБД по организации и управлению транзакциями называют монитором транзакций. 4.1. Классификация моделей данных Объектные модели данных Модели данных на основе записей Теоретико-множественные модели Физическая модель данных Иерархическая модель данных Иерархическая МД основана на структуре, имеющей сходство, с перевернутым деревом, где от ствола отходят ветви от которых в свою Ограничения целостности Каждый предок может иметь несколько потомков 4.3.1. Структурная часть иерархической модели

Подобный материал:

• Системы управления базами данных (субд). Назначение и основные функции, 30.4kb.
• Программа курса лекций "Базы данных в научных исследованиях", 49.32kb.
• Система управления базами данных это комплекс программных и языковых средств, необходимых, 150.5kb.
• Лекция 2 Базы данных, 241.25kb.
• Любая программа для обработки данных должна выполнять три основных функции: ввод новых, 298.05kb.
• Вопросы к государственному экзамену по специальности «Информационные системы и технологии», 39.93kb.
• Лекция № Технологии баз данных, 92.24kb.
• Проектирование базы данных, 642.58kb.
• Системы управления базами данных, 313.7kb.
• Программа дисциплины Системы управления базами данных Семестры, 22.73kb.

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

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

Модели данных информационных систем

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

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

1. структурную часть, определяющую правила порождения допустимых для данной СУБД видов структур данных;
   
2. управляющую часть, определяющую возможные операции над такими структурами;
   
3. классы ограничений целостности данных, которые могут быть реализо­ваны средствами этой системы.
   

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

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


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


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

4.1. Классификация моделей данных

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

1. объектные модели данных;
   
2. модели данных на основе записей;
   
3. физические модели данных.
   

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

Объектные модели данных

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

Модели данных на основе записей

В модели данных на основе записей база данных состоит из нескольких за­писей фиксированного формата, которые могут иметь разные типы. В большинстве коммерческих СУБД используются ставшие классическимр Два типа такого рода моделей данных: теоретико-графовые (ТГ) и теорети-ко-множественные (ТМ) модели данных. К теоретико-графовым моделям относятся две разновидности: сетевые модели; и иерархические модели. В таких моделях данных предусматриваются характерные для подобного рода структур операции навигации и манипулирования данными. Принципиально

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

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

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

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

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


Физическая модель данных

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

Информационные системы, использующие базы данных, позволили преодолеть ограничения файловых систем. Поддерживая целостную, централизованную структуру данных, информационные системы, использующие базы данных, позволили избавиться от проблем избыточности и слабого контроля данных. Доступ к централизованной базе данных имеет вся организация и если необходимо внести изменение в какое либо поле, это изменение будет известно всем пользователям. Данные контролируются посредством словаря/каталога данных (Data dictionary/directory, DD/D), которым в свою очередь управляет группа сотрудников организации, называемых администраторами базы данных (АБД). Новые методы обращения к данным сильно упростили процесс связывания элементов данных, что в свою очередь привело к расширению возможностей работы с данными. Все эти характеристики систем управления базами данных упрощают процесс программирования и уменьшают необходимость программной поддержки.

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

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

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

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

Основная иерархическая СУБД – система IMS фирмы IBM, созданная в середине шестидесятых годов. В конце шестидесятых – начале семидесятых были созданы и завоевали рынок несколько сетевых СУБД; стандартом для такой модели стал CODASYL.


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

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

Кроме этой системы применяются и другие иерархические системы, включая TDMS (Time-Shared Data Management System компании), MARK IV (Multi-Access Retrieval System компании Control Data Corporation) и System-2000 (SAS-Institute).

И иерархические и сетевые СУБД были созданы в начале шестидесятых годов. IMS появилась в результате совместных усилий компаний IBM и North American Aviation (позднее Rockwell) по созданию СУБД для поддержки лунного проекта Аполлон – одного из самых крупных инженерных проектов того времени. Ключевым фактором при создании IMS была необходимость управления миллионами деталей, связанных друг с другом иерархическим способом. То есть, из небольших деталей были собраны более крупные узлы, которые входили в еще большие модули и т.д.

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

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

Хотя терминология иерархической модели несколько отличается от терминологии сетевой модели данных, существуют многие архитектурные аналогии. Как и в случае сетевой модели, с иерархической структурой данных связаны два основных параметра:

типы сегментов, или просто сегменты и типы отношений предок-потомок (типы ОПП).

Сегмент аналогичен типу записей сетевой модели. Тип ОПП аналогичен типу набора сетевой модели, за исключением того, что тип сегмента может являться потомком только для одного типа ОПП.

Иерархическую структуру данных задают три объекта:

1. деревья,
   
2. сегменты
   
3. поля сегментов.
   

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

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

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

Для приложений с иерархической структурой и устойчивыми транзакциями запросов иерархическая модель может оказаться вполне удовлетворительной. Тот факт, что было установлено около 7000 IMS, подтверждает этот вывод, хотя некоторые из владельцев таких систем переходят к реляционным системам.

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

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

Иерархическая МД основана на структуре, имеющей сходство, с перевернутым деревом, где от ствола отходят ветви от которых в свою очередь отходят другие ветви.

Причины необходимости изучения Иерархической модели.

- Основные идеи этой модели БД лежат в основе разработки современных БД

- Ограничения, имеющиеся в иерархической модели, позволяют по новому взглянуть на проектирование БД

Основные понятия: Иерархическая модель представляет собой иерархию сегментов- которые эквивалентны записям в системе файлов.

Рассмотрим упрощенную процедуру создания картотеки

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

Каждый узел состоит из более мелких сборок (ручка, ролики ит.д.)


Каждая сборка состоит из нескольких деталей

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

Описание этого процесса помогает представить весь этот логический процесс в виде перевернутого дерева , которое называют иерархической структурой


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


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

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


Каждый предок может иметь несколько потомков

Каждый потомок имеет только одного предка

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

Например:

Изделие-Узел А-Сборка А-Деталь А-Деталь В-УзелВ

УзелС-СборкаВ-Деталь С-ДетальД

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

На иерерхической модели данных основано сравнительно ограниченной количество СУБД, в том числе IMS, PS/Focus, Team-Up, Data Edge,Ока,

Для организации физического размещения иерархических данных в памяти ЭВМ используются следующие методы

• представление линейным списком с последовательным распределением памяти
  
• представление связными линейными списками
  

Первые системы управления базами данных использовали иерархическую модель данных, и во времени их появление предшествует появлению сете­вой модели. Для иерархической модели данных стандарты не разрабатыва­лись, и ее изучение может быть осуществлено путем рассмотрения реально существующих СУБД. Самой известной СУБД, использующей модель дан­ных этого типа, является система фирмы IBM — Information Management System (IMS). Именно эта система зарегистрирована как первая промышлен­ная СУБД. Она была создана для поддержки лунного проекта "Аполлон" и призвана была управлять огромным количеством деталей, иерархически свя­занным между собой — из деталей собирались узлы, которые входили в еще более крупные модули и так далее. Поскольку структур данных с такой орга­низацией существует достаточно много, а системы с иерархической моделью данных работают достаточно эффективно и проще в реализации, чем сетевые, то нетрудно понять истоки популярности в свое время подобных систем.

4.3.1. Структурная часть иерархической модели

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

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

Иерархическая модель представляет собой связный неориентированный граф древовидной структуры, объединяющий сегменты. Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева, а не произвольных графов. При этом граф — дерево обладает следующими свойствами (рис. 4.13):

1. имеется только одна вершина графа — корень, в которую не заходит ни
   одно ребро;
   
2. имеются вершины графа я-ro уровня, называемые исходными, куда захо­
   дит одно ребро (л — 1) уровня; исходит из этого узла ноль, один или
   несколько порожденных узлов, которые называются потомками;
   
3. единственный проход к порожденному узлу лежит через его исходный узел;
   
4. каждый потомок может иметь только одного предка;
   
5. нет замкнутых петель или циклов;
   
6. сегмент, у которого нет потомков, называется листовым сегментом.
   

Рис. 4.13. Иерархическая модель данных

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


деревом оп­ределений. Вершины графа — типы сегментов — не должны быть простыми.


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

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

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

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