Лекция Базисные средства манипулирования реляционными данными: реляционная алгебра Кодда

Введение

1. Обзор реляционной алгебры Кодда

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

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

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

4.1. Операции объединения, пересечения, взятия разности. Совместимость по объединению

4.2. Операция расширенного декартова произведения и совместимость отношений относительно этой операции

5. Специальные реляционные операции

5.1. Операция ограничения

5.2. Операция взятия проекции

5.3. Операция соединения отношений

5.4. Операция деления отношений

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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