Базовая («классическая») алгебра отношений (реляционная алгебра)

Базовая («классическая») алгебра отношений (реляционная алгебра).

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

Операторы:

1.  Объединение, пересечение и разность: Обычный набор операторов над множествами.

§  Схемы отношений должен быть одинаковыми.

2.  Выборка: Выбор некоторых строк из отношения.

3.  Проекция: Выбор некоторых столбцов.

4.  Произведение и соединение: Композиция отношений.

5.  Переименование отношений и их атрибутов.

Выборка.

R1 = sC(R2),

где C – это условие включающее атрибуты R2.

Пример:

Отношение Sells

bar beer price

 

Joe's Bud 2.50

Joe's Miller 2.75

Sue's Bud 2.50

Sue's Coors 3.00

Имеется в продаже у Joe JoeMenu = sbar=Joe’s(Sells):

bar beer price

 

Joe's Bud 2.50

Joe's Miller 2.75

Проекция.

R1 = pL(R2), где L – это список атрибутов отношения R2.

Пример: pbar, price(Sells):

bar price

 

Bud 2.50

Miller 2.75

Bud 2.50

Coors 3.00

§  Замечание: в результат включаются и одинаковые кортежи (строки).

Произведение.

R = R1 х R2. Каждый кортеж t1 отношения R1 соединяется с каждым кортежем t2 отношения R2 и кортеж t1 t2 добавляется в отношение R.

q-соединение.

R = R1 C R2. Эта операция эквивалентна R = sC (R1х R2).

Пример:

Sells =

bar beer price

 

Joe's Bud 2.50

Joe's Miller 2.75

Sue's Bud 2.50

Sue's Coors 3.00

Bars =

name addr

 

Joe's Maple St.

Sue's River Rd.

 

BarInfo = Sells Sells. bar=Bars. nameBars:

bar beer price name addr

 

Joe's Bud 2.50 Joe's Maple St.

Joe's Miller 2.75 Joe's Maple St.

Sue's Bud 2.50 Sue's River Rd.

Sue's Coors 3.00 Sue's River Rd.

Естественное соединение.

R = R1 R2

Выполняется q-соединение отношений R1 и R2 с условием равенства атрибутов с одинаковыми именами. В результат будет включен один столбец для каждой пары одинаковых атрибутов.

Пример: Предположим, что имя атрибута name отношения Bars изменили на bar, т. е. теперь имена атрибутов, определяющих название бара в отношениях Bars и Sells совпадают.

BarInfo = Sells Bars:

bar beer price addr

 

Joe's Bud 2.50 Maple St.

Joe's Miller 2.75 Maple St.

Sue's Bud 2.50 River Rd.

Sue's Coors 3.00 River Rd.

Переименование.

rS(A1, . . . , An ) (R) создаст отношение идентичное отношению R, но с именем S и с атрибутами, порядок и имена которых определены A1,..., An.

Пример: Отношение Bars

name addr

 

Joe's Maple St.

Sue's River Rd.

rR(bar, addr) (Bars) =

name addr

 

Joe's Maple St.

Sue's River Rd.

§  Имя последнего отношения R.

Комбинирование операций.

Алгебра =

1.  Аргументы +

2.  Способы построения выражений.

Алгебра отношений (реляционная алгебра):

1.  Аргументы = переменные, обозначающие отношения + кнечные (константные) отношения.

2.  Выражения, построенные с использованием каких-либо операторов и круглых скобок.

§  Запрос = выражение алгебры отношений (реляционной алгебры).

Приоритеты операторов.

Обычный способ группировки операторов:

1.  Унарные операторы s, p и r имеют самый высокий приоритет.

2.  Затем следуют “мультипликативные” операторы, С и х.

3.  Самый низкий приоритет имеют «аддитивные» операторы È, Ç и -.

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

Пример:

R È s S T

Операторы будут сгруппированы:

R È (s (S) T).

Каждое выражение требует схемы отношения.

§  Если в выражении присутствуют операторы È, Ç и -, то структура всех отношений должна быть одинаковой, поэтому используется любая из структур.

§  Проекция: используется список атрибутов этой операции.

§  Выборка: структура не изменяется.

§  Произведение R х S: используются атрибуты R и S.

Но если атрибут A есть и в R и в S и он участвует в операции, то перед именем атрибута ставится имя отношения с точкой, например R. A, S. A.

§  q-соединение: так же как и произведение.

§  Естественное соединение: используются атрибуты каждого отношения, общие атрибуты присутствуют только один раз.

§  Переименование: используется все, о чем сказано в операции.

Пример 1. Найти бар, который расположен на Maple Str. или в котором имеется в продаже пиво Bud по цене меньше $3.

Sells (bar, beer, price)

Bars (name, addr) È

rR(name)

pname pbar

 

saddr=Maple Str. sbeer=bud AND price<3

 

Bars Sells

Пример 2. Найти бары, где есть разные сорта пива по одинаковой цене. Sells (bar, beer, price)

pbar

 

s beer <> beer1

 

 

rS(bar, beer1, price)

 

Sells Sells

Запись выражений «в строку».

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

