2014-02-02
1008
Выражение реляционного исчисления с переменными-кортежами имеет вид: { t(R) | ψ(t) }, где t – переменная-кортеж, удовлетворяющая схеме отношения R; единственная переменная, имеющая свободное вхождение в формулу ψ(t); ψ(t) – правильно построенная формула.
Интерпретация выражения реляционного исчисления: множество кортежей t, удовлетворяющих схеме отношения R, таких, для которых правильно построенная формула ψ(t) истинна.
Пример
Пусть есть отношение R(Имя, Стипендия); атрибут Стипендия определен на домене D = {«да», «нет»}. Тогда выражение
{ t(Имя) | ∃x(R) (r(x) ∧ x[ Стипендия ] = «да» ∧ x[ Имя ] = t[ Имя ]}
позволит получить из отношения имена всех студентов, получающих стипендию.
Безопасные выражения
Выражение вида { t | ¬ r(t) } в общем случае определяет бесконечное отношение, что недопустимо. Поэтому в реляционном исчислении ограничиваются рассмотрением так называемых безопасных выражений вида { t | ψ(t) }, которые гарантированно дают ограниченное множество кортежей. В таких выражениях значения атрибутов кортежей t являются элементами некоторого ограниченного универсального множества – DOM(ψ). Здесь DOM(ψ) – унарное отношение, элементами которого являются символы, которые либо явно появляются в ψ, либо служат компонентами какого-либо кортежа в некотором отношении R, упоминаемом в ψ.
В книге Дж. Ульмана [3, стр. 103 – 104], приведено следующее определение:
«Выражение { t | ψ(t) } реляционного исчисления с переменными-кортежами назовем безопасным, если выполняются следующие условия:
1. Всякий раз, когда t удовлетворяет ψ(t), каждый компонент t есть элемент DOM(ψ).
2. Для любого подвыражения ψ вида ( ∃ u) (ω(u)) каждый компонент u принадлежит DOM(ω), если u удовлетворяет ω.
3. Если для любого подвыражения ψ вида ( ∀ u) (ω(u)) каждый компонент u не принадлежит DOM(ω), то u удовлетворяет ω.
Условия 2 и 3 позволяют устанавливать истинность квалифицированной формулы ( ∃ u) (ω(u)) или ( ∀ u) (ω(u)), рассматривая только u, составленные из принадлежащих DOM(ω) символов. Например, любая формула ( ∃ u) (R(u) ∧ …) удовлетворяет условию 2, а любая формула ( ∀ u) (¬R(u) ∨ …) – условию 3.
Хотя условие 3 может показаться не интуитивным, мы должны заметить, что формула ( ∀ u) (ω(u)) логически эквивалентна формуле ¬ ( ∃ u) ( ¬ ω(u)). Последняя не является безопасной, если и только если существует некоторое u0, для которого истинно ¬ω(u0) и u0 не принадлежит домену формулы ¬ω. Так как домены ω и ¬ω одни и те же, условие 3 устанавливает, что формула ( ∀ u) (ω(u)) безопасна, когда безопасна формула ¬ ( ∃ u) ( ¬ ω(u)) …»
Эквивалентность выражений реляционной алгебры и реляционного исчисления с переменными-кортежами
В той же книге (стр. 104) доказана следующая теорема, которая здесь приводится без доказательства.
Если E – выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение реляционного исчисления с переменными-кортежами.
Ниже приводятся некоторые эквивалентности.
| Выражение реляционной алгебры | Выражение реляционного исчисления с переменными-кортежами |
| Объединение: r1 ∪ r2, r1(R), r2(R) | {x(R) | r1(x) ∨ r2(x) } |
| Разность: r1 – r2 , r1(R), r2(R) | {x(R) | r1(x) ∧ ¬r2(x) } |
| Пересечение: r1 ∩ r2, r1(R), r2(R) | {x(R) | r1(x) ∧ r2(x) } |
| Декартово произведение: r1 × r2, r1(R1), r2(R2) | {x(R1R2) | ∃u(R1) ∃v(R2) (r1(u) ∧ r2(v) ∧ x[R1] = u{r1] ∧ x[R2] = v[R2]) } |
| Проекция: πL(r), r(R), L ⊆ R | {t(L) | ∃u(R) (r(u) ∧ u[L] = t[L] } |
| Выбор: σF(r), r(R) | { t(R) | r(t) ∧ F’) } |
| Естественное соединение: r1 r2 r1(AB), r2(BC) | { t(ABC) | ∃u(AB) ∃v(BC) (r1(u) ∧ r2(v) ∧ u[B] = v[B] ∧ t[AB] = u[AB] ∧ t[C] = v[C]) } |
| Деление: r1 ÷ r2, r1(AB), r2(B) | { t(A) | ∀x(B) (r2(x) ∧ ∃y(AB) (r1(y) ∧ y[B] = x[B] ∧ y[A] = t[A] } |
Рассмотрим те же примеры запросов, которые приводились для языка реляционной алгебры.
Дана та же схема базы данных:
S(S#, SN, SC) – ПОСТАВЩИК (Номер поставщика, Имя, Город)
P(P#, PN, PC) – ДЕТАЛЬ (Номер детали, Название, Цена)
SP(S#, P#, QTY) – ПОСТАВКА ( Номер поставщика, Номер детали, Количество)
1. Получить имена поставщиков, поставляющих деталь с номером P1.
{t(SN) | ∃u(S)∃v(SP)(S(u) ∧ SP(v) ∧ u[S#] = v[S#] ∧ v[p#] = ‘P1’ ∧ u[SN] = t[SN])}
Пояснение: результат запроса – множество кортежей t, имеющих только один атрибут SN, таких, что:
• существует, по крайней мере, один кортеж из отношения S (∃u(S)… (S(u) …), и
• существует, по крайней мере, один кортеж из отношения SP (…∃v(SP)(… SP(v) …),
такие, что
• значения этих кортежей по атрибуту S# совпадают (u[S#] = v[S#]),
• значение кортежа v по атрибуту P# определяет интересующую нас деталь P1 (v[p#] = ‘P1’), и
• кортеж u определяет результат запроса (u[SN] = t[SN]).
2. Получить имена поставщиков, не поставляющих деталь с номером P1.
{t(SN) | ∃u(S)(S(u) ∧¬∃v(SP) (SP(v) ∧ v[P#] = ‘P1’ ∧ u[S#] = v[S#] ∧ u[SN] = t[SN]))}
Т.е. для кортежа из отношения S, определяющего результат запроса, не найдется кортеж из отношения SP, имеющий такое же значение по атрибуту S# и определяющий деталь P1.
3. Получить имена поставщиков, поставляющих только деталь с номером P1.
Этот запрос, по сути, объединяет два предыдущих: т.е. определяются кортежи, соответствующие поставляемой детали P1, и их этих кортежей удаляются те, которые соответствуют поставке других деталей.
{t(SN) | ∃u(S)∃v(SP)(S(u) ∧ SP(v) ∧ u[S#] = v[S#] ∧ v[P#] = ‘P1’ ∧ u[SN] = t[SN] ∧
¬∃w(SP)(SP(w) ∧ w[S#] = u[S#] ∧ w[P#] ≠ ‘P1’))}
4. Получить имена поставщиков, поставляющих все детали.
Поскольку этот запрос реализуется операцией деления реляционной алгебры, воспользуемся приведенной выше эквивалентностью. Рассмотрим сначала запрос, позволяющий получить номера поставщиков, поставляющих все детали.
{t(S#) | ∀w(P)∃u(SP)(P(w) ∧ SP(v) ∧ w[P#] = v[P#] ∧ t[S#] = v[S#])}
Теперь добавим в этот запрос конструкции, необходимые для получения имени поставщика из отношения S.
{t(SN) | ∃u(S)∀w(P)∃u(SP)(S(u) ∧ P(w) ∧ SP(v) ∧ w[P#] = v[P#] ∧ u[S#] = v[S#] ∧ t[SN] = u[SN])}
Реляционное исчисление с переменными на доменах
Выражение реляционного исчисления с переменными на доменах строится с использованием тех же средств, что и выражение реляционного исчисления с переменными-кортежами. Отличие состоит в том, что здесь областью определения являются домены.
Здесь также строится правильно определенная формула, основой которой являются атомы.
I. Атомы имеют следующий вид:
a. r(x1x2…xn), где r – отношение, удовлетворяющее схеме R(A 1 A 2 …A n), и каждое x i есть константа или переменная на домене;
b. u θ v, где u и v – константы или переменные, определенные на доменах, совместимых по операции θ, θ – арифметическая операция сравнения (<, =, >, ≥, ≠, ≤);
II. Формула реляционного исчисления ψ(t), а также свободные и связанные вхождения переменных определяются так же, как и для исчисления с переменными-кортежами.
Эквивалентность выражений реляционного исчисления с переменными-кортежами и исчисления с переменными на доменах
Выражение исчисления с переменными на доменах, эквивалентное выражению исчисления с переменными-кортежами { t | ψ(t) }, конструируется в соответствии со следующими правилами.
Пусть есть переменная-кортеж t(R), где R = (A1A2…An) имеет арность n. Тогда вместо переменной-кортежа t вводятся n новых переменных на доменах t1, t2, …, tn, и заданное выражение исчисления с переменными-кортежами заменяется выражением {t1, t2, …, tn | ϕ΄(t1, t2, …, tn)}. Здесь ϕ΄ представляет собой ϕ, в которой:
• любой атом r(t) заменяется атомом r(t1, t2, …, tn);
• каждое свободное вхождение t[Ai] заменено переменной ti;
• для каждого квантора ∃u или ∀u вводится m новых переменных u1, u2, …, um, где m – арность u. Кванторы ∃u (или ∀(u)) заменяются кванторами ∃u1 ∃u2 … ∃um (∀u1 ∀u2 … ∀um, соответственно), и в подчиненных кванторам выражениях u[Ai] заменяются ui, а r(u) – r(u1, u2, …, um).
