кафедра компьютерных и информационных технологий

курс лекций

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

Основное назначение данного курса - систематическое введение в идеи и методы, используемые в современных системах управления базами данных. В курсе не рассматривается какая-либо одна популярная СУБД; излагаемый материал в равной степени относится к любой современной системе. Как показывает опыт, без знания основ теории баз данных трудно на серьезном уровне работать с конкретными системами, как бы хорошо они не были документированы.

253

Содержание

• ЛЕКЦИЯ 1. Понятие СУБД. Функции СУБД 7
• 1.1 Введение 7
• 1.2 Понятие БД и СУБД 7
• 1.3 Уровни абстракции в СУБД. Функции абстрактных данных 9
• 1.4 Представления 10
• 1.5 Функции СУБД 11
• 1.6 Экспертные системы и базы знаний 11
• ЛЕКЦИЯ 2. Модели БД 13
• 2.1 Обзор ранних (дореляционных) СУБД 13
• 2.2 Системы, основанные на инвертированных списках 13
• 2.3 Иерархическая модель 14
• 2.4 Сетевая модель 16
• 2.5 Основные достоинства и недостатки ранних СУБД 17
• ЛЕКЦИЯ 3. Реляционная модель и ее характеристики. Целостность в реляционной модели 18
• 3.1 Представление информации в реляционных БД 18
• 3.2 Домены 19
• 3.3 Отношения. Свойства и виды отношений 20
• 3.4 Целостность реляционных данных 21
• 3.5 Потенциальные и первичные ключи 22
• 3.6 Внешние ключи 22
• 3.7 Ссылочная целостность 23
• 3.8 Значения NULL и поддержка ссылочной целостности 24
• ЛЕКЦИЯ 4. Реляционная алгебра 25
• 4.1 Понятие реляционной алгебры 25
• 4.2 Замкнутость в реляционной алгебре 25
• 4.3 Традиционные операции над множествами 25
• 4.4 Свойства основных операций реляционной алгебры 27
• 4.5 Специальные реляционные операции 28
• ЛЕКЦИЯ 5. Вопросы проектирования БД 34
• 5.1 Понятие проектирования БД 34
• 5.2 Функциональные зависимости 35
• 5.3 Тривиальные и нетривиальные зависимости 36
• 5.4 Замыкание множества зависимостей и правила вывода Армстронга 36
• 5.5 Неприводимое множество зависимостей 38
• 5.6 Нормальные формы - основные понятия 38
• 5.7 Декомпозиция без потерь и функциональные зависимости 39
• 5.8 Диаграммы функциональных зависимостей 40
• ЛЕКЦИЯ 6. Проектирование БД. Нормальные формы отношений 42
• 6.1 Первая нормальная форма. Возможные недостатки отношения в 1НФ 42
• 6.2 Вторая нормальная форма. Возможные недостатки отношения во 2НФ 44
• 6.3 Третья нормальная форма. Возможные недостатки отношения в 3НФ 45
• 6.4 Нормальная форма Бойса-Кодда 46
• ЛЕКЦИЯ 7. Проектирование БД. Нормальные формы отношений (продолжение) 49
• 7.1 Многозначные зависимости 49
• 7.2 Четвертая нормальная форма 51
• 7.3 Зависимости соединения 51
• 7.4 Пятая нормальная форма 53
• 7.5 Итоговая схема процедуры нормализации 53
• ЛЕКЦИЯ 8. Проектирование БД методом сущность-связь. ER-диаграммы 55
• 8.1 Возникновение семантического моделирования 55
• 8.2 Основные понятия метода 55
• 8.3 Диаграммы ER-экземпляров и ER-типа 56
• 8.4 Правила формирования отношений 59
• 8.5 Методология IDEF1 (самостоятельное изучение) 62
• ЛЕКЦИЯ 9. Язык SQL 66
• 9.1 История создания и развития SQL 66
• 9.2 Основные понятия SQL 66
• 9.3 Запросы на чтение данных. Оператор SELECT 71
• 9.4 Многотабличные запросы на чтение (объединения). 75
• ЛЕКЦИЯ 10. Язык SQL (продолжение) 77
• 10.1 Объединения и стандарт SQL2 77
• 10.2 Итоговые запросы на чтение. Агрегатные функции 80
• 10.3 Запросы с группировкой (предложение GROUP BY) 80
• 10.4 Вложенные запросы 82
• ЛЕКЦИЯ 11. Язык SQL. (продолжение) 86
• 11.1 Внесение изменений в базу данных. 86
• 11.2 Удаление существующих данных (Оператор DELETE) 87
• 11.3 Обновление существующих данных (Оператор UPDATE) 87
• 11.4 Определение структуры данных в SQL 88
• 11.5 Понятие представления. 91
• 11.6 Представления в SQL. 92
• 11.7 Системный каталог (самостоятельное изучение) 93
• ЛЕКЦИЯ 12. Обеспечение безопасности БД 99
• 12.1 Общие положения 99
• 12.2 Методы обеспечения безопасности 100
• 12.3 Избирательное управление доступом 101
• 12.4 Обязательное управление доступом 102
• 12.5 Шифрование данных 102
• 12.6 Контрольный след выполняемых операций 102
• 12.7 Поддержка мер обеспечения безопасности в языке SQL 103
• 12.8 Директивы GRANT и REVOKE 103
• 12.9 Представления и безопасность 105
• ЛЕКЦИЯ 13. Физическая организация БД: структуры хранения и методы доступа 106
• 13.1 Доступ к базе данных 106
• 13.2 Кластеризация 108
• 13.3 Индексирование 108
• 13.4 Структуры типа Б-дерева 111
• 13.5 Хеширование 114
• ЛЕКЦИЯ 14. Оптимизация запросов 116
• 14.1 Оптимизация в реляционных СУБД. 116
• 14.2 Пример оптимизации реляционного выражения 116
• 14.3 Обзор процесса оптимизации 117
• 14.4 Преобразование выражений 119
• ЛЕКЦИЯ 15. Восстановление после сбоев 123
• 15.1 Понятие восстановления системы 123
• 15.2 Транзакции 123
• 15.3 Алгоритм восстановления после сбоя системы 125
• 15.4 Параллелизм. Проблемы параллелизма 127
• 15.5 Понятие блокировки 129
• 15.6 Решение проблем параллелизма 130
• 15.7 Тупиковые ситуации 132
• 15.8 Способность к упорядочению 133
• 15.9 Уровни изоляции транзакции 134
• 15.10 Поддержка в языке SQL 135
• ЛЕКЦИЯ 16. Технологии СУБД 136
• 16.1 Распределенные базы данных 136
• 16.2 Принципы функционирования распределенной БД 136
• 16.3 Системы типа клиент/сервер 139
• 16.4 Серверы баз данных 139
• ЛЕКЦИЯ 17. Современные постреляционные модели БД 141
• 17.1 Системы управления базами данных следующего поколения 141
• 17.2 Ориентация на расширенную реляционную модель 141
• 17.3 Объектно-ориентированные СУБД 143

