Банки и базы данных

4.2.4 Атомарность значений атрибутов

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

Таблица 4.1

Можно сказать, что здесь мы имеем бинарное отношение, значениями атрибута ОТДЕЛЫ которого являются отношения. Заметим, что исходное отношение СОТРУДНИКИ является нормализованным вариантом отношения ОТДЕЛЫ:

Таблица 4.2

СОТР_НОМЕР	СОТР_ИМЯ	СОТР_ЗАРП	СОТР_ОТД_НОМЕР
2934	Иванов	112,000	310
2935	Петров	144,000	310
2936	Сидоров	92,000	313
2937	Федоров	110,000	310
2938	Иванова	112,000	315

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

Зачислить сотрудника Кузнецова (пропуск номер 3000, зарплата 115,000) в отдел номер 320 и

Зачислить сотрудника Кузнецова (пропуск номер 3000, зарплата 115,000) в отдел номер 310.

Если информация о сотрудниках представлена в виде отношения СОТРУДНИКИ, оба оператора будут выполняться одинаково (вставить кортеж в отношение СОТРУДНИКИ). Если же работать с ненормализованным отношением ОТДЕЛЫ, то первый оператор выразится в занесение кортежа, а второй - в добавление информации о Кузнецове в множественное значение атрибута ОТДЕЛ кортежа с первичным ключом 310.

4.3 Общая характеристика реляционной модели данных

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

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

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

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

требование целостности сущностей;

требование целостности по ссылкам.

Лекция 5. Базисные средства манипулирования реляционными данными

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

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

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

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

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

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

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

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

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

5.1 Реляционная алгебра

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

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

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

объединения отношений;

пересечения отношений;

взятия разности отношений;

прямого произведения отношений.

Специальные реляционные операции включают:

ограничение(выборка) отношения;

проекцию отношения;

соединение отношений;

деление отношений.

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

5.1.1 Общая интерпретация реляционных операций

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

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

2. Специальные реляционные операции: выборка, проекция, соединение и деление.

Ниже приведены упрощенные определения этих восьми операторов (рис. 5.1).

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

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

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

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

Рисунок 5.1. Первоначальные восемь операторов (обзор).

Пересечение Возвращает отношение, содержащее все кортежи, которые принадлежат одновременно двум заданным отношениям.

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

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

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

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

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

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

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

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

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

S RENAME CITY AS SCITY

С помощью этого выражения (рассматриваемая запись является именно выражением, а не "командой" или оператором, а значит, может быть вложена в другие выражения) вычисляется отношение, имеющее то же самое тело, что и отношение S, но с именем атрибута SCITY вместо CITY.

Таблица 5.1

Важно отметить, что выражение RENAME не изменяет базовую переменную-отношение поставщиков в базе данных -- оно является выражением (точно так, как и выражение S JOIN SP) и, следовательно, выдает некоторый результат (в данном случае этот результат очень похож на текущее значение переменной-отношения поставщиков).

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

Р RENAME PNAME AS PN, WEIGHT AS WT

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

Таблица 5.2

Лекция 6. Базисные средства манипулирования реляционными данными

6.1 Особенности теоретико-множественных операций реляционной алгебры

Объединение

В математике объединением двух множеств называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из исходных множеств. Поскольку отношение является множеством (точнее, содержит множество), а именно -- множеством кортежей, очевидно, что можно получить объединение двух таких множеств. Результатом выполнения этой операции будет множество, состоящее из всех кортежей, которые принадлежат хотя бы одному из исходных отношений. Например, объединение множества кортежей описания поставщиков переменной-отношения S и множества кортежей описания деталей переменной-отношения Р, определенно, будет множеством.

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

Точное определение оператора реляционного объединения. Для заданных отношений А и В одного и того же типа объединением этих двух отношений (что записывается как А UNION В) называется новое отношение того же типа с телом, состоящим из множества всех кортежей t, которые принадлежат либо отношению А, либо отношению В, либо обоим отношениям одновременно.

Пример. Пусть отношения А и В будут такими, как показано на рис. 6.1 (отношение А представляет поставщиков из Лондона, а отношение В -- поставщиков, которые поставляют деталь под номером 'Р1'). Тогда выражение A UNION В (см. рис. 6.1,а) представляет поставщиков, которые или находятся в Лондоне, или поставляют деталь под номером 'Р1' (или и то, и другое). Обратите внимание, что результат имеет три кортежа, а не четыре -- повторяющиеся кортежи удаляются по определению. Вопрос удаления дубликатов не возникает в других традиционных операциях над множествами. фактически еще существует только одна операция (помимо объединения), где этот вопрос актуален, - операция проекции.

