Шехтман В.Е. Базы данных, SQL и все такое. Курс лекций

Подождите немного. Документ загружается.

Ф4

Яблоки

Ф5

Помидоры

Таблица 3.5 – Результат операции Маг2 \ Маг1

Шифр товара

Наименование

товара

Ф7

Груши

Как можно видеть из вышеприведенных примеров, Объединение и

Пересечение – коммутативны, Разность – нет.

В отличие от навигационных методов обработки данных, реляционные операции

гораздо более информативны, лаконичны и понятны пользователю (говорят, что они

манипуляционные).

Рассмотрим примеры запросов, которые можно сформулировать и эффективно

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

 Пример:

Пусть отношение МагО содержит список обязательного минимума товаров для

каждого магазина. Схема отношения МагО совпадает со схемами Маг1 и Маг2.

Какие продукты есть и в первом и во втором магазинах, но нет в МагО?

Ответ: (Маг1  Маг2) \ МагО .

Какие продукты есть в первом магазине, отсутствуют во втором магазине, но

входят в обязательный список?

Ответ: (Маг1 \ Маг2 )  МагО .

Какие продукты из обязательных есть и в первом и во втором магазинах?

Ответ: (Маг1  МагО)  (Маг2  МагО) .

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

магазинах?

Ответ: МагО \ (Маг1  Маг2) .



Предыдущие операции не меняли степени результирующего отношения. Новая

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

отношения.

Введем определение: сцеплением кортежей с = <c

, …, c

> и q = <q

, …, q

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

кортежа:

(c, q) = <c

, …, c

, q

, …, q

3.1.4 Расширенное декартово произведение отношения R1 со схемой S

= (A

…, A

) и отношения R2 со схемой S

= (B

, …, B

) – это отношение R3 степени n+m со

схемой S

= (A1, …, An, B1, …, Bm), содержащее кортежи, полученные сцеплением

каждого картежа R1 с каждым кортежем R2.

R1 = {r}, R2 = {q}

R1  R2 = {(r, q) | r  R1  q  R2}

Ввиду возможности перестановки атрибутов в отношении,  - коммутативна.

Эта операция обычно используется для получения универсума – всех мыслимых

возможностей.

 Пример:

Пусть МагО содержит следующие кортежи:

(Ф1, Бананы)

(Ф9, Апельсины)

(Ф11, Ананасы)

Введем отношение Магазины – оно просто перечисляет имеющиеся магазины (таблица

3.6).

Таблица 3.6 – Отношение Магазины

Наименование

магазина

Привет

Ласточка

Рябинка

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

(таблица 3.7):

МагО  Магазины

Таблица 3.7 – Результат операции МагО



Магазины

Шифр товара

Наименование

товара

Наименование

магазина

Ф1

Бананы

Привет

Ф1

Бананы

Ласточка

Ф1

Бананы

Рябинка

Ф9

Апельсины

Привет

Ф9

Апельсины

Ласточка

Ф9

Апельсины

Рябинка

Ф11

Ананасы

Привет

Ф11

Ананасы

Ласточка

Ф11

Ананасы

Рябинка

Введем отношение МагР – оно хранит сведения о фактическом наличии товаров

в каждом из магазинов (таблица 3.8).

Таблица 3.8 – Отношение МагР

Шифр товара

Наименовани

е товара

Наименовани

е магазина

Ф1

Бананы

Привет

Ф1

Бананы

Ласточка

Ф9

Апельсины

Ласточка

Ф9

Апельсины

Рябинка

Ф11

Ананасы

Привет

Какие продукты из списка обязательных (МагО) отсутствуют в каких магазинах

(таблица 3.9)? Ответ на вопрос даѐт выражение:

МагО  Магазины \ МагР

Таблица 3.9 – Магазины и отсутствующие в них продукты из спискаа обязательных

Шифр товара

Наименовани

е товара

Наименовани

е магазина

Ф1

Бананы

Рябинка

Ф9

Апельсины

Привет

Ф11

Ананасы

Ласточка

Ф11

Ананасы

Рябинка



Набор из 4 теоретико-множественных операций избыточен т.к. например

R1  R2 = (R1  R2) \ (R1 \ R2) \ (R2 \ R1)

или

R1  R2 = R1 \ (R1 \ R2)

3.2 Специальные операции реляционной алгебры

3.2.1 Горизонтальный выбор (горизонтальная фильтрация, ограничение

отношения).

Пусть α – булевское выражение (предикат) над атрибутами отношения,

например:

A1 > 10 или A2 = ‗Новокузнецк‘

Отношение sel

R = {r | r  R  α( r ) = True}

 Пример:

sel

Шифр товара = ‗Ф1‘

МагР (таблица 3.10).

Таблица 3.10 – Результат операции горизонтального выбора

Шифр

товара

Наименование

товара

Наименование

магазина

Ф1

Бананы

Привет

Ф1

Бананы

Ласточка



3.2.2 Проектирование (вертикальная фильтрация).

Проекция отношения R на набор атрибутов B ( записывается proj

R ) –

отношение, содержащее только атрибуты из набора B, с кортежами, полученными из

кортежей R путем удаления дубликатных кортежей.

 Пример:

Чтобы выяснить, в каких магазинах имеются в продаже Бананы и Апельсины

необходимо выполнить две операции:

1. R = sel

НаименованиеТовара = ‗Бананы‘ OR НаименованиеТовара = ‗Апельсины‘

МагР

2. R1 = proj

Наименование магазина

Эти две операции можно записать в виде одной длинной, задав приоритет

выполнения скобками ( и ):

R1 = proj

Наименование магазина

(sel

НаименованиеТовара = ‗Бананы‘ OR НаименованиеТовара = ‗Апельсины‘

МагР)



До сих пор рассматривались унарные специальные операции. Следующие

операции бинарные.

3.2.3 Условное соединение

Пусть отношение R = {r}, отношение Q = {q}. S

= (A

, …, A

), S

