3.8.1. Реляционное исчисление кортежей

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

Используемые обозначения :

Сотрудник(S) – областью значений переменной S служит отношение “Сотрудник”

{S | F(S)} – множество всех кортежей S, для которых F(S) является истинным. Здесь предикат F называется формулой.

Любое выражение имеет общую форму:

{S₁.a₁, S₂.a₂, …, S_n.a_n | F(S₁, S₂,…,S_m)}; m ≥ n

здесь S₁, S₂,…,S_n,…,S_m – переменные кортежа, a_i – атрибуты, F – формула.

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

Правильно построенная формула F имеет вид

Элементарное выражение в формуле может иметь одну из следующих форм:

• R(Si), где R – отношение, Si – переменная кортежа

• Si.a₁ ¤ Sj.a₂, где Si,, Sj-переменные кортежа; a₁,a₂-атрибуты отношения переменных Si и Sj соответственно; ¤ - одна из операций сравнения: <, ≤, >, ≥, =, ≠

• Si.a₁ ¤ C, где Si – переменная кортежа; a₁ – атрибут отношения переменной S_i; С – константа из области определения атрибута a_i; ¤ - одна из операций сравнения

Формулы рекурсивно строятся из элементарных выражений по следующим правилам:

• любое элементарное выражение – формула

• если выражения F₁ и F₂ являются формулами, то выражения, полученные в результате их конъюнкции (F₁ F₂), дизъюнкции (F₁ F₂), отрицания (ØF₁) – формулы

• если выражение F является формулой, со свободной переменной X, то выражения ( X)(F) и ( X)(F) - формулы

В отношении логических операций с кванторами могут применяться следующие правила эквивалентности:

( X) (F(X))   ( X) ((F(X)))

( X) (F(X))   ( X) ((F(X)))

( X) (F₁(X)  F₂(X))   ( X) ((F₁(X)) (F₂(X)))

( X)(F₁(X)  F₂(X))   ( X) ((F₁(X)) (F₂(X)))

Примеры формул реляционного исчисления кортежей.

{S | Сотрудники(S) (S.Зарплата > 10000)} – выбрать все атрибуты отношения «Сотрудники» для сотрудников, получающих зарплату больше 10000 руб.

{S.Зарплата | Сотрудники(S) (S.Зарплата > 10000)} – выбрать один атрибут «Зарплата» отношения «Сотрудники» для сотрудников, получающих зарплату больше 10000 руб.

{S.ФИО | Сотрудники(S) ( В) (Офис(В) (В.Таб№=S.Таб№) (В.Город=’Екатеринбург’))} – выбрать атрибут «ФИО» отношения «Сотрудники», если в отношении «Офис» существует кортеж, который имеет такое же значение атрибута «Таб№», что и значение атрибута «Таб№» в текущем кортеже S и атрибут «Город» из кортежа В имеет значение ‘Екатеринбург’, проще говоря - выбрать «ФИО» из отношения «Сотрудники», которые работают в офисе, расположенном в городе Екатеринбург.

{S.ФИО | Сотрудники(S) (Ø P)(ОбъектыНедвижимости) (S.Таб№=P.Таб№)))} - создать список всех сотрудников, которые в данный момент не работают с объектами недвижимости. Используя правила эквивалентности логических операций, это выражение можно переписать так:

{S.ФИО | Сотрудники(S) (( P)( ØОбъектыНедвижимости(P) Ø(S.Таб№=P.Таб№)))}