ЛЕКЦИЯ 1. Понятие СУБД. Функции СУБД

• 1.1 Введение
• 1.2 Понятие БД и СУБД
• 1.3 Уровни абстракции в СУБД. Функции абстрактных данных
• 1.4 Представления
• 1.5 Функции СУБД
• 1.6 Экспертные системы и базы знаний

1.1 Введение

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

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

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

В настоящее время ведутся исследования в следующих направлениях:

1. дедуктивные системы;

2. экспертные системы;

3. расширяемые системы;

4. объектно-ориентированные системы.

1.2 Понятие БД и СУБД

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

Система баз данных включает в себя (рис. 1.1):

1. данные, непосредственно сохраняемые в базе данных;

2. аппаратное обеспечение;

3. программное обеспечение;

4. пользователей:

4.1. прикладные программисты;

4.2. конечные пользователи;

4.3. администраторы баз данных.

рис. 1.1 Система баз данных.

1.2.1 Данные.

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

1.2.2 Аппаратное обеспечение.

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

1.2.3 Программное обеспечение.

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

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

1.2.4 Пользователи.

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

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

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

Функции администратора базы данных:

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

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

3. Взаимодействие с пользователями. Администратор БД обеспечивает пользователей необходимыми им данными. Для этого администратор БД должен написать (или оказать пользователям помощь в написании) необходимых внешних схем. Кроме этого необходимо определить отображение между внешней и концептуальной схемами.

4. Определение правил безопасности и целостности.

5. Определение процедур резервного копирования и восстановления.

6. Управление производительностью и реагирование на изменяющиеся требования.

База данных состоит из некоторого набора постоянных данных, которые используются прикладными системами какого-либо предприятия. Под словом "постоянные" подразумеваются данные, которые отличаются от других, более изменчивых данных, таких, как промежуточные данные и вообще все транзитные данные. "Постоянные" данные на самом деле могут недолго оставаться таковыми, поскольку данные в БД должны отражать об изменчивых объектах реального мира и отношениях между ними.

Использование баз данных для хранения информации позволяет организовать централизованное управление данными, что обеспечивает следующие преимущества:

1. возможность сокращения избыточности;

2. возможность устранения (до некоторой степени) противоречивости;

3. возможность общего доступа к данным;

4. возможность соблюдения стандартов;

5. возможность введения ограничений для обеспечения безопасности

6. возможность обеспечения целостности данных;

7. возможность сбалансировать противоречивые требования;

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

1.3 Уровни абстракции в СУБД. Функции абстрактных данных

Существует 3 уровня архитектуры СУБД (рис. 1.2):

1. Внутренний уровень - наиболее близкий к физическому хранению. Он связан со способами хранения информации на физических устройствах хранения;

2. Внешний уровень - наиболее близкий к пользователям. Он связан со способами представления данных для отдельных пользователей;

3. Концептуальный уровень - является промежуточным между двумя первыми. Этот уровень связан с обобщенными представлениями пользователей, в отличие от внешнего уровня, связанного с индивидуальными представлениями пользователей.

1.4 Представления

Соответственно трем уровням архитектуры выделяют три уровня абстракции данных в СУБД.

1.4.1 Внешний уровень - внешнее представление

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

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

1.4.2 Концептуальный уровень - концептуальное представление

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

1.4.3 Внутренний уровень - внутреннее представление

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

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

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

1.5 Функции СУБД

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

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

3. Безопасность и целостность данных. СУБД должна контролировать запросы и пресекать попытки нарушения правил безопасности и целостности.

4. Восстановление данных и дублирование. СУБД должна обеспечить восстановление данных после сбоев.

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

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

1.6 Экспертные системы и базы знаний

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

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

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

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

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

Литература:

1. Дейт К.Дж. Введение в системы баз данных. -Пер. с англ. -6-е изд. -К. Диалектика, 1998. Стр. 36-75.

ЛЕКЦИЯ 2. Модели БД

• 2.1 Обзор ранних (дореляционных) СУБД
• 2.2 Системы, основанные на инвертированных списках
• 2.3 Иерархическая модель
• 2.4 Сетевая модель
• 2.5 Основные достоинства и недостатки ранних СУБД

2.1 Обзор ранних (дореляционных) СУБД

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

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

Рассмотрим некоторые наиболее общие характеристики ранних систем:

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

2. Все ранние системы не основывались на каких-либо абстрактных моделях. Понятие модели данных фактически вошло в обиход специалистов в области БД только вместе с реляционным подходом. Абстрактные представления ранних систем появились позже на основе анализа и выявления общих признаков у различных конкретных систем.

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

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

5. После появления реляционных систем большинство ранних систем было оснащено "реляционными" интерфейсами. Однако в большинстве случаев это не сделало их по_настоящему реляционными системами, поскольку оставалась возможность манипулировать данными в естественном для них режиме.

2.2 Системы, основанные на инвертированных списках

К числу наиболее известных и типичных представителей таких систем относятся Datacom/DB компании Applied Data Research, Inc. (ADR), ориентированная на использование на машинах основного класса фирмы IBM, и Adabas компании Software AG.

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

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

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

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

2. Физическая упорядоченность строк всех таблиц может определяться и для всей БД (так делается, например, в Datacom/DB).

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

2.2.2 Манипулирование данными

Поддерживаются два класса операторов:

1. Операторы, устанавливающие адрес записи, среди которых:

1.1. прямые поисковые операторы (например, найти первую запись таблицы по некоторому пути доступа);

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

2. Операторы над адресуемыми записями

Типичный набор операторов:

1. Найти первую запись таблицы T в физическом порядке;

2. Найти первую запись таблицы T с заданным значением ключа поиска K;

3. Найти запись, следующую за записью с заданным адресом в заданном пути доступа;

4. Найти следующую запись таблицы T в порядке пути поиска с заданным значением K;

5. Найти первую запись таблицы T в порядке ключа поиска K cо значением ключевого поля, большим заданного значения K;

6. Выбрать запись с указанным адресом;

7. Обновить запись с указанным адресом;

8. Удалить запись с указанным адресом;

9. Включить запись в указанную таблицу; операция генерирует адрес записи.

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

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

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

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

2.3.1 Иерархические структуры данных

Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева.

Тип дерева (рис. 2.1) состоит из одного "корневого" типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи.

рис. 2.1 Пример типа дерева (схемы иерархической БД)

Здесь (рис. 2.1) Группа является предком для Куратора и Студенты, а Куратор и Студенты - потомки Группа. Между типами записи поддерживаются связи.

База данных с такой схемой могла бы выглядеть следующим образом (рис. 2.2):

рис. 2.2 Один экземпляр дерева.

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

В IMS использовалась оригинальная и нестандартная терминология: "сегмент" вместо "запись", а под "записью БД" понималось все дерево сегментов.

2.3.2 Манипулирование данными

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

1. Найти указанное дерево БД (например, отдел 310);

2. Перейти от одного дерева к другому;

3. Перейти от одной записи к другой внутри дерева (например, от отдела - к первому сотруднику);

4. Перейти от одной записи к другой в порядке обхода иерархии;

5. Вставить новую запись в указанную позицию;

6. Удалить текущую запись.

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

Автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя. Заметим, что аналогичное поддержание целостности по ссылкам между записями, не входящими в одну иерархию, не поддерживается (примером такой "внешней" ссылки может быть содержимое поля Каф_Номер в экземпляре типа записи Куратор).

В иерархических системах поддерживалась некоторая форма представлений БД на основе ограничения иерархии. Примером представления приведенной выше БД может быть иерархия, изображенная на рис. 2.3.

рис. 2.3 Пример представления иерархической БД.

2.4 Сетевая модель

Типичным представителем является Integrated Database Management System (IDMS) компании Cullinet Software, Inc., предназначенная для использования на машинах основного класса фирмы IBM под управлением большинства операционных систем. Архитектура системы основана на предложениях Data Base Task Group (DBTG) Комитета по языкам программирования Conference on Data Systems Languages (CODASYL), организации, ответственной за определение языка программирования Кобол. Отчет DBTG был опубликован в 1971г., а в 70-х годах появилось несколько систем, среди которых IDMS.

2.4.1 Сетевые структуры данных

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

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

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

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

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

На формирование типов связи не накладываются особые ограничения; возможны, например, следующие ситуации:

1. Тип записи потомка в одном типе связи L1 может быть типом записи предка в другом типе связи L2 (как в иерархии).

2. Данный тип записи P может быть типом записи предка в любом числе типов связи.

3. Данный тип записи P может быть типом записи потомка в любом числе типов связи.

4. Может существовать любое число типов связи с одним и тем же типом записи предка и одним и тем же типом записи потомка; и если L1 и L2 - два типа связи с одним и тем же типом записи предка P и одним и тем же типом записи потомка C, то правила, по которым образуется родство, в разных связях могут различаться.