§  Переименование атрибутов в схеме нового отношения может быть неявным.

Пример:

Найти бар, который расположен на Maple Str. или в котором имеется в продаже пиво Bud по цене меньше $3.

Sells (bar, beer, price)

Bars (name, addr)

R1(name) := pname(saddr=Maple Str. (Bars))

R2(name) := pbar(sbeer=Bud AND price<$3 (Sells))

Ответ(name) := R1 È R2

Семантика для наборов.

Отношение (в SQL, по крайней мере) - действительно набор или множество с повторениями.

§  Может содержать одинаковые (равные) кортежи более одного раза, хотя нет никакого определенного порядка (в отличие от списка).

§  Например: {1; 2; 1; 3} – набор, а не множество.

§  Выболрка, проекция и соединения для наборов выполняются также как для множеств.

§  Работают на основе кортеж-с-кортежем и не устраняют дублированные кортежи.

Объединение наборов.

Суммируется количество вхождений элемента в обоих наборах.

Пример: {1; 2; 1} È {1; 2; 3} = {1; 1; 1; 2; 2; 3}.

Пересечение наборов.

Выбирается минимум количества вхождений в каждый набор.

Пример: {1; 2; 1} Ç {1; 2; 3; 3} = {1; 2}.

Разность наборов.

Результат - разность количества вхождений в набор.

Пример: {1; 2; 1} – {1; 2; 3; 3 } = {1}.

Законы для множеств и наборов отличаются.

§  Некоторые знакомые законы поддерживаются для наборов.

¨  Например: операторы объединения и пересечения - коммутативны и ассоциативны.

§  Но другие законы, которые поддерживаются для множеств, не поддерживаются для наборов.

Пример:

R Ç (S È T) º (R Ç S) È (R Ç T) поддерживается для множеств.

§  Пусть R, S, и T – наборы из одного элемента {1}.

§  Левая сторона: S È T = {1; 1}; R Ç (S È T) = {1}.

§  Правая сторона: R Ç S = R Ç T = {1};

( R Ç S) È (R Ç T) = {1} È {1} = {1; 1} ¹ {1}.

Расширенная (“неклассическая”) реляционная алгебра.

Добавляется несколько операторов, необходимых для SQL, операций над наборами.

1. Оператор устранения дублирования d.

2. Расширенная проекция.

3. Оператор сортировки t.

4. Оператор группировки-агрегирования g.

5. Оператор внешнего соединения.

Устранение дублирования.

d(R) = отношению, где присутствует только один кортеж из нескольких одинаковых, имеющихся в отношении R.

Например:

R = A B d (R) = A B

 

1 2

Сортировка.

tL(R) = список кортежей R, отсортированных по значениям атрибутов из списка L.

§  Замечание: тип результата отличается от обычного типа (набор или множество) реляционной алгебры.

¨  Следствие: другие реляционные операторы не могут следовать t.

Например:

R = A B

1 3

3 4

5  2

tB(R) = [(5; 2), (1; 3), (3; 4)].

Расширенная проекция.

В качестве столбца в проекции допускается функция, имеющая в качестве аргумента один или несколько столбцов отношения R.

Например:

R = A B pA+B, A,A(R) = A + B A1 A2

 

Операторы агрегирования.

§  Это не реляционные операторы; как правило, эти операторы позволяют определить каким-либо способом итоговое значение столбца.

§  Пять стандартных операторов: SUM, AVERAGE, COUNT, MIN и MAX.

Оператор группировки.

gL (R), где L - список элементов, каждый из которых

a) Единичный ( группирующий) атрибут или

b) Форма q(A), где q - оператор агрегирования, а А - атрибут, к которому этот оператор применяется.

Оператор выполняется путем:

1.  Группировки R согласно всем атрибутам (одинаковым множествам значений) из списка L.

2.  Внутри каждой группы, вычисляет q (A), для каждого элемента q(A) из списка L.

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

Пример. Пусть R =

Bar beer price

 

Joe's Bud 2.00

Joe's Miller 2.75

Sue's Bud 2.50

Sue's Coors 3.00

Mel's Miller 3.25

Выполнить gbeer, AVG(price) (R).

1. Определяются группы, согласно атрибутам группировки, в нашем примере, это сорт пива:

Bar beer price

 

Joe's Bud 2.00

Sue's Bud 2.50

Joe's Miller 2.75

Mel's Miller 3.25

Sue's Coors 3.00

­

2. Вычисляется средняя цена внутри группы:

beer AVG(price)

 

Bud 2.25

Miller 3.00

Coors 3.00

Внешнее соединение.

Естественное соединение может привести к потере информации, т. к. кортеж, который не может быть соединен с каким-либо другим кортежем, «повисает», т. е. не включается в результат.

§  Пустое значение (NULL ^) может быть использовано для отметки «висящих» кортежей в результате.

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

§  Варианты оператора внешнего соединения: q - внешнее соединение, левое внешнее соединение, правое внешнее соединение (левое внешнее соединение позволит включить все «висящие» кортежи из левого отношения, правое внешнее соединение – из правого).

Пример.

R = A B S = B C R S = A B C

 

^

^ 6 7