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

обеспечения

и оптимизация выражений реляционной алгебры

получить)
Формальные языки:
реляционная алгебра
реляционное исчисление (кортежное, доменное)
Язык запросов – это язык,

Формальные языки используются для создания языков запросов баз данных (Alpha, QUEL, QBE, SQL)

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

Свойства бинарных операций:
Операция ϕ является коммутативной, если А ϕ В = B ϕ A
Операция ϕ является ассоциативной, если (А ϕ В) ϕ С = А ϕ (В ϕ С)
Операция ϕ является дистрибутивной по отношению к операции θ, если А ϕ (В θ С ) = (А ϕ В) θ (А ϕ С)

операции
Присвоение
Переименование
Обобщенная проекция
Внешнее соединение
…

и S имеют одинаковую степень (арность), то есть одинаковое количество

Теоретико-множественные операции требуют совместимости их операндов

R(A) и S(A), где А – множество атрибутов, называется такое

Операция коммутативна, ассоциативна и дистрибутивна по отношению к пересечению.

Пример:

R(A) и S(A), где А – множество атрибутов, называется такое

Операция не коммутативна, не ассоциативна и не дистрибутивна по отношению к другим операциям.

Т(А) = R(А) ⎯ S(А) = {t | t ∈ R & t ∉ S}

Пример:

Примечание: В РА на используется теоретико-множественная операция дополнения!!!

и S(A), где А – множество атрибутов, называется такое отношение

Операция коммутативна, ассоциативна и дистрибутивна по отношению к объединению.

Т(А) = R(А) ∩ S(А) = {t | t ∈ R & t ∈ S}

Пример:

Пересечение выражается через разность: R ∩ S = R – (R – S)

множество атрибутов, по множеству атрибутов В, где В ⊂ А,

S(B) = R[B] = {t[B] ⏐ t ∈ R}

Проекция обозначается так: R[B] или πВ(R)

Пример:

Примечание: Дубликаты строк удаляются

операторов сравнения: =, ≠, < ≤, >, ≥. Атрибуты А

Наборы атрибутов М = (A1,…, Ak) и N = (B1,…,Bn) называются θ-сравнимыми, если k = n и пары атрибутов (Ai, Bi) являются θ‑сравнимыи. В этом случае M θ N подразумевает следующее:
M θ N = (A1 θ B1) & … & (Ak θ Вk)

Если t – кортеж отношения, содержащего множества θ‑сравнимых атрибутов M и N, то запись запись t[M] θ t[N] подразумевает: (t[A1] θ t[B1]) & … & (t[Ak] θ t[Вk]).

отношения R. Тогда селекцией отношения R по условию М θ N, обозначаемой

Т(А) = R[M θ N] = {t | t ∈ R & t[M] θ t[N]}

Пример:

Операция также имеет следующую нотацию: σM θ N(R)

Один из наборов атрибутов M или N может быть константой.

R(А) и S(B) (A и B – множества атрибутов), обозначаемым

Операция коммутативна, ассоциативна и дистрибутивна по отношению к объединению и пересечению.

Т(А,В) = R(А) x S(B) = {(t1,t2) | t1 ∈ R & t2 ∈ S}

Пример:

Соединением отношения R со схемой R(A,M) с отношением S со

T = R[М θ N]S = {(t1, t2) ⏐ t1 ∈ R ∧ t2 ∈ S ∧ t1[М] θ t2[N]}

Пример:

Операция коммутативна и ассоциативна

Операция также обозначается: R M θ NS
Соединение выражается через произведение и селекцию: R M θ NS = σM θ N(R x S)

атрибутов.

Естественное соединение – соединение по условию равенства совпадающих по

Пример:

R S R[B,C=B,C]S R*S

t2 ∈ S ∧ t1[М] θ t2[N]}
Пример:
R

R[М θ N)S = (R[М θ N]S)[A] – где А – набор атрибутов отношения R

Полусоединение выражается через соединение и проекцию:

R[M], изображаемым как It1(R), называется такое множество кортежей t2 ∈

It1 ∈ R[M](R) = {(t2) ⏐ t2 ∈ R[N] ∧ (t1,t2) ∈ R}

Примеры:

R Ia1∈ R[A](R) Ia2∈ R[A](R) I(a1,b1)∈ R[A,B](R) Ic2∈ R[C](R)