5. Типы записи X и Y могут быть предком и потомком в одной связи и потомком и предком - в другой.

6. Предок и потомок могут быть одного типа записи.

рис. 2.4 Простой пример сетевой схемы БД.

2.4.2 Манипулирование данными

Примерный набор операций может быть следующим:

1. Найти конкретную запись в наборе однотипных записей (инженера Сидорова);

2. Перейти от предка к первому потомку по некоторой связи (к первому сотруднику отдела 310);

3. Перейти к следующему потомку в некоторой связи (от Сидорова к Иванову);

4. Перейти от потомка к предку по некоторой связи (найти отдел Сидорова);

5. Создать новую запись;

6. Уничтожить запись;

7. Модифицировать запись;

8. Включить в связь;

9. Исключить из связи;

10. Переставить в другую связь и т.д.

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

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

2.5 Основные достоинства и недостатки ранних СУБД

Сильные места ранних СУБД:

1. Развитые средства управления данными во внешней памяти на низком уровне;

2. Возможность построения вручную эффективных прикладных систем;

3. Возможность экономии памяти за счет разделения подобъектов (в сетевых системах).

Недостатки:

1. Слишком сложно пользоваться;

2. Фактически необходимы знания о физической организации;

3. Прикладные системы зависят от этой организации;

4. Их логика перегружена деталями организации доступа к БД.

Литература:

1. Сергей Кузнецов, “Основы современных баз данных”. Центр Информационных Технологий, http://www.citforum.ru/database/osbd/contents.shtml

ЛЕКЦИЯ 3. Реляционная модель и ее характеристики. Целостность в реляционной модели

• 3.1 Представление информации в реляционных БД
• 3.2 Домены
• 3.3 Отношения. Свойства и виды отношений
• 3.4 Целостность реляционных данных
• 3.5 Потенциальные и первичные ключи
• 3.6 Внешние ключи
• 3.7 Ссылочная целостность
• 3.8 Значения NULL и поддержка ссылочной целостности

3.1 Представление информации в реляционных БД

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

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

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

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

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

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

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

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

В реляционной модели рассматриваются три аспекта данных:

1. структура данных (объекты данных);

2. целостность данных;

3. обработка данных (операторы).

Рассмотрим специальную терминологию, применяемую в рамках аспекта "структура данных" (рис. 3.1).

рис. 3.1 Отношение.

3.2 Домены

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

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

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

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

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

3.3 Отношения. Свойства и виды отношений

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

Отношение R, определенное на множестве доменов D1, D2, …, Dn (не обязательно различных), содержит две части - заголовок и тело:

1. заголовок содержит фиксированное множество атрибутов или, точнее, пар <имя_атрибута : имя_домена>:

2. {<A1:D1>, <A2:D2>, …, <An:Dn>},
причем каждый атрибут Aj соответствует одному и только одному из лежащих в основе доменов Dj (j=1,2, …, n). Все имена атрибутов A1, A2, …, An разные.

3. Тело состоит из множества кортежей. Каждый кортеж, в свою очередь содержит множество пар <имя_атрибута : значение_атрибута>:
{<A1:Vi1>, <A2:Vi2>, …, <An:Vin>},
(i=1, 2, …, m, где m - количество кортежей в этом множестве). В каждом таком кортеже есть одна такая пара <имя_атрибута : значение_атрибута>, т.е. <Aj:Vij>, для каждого атрибута Aj в заголовке. Для любой такой пары <Aj:Vij> Vij является значением из уникального домена Dj, который связан с атрибутом Aj.

Значения m и n называются соответственно кардинальным числом и степенью отношения R.

3.3.1 Свойства отношений

1. В отношении отсутствуют одинаковые кортежи.

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

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

2. Кортежи не упорядочены сверху вниз.

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

3. атрибуты не упорядочены слева на право.

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

4. все значения атрибутов атомарные.

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

3.3.2 Виды отношений

Определим некоторые виды отношений, встречающиеся в реляционных системах.

1. Именованное отношение - это переменная отношения, определенная в СУБД посредством операторов создания отношений.

