Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. - Базы данных. Учебник для высших учебных заведений (6-е изд.) - 2009

Пример 5. Деление отношения.

Пусть R1 — проекция SP [П#, Д#], a R2 — отношение с заголовком Д# и телом {Р2, Р4}, тогда результатом деления R1 на R2 будет отношение R с заголовком Г1# и телом {SI, S4}.

R1 R2 R1DIVIDEBYR2

Соединение Cf (Rl, R2) отношений R1 и R2 по условию, заданному формулой f, представляет собой отношение R, которое можно получить путем Декартова произведения отношений R1 и R2 с последующим применением к результату операции выборки по формуле f. Правила записи формулы f такие же, как и для операции селекции.

Другими словами, соединением отношения R1 по атрибуту А с отношением R2 по атрибуту В (отношения не имеют общих имен атрибутов) является результат выполнения операции вида:

(R1 TIMES R2) WHERE А 0 В,

где Q — логическое выражение над атрибутами, определенными на одном (нескольких — для составного атрибута) домене. Соединение Cf (Rl, R2), где формула f имеет произвольный вид (в отличие от частных случаев, рассматриваемых далее), называют также Q-соединением.

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

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

74 Часть 1. Основы построения баз данных

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

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

Результатом операции естественного соединения является отношение R, которое представляет собой проекцию эквисоединения отношений R1 и R2 по общему атрибуту на объединенную совокупность атрибутов обоих отношений.

Пример 6. Q-соединение.

Необходимо найти соединение отношений S и Р по атрибутам Город_Г1 и Город_Д соответственно, причем кортежи результирующего отношения должны удовлетворять отношению «больше» (в смысле лексикографического порядка — по алфавиту).

(S TIMES Р) WHERE Город_П > Город_Д Пример 7. Эквисоединение.

Пусть необходимо найти естественное соединение отношений S и Р по общему атрибуту, характеризующему город (в отношении S — это Город_П, а в отношении Р — Город_Д). Поскольку условие операции требует одинаковости имен атрибутов, по которым выполняется соединение, то применяется операция RENAME переименования атрибутов.

(S RENAME Город_П AS Город) JOIN (Р RENAME Город_Д AS Город)

Дополнительные операции реляционной алгебры, предложенные Дейтом,

включают следующие операции.

Операция переименования позволяет изменить имя атрибута отношения и имеет вид:

RENAME <исходное отношение> <старое имя атрибута> AS <новое имя атрибута>,

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

Например, RENAME Город_П AS Город_размещения_Поставщика.

Замечание.

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

RENAME <отн.> <ст. имя атр.1> AS <нов. имя атр.1>,<ст. имя атр.2> AS <нов. имя агр.2>,... ,<ст. имя aTp.N> AS <нов. имя атр.№>.

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

EXTEND <исходное отношение> ADD <выражение> AS <новый атрибут>,

где к исходному отношению добавляется (ключевое слово ADD) <новый атрибуту подсчитываемый по правилам, заданным <выражением>. Исходное отношение может быть задано именем отношения и с помощью выражения реляционной алгебры, заключенного в круглые скобки. При этом имя нового атрибута не должно входить в заголовок исходного отношения и не может использоваться в <выражении>. Помимо обычных арифметических операций и операций сравнения, в выражении можно использовать различные функции, называемые итоговыми, такие как: COUNT (количество), SUM (сумма), AVG (среднее), МАХ (максимальное), MIN (минимальное).

Например,

EXTEND (РJOIN SP) ADD (Вес * Количество) AS 06щий_Вес.

76 Часть 1. Основы построения баз данных

Замечания.

• Пользуясь операцией расширения, можно выполнить переименование атрибута. Для этого нужно в выражении указать имя атрибута, в конструкции AS определить новое имя этого атрибута, затем выполнить проекцию полученного отношения на множество атрибутов, исключая старый атрибут. Таким образом, запись (EXTEND S ADD Город_П AS Город) [П#, Имя, Статус, Город] эквивалента конструкции S RENAME Город_Г1 AS Город.

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

EXTEND<отн> ADD<выр.1> AS<атр.1>,<выр.2>

AS <атр.2>,... ,<Bbip.N> AS <aTp.N>.

Операция подведения итогов SUMMARIZE выполняет «вертикальные» или групповые вычисления и имеет следующий формат:

SUMMARIZE <исх. отн.> BY (<список атрибутов>) ADD <выр.> AS <новый атрибут>,

где исходное отношение задается именем отношения либо заключенным в круглые скобки выражением реляционной алгебры, <список атрибутов> представляет собой разделенные запятыми имена атрибутов исходного отношения Al, А2,..., AN, <выр.> — скалярное выражение, аналогичное выражению операции EXTEND, а <новый атрибут> — имя формируемого атрибута. В списке атрибутов и в выражении не должен использоваться <новый атрибут>.

Результатом операции SUMMARIZE является отношение R с заголовком, состоящим из атрибутов списка, расширенного новым атрибутом. Для получения тела отношения R сначала выполняется проецирование (назовем проекцию R1) исходного отношения на атрибуты Al, А2,..., AN, после чего каждый кортеж проекции расширяется новым (N+1)-M атрибутом. Поскольку проецирование, как правило, приводит к сокращению количества кортежей по отношению к исходному отношению (удаляются одинаковые кортежи), то можно считать, что происходит своеобразное группирование кортежей исходного отношения: одному кортежу отношения R1 соответствует один или более (если было дублирование при проецировании) кортежей исходного отношения. Значение (N+l)-ro атрибута каждого кортежа отношения R формируется путем вычисления выражения над соответствующей этому кортежу группой кортежей исходного отношения.

Пример 8. Подведение итогов.

Пусть требуется вычислить количество поставок по каждому из поставщиков.

SUMMARIZE SP BY (П#) ADD COUNT AS Количество_поставок

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

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

SUMMARIZE SP BY (Д#) ADD SUM Количество AS Общее_число_поставок AVG Количество AS Среднее_число_поставок.

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

Операцию присвоения можно представить следующим образом: <выражение-цель> := <выражение-источник>,

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

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

S := S UNION {{< П# : 'S6' >, < Имя: 'Борис' >, < Статус: '50' >, < Город_П : 'Мадрид' >}}.

Более удобными операциями изменения тела отношения являются операции вставки, обновления и удаления.

Операция вставки INSERT имеет следующий вид:

INSERT <выражение-источник> INTO <выражение-цель>,

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

UPDATE <выражение-цель> <список элементов>,

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

Например, UPDATE Р WHERE Тип='каленый' Город := 'Киев'. Эта операция предписывает изменить значение атрибута Город (независимо от того, каким оно было) на новое значение — 'Киев' таких кортежей отношения Р, атрибут Тип которых имеет значение 'каленый'.

Операция удаления DELETE имеет следующий вид: DELETE <выражение-цель>,

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

Например, DELETE S WHERE Статус < 20.

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

<выражение1> О <выражение2>,

где оба выражения задают совместимые по структуре отношения, а знак О — один из следующих операторов сравнения: = (равно), Ф (не равно), < (собственное подмножество), < (подмножество), > (надмножество), > (собственное надмножество).

Например, сравнение: «Совпадают ли города поставщиков и города хранения деталей?» можно записать так: S [Город_П] = Р [Город_Д].

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

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

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

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

2. Существуют тождественные преобразования, позволяющие по-разному записывать одно и то же выражение. Например, следующие выражения эквивалентны (здесь А — отношение, С, CI, С2 — выражения):

A WHERE CI AND С2 и (A WHERE CI) INTERSECT (A WHERE С2), A WHERE С1 OR С2 и (A WHERE CI) UNION (A WHERE С2),

A WHERE NOT С и A MINUS (A WHERE С).

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

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

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

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

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

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

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

Словесно алгебраическая версия этого запроса описывается так:

• образовать естественное соединение отношений S и SP по атрибуту П#;

•выбрать из результата этого соединения кортежи с деталью Р2 (в поле Д# должна быть строка Р2);

•спроецировать результат предыдущей операции на атрибуты П# и Город_П.

Этот же запрос в терминах реляционного исчисления можно сформулировать примерно гак: «Получить атрибуты П# и Город_П для таких поставщиков, для которых существует поставка в отношении SP с тем же значением атрибута П# и со значением Р" атрибута Д#».

Читатель может самостоятельно убедиться в этом, проделав описанные выше операции реляционной алгебры.

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

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

• выбрать из отношения SP кортежи, относящиеся к детали Р2;

•выполнить естественное соединение отношения S и отношения, полученного на предыдущем шаге;

•спроецировать текущее отношение на атрибуты П# и Город_П. Экономия памяти при реализации этого алгоритма в сравнении с перво-

начальным вариантом достигается за счет снижения размерности участвующих в операциях временных таблиц, необходимых для хранения промежуточных результатов. Если в предыдущем случае размерность временной таблицы была 12*6 (12 строк на 6 колонок), то в последнем случае — 4*6.

Математической основой реляционного исчисления является исчисление предикатов — один из разделов математической логики. Понятие реляционного исчисления как языка работы с базами данных впервые предложено Коддом. Им же был разработан язык ALPHA — прототип программно реализованного языка QUEL, который некоторое время конкурировал с языком SQL.

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

Реляционное исчисление, основанное на кортежах {исчисление кортежей),

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

RANGE OF <переменная> IS <список>,

где прописными буквами записаны ключевые слова языка, <переменная> — идентификатор переменной кортежа (области значений), а <список> — последовательность одного или более элементов, разделенных запятыми, то есть конструкция вида: х, [, х2 [..., хп]...].

Вся конструкция RANGE указывает идентификатор переменной и область ее допустимых значений. Список элементов х, [, х2 [... , xj...] содержит элементы, каждый из которых является либо отношением, либо выражением над отношением (порядок записи выражений описывается далее). Все элементы списка должны быть совместимы по типу, то есть соответствующие элементам отношения должны иметь идентичные заголовки. Область допустимых значений <переменной> образуется путем объединения значений всех элементов списка. Так, запись вида RANGE OF Т IS XI,Х2 означает, что область определения переменной Т включает в себя все значения из отношения, которое является объединением отношений XI и Х2.

Пример 1. Варианты описаний.

RANGE OF SX IS S; RANGE OF SPX IS SP;

RANGE OF SY IS (SX) WHERE 5Х.Город_П = 'Москва',

(SX) WHERE EXISTS SPX (SPX.n# = SX.n# AND 5РХ.Д# = 'Pi');

Переменные SX и SPX в первых двух примерах определены соответственно на отношениях S и SP соответственно (рис. 3.7). Третий пример иллюстрирует запись выражений при определении переменной кортежа. Переменная SY здесь может принимать значения из множества кортежей отношения S для поставщиков из Лондона или поставщиков, которые поставляют деталь Р1 (или для тех и других).

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

<выражение> ::= (у, [, у2 [..., ут ]...]) [ WHERE wff ]

у ::= {<переменная> | <переменная>.<атрибут> } [ AS <атрибут> ] Wff ::= <условие> |

NOT wff | <условие> AND wff | <условие> OR wff |

IF <условие> THEN wff | EXISTS <переменная> (wff) | FORALL <переменная> (wff) | (wff)

82 Часть 1. Основы построения баз данных

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

В паре <переменная>.<атрибут> первая составляющая служит для указания переменной кортежа (определенной конструкцией RANGE), а вторая — для определения атрибута отношения, на котором изменяется переменная кортежа. Необязательная часть «AS <атрибут>» используется для переименования целевого отношения. Если она отсутствует, то имя атрибута целевого отношения наследуется от соответствующего имени атрибута исходного отношения.

Употребление в качестве элемента целевого отношения просто имени переменной Т равносильно перечислению в списке всех соответствующих атрибутов, т. е. Т.А(, Т.А2, ... , Т.Ап, где AJf А2, ... , Ап — атрибуты отношения, сопоставляемого с переменной Т.

Пример 2. Варианты записи пары <переменная>.<атрибут>.

sx.n#

SX.n# AS Город_Поставщика SX

SXXI#, 5Х.Город_П AS Город_Г1оставщика, РХ.Д#, РХ.Город_Д# AS Город_Летали

В приведенном определении wff <условие> представляет собой либо формулу wff, заключенную в скобки, либо простое сравнение вида:

<операнд1> О <операнд2>,

где в качестве любого операнда выступает переменная или скалярная константа, а символ © обозначает операцию сравнения =, Ф, >, >, <, < и т. д.

Ключевые слова NOT, AND и OR обозначают логические операции соответственно: И, НЕ и ИЛИ. Ключевые слова IF и THEN переводятся соответственно «если» и «то». И наконец, ключевые слова EXISTS й FORALL называются кванторами. Первый из них — квантор существования, а второй — квантор всеобщности. Рассмотрим эти кванторы несколько подробнее.

Формула wff вида: EXISTS х (f) означает: «Существует по крайней мере одно такое значение переменной х, что вычисление формулы f дает значение истина». Выражение вида: FORALL х ( 0 интерпретируется как высказывание: «Для всех значений переменной х вычисление формулы f даст значение истина». В общем случае переменные кортежей в формулах могут быть свободными или связанными. В формулах EXISTS х (f) и FORALL х (f) переменные кортежей х всегда являются связанными.