Рис. 6.1. Примеры операций объединения, пересечения и вычитания.

Пересечение

Как и для оператора объединения, для реляционного оператора пересечения (и по тем же причинам) необходимо, чтобы его операнды были совместимы по типу. Итак, пересечением двух совместимых по типу отношений А и В (что записывается как A INTERSECT В) называется отношение того же типа с телом, состоящим из множества всех кортежей t, которые принадлежат одновременно обоим исходным отношениям А и В.

Пример. Пусть вновь отношения А и В будут такими, как показано на рис.2. Тогда выражение A INTERSECT В (см. рис. 2, б) представляет поставщиков, которые находятся в Лондоне и поставляют деталь под номером 'Р1'.

Вычитание

Как и для операторов объединения и пересечения, для реляционного оператора вычитания необходимо, чтобы его операнды были совместимы по типу. Тогда вычитанием двух совместимых по типу отношений А и В (что записывается как A MINUS В, причем порядок их указания здесь играет роль) называется отношение того же типа, что и отношения А и В с телом, состоящим из множества всех кортежей t, которые принадлежат отношению А, но не принадлежат отношению В.

Пример. Пусть еще раз отношения А и В будут такими, как показано на рис. 2. Тогда выражение A MINUS В (см. рис. 2, в) представляет поставщиков, которые находятся в Лондоне и не поставляют деталь под номером 'Р1', а выражение В MINUS А (см. рис. 2, г) представляет поставщиков, которые поставляют деталь под номером 'Р1' и не находятся в Лондоне. Заметьте, что при вычитании учитывается порядок следования операндов, точно так, как в обычной арифметике (например, 5-2 и 2-5 -- это не одно и то же).

Произведение

В математике декартово произведение (или для краткости -- просто произведение) двух множеств является множеством всех таких упорядоченных пар элементов, что первый элемент в каждой паре берется из первого множества, а второй элемент в каждой паре берется из второго множества. Следовательно, декартово произведение двух отношений должно быть множеством упорядоченных пар кортежей. Но, опять-таки, необходимо сохранить свойство замкнутости; иначе говоря, результат должен содержать кортежи, а не упорядоченные пары кортежей. Поэтому версия декартова произведения в реляционной алгебре представляет собой расширенную форму операции, в которой каждая упорядоченная пара кортежей заменяется одним кортежем, образованным из двух сцепленных кортежей этой пары. "Сцепление" здесь означает объединение (в смысле теории множеств, а не реляционной алгебры), т.е. кортежи { А1:а1, А2:а2,..., Am:am }и{ В1:b, В2:b2,..., Bn:bn } объединяются в один кортеж. { А1:а1, А2:а2,..., Аm:аm, В1:b1, В2:b2,..., Bn:bn }.

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

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

Пример. Пусть отношения А и В будут такими, как показано на рис. 6.2 (отношение А представляет, например, номера всех существующих на данный момент поставщиков, а отношение В -- номера всех поставляемых на текущий момент деталей). Тогда произведение A TIMES В -- это набор всех возможных на текущий момент пар из значений номера поставщика и номера детали.

Рис. 6.2 Пример операции декартова произведения.

6.2 Специальные реляционные операции*

Выборка

Пусть задано отношение А с атрибутами X и Y (, возможно, с другими атрибутами), а символ И обозначает любой скалярный оператор сравнения (=, ?, ?,< и т.д.), такой, что условие X И Y корректно определено и при заданных значениях атрибутов X и Y его проверка дает значение истина или ложь. Тогда И-выборкой из отношения А по атрибутам X и Y (что записывается, например, как S WHERE CITY = 'London', причем именно в этом порядке) называется отношение, имеющее тот же заголовок, что и отношение А, и тело, содержащее множество всех кортежей t отношения А, для которых проверка условия X ИY дает значение истина.

Необходимо отметить следующее:

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

A WHERE cl AND с2 ? ( A WHERE cl ) INTERSECT ( A WHERE с2 )

A WHERE cl OR c2 ? ( A WHERE cl ) UNION ( A WHERE c2 )

