Реляционное исчисление

обеспечения

Связь (отношений)
Множество М

Р(х); Р – предикатный символ х ∈ М ⇔ Р(х) = t х – переменная
М θ N Р(х) θ Q(y) х ∈ М θ N ⇔ Р(х) θ Q(y) = t θ = {∪, ∩, , −} θ = {∨, ∧, ¬, →}

Теория множеств

Исчисление предикатов

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

Реляционное исчисление

Пример связи ТМ и ИП:

из базы данных. Например:
ЕЯ - "Выдать факультеты с фондом финансирования

> 10000"
РИ - {t | (FAC(t) & t.fund > 10000}

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

Два варианта реляционного исчисления:
Кортежное реляционное исчисление (TRC) – переменные представляют строки отношений
Доменное реляционное исчисление (DRC) - переменные представляют домены атрибутов отношений

{t | (F(t)}
t - кортежная переменная;
F(t) - формула, в которой

присутствует кортежная переменная t
Ответ: Множество всех таких кортежей t, для которых формула F(t) принимает значение true.

Формула: Рекурсивно определяется через атомарные формулы и построением более сложных формул с помощью логических связок и кванторов.
SQL: Является формальной основной языка SQL.

переменные: t1, t2,... – интерпретируются кортежами отношений.
Срезы кортежных переменных: t.a,…

а - имя атрибута, значение которого входит в состав кортежа.
Предикатные символы: P, P1,...,Q, Q1,… Интерпретируются отношениями
Операторы (предикаты) сравнения : = {=, <, <=, >, >=, <>} и т.д.
Логические связки: ∨ (или), ∧(&) (и), ¬ (не ), → (влечет)
Кванторы: ∃(существует), ∀(для любого)

- предикатный символ, - t - кортежная переменная.

Если Р интерпретируется отношением R, то P(t) означает t ∈ R
t.a θ t.b - t.a и t.b - срезы
t.a θ с - t.a - срез, с - константа

Правильно построенные формулы (ппф):
Атомарные формулы являются ппф;
Если F ппф, то ппф также являются ¬F и (F)
Если F и G ппф, то ппф также являются F ∨ G, F ∧ G, F → G
Если F ппф со свободной переменной t, то ппф также являются ∃tF(t) и ∀tF(t).

∃tF(t) и ∀tF(t). связывает переменную t в формуле F. Переменная,

которая не связана, называется свободной.

Запрос - в общем случае это выражение вида: {(t1,t2,...) | (F(t1,t2,...)}
где - t1,t2,... - кортежные переменные или их срезы;
- F(t1,t2,...) - формула, в которой присутствуют свободные кортежные переменные t1,t2,...

ВНИМАНИЕ: Переменные t1,t2,..., расположенные слева от символа ’|’, должны быть единственными свободными переменными в формуле F. Это значит, что если F содержит другие переменные, то они должны быть связанными с помощью кванторов.

Bld, Fund)
DEP DEPARTMENT (DNo, FNo, Name, Head, Bld, Fund)
TCH TEACHER(TNo,

DNo, Name, Post, Tel, Salary, Comm)
GRP GROUP(GNo, DNo, Course, Num, Quantity, CurNo)
SBJ SUBJECT(SNo, Name)
ROM ROOM (RNo, Num, Building, Seats)
LEC LECTURE (TNo, GNo, SNo, RNo, Type, Day, Week)

Предикатные символы

Отношения БД

Вывести названия факультетов и имена их деканов
2) Селекция и проекция

Запрос. Вывести имена и должности преподавателей, имеющих зарплату > 1000 и надбавку > 500

{(f.Name, f.Dean)|FAC(f)}

3) Соединение, селекция и проекция
Запрос. Вывести имена факультетов и их кафедр, расположенных (факультетов) в корпусе 5

{(t.Name, t.Post) | TCH(t) & t.Salary > 1000 & t.Comm > 500}

{(f.Name,d.Name) | FAC(f) & DEP(d) & f.FNo = d.FNo & f.Bld = 5}

и их кафедр

{(f.Name,d.Name) | DEP(d) & FAC(f) & f.FNo =

d.FNo & f.Bld = 5}

Запрос. Вывести имена кафедр факультетов корпуса 5

{d.Name | DEP(d) & ∃f(FAC(f) & f.FNo = d.FNo & f.Buld = 5)}

Запрос. Вывести имена преподавателей-профессоров, имеющих лекции в группах первого курса

{t.Name | TCH(t) & t.Post='professor' & ∃l(LEC(l) & l.TNo = t.Tno & ∃g(GRP(g) & l.GNo = g.GNo & g.Course = 1))}

Вывести имена профессоров,

для которых существуют такие лекции,

для которых (лекций) существуют группы первого курса

во всех группах
{l.TNo | LEC(l) & ∀g(GRP(g) → g.GNo =

l.GNo)}