2. Базовым отношением называется именованное отношение, которое не является производным (т.е. базовое отношения является автономным).

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

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

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

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

7. Результатом запроса называется неименованное производное отношение, служащее результатом некоторого определенного запроса.

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

9. Хранимое отношение - отношение, которое поддерживается непосредственно в физической памяти.

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

Например: студент с номером SNo имеет фамилию SurName и проживает в городе City. При этом нет двух студентов с одинаковыми номерами.

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

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

3.4 Целостность реляционных данных

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

3.5 Потенциальные и первичные ключи

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

1. Свойство уникальности - нет двух разных кортежей в отношении R с одинаковым значением K.

2. Свойство не избыточности - никакое из подмножеств K не обладает свойством уникальности.

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

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

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

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

3. Понятие не избыточности. Если определить "потенциальный ключ" не являющийся не избыточным, системе не будет известно об этом и она не сможет обеспечить должным образом соответствующее ограничение целостности. Например: в отношении с данными о студентах можно определить избыточный потенциальный ключ, состоящий из уникального кода студента StNo и названия города, в котором он проживает City. В таком случае система не сможет соблюдать ограничение, обеспечивающее уникальность номера студента в глобальном смысле, вместо этого будет выполняться более слабое ограничение, обеспечивающее уникальность номера студента в пределах города.

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

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

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

3.6 Внешние ключи

Пусть R2 - базовое отношение. Тогда внешний ключ - FK в отношении R2 - это подмножество множества атрибутов R2 такое, что:

1. существует базовое отношение R1 (R1 и R2 не обязательно различны) с потенциальным ключом CK.

2. каждое значение FK в текущем значении R2 всегда совпадает со значением CK некоторого кортежа в текущем значении R1.

Следует отметить, что:

1. Внешние ключи как и потенциальные определены как множества атрибутов.

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

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

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

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

6. Связи, существующие в базе данных отображают с помощью ссылочных диаграмм. Groups Students Cities

7. Отношение может быть и ссылочным и ссылающимся одновременно Students Groups Department

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

9. Самоссылающиеся отношения представляют собой частный случай ситуации, когда могут возникнуть ссылочные циклы, которые можно отобразить на ссылочной диаграмме следующим образом: Rn R(n-1) R(n-2) … R2 R1 Rn

3.7 Ссылочная целостность

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

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

3.7.1 Правила внешних ключей

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

1. При попытке удалить объект ссылки внешнего ключа:

1.1. Ограничить - приостановить операцию удаления, до момента, когда не будет существовать ссылающихся объектов.

1.2. Каскадировать - каскадировать операцию удаления, удалив соответствующие ссылающиеся объекты.

2. При попытке обновить потенциальный ключ, на который ссылается внешний ключ:

2.1. Ограничить - приостановить операцию обновления, до момента, когда не будет существовать ссылающихся объектов.

2.2. Каскадировать - каскадировать операцию обновления, обновив значение внешнего ключа в соответствующих ссылающихся объектах.

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

3.8 Значения NULL и поддержка ссылочной целостности

Значения NULL используются для обозначения факта отсутствия информации. Например: дата рождения человека может быть неизвестна. При этом следует учесть, что значения NULL отличаются от числового значения 0 или символьных пробелов. Значение NULL вообще не является реальным значением. Для данного атрибута может быть разрешено или запрещено содержать значения NULL.

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

Правило ссылочной целостности также должно быть расширено с учетом возможности присутствия значений NULL.

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

Литература:

1. Дейт К.Дж. Введение в системы баз данных. -Пер. с англ. -6-е изд. -К. Диалектика, 1998. Стр. 79-134.

ЛЕКЦИЯ 4. Реляционная алгебра

• 4.1 Понятие реляционной алгебры
• 4.2 Замкнутость в реляционной алгебре
• 4.3 Традиционные операции над множествами
• 4.4 Свойства основных операций реляционной алгебры
• 4.5 Специальные реляционные операции

4.1 Понятие реляционной алгебры

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

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