Реляционный подход в настоящее время представляет наиболее развитую идеологию построения БД и БЗ. Реляционная модель данных была предложена в начале 70-х годов американским ученым Э.Ф. Коддом, за что в 1981 г. он был удостоен премии Тьюринга Американской ассоциации по вычислительной технике.
Структура данных. В основе реляционной модели лежит понятие «отношение», представляющее собой подмножество декартова произведения доменов. Домен – некоторое множество элементов (например, множество целых чисел или множество допустимых значений, которые может принимать объект по некоторому свойству и т.п.).
Декартовым произведением доменов D 1, D 2,..., Dk является выражение вида
D = D 1 × D 2 ×... × Dk,
где
Это множество всех кортежей, состоящих из k элементов – по одному из каждого домена Di:
Например, если
D 1 = { A, 2}, D 2 = { B, C }, D 3 = { 4, 5, D },
то k = 3 и соответственно
D = D 1 × D 2 × D 3 = {(А, В,4), (А, В,5), (А, В, D),(А, С, 4), (А, С,5),
(А, С, D),(2, В,4), (2, B, 5), (2, B, D), (2, С, 4), (2, С, 5), (2, С, D)},
т.е. декартово произведение позволяет получить все возможные комбинации элементов исходных множеств рассматриваемых доменов.
Отношением R на множествах D 1, D 2,..., Dk называется подмножество декартова произведения D 1× D 2×... × Dk. Иными словами, отношение R,определенное на множествах D 1, D 2,..., Dk (причем не обязательно, чтобы эти множества были различными), есть некоторое множество кортежей арности k:
Элементами отношения являются кортежи. Арность кортежа определяет арность отношения.
Отношения арности 1 часто называют унарным, арности 2 – бинарным, арности 3 – тернарным, арности k – парным. Поскольку отношение есть множество, в нем не должны встречаться одинаковые кортежи и, кроме того, порядок кортежей в отношении несуществен.
|
|
Укажем в данном примере несколько отношений:
В ряде случаев отношение удобно представлять как таблицу, где каждая строка – это кортеж, а каждый столбец соответствует одному и тому же компоненту декартова произведения (т.е. в нем могут появляться только элементы из соответствующего домена). Таблица, представляющая парное отношение R, обладает следующими свойствами:
• каждая строка представляет собой кортеж из k значений, принадлежащих k столбцам;
• порядок столбцов фиксирован (1, 2,..., k);
• порядок строк безразличен;
• любые две строки различаются хотя бы одним элементом;
• строки и столбцы таблицы могут обрабатываться в любой последовательности, определяемой применяемыми операциями обработки.
Использование отношений для представления данных. Для представления данных математическое отношение используется двояко:
• для представления набора объектов (напомним, что набор объектов представляет собой группу подобных объектов);
• для представления связей между наборами объектов.
Для представления набора объектов атрибуты интерпретируются столбцами отношения, а множество допустимых значений атрибута – соответствующим доменом. Каждый кортеж отношения выполняет роль описания отдельного объекта из набора, само отношение – всего набора объектов.
Пусть имеется:
1) набор объектов Е
Е = { е 1, е 2,..., еi,..., еn };
2) множество атрибутов, описывающих набор
А = { А 1, А 2,..., Aj,..., Аm };
|
|
3) множество значений по каждому атрибуту (которые этот атрибут
может принимать):
При выполнении интерпретации объявляем, что:
1) 1-й столбец отношения соответствует атрибуту А 1;2-й столбец отношения – атрибуту А 2;...; т -й столбец отношения – атрибуту Ат.
2) каждому атрибуту соответствует домен:
D 1 = K 1, D 2= K 2, …, Dm = Km;
3) отношение
описывает набор объектов Е.
В этом отношении R будет п кортежей – по числу объектов в наборе Е. Каждый кортеж r i отношения R описывает отдельный объект еi из набора объектов Е.
Если атрибут Аi (или совокупность атрибутов { А 1, А 2,..., Аz }) является ключом, то значение в столбце i (или совокупность значений из столбцов 1,2,..., z) некоторой строки отношения R однозначно идентифицирует эту строку (кортеж) в данном отношении. Таким образом, по значению ключа всегда найдем в отношении кортеж, описывающий интересующий нас объект. Например, нас интересует описание объекта Аj. Известно, что значение ключа Aj для этого объекта равно kj3. Находим в отношении R строку, у которой в столбце j находится значение kj3. Это и будет искомое описание объекта eh.
Отношение также используется для представления связей между наборами объектов Е 1, Е 2,..., Еk.
Кортеж ri в отношении R в этом случае обозначает список объектов:
где
Чтобы реализовать такую ситуацию, каждому столбцу отношения R ставят в соответствие ключевой атрибут соответствующего набора объектов. Например, 1-й столбец соответствует ключевому атрибуту набора Е 1; 2-й столбец – Е 2;...; k -йстолбец – Ek.
Наличие кортежа ri в отношении R указывает, что объекты e 1 i 1, е 2 i 2,..., ekik ассоциируют между собой с помощью связи, представляемой отношением R.
|
|
Схема отношения. Традиционная форма определения теоретико-множественного отношения предполагает работу с линейными списками при обработке данных. Такая форма представления оказывается удобной для обсуждения операций реляционной алгебры, но не всегда целесообразна из-за фиксированного порядка столбцов в отношении (в целом ряде практических приложений возникает необходимость перестановки столбцов в отношениях в любом порядке). Чтобы устранить необходимость фиксированного порядка столбцов в отношении, последние именуют. Присвоение столбцам отношений имен делает их порядок в отношении несущественным (т.е. столбец определяется по его имени, а не по порядковому номеру). При таком подходе оказываются эквивалентными отношения (например, два отношения, отличающиеся порядком столбцов), которые не были бы эквивалентными при традиционном определении.
Итак, столбцы отношения назовем атрибутами и присвоим им имена. В этом случае можно будет говорить об отображении имен атрибутов в множества значений, принадлежащих доменам атрибутов.
Список имен атрибутов отношения называется схемой отношения. Если отношение называется R и его схема имеет атрибуты А 1, А 2,..., Аk,то схема отношения обозначается следующим образом:
R (A 1, A 2,..., Ak).
Существует аналогия между схемой отношения и форматом записи, между кортежем и записью, между отношением и файлом. Одной из возможных реализаций отношения является файл записей, формат которых соответствует схеме отношения.
Реляционная БД содержит конечное множество экземпляров отношений. Схему реляционной базы данных можно представить в виде
Выполнение операций над отношениями. Для получения информации из отношений необходим ЯМД, выполняющий соответствующие операции над отношениями. Наиболее важной частью ЯМД является его раздел для формулировки запросов. Поскольку запросы в общем случае представляют собой произвольные функции над отношениями, необходимо решить вопрос о требуемой выразительности языка запросов. Для исследования этого вопроса были разработаны три абстрактных теоретических языка:
1)реляционная алгебра;
2) реляционное исчисление с переменными-кортежами;
3) реляционное исчисление с переменными-доменами.
Языки запросов первого типа – алгебраические языки – позволяют выражать запросы средствами специализированных операторов, применяемых к отношениям.
Языки второго и третьего типов – языки исчисления – позволяют выражать запросы путем спецификации предиката, которому должны удовлетворять требуемые кортежи (или домены).
Все эти языки предложил Е.Ф. Кодд для оценки возможностей реальных языков запросов к реляционной модели данных. По своей выразительности все три языка оказались эквивалентны между собой.
Реальные языки (ISBL, SEQUEL, QBE и др.) обеспечивают не только функции соответствующего теоретического языка или их комбинации, но и реализуют некоторые дополнительные операции (арифметические операции, команды присваивания, печати и т.п.).
Реляционная алгебра. При определении операций реляционной алгебры предполагается, что порядок столбцов в отношении фиксирован, сами отношения конечны.
Основные операции реляционной алгебры.
1. Объединение отношений R 1и R 2:
Операция применяется только к отношениям одной и той же арности.
2. Разность отношений R 1 и R2:
R = R 1 - R 2.
Разностью (R 1 - R 2)называется множество кортежей, принадлежащих отношению R 1, но не принадлежащих отношению R 2.
Отношения R 1, R 2 и R должны быть одинаковой арности.
3. Декартово произведение отношений R 1и R2:
R = R 1´ R 2.
Если отношение R 1имеет арность k 1,а отношение R 2– арность k2, то декартовым произведением R 1´ R 2отношений R 1и R 2называется множество кортежей арности (k 1+ k 2),причем первые k 1элементов образуют кортеж из отношений R 1,а последние k 2 элементов образуют кортеж из отношения R 2.
4. Проекция отношения R 1на компоненты i 1, i 2,..., ir:
где i 1, i 2,..., ir – номера столбцов отношения R 1.
Операция проекции заключается в том, что из отношения R 1выбираются указанные столбцы и компонуются в указанном порядке.
5. Селекция отношения R 1по формуле F:
где F – формула, образованная:
– операндами, являющимися номерами столбцов;
– логическими операторами:
Ù (and, и), Ú (or, или), ù (not, не);
– арифметическими операторами сравнения
=, ≠, >, ≥, <, ≤;
В формуле могут использоваться скобки.
Следующие операции реляционной алгебры могут быть получены с помощью основных, но они имеют самостоятельное значение.
6. Пересечение отношений R 1и R 2:
R = R 1 Ç R 2 = R 1 – (R 1 – R 2).
7.Частное отношений R 1и R 2:
R = R 1: R 2 = П1,2,… n-m (R 1) – П1,2,… n-m (П1,2,… n-m (R 1) ´ R 2) – R 1)
где п – арность отношения R 1; т – арность отношения R 2; п > т, R 2 ¹ Æ.
8. Соединение отношений R 1и R 2:
R = R 1 Ä R 2 = s i q(n + j) (R 1 ´ R 2),
где s – арифметический оператор сравнения; п – арность отношения R 1; i и j – номера столбцов соответственно в отношениях R 1и R2.
Если T является арифметическим оператором равенства, то операцию называют эквисоединением.
В приведенных выше операциях использовано обращение к элементам кортежей по номерам столбцов отношения. Если будет обращение по имени столбцов, при этом, естественно, должны выполняться преобразования имени столбца в его порядковый номер и обратно. Тогда в случае использования имен атрибутов отношения R можно подставлять имена в формулы. Например, если имеется отношение со схемой R (A, В, С, D),то можно записать
9. Естественное соединение отношений R 1и R 2.
Эта операция применяется только тогда, когда столбцы отношений R 1и R 2 имеют имена.
Пусть отношения R 1и R 2имеют соответственно схемы:
где имена А 1, А 2,..., A kу обоих отношений совпадают, а остальные различаются (для упрощения совпадающие имена поместим в начале, но они, конечно, могут быть записаны в любом другом порядке):
где R 1. A 1– имя столбца отношения (R 1´ R 2), соответствующего столбцу А 1в отношении R 1; R 2. A 1– имя столбца отношения (R 1´ R 2),соответствующего столбцу A 2, в отношении R 2.
В заключение отметим, что конечность отношений делает недопустимой в реляционной алгебре операцию дополнения ù R, поскольку отношение ù R является бесконечным (это бесконечное множество всех кортежей, не принадлежащих R).
Реальным языком запросов, реализующим реляционную алгебру, является, например, алгебраический язык ISBL (Information System Base Language).
Реляционное исчисление с переменными кортежами. Выражения реляционного исчисления с переменными кортежами записываются в следующем виде:
где t – единственная свободная переменная – кортеж, обозначающая кортеж фиксированной длины; если необходимо указать арность кортежа, то используют запись t( i )где i – арность кортежа t; Y – некоторая формула, построенная по специальным правилам (для обозначения переменных-кортежей будем использовать прописные буквы). Например, выражение
{ t / R 1(t) Ú R 2(t)},
где в качестве формулы выступает конструкция R 1(t)v R 2(t),означает, что нас интересует множество всех кортежей t, причем таких кортежей, которые принадлежат отношению R 1или отношению R 2. Отметим, что формула (R 1(t) Ú R 2(t)имеет смысл только тогда, когда отношения R 1и R 2 имеют одинаковую арность (поскольку переменная-кортеж t задана как переменная фиксированной длины). Приведенное выражение { t / R 1(t) Ú R 2(t)}эквивалентно операции объединения (R 1 È R 2)реляционной алгебры.
Формулы в реляционном исчислении строятся из атомов и совокупности операторов (арифметических и логических).
Атомы формул бывают трех типов:
1) R (t), где R – имя отношения. Этот атом означает, что t есть кортеж в отношении R;
2) s [ i ]q u [ j ],где s и и – переменные-кортежи; q – арифметический оператор отношения; i, j – номера или имена интересующих нас компонентов (столбцов) в соответствующих кортежах; s [ i ]– обозначение i -го компонента в кортеже-переменной s; u [ j ]– обозначение j -го компонента в кортеже-переменной и.
Например, атом (s [3]³ и [5])означает, что третий компонент переменной s больше или равен пятому компоненту переменной и;
3) s [ i ]q а или а q s [ i ], где а – константа.
Например, атом (s [4] = 70) означает, что четвертый компонент переменной-кортежа s равен 70.
При записи формул используется понятие «свободных» и «связанных» переменных-кортежей, что определяется характером использования в формуле кванторов:
" – квантор всеобщности (общности); читается: все, всякий, каков бы ни был и т.п.
$ – квантор существования; читается: некоторые, хотя бы один, существует и т.п.
Вхождение переменной X в формуле Y связано, если в Yоно находится в подформуле, начинающейся квантором " или $, за которым непосредственно следует переменная X и о котором говорят в данном случае, что он связывает переменную X. В остальных случаях вхождение переменной X в формулу Y свободно. Например, в формуле
(" x)(R (x, y) Ú ($ y)(U (x, y, z) Ù Q (x, y))) Ú (" x)($ r)(U (x, y, z) Ú ($ x) F (x))
все вхождения x связаны, первое и последнее вхождения у свободны, остальные вхождения переменной у связаны, все вхождения переменной z свободны, единственное вхождение переменной r связано.
Кванторы в реляционном исчислении играют ту же роль, что и декларации в языке программирования. Понятие свободной переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие связанной переменной аналогично понятию локальной переменной, описанной в текущей процедуре.
Формулы, а также свободные и связанные вхождения переменных-кортежей в эти формулы определяются рекурсивно следующим образом:
1. Каждый атом есть формула. Все вхождения переменных-кортежей,
упомянутые в атоме, являются свободными.
2. Если f 1 и f 2– формулы, то:
f 1 Ù f 2(утверждает, что f 1 и f 2 являются истинными),
f 1 Ú f 2 (утверждает, что f 1 или f 2, или обе истинны),
ù f 1 (утверждает, что f 1 не истинна) также являются формулами.
Экземпляры переменных-кортежей являются свободными или связанными в (f 1 Ù f 2), (f 1 Ú f 2) и (ù f 1) точно так же, как они являются свободными или связанными в f 1 и f 2 (т.е. свободны, соответственно связаны, те и только те вхождения переменных, которые происходят от свободных, соответственно связанных, вхождений переменных в f 1 и f 2). Некоторое вхождение переменной может быть связанным в f 1, например, в то время как другое – свободным в f 2 и т.п.
3. Если f – формула, то (" s)(f) тоже формула. Свободные вхождения переменной s в формуле f теперь становятся связанными квантором (" s) в формуле (" s)(f). Формула (" s)(f) утверждает: какое бы значение (т.е. какой бы кортеж) подходящей арности ни подставляли вместо свободных вхождений s в формуле f, она всегда истинна.
4. Если f – формула, то ($ s)(f)также формула. Свободные вхождения переменной s в формуле f теперь также становятся связанным квантором ($ s) в формуле ($ s)(f). Формула ($ s)(f)утверждает, что существует значение s, при подстановке которого вместо всех свободных вхождений s в формулу f эта формула становится истинной.
Например, формула ($ s)(R (s))означает, что отношение R не пусто, т.е. существует некоторый кортеж s, принадлежащий R.
5. Формулы при необходимости заключаются в скобки. Используется следующий порядок старшинства (в перечисленном порядке): арифметические операторы сравнения; кванторы $ и "; ù, Ù, Ú.
6. Ничто иное не является формулой.
На основании изложенного в качестве примера запишем выражение реляционного исчисления на переменных-кортежах, соответствующее операции проекции Пi1,i2,...,ik(R) в реляционной алгебре. Оно будет иметь вид
{ t (k)/($ u)(R (u) Ù ((t [1] = u[ i 1]) Ù... Ù (t [ k ] = u [ ik ]))}.
Можно сократить число скобок:
{ t (k)/($ u)(R (u) Ù t [1] = u[ i 1] Ù... Ù t [ k ] = u [ ik ])}.
Введем ограничения на конечность реальных отношений в БД, чтобы исключить возможность формирования выражений вида
{ t /ù R (t)},
не имеющих смысла (выражение обозначает все возможные, не принадлежащие R кортежи, арность которых согласуется с t).
С этой целью в реляционном исчислении рассматривают только так называемые «безопасные» выражения { t /Y(t)},для которых выполняется условие, что каждый компонент (элемент столбца) любого t, удовлетворяющего Y(t), является элементом некоторого множества элементов D (Y).
Множество D (Y)определяется как функция фактических отношений, которые указываются в Y(t), констант, присутствующих в формуле Y(t), и элементов кортежей тех отношений, которые указаны в Y(t). Так как все отношения в БД предполагаются конечными, то и множество D (Y)конечно:
D (Y)={ a 1Y} È { a 2Y} È... È { an Y} È П1(R 1) È П2(R 1) È... П k (R 1) È П1(R 2) È... È П k (Rn),
где a 1Y, a 2Y,..., an Y – константы, встретившиеся в формуле Y(t),П1(R 1),П2(R 1),..., П k (Rn) – проекции кортежей фактических отношений R 1, R 2,..., Rn, встретившихся в формуле Y(t) (в данном случае – компоненты кортежей). При таком определении множества D (Y)справедливо следующее:
D (Y1(t) Ú Y2(t)) = D (Y1) È D (Y2);
D (Y1(t) Ù Y2(t)) = D (Y1) È D (Y2);
D (Y1(t) Ù ùY2(t)) = D (Y1) È D (Y2) и т.п.
Например, если задано выражение { t / C Ú R (t)},где R – бинарное отношение, то
D (Y) = { С } È П1(R) È П2(R).
Окончательное определение безопасных выражений следующее. Выражение реляционного исчисления является безопасным, если выполняются следующие условия.
1. Из истинности Y(t) следует, что каждый компонент кортежа t принадлежит D (Y).
2. Для любой подформулы Y вида
($ u)(Y1(u)),
входящей в состав Y, и принадлежит D (Y),если и удовлетворяет Y.
3. Если для любой подформулы Y вида
(" u)(Y1(u)),
входящей в состав Y, каждый компонент и не принадлежит D (Y1) (или, что то же самое, из истинности ùY(u)следует, что и принадлежит D (Y1)),то и удовлетворяет Y1(t). При выполнении этих условий выражение { t /Y(t)}является безопасным.
Отметим, что выражению (" u)(Y1(u)) эквивалентно выражение ù($ u)(ùY1(u)). По условию 3 (" u)(Y1(u)) безопасно, когда безопасно ù($ u)(ùY1(u)).
На основании вышеизложенного можно утверждать, что если формула Y(t) такова, что любая ее подформула вида ($ u)(Y i (t)) или (" u)(Y i (t)) безопасна, то безопасно каждое выражение вида
{ t / R (t) Ù Y(t)}.
Действительно, любой кортеж, удовлетворяющий формуле (R (t) Ù Y(t)) (т.е. при подстановке которого в эту формулу она становится истинной), принадлежит (в соответствии с этой формулой) отношению R. Следовательно, каждый из его компонентов будет принадлежать также и множеству элементов D (R (t) Ù Y(t)) – Тогда по условию 1 (выполнение условий 2 и 3 задано как исходная предпосылка) выражение { t /(R (t) Ù Y(t))}является безопасным.
Заметим, что если в Y(t)найдется хотя бы одна из подформул вида ($u)(Y i (t)) или (" u)(Y j (t)), которая окажется небезопасной, то тогда и выражение { t / R (t) Ù Y(t)} не будет являться безопасным. Если в формуле Y(t) вообще отсутствуют подформулы вида ($u)(Y i (t)) или (" u)(Y j (t)), то выражение { t / R (t) Ù Y(t)} всегда является безопасным.
Например, если Y(t) = ù R 2(t), то получим безопасное выражение
{ t / R 1(t) Ù ù R 2(t)}.
Безопасным является также выражение { t / R (t)},соответствующее отношению R (точнее – переменной R, обозначающей отношение).
В реляционности исчисления на переменных-кортежах доказана теорема, устанавливающая эквивалентность безопасных выражений в исчислении выражениям в реляционной алгебре.
Теорема 1. Если Е – выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение в реляционном исчислении с переменными-кортежами.
Для основных операций реляционной алгебры можно указать следующие соответствующие выражения реляционного исчисления на переменных-кортежах:
1. Операции объединения (R 1 È R 2) соответствует выражение:
{ t / R 1(t) Ú R 2(t)}.
2. Операции разности (R 1 - R 2) соответствует выражение:
{ t / R 1(t) Ù ù R 2(t)}.
Здесь рассматривается все множество кортежей t таких, что t принадлежит R 1 и не принадлежит R 2.
3. Операции декартово произведение (R 1 ´ R 2)соответствует выражение
{ t (k - m )/($ u)($n)(R 1(u) Ù R 2(n) Ù t [1] = u [1] Ù... Ù t [ k ] = u [ k ] Ù t [ k + 1] = n[1] Ù... Ù t [ k + m ] = n[ m ]}.
Здесь рассматривается все множество кортежей t арности (k + т)таких, что существует кортеж и, принадлежащий R 1,и существует кортеж n, принадлежащий R 2,причем k первых компонентов кортежа t образуют компоненты кортежа и, а следующие т компонентов кортежа t образуют компоненты кортежа n.
4. Операции проекции П i 1, i 2,..., ik (R) соответствует выражение
{ t (k)/($ u)(R 1() л /[1] = u[i,] ö... ö t[k] = u[ ik ])}.
5. Операции селекции s F (R)соответствует выражение
{ t / R (t) Ù F' },
где выражение F' есть выражение F, в котором каждый операнд, обозначающий компонент i, заменен на t [ i ].
Примером реального языка, реализующего реляционное исчисление с переменными-кортежами, является язык запросов QUEL.
Реляционное исчисление с переменными на доменах. В реляционном исчислении с переменными на доменах не существует переменных-кортежей. Вместо них вводятся переменные на доменах. В остальном реляционное исчисление с переменными на доменах строится также, как и реляционное исчисление с переменными-кортежами с использованием тех же самых операторов.
Атомами формул могут быть:
1. R(x 1, х 2,..., xk),где R – k -арное отношение; хi – константа или переменная на некотором домене.
Атом R(x 1, х 2,..., xk)указывает на то, что значения тех хi, которые являются переменными, должны быть выбраны так, чтобы (x 1, х 2,..., xk) было кортежем отношения R.
2. x q y, где х и у – константы или переменные на некотором домене; q – арифметический оператор сравнения.
Атом x q y указывает на то, что x и y представляют собой значения, при которых истинно x q y.
Формула в реляционном исчислении с переменными на доменах также использует логические связки Ù, Ú, ù и кванторы (" x) и ($ x), где х –переменная на доменах. Аналогично используются понятия свободных и связанных переменных.
Выражение реляционного исчисления с переменными на доменах имеет вид
{ x 1, x 2,..., xk /Y(x 1, x 2,..., xk)},
где Y – формула; x 1, x 2,..., xk – различные свободные переменные.
Например, выражение
{ x 1, x 2/ R 1(x 1, x 2) Ù (" y)(ù R 2(x 1, y) Ù ù R 2(x 2, y))}
имеет место для бинарных отношений R 1и R 2 и означает множество кортежей в отношении R 1таких, что ни один из их компонентов не является первым компонентом какого-либо кортежа отношения R 2.
Для учета ограничения – конечности реальных отношений – аналогично вводятся и рассматриваются безопасные выражения.
Выражение исчисления с переменными на доменах, эквивалентное заданному выражению исчисления с переменными-кортежами
{ t /Y(t)},
строится следующим образом.
1. Если t является кортежем арности k, то вводится k новых переменных на доменах:
t 1, t 2,..., tk.
2. Атомы R (t)заменяются атомами R (t 1, t 2,..., tk)
3. Каждое свободное вхождение t [ i ]заменяется на ti.
4. Для каждого квантора ($ u) или (" u) вводится т новых переменных на доменах u 1, u 2,..., um, где т – арность и.
В области действия этой квантификации выполняются замены:
R (u) на R (u 1, u 2,..., um);
u [ i ]на ui;
($ u) на ($ u 1)($ u 2)...($ um);
(" u) на (" u 1)(" u 2)...(" um).
5. Выполняется построение выражения
{ t 1, t 2,..., tk /Y'(t 1, t 2,..., tk)},
где Y' представляет собой Y, в которой выполнены соответствующие замены.
Полученное в результате построения выражение реляционного исчисления с переменными на доменах эквивалентно исходному выражению реляционного исчисления с переменными-кортежами.
Например, выражение { t / R(t) v R2(t)} после всех подстановок примет следующий вид:
{ t 1, t 2,..., tk / R 1(t 1, t 2,..., tk) Ú R 2(t 1, t 2,..., tk)}.
В реляционном исчислении с переменными на доменах доказаны следующие две теоремы.
Теорема 2. Для каждого безопасного выражения реляционного исчисления с переменными-кортежами существует эквивалентное безопасное выражение реляционного исчисления с переменными на доменах.
Теорема 3. Для каждого безопасного выражения реляционного исчисления с переменными на доменах существует эквивалентное ему выражение реляционной алгебры.
Примером реального языка запросов (осуществляется реляционное исчисление с переменными на доменах) является язык QBE.
Сравнение алгебраических языков и языков исчисления. Рассмотренные выше три абстрактных языка запросов служат основой реальных языков манипулирования данными реляционных систем. Каждый из этих языков эквивалентен по своей выразительности двум другим. Однако языки исчисления являются непроцедурными языками, так как их средствами можно выразить то, что нужно, и не обязательно говорить о том, как это получить (выражение в исчислении описывает лишь свойства желаемого результата, фактически не указывая, как его получить). Определение наиболее эффективного порядка вычислений для реализации запроса пользователя (т.е. оптимизация запроса) выполняется транслятором (или интерпретатором).
Выражения реляционной алгебры, напротив, специфицируют конкретный порядок выполнения операций, и пользователь обычно сам должен выполнить оптимизацию своего запроса при его формулировке. Однако, например, в соответствии с теоремой 1 транслятор на первом шаге трансляции запроса может выполнить преобразование выражения исчисления в эквивалентное алгебраическое выражение и далее определить эффективный порядок вычислений.
Дополнительные возможности ЯМД в реляционных системах. В общем случае ЯМД выходят за рамки абстрактных языков, так как для обработки данных требуются операции, выходящие за рамки возможностей реляционной алгебры или реляционного исчисления. Это прежде всего следующие команды: включить данные; модифицировать данные; удалить данные.
Кроме этих операций можно использовать следующие дополнительные возможности.
1. Арифметические выражения. Арифметические вычисления и сравнения включают в формулы селекции реляционных алгебраических выражений или в атомы в выражениях реляционного исчисления.
2. Команды присваивания и печати.
3. Агрегатные функции. Это функции, применяемые к столбцам отношений, в результате выполнения которых вычисляется одна-единственная величина. Например, максимальное или минимальное значение, сумма, среднее.
Так как реальные ЯМД реализуют функции, не имеющие аналогов ни в реляционной алгебре, ни в реляционном исчислении, то в действительности они являются более чем полными. Полным считается язык, в котором реализуются все возможности реляционного исчисления с переменными-кортежами либо, что равносильно, реляционного исчисления с переменными на доменах или реляционной алгебры.
Ограничения модели
Отношения в БД обладают всеми свойствами множеств. Основным ограничением является невозможность представления в отношении кортежей-дубликатов, т.е. каждое отношение имеет, по крайней мере, хотя бы один первичный ключ (в крайнем случае, этот ключ состоит из всех атрибутов).
В реляционной МД ключ определяется как неизбыточное подмножество атрибутов схемы отношения, совокупность значений которых однозначно идентифицирует каждый кортеж в отношении.
Отношение может иметь несколько ключей, называемых ВОЗМОЖНЫМИ КЛЮЧАМИ. Один из возможных ключей выбирается в качестве первичного ключа отношения.