С.Д. Кузнецов - Основы баз данных (1121716), страница 13
Текст из файла (страница 13)
Базисные средства манипулирования реляционными данными: реляционная алгебра Кодда В предыдущей лекции упоминались три составляющих реляционной модели данных. Две из них — структурную и целостную части — мы рассмотрели более или менее подробно, а манипуляционной части реляционной модели данных посвящается эта и следующие лве лекции, Мы уделяем данной теме такое большое внимание, поскольку понимание формальных механизмов манипулирования реляционными данными исключительно важно для понимания технологии баз данных вообще.
В этой лекции после небольшого введения будет рассмотрен вариант реляционной алгебры, предложенный Кристофером Дейтом около 15 лет тому назад. Мне этот вариант алгебры кажется наиболее попятным, хотя предлагаемый набор операций несколько избыточен. В следующей лекции мы обсудим новый «минимальный» вариант алгебры, предложенный Дейтом и Дарвеном в конце 1990-х гг. Возможно, новая алгебра не очень практична, но зато красива и элегантна.
После этого в лекции 5 мы перейдем к реляционному исчислению, достаточно подробно рассмотрим один из вариантов реляционного исчисления кортежей и кратко обсудим особенности исчисления доменов. Ключевые слова: механизмы манипулирования реляционными данными, реляционная алгебра, рсляционно полный язык баз данных, реляционная алгебра Ковда, операция объединения отношений, операция пересечения отношений, операция взятия разности отношений, операция взятия расширенного декартова произведения отношений, операция ограничения отношения, операция проекции отношения, операция соединения отношений, операция деления отношений, операция переименования атрибутов, операция присваивания отношений, замкнутость реляционной алгебры, совместимость отношений по объединению, совместимость отношений относительно операции расширенного декартова произведения, эквисосдинсннс, естественное соединение. Введение Как мы отмечали в предыдущей лекции, в манипуляционной составляющей реляционной модели данных определяются два базовых механизма манипулирования реляционными данными — основанная на теории множеств реляционная алгебра и базирующееся на математической логике (точнее, на исчислении прсдикатов первого порядка) реляционное исчисление.
В свою очередь, обычно выделяются два вида реляционного исчисления — исчисление кортежей и исчисление доменов. 54 реляционная алгебра Кодда Лекция 3 Все эти механизмы обладают одним важным свойством: они замкнуты относительно понятия отношения. Это означает, что выражения реляционной алгебры и формулы реляционного исчисления определяются над отношениями реляционных БД и результатом их «вычисления» также являются отношения (конечно, здесь имеются в виду значения-отношения). В результате любое выражение или формула могут интерпретироваться как отношения, что позволяет использовать их в других выражениях или формулах.
Как мы увидим, алгебра и исчисление обладают большой выразительной мощностью: очень сложные запросы к базе данных могут быть выражены с помощью одного выражения реляционной алгебры или одной формулы реляционного исчисления. Именно по этой причине такие механизмы включены в реляционную модель данных.
Конкретный язык манипулирования реляционными БД называется реляционно-полным, если любой запрос, формулируемый с помощью одного выражения реляционной алгебры или одной формулы реляционного исчисления, может быть сформулирован с помощью одного оператора этого языка. Известно (и мы не будем это доказывать), что механизмы реляционной алгебры и реляционного исчисления эквивалентны, т.
е. для любого допустимого выражения реляционной алгебры можно построить эквивалентную (т. е. производящую такой же результат) формулу реляционного исчисления и наоборот. Почему же в реляционной модели данных присутствуют оба эти механизма? Дело в том, что они различаются уровнем процедурности. Выражения реляционной алгебры строятся на основе алгебраических операций (высокого уровня), и подобно тому, как интерпретируются арифметические и логические выражения„выражение реляционной алгебры также имеет процедурную интерпретацию. Другими словами, запрос, представленный на языке реляционной алгебры, может быть вычислен на основе выполнения элементарных алгебраических операций с учетом их приоритетности и возможного наличия скобок. Для формулы реляционного исчисления однозначная вычислительная интерпретация, вообще говоря, отсутствует.
Формула только ставит условия, которым должны удовлетворять кортежи результирующего отношения. Поэтому языки реляционного исчисления являются в большей степени непроцедурными, или декларативными. Поскольку механизмы реляционной алгебры и реляционного исчисления эквивалентны, в конкретной ситуации для проверки степени реляционности некоторого языка БД можно пользоваться любым из этих механизмов. Заметим, что крайне редко алгебра или исчисление принимается в качестве полной основы какого-либо языка БД. Обычно (например, в случае языка БО) ) язык основывается на некоторой смеси алгебраичес- 55 Основы баз данных Курс ких и логических конструкций. Тем не менее знание алгебраических и логических основ языков баз данных часто применяется на практике.
Для зкономии времени и места мы не будем вводить какие-либо строгие синтаксические конструкции, а в основном ограничимся рассмотрением материала на содержательном уровне. Обзор реляционной алгебры Кодда Основная идея реляционной алгебры состоит в том, что коль скоро отношения являются множествами, средства манипулирования отношениями могут базироваться на традиционных теоретико-множественных операциях, дополненных некоторыми специальными операциями, специфичными для реляционных баз данных. Существует много подходов к определению реляционной алгебры, которые различаются наборами операций и способами их интерпретации, но, в принципе, являются более или менее равносильными. В данном разделе мы опишем немного расширенный начальный вариант алгебры, который был предложен Колдом (будем называть ее «алгеброй Колла»).
В этом варианте набор основных алгебраических операций состоит из восьми операций, которые делятся на два класса — теоретико-множественные операции и специальные реляционные операции. В состав теоретико- множественных операций входят операции: ° объединения отношений; ° пересечения отношений; ° взятия разности отношений; в взятия декартова произведения отношений. Специальные реляционные операции включают: ° ограничение отношения; ° проекцию отношения; ° соединение отношений; ° деление отношений. Кроме того, в состав алгебры включается операция присваивания, позволяющая сохранить в базе данных результаты вычисления алгебраических выражений, и операция переименования атрибутов, дающая возможность корректно сформировать заголовок (схему) результирующего отношения.
Общая интерпретация реляционных операций Если не вдаваться в некоторые тонкости, которые мы рассмотрим в следующих разделах, то почти для всех операций предложенного выше набора имеется очевидная и простая интерпретация. 56 Лекция 3 Реляционная алгебра Кодда ° При вгяполнении операции обьединения (1ЛЧ(ОХ) двух отношений с одинаковыми заголовками производится отношение, включающее все кортежи, которые входят хотя бы в одно из отношений-операндов.
° Операция пересечения (1ХТЕКБЕСТ) двух отношений с одинаковыми заголовками производит отношение, включающее все кортежи, которые входят в оба отношения-операнда. ° Отношение, являющееся разностью (М1М()Ь) двух отношений с одинаковыми заголовками, включает все кортежи, входящие в отношение-первый операнд, такие, что ни один из них не входит в отношение, которое является вторым операндом. ° При выполнении декартова произведения (Т!МЕЯ) двух отношений, пересечение заголовков которых пусто, производится отношение, кортежи которого производятся путем объединения кортежей первого и второго операндов.
° Результатом ограничения (СЕНЕКЕ) отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию. ° При выполнении проекции (РКО)ЕСТ) отношения на заданное подмножество множества его атрибутов производится отношение, кортежи которого являются соответствующими подмножествами кортежей отношения-операнда. ° При соединении ()О(Х) двух отношений по некоторому условию образуется результирующее отношение, кортежи которого производятся путем объединения кортежей первого и второго отношений и удовлетворяют этому условию.
° У операции реляционного деления (О1У(ОЕ ВУ) два операнда — бинарное и унарное отношения. Результирующее отношение состоит из унарных кортежей, включающих значения первого атрибута кортежей первого операнда таких, что множество значений второго атрибута (при фиксированном значении первого атрибута) включает множество значений второго операнда. ° Операция переименования (КЕ)к(АМЕ) производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены.
° Операция присваивания (;=) позволяет сохранить результат вычисления реляционного выражения в существующей переменной отношения БД. Поскольку результатом любой реляционной операции (кроме операции присваивания, которая не вырабатывает значения) является некое отношение, можно образовывать реляционные выражения, в которых вместо отношения-операнда некоторой реляционной операции находится вложенное реляционное выражение. В построении реляционного выражения могут участвовать все реляционные операции, кроме операции Основы баз данных Курс присваивания. Вычислительная интерпретация реляционного выражения диктуется установленными приоритетами операций: ЕЕМйМЕ х ХНЕЕЕ =' РЕОЯЕСТ х Т1МЕЯ = д01И = 1МТЕЕЯЕСТ Р1Ч1РЕ ВУ > РМ10И = М1МБЯ В другой форме приоритеты операций показаны на рис.
3.!. Вычисление выражения производится слева направо с учетом приоритетов операций и скобок, Рис. 3.1. Таблица приоритетов операций традиционной реляционной алгебры Замкнутость реляционной алгебры и операция переименования Как мы отмечали в предыдущей лекции, каждое значение-отношение характеризуется заголовком (или схемой) и телом (или множеством кортежей). Поэтому, если нам действительно нужна алгебра, операции которой замкнуты относительно понятия отношения, то каждая операция должна производить отношение в полном смысле, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
