- •Введение
- •Глава 1. Проектирование баз данных
- •1.1. История развития баз данных и субд
- •1.2. Введение в субд
- •1.2.1. Основные термины, понятия и определения
- •1.2.2. Классификация субд
- •1) Сетевые, корпоративные, распределенные, клиент-серверные, полнофункциональные, масштабируемые, “большие” субд.
- •2) Локальные, персональные, настольные, файл-серверные, “малые” субд.
- •1.3. Модели данных
- •1.3.1. Типы связей между объектами
- •1.3.2. Формы записи инфологической (концептуальной) модели
- •1.3.3. Уровни представления и независимости данных
- •1.3.4. Порядок взаимодействия пользователя, субд и ос
- •1.3.5. Поддержка целостности базы данных
- •1.3.6. Иерархическая модель
- •1.3.7. Сетевая модель
- •1.3.8. Реляционная модель
- •1.3.8.1. Отношения
- •1.3.8.2. Теоретико-множественные операции с отношениями
- •1.3.8.3. Правила Кодда
- •1.3.8.4. Индексирование таблиц
- •1.3.8.5. Связывание таблиц
- •1.3.9. Постреляционная модель
- •1.3.10. Многомерная модель
- •1.3.11. Объектно‑ориентированная модель
- •1.4. Модели использования баз данных в сети
- •1.4.1. Сеть
- •1.4.2. Модели использования баз данных
- •1.4.2.1. Локальная однопользовательская модель
- •1.4.2.2. Файл-серверная модель
- •1.4.2.3. Клиент-серверная модель
- •В моделях «клиент–сервер»
- •1.4.2.4. Модель удаленного доступа (rda)
- •1.4.2.5. Модель сервера данных
- •1.4.2.6. Трехзвенная распределенная модель
- •1.4.2.7. Модели серверов баз данных
- •1.4.2.8. Клиент-Интернет
- •1.4.2.9. ИнтерфейсOdbc
- •1.4.3. Мониторы обработки транзакций (tpm)
- •1.4.4. Децентрализованное управление базами данных
- •1.4.5. Таблицы в локальных сетях
- •1.5. Проектирование баз данных
- •1.5.1. Принципы и этапы проектирования и создания баз данных
- •1.4.Определение доменов атрибутов.
- •1.5. Определение первичных и вторичных ключей.
- •1.6. Определение суперклассов и подклассов для типов сущностей.
- •1.7. Создание er‑диаграмм для отдельных пользователей.
- •2.6. Создание er‑диаграмм для отдельных пользователей.
- •3.4. Создание er‑диаграммы глобальной логической модели.
- •4. Создание глобальной логической модели в среде целевой субд.
- •6. Разработка механизма защиты.
- •1.5.3. Правила формирования взаимосвязанных таблиц
- •1.5.4. Модели жизненного цикла и проектирование баз данных
- •1.5.4.1. Модели жизненного цикла
- •1.5.4.2. Обследование, системный анализ и постановка задачи
- •1.5.4.3. Инфологическое проектирование
- •1.5.4.4. Датологическое проектирование
- •1.5.4.5. Проектирование физической модели
- •1.5.4.6. Реализация, интеграция и внедрение
- •1.5.5. Выбор субд
- •1.5.5.1. Сравнение Visual FoxPro, Access, sql Server, Oracle и Excel
- •1.5.5.2. Методика балловой оценки программных средств
- •1.5.6. Case‑средства автоматизации проектирования
- •1. Ориентация на этапы жизненного цикла
- •2. Функциональная полнота
- •Пользователя в ms sql Server 7.0
- •1.6.2. Резервирование информации
- •1.6.3. Варианты разработки приложений
- •1.7. Стандартизация баз данных
- •1.8. ЯзыкSql
- •1.8.1. Введение вSql
- •1.8.2. Типы данныхSql
- •1.8.3. Оператор выбора данныхSelect
- •1.8.3.1. Назначение и синтаксис оператора
- •1.8.3.2. Объединение таблиц
- •1.8.3.3. Вложенные и коррелированные запросы
- •1.8.3.4. Запросы, использующиеExist, any, all
- •1.8.3.5. Стандартные функции
- •1.8.3.6. Запрос с группировкой
- •1.8.4. Операторы обновления базы
- •1.8.4.1. Оператор корректировки данныхUpdate
- •1.8.4.2. Оператор удаления записейDelete
- •1.8.4.3. Оператор включения записей insert
- •1.8.5. Представления
- •1.9. Транзакции
- •1.9.1. Определение транзакций
- •1.9.2. Организация транзакций
- •1.9.3. Журнал транзакций
- •1.9.4. Журнализация и буферизация
- •1.9.5. Индивидуальный откат транзакций
- •1.9.6. Восстановление после мягкого сбоя
- •1.9.7. Физическая согласованность базы данных
- •1.9.8. Восстановление после жесткого сбоя
- •1.9.9. Параллельное выполнение транзакций
- •1.9.10. Уровни изолированности пользователей
- •1.9.11. Гранулированные синхронизационные захваты
- •1.9.12. Предикатные синхронизационные захваты
- •1.9.13. Метод временных меток
- •1.10. ВстроенныйSql
- •1.10.1. Особенности встроенногоSql
- •1.10.2. Определение курсора
- •1.10.3. Открытие курсора
- •1.10.4. Чтение очередной строки курсора
- •1.10.5. Закрытие курсора
- •1.10.6. Удаление и обновление данных
- •1.10.7. Хранимые процедуры
- •Хранимой процедуры на сервере
- •1.10.8. Триггеры
- •1.10.9. ДинамическийSql
- •1.11. Архитектура субд и оптимизация запросов
- •1.12. Перспективы развития субд
- •Вопросы для самопроверки и контроля
- •1Оглавление
1.3.6. Иерархическая модель
Иерархическая модель (дерево) представляет собой связанный ориентированный граф, у которого любой подчиненный узел (кроме корневого) имеет только один исходный узел (рисунок 1.3.6.1).
Рисунок 1.3.6.1. Пример иерархической структуры
Рассмотрим ряд терминов иерархической модели.
Высота, вес и момент дерева‑ число уровней, листьев и узлов в дереве.
Путь доступа ‑совокупность узлов и дуг, проходя которые можно прийти к искомому узлу.
Сцепленный ключ ‑соединение в один ключ всех ключей узлов на пути доступа к искомому узлу в порядке их обхода. Такой ключ обеспечивает наиболее простой и быстрый доступ к искомому узлу.
Сбалансированное дерево- дерево, в котором любой исходный узел имеет одинаковую степень (одинаковое число ветвей или подчиненных узлов).
Бинарное (двоичное) дерево‑ сбалансированное дерево с исходными узлами степени два. Любое дерево можно преобразовать в бинарное дерево. Поиск данных в бинарном дереве наиболее быстрый.
Один экземпляр дерева хранится в виде списка данных узлов, полученного левосторонним обходом дерева (сверху вниз и справа налево).
Основные операции над записями (узлами): поиск нужной записи по ключу, переход от исходного к первому подчиненному узлу, переход к следующему подобному узлу, возврат к исходному узлу, удаление текущего узла и всех его подчиненных, вставка нового узла и обновление.
Иерархическая модель данных является наиболее простой среди всех даталогических моделей. Исторически она появилась первой: именно эту модель поддерживает первая из зарегистрированных промышленных СУБД IMS фирмы IBM.
Рассмотрим основные понятия этой СУБД.
Основными информационными единицами в иерархической модели являются: база данных (БД), сегмент и поле.
Поле данных - это минимальная, неделимая единица данных, доступная пользователю с помощью СУБД.
Сегмент – это запись, при этом определяются два понятия:тип сегмента илитип записи иэкземпляр сегмента илиэкземпляр записи.
Тип сегмента - это поименованная совокупность типов элементов данных, в него входящих.
Экземпляр сегмента образуется из конкретных значений полей или элементов данных, в него входящих. Каждый тип сегмента в рамках иерархической модели образует некоторый набор однородных записей. Для возможности различия отдельных записей в данном наборе каждый тип сегмента должен иметь ключ или набор ключевых атрибутов (полей, элементов данных).
Ключ - это набор элементов данных, однозначно идентифицирующих экземпляр сегмента.
В иерархической модели сегменты объединяются в ориентированный древовидный граф (содержание этого и следующих параграфов скопировано из работы [19]). При этом полагают, что дуги отражают иерархические связи между сегментами: каждому экземпляру сегмента, стоящему выше по иерархии и соединенному с данным типом сегмента, соответствует несколько (множество) экземпляров данного (подчиненного) типа сегмента. Тип сегмента, находящийся на более высоком уровне иерархии, называется логически исходным по отношению к типам сегментов, соединенным с данным направленными иерархическими ребрами, которые в свою очередь называются логически подчиненными по отношению к этому типу сегмента. Иногда исходные сегменты называют сегментами-предками, а подчиненные сегменты называют сегментами-потомками.
Схема иерархической БД - это совокупность отдельных деревьев, каждое дерево в рамках модели называется физической базой данных.
Каждая физическая БД удовлетворяет следующим иерархическим ограничениям:
в каждой физической БД существует один корневой сегмент, то есть сегмент, у которого нет логически исходного (родительского) типа сегмента;
каждый логически исходный сегмент может быть связан с произвольным числом логически подчиненных сегментов;
каждый логически подчиненный сегмент может быть связан только с одним логически исходным (родительским ) сегментом.
Сегмент является экземпляром типа сегмента. Между экземплярами сегментов также существуют иерархические связи.
Экземпляры-потомки одного типа, связанные с одним экземпляром сегмента-предка, называют «близнецами». Набор всех экземпляров сегментов, подчиненных одному экземпляру корневого сегмента, называется физической записью. Количество экземпляров-потомков может быть разным для разных экземпляров родительских сегментов, поэтому в общем случае физические записи имеют разную длину.
В рамках иерархической модели выделяют языковые средства описания данных (DDL, Data Definition Language) и средства манипулирования данными (DML, Data Manipulation Language).
Каждая физическая база описывается набором операторов, определяющих как ее логическую структуру, так и структуру хранения БД. Описание начинается с оператора определения базы- DBD (Data Base Definition):
DBD Name = < имя БД>, ACCESS = < способ доступа>
Способ доступа определяет способ организации взаимосвязи физических записей.
Определено 4 способа доступа:
HDAM-hierarchical direct access method (иерархически прямой метод) - максимально быстрый, но не компактно хранящий данные;
HSAM-hierarchical sequential access method (иерархически последовательный метод) - наиболее медленный, но компактно хранящий данные;
HIDAM-hierarchical index direct access method (иерархически индексно-прямой метод) – компромиссный вариант, ближе кHDAM.
HISAM-hierarchical index sequential access method (иерархически индексно-последовательный метод) - компромиссный вариант, ближе кHSAM;
Каждая программа, пользователь или приложение определяет свою внешнюю модель. Внешняя модель представляет собой совокупность поддеревьев для физических баз данных, с которыми работает данный пользователь. Каждый подграф внешней модели в обязательном порядке должен содержать корневой тип сегмента соответствующей физической базы данных концептуальной модели.
Представление внешней модели называется логической базой данных и определяется совокупностью блоков связи данного приложения с физическими БД, входящими в концептуальную схему БД. Блок связи – РСВ, program communication bloc – описывает связь с одной физической БД. Совокупность блоков РСВ образует полное внешнее представление данного приложения, называемое «блоком спецификации программ»(PSB, program specification block).
При формировании исполнимого файла прикладной программы модуль с описанием базы данных и подсхемы (PSB) включались в исполнимый файл и использовались при выполнении программы.
Для организации физического размещения иерархических данных в памяти ЭВМ могут использоваться следующие группы методов:
представление линейным списком с последовательным распределением памяти (адресная арифметика, левосписковые структуры);
представление связными линейными списками (методы, использующие указатели и справочники).
К основным операциям манипулирования иерархически организованными данными относятся следующие:
поиск указанного экземпляра БД (например, дерева со значением 10 в поле Отд_номер);
переход от одного дерева к другому;
переход от одной записи к другой внутри дерева (например, к следующей записи типа Сотрудники);
ставка новой записи в указанную позицию;
удаление текущей записи и т. д.
В соответствии с определением типа "дерево", можно заключить, что между предками и потомками автоматически поддерживается контроль целостности связей. Основное правило контроля целостности формулируется следующим образом: потомок не может существовать без родителя, а у некоторых родителей может не быть потомков. Механизмы поддержания целостности связей между записями различных деревьев отсутствуют.
К достоинствам иерархической модели данных относятся эффективное использование памяти ЭВМ и неплохие показатели времени выполнения основных операций над данными. Иерархическая модель данных удобна для работы с иерархически упорядоченной информацией.
Недостатками иерархической модели являются ее громоздкость (для обработки информации с достаточно сложными логическими связями и сложность понимания для обычного пользователя) и жесткость(пока не будет создана логическая модель базы нельзя разрабатывать прикладные программы, и изменение структуры базы приводит к необходимости модифицировать прикладные программы).
На иерархической модели данных основано сравнительно ограниченное количество СУБД, в числе которых можно назвать зарубежные системы IMS, PC/Focus, Team-Up и Data Edge, а также отечественные системы Ока, ИНЭС и МИРИС.