2014-02-03
659
Работа с базами данных прежде всего требует понимания вопросов связанных с процессом получения требуемой информации непосредственно из хранимых данных. При работе с иерархическими или сетевыми базами данных основу языков манипулирования данными составляет список операторов, позволяющих оперировать минимальными структурными единицами, например записью в сетевой модели, сегментом в иерархической модели. Подобный уровень языка манипулирования данными приводит к тому, что запросы к базе данных приходится программировать на внешних языках типа КОБОЛ, ПЛ/1, в которых стандартным образом с помощью оператора вызова процедур используются операторы языка манипулирования данными.
Реляционная модель дает нам основу для построения более мощных языков манипулирования данными, ибо позволяет манипулировать как объектами языка целыми множествами хранимых данных. Несмотря на то, что в настоящий момент нет промышленных систем управления реляционными базами данных, реляционную модель и соответствующий язык манипулирования данными можно использовать с целью автоматической генерации программ доступа к базам данных сетевого и иерархического типа. Подобный подход завоевывает в настоящее время все большую популярность, ибо не требует слишком высокой квалификации при программировании запросов и в значительной степени ориентирован на конечного пользователя. В качестве основы языков манипулировании данными в реляционной модели рассмотрим алгебру отношений. Алгебра отношений дает основу для построения процедурных языков манипулирования.
|
|
|
Алгебра отношений
Формально отношение есть подмножество декартового произведения некоторых множеств (доменов – областей определения).
Например, пусть имеется два подмножества:
D1: {d1, d2, d3} – множество деталей;
D2: {m1, m2, m3, m4} – множество материалов.
На этих двух множествах можно задать отношение R, интерпретируемое как «возможность изготовления детали из материала»:
R Í D1´D2,
где ´ - символ операции декартового произведения. Отношение R есть множество пар, которое формально есть подмножество всех возможных пар:
R Í D1´D2
d1 m3 d1 m1; d2 m1; d3 m1;
d2 m2 Í d1 m2; d2 m2; d3 m2;
d2 m4 d1 m3; d2 m3; d3 m3;
d3 m1 d1 m4; d2 m4; d3 m4;
Отношение, будучи множеством, может быть задано перечислением элементов. Так как элементы отношения представляют собой кортежи, идентичные по своей структуре, то все отношение может быть представлено в форме таблицы R(A1, A2), где A1 и A2 есть имена атрибутов, которые можно рассматривать как имена подмножеств, определенных на множествах A1 на D1 и A2 на D2, соответственно:
R(A1, A2)
|
|
|
d1 m3
d2 m2
d2 m4
d3 m1
В общем случае отношение R может иметь n атрибутов, что определяет степень отношения. В рассмотренном примере n = 2. Количество выборок определяет мощность отношения М, в примере М = 4. Идентификатор отношения и совокупность имен атрибутов составляют схему отношения. Схема базы данных определяется совокупностью схем отношений. Заметим еще раз, что данный случай характеризуется тем, что схема базы данных состоит из сравнительно небольшого числа схем отношений, но каждое отношение есть множество достаточно большой мощности, исчисляемой тысячами и десятками тысяч кортежей.
В реляционном подходе ответ на конкретный запрос также представляется в форме отношения, поэтому в основе средств, используемых для формулировки запроса, может лежать алгебра отношений. Алгебра отношений, как самостоятельная математическая дисциплина, была развита достаточно давно, но, видимо, Е. Кодд был первым, кто предложил использовать отношения и алгебру отношений для моделирования поисковых процессов в больших базах данных.
Как известно, алгебра есть совокупность
А: <H, S>
носителя Н – в данном случае множество отношений и сигнатуры S – в данном случае множество операций над отношениями. Можно придумать много вариантов операций для реляционной алгебры; изучим только операции, использованные Е. Коддом.
Все множество S операций реляционной алгебры целесообразно разбить на два подмножества.
Стандартные теоретико-множественные операции: объединение - È; пересечение - Ç; разность - \; декартово произведение - ´.
Специальные операции: проекция; ограничение; соединение; деление.
Операции реляционной алгебры либо унарны, т. е. используются в качестве операнда только одно отношение, либо бинарны, когда имеются два операнда. Рассмотрим более подробно каждую из операций.
Операции объединение, пересечение и разность двух отношений
R1(A1, A2, …, An)
и R2(B1, B2, …, Bn)
возможны только в том случае, когда отношения R1, R2 являются объединяемыми.
Это означает, что степени объединяемых отношений идентичны, а соответственные атрибуты определены на одних и тех же доменах. Например, атрибут А1 из R1 и B1 из R2 определены на домене D1.
В результате операции объединения получающееся отношение имеет ту же степень, что и исходные
Rрез(С1, …, Cn) = R1(A1, …, An) È R2(B1, …, Bn),
а мощность Mрез лежит в пределах:
max (M1, M2) £ Mрез £ M1 + M2.
Имена атрибутов результирующего отношения могут быть выбраны произвольно, но атрибуты определяются на тех же доменах, что и в исходных отношениях. В частности, во всех трех отношениях могут быть использованы идентичные имена атрибутов, если это не ведет к путанице.
В результате операции пересечения
Rрез(С1, …, Cn) = R1(A1, …, An) Ç R2(B1, …, Bn)
степень отношения также сохраняется, а мощность лежит в пределах:
0 £ Mрез £ min (M1, M2).
При операции взятия разности двух отношений
Rрез(С1, …, Cn) = R1(A1, …, An) \ R2(B1, …, Bn)
Степень сохраняется, а мощность лежит в пределах:
0 £ Mрез £ M1.
Пример с указанными операциями представлен на рис.1. Последней из теоретико-множественных операций является операция декартового произведения отношений
Rрез(С1, …, Cn) = R1(A1, …, An) ´ R2(B1, …, Bn)
при которой степень результирующего отношения есть сумма степеней исходных, а мощность
Mрез = М1 ∙ М2.
Исходные отношения:
R1 (КД, КМ, ЕИ, НР) R2 (КД’, КМ’, ЕИ’, НР’)
Д1 М2 1 15 Д2 М5 3 3
Д2 М5 3 3 Д3 М3 2 15
Д2 М9 3 5
Д3 М2 1 10
1. Объединение Rрез = R1ÈR2
Rрез (КД, КМ, ЕИ, НР)
Д1 М2 1 15
Д2 М5 3 3
Д2 М9 3 5
Д3 М2 1 10
Д3 М3 2 15
2. Пересечение Rрез = R1ÇR2
Rрез (КД, КМ, ЕИ, НР)
Д2 М5 3 3
3. Разность Rрез = R1 \ R2
Rрез (КД, КМ, ЕИ, НР)
Д1 М2 1 15
Д2 М9 3 5
Д3 М2 1 10
Рис.11.1 Применение к отношениям теоретико-множественных операций
В результате этой операции осуществляется конкатенация (приписывание) кортежей (строк) отношений, причем каждая строка конкатенирует с каждой. Никаких ограничений на степени исходных отношений и природу атрибутов не накладывается.
|
|
|
Перейдем к рассмотрению специальных отношений.
Проекция. Операция является унарной и предназначена для изменения степени отношения и порядка вхождения атрибутов в схему. Пусть имеется исходное отношение
R1 (A1, …, An)
и список атрибутов А. Проекция отношения R1 на список A обозначается следующим образом:
Rрез (А) = R1 [A1],
где квадратные скобки являются операционными. При выполнении операции проекция на первом этапе из таблицы, представляющей исходное отношение, вычеркиваются все столбцы, соответствующие атрибутам, не вошедшим в список А. В результате, получается срез отношения. Срез отношения не является отношением в полном смысле, так как там могут быть идентичные строки. Чтобы получить результирующее отношение, необходимо выбросить лишние строки из среза.
Пример: R1 (КД, КМ, ЕИ, НР)
Д1 М2 1 15
Д2 М5 3 3
Д2 М9 3 5
Д3 М2 1 10
Проекция на атрибут КД:
Rрез (КД) = R1 [КД]
В результате вычеркивания столбцов, соответствующих атрибутам, не вошедших в список А = {КД}, получаем срез:
Д1
Д2
Д2
Д3
В полученном срезе необходимо удалить лишний элемент Д2, в результате чего
Rрез (КД) = R1 [КД]
Д1
Д2
Д3
Если спроектировать это же отношение на список А = {КМ, ЕИ}, то срез будет
М2 1
М5 3
М9 3
М2 1,
а проекция будет
М2 1
М5 3
М9 3
Таким образом, проектируя некоторое исходное отношение, прежде всего уменьшаем степень отношения, но при этом может уменьшиться и мощность отношения:
1 £ Мрез £ М1
Ограничение. Так же как и проекция, ограничение является унарной операцией, но в отличие от проекции ориентирована на выделение нужных строк отношения. Пусть имеется исходное отношение
R1 (A1, …, An).
При ограничении производится либо сужение подмножества значений некоторых атрибутов, например А1 «Константа», причем «Константа» выбирается из домена, на котором определен атрибут А1, либо происходит сопоставление атрибутов, например, А2 = А4, при этом и А2, и А4 должны быть определены на одном и том же домене. При проверке очередной выборки (строки) отношения на введенные условия при подстановке вместо имен атрибутов конкретных значений получающиеся элементарные высказывания могут быть либо истинными, либо ложными. Если булевское выражение, составленное из элементарных высказываний (их иногда называют термами сравнения) с помощью связок &(И), Ú(ИЛИ), будет истинными, то выборка попадает в результирующее отношение, если нет – то не попадает.
|
|
|
Таким образом, термы сравнения могут иметь следующий вид:
(Aiq «Константа») или (А1 q Aк),
где q Î {=, ¹, >, <, ³, £}, а операция ограничения в общем виде записывается следующим образом:
Rрез (A1, …, An) = R1 [A1 q1 «Константа») & … & (Ai qm Ak)] (возможна и дизъюнкция термов). Как видно, степень результата остается прежней, а мощность лежит в пределах:
0 £ Мрез £ М1
Пример: Для отношения
R1 (КД, КМ, ЕИ, НР)
Д1 М2 1 15
Д2 М5 3 3
Д2 М9 3 5
Д3 М2 1 10
Найти все выборки, в которых единица измерения (ЕИ) имеет код «1», а норма расхода (НР) больше или равна 10:
Rрез (КД, КМ, ЕИ, НР) = R1 [(ЕИ = «1») & (НР ³ «10»)].
В результате имеем
Rрез (КД, КМ, ЕИ, НР)
Д1 М2 1 15
Д3 М2 1 10
Соединение: Операция соединения двух отношений является важнейшей и часто используемой. При этой операции выборки одного отношения конкатенируются (соединяются) с выборками другого, как и при декартовом произведении двух отношений, но конкатенация происходит только при условии, что булевское выражение, в каждый терм которого входят атрибуты обоих отношений, принимает значение «истина».
Итак, для двух исходных отношений
R1 (A1, …, An)
и R2 (В1, …, Вm)
в результате операции соединения получается отношение
Rрез (A1, …, An, B1, …, Bm) = R1 [(булевское выражение)] R2.
В булевском выражении термы имеют вид, например
(А1 q B1),
где атрибуты A1 и B1 определены на одном домене. Очень часто булевское выражение состоит из единственного терма сравнения, в котором q есть «=». Это частный случай называется операцией эквисоединения двух отношений по атрибутам A1 и B1.
Смысл операции соединения двух отношений более четко можно выразит сведением операции к ранее введенным:
Rрез (A1, …, An, B1, …, Bm) =
= R1 [(булевское выражение)] R2 =
= (R1 ´ R2) [(булевское выражение)],
то есть операция соединения сводится к декартовому произведению отношений с последующим ограничением получаемого промежуточного отношения. Это означает, что мощность результата:
0 £ Мрез £ М1 М2.
Пример: Пусть заданы
R1 (КД, КМ, ЕИ, НР)
Д1 М2 1 15
Д2 М5 3 3
Д2 М9 3 5
Д3 М2 1 10
и
R2 (КМ’, НМ)
М2 Ст-5
М5 Ст-7
и требуется приписать к шифру материала его наименование. Это можно произвести с помощью операции эквисоединения
Rрез (КД, КМ, ЕИ, НР, КМ’, НМ) = R1 [(КМ = КМ’)] R2.
В результате получим
Д1 М2 1 15 М2 Ст-5
Д2 М5 3 3 М9 Ст-7
Д3 М2 1 10 М2 Ст-5
при этом избавиться от лишних столбцов и поменять столбцы местами (если нужно) можно с помощью последующей операции проекции.
Рассмотрим более подробно, как получается результат, сведя операцию соединения к последовательности операций декартова произведения и ограничения:
R1 [(КМ = КМ’)] R2 = (R1 ´ R2) [(КМ = КМ’)]
(R1 ´ R2) = Rпром (КД, КМ, ЕИ, НР, КМ’, НМ)
Д1 М2 1 15 М2 Ст-5
Д2 М5 3 3 М2 Ст-5
Д2 М9 3 5 М2 Ст-5
Д3 М2 1 10 М2 Ст-5
Д1 М2 1 15 М9 Ст-7
Д2 М5 3 3 М9 Ст-7
Д2 М9 3 5 М9 Ст-7
Д3 М2 1 10 М9 Ст-7
Чтобы получить результат Rпром, необходимо ограничить:
Rрез (КД, КМ, ЕИ, НР, КМ’, НМ) = Rпром [(КМ = КМ’)]
Д1 М2 1 15 М2 Ст-5
Д3 М2 1 10 М2 Ст-5
Д2 М9 3 5 М9 Ст-7
Интересно отметить, что в результирующем отношении нет сведений о нормах расхода материала «М5». Это произошло потому, что в справочнике наименований материалов (отношение R2) нет сведений об «М5», и формальное эквисоединение двух отношений выбросило строки с «М5» из результата.
Деление. Чтобы понять сущность операции деления отношений, целесообразно рассмотреть упрощенный пример.
Пусть нам задано отношение R1 (КД, КМ), которое задает возможные варианты изготовления деталей из разных материалов:
R1 (КД, КМ)
Д1 М2
Д2 М5
Д2 М9
Д3 М2
Д3 М5
Д2 М3
и
R2 (КМ)
М5
М9
Кроме того, задан список R2 (КМ) и требуется определить детали, которые могут быть сделаны из всех материалов, заданных в списке R2.
Ответ в данном случае очевиден, это деталь Д2, так как список R2 есть подмножество материалов, из которых может быть сделана деталь Д2:
{M5, M9} Í {M3, M5, M9}.
Формально список деталей определяется с помощью операции деления:
Rрез (КД) = R1 [КМ ¸ КМ] R2.
В общем случае имеется два отношения:
R1 (A1, …, An)
и R2 (В1, …, Вm)
и задан список атрибутов А, так что, не теряя общности, отношения R1 и R2 можно представить в виде
R1 (¯А, A) и R2 (А, ¯В),
где ¯А и ¯В есть дополнение списка А до полного списка атрибутов отношения R1 и R2 соответственно. Тогда
Rрез (¯А) = R1 [А ¸ А] R2.
Степень результирующего отношения определяется количеством атрибутов в списке ¯А, а мощность Мрез £ М1.
Чтобы более точно объяснить смысл операции деления, целесообразно выразить ее через ранее введенные операции. Что необходимо сделать? Необходимо дать перечень объектов из R1 [¯А], каждый из которых обладал бы совокупностью свойств R2 [А]. Для того чтобы это сделать, наделим все объекты, задаваемые совокупностью атрибутов ¯А и принадлежащие R1, совокупностью свойств R2 [А]. Это можно сделать спомощью декартова произведения:
R1 [¯А] ´ R2 [А].
В конкретном примере с деталями и материалами получим
R1 [КД] ´ R2 [КМ]
Д1 М5
Д1 М9
Д2 М5
Д2 М9
Д3 М5
Д3 М9
Получаемое в результате произведения, промежуточное отношение объединимо с отношением R1, поэтому можно взять разность
R1 [¯А] ´ R2 [А] \ R1 (¯А, A),
которая, будучи спроектированной на список ¯А:
(R1 [¯А] ´ R2 [А] \ R1 (¯А, A)) [¯А],
дает перечень объектов, не обладающих списком свойств R2 [А].
На примере
R1 [КД] ´ R2 [КМ] \ R1 (КД, КМ)
Д1 М5 Д1 М2
Д1 М9 Д2 М5 Д1 М5
Д2 М5 \ Д2 М9 Д1 М9
Д2 М9 Д2 М3 = Д3 М9
Д3 М5 Д3 М2
Д3 М9 Д3 М5
и после проектирования получаем список деталей {Д1, Д3}, которые не могут быть сделаны как из материала «М5», так и из «М9». После этого список объектов, обладающих свойствами R2[A], находится элементарно
Rрез (¯А) = R1 [¯А] \ (R1 [¯А] ´ R2 [А] \ R1 (¯А, A)) [¯А].
Именно таким образом операция деления выражается через ранее введенные операции. Полученное выражение точно описывает смысл операции деления.
Продолжается конкретный пример, получим
Rрез (КД) = R1 [КД] \ (R1 [КД] ´ R2 (КМ) \ R1 (КД, КМ)) [КД].
{Д1, Д2, Д3} \ {Д1, Д3} = {Д2}.
Заканчивая рассмотрение операции деления, укажем на следующее свойство:
(R1 (A) ´ R2 (B)) [B ¸ B] R2 (B) = R1 (A),
то есть операция деления обратна операции умножения, что проливает свет на название операции.
Рассмотрение алгебры отношений завершим построением запроса. Пусть схема базы данных задается следующей совокупностью схем отношений:
R1 (КД, КМ, ЕИ, НР);
R2 (КМ, НМ).
Требуется перечислить шифры материалов и их наименования, которые идут на изготовление одной детали в количестве, большем, чем на 25 кг (код кг – «3»):
Rрез (КМ, НМ) = (((R1 [ЕИ = «3») & (НР > «25»)]) ([КМ])
([КМ = КМ’]R2) [КМ, НМ].
Круглые скобки определяют последовательность действий:
o Ограничение отношения R1;
o Проектирование промежуточного отношения;
o Соединение с R2;
o Проектирование с получением результата.
Четкая последовательность действий характеризует степень «процедурности» запроса. Говорят, что алгебра отношений лежит в основе процедурных языков манипулирования данными в реляционной модели баз данных.
