Парадигма развития науки (стр. 40 )

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

где —это проекция отношения на атрибуты списка .

Пример.

Включим в список матрицы М атрибуты С и D (из отношения R1), тогда в список войдут атрибуты А и В, а в список N — атрибуты С и D из отно­шения R2:

Действительно,

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

Другой подход к построению языка манипулирования данными основан на использовании моделей реляционного исчисления.

Суть этого подхода заключается в том, что желаемый результат определяется не заданием набора операций над отношениями, а путем описания требований, которым должно удовлетворять ре­зультирующее отношение. СУБД представляется самой подобрать последовательность операций, ведущих к поставленной цели. Ес­тественно, что языки, основанные на использовании моделей реля­ционного исчисления, представляют собой языки очень высокого

уровня.

Реляционное исчисление. В реляционном исчислении, так же как и в реляционной алгебре, имеется набор понятий и операций, которые позволяют записывать любое отношение в виде некоторой формулы или формального выражения (α-выражения).

Формулы в реляционном исчислении помимо арифметических операций ( = , ≠, <, ≤, >, ≥) включают дополнительные логи­ческие операции. К ним относят операции квантификации:

— квантор общности и — квантор существования.

Квантор общности читается как: «все для всех», «для каж­дого», «каков бы ни был».

Например, запись x читается «для любого х» или «для всех х».

Квантор существования читается «для некоторого», «сущест­вует хотя бы один». Например, у читается «для некоторого у» или «существует у такой, что». Кроме кванторов в реляционном исчис­лении используются логические операции: ,, .

Операция носит название логическое сложение, или дизъюнк­ция, и по смыслу соответствует слову «ИЛИ». Операция логиче­ское умножение, или конъюнкция, и соответствует слову «И». Опе­рация — операция отрицания, соответствует «НЕ». Запись R1R2 будет читаться как отношение R1 И отношение R2, запись R1R2 — «отношение R1 ИЛИ отношение R2».

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

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

Например, в формуле

переменная х связана, переменная у в отношении R1 свободна, а в R2 — связана, переменная z свободна.

Формулы в реляционном исчислении строятся из атомов и сово­купности арифметических и логических операторов. Атомы в реля­ционном исчислении представляются по-разному. В зависимости от того, что используется в качестве переменной — кортеж (строка) или атрибут (столбец). Поэтому различают реляционное исчисле­ние с переменными-кортежами и переменными-доменами.

Реляционное исчисление с переменными-кор­тежами. Выражение такого исчисления может иметь следую­щий вид:

где r —кортеж: ψ — некоторая формула исчисления. Например, выражение {r|R1(r)R2(r)}, где в качестве формулы ψ(r) исполь­зуется выражение R1(r)R2(r), означает, что необходимо полу­чить множество всех кортежей r, таких, что они принадлежат одно­временно как отношению R1, так и отношению R2. В том случае, когда в качестве переменных в реляционном исчислении использу­ются кортежи атомы, из которых конструируются формулы, они могут быть следующих типов:

1. Атом — отношение R(r), где r — кортеж в отношении R.

2. Атом — конструкция типа s[i]θv[j] или s[i]θc, где с — некото­рая константа; θ — арифметический оператор (= , ≠, <, ≤, >, ≥);

s, v — кортежи; i, j — номера (или имена) атрибутов (столб­цов) в соответствующих кортежах. Например, атом (s[l] =q[7]) означает, что первая компонента кортежа s равна седьмому кортежа q, а атом s[5]<10 означает, что пятая компонента меньше 10. Два перечисленных выше типа вида атомов являются единственными в реляционном исчислении.

Сами формулы рекурсивно конструируются из атомов по сле­дующим правилам.

1. Любой атом—это формула. Все вхождения переменных-кор­тежей, упомянутые в атоме, являются свободными.

2. Если ψ формула, то ψ — тоже формула (—символ ло­гического отрицания).

3. Если ψ1 и ψ2 формулы, то и выражения ψ1ψ2 и ψ1ψ2 так­же являются формулами. Причем свободными (связными) явля­ются те и только те вхождения переменных, которые происходят от свободных (связных) вхождений переменных ψ1 и ψ2.

4. Если ψ формула и r — свободная переменная-кортеж этой формулы, то r(ψ)) и r(ψ) также формулы, переменная в этом случае становится связанной.

5. Формулы могут при необходимости заключаться в скобки.

6. Ничто иное не является формулой.

Реляционное исчисление с переменными-доме­нами. В этом случае в качестве переменных вместо кортежей ис­пользуются домены. Реляционное исчисление с переменными на доменах строится с использованием тех же операторов, что и с пе­ременными кортежами. Но в качестве атомов формул исчисления используются следующие типы:

1. R(x1, х2, ..., хп), где R — n-арное отношение, xi — константа или переменная на некотором домене.

Атом R(x1, х2, ..., хп) указывает, что значения xi, которые явля­ются переменными, должны быть выбраны так, чтобы (x1, х2, ..., хп) было кортежем отношения.

2. хθу, где х и у — константы или переменные на некотором до­мене, θ — арифметический оператор сравнения.

В остальном формулы реляционного исчисления с переменны­ми-доменами строятся аналогично формулам исчисления с перемен­ными-кортежами.

Выражение реляционного исчисления с переменными на доменах имеет вид {х1, х2.....хп|ψ(х1, х2, ..., хn)}, где ψ — формула, облада­ющая тем свойством, что только ее свободные переменные на до­менах являются различными переменными x1, x2, ..., хп.