Запрос. Вывести номера преподавателей, которые читают лекции во всех группах первого курса

{l.TNo | LEC(l) & ∀g((GRP(g) & g.Course = 1) → g.GNo = l.GNo)}

Запрос. Вывести имена преподавателей, которые читают лекции во всех группах первого курса

{t.Name | TCH(t) & ∃l(LEC(l) & l.TNo = t.TNo & ∀g((GRP(g) & g.Course = 1) → g.GNo = l.GNo)}

Вывести имена преподавателей,

для которых существуют такие лекции,

которые читаются всем группам 1 курса

не имеющие интерпретации в БД. Или, другими словами, имеющие бесконечное

к-во ответов (дающие в результате бесконечные отношения). Примеры:

Запрос называется безопасным, если он интерпретируется конечным отношением.

Для построения безопасных запросов:
все переменные в формуле должны быть ограниченными;
все логические связки должны быть ограниченными;
все кванторы должны быть ограниченными.

{t | t.Post = 'professor'}
{t | ¬TCH(t)}
{(t,d) | TCH(t) ∨ DEP(d)}

который интерпретируется отношением БД, или если она ограничена другой переменной

или константой.

Переменная t ограниченна, если:
она появляется в предикате Р(t), где Р интерпретируется отношением БД;
она появляется в формуле t.a1 = c1 & ... & t.an = cn, где a1,..., an - все атрибуты корежа t, а c1, ..., cn - константы;
она появляется в формуле t = s, где s – ограниченная переменная.

Примеры:

P(t) - переменная t ограничена предикатом P
P(t) & t = x - переменная x ограничена ограниченной переменной t
t.Name=‘john’ & t.Post=‘prof’ & t.Salary = ‘1200’

ограниченные переменные, то:
F ∨ G будет являться формулой с ограниченными

переменными, если F и G имеют одинаковые свободные переменные;
F & G всегда является формулой с ограниченными переменной не зависимо от того, совпадают ли в этих формулах переменные;
F & ¬G является формулой с ограниченной переменной, если в этих формулах совпадают свободные переменные;
F → G никогда не является формулой с ограниченной переменной.

Примеры:
P(t) ∨ Q(t) – формула с ограниченной переменной
P(t) ∨ Q(q) – переменные в результирующей формуле не ограничены
P(t) & Q(q) – формула с ограниченной переменной
¬Q(t) – не является формулой с ограниченной переменной
P(t) & ¬Q(q) – не является формулой с ограниченной переменной
P(t) & ¬Q(t) – формула с ограниченной переменной

x.Fund < 5) – квантор существования ограничен
∀x(P(x)) → Q(x, y))

– квантор общности ограничен

Если F(t) - ограниченная формула а G(t) – произвольная формула, то формула ∃t(F(t)& G(t)) называется формулой с ограниченным квантором существования. Сама формула интерпретируется ограниченным отношением.

Если F(t) - ограниченная формула, а G(t) – произвольная формула, то формула ∀t(F(t) → G(t)) называется формулой с ограниченным квантором общности. Сама формула интерпретируется ограниченным отношением

доменные переменные;
F(x1,x2,...,xn) - формула, в которой единственными свободными переменными являются

x1,x2,...,xn
Ответ. Множество всех таких кортежей , для которых формула F принимает значение true.

Формула. Рекурсивно определяется через атомарные формулы и построением более сложных формул с помощью логических связок и кванторов точно так же, как и в TRC.
QBE. Является формальной основной языка QBE.

их деканов

{(y, z)|∃x∃u∃vFAC(x,y,z,u,v)}

2) Селекция и проекция
Запрос. Вывести названия факультетов корпуса

5 и их деканов

{(y, z) | ∃x∃u∃vFAC(x,y,z,u,v) & u = 5}

3) Соединение, селекция и проекция
Запрос. Вывести имена факультетов корпуса 5 и имена их кафедр

{(y,n)|∃x∃f(∃z∃u∃v(FAC(x,y,z,u,v) & u=5) & ∃d∃h∃b∃uDEP(d,f,n,h,b,u) & x=f)}

FAC (FNo,Name,Dean,Bld,Fund) DEP(DNo,FNo,Name,Head,Bld,Fund)
x y z u v d f n h b u

полноте): Язык реляционной модели является реляционно полным, если он обладает

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

Утверждение: Реляционная алгебра, безопасное кортежное реляционное исчисление и безопасное доменное реляционное исчисление являются эквивалентными.

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

безопасное кортежное реляционное исчисление

безопасное доменное реляционное исчисление

Утверждение: Язык SQL является реляционное полным.

проблему различия между ппф и безопасными формулами
Запросы являются безопасными
Является эквивалентным

реляционное алгебре; значит обладает реляционной полнотой

