Лекция №4
Тема: «Реляционная алгебра и реляционное исчисление»
Реляционная алгебра
Реляционная алгебра — это теоретический язык операций, позволяющих создавать на основе одного или нескольких отношений другое отношение без изменения самих исходных отношений. Таким образом, оба операнда и результат являются отношениями, поэтому результаты одной операции могут применяться в другой операции. Это позволяет создавать вложенные выражения реляционной алгебры (по аналогии с тем, как создаются вложенные арифметические выражения), но при любой глубине вложенности результатом является отношение. Такое свойство называется замкнутостью. Оно подчеркивает то, что применение любого количества операций реляционной алгебры к отношениям не приводит к созданию иных объектов, кроме отношений, точно так же, как результатами арифметических операций с числами являются только числа.
Реляционная алгебра является языком последовательного использования отношений, в котором все кортежи, возможно, даже взятые из разных отношений, обрабатываются одной командой,, без организации циклов. Для команд реляционной алгебры предложено несколько вариантов синтаксиса. Ниже мы воспользуемся общепринятыми символическими обозначениями для этих команд и представим их в неформальном виде.
Существует несколько вариантов выбора операций, которые включаются в реляционную алгебру. Первоначально Кодд [67] предложил восемь операций, но впоследствии к ним были добавлены и некоторые другие. Пять основных операций реляционной алгебры, а именно выборка (selection), проекция (projection), декартово произведение (cartesian product), объединение (union) и разность множеств (set difference), выполняют большинство действий по извлечению данных, которые могут представлять для нас интерес. На основании пяти основных операций можно также вынести дополнительные операции, такие как операции соединения (join), пересечения (intersection) и деления (division), которые могут быть выражены в терминах пяти основных операций.
Операции выборки и проекции являются унарными, поскольку они работают с одним отношением. Другие операции работают с парами отношений, и поэтому их называют бинарными операциями. В приведенных ниже определениях R иS — это два отношения, определенные на атрибутах А= {а1( аг , . . ., а„) и В= (bj, Ь2, . . ., Ьм) соответственно.
Унарные операции
Начнем описание операций реляционной алгебры с изучения двух унарных операций: выборки и проекции.
Выборка (или ограничение)
σ предикат (R)- - Операция выборки применяется к одному отношению R и определяет результирующее отношение, которое содержит только те кортежи (строки) из отношения R, которые удовлетворяют заданному условию (предикату).
Операции с множествами
Операции выборки и проекции предусматривают извлечение информации только из одного отношения. Тем не менее на практике часто возникает необходимость получить данные с помощью нескольких отношений. Ниже в этом разделе рассматриваются бинарные операции реляционной алгебры, начиная с операций объединения, вычисления разности, пересечения и декартова произведения.
Объединение
Объединение двух отношений и'й'в определяет новое отношение, которое включает все кортежи, содержащиеся только в R, только в S, одновременно в R и S причем все дубликаты кортежей исключены. При этом отношения R и s должны быть совместимыми по объединению.
Если R и S включают, соответственно, / и J кортежей, то объединение этих отношений можно получить, собрав все кортежи в одно отношение, которое может содержать не более (/ + J) кортежей. Объединение возможно, только если схемы двух отношений совпадают, т.е. состоят из одинакового количества атрибутов, причем каждая пара соответствующих атрибутов имеет одинаковый домен. Иначе говоря, отношения должны быть совместимыми по объединению. Отметим, что в определении совместимости по объединению не указано, что атрибуты должны иметь одинаковые имена. В некоторых случаях для получения двух совместимых по объединению отношений может быть использована операция проекции.
Пример 4.1. Операция выборки
Составьте список всех сотрудников с зарплатой, превышающей 10000 фунтов стерлингов.
Здесь исходным отношением является отношение staff, а предикатом — выражение salary>!0000. Операция выборки определяет новое отношение, содержащее только те кортежи отношения staff, в которых значение атрибута
salary превышает 10000 фунтов стерлингов. Результат выполнения этой операции показан в табл. 4.1. Более сложные предикаты могут быть созданы с помощью логических операций л (AND), v (OR) и - (NOT). кортежей с атрибутом salary > 10000
Пример 4.2, Операция проекции
Создайте ведомость зарплаты всех сотрудников компании с указанием только атрибутов
staffNo, fName, INametf salary.
n.t af £Ha,fName,IName,salary (Staff)
В этом примере операция проекции определяет новое отношение, которое будет содержать только атрибуты staffNo, fName, IName и salary отношения Staff,
Пример 4.3. Операция объединения
Создайте список всех городов, в которых имеется отделение компании или объект недвижимости.
ncitiP (Branch) U Пcity (PropertyForRent}
Для создания совместимых по объединению отношений сначала следует применить операцию проекции, чтобы выделить из отношений Branch и
PropertyForRent столбцы с атрибутами city, исключая в случае необходимости дубликаты. Затем для комбинирования полученных промежуточных отношений следует использовать операцию объединения.
Пример 4.4. Операция разности
Создайте список всех городов, в которых есть отделение компании, но нет объектов недвижимости, сдаваемых в аренду.
' '
ncity(Branch) - Пс1су( PropertyForRent)
В данном случае аналогично предыдущему примеру следует создать совместимые по объединению отношения Branch и PropertyForRent, выполнив их проекцию по атрибуту city. Затем для комбинирования полученных новых отношений следует использовать операцию разности.
Пересечение
R **S. Операция пересечения определяет отношение, которое содержит кортежи, присутствующие как в отношении R, так и в отношении s. Отношения R и s должны быть совместимыми по объединению.
Пример 4.5. Операция пересечения
Создайте список всех городов, в которых есть отделение компании, а также по меньшей мере один объект недвижимости, сдаваемый в аренду. nciEy(Branch) n ncity(PropertyForRent)
Декартово произведение
• RxS. Операция декартова произведения определяет новое отношение, которое является результатом конкатенации (т.е. сцепления) каждого кортежа из отношения R с Каждым кортежем из отношения s
Пример 4.6. Операция декартова произведения
Создайте список всех арендаторов, которые осматривали объекты недвижимости, с указанием сделанных ими комментариев.
Имена арендаторов хранятся в отношении Client, а сведения о выполненных ими осмотрах — в отношении Viewing. Чтобы получить список арендаторов и комментарии об осмотренной ими недвижимости, необходимо объединить эти два отношения: (nciientNo,fName,lName (Client) ) X (nclienCNO,propertyNo, comment (Viewing) ) Результаты выполнения этой операции показаны в табл. 4.6. В таком виде это отношение содержит больше информации, чем необходимо. Например, первый кортеж этого отношения содержит разные значения атрибута clientNo. Для получения искомого списка необходимо для этого отношения произвести операцию выборки с извлечением тех кортежей, для которых выполняется равенство Client .clientNo=Vlewing.clientNo. Полностью эта операция выглядит так, как показано ниже.
Операции соединения
Как правило, пользователей интересует лишь некоторая часть всех комбинаций кортежей декартова произведения, которая удовлетворяет заданному условию. Поэтому вместо декартова произведения обычно используется одна из самых важныхопераций реляционной алгебры — операция соединения. В результате ее выполнения на базе двух исходных отношений создается некоторое новое отношение. Операция соединения является производной от операции декартова произведения, так как она эквивалентна операции выборки из декартова произведения двух операндов-отношений тех кортежей, которые удовлетворяют условию, указанному в предикате соединения в качестве формулы выборки. С точки зрения эффективной реализации в реляционных СУБД эта операция является одной из самых сложных и часто оказывается одной из основных причин, вызывающих проблемы с производительностью, свойственные всем реляционным системам. Стратегии реализации операции соединения рассматриваются в разделе 20.4.3.
Ниже перечислены различные типы операций соединения, которые несколько отличаются друг от друга и могут быть в той или иной степени полезны.
• Тета-соединение (theta join).
• Соединение по эквивалентности (equijoin), которое является частным видом тета-соединения.
• Естественное соединение (natural join).
• Внешнее соединение (outer join).
• Полусоединение (semijoin).