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

Операторы:

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

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

2. 
   Выборка: Выбор некоторых строк из отношения.
   
3. 
   Проекция: Выбор некоторых столбцов.
   
4. 
   Произведение и соединение: Композиция отношений.
   
5. 
   Переименование отношений и их атрибутов.
   

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

Отношение Sells

Joe's Bud 2.50

Joe's Miller 2.75

Sue's Bud 2.50

Sue's Coors 3.00

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

Joe's Bud 2.50

Joe's Miller 2.75
Проекция.
R₁ = _L(R₂), где L – это список атрибутов отношения R₂.
Пример: _bar,price(Sells):
bar price

Bud 2.50

Bud 2.50

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

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

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

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.name}Bars:

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 = R₁ R₂

Выполняется -соединение отношений R₁ и R₂ с условием равенства атрибутов с одинаковыми именами. В результат будет включен один столбец для каждой пары одинаковых атрибутов.
Пример: Предположим, что имя атрибута 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.

Переименование.
_{S(A1, . . . , An )} (R) создаст отношение идентичное отношению R, но с именем S и с атрибутами, порядок и имена которых определены A₁,..., A_n.
Пример: Отношение Bars
name addr

Joe's Maple St.

Sue's River Rd.

_R(bar,addr) (Bars) =

name addr

Joe's Maple St.

Sue's River Rd.

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

1. 
   Аргументы +
   
2. 
   Способы построения выражений.
   

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

1. 
   Аргументы = переменные, обозначающие отношения + кнечные (константные) отношения.
   
2. 
   Выражения, построенные с использованием каких-либо операторов и круглых скобок.
   

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

1. 
   Унарные операторы ,  и  имеют самый высокий приоритет.
   

2. 
   Затем следуют “мультипликативные” операторы , _С и х.
   
3. 
   Самый низкий приоритет имеют «аддитивные» операторы ,  и -.
   

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

Пример:

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

R  ( (S) T).
Каждое выражение требует схемы отношения.

• 
  Если в выражении присутствуют операторы ,  и -, то структура всех отношений должна быть одинаковой, поэтому используется любая из структур.
  
• 
  Проекция: используется список атрибутов этой операции.
  
• 
  Выборка: структура не изменяется.
  
• 
  Произведение R х S: используются атрибуты R и S.
  

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

• 
  -соединение: так же как и произведение.
  
• 
  Естественное соединение: используются атрибуты каждого отношения, общие атрибуты присутствуют только один раз.
  
• 
  Переименование: используется все, о чем сказано в операции.
  

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

Bars (name, addr) 

_R(name)

_name _bar

_{addr=Maple Str.} _{beer=bud AND price<3}

Bars Sells

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

 _{beer <> beer1}

_{S(bar, beer1, price)}

Sells Sells

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

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

Пример:

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

Sells (bar, beer, price)

Bars (name, addr)

R1(name) := _name(_{addr=Maple Str.} (Bars))

R2(name) := _bar(_{beer=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. Оператор устранения дублирования .

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

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

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

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

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

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

Например:

R = A B  (R) = A B

1 2 1 2

3 4 3 4

1 2

Сортировка.

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

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

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

Например:

R = A B

1 3

3 4

5. 
   2
   

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

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

R = A B _A+B,A,A(R) = A + B A1 A2

1 2 3 1 1

3 4 7 3 3

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

• 
  Это не реляционные операторы; как правило, эти операторы позволяют определить каким-либо способом итоговое значение столбца.
  
• 
  Пять стандартных операторов: SUM, AVERAGE, COUNT, MIN и MAX.
  

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

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

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

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

1. 
   Группировки R согласно всем атрибутам (одинаковым множествам значений) из списка L.
   
2. 
   Внутри каждой группы, вычисляет  (A), для каждого элемента (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

Выполнить _{beer, 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 ) может быть использовано для отметки «висящих» кортежей в результате.
  
• 
  Оператор внешнего соединения также используется для этой цели.
  
• 
  Варианты оператора внешнего соединения:  - внешнее соединение, левое внешнее соединение, правое внешнее соединение (левое внешнее соединение позволит включить все «висящие» кортежи из левого отношения, правое внешнее соединение – из правого).
  

Пример.
R = A B S = B C R S = A B C

1 2 4 5 3 4 5

3 4 6 7 1 2 

 6 7

жүктеу/скачать 75.5 Kb.

Достарыңызбен бөлісу: