1.6. Реляционная алгебра

пять основных операций - ОБЪЕДИНЕНИЕ, РАЗНОСТЬ, ДЕКАРТОВО ПРОИЗВЕДЕНИЕ, ПРОЕКЦИЯ, ВЫБОР; 2)

дополнительные операции, не расширяющие возможности основных операций, однако обеспечивающие краткость записи, - ПЕРЕСЕЧЕНИЕ, СОЕДИНЕНИЕ, ДЕЛЕНИЕ.

Операндами операций реляционной алгебры являются постоянные и (или) переменные отношения.

Рассмотрим название операции на примерах отношений R и S\ R (А В С) S(D Е F) Р 1 а Р 2 Ь Р 2 Ь Ч 3 а Ч 2 с Основные операции. Операцией ОБЪЕДИНЕНИЕ отношений R и S называется отношение Т = R V S включающее множество кортежей, принадлежащих R или S или им обоим. Все кортежи результативного отношения Т имеют одинаковое число компонентов, поскольку операция применяется к отношениям одной и той же арности.

Пример. Операция ОБЪЕДИНЕНИЕ имеет вид

RVS р 1 а

р 2 Ь

q 2 с

q 3 а

Операцией РАЗНОСТЬ отношений Я и 5, определенных на общем домене, называется отношение Т =R-S, включающее множество кортежей, принадлежащих R, но не принадлежащих S. Отношения R и S имеют одинаковую арность.

Пример. Операция РАЗНОСТЬ имеет вид

R-S р 1 а q 2 с

Операцией ДЕКАРТОВО ПРОИЗВЕДЕНИЕ отношений R и S, которые соответственно имеют арности кх и к2, называется отношение Т =RxS , включающее множество кортежей длиной кх+к2, первые кх компонентов которых образуют кортежи, принадлежащие R, а последние к2 - кортежи, принадлежащие S. Другими словами, производится конкатенация кортежей из отношение R и S.

Пример. Операция ДЕКАРТОВО ПРОИЗВЕДЕНИЕ имеет вид А В С D Е п Р 1 а Р 2 ь Р 1 а Ч 3 а Р 2 Ь Р 2 Ъ Р 2 b Ч 3 а Ч 2 с Р 2 Ъ Ч 2 с Ч 3 а Пусть t ~ кортеж отношения R (X) и А - атрибут X, тогда t [А\ - Л-компонента кортежа t.

Операцией ПРОЕКЦИЯ Я и Г называется отношение R [Г], которое является вертикальным подмножеством столбцов отношения R:

R\Y] = {t{y}\teR}.

Таким образом, R [У] - отношение на Y, включающее все кортежи, получаемые из кортежей R путем отбора компонентов, соответствующих Y, и удаление одинаковых кортежей (кроме одного) из множества, полученного в результате проектирования.

Другое обозначение для операции ПРОЕКЦИЯ % (Л).

Пример. Операция ПРОЕКЦИЯ имеет вид

R\AC\ (А С) IE F)

pa 2 b

p b 3 a

q с

Операция ВЫБОР строит горизонтальное подмножество кортежей отношения R, удовлетворяющих определенному предикату. Пусть © - одна из бинарных операций «<» , «<», «>», «>», «=», «=?», применяемая к атрибуту (атрибутам) А и кортежу t. Тогда R\A © i\ - это набор кортежей отношения Л, каждая А -компонента которых находится в отношении © к кортежу t. Вместо кортежа t можно взять множество кортежей В таких, что А и В определяются на общих домеиах. Тогда R[A © В] - это набор кортежей отношения R, Л-компоненты которых находятся в отношении © к В-компонентам.

Пример. Операция ВЫБОР имеет вид:

R[C*b\ (ABC) R\A*q*B> 1] (ABC) p 1 a p 2 b

q 2 с

Другим обозначением операции ВЫБОР является aA@t (R).

Операцией ПЕРЕСЕЧЕНИЕ отношений R и S называется отношение Т = RI S , которое включает кортежи, принадлежащие как R, так и S. Другими словами, R I S -R-(R-S).

Пример. Операция ПЕРЕСЕЧЕНИЕ имеет вид: Rl S р 2 Ь