(строковые) переменные: t1, t2,... – интерпретируются кортежами отношений.
Срезы кортежных переменных:

t.[i],… i – компонента кортежной переменной.
Предикатные символы: P, P1,...,Q, Q1,… Интерпретируются отношениями
Операторы (предикаты) сравнения : = {=, <, <=, >, >=, <>} и т.д.
Логические связки: ∨ (или), ∧(&) (и), ¬ (не ), → (влечет)
Кванторы: ∃(существует), ∀(для любого)

P - предикат, t - кортежная переменная.

Если Р интерпретируется отношением R, то P.t означает t ∈ R
t[i] θ s[j], t[i] = c - термы соединений
Примеры: t1[3] = t2[1]; t4[7] = 15

Формулы, правильно определенные над строковой переменной:
Все входящие в формулу предикатные символы интерпретируются совместимыми по объединению отношениями.
В формулу входят только термы значений с единственной переменной.
Термы значений соединяются связками ∨, &, ¬. Причем, связке ¬ непосредственно предшествует связка &.
Примеры формул, правильно определенных над переменной t.
P1.t ∨ P2.t ∨ (P3.t & P4.t); (P1.t ∨ P2.t) & ¬P3.t.

ограниченных кванторов существования и общности. Здесь формула F указывает ту

область, в пределах которой изменяется переменная, используемая в кванторах.
Будем записывать эти формулы следующим образом:
∃F(G) и ∀F(G)

Пусть F – формула, правильно определенная над строковой переменной t, а G – формула, содержащая t в качестве свободной переменной, но не содержащая термов значений вида P.t. Тогда формулы:
∃t(F & G); ∀t(F → G)
называются правильно определенными на кванторах.

Примеры: ∃t((P.t ∨ Q.t) & ¬S.t) & t[2] = ‘john’ & t[5] = 1000)
∀t((P.t ∨ Q.t) & ¬S.t) → (t[2] = ‘john’ & t[5] = 1000))

определения, если она имеет вид:
W = U1 & U2 &…&

Un & V, n ≥ 1
и обладает следующими свойствами:
Каждая формула Ui является правильно определенной над кортежной переменной ti.
Формула V либо пуста, либо обладает следующими свойствами:
Если в ней содержатся кванторы, то они правильно определены.
Каждая свободная переменная из V является одной из переменных формул U1, U2,…, Un
В V нет термов значений, содержащих свободные переменные.

Примеры: P.r & Q.s & R.t - декартово произведение P.r & (r[3] = b) - селекция P.r & Q.s & (r [2] = s[1]) - соединение

выполнены следующие условия:
W – формула с областью определения.
t1, t2,…,

tk – последовательность кортежных переменных и срезов. Эти переменные должны быть свободными в W.

Произвольное альфа-выражение определяется рекурсивно следующим образом:
Каждое простое альфа-выражение является альфа-выражением.
Пусть t = (t1, t2,…, tk). Если t : W1 и t : W2 – альфа-выражения, то выражения t : W1 ∨ W2, t : W1 & W2 и t : W1 & ¬W2 являются альфа-выражениями.

| ALL]
…
GET ( ) :

range – указание

имени кортежной переменной , которая принимает значения из отношения .
SOME | ALL – указывают, следует ли интерпретировать переменную с квантором существования или общности.
workspace – идентификатор, который именует временное рабочее отношение, содержащее результат выполнения команды Get.
target list – целевой список кортежных переменных и их срезов, указывающих столбцы, которые проецируются в результирующее отношение.
wff – правильно построенная формула кортежного реляционного исчисления

их деканов

CRC: {f[2], f[3] | FAC.f}
ALPHA: RANGE FACULTY f
GET W(f.Name, f.Dean)

Запрос.

Вывести имя декана факультета CSF

CRC: {f[3] | FAC.f & f[2] = ‘CSF’}
ALPHA: RANGE FACULTY f
GET W(f.Dean) : f.Name = ‘CSF’

Запрос. Вывести названия кафедр факультета CSF

CRC: {d[3] | DEP.d & ∃f(FAC.f & f[2] = ‘CSF’ & f[1] = d[2])}
ALPHA: RANGE FACULTY f SOME
RANGE DEPARTMENT d
GET W(d.Name) = f.Name = ‘CSF’ & f.FNo = d.DNo

формулируются в терминах того, ЧТО требуется, а не КАК вычислить

требуемые значения.

(Безопасное) реляционное исчисление и реляционная алгебра имеют одинаковую выразительную силу, и на их основании формулируется тезис о реляционной полноте.
Имеется возможность формулировать правильные, но не эффективные запросы. В связи с этим необходимы оптимизаторы.
Имеются языки непосредственно реализующие реляционное исчисление (ALPHA, QUEL), а также базирующиеся на кортежном исчислении (SQL) и доменном исчислении (QBE).