Литература

1. Мартин Дж. Организация баз данных в вычислительных системах: Пер. с англ. /Под ред. А.А. Стогния и А.Л. Щерса. – М.: Мир, 1980. – 664 с.

2. Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. Базы данных: Учебник для вузов. – СПб.: КОРОНА принт, 2000. – 416 с.

3. Горев А., Ахаян Р., Макашарипов С. Эффективная работа с СУБД. СПб.: Питер, 1997. – 700 с.

4. Карпова Т. Базы данных. Модели, разработка, реализация. – СПб.: Питер, 2001. – 304 с.

5. Саймон А.Р. Стратегические технологии баз данных: менеджмент на 2000 год: Пер. с англ. / Под ред. и с предисл. М.Р. Кога­ловского. – М.: Финансы и статистика, 1999. – 479 с.

6. Ульман Дж. Д., Уидом Дж. Введение в системы баз данных: Пер. с англ. – М.: Лори, 2000. – 374 с.

7. Швецов В.И., Визгунов А.Н., Мееров И.Б. Базы данных. Учебное пособие. Н.Новгород: Изд-во ННГУ, 2004. 271 с.

8. Хаббард Дж. Автоматизированное проектирование баз данных: Пер. с англ. под ред. А.Л. Щерса. – М.: Мир, 1984. – 296 с..

Лекция 7. Формализация реляционной модели

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

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

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

7.1. Формализованное описание отношений и схемы отношений

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

ПустьA₁, A₂,…, A_n имена атрибутов. Каждому имени атрибута A_i соответствует допустимое множество значений, которые может принимать атрибут A_i. Это множество значений D_i называется доменом атрибута A_i, . По определению, домены являются непустыми конечными или счетными множествами. Уточним, что в теории реляционных баз данных домен рассматривается как множество значений одного (причем простого) типа данных. Понятию домена D_i соответствует множество значений, стоящих в столбце A_i рассматриваемой таблицы.

Схемой отношения R {A₁, A₂, …, A_n} называеся конечное множество имен атрибутов {A₁, A₂, …, A_n}, причем атрибут A_i принимает значение из множества D_i (i=1, 2,…n), где n – арность отношения.

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

Пусть D = D₁ D₂…D_n .

Отношением r со схемой R называется конечное множество отображений {t₁, t₂,…, t_p} из множества R: {A₁, A₂, …, A_n} в множество D:{ D₁ D₂…D_n }, таких, что

t_k(A_i)  D_i, ; .

Отображение t_k называется k-м кортежем, n – размерность кортежа.

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

Понятию отношения r соответствует множество значений, стоящих во всех строках рассматриваемой таблицы.

Ключом отношения r со схемой R называется минимальное подмножество K = {A_i1, A_i2,…, A_im}{A₁, A₂, …, A_n}, где {i1, i2, …,im}{1, 2, …, n}, такое, что любые два различных кортежа t₁, t₂ r (t₁  t₂) не совпадают по значениям множества K ={A_i1, A_i2, …, A_im}.

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

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

Выпишем реляционную модель данных примера из предыдущей лекции (см. рис. 6.3.). Введем обозначения атрибутов всех соответствующих сущностей. Пусть A₁ – код студента, A₂ – фамилия, A₃ – дата рождения, A₄ – место рождения, A₅ – номер факультета, A₆ – название факультета, A₇ – номер специальности, A₈ – название специальности. Обозначим схему отношения СТУДЕНТ как R1, ФАКУЛЬТЕТ как R2, СПЕЦИАЛЬНОСТЬ как R3, СТУДЕНТ УЧИТСЯ НА ФАКУЛЬТЕТЕ как R4, СТУДЕНТ УЧИТСЯ ПО СПЕЦИАЛЬНОСТИ как R5, НА ФАКУЛЬТЕТЕ ИМЕЮТСЯ СПЕЦИАЛЬНОСТИ как R6.

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

R1(A₁, A₂, A₃, A₄)

R2(A₅, A₆)

R3(A₇, A₈)

R4(A₁, A₅)

R5(A₁, A₇)

R6(A₅, A₇)

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

r1, r2, r3, r4, r5, r6,

Отметим следующие свойства отношения:

1. Отношение имеет имя, которое отличается от имен всех других отношений.

2. Каждое значение элементов кортежей представляется простым (атомарным) типом данных.

3. Каждый атрибут имеет уникальное имя.

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

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

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

7.2. Манипулирование данными в реляционной модели

Для манипулирования данными в реляционной модели используются два формальных аппарата:

• реляционная алгебра, основанная на теории множеств;

• реляционное исчисление, базирующееся на исчислении предикатов первого порядка.

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

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

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

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

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

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

7.3. Операции реляционной алгебры

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

Объединение r  s

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

Для примера, пусть

r					s
a	b	a			b	g	a
d	a	f			d	a	f
c	b	d

тогда

r  s

a	b	a
d	a	f
c	b	d
b	g	a

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

Разность r – s

Разностью отношений r и s называется множество кортежей, принадлежащих r, но не принадлежащих s. Для этой операции также требуется одинаковая арность отношений.