Пусть R (X, Г) и S (Y, Z) - отношения, где X, Y, Z - непересекающиеся множества атрибутов и Y - множество атрибутов, общее Для отношений RvlS,

Операцией СОЕДИНЕНИЕ отношений R и S называется отношение Т(Х, Y, Z), определяемое как

T(X,Y,Z) = {(x,y,z)\(x,y)eR H(y,z) eS}.

Таким образом, отношение Т ~ это множество кортежей отношений R и S, имеющих одинаковое значения общих атрибутов для этих отношений.

Можно определить операцию СОЕДИНЕНИЕ более широко с точки зрения типа отношения менаду атрибутами отношений R и S. Пусть даны отношенияR (А, В\) и S(B2, С), где В\ и В2 определены на общем домене; © - о,дна из бинарных операций «<», «<», «>», «>», «=», «*», в которых могут находиться атрибуты В{ и В2.

Пример. Операция СОЕДИНЕНИЕ имеет вид R[A = D] S (А В С D Е F) Р 1 а Р 2 b Р 2 b Р 2 Ь Ч 2 с Ч 3 а R[BT(D,E,F,G) = R(A,B)[B > В^(А,В).

Источником значений для атрибута D в Т является атрибут Л в R. Аналогично для атрибутов Е, F, G и 'Г источниками будут атрибуты BbR,A BS.

Операция СЛИЯНИЕ (естественное соединение) выполняется так же, как и СОЕДИНЕНИЕ, при использовании операции «=» между атрибутами или множествами атрибутов или множествами атрибутов отношений; при этом в результатном отношении удаляются одинаковые столбцы. Применим операцию СЛИЯНИЕ для примера, рассмотренного выше. F) Ь Ъ

а

(А В С Е

р 1 а 2 р 2 b 2 q 2 с 3 Операция слияния может быть также обозначена r№s.

Операция ДЕЛЕНИЕ определяется следующим образом. Пусть даны отношения R (А, В) и Р (С), где атрибуты В я С определены на одном домене. Тогда R [В + С]Р - подмножество R [А] (частное), которое получается в результате деления значений атрибута В в R (делимое) на значение атрибута С в S (делитель), т.е. если отношения R и Р имеют соответственно арность г и р, где г > р; р Ф 0, Тогда R + P - множество кортежей t длиной г - р таких, что для всех кортежей длиной р, принадлежащих Р, кортеж t принадлежит R. Заметим, что декартово произведение R\A\ с Р[С\ принадлежит отношению R.

Пример. Пусть задано отношение Р:

Р(В С) 1

а 2

с

Тогда операция ДЕЛЕНИЕ имеет вид

R + Р(А) Р Ч

Контрольные вопросы и упражнения 1.

Приведите пример нарушения целостности БД. 2.

Представьте в виде реляционной БД четыре массива сетевой БД, приведенной на рис.

а) разработайте структуру записей каждого массива;

б) предложите схемы реализации задач с использованием реляционных операций. 3.

Используя отношения ПРОИЗВОДИТЕЛЬ, ТОВАР, ПОТРЕБИТЕЛЬ и ПОСТАВКА и операции ВЫБРАТЬ, ПРОЕКТИРОВАТЬ и СОЕДИНИТЬ, реализуйте следующие запросы:

а) получить наименование потребителя, наименование производителя, город производителя, который поставляет товар по цене от 12 до 20 тыс. потребителю из г. Москвы;

б) получить наименование производителя, наименование потребителя, наименование товара, количество поставляемого товара по цене меньше чем 15 тыс.

Литература 1.

Дейт К. Введение в системы баз данных. М.: Наука, 1980. 2.

Евдокимов В.В. и др. Экономическая информатика. Учебник для вузов / Под ред. В.В. Евдокимова. Спб.: Питер, 1997. 3.

Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир, 1980, 4.

Мейер Д. Теория реляционных баз данных. М.: Мир, 1987. 5.

Тиори Т., Фрай Д. Проектирование структур баз данных. М.: Мир, 1985. 6.

Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983. 7.

Хаббард Д. Автоматизированное проектирование баз данных. М.: Мир, 1984. 8.

Цикритзис Д., Лоховски Ф. Модели данных. М.: Финансы и статистика, 1985.