= (B

, …, B

Набор атрибутов A принадлежит {A

}, i=1,k; набор атрибутов B принадлежит {B

j=1,m. A и B состоят из Θ-сравнимых атрибутов (по поводу Θ-сравнимости см.

предыдущий раздел).

Соединение отношений R и Q при условии β (записывается R join

Q) – это

подмножество декартова произведения RQ, кортежи которого удовлетворяют

условию β.

R join

Q = {(r, q) | (r, q) | r.A Θ q.B = True, I=1, k}

 Пример:

Введем в рассмотрение отношение МагП, указывающее поставщиков

соответствующих товаров (таблица 3.11).

Таблица 3.11 – Товары и их поставщики

Шифр

товара

Наименование

товара

Поставщик

Ф1

Бананы

Глобус

Ф2

Арбузы

Центрпродсервис

Ф3

Авокадо

Голбус

Ф4

Яблоки

Глобус

Ф5

Помидоры

Центрпродсервис

Ф6

Фейхоа

Глобус

Ф11

Ананасы

Центрпродсервис

Какие продукты из имеющихся в магазине ―Привет‖ были поставлены фирмой

―Глобус‖ (ответ приведен в таблице 3.12)?

proj

НаименованиеТовара

( МагП join

МагП.ШифрТовара = МагР.ШифрТовара) AND

МагР.НаименованиеМагазина = ‖Привет‖ AND

МагП.Поставщик = ―Голбус‖

МагР )

Таблица 3.12 – Товары из ―Привета‖ поставленные фирмой ―Глобус‖

Наименование товара

Бананы



 Пример:

Для демонстрации способов использования всех рассмотренных выше операций

введем новые отношения:

= (ФИО, Дисциплина, Оценка)

= (ФИО, Группа)

= (Группа, Дисциплина)

Домен атрибута Дисциплина – все дисциплины в ВУЗе.

Домен атрибута Группы – все группы в ВУЗе.

Домен атрибута ФИО – все студенты ВУЗа.

Кто сдал экзамен по базам данных?

Proj

ФИО

(sel

Дисциплина = ―базы данных‖

R1)

Список ФИО, сдавших на 5 экзамен по базам данных?

Proj

ФИО

(Sel

Оценка=5 AND Дисциплина = ―базы данных‖

R1)

Кто должен сдавать экзамен по БД?

Proj

ФИО

( R2 join

R3.Группа = R2.Группа AND R3.Дисциплина = ―базы данных‖

R3 )

Кто имеет двойки более чем по одной дисциплине?

Proj

ФИО

(R1 join

R1.ФИО=R1^.ФИО

AND R1.Дисциплина<>R1^.Дисциплина

AND R1.Оценка<=2

AND R1^.Оценка<=2

R1^)

Здесь использовано условное соединение отношения R1 с самим собой. При

этом, для того чтобы отличить второй экземпляр отношения от первого, для второго

экземпляра вводится псевдоним R1^. В остальном условное соединение в этом запросе

ничем не отличается от обычного.

А теперь зададимся вопросом: кто является круглым отличником?

1. Список всех верных пар (студент, дисциплина) :

R4 = Proj

ФИО, Дисциплина

(R2 join

R2.Группа = R3.Группа

R3) .

2. Список всех пар (студент, дисциплина), для которых получены отличные оценки:

R5 = proj

ФИО, Дисциплина

(sel

Оценка = 5

R1) .

3. Список студентов, не сдавших что-либо на 5:

R6 = proj

ФИО

(R4 \ R5) .

4. Исключаем R6 из общего списка студентов:

(proj

ФИО

R2 ) \ R6 .

Это и является ответом на первоначальный вопрос.

3.2.4 Деление

Пусть заданы два отношения: A со схемой (a

, a

, ..., a

, b

, ..., b

) и B со

схемой (b

, b

, ..., b

). Будем считать, что атрибут b

отношения A и атрибут b

отношения B не только обладают одним и тем же именем, но и определены на одном и

том же домене (имеют один и тот же тип). Назовем множество атрибутов {a

}

составным атрибутом a, а множество атрибутов {b

} - составным атрибутом b. Теперь

можно ввести операцию реляционного деления бинарного отношения A(a,b) на

унарное отношение B(b).

Результатом деления A на B является отношение C(a), состоящее из всех

кортежей a таких, что существует кортеж <a, b>, принадлежащий A, для всех кортежей

B. Иными словами: результат содержит такие кортежи a из A, для которых

соответсвующие кортежи b (из A) включают все кортежи a из отношения B.

 Пример:

Введем два отношения:

R1:

Должность Отдел

Начальник ПРОЕКТНЫЙ ОТДЕЛ

Аналитик ПРОЕКТНЫЙ ОТДЕЛ

Расчетчик БУХГАЛТЕРИЯ

Расчетчик ПРОЕКТНЫЙ ОТДЕЛ

Секретарь ПРОЕКТНЫЙ ОТДЕЛ

Инженер ПРОЕКТНЫЙ ОТДЕЛ

Секретарь АДМИНИСТРАЦИЯ

Техник ПРОЕКТНЫЙ ОТДЕЛ

R2 (содержит все должности в штатном расписании организации):

Должность

Начальник

Расчетчик

Секретарь

Аналитик

Инженер

Техник

Тогда после выполнения операции реляционного деления отношения R1 на

отношение R2 будет получено унарное отношение, содержащее перечень отделов,

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

R1 div R2:

ОТДЕЛ

ПРОЕКТНЫЙ ОТДЕЛ

Эту операцию обычно можно заменить комбинацией других операций.



3.2 Реляционная алгебра и ограничения на данные

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

условиях ―вузовского‖ примера из п. 3.2.3., естественно потребовать, чтобы в

отношении R1 присутствовали бы только ФИО, имеющиеся в отношении R2. С

помощью алгебраического выражения это можно записать так (это пример

так называемого ограничения ссылочной целостности):

proj

ФИО

R1 ≤ proj

ФИО

или

(proj

ФИО

R1) \ (proj

ФИО

R2) = Ø

Кроме того, желательно наложить условие единственности оценки для

комбинации (ФИО, Дисциплина) (так называемое ограничение функциональной

зависимости). Этого можно добиться с помощью выражения:

R1^ = R1

R1 join

R1.ФИО=R1^.ФИО AND R1.Дисциплина=R1^.Дисциплина AND R1.Оценка<>R1^.Оценка

R1^ = Ø

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

только производить манипуляции над данными, но и реализовывать ограничения. Это

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

функции, характерные для баз данных. А как станет ясно из дальнейшего, аппарат

ограничений – одна из важнейших составляющих СУБД.

Отметим еще раз, что в понятие модели данных входят три составляющие:

1. Структурные основы модели (как данные хранятся и как отражаются

взаимосвязи между ними)

2. Операции над данными (как задавать всевозможные вопросы, связанные с

предметной областью, моделируемой в базе данных)

3. Ограничения на данные

К настоящему моменту все три составляющие абстрактной модели данных

описаны для реляционной модели данных! В следующих нескольких разделах речь

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

будет иметь дело та или иная база данных (иначе говоря, о проетировании моделей

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

некотором смысле структур данных.

4 Инфологическое моделирование

Чтобы получить адекватную потребностям прикладной задачи структуру базы

данных, необходимо разработать проект базы данных. Что такое проект? Это схема

некоторого устройства, которая должна быть воплощена в реальности. Что такое

проект реляционной базы данных? Это набор взаимосвязанных отношений, в которых

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

отношения взаимосвязаны? Потому что в ходе выполнения программного приложения,

основанного на базе данных, выполняются соединения отношений и одни и те же

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

одном отношении оценки обозначаются цифрами, а в другой словами «отлично»,

«хорошо» и т. д.: в этом случае не удастся соединить эти отношения по столбцу

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

несопоставимые вещи. Здесь проявляется обычная проблема компьютерных систем:

они могут решать весьма сложные интеллектуальные задачи, но пасуют, не в силах

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

данных должен быть очень конкретен и аккуратен. Фактически такой проект – это

фундамент будущего программного комплекса. Развивая аналогию, можно сказать, что

хорошо спроектированное готовое здание можно подвергнуть переделке, которая

затронет многие существенные детали, но нельзя заменить фундамент, не разрушив

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

базу данных, изображены на рисунке 4.1 .

Проектирование БД

Проектирование

программного

приложения

Реализация БД и

приложения

Эксплуатация приложения и

БД

Анализ предметной

области

Инфологическое

проектирование

Даталогическое

проектирование

Физическое

проектирование

Рисунок 4.1 – Этапы жизненного цикла приложения

На этом рисунке детализирован этап проектирования БД, который представляет

собой последовательность перехода от неформального словесного описания

предметной области к формализованному описанию объектов предметной области в

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

проектирования:

1. Системный анализ и словесное описание информационных объектов

предметной области.

2. Проектирование инфологической модели предметной области – т. е. создание

частично формализованного описания объектов предметной области в терминах

некоторой семантической модели (далее в этом разделе мы рассмотрим одну из

моделей – ER-диаграмму).

3. Даталогическое проектирование БД, то есть описание БД в терминах выбранной

СУБД, на конкретном диалекте языка SQL (см. далее).

4. Физическое проектирование БД, то есть выбор эффективного размещения БД на

внешних носителях для обеспечения наиболее эффективной работы

приложения.

С точки зрения проектирования БД, в рамках этапа анализа необходимо

провести подробное словесное описание объектов предметной области и реальных

связей, которые присутствуют между описываемыми объектами. Желательно, чтобы

данное описание позволяло корректно определить все взаимосвязи между объектами

предметной области.

В общем случае существуют два подхода к выбору состава и структуры

предметной области.

Функциональный подход — он реализует принцип «от задач» или, как его еще

называют, ―чего изволите‖ и применяется тогда, когда заранее известны функции

будущих пользователей и задачи в целом. В этом случае мы можем четко выделить

минимальный необходимый набор объектов предметной области, которые должны

быть описаны.

Предметный подход — когда информационные потребности будущих

пользователей БД до конца не определены. Они могут быть многоаспектными и

изменчивыми. Мы не можем точно выделить минимальный набор объектов предметной

области, которые необходимо описывать. В описание предметной области в этом

случае включаются такие объекты и взаимосвязи, которые наиболее характерны и

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

то есть она может быть использована при решении многих, заранее не определенных

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

конкретных задач будет неэффективной.

Чаще всего на практике стоит использовать некоторый компромисс, который, с

одной стороны, ориентирован на конкретные задачи или функциональные потребности

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

функций в программном приложении.

Анализ должен дать подробное описание объектов предметной области,

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

БД, с кратким описанием алгоритмов их решения, описание выходных документов,

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

источником данных для БД. Далее начинается этап собственно инфологического

моделирования.

Одной из целей инфологического моделирования является достижение

понимания того, что содержится в базе данных, всеми участниками проекта по

созданию приложения, в основе которого лежит база данных. Иными словами,

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

человеку концепций, независимых от особенностей реализации системы в конкретной

СУБД. Для такого моделирования принято использовать совокупность диаграмм,

предложенных Ченом, называемых ―модель сущность-связь‖. Другое название

использует английскую аббревиатуру: ER–диаграмма (Entity–Relation). Впоследствии

инфологическая модель должна быть отображена в даталогическую (и в физическую)

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

перевода модели ―сущность–связь‖ в даталогическую модель (реляционную базу

данных). Для этой цели служит целый класс программных продуктов, называемый

CASE (Computer Aided Software Engineering). Рассмотрим основные понятия

инфологической модели.

4.1 Сущность и набор сущностей

Сущность описывает некоторый объект предметной области. Набор сущностей

– класс однотипных объектов (или сущностей). Набор сущностей имеет атрибуты –

характеристики, определяющие свойства объекта. Все сущности набора имеют одни и

те же атрибуты. Совокупность атрибутов должна быть такой, чтобы отличить один

объект от другого. Атрибуты, как правило, являются простыми значениями, такими как

целые числа, числа с плавающей запятой, строки символов, даты и т. д. В диаграмме

―сущность–связь‖ каждый набор сущностей изображается прямоугольником (рисунок

4.2).

Сотрудники

Табельный номер

Фамилия

Имя

Отчество

Адрес

…

Рисунок 4.2 – Пример набора сущностей

Набор сущностей Сотрудники имеет как минимум 5 атрибутов (Табельный

номер, Фамилия, Имя, Отчество, Адрес, …).

4.2 Связи между сущностями

Между наборами сущностей могут быть установлены связи. Связь соединяет два

или больше наборов сущностей. Она изображается линией. Между двумя наборами

сущностей можно установить много связей (рисунок 4.3).

Студенты

№ студ.билета

Фамилия

Имя

Отчество

Группа

Преподаватели

Таб.№

Фамилия

Имя

Отчество

Кафедра

Руководит дипломным

проектом

Читает

лекции

Рисунок 4.3 – Пример модели ―сущность–связь‖

Эта диаграмма означает, что объект набора сущностей Преподаватели связан с

объектом набора сущностей Студенты (Читает лекции). Связь двунаправлена:

преподаватель читает лекции студентам, студент слушает лекции преподавателей.

Вторая связь (Руководит дипломным проектом) устанавливает связь объекта набора

сущностей Преподаватели с объектом набора сущностей Студенты по иному

признаку, а именно, устанавливается связь между преподавателями-руководителями

дипломных проектов и студентами-дипломниками.

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

Например, связь Руководит дипломным проектом на левом конце имеет так

называемую ―лапу‖ (см. рисунок 4.3) а на правом конце единственную линию. Это

отражает тот факт, что один преподаватель может руководить несколькими

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

многим‖. Кроме мощности, характер изображения связи говорит о ее обязательности. В

частности, связь Руководит дипломным проектом обязательна со стороны сущности

Преподаватели (не бывает дипломного проекта без руководителя). Это отражено

черточкой, перпендикулярной линии связи вблизи набора сущностей Преподаватели.

Однако не каждый преподаватель руководит дипломным проектом хотя бы одного

студента. Поэтому связь может и не соединять конкретного преподавателя со

студентами, т. е. является ―необязательной‖. Это выражается наличием кружка со

стороны набора сущностей Студенты. Вторая связь, Читает лекции, является

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