атрибутов N и K, которые являются совместимыми (обозначается R[N÷K)]S), называется

T(M) = R[N÷K]S = {t ⏐t ∈ R[M] & It(R) ⊇ S[K]}

Позволяет формулировать запросы типа следующего: - Вывести преподавателей, читающих ВСЕ типы лекций.

S

Операция деления выражается через другие операции РА:
R[N÷K]S = R[M] – ((R(M) x S[K]) – R)[M]
Операция деления не коммутативна и не ассоциативна

Bld, Fund)
TCH (TNo, DNo, Name, Post, Tel, Salary, Comm)
GRP (GNo,

Пример БД для запросов РА

их должностями:
TCH[Name, Post] πName,Post(TCH)
Селекция: Вывести сведения о факультете CSF:
FAC[Name = ‘CSF’]

Вывести названия факультетов и названия их кафедр
(FAC[FNo = FNo]DEP) [FAC.Name,

=‘prof’ – условие отбора Name - вывести
Name - вывести
Вывести имена преподавателей-профессоров

((((((FAC[FNo=Fno]DEP) [DNo=DNo]TCH) [TNo=TNo]LEC) [SNo=SNo]SBJ) [FAC.Name=‘CSF’]) [Post=‘prof’]) [TCH.Name, SBJ.Name]

преподавателей, преподающих во всех группах первого курса:
((LEC[TNo,GNo])[GNo÷GNo](GRP[Course=1]))[TNo]
3) Вывести номера преподавателей, преподающих

LEC(GNo,TNo,...)

GRP(GNo, Course...)

TCH(TNo, Name...)

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

в результате вычисления выражений реляционной алгебры. Операция именования имеет следующий

Пример: Вывести названия факультетов и названия их кафедр. Полученное отношение имеет имя FAC_DEP с именами атрибутов FName и DName соответственно:
ρFAC_DEP(FName,DName)(FAC[FNo=FNo]DEP)[FAC.Name,DEP.Name]

функций в список проецируемых столбцов. R[F1, F2,...,Fn] πF1, F2,...,Fn(R)
Где: R –отношение или выражение

теряется информация определенного вида.

При внешнем соединении производится обычное соединение и

F-1 CSF Ann F-2 CTF Dick F-3 CEF Bob F-4 CYB John

1) Обычное соединение (внутреннее соединение)
FAC [Fno=Fno] DEP
FAC DEP

FNo Name Dean DNo Name Head FNo

F-1 CSF Ann D-1 SE Kate F-1 F-1 CSF Ann D-2 DBMS Lucy F-1 F-2 CTF Dick D-3 CAD Dave F-2

FAC

DEP

F-2 CTF Dick F-3 CEF Bob F-4 CYB John

2) Внешнее соединение слева FAC 〈Fno=Fno] DEP
FAC DEP

FNo Name Dean DNo Name Head FNo

F-1 CSF Ann D-1 SE Kate F-1 F-1 CSF Ann D-2 DBMS Lucy F-1 F-2 CTF Dick D-3 CAD Dave F-2 F-3 CEF Bob null null null null F-4 CYB John null null null null

FAC

DEP

F-2 CTF Dick F-3 CEF Bob F-4 CYB John

3) Внешнее соединение справа FAC [Fno=Fno〉 DEP
FAC DEP

FNo Name Dean DNo Name Head FNo

F-1 CSF Ann D-1 SE Kate F-1 F-1 CSF Ann D-2 DBMS Lucy F-1 F-2 CTF Dick D-3 CAD Dave F-2 null null null D-4 PL Stiv null null null null D-5 CAM Sam null

FAC

DEP

DEP




FNo Name Dean DNo Name

FAC

DEP

Внутреннее соединение

Внешнее соединение слева

Внешнее соединение справа

если G ⊇ F
3) Дистрибутивность селекции и произведения
σF(R х S)

S(C,D) RA,B) S(C,D)

× × ×

σD=9

σB=C & D=9 σB=C σB=C B=C

σD=9

πA

πA

πA

πA

πA(σB=C & D=9(R(A, B)x S(C,D)))

предоставляются в виде последовательности селекций σF1(... σFn(E))
Каждая из селекций

язык, описывает как находить данные
Практически не используется в БД в