A WHERE NOT c ? A MINUS ( A WHERE С )

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

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



Рис. 6.3 Примеры операции выборки.

Проекция

Пусть задано отношение А с атрибутами X, Y, ... , Z. Тогда проекцией отношения А по атрибутам X, У, ... , Z (что записывается как А {X, Y, ... , Z }) называется отношение, удовлетворяющее следующим требованиям.

¦ Его заголовок получается из заголовка отношения А посредством удаления из него всех атрибутов, не входящих в множество {X, Y, ... , Z}.

¦ Его тело содержит множество всех кортежей вида {X:x, Y:y, ... , Z:z}, таких, для которых в отношении А значение атрибута X равно х, значение атрибута Y равно у,..., значение атрибута Z равно z.

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

Из этого определения можно сделать следующие выводы

1. Никакой атрибут не может быть указан в списке атрибутов более одного раза.

2. Если в списке атрибутов указаны все атрибуты отношения А, то такая проекция представляет собой тождественную проекцию.

3. Проекция вида А{ } (т.е. такая, в которой список атрибутов пуст) также допустима.

Она представляет собой нулевую проекцию.

Несколько примеров операции проекции показано на рис. 6.4 В первом примере (проекция отношения поставщиков по атрибуту CITY), несмотря на то что исходное отношение S имеет пять кортежей (и, следовательно, пять значений городов), в результирующем отношении присутствует только три города, поскольку дублирующиеся кортежи исключены. Аналогичные замечания можно сделать и для других примеров.

Рис. 6.4 Примеры операций проекции.

Соединение

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

Пусть отношения А и В имеют заголовки

{ XI, Х2, ... , Xm, Yl, Y2, ... , Yn }

и

{ Yl, Y2, ... , Yn, Zl, Z2, ... , Zp }

соответственно, т.е. атрибуты Yl, Y2, ... , Yn (и только они) -- общие для двух этих отношений, XI, Х2, .... , Xm -- остальные атрибуты отношения А и Zl, Z2, ... , Zp - остальные атрибуты отношения В. Далее будем рассматривать выражения {XI, Х2, ... ,Xm}, {Yl, Y2, ... , Yn} и {Zl, Z2, ... , Zp} как три составных атрибута X, Y и Z соответственно. Тогда естественным соединением отношений А и В (что записывается как A JOIN В) называется отношение с заголовком {X, Y, Z} и телом, содержащим множество всех кортежей вида {Х:х, Y:y, Z:z}, таких, для которых в отношении А значение атрибута X равно х, а значение атрибута Y равно у и в отношении В значение атрибута Y равно у, а значение атрибута Z равно z

Пример естественного соединения (естественное соединение S JOIN P по общему атрибуту CITY) приведен на рис. 6.5

Рис. 6.5 Естественное соединение S JOIN P.

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

Деление

Определение оператора деления. Пусть отношения А и В имеют заголовки { X1, Х2, ... , Хm } и { Yl, Y2, ... , Yn } соответственно (т.е. заголовки отношений А и В не пересекаются). Пусть также отношение С имеет следующий заголовок.

{ XI, Х2, ... , Xm, Yl, Y2, ... , Yn }

(Иначе говоря, заголовок отношения С является объединением заголовков отношений А и В.) Далее будем рассматривать множества { X1, Х2, ... , Хm } и { Yl, Y2, , Yn } как составные атрибуты X и Y соответственно. Тогда результатом деления отношения А на отношение B по отношению С (что записывается как A DIVIDEBY В PER С, где отношение А представляет собой делимое, отношение В -- делитель, а отношение С -- "посредник") называется отношение с заголовком {X} и телом, содержащим множество всех кортежей вида {Х:х}, таких, что кортеж вида {Х:х, Y:y} принадлежит отношению В для всех кортежей вида {Y:y}, принадлежащих отношению В. Нестрого это можно сформулировать так: результат содержит такие Х-значения из отношения А, для которых соответствующие Y-значения из отношения С включают все Y-значения из отношения В.

На рис. 8 показаны некоторые простые примеры операции деления. В каждом случае делимое (отношение DEND) -- это проекция текущего , значения переменной-отношения S по атрибуту S#, посредник (MED) -- это проекция текущего значения переменной-отношения SP по атрибутам S# и P#, а три делителя (отношения DOR)-- такие, как показано на рисунке. В частности рассмотрим последний пример, в котором делителем является отношение, содержащее номера всех известных в данный момент деталей. В результате, получим номера поставщиков, поставляющих все типы этих деталей. Как видно из примера, оператор DIVIDEBY полезен именно для запросов такого рода. Более того, если запрос на обычном языке включает слово "все" ("определить поставщиков всех типов деталей"), то почти наверняка понадобится использовать операцию деления. Тем не менее, следует отметить, что подобны запросы удобнее записывать в терминах реляционных сравнений.



Рис. 6.6

Ассоциативность и коммутативность

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

( A UNION В ) UNION С A UNION ( В UNION С )

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

A UNION В UNION С.

Аналогичные замечания можно сделать и для операций пересечения (INTERSECT), декартова произведения (TIMES) и соединения (JOIN) (но не операции вычитания MINUS).

Заметим также, что операции объединения (UNION), пересечения (INTERSECT), декартова произведения (TIMES) и соединения (JOIN) (но не операция вычитания MINUS) еще и коммутативны, т.е. выражения A UNIQN В и В UNION А эквивалентны, что справедливо и для операций пересечения, декартова произведения и соединения.

Зачем нужна реляционная алгебра

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

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

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

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

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

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

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

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

В целом, выражения реляционной алгебры служат для символического высокоуровневого представления намерений пользователя (например, в отношении некоторого определенного запроса). И именно потому, что подобные выражения являются символическими и высокоуровневыми, ими можно манипулировать в соответствии с различными символическими высокоуровневыми правилами преобразования. Например, рассмотрим следующее выражение ("Получить имена поставщиков детали с номером 'Р2').

( ( SP JOIN S ) WHERE Р# = Р# ( 'Р2' ) ) { SNAME }

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

( ( SP WHERE P# = P# ( 'Р2' ) ) JOIN S ) { SNAME }

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

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

Операция расширения

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

EXTEND P ADD { WEIGHT * 454 ) AS GMWT

С помощью этого выражения создается новое отношение с таким же заголовком, как и у отношения Р, за исключением дополнительного атрибута GMWT. Каждый кортеж этого отношения совпадает с соответствующим кортежем отношения Р, но содержит еще одно дополнительное значение атрибута GMWT, вычисляемое в соответствии с указанным выражением, как показано на рис. 6.7

Рис. 6.7 Пример операции расширения.

Выражение EXTEND не изменяет содержимое базовой переменной-отношения деталей в базе данных. Это всего лишь выражение, такое же, как, например, S JOIN SP, и значит, оно создает определенный результат. В данном случае этот результат подобен текущему значению базовой переменной-отношения деталей. (Иначе говоря, операция расширения -- это не реляционный аналог SQL-оператора ALTER TABLE.)

Операция обобщения

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

SUMMARIZE SP PER SP { P# } ADD SUM ( QTY ) AS TOTQTY

В результате его вычисления создается отношение с заголовком {Р#,TOTQTY}, содержащее один кортеж для каждого значения атрибута P# в проекции SP{P#}. Каждый из этих кортежей содержит значение атрибута P# и соответствующее общее количество деталей (Рис. 6.8). Другими словами, концептуально исходное отношение Р "перегруппировано" в множество групп кортежей (по одной группе для каждого уникального значения атрибута P#), после чего для каждой полученной группы сгенерирован один кортеж, помещаемый в окончательный результат.

Рис. 6.8 Пример выполнения операции SUMMARIZE

В общем случае значение выражения SUMMARIZE A PER В ADD <обобщение> AS Z определяется следующим образом.

Отношение В должно иметь такой же тип, как и некоторая проекция отношения А, т.е. каждый атрибут отношения В должен одновременно присутствовать в отношении А. Примем, что атрибутами этой проекции (или, что эквивалентно, атрибутами отношения В) являются атрибуты А1, А2, ... , An.

Результатом вычисления данного выражения будет отношение с заголовком {А1,А2, ... , An, Z}, где Z является новым добавленным атрибутом.

¦ Тело результата содержит все кортежи t, где t является кортежем отношения В, расширенным значением нового атрибута Z. Это значение нового атрибута Z подсчитывается посредством вычисления обобщающего выражения по всем кортежам отношения А, которое имеет те же значения для атрибутов А1, А2, ... , An, что и кортеж t. (Разумеется, если в отношении А нет кортежей, принимающих те же значения для атрибутов А1, А2,... , An, что и кортеж t, то обобщающее выражение будет вычислено для пустого множества.) Отношение В не должно содержать атрибут с именем Z, а обобщающее выражение не должно ссылаться на атрибут Z. Кардинальность результата равна кардинальности отношения В, а степень результата равна степени отношения В плюс единица. Типом переменной Z в этом случае будет тип обобщающего выражения.

Группирование и разгруппирование

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

SP GROUP ( P#, QTY ) AS PQ

Результат выполнения этого выражения будет выглядеть так, как показано на рис. 6.9

Рис. 6.9 Группирование оnношения SP по атрибуту S#.

Реляционные сравнения

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

<реляционное выражение> И <реляционное выражение>

Здесь параметр <реляционное выражение> -- это в обоих случаях выражения реляционной алгебры, представляющие совместимые по типу отношения, а символ И -- это один из следующих операторов сравнения.

=Равно

?Не равно

? Подмножество

<Собственное подмножество

? Супермножество

> Собственное супермножество

6.3 Реляционное исчисление.

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

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

· основанное на математической логике реляционное исчисление.

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

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

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

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

Пример: Пусть даны два отношения:

СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРПЛ, ОТД_НОМЕР) ОТДЕЛЫ(ОТД_НОМЕР, ОТД_КОЛ, ОТД_НАЧ)

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

(1).выполнить соединение отношений СОТРУДНИКИ и ОТДЕЛЫ по условию СОТР_НОМ = ОТДЕЛ_НАЧ.

С1 = СОТРУДНИКИ [СОТР_НОМ = ОТД_НАЧ] ОТДЕЛЫ

(2).ограничить полученное отношение по условию ОТД_КОЛ > 50

С2 = С1 [ОТД_КОЛ > 50].

(3).спроецировать результаты предыдущей операции на атрибуты СОТР_ИМЯ, СОТР_НОМЕР

С3 = С2 [СОТР_ИМЯ, СОТР_НОМЕР]

Заметим, что порядок выполнения шагов может повлиять на эффективность выполнения запроса. Так, время выполнения приведенного выше запроса можно сократить, если поменять местами этапы (1) и (2). В этом случае сначала из отношения СОТРУДНИКИ будет сделана выборка всех кортежей со значением атрибута ОТДЕЛ_КОЛ > 50, а затем выполнено соединение результирующего отношения с отношением ОТДЕЛЫ. Машинное время экономится за счет того, что в операции соединения участвуют меньшие отношения. На языке реляционного исчисления данный запрос может быть записан как:

Выдать СОТР_ИМЯ и СОТР_НОМ для СОТРУДНИКИ таких, что существует ОТДЕЛ с таким же, что и СОТР_НОМ значением ОТД_НАЧ и значением ОТД_КОЛ большим 50.

Здесь мы указываем лишь характеристики результирующего отношения, но не говорим о способе его формирования. СУБД сама должна решить какие операции и в каком порядке надо выполнить над отношениями СОТРУДНИКИ и ОТДЕЛЫ. Задача оптимизации выполнения запроса в этом случае также ложится на СУБД.

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

Лекция 7. Нормализация данных. 1-я, 2-я, 3-я нормальные формы

Цель нормализации - устранение избыточности, связанной с хранением неключевых атрибутов.

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

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

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

первая нормальная форма (1NF);

вторая нормальная форма (2NF);

третья нормальная форма (3NF);

нормальная форма Бойса-Кодда (BCNF);

четвертая нормальная форма (4NF);

пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).

Основные свойства нормальных форм:

каждая следующая нормальная форма в некотором смысле лучше предыдущей;

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

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

7.1 Функциональная зависимость

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

Определение 1. Функциональная зависимость

В отношении R атрибут Y функционально зависит от атрибута X (X и Y могут быть составными) в том и только в том случае, если каждому значению X соответствует в точности одно значение Y: R.X R.Y.

Определение 2. Полная функциональная зависимость

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

Определение 3. Транзитивная функциональная зависимость

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

Определение 4. Неключевой атрибут

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

Определение 2~. Полная функциональная зависимость

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

Определение 5. Взаимно независимые атрибуты

Два или более атрибута взаимно независимы, если ни один из этих атрибутов не является функционально зависимым от других.

7.2 Вторая нормальная форма

Рассмотрим следующий пример схемы отношения:

СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ

(СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)

Первичный ключ: СОТР_НОМЕР, ПРО_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР СОТР_ЗАРП

СОТР_НОМЕР ОТД_НОМЕР

ОТД_НОМЕР СОТР_ЗАРП

СОТР_НОМЕР, ПРО_НОМЕР СОТР_ЗАДАН

Как видно, хотя первичным ключом является составной атрибут СОТР_НОМЕР, ПРО_НОМЕР, атрибуты СОТР_ЗАРП и ОТД_НОМЕР функционально зависят от части первичного ключа, атрибута СОТР_НОМЕР. В результате мы не сможем вставить в отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ кортеж, описывающий сотрудника, который еще не выполняет никакого проекта (первичный ключ не может содержать неопределенное значение). При удалении кортежа мы не только разрушаем связь данного сотрудника с данным проектом, но утрачиваем информацию о том, что он работает в некотором отделе. При переводе сотрудника в другой отдел мы будем вынуждены модифицировать все кортежи, описывающие этого сотрудника, или получим несогласованный результат. Такие неприятные явления называются аномалиями схемы отношения. Они устраняются путем нормализации.

Определение 6. Вторая нормальная форма (в этом определении предполагается, что единственным ключом отношения является первичный ключ)

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

Можно произвести следующую декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ в два отношения СОТРУДНИКИ-ОТДЕЛЫ и СОТРУДНИКИ-ПРОЕКТЫ:

СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР)

Первичный ключ: СОТР_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР СОТР_ЗАРП

СОТР_НОМЕР ОТД_НОМЕР

ОТД_НОМЕР СОТР_ЗАРП

СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)

Первичный ключ: СОТР_НОМЕР, ПРО_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР, ПРО_НОМЕР CОТР_ЗАДАН

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

Если допустить наличие нескольких ключей, то определение 6 примет следующий вид:

Определение 6~

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

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

7.3 Третья нормальная форма

Рассмотрим еще раз отношение СОТРУДНИКИ-ОТДЕЛЫ, находящееся в 2NF. Заметим, что функциональная зависимость СОТР_НОМЕР СОТР_ЗАРП является транзитивной; она является следствием функциональных зависимостей СОТР_НОМЕР ОТД_НОМЕР и ОТД_НОМЕР СОТР_ЗАРП. Другими словами, заработная плата сотрудника на самом деле является характеристикой не сотрудника, а отдела, в котором он работает (это не очень естественное предположение, но достаточное для примера).

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

Определение 7. Третья нормальная форма. (Снова определение дается в предположении существования единственного ключа.)

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

Можно произвести декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ в два отношения СОТРУДНИКИ и ОТДЕЛЫ:

СОТРУДНИКИ (СОТР_НОМЕР, ОТД_НОМЕР)

Первичный ключ: СОТР_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР ОТД_НОМЕР

ОТДЕЛЫ (ОТД_НОМЕР, СОТР_ЗАРП)

Первичный ключ: ОТД_НОМЕР

Функциональные зависимости: ОТД_НОМЕР СОТР_ЗАРП

Каждое из этих двух отношений находится в 3NF и свободно от отмеченных аномалий.

Если отказаться от того ограничения, что отношение обладает единственным ключом, то определение 3NF примет следующую форму:

Определение 7~

Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, если находится в 1NF, и каждый не ключевой атрибут не является транзитивно зависимым от какого-либо ключа R.

Лекция 8. Нормализация данных. Нормальные формы более высоких порядков

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

8.1 Нормальная форма Бойса-Кодда

Рассмотрим следующий пример схемы отношения:

СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, СОТР_ИМЯ, ПРО_НОМЕР, СОТР_ЗАДАН)

Возможные ключи:

СОТР_НОМЕР, ПРО_НОМЕР

СОТР_ИМЯ, ПРО_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР CОТР_ИМЯ

СОТР_НОМЕР ПРО_НОМЕР

СОТР_ИМЯ CОТР_НОМЕР

СОТР_ИМЯ ПРО_НОМЕР

СОТР_НОМЕР, ПРО_НОМЕР CОТР_ЗАДАН

СОТР_ИМЯ, ПРО_НОМЕР CОТР_ЗАДАН

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