r – s

a	b	a
c	b	d

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

Декартово произведение r s

Пусть r и s – отношения арности k1 и k2 соответственно. Декартовым произведением rs называется множество кортежей длины k1+k2, первые k1 компонентов которых образуют кортежи, принадлежащие r, а последние k2 – кортежи, принадлежащие s.

r  s

a	b	a	b	g	a
a	b	a	d	a	f
d	a	f	b	g	a
d	a	f	d	a	f
c	b	d	b	g	a
c	b	d	d	a	f

Проекция

Проекция есть множество кортежей, получаемых из кортежей отношения r выбором столбцов с именами A_i1, A_i2, …, A_im.

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

a	a
d	f
c	d

Выбор (селекция) _F(r)

Пусть F – формула, образованная: операндами, являющимися константами или именами атрибутов, арифметическими операторами сравнения, логическими операторами (и, или, не), тогда выбором (селекцией) _F называется множество кортежей, компоненты которого удовлетворяют условию, заданному формулой F.

 (1)=(3)(r)=

a

b

a

Здесь F:(1)=(3) – содержимое первого столбца равно содержимому третьего столбца.

Приведем ряд примеров представления запросов с помощью формальных операций для реляционной модели (СТУДЕНТ, ФАКУЛЬТЕТ, СПЕЦИАЛЬНОСТЬ), рассмотренной выше.

Пример 1.

Сформировать список студентов (фамилия).

Рассмотрим схему отношения СТУДЕНТ.

Атрибут «Фамилия» обозначен здесь А₁ Для ответа на запрос необходимо взять проекцию отношения r1 на столбец А₁.

.

Пример 2.

Выдать список фамилий и дат рождений студентов, которым на текущую дату (date) больше 35 лет.

Рассмотрим то же отношение r1. Сначала выбираем студентов, которым больше 35 лет:

.

Затем берем проекцию полученного отношения на столбцы

.

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

Пример 3.

Выдать список фамилий студентов, обучающихся по специальности «Информационные технологии». Название специальности является атрибутом отношения r3. Если бы в этом отношении присутствовал атрибут «фамилия», то задача решалась бы аналогично примеру 2. В отношении r3 присутствует атрибут «код студента», а «фамилия» присутствует в отношении r1. Для ответа на этот запрос необходимо связывать по «код студента» отношение r3 и отношение r1.

Сначала выберем из отношения r3 кортежи с названием специальности «Информационные технологии». Обозначим полученное отношение rp1. (Дальнейшие промежуточные отношения будем обозначать последовательно rp1, rp2, rp3 и т.д.).

.

Далее нас будет интересовать только атрибут A₁ – «код студента». Поэтому возьмем проекцию на эти столбцы.

.

Далее необходимо связать отношения r1 и rp2 (склеить таблицы). Для склейки таблиц используется операция «декартово произведение»:

.

В отношении r3 присутствуют два одинаковых столбца: A₁ из отношения r1 и A₁ из отношения rp2. Выбирая из отношения rp3 строки, в которых значения в соответствующих столбцах совпадают, получим сведения о студентов, обучающихся по специальности «Информационные технологии»

,

где A₁  r1 и A₁  rp2 обозначают соответственно столбец A₁ соответствующей первой и второй составной части декартова произведения. Теперь осталось только выбрать фамилии соответствующих студентов

.

Получаем требуемый результат. Заметим, что для экономии действий и памяти, перед тем как склеивать таблицы, целесообразно было сделать операцию проекции отношения r1 на столбцы A₁, A₂. (чтобы не включать в декартово произведение лишние столбцы).

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

Пересечение r  s

Пересечением отношений r и s называется множество кортежей, принадлежащих как r, так и s. Пересечение может быть выражено через операции разности

r  s = r – (r – s).

-соединение

-соединение r и s по столбцам A_i и A_j представляет собой множество таких кортежей в декартовом произведении r и s, что i-й компонент r находится в отношении  c j-м компонентом s, где  – арифметический оператор сравнения. Если  является оператором равенства, то эта операция называется эквисоединением

,

где l – арность отношения r.

Пример.

r					s
1	2	3			3	1
4	5	6			6	2
7	8	9

1	2	3	3	1
1	2	3	6	2
4	5	6	6	2

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

Естественное соединение

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

Пусть

r = (A₁, ..., A_k, B₁,..., B_n), s = (A₁, ..., A_k, C₁,..., C_m),

имена A₁, ..., A_k совпадают.

Тогда определяется следующим образом

.

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

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

Вопросы, рассматриваемые в данной лекции, более подробно описаны в [1-5].

Контрольные тесты

Задача 1. Что такое схема отношения?

Вариант 1.

Что называется схемой отношения R?

ð+ множество имен атрибутов

 множество названий сущностей

 множество кортежей

 множество доменов

Вариант 2.

Чему соответствует понятие «схемы отношения»?

 двумерной таблице

ð+ описанию структуры конкретной таблицы

 описанию структуры любой таблицы

 множеству значений в таблице

Вариант 3.

Что соответствует имени атрибута в схеме отношения?

ð+ множество значений определенного типа данных

ð+ домен

 кортеж

 множество значений разных типов данных

Задача 2. Что такое отношение?

Вариант 1.

Что называется отношением?

 множество имен атрибутов таблицы

 множество названий сущностей

ð+ множество кортежей таблицы

 множество доменов таблицы

Вариант 2.

Чему соответствует понятие «отношения»?

 описанию структуры конкретной таблицы

 описанию структуры любой таблицы

 множеству значений в двумерной таблице

ð+ множеству строк в двумерной таблице

Вариант 3.

Что такое ключ отношения?

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

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

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

 множество всех атрибутов

Задача 3. Что такое реляционная модель базы данных и реляционная база данных?

Вариант 1.

Что называется реляционной моделью базы данных?

ð+ совокупность схем отношений, используемых для представления концептуальной модели

 совокупность отношений, реализующих концептуальную модель

 текущие значения отношений

 модель данных реляционной СУБД

Вариант 2.

Что называется реляционной базой данных?

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

 совокупность схем отношений, реализующих концептуальную модель

ð+ текущие значения отношений, описываемых концептуальной моделью

 модель данных реляционной СУБД

Вариант 3.

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

ð+ операции реляционной алгебры

ð+ формулы реляционного исчисления

 аппарат схем отношений

 ER-диаграммы

Задача 4. Операции объединения и пересечения отношений

Вариант 1.

Какие требования к отношениям накладываются для применения этих операций?

 одинаковое число строк

ð+ одинаковое число столбцов

 одинаковые названия столбцов

 равные размеры таблиц

Вариант 2.

Что называется объединением отношений?

ð+ множество кортежей, принадлежащих одному или другому отношению, или им обоим

 множество кортежей, принадлежащих одному или другому отношению

 множество кортежей, принадлежащих обоим отношениям

 множество кортежей, одна часть которого представляет кортеж из первого отношения, вторая часть – кортеж из второго отношения

Вариант 3.

Что называется разностью отношений?

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

ð+ множество кортежей, принадлежащих первому отношению, но не принадлежащих второму отношению

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

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

Задача 5. Что такое операция «декартово произведение»?

Вариант 1.

Что представляет собой результат операции «декартово произведение» двух отношений?

 схему отношения, составленную из двух схем отношений

ð+ новое отношение со схемой отношения, составленной из двух исходных схем отношений

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

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

Вариант 2.

Если арность отношений, участвующих в операции «декартово произведение» равна соответственно k1 и k2, чему равна арность полученного отношения?

ð+ k1+ k2

 k1* k2

 k1 ‑ k2

 k1+ k1 * k2

Вариант 3.

Если арность отношений, участвующих в операции «декартово произведение» равна соответственно k1 и k2, чему равно количество кортежей в полученном отношении?

 k1+ k2

ð+ k1* k2

 k1 ‑ k2

 (k1+ k2) * k2

Вариант 4.

Для чего используется операция «декартово произведение»?

ð+ для «склейки» таблиц

ð+ для перехода от значений атрибута в одной таблице к такому же значению атрибута в другой таблице

 для объединения таблиц

 для поиска данных в таблицах

Задача 6. С помощью каких операций осуществляется выборка данных из таблицы?

Вариант 1.

С помощью какой операции выбираются нужные столбцы таблицы?

 cелекция

ð+ проекция

 декартово произведение

 разность

Вариант 2.

С помощью какой операции выбираются нужные кортежи отношения?

 проекция

 декартово произведение

 разность

ð+ cелекция

Вариант 3.

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

ð+ имена атрибутов

ð+ константы

ð+ арифметические операторы сравнения

ð+ логические операторы сравнения

Задача 7. В чем смысл операций соединения?

Вариант 1.

Какие операции входят в операции соединения?

ð+ селекция

ð+ проекция

ð+ декартово произведение

 разность

Вариант 2.

Для чего нужны операции соединения?

ð+ для «склейки» таблиц

ð+ для перехода от значений атрибутов в одной таблице к таким же значениям атрибутов в другой таблице

ð+ для объединения таблиц с совпадающими значениями одного или нескольких атрибутов

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

Вариант 3.

В чем отличие операции «-соединение» от операции «естественное соединение»?

 используется меньше операций реляционной алгебры

ð+ сравниваются значения одного общего атрибута

 накладывается меньше условий на исходные отношения

 при сравнении значений может использоваться больше арифметических операторов

Задача 8. Какая система работы с базой данных является реляционной?

Вариант 1.

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

ð+ как набор таблиц

 как иерархическую структуру

 как наборы записей с указателями

 как совокупность файлов

Вариант 2.

Какие операции должна поддерживать реляционная система?

 поиск

 добавление

 удаление

ð+ селекция

ð+ проекция

ð+ соединение

Вариант 3.

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

ð+ не указывает, указывает только операции

 указывает в программе выполнения операции

 указывает в прикладной программе

 указывает